全国2012年10月高等教育自学考试
数据结构试题
课程代码：02331
请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分
注意事项：
1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。
一、单项选择题(本大题共l5小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个算法的时间耗费的数量级称为该算法的 A．效率 C．可实现性 2．顺序表便于 A．插入结点 C．按值查找结点
B．删除结点 D．按序号查找结点 B．难度 D．时间复杂度
3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p->next->next==head C．p->next->next==NULL
B．p->next==head D．p->next==NULL
4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为
A．(rear-front+m)％m C．(front-rear+m)％m
5．下列关于顺序栈的叙述中，正确的是
A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空 D．入栈操作不需要判断栈满，出栈操作不需要判断栈空
- 本套试题共分10页，当前页是第1页-
B．rear-front+1 D．(rear-front)％m
6．A是一个10×10的对称矩阵，若采用行优先的下三角压缩存储，第一个元素a0,0的存储地址为1，每个元素占一个存储单元，则a7,5的地址为 A．25 C．33
7．树的后序遍历等价于该树对应二叉树的 A．层次遍历 C．中序遍历
8．使用二叉线索树的目的是便于 A．二叉树中结点的插入与删除 C．确定二叉树的高度
B．在二叉树中查找双亲 D．查找一个结点的前趋和后继 B．前序遍历 D．后序遍历 B．26 D．34
9．设无向图的顶点个数为n，则该图边的数目最多为 A．n-l C．n(n+1)／2
10．可进行拓扑排序的图只能是 A．有向图 C．有向无环图 11．下列排序方法中稳定的是 A．直接插入排序 C．堆排序 12．下列序列不为堆的是 ．． A．75,45,65,30,15,25 C．75,65,30,l5,25,45
B．75,65,45,30,25,15 D．75,45,65,25,30,15 B．直接选择排序 D．快速排序 B．无向图 D．无向连通图 B．n(n-1)／2 D．n2
13．对线性表进行二分查找时，要求线性表必须是 A．顺序存储
C．顺序存储且按关键字有序
B．链式存储
D．链式存储且按关键字有序
14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同 ．． 的序列是 A．(4,1,2,3,5) C．(4,5,2,1,3)
B．(4,2,3,l,5) D．(4,2,1,5,3)
15．下列关于m阶B树的叙述中，错误的是 ．． A．每个结点至多有m个关键字 B．每个结点至多有m棵子树
C．插入关键字时，通过结点分裂使树高增加 D．删除关键字时通过结点合并使树高降低
非选择题部分
- 本套试题共分10页，当前页是第2页-
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题(本大题共10小题，每小题2分，共20分) 16．数据元素之间的逻辑关系称为数据的______结构。 17．在线性表中，表的长度定义为______。
18．用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1、2、3、4，为了得到 1、3、4、2的出栈顺序，相应的S和X的操作序列为______。 19．在二叉树中，带权路径长度最短的树称为______。
20．已知广义表G，head(G)与tail(G)的深度分别为4和6，则G的深度是______。
21．一组字符(a,b,c,d)在文中出现的次数分别为(7，6，3，5)，字符＇d＇的哈夫曼编码的长度为______。 22．在一个具有n个顶点的无向图中，要连通全部顶点至少需要______条边。 23．直接选择排序算法的时间复杂度是______。
24．对于长度为81的表，若采用分块查找，每块的最佳长度为______。 25．用二叉链表保存有n个结点的二叉树，则结点中有______个空指针域。 三、解答题(本大题共4小题，每小题5分，共20分)
26．假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一 个位置，队头指针指向队头元素)，初始状态Q.front=Q.rear=0；写出依次执行 下列操作后头、尾指针的当前值。
a,b,c,d,e,f入队，a,b,c,d出队； (1) Q.front=______；Q.rear=______。 g,h,i,j,k,l入队，e,f,g,h出队； (2) Q.front=______；Q.rear=______。 M,n,o,P入队， i,j,k,l,m出队； (3) Q.front=______；Q.rear=______。
27．已知一个无向图如题27图所示，以①为起点，用普里姆(Prim)算法求其最小生成树，画出最小生成树的构
造过程。
28．用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序，问： (1)一共需要几趟归并可完成排序。 (2)写出第一趟归并后数据的排列次序。
- 本套试题共分10页，当前页是第3页-