一 填空（每空一分，共14分）

1 数据元素是数据结构的基本单位，数据项是数据的不可分割的最小单位。
2 深度是k的完全二叉树至少有2^（k－1）个结点，至多有2^k-1个结点。
3 哈希表的查找效率主要取决于造表时选取的哈希函数和处理冲突的方法。
4 对100个记录进行折半查找，最多比较7次，最少比较1次。
5 有n个顶点的无向图，最少有0条边，最多有n(n-1)/2条边。
6 AOE网中，从源点到汇点的最长路径上的活动叫做关键活动。有环的图不能进行拓扑排序。
7 对于堆排序，常用的建堆算法是筛选法，堆的形状是一棵完全二叉树。

二 判断题（每小题1分，共5分）
1 线性表的链式存储结构优于顺序存储结构。 错
2 链表的每个节点中都帢包含一个指针。 错 例如双向链表
3 栈和队列都是顺序存储结构的线性结构。 错 链栈
4 若数的度为2时，则该树为二叉树。 错
5 若广义表中的每个元素都是原子，则广义表为线性表。 对

三 问答题（每小题4分，共16分）
1 一棵3阶4层（根为第一层，叶子为第四层）的B－树，至少有多少个关键字，至多有多少个关键字？
答：7个 26个
2 利用栈秋表达式（（A-B）-C）-(D-(E-F)) 的值，运算符栈和操作数栈各必须具有多少项？
答：5项 4项

3 以行序为主序存储10阶对称矩阵A，采用下三角的压缩存储方式，若起始地址是d，则A85的存储地址是多少？
答：32＋d

4 设哈希表中以存在无个记录（如图一所示）。哈希函数为H(K)=K MOD 11，用二次探测再散列处理冲突。请问关键字为94的记录的存储地址是多少？
0 1 2 3 4 5 6 7 8 9 10
图一
45 16 39 62 76
答：存储地址是 2

四 综合题（每小题5分，共35分）
1 给定一组权值{9，6，14，17，2，15，3，16}，请构造哈夫曼树，并计算其带权路径长度。
答：带权路径长度186

2 已知二叉树的先序遍历的结果为ABCDEFGHIJ，中序遍历的结果为CBEDAHGIJF，请画出这颗二叉树。

3 对图二所示的无向图，（1）请用邻接表表示，且顶点链接按序号从小到大链接。
（2）请写出从V0出发的深度优先遍历和广度优先遍历的结果。
图二：
0
O

1 2

3 4 5 6

7

4 将图三所示的树转换为二叉树，并使其成为后序线索树。


图三: A

B C D

E F


G H I J



K L M



N


5 对关键字序列{44，12，53，13，37，88，24，61}构造一棵平衡二叉树。

6 已知一个OE网，如图四所示，求其关键路径，并给出时间4的最迟发生时间和事件5最早发生时间？




图四： 1 4 4

12
5 2 6 9
11 5 10
0 9
18
14 6
3 5
3 5
7 7 8
8

7 对序列{50，77，64，98，39，12，26，48，44，35}创建初始堆。

五（8分） 设指针head 指向无表头结点单链表的首结点。试设一算法，删除链表中值为X的结点，若X结点不存在，则输出“不存在”信息。

六（10分）已知一个有向图的邻接表，试编写一个算法求每个结点的出度和入度。

七（12分）已知一个二叉树存储于二叉链表中，其结点结构为 lc data rc
其中lc和rc分别为指向左子树和右子树根的指针域。试编写一个
非递归算法，求二叉树的结点总数及其深度。