数据结构综合练习A卷

（ ）。

9、在散列存储中，处理冲突有（ ）和（ ）两类方法。 10、在栈顶指针为HS的链栈中，判定栈空的条件是（ ）。 11、在图形结构中，每个结点的前驱结点和后继结点可以有（ ）。 12、在无向图G的邻接矩阵A中，若A[i][j]=1，则A[j][i]等于（ ）。 13、折半查找效率较高，但要求结点（ ）并且要求线性表（ ）；而对于顺序查找，则线性表的存储方式（ ）。

14、对于n个记录的集合进行归并排序，所需的附加空间（ ）。 七、简答与运算题（每小题 5 分，共7小题共 35 分） 得分 1、设有如图所示的逻辑结构图，依据该图写出数据结构的二元组描述形式。

5

2、下图为单链表，请写出把数据元素30所在结点删除的操作顺序步骤。

L

3、写出下图中二叉树的前序、中序、后序和层次遍历结果。

BECDA21 18 30 75 42 56 ∧

4、将下图的森林转换成二叉树并画在下图的右侧。

FGHI A C D F H G I L J K M N B E

6

5、某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，请画出对应的赫夫曼树，并设计赫夫曼编码。

6、下图是某一有向图的邻接表，请画出这个有向图，并分别写出一个从顶点V1出发的深度优先搜索序列和的广度优先搜索序列。 0 1 2 3 4 5

7、若哈希表的地址范围为0到9，Hash函数为H(key)=(key2+2)mod 9,并采用链地址法处理冲突，画出元素7，4，5，3，6，2，8，9依次插入哈希表以后该哈希表的状态。

V1 V2 V3 V4 ∧ V5 V6 ∧ 1 2 5 ∧ 3 5 2 ∧ 4 4 ∧ 3 ∧ 7