数据结构试卷A(2012专升本).doc

线订装郑州轻工业学院 / 学年 第 学期 试卷专业年级及班级姓名学号2012-2013学年第一学期期末考试试卷数据结构试卷A 一、选择题（每题2分，共30分）1一种抽象数据类型包括数据对象、数据关系和【 】三部分。A数据抽象 B基本操作 C数据元素 D类型说明2在一个长度为n的顺序表中插入一个元素的算法的时间复杂度为【 】。AO（1）B（log n）CO（n）DO（n2）3. 指针p1和p2分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为【 】。Ap1next=p2next; p2next=p1next;Bp2next=p1next; p1next=p2next;Cp=p2next; p1next=p; p2next=p1next;Dp=p1next; p1next= p2next; p2next=p;4设栈的初始状态为空，入栈序列为1，2，3，4，5，6，若出栈序列为2，4，3，6，5，1，则操作过程中栈中元素个数最多时为【 】。A2个B3个C4个D6个5队列的特点是【 】。A允许在表的任何位置进行插入和删除B只允许在表的一端进行插入和删除C允许在表的两端进行插入和删除D只允许在表的一端进行插入，在另一端进行删除6设有一个二维数组A1020，按行存放于一个连续的存储空间中，A00的存储地址是200，每个数组元素占1个存储字节，则A62的地址为【 】。A226 B322 C341 D342线订装郑州轻工业学院 / 学年 第 学期 试卷专业年级及班级姓名学号7递归过程或函数调用时，处理参数及返回地址，要用一种称为【 】的数据结构。A队列 B多维数组 C栈 D线性表8在各种查找方法中，平均查找长度与结点个数n无关的查找方法是【 】。A折半查找 B二叉排序树查找 C散列查找 D顺序查找9对有序表进行折半查找成功时，元素比较的次数【 】。A仅与表中元素的值有关 B仅与表的长度和被查元素的位置有关C仅与被查元素的值有关 D仅与表中元素按升序或降序排列有关10快速排序执行两趟之后，已经到位的元素个数是【 】。A1B3CD11下列序列不为堆的是【 】。 A75, 45, 65, 30, 15, 25 B75, 65, 45, 30, 25, 15 C75, 65, 30, l5, 25, 45 D75, 45, 65, 25, 30, 1512森林转换为二叉树后，从根结点开始一直沿着右子树下去，一共有4个结点，表明【 】。A 森林有4棵树 B 森林的最多深度为4C 森林的第一棵树有4层 D森林有4个结点13关键路径是AOE网中【 】。A从始点到终点的最短路径 B从始点到终点的最长路径 C从始点到终点的边数最多的路径 D从始点到终点的边数最少的路径14有数据57，35，40，19，45，24，100，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下面哪个序列插入【 】。A45，24，57，19，40，100，35 B40，24，19，35，57，45，100 C19，24，35，40，45，57，100 D35，24，19，40，45，100，5715下列哪一个选项不是图1所示的有向图的拓扑排序的结果【 】。BACDEFAAFBCDE BFABCDECFACBDE DFADBCE图1二、应用题（6题，共50分）1（4分）线性表有两种存储结构：一是顺序表，而是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动的改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，其很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 2.（8分）已知一棵二叉树的中序遍历结果为GDHBAECIF，后序遍历结果为GHDBEIFCA，请画出该二叉树，并写出其先序遍历序列3(12分）根据下图所示的无向带权图回答下列问题：（1）写出它的邻接矩阵（按照字母序依次存放）。（2）画出其最小生成树（给出生成最少生成树过程的示意图）。（3）给出从顶点a出发深度优先搜索和广度优先搜索遍历该图的顶点序列（多个顶点可以选择按字母序）。4.（10分） 假定用于通信的电文仅有8个字母C1，C2，.，C8组成，各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4，试为这8个字母设计哈夫曼编码树，并计算该哈夫曼树的带权路径长度WPL。5（10分）设有一组关键字29, 1, 13, 15, 56, 20, 87, 27, 69, 9, 10, 74。哈希函数为H（key)=key%17，采用线性探测法解决冲突。试在0-18的哈希地址空间中对该关键字序列构造哈希表，并计算成功查找的平均查找长度。6（6分）将下面的二叉树转换为一棵树。三、编程题（2题，每题10分，共20分）1（5分）在顺序表中求值为X的元素个数。typedef structelemtype *elem;int length;int listsize;SqList; int Count_Num(SqList L,elemtype X)int n=0; （请完成）return n;2（7分）设在一个带表头结点的单链表中所有元素结点的数据值按递增顺序排列，试完成下列函数，删除表中所有大于min，小于max的元素（若存在）。 typedef struct LNode ElemType data; struct LNode *next; LNode，*LinkList; void rangeDelete (LinkList L, ElemType min, ElemType max ) LNode * pr ，*p ； pr = L，p= L-next； （请完成） 3. （8分）给出算法分别求出二叉树的叶结点、度为1的结点、度为2的结