[数据结构]期末考试及答案

《数据结构》 期末考试试卷

考生注意：1．本试卷满分100分。

（C ）、各叶子结点的带权路径长度之和 （D ）、根结点的值 10．线索二叉链表是利用（ ）域存储后继结点的地址。 （A ）、lchild （B ）、data （C ）、rchild （D ）、root 二、

填空题（每题2分，共计14分）

1．逻辑结构决定了算法的 ，而存储结构决定了算法的 。 2．栈和队列都是一种 的线性表，栈的插入和删除只能在 进行。 3．线性表（a 1,a 2, …,a n ）的顺序存储结构中，设每个单元的长度为L ，元素a i 的存储地址LOC(ai ) 为

2．考试时间90分钟。

3．卷面整洁，字迹工整。 4．已知一双向链表如下(指针域名为next 和prior) ： 4．填写内容不得超出密封线。

现将p 所指的结点插入到x 和y 结点之间，其操作步骤为： ； ； ； ；

5．n 个结点无向完全图的的边数为 ， 一、 单项选择题（每题2分，共计20分）

1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 n个结点的生成树的边数为 。 (A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性

6．已知一有向无环图如下： 2．设S 为C 语言的语句, 计算机执行下面算法时，算法的时间复杂度为（ ）。

for(i=n-1；i>=0；i--)

for(j=0；j

2

(A)、n (B). O(nlgn) (C). O(n) (D). O(n)

3．折半查找法适用于（ ）。

任意写出二种拓扑排序序列： 、 。

（A ）、有序顺序表 （B ）、有序单链表

7．已知二叉树的中序遍历序列为BCA ，后序遍历序列为CBA ，则该二叉树的先序遍历序列（C ）、有序顺序表和有序单链表都可以 （D ）、无限制 为 ，层序遍历序列为 。

4．顺序存储结构的优势是（ ）。

（A ）、利于插入操作 （B ）、利于删除操作 三、 应用题（每题11分 共计66分）

（C ）、利于顺序访问 （D ）、利于随机访问

1．设散列函数H(k)=k % 13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲5．深度为k 的完全二叉树，其叶子结点必在第（ ）层上。

突。(6分)

（A ）、k-1 （B ）、k （C ）、k-1和k （D ）、1至k

(1) 构造HASH 表。

6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）

(2) 分别求查找成功和不成功时的平均查找长度。 （A ）、11 （B ）、13 （C ）、48 （D ）、37

7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法的推广。 （A ）、先序 （B ）、中序 （C ）、后序 （D ）、层序 8．在下列链队列Q 中，元素a 出队的操作序列为（ ）

（ （B ）、p=Q.front->next; Q.front->next=p->next; （C ）、p=Q.rear->next; p->next= Q.rear->next; （D ）、p=Q->next; Q->next=p->next; 9

． Huffman树的带权路径长度WPL 等于（ ）

（A ）、除根结点之外的所有结点权值之和 （B ）、所有结点权值之和

2． 给定表（19,14,22,15,20,21,56,10）. （8分）

第 1 页 共 3 页

（1） 按元素在表中的次序，建立一棵二叉排序树

（2） 对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。 （3） 画出对(2)中的遍历序列进行折半查找过程的判定树。

3． 已知二个稀疏矩阵A 和B 的压缩存储三元组表如下：

A B C D E F

A ⎡∞651∞∞⎤

⎥B ⎢6∞∞53∞⎢⎥

C ⎢5∞∞7∞2⎥⎢⎥D ⎢157∞64⎥E ⎢∞3∞6∞6⎥⎢⎥F ⎢⎣∞∞246∞⎥⎦

（1）求从顶点A 开始的最小生成树。

（2）分别画出以A 为起点的DFS 生成树和BFS 生成树。

6写出A-B 压缩存储的三元组表。（5分）

4． 已知一维数组中的数据为（18,12,25,53,18）, 试写出插入排序（升序）过程。并指出具有n 个元素的插入排序的时间复杂度是多少？(5分)

5． 已知一网络的邻接矩阵如下，求从顶点A 开始的最小生成树。(8分，要有过程)

把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程) 。

（1） 画出对应的Huffman 树。 （2） 计算带权路径长度WPL 。

（3） 求A 、B 、C 、D 、E 、F 的Huffman 编码。

第 2 页 共 3 页

《数据结构》期末考试答案

选择题（每题1分）

1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 一、填空题 1．设计、实现 2．特殊、栈顶

3．LOC （a1）+(i-1)*L

4．p->next=q->next;q->next->prior=p;

4、 初始关键字： [18] 12 25 53 第 一 趟： 25 53 第 二 趟：[12 18 18 第 三 趟：[12 18 第 四 趟：[12 18 （4分）

O （n 2）（1分）。 5、7分 （1）4分 A

q->next=p;p->prior=q; B C 5．n(n-1)/2、n-1

3 6．ADCBFEG 、ABCDEFFG 5 7．ABC 、ABC 二、应用题

（2）查找成功的平均查找长度：（1分） （5*1+1*2+2*3+1*7）/9=20/9

查找不成功的平均查找长度：（1分）

（2+1+9+8+7+6+5+4+3+2+1）/13= 2（1）、构造（3

(2)、10 14 15 19 20 21 22 56（2分） （3）、（3分）

3、(5分，每行

（2）4分

6、(1) 3分 （2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21= （3）A ：010 B ：011 C ：110 D ：111 E ：00 F ；10

第 3 页 共 3 页

(1分) 3分） （