最新2012版教材
全国2012年10月高等教育自学考试
数据结构导论试题 课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的。错选、多选或未选均无分。 1.下面几种算法时间复杂度阶数中，值最大的是
A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) 2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为
A.正确性 B.易读性 C.健壮性 D.时空性
3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为 A.40 B.60 C.61 D.100 解法：41至100共需要移动60次
4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要判断栈是否为空的是
A.出栈 B.进栈
C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A
C.D，C，B，A D.C，D，B，A
7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是
A.100 B.108 C.114 D.116
解法：loc[i,j]=loc(0,0)+(n*i+j)*k = 100+(5*1+2)*2=14
8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5
C.6 D.无法确定 解法：n0=n2+1 就有5=x+1
9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1 C.2m D.2m-1 解法：2m-1
10.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是
A.在二叉树中P在Q的左边 B.在二叉树中P在Q的右边 C.在二叉树中P是Q的祖先 D.在二叉树中P是Q的子孙 解法：中顺遍历顺序：左中右 11.有10个顶点的无向完全图的边数是
最新2012版教材
A.11 B.45
C.55 D.90 解法：n(n-1)÷2 = 10（10-1）÷2 =45
12.在带权有向图中求两个结点之间的最短路径可以采用的算法是
A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆（Prim）算法 D.深度优先搜索（DFS）算法 13.二分查找（Binary Search）算法的时间复杂度是 A.O（n2） B.O（nlog2n） C.O（n） D.O（log2n）
14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是 A.2 B.3 C.4 D.5 解法：画二叉树后得出：50→72→65→60
15.快速排序属于
A.插入排序 B.交换排序 C.选择排序 D.归并排序
非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题(本大题共13小题，每小题2分，共26分) 16.下面算法程序段的时间复杂度为___O(n^3)___。 for (i=1; i<=n; i++) for (j=1; j<=n; j++)
for (k=1;k<=n;k++) x++；
17.所有存储结点存放在一个连续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。这种存储方式是__顺序存储方式____。
18.单链表中指针p指向结点A，若要删除A之后的结点（存在且不释放存储空间），则需要修改指针的操作为p->next=p->next->next______。
19.在带有头结点的单链表head中，首结点的指针为__head->next____。
20.在栈结构中，允许插入和删除的一端称为__栈顶____。
21.C程序中，将对称矩阵A［n］［n］的下三角元素压缩存储到n(n+1)/2个元素的一维数组M中，设［ai］［j］（i≥j）存放在数组M［k］中，则k的值（用i,j表示）为___k = i(i+1)/2+j___。 22.具有64个结点的完全二叉树的深度为____∟log(2，n)」+1=6+1=7_____。
23.某二叉树的先序遍历序列为AJKLMNO，中序遍历序列为JLKANMO，则根结点A的右子树中的结点个数为__3个分别为：NMO____。 24.三个顶点v1,v2,v3的图的邻接矩阵为，则该图中顶点v2的出度为__2(即v2行之和)____。 25.除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为___简单回路或简单环___。
最新2012版教材
26.在顺序查找、二分查找、散列查找和索引顺序查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是__散列查找____。 27.堆排序算法的时间复杂度为_ O(nlog2n)_____。
28.如果要将序列{60，18，28，69，99，75，78}建成堆，则只需把60与__18(最小堆)____相互交换。
三、应用题(本大题共5小题，每小题6分，共30分)
29.如题29图所示，在栈的输入端依次输入元素A，B，C，试写出在栈的输出端可以得到的所有输出序列，并给出每个序列的操作过程（用push（A）表示A进栈，pop(A)表示A出栈）。
题29图
解：
1.push(A),pop(A),push(B),pop(B),push(C),pop(C) 输出序列为：ABC 2.push(A),push(B),pop(B),pop(A),push(C),pop(C) 输出序列为：BAC 3.push(A),push(B),push(C),pop(C),pop(B),pop(A) 输出序列为：CBA 4.push(A),pop(A),push(B),push(C),pop(C),pop(B) 输出序列为：ACB 5.push(A),push(B),pop(B),push(C),pop(C),pop(A) 输出序列为：BCA 30.将题30图所示的一棵树转换为对应的二叉树。 解：
题30图
31.已知含五个顶点A，B，C，D，E的连通带权图的邻接矩阵如题31图所示，试画出它所表示的连通带权图及该连通带权图的最小生成树。
题31图
解：联通图最小生成树
32.题32图所示二叉排序树的各结点的值为1~10中的数，试标出各结点的数值。
题32图
33.设散列函数H（key）=key mod 11(mod表示求余运算)，给出键值序列为
66,13,41,15,44,6,68,17,26,31,39,46,用链地址法解决冲突，试画出相应的散列表，并计算在等概率情况下查找成功时的平均查找长度。
四、算法设计题(本大题共2小题，每小题7分，共14分) 34. 带头结点的单链表的结点结构如下： typedef struct node { int data;
struct node *next; }Node,*LinkList;
试编写单链表的删除运算算法void DeleteLinklist( LinkList head，int i) 35.写出直接选择排序算法。