2011 年 1 月全国高等教育自学考试数据结构导论真题
一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号
内。错选、多选或未选均无分。
1.在顺序表中查找第 i 个元素,时间效率最高的算法的时间复杂度为(
)
A.O(1)
B.O( )
C.O(log2n)
D.O(n)
2.树形结构中,度为 0 的结点称为(
)
A.树根
B.叶子
C.路径
D.二叉树
3.已知有向图 G=(V,E),其中 V={V1,V2,V3,V4,V5,V6,V7},E={,,,
,,,,,,},则图 G 的拓扑序列是(
)
A.V1,V3,V4,V6,V2,V5,V7
B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V4,V5,V2,V6,V7
D.V1,V2,V5,V3,V4,V6,V7
4.有关图中路径的定义,表述正确的是(
)
A.路径是顶点和相邻顶点偶对构成的边所形成的序列
B.路径是不同顶点所形成的序列
C.路径是不同边所形成的序列
D.路径是不同顶点和不同边所形成的集合
5.串的长度是指(
)
A.串中所含不同字母的个数
B.串中所含字符的个数
C.串中所含不同字符的个数
D.串中所含非空格字符的个数
6.组成数据的基本单位是(
)
A.数据项
B.数据类型
C.数据元素
D.数据变量
7.程序段 i=n;x=0;do{x=x+5*i;i--;}while (i>0);的时间复杂度为(
)
A.O(1)
B.O(n)
C.O(n2)
D.O(n3)
8.与串的逻辑结构不同的数据结构是(
)
A.线性表
B.栈
C.队列
D.树
9.二叉树的第 i(i≥1)层上所拥有的结点个数最多为(
)
A.2i
B.2i
C.2i-1
D.2i-1
10.设单链表中指针 p 指向结点 A,若要删除 A 的直接后继,则所需修改指针的操作为
(
)
A.p->next=p->next->next
B.p=p->next
C.p=p->next->next
D.p->next=p
11.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是(
)
A.堆排序
B.冒泡排序
C.直接插入排序
D.快速排序
12. 设 字 符 串 S1= ″ ABCDEFG ″ , S2= ″ PQRST ″ , 则 运 算
S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后 S 的结果为(
)
A.″BCQR″
B.″BCDEF″
C.″BCDEFG″
D.″BCDEFEF″
13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为 A,并且 A 的左
孩子的平衡因子为-1,右孩子的平衡因子为 0,则使其平衡的调整方法为(
)
A.LL 型
B.LR 型
C.RL 型
D.RR 型
14.如果结点 A 有 3 个兄弟结点,而且 B 为 A 的双亲,则 B 的度为(
)
A.1
B.3
C.4
D.5
15.数据表 A 中每个元素距其最终位置较近,则最省时间的排序算法是(
)
A.堆排序
.插入排序
C.直接选择排序
D.快速排序
二、填空题(本大题共 13 小题,每小题 2 分,共 26 分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.下列程序段的时间复杂度为___________。
i=1;
while(i
19.队列的插入操作在队列的___________部分进行。
20.一个栈的输入序列是 1,2,3,…,n,输出序列的第一个元素是 n,则第 i 个输出元素
为___________。
21.一个 10 阶对称矩阵 A,采用行优先顺序压缩存储下三角,a00 为第一个元素,其存储地
址为 1,每个元素占有 1 个存储地址空间,则 a85 的地址为___________。
22.设字符串 S=″I□AM□A□STUDENT″(其中□表示空格字符),则 S 的长度为___________。
23.在树形结构中,没有后继的结点是___________结点。
24.一棵深度为 n(n>1)的满二叉树中共有___________个结点。
25.在无向图中,如果从顶点 v 到顶点 v′有路径,则称 v 和 v′是___________。
26.无向完全图 G 采用___________存储结构较省空间。
27.在顺序查找、二分查找、索引查找和散列查找四种查找方法中,平均查找长度与元素个
数没有关系的查找方法是___________。
28.快速排序最好情况下的时间复杂度为___________。
三、应用题(本大题共 5 小题,每小题 6 分,共 30 分)
29.稀疏矩阵 A 如下,写出矩阵 A 的三元组表及矩阵 A 的转置矩阵的三元组表。
30.一棵二叉树的前根遍历序列为 ABCDEFG,中根遍历序列为 CBDAEGF,试构造出该二叉树。
31.下述矩阵表示一个无向连通网,试画出它所表示的连通网及该连通网的最小生成树。
32.给定表(80,90,50,70,75,60,40,100),试按元素在表中的顺序将它们依次插入
一棵初始时为空的二叉排序树,画出插入完成后的二叉排序树。
33.试写出一组键值(46,58,15,45,90,18,10,62)应用直接插入排序算法从小到大
排序后各趟的结果。
四、算法设计题(本大题共 2 小题,每小题 7 分,共 14 分)
34.试分别写出二叉树的先根遍历和中根遍历的递归算法。
35.试编写以单链表为存储结构实现直接选择排序的算法。