数据结构复习题.pdf

数据结构复习题--第1页

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，则所有顶点

数据结构复习题--第1页

数据结构复习题--第2页

的入度之和为_____________。

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

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

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

__________________。

应用题

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

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

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

现的频度分别为：7，26，