数据结构期末考试试卷B

一、 选择题（10×2＝20分）

1. 算法分析的两个主要方面是 ··················································································· 【 】

A) 时间复杂性与空间复杂性 B) 可读性与健壮性 C) 正确性与可读性 D) 简单性与文档性 2. 将新生成的元素插入到链队列Q的队尾的操作指令是 ········································ 【 】 A)Q.front->next=p; Q.front=p; C)Q.rear->next=p;Q.rear=p;

B)Q.rear=p;Q.rear->next=p; D) Q.front->next=p->nexr; Q.front=p;

3. 在有n个结点的二叉链表中，值为非空的链域的个数为 ····································· 【 】 A)n+1 B)2n-1 C)2n+1 D) n-1 4. 已知s= ‘howareyou’，则sub(s,length(s)-6,length(s)-5)的结果为 ··························· 【 】 A) howar B) ware C) areyou D) eyou 5. 一棵二叉树的度为0的结点n0个，度为1的结点n1个，度为2的结点n2个，则下列

表达正确的是 ········································································································ 【 】 A) n0n1n2

B) n0n21

C) n2n0n1

D) n2n01

6. 一个无向图有n个顶点，多于n-1条边，则该图一定是 ······································ 【 】 A) 含有环的图 B) 生成树 C) 连通图 D)都不对 7. 设有 120 个元素，用二分法查找时，最大比较次数是. ······································ 【 】 A) 60 B) 30 C) 7 D) 4 8. 一个有n个顶点的无向图有少于n-1条边，则该图一定是 ·································· 【 】 A)生成树 B)非连通图 C)连通图 D)含有环的图对工程图进行拓扑排序时所用的AOV网，不能采用下列哪种存储结构？ 【 】 A)数组表示法

B)邻接表

C)邻接多重表

D)十字链表

9. 在下列排序方法中，平均时间性能为O(nlogn)且空间性能最好的是 ·················· 【 】 A）快速排序 B）堆排序 C）归并排序 D）基数排序

二、 判断题（5×1＝5分）

1. 二叉链表不能用来存储非二叉树 ··········································································· 【 】

2. 对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可

访问到该图的每个顶点 ·························································································· 【 】 3. 创建哈希表时，只要选择或设置恰当的希尔函数，就不会发生冲突，就不需要确定处

理冲突的方案了。 ·································································································· 【 】

第1页/共4页

4. 折半查找法在成功时进行比较的关键字个数最多不超过其判定树的深度。 ······· 【 】 5. 外部排序指的是待排序的记录数量很大，以致内存一次不能容纳全部记录，在排序过

程中尚需对外存进行访问的排序过程。 ································································ 【 】

三、 填空题（10×2＝20分）

1. 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2. 指针P指向一个新生成的结点，假设已经给数据域赋值，将该结点插入到链队列Q的

队尾的操作指令是Q.rear->next=p;和 ；

3. 串有三种机内表示方法，其中__________存储表示的特点是：仍以一组地址连续的存

储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配而得。 4. 假设用低下标优先存储整数数组A1210，每个元素用5B存储，存储器按字节编址。已

知A0,0地址为1000，则A10,9地址为 。 5. 含有50个结点的完全二叉树的高度是 。

6. 深度为K (K≥1)的二叉树至少有K个结点，至多有 个结点。

7. 以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度WPL是

________________。

8. 一个连通图的生成树是一个 子图，它含有图中的全部顶点，但只有足以

构成一棵树的n-1条边。

9. 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找

算法的 。

10. 用起泡法对n个关键字排序，在最好情况下，需要做 次比较。

四、 简答题（2×5＝10分）

1. 简述算法的特点，并说说一个“好”的算法在设计时应达到什么要求？ 2. 根据下面的数据表，写出采用冒泡排序算法排序的每一趟的结果。

（25 10 20 31 5 44 16 61 100 3 ）

五、 应用题（4×5＝20分）

1. 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成，这7个字母在电文中出现

第2页/共4页

的概率分别为{0.01，0.02，0.04，0.08，0.16，0.32，0.37}。试画出对应的哈夫曼树并求出这7个字母的哈夫曼编码。

2. 选取哈希函数h（k）=k mod 11。用公共溢出区法处理冲突，试在基本表空间0～10，

溢出表空间11～14的散列空间中对关键字序列（22，41，26，65，53，46，30，13，1，67，29）构造哈希表。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

3. 一棵二叉树如下，试给出其先序、中序、后序遍历序列及该树的中序线索链表的示

意图，注意标出每个结点的左右标记。

a b c d e f g h i （

4. 画出下图的邻接表及邻接矩阵，用普里姆和克鲁斯卡尔算法画出最小生成树。

A 6 B 3 5 4 C

4 1 F 6 6 6 D E 2

第3页/共4页

六、 算法题（7+8+10＝25分）

要求：算法中要写算法说明及注释。

1. 顺序存储结构的线性表L中元素无序存放，要求以简单选择排序的方法对其排序，使

其元素非递减有序。

2. 试写一个算法查找二叉树T中是否存在某个结点X，计算结点X的所有子孙结点的数

量。用二叉链表作为T的存储结构。

第4页/共4页