2016年湖南师范大学数学与计算机科学学院数据结构考研复试题库
● 摘要
一、选择题
1． 图中有关路径的定义正确的是（ ）。
A. 由顶点和相邻顶点构成的边所形成的序列
B. 由不同顶点所形成的序列
C. 由不同边所形成的序列
D. 上述定义都不是
答:A
【解析】顶点Vp 到顶点Vq 之间的一条路径是指顶点序列
的数目称为路径的长度。
2． 执行完下列语句段后，f 值为（ ）。
A.2
B.4
C.8
D. 无限递归
答:B
【解析】该程序使用了递归调用，由题知，所以结果为4。
3． 对序
列用希尔排序方法排序，经一趟后序列变
为
则该次采用的增量是（ ）。
A.1
B.4
C.3
D.2
答:B
【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的増量是4。
4． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
第 2 页，共 42 页 ，路径上边
C. 双链表
D. 仅有尾指针的单循环链表
答:D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
5． 下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫曼树的是（ ）。
A.24，10，5 和24，10，7
B.24，10，5 和24，12，7
C.24，10，10和24，14，11
D.24，10，10和 24，14，6
答:D
【解析】哈夫曼树是带权路径长度最短的二叉树。由根节点出发到两个叶子节路径中，第二个被访问的两个结点的权值要么相等，要么和为根节点的权值，故B 项错误。同理，通过第三个被访问的节点排除A 项。C 项，由两条路径可推出三个叶子节点的权值分别是：3、10和11，而根据哈夫曼树的定义可知，权值为3的节点应该和权值为10的结点结合，故C 项错误。D 项，反推出有四个叶子节点，权值分别为：5、5、6和8，满足哈夫曼树的条件。
6． 偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（ ）。
A. 间接寻址
B. 基址寻址
C. 相对寻址
D. 变址寻址
答:A
【解析】在四种不同的寻址方式中，间接寻址按指令的形式地址从主存中取出操作数的有效地址，然后再按此有效地址从主存中读出操作数。其余三种寻址方式可以统称为偏移寻址。
7． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
答:A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语句，则有设其执行时间为T （n ）
第 3 页，共 42 页
相关内容
相关标签