数据结构复习题.pdfVIP

1.设有指针head指向不带表头结点的单链表，用next表示结点的一个链域，指

针p指向与链表中结点同类型的一个新结点。现要将指针p指向的结点插入表

中，使之成为第一个结点，则所需的操作为p→next=head和______________。

2.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现_________

个不同的出栈序列。

3.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空

闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空

标志为________。

4.某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树

中根结点的右孩子是_______。

5.一棵含9个结点的完全二叉树的深度为_______。

6.已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________个非

叶子结点。

7.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____________。

8.在一个具有n个顶点的有向图中，若所有顶点的出度之和为10，则所有顶点

的入度之和为_____________。

9.有4个顶点的无向完全图的边数为________________。

10.对表长为900的索引顺序表进行分块查找，且以顺序查找确定块，则在各记

录的查找概率均相等的情况下，每块应分为最佳结点数是

__________________。

1.在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的

正确操作是______________。

2.中序遍历二叉排序树所得到的序列是________序列（填有序或无序）。

3.在循环队列中，存储空间为0～n-1,设队头指针front指向队头元素前一个空

闲元素，队尾指针指向队尾元素，那么队满标志为front=(rear+1)%n，队空

标志为________。

4.某二叉树的先根遍历序列为IJKLMNO，中根遍历序列为JLKINMO，则该二叉树

中根结点的右孩子是_______。

5.设某棵二叉树中度数为0的结点数为N，度数为1的结点数为N，则该二叉树

01

中度数为2的结点数为______。

6.已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________个非

叶子结点。

7.在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于_____________。

8.在一个具有n个顶点的有向图中，若所有顶点的出度之和为10，则所有顶点

的入度之和为_____________。

9.有4个顶点的无向完全图的边数为________________。

10.对表长为900的索引顺序表进行分块查找，且以顺序查找确定块，则在各记

录的查找概率均相等的情况下，每块应分为最佳结点数是

__________________。

应用题

1.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF，

写出该二叉树的后序序列。

2.假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出

现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼

编码。要求：

(1)画出构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点权

值)；

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

3．从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一

棵二叉排序树。

（1）画出该二叉排序树；

（2）画出从（1）所得树中删除关键字为37的结点之后的二叉排序树。

4.已知如图所示，用普里姆（prim）算法从顶点A开始求最小生成树。

5．对下列关键字序列（33，15，27,48，59，36，72，46，08，65，30）构造表

长为15的散列表。假设散列函数为h(key)=key%13,用线性探查法解决冲突。

（1）画出该散列表；

（