2016年青海大学土木工程学院程序设计之数据结构考研复试题库
● 摘要
一、选择题
1． 4个圆盘的Hanoi 塔，总的移动次数为（ ）。
A.7
B.-8
C.15
D.16
答:C
【解析】Hanoi 问题总移动次数为：次。
2． 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。
答:A
【解析】其中，以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是 ，则有语句设其执行时间为T （n ）
3． 某计算机使用4体交叉存储器，假定在存储器总线上出现的主存地址（十进制）序列为8005, 8006，8007，8008, 8001，8002，8003，8004，8000， 则可能发生发生缓存冲突的地址对是（ ）。
A.8004、8008
B.8002、8007
C.8001、8008
D.8000、8004
答:D
【解析】交叉存储器，又称低位交叉编址，即低位地址为体号，高位地址为体内地址。本题中，主存地址对应的体号分别是：1，2，3，4，1，2，3，4，4。地址为8004和8000都是存取的四号储存器，可能导致8004存储还未完成而又存取8000地址，因此可能发生缓存冲突。
4． 在下面的排序方法中，辅助空间为的是（ ）。
A. 希尔排序
B. 堆排序
C. 选择排序
D. 归并排序
答:D
5． n 个顶点的无向图的邻接表最多有（ ）个表结点。
A.IT B.n （n-l ） C.n （n+l） D.n （n-l ）/2
答:B
【解析】当n 个顶点构成的无向图是无向完全图时，则每一个结点都会和其余的n-1个结点连接，从而会产生n （n-l ）个表结点。
6． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1
B.n
C.n+1
D.2n
答:B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n 条边。
7． 当字符序列作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ） 。
A.4个
B.5个
C.3个
D.6个
图
答:C
【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t , 有两种结果若首字符为则只有一种结果因此总共有3种结果。
8． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
相关内容
相关标签