数据结构期末考试试卷A

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

1. 算法分析的目的是 ·································································································· 【 】

A)找出数据结构的合理性 B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进 D)分析算法的清晰性 2. 下面程序段的时间复杂度是 ··················································································· 【 】 for (i=0; i元素，其存储地址为1，每个元素占1个地址空间，则a7,4的地址为 ················ 【 】 A)13 B) 33 C)18 D) 40 8. 在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为 ·················· 【 】

22

A) e B) 2e C) n-2e D) n-e 9. 有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100}，运用折半查找，要找值为82的结点，查找成功时需比较的次数为 ··································································· 【 】 A)1 B)2 C)4 D)8 10. 下述排序算法中，稳定的是 ··················································································· 【 】 A) 快速排序 B)堆排序 C) 希尔排序 D) 冒泡排序

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

1. 在线性表中，所有的结点都有一个直接前趋和一个直接后继 ····························· 【 】

第1页/共3页

2. 递归定义的数据结构尽量使用递归算法 ································································ 【 】 3. 一个带权图的最小生成树是唯一的 ····································································· 【 】 4. 由于希乐排序的最后一趟与直接插入排序的过程相同，因此前者一定比后者花费的

时间多。 ··············································································································· 【 】 5. 在二叉树中，若结点u是v的祖先，则在先序遍历序列中，u一定在v的左边 【 】

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

1. ____________是相互之间存在一种或多种特定关系的数据元素的集合。

2. 通常设计一个“好”的算法应考虑达到以下目标：（1）正确性（2）可读性（3）健壮

性（4）_____________________。

3. 指针P指向双向循环链表的第i个结点，指针S指向新生成的结点，将结点S插入到

结点P之前的操作是：s->prior=p->prior；_________________________；s->next=p；_________________________。

4. 假设一个有序表表长为15，在记录的查找概率相等的情况下，查找成功时折半查找的

平均查找长度为_______________。

5. 一棵二叉树遍历的前序序列为ABCDFE，中序序列为BAFDCE，则它的后序序列为

_______________。

6. 所谓连通分量指的是无向图的_______________。

7. 串有三种机内表示方法：定长顺序存储表示、____________、串的块链存储表示。 8. 深度为K (K≥1)的二叉树至多有____________个结点。 9. 进行拓扑排序时，一个表示工程的图我们称为___________网。

10. 由于待排序的记录数量不同，使得排序过程中涉及的____________不同，可将排序分

为内部排序和外部排序两大类。

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

1. 已知待排序文件各记录的排序码顺序如下：

49 38 65 23 94 27 05 18

请列出快速排序过程中每一趟的排序结果。

2. 试简述为哈希表构造哈希函数时，我们常用的处理的冲突的方法。

第2页/共3页

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

1. 给定的权值{4，6，9，11，12， 13，17， 28 }，根据赫夫曼算法画出赫夫曼树，并

求出该赫夫曼树的WPL值。（权值小的放在左边，权值大的放在右边）。

2. 对于一棵完全二叉树按层从上至下、从左至右编号，以编号为地址，采用顺序存储结

构，如下存放于数组S： A B I C F J L D E G H K 共12 个结点，请分别指出结点C、结点H、结点F的双亲结点与孩子结点。 3. 下列二叉树存放于线索链表之中，对其进行中序线索化。在图中以箭头画出各结点的

线索指针示意图，并标出左右标记的值。

A D H C B F E G A 4. 试画出下图的邻接表和逆邻接表。

B E C D F 六、 算法题（7+8+10＝25分）

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

1. 现有一从小到大的有序序列a1,a2,…,an。试采用二分法实现查找元素x。

2. 写一个算法，实现在带头结点的单链表中的按值查找locate(p,x)。若在头结点为P的

单链表中找到了数据为X的结点，则返回首次找到的结点的序号，若未找到，则返回一个特定的值-1。

3. 以二叉链表作为存储结构存放二叉树T，写一个算法在树中查找结点X并求出其度数。

第3页/共3页