CS203 2016秋期末

2016-2017 年 秋季学期 期末考试试卷

SOUTHERN UNIVERSITY OF SCIENCE AND TECHNOLOGY

课程名称: 数据结构与算法分析
课程代码: CS203
开课单位: 计算机科学与工程系

试卷代码： __________
命题教师： 骆宗伟

考试时长：120 分钟

满分 100

一填空题 15 分

1-1

表达式 $a * (b + c) - d$ 的后缀表达式为 $\underset{―}{}$ .

1-2

有 5 个元素, 其入栈次序为 A、B、C、D、E, 在各种可能的出栈序列中, 以元素 C 第一个出栈且元素 D 第二个出栈的序列包括 $\underset{―}{}$ .

1-3

深度为 $k$ (根为第 0 层, 深度为最大层数)的三叉树所包含的结点最多有 $\underset{―}{}$ 个.

1-4

图一中二叉树的后序遍历序列(Postorder Traversal)为 $\underset{―}{}$ .

图一:

         A
       /   \
     B        E
    /  \     /  \
   C    D    F    G
            /     / \
           H     I   J

1-5

将一棵树 $T$ 转换为左子/右兄(FirstChild-NextSibling)链表表示的二叉树 $B$ , 则 $T$ 的后根次序遍历序列是 $B$ 相应的 $\underset{―}{}$ 遍历序列.

1-6

字符串 "abababb" 的特征向量(next 数组)为 $\underset{―}{}$ .

1-7

一棵完全二叉树上有 1001 个结点, 则其中叶子结点的个数是 $\underset{―}{}$ .

1-8

在一棵度(Degree)为 4 的树 $T$ 中, 若有 20 个度为 4 的结点、10 个度为 3 的结点、1 个度为 2 的结点、10 个度为 1 的结点, 则树 $T$ 中的叶子结点个数是 $\underset{―}{}$ .

1-9

如果将图一中的二叉树处理成中序(Inorder Traversal)线索二叉树(Threaded Binary Tree), 则结点 $H$ 的左、右线索(Thread)指向的结点分别是 $\underset{―}{}$ 和 $\underset{―}{}$ .

1-10

已知某通信电文只有 6 种字符 ${a, b, c, d, e, f}$ 构成, 每个字符出现的次数分别为 ${23, 5, 14, 8, 25, 7}$ , 请给出各字符的 Huffman 编码： $\underset{―}{}$ .

二、选择题 15 分

2-1

以下数据结构中, $\underset{―}{}$ 是非线性结构.

A 队列
B 栈
C 线性表
D 二叉树

2-2

（2）为解决计算机与打印机之间速度不匹配的问题, 通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区, 而打印机则依次从该缓冲区中取出数据, 该缓冲区的逻辑数据结构应该是?

A 栈
B 队列
C 树
D 图

2-3

若某栈的输入序列为 1, 2, 3, ..., n 输出序列的第一个元素为n, 则输出序列中第 i 个元素为

A i
B n - i
C n- i + 1
D 都有可能

2-4

将一棵含有 54 个结点的完全二叉树中, 根结点编号为 1, 则编号为 27 的结点的右孩子编号为 $\underset{―}{}$ (或选项中的描述).

A 52
B 53
C 54
D 无右孩子

2-5

已知关键字序列 ${5, 8, 12, 19, 28, 20, 15, 22}$ 为最小堆, 添加关键字3, 调整后得到的最小堆是

A ${3, 5, 12, 8, 28, 20, 15, 22, 19}$
B ${3, 5, 12, 19, 20, 15, 22, 8, 28}$
C ${3, 8, 12, 5, 20, 15, 22, 28, 19}$
D ${3, 12, 5, 8, 28, 20, 15, 22, 19}$

2-6

对某有向无环图(DAG)进行拓扑排序, 可以得到的不同拓扑序列的个数是

node a, b,c,e,d
edge:
a to b
a to c
a to e
b to c
c to d
e to d

2-7

对一组数据 $(2, 12, 16, 88, 5, 10)$ 进行排序，若前三趟排序结果如下，则采用的排序算法可能是 $\underset{―}{}$

1: 2 ， 12 ，16，5，10， 88
2: 2 ， 12 ， 5 ， 10 ， 16 ， 88
3: 2，5，10，12，16，88
A 冒泡排序（Bubble Sort）
B 归并排序（Merge Sort）
C 希尔排序（Shell Sort）
D 基数排序（Radix Sort）

2-8

若一棵二叉树的前序遍历序列为 a, e, b, d, c, 后序遍历顺序为 b, c, d, e, a

则根结点的子结点可能是 $\underset{―}{}$ 。

A: only e
B: e, b
C: e, c
D: 无法确定

2-9

假设栈初始为空, 将中缀表达式 $a / b + (c * d - e * f) / g$ 转换为后缀表达式的过程中, 当扫描到 f 时, 栈中的元素从栈底到栈顶依次是 $\underset{―}{}$ 。

A: +(*-
B: +(-*
C: /+(*-*
D: /+-*

2-10

设 Huffman 树的叶子结点个数为 $m$ , 则其结点总数为 $\underset{―}{}$ .

A: $2 m$
B: $2 m - 1$
C: $2 m + 1$
D: $m + 1$

三 10分

试证明, 在具有n(n>=1)个节点的 m 叉树中, 有n(m-1)+1个指针域(结点中指向子结点的引用)为空

四 10分

给定一组关键字序列 $T = [13, 25, 16, 29, 8, 28, 4, 9, 20, 12, 19]$ , 使用排序算法按从小到大的顺序进行排序：

使用快速排序, 选择第一个记录作为pivotkey, 请写出第一趟排序结束时的序列.
使用希尔排序(Shell Sort)算法, 选取增量序列 ${4, 2, 1}$ , 写出每轮排序结束时的序列.
使用基数排序(Radix Sort)进行排序, 按照最低位优先进行排序, 写出每轮排序结束时的序列.

五

已知数组 $A [1 \dots n]$ 中的元素均为正整数, 且既包含奇数也包含偶数.

请设计一个算法将其调整为左右两个部分, 左边为奇数, 右边为偶数, 要求时间复杂度 $O (n)$ , 空间复杂度 $O (1)$

描述算法的基本思想
请写出算法, 并在关键之处给出简要解释

六 10分

已知带头结点的单链表, 结点结构：

|data|next|

请在不改变链表节点分配的前提下, 设计高效算法查找链表倒数第 $k$ 个位置上的节点( $k$ 为正整数)。成功返回该节点 data, 否则返回 0

描述算法的基本思想
请写出查找算法, 并在关键之处给出简要解释

七 10分

判别序列 $[14, 63, 8, 35, 28, 46, 13, 82, 88, 21]$ 是否为最小堆(Min Heap), 若不是, 请调整为最小堆并画出调整过程

八 10分

给出下面的有向带权图

node v0, v1, v2, v3 ,v4, v5
edge:
v0 -> v2 10
v0 -> v4 30
v0 -> v5 100
v1 -> v2 5
v2 -> v3 50
v3 -> v5 10
v4 -> v3 20
v4 -> v5 50

使用 Dijkstra 算法求带权有向图中从顶点 $V_{0}$ 到其它顶点的最短距离和最短路径

简述算法基本思想
写出算法关键变量
用表格列出运行过程中的关键变量变化.

九 10分

对于二叉搜索树(Binary Search Tree), 节点结构如下：

public class Node {
    private int data;
    private Node left;
    private Node right;
}

设计算法, 将给定二叉搜索树按节点 data 值递增顺序转换为双向链表(Doubly Linked List), 即在转化后的双向链表中, 每个节点left域指向其前驱节点, right域指向其后继节点, 算法返回值为结果链表的头节点.

例如: 对以下的二叉搜索树

        40
       /  \
     20      50
    /  \    /  \
   15  24  45   60

转换之后的双向链表为

head <-> 15 <-> 20 <-> 24  <-> 40  <-> 50  <-> 60

要求:

先描述算法的基本思想
写出转换算法, 关键之处给出简要解释
转化时在原节点结构上做修改, 不能新建新的节点作为链表节点

CS203 2016秋 期末 ​

一 填空题 15 分 ​

1-1 ​

1-2 ​

1-3 ​

1-4 ​

1-5 ​

1-6 ​

1-7 ​

1-8 ​

1-9 ​

1-10 ​

二、选择题 15 分 ​

2-1 ​

2-2 ​

2-3 ​

2-4 ​

2-5 ​

2-6 ​

2-7 ​

2-8 ​

2-9 ​

2-10 ​

三 10分 ​

四 10分 ​

五 ​

六 10分 ​

七 10分 ​

八 10分 ​

九 10分 ​