专升本《数据结构》试卷

专升本《数据结构》试卷A

专升本

《数据结构》试卷A

一、单项选择填空题：（每小题2分，共10分）

对于下列各题，在备选答案中选出一个正确的，并将其编号填在“ ”位置上。

1. 若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采

用 存储方式最节省运算时间。

A. 单链表 B. 双链表 C. 单循环链表 D. 顺序表

2. 在有 n 个叶子结点的哈夫曼树中结点总数为 3. 折半查找法要求查找表中各元素的键值必须是

。

A. 不确定 B. 2n-1 C. 2n D. 2n+1

。

A. 递增或递减 B. 递增 C. 递减 D. 无序

4. 对于键值序列（11，13，18，60，15，7，19，25，12，80），用筛选法建

堆，必须从键值为 的结点开始。 A. 80 B. 12 C. 60 D. 15

5. 设图 G 用邻接表存储，则求每个顶点入度的时间复杂度为

A. O(n) B. O(n+e) C. O(n*n) D. O(n*e) 二、填空题：（每小题2分，共10分）

。

1. 已知完全二叉树的第5层有8个结点(根结点在1层)，则其叶子结点有 个。

2. 在单链表中，删除指针 P 所指结点的后继结点的语句是： 。

3. 假设队列 Q 采用循环队列存储，则队列中当前有 个元素。

4. 有向图 G 用邻接矩阵 A[1..n，1..n] 存储，其第 i 行的所有非零元素之个数等于顶点 i 的 。 5. 平衡二叉树中每个结点的平衡因子定义为 。 三、解答下列各题：（每小题10分，共60分）

1. 已知线性表 L 采用带头结点的的双向循环链表表示，试给出它的存储结构

类型描述及相应的示意图。

2. 假设栈 S 以顺序结构存储，试给出它的存储结构类型描述以及相应的入栈

和出栈操作示意图。

3. 已知二叉树的后序和中序序列如下，画出该二叉树以及建立中序线索后的示

意图。

先序序列是：ABDGCEFH 中序序列是：DGBAECHF

4. 已知数据表为（12，70，33，65，24，56，48，92，86，22），a) 写出采

用快速排序算法进行排序时第一趟快速划分的详细过程及结果；b) 写出按基数排序思想进行一次分配和收集的结果。

5. 已知图 G 如下所示，试写出采用邻接表存储时的类型描述和存储结构示意

图，以及从顶点1为出发点，按广度优先搜索策略遍历图 G 时所获得的顶点序列。

6. 设哈希函数为 H(K) = K mod 11，地址空间为 0..12，用线性探测法解决冲

突。请画出依次插入23，6，35，12，17所得到的散列地址表示意图。 四、算法设计题：（每小题10分，共20分） 对以下各题均要求写出相应的存储结构的类型描述。

1. 设计算法将一个带头结点的单循环链表 A 分解为两个具有相同结构的链表

B、C，其中：B 表中的结点为 A 表中值为奇数的结点，而 C 表中的结点为 A 表

中值为偶数的结点。（假设每个结点的数据域为整型值。要求利用原表结点。）

2. 设计算法实现中序遍历二叉树（采用三叉链表存储）。