全国2012年10月高等教育自学考试数据结构导论试题及答案

1、20122012版教材201210数据结构导论试题02142一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。下面几种算法时间复杂度阶数中，值最大的是A.O(nlog2n)C.O(n)D.O(2n)这种算法好坏的评价因素称为正确性B.易读性C.健壮性D.时空性10040个元素之后插入一个元素所需移动元素的个数为A.40B.60C.61D.100解法：41 至 100 共需要移动 60 次设带头结点的单循环链表head，则判断该链表是否为空的条件是A. head-next=headB. head-nex

2、t=NULLC. head!=NULLD. head=NULL 5.在链栈的运算中，不需要判断栈是否为空的是出栈进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是 则该队列的输出序列A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A以行序为主序的二维数组 中，第一个元素 1002 a12的存储地址是A.100B.108C.114D.116解法：loci,j=loc(0,0)+(n*i+j)*k = 100+(5*1+2)*2=14T5 2 的结点个数为A.4B.5C.6D.无法确定解法：n0=n2+1 就有 5=x+19.m 个叶结点的哈夫曼树中，其结点总数为

3、A.mB.2m+1C.2mD.2m-1解法：2m-1二叉树的中序遍历序列中，结点P Q 之前的条件是在二叉树中P 在Q 的左边在二叉树中P 在Q 的右边C.在二叉树中P 是Q 的祖先D.在二叉树中P 是Q 的子解法：中顺遍历顺序：左中右10 个顶点的无向完全图的边数是A.11B.45C.55D.90解法：n(n-1)2 = 10（10-1）2 =45在带权有向图中求两个结点之间的最短路径可以采用的算法是迪杰斯特拉（Dijkstra）算法克鲁斯卡尔算C.普里姆（Prim）算法D.深度优先搜索（DFS）算法13.二分查找（Binary Search）算法的时间复杂度是B.O（nlog2n）C.O（

4、n）14.在一棵初始时为空的二叉树中，依次插入键值序列 50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素 60 要进行的比较次数是A.2B.3C.4D.5解法：画二叉树后得出：50726560 15.快速排序属于插入排序交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题(本大题共 13 小题，每小题 2 分，共 26 分)下面算法程序段的时间复杂度为 O(n3) for (i=1; i=n; i+)for (j=1; j=n; j+) for (k=1;knext=p-ne

5、xt-next。在带有头结点的单链表head 中，首结点的指针为head-next。在栈结构中，允许插入和删除的一端称为栈顶。21.C 程序中，将对称矩阵的下三角元素压缩存储到n(n+1)/2 个元素的一维数组M 中设a （存放在数组中则k 的（用i,j表示为 k = i(i+1)/2+ 22.具有64 个结点的完全二叉树的深度为log(2，n)+1=6+1=7。JLKANMOA 的右子树中的结点个数为3 个分别为。三个顶点v1,v2,v3 的图的邻接矩阵为则该图中顶点v2 的出度为即v2行之和)。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称简单回路或简环。在顺序查找、二分查找、

6、散列查找和索引顺序查找四种查找方法中，平均查找长度与素个数没有关系的查找方法是散列查找。堆排序算法的时间复杂度为_ O(nlog2n)。28.如果要将序列60，18，28，69，99，75，78建成堆，则只需把60 与18(最小堆) 相互交换。三、应用题(本大题共 5 小题，每小题 6 分，共 30 分)29.如题 29 的所有输出序列，并给出每个序列的操作过程（push（A）A 进栈，pop(A)A 出栈）。题 29 图解：push(A),pop(A),push(B),pop(B),push(C),pop(C) 输出序列为：ABCpush(A),push(B),pop(B),pop(A),p

7、ush(C),pop(C) 输出序列为：BACpush(A),push(B),push(C),pop(C),pop(B),pop(A) 输出序列为：CBApush(A),pop(A),push(B),push(C),pop(C),pop(B) 输出序列为：ACBpush(A),push(B),pop(B),push(C),pop(C),pop(A) 30.30 图所示的一棵树转换为对应的二叉树。解：题 30 图 31 表示的连通带权图及该连通带权图的最小生成树。题 31 图解：联通图最小生成树32 110 中的数，试标出各结点的数值。题 32 图 mod 11(mod )，给出键值序列为66,13,41,15,44,6,68,17,26,31,39,46, 概率情况下查找成功时的平均查找长度。四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分)带头结点的单链表的结点结构如下：typedef struct n