《数据结构考试题5》由会员分享，可在线阅读，更多相关《数据结构考试题5（8页珍藏版）》请在金锄头文库上搜索。
1、要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写 上姓名和学号。一、单项选择题(每小题2 分，共20 小题，共计40 分)1. 某算法的空间复杂度为0(1)，则。A. 该算法执行不需要任何辅助空间B. 该算法执行所需辅助空间大小与问题规模n无关C. 该算法执行不需要任何空间D. 该算法执行所需全部空间大小与问题规模n无关2. 在长度为n的顺序表中插入一个元素，对应算法的时间复杂度为。A. O(1)B.O(log2n)C.O(n)D.O(n2)3. 设线性表中有n个元素，以下运算中，在单链表上实现要比在顺序表上实现效率更高。A. 删除指定位置元素的后一个元素B. 在最后
2、一个元素的后面插入一个新元素C. 顺序输出前k个元素D. 交换第i个元素和第n-i+1个元素的值(i=1, 2,，n)4. 以下数据结构中元素之间为非线性关系的。A.栈B.队列C.线性表D.以上都不是5. 若一个栈用数组data1.n存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是。A. top+;datatop=x;B.datatop=x;top+;C.top-;datatop=x;D.datatop=x;top-;6. 若某循环队列有队首指针front和队尾指针rear，在队不满时进队操作仅会改变。A.frontB.rearC.front 和 rear D.以上都不队7. 设
3、循环队列中数组的下标是0N-1,其队头、队尾指针分别为f和r(f指向队首元素的前一位置，r指向队尾元素)，则其元素个数为。A.r-fB.r-f-1C.(r-f)N+1D.(r-f+N)N8. 设树T的度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中的叶子结点个数。A.5B.6C.7D.89. 一棵哈夫曼树中共有199个结点，它用于多少个字符的编码。A.99B.100C.101D.19910. 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为a、b、c、，将森林F转换为一颗二叉树B,则二叉树B根结点的左子树上的结点个数是A.a-1B.aC. a+b+cD.b+c+d1
4、1. 下列关于图的叙述中，正确的。I 回路是简单路径II 存储稀疏图，用邻接矩阵比邻接表更省空间III若有向图中存在拓扑序列，则该图不存在回路A.仅 IIB.仅 I、IIC.仅IIID.仅 I、III12. 以下关于有向图的说法中，正确的 。A. 强连通图是任何顶点到其他所有顶点都有边B. 完全有向图一定是强连通图C. 有向图中任一顶点的入度等于出度D. 有向图边集的子集和顶点集的子集可构成原有向图的子图13. 无向图的邻接矩阵是一个。A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵14. 如果从无向图的任一顶点出发进行一次广度优先遍历即可访问所有顶点，则该图A.完全图B.连通图C.有回路D.
5、棵树15. 用Dijkstra算法求一个带权有向图G中从顶点0出发的最短路径，在算法执行的某 时刻，S=0,2,3,4，下一步选取的目标顶点可能 。A.顶点2B.顶点3C.顶点4D.顶点716 .哈希表中出现冲突是指。A. 两个元素具有相同的序号B. 两个元素的关键字不同，而其他属性相同C. 数据元素过多D. 两个元素的关键字不同，而对应的哈希函数值(存储地址)相同17. 适合于折半查找的数据组织方式。A.以链表存储的线性表B.以顺序表存储的任意线性表C.以链表存储的有序线性表D.以顺序表存储的有序线性表18. 对有n个记录的表进行直接插入排序，在最好情况下需比 次关键字。A.n-1B.n+1
6、C.n/2D.n(n-1)/219. 若数据元素序列11,12,15,7,8,9,23,1,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能。A.冒泡排序B.直接插入排序C.选择排序D.二路归并排序20. 对一组数据(25,84,21,47,15,27,68,35,20)进行排序，前 3 趟的排序结果如下： 第 1 趟：20， 15， 21， 25， 47， 27， 68， 35， 84第 2 趟：15 ，20 ，21 ，25， 35 ，27，47， 68， 84第 3 趟：15 ，20 ，21 ，25， 27，35 ，47， 68， 84则所采用的排序方法是。A.简单选择排
7、序B.希尔排序C.二路归并排序D.快速排序二、问答题（共4小题，共计35 分）注意：按求解的顺序给出最小生成1. （10 分）对于如图1所示的带权无向图，直接给出利用普里姆算法（从顶点0开始 构造）和克鲁斯卡尔算法构造出的最小生成树的结果树的所有边，每条边用（i, j）表示2. （10 分）假设一棵二叉排序树的关键字为单个字母，其后序遍历序列为 ACDBFIJHGE， 回答以下问题：（1）画出该二叉排序树。（6 分）（2）求在等概率下的查找成功的平均查找长度。（2 分）（3）求在等概率下的查找不成功的平均查找长度。（2 分）3. （8 分）已知序列15,5,16,2,25,8,20,9,18,
8、12，给出采用二路归并排序法对该序列作 升序排序时的每一趟的结果。4. （7 分）简要回答下列关于堆排序中堆的一些问题：（1）通常堆采用顺序还是链式存储结构？（3 分）（2）设有一个小根堆，即堆中任意结点的关键字均小于它的左孩子和右孩子的关键字 其中具有最大关键字的结点可能在什么地方？（4 分）三、算法设计题（共2 小题，共计25 分）1. （10分）某带头结点的非空单链表L中所有元素为整数，结点类型定义如下：typedef struct node int data;struct node *next; LinkNode;设计一个尽可能高效的算法，将所有小于零的结点移到所有大于等于零的结点的前
9、面。2. （15分）假设二叉树中有n个结点，每个结点值为单个字符，而且所有结点值均不 相同，采用二叉链存储结构存储，其结点类型定义如下：typedef struct node char data;struct node *lchild,*rchild; BTNode;请完成以下任务：（1）设计一个算法，在二叉树b中查找x结点（指结点值为x的结点），若找到该结 点，返回其地址，否则返回NULL。给出你设计的算法的时间复杂度。（8分）（2）设计一个算法，利用（1）小题设计的算法输出二叉树b中x结点的所有子孙结 点值。（7 分）“数据结构”考试试题（A）参考答案一、单项选择题（每小题2 分，共20
10、小题，共计40 分）1. B2. C3. A4. D5. C6. B7. D8. D9. B10. A11. C12. B13. A14. B15. D16. D17. D18. A19. B20. D二、问答题（共4小题，共计35 分）1. （10 分）答案：利用普里姆算法从顶点0 出发构造的最小生成树为：（0,1），（0,3），（1,2），（2,5），（5,4）， （5 分）。利用克鲁斯卡尔算法构造出的最小生成树为： （0,1），（0,3），（1,2），（5,4），（2,5） ，（5 分）。说明：顺序错误不给分。2. （10 分）答案：（1）该二叉排序树的后序遍历序列为ACDBFIJHGE
11、，则中序遍历序列为ABCDEFGHJ,由后序序列和中序序列构造的二叉排序树如图2 所示。（6 分）（2）ASL =（1x1+2x2+4x3+2x4+1x5）/10=3。（2 分）成功（3）ASL 、=（6x3+3x4+2x5）/11=40/11=3.64（2 分）不成功3.（8 分）答案：采用二路归并排序法排序的各趟结果如图3所示。（每趟2分）排序前：15,5, 16,2, 25,& 20,9, 18,12leng th=1:5, 15,2, 16,8, 25,9, 20,12,18 leng th=2:2, 5,15, 16,8, 9, 20,25,12,18 leng th=4:2, 5,
12、8,9, 15,16,20,25,12,18length=8:2； 5,8,9； 12,15,16,18,20,25排序后：2, 5,8,9, 12,15,16,18,20,25图 3 各趟排序结果4. （7 分）答案：（1）通常堆采用顺序存储结构。（3 分）（2）小根堆中具有最大关键字的结点只可能出现在叶子结点中。因为最小堆的最小关 键字的结点必是根结点，而最大关键字的结点由偏序关系可知，只有叶子结点可能是最大 关键字的结点。（4 分）三、算法设计题（共2 小题，共计25 分）1. （10分）答案：void Move(LinkNode *&L) LinkNode *p=L-next,*pre
13、=L;while (p!=NULL & p-datanext; while （p!=NULL） f （p-datanext=p-next;从链表中删除*卩结点p-next=L-next; /将*卩结点插入到头结点之后L-next=p;p=pre-next;/p指向*pre之后结点，pre不变else若*p结点值不小于0 pre=p;/pre、p 同步后移一个结点p=p-next;2. （15 分）答案（1）（7 分）BTNode *Findx(BTNode *b,char x)/在二叉树 b 中查找 x 结点 BTNode *p;if (b=NULL)return NULL;else if (
14、b-data=x)return b;p=Findx(b-lchild,x);if (p!=NULL)return p;return Findx(b-rchild,x);算法的时间复杂度为0(n) (1分)。( 2)( 7 分)void Sons(BTNode *b,char x)/输出 x 结点的子孙，初始时 b 指向 x 结点 if (b!=NULL) if (b-data!=x)printf(%c ,b-data);Sons(b-lchild,x);Sons(b-rchild,x);void OutSons(BTNode *b,char x) /输出二叉树 b 中 x 结点的所有子孙结点值 BNode *p= Findx(b,x);if (p!=NULL)Sons(p,x);
