绝密 ★ 考试结束前
全国2013年10月高等教育自学考试
数据结构导论试题
课程代码：02142
请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分
注意事项：
1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1．下列几种算法时间复杂度中，最大的是 A．O（1） C.O（nlog2n）
B.O（n） D.O（n2）
2．数据结构中结点按逻辑关系依次排列形成一条“链”的结构是 A．集合 C.树形结构
B.图结构 D.线性结构
3．在表长为100的顺序表中做插入运算，平均移动元素的次数为 A．25 C.50
B.33 D.100
4．已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为 A．O（1） C.O（n）
5．下列表述正确的是
A．栈空时出栈产生“上溢”，栈满时进栈产生“下溢” B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢” C.栈空时出栈和栈满时进栈均产生“上溢” D.栈空时出栈和栈满时进栈均产生“下溢” 6.队列操作的原则是
B.O（log2n） D.O(n2)
A.先进先出 C.先进后出
7．一棵深度为6的满二叉树有 A．63个结点 C.127个结点
B.后进先出 D.只进不出
B.64个结点 D.128个结点
8.在一棵度为3的树中，度为3的结点有4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有 A.8个 C.11个
B.10个 D.12个
9．一棵二叉树T，度为2的结点数为20个，则叶子结点数为 A．19个 C.21个
10．有10个叶结点的哈夫曼树中共有 A．10个结点 C.19个结点
B.11个结点 D.21个结点 B.20个 D.22个
11．求图中两个结点之间的最短路径采用的算法是 A．广度优先搜索（BFS）算法 C.普里姆（Prim）算法
12．顺序查找算法的平均查找长度为 A．log2n C.n/2
13．二叉排序树中，根的
A．左子树是二叉排序树、右子树不一定是二叉排序树 B.左子树是二叉排序树、右子树也是二叉排序树 C.左子树不一定是二叉排序树、右子树是二叉排序树
D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树 14．冒泡排序的时间复杂度为 A．O(n) C.O(n2)
15．关于稳定性的表述，正确的是
A．稳定性是排序方法本身的特性，与数据无关 B.稳定性不是排序方法本身的特性，与数据有关 C.稳定性是排序方法本身的特性，与数据有关 D.稳定性不是排序方法本身的特性，与数据无关
B.O(nlog2n) D.O(log2n) B.（n-1）/2 D.（n+1）/2
B.克鲁斯卡尔（Kruskal）算法 D.迪杰斯特拉（Dijkstra）算法
非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题(本大题共13小题，每小题2分，共26分) 16．数据中不可分割的最小标识单位是___数据项_______。
17．双向循环链表中，在p所指结点的后面插入一个新结点*t，需要修改四个指针，分别为：t->prior=p；__t->next=p->next________；p->next->prior=t；p->next=t；。
18.在带有头结点的循环链表中，头指针为head，判断指针p所指结点为首结点的条件是_p==head->next;_________。 19．元素的进栈次序为1，2，3，…，n，出栈的第一个元素是n，则第k个出栈的元素是__n-k+1________。 20．在栈结构中，允许插入和删除的一端称为___栈顶_______。
21．100个结点的二叉树采用三叉链表存储时，空指针域NULL有___102_______个。
22.某二叉树的先序遍历序列为ABKLMNO，中序遍历序列为BLKANMO，则该二叉树中结点A的右孩子为结点__m______。
23．一个二叉树的最少结点个数为_____0_____。
24．图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为_____简单回路____。
25．设查找表有n个数据元素，则二分查找算法的平均查找长度为___(n+1)/2 log2(n+1) -1 _______。 26．用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为___散列表_______。
27．若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用___顺序_______存储结构。 ?k?k2i?n?(i?1,2,?,??)，28．堆分为最小堆和最大堆，若键值序列{k1,k2,…，kn}，满足?i则这n个键值序列{k1,k2,…，
k?k2???i2i?1kn}是___最大堆_______。
三、应用题(本大题共5小题，每小题6分，共30分)
29．设一个链栈的输入序列为X，Y，Z，试写出出栈的所有可能的输出序列及其操作步骤。
30．设二叉树的先序遍历序列为DCBAHEIFG，中序遍历序列为ABCHDIEFG，试画出该二叉树并写出后序遍历序列。
31．已知连通带权图如题31图所示，试利用普里姆（Prim）算法，从顶点A出发，构造它的最小生成树，画出构造过程。