南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

南师大数学与计算机学院

计算机专业《数据结构》试题（A卷）2006.6.30

班级 学号 姓名

一、填空题（每空2分，共20分）

1．当

2．对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为 。

3．设某二叉树的前序和中序序列均为ABCDE，则它的后序序列是 。

4．假设以一维数组S n n 1 /2 作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A[5][6]的值存储在S[___]中。

5. 若一棵树中度为1的结点有N1个，度为2结点有N2个，……度为m的结点有Nm个，则该树的叶结点有 个。

6.设循环队列的元素存放在一维数组Q[0..30]中,front指向队头元素的前一个位置,rear指向队尾元素。若front=25, rear=5,则该队列中的元素个数为 。

7．图的遍历方法主要是

8．设源串S=“bcdcdcb”，模式串P=“cdcb”，按KMP算法进行模式匹配，当“S2S3S4”=“P1P2P3”，而S5≠P4时，S5应与 比较。

9. 设序列{12，34，19，23，8，56}，试建立表长为7的Hash表。Hash函数为H（key）=key % 7，用线性探测法解决冲突，则56冲突

10.求解图的最小生成树的算法有两个，分别是

二、根据要求解答下列问题。（共34分）

1．画出广义表D=(( )，x，(a，(b，c)))的存储结构。（5分）

南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

2．根据图的邻接表画邻接矩阵。（5分）

3．请给出堆排序不稳定的例子。（6分）

4．设输入下列关键字序列：12，34，56，8，5，18，15，

试建立一棵平衡的二叉排序树，写出步骤。（6分）

南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

5． 分别画出一个B树和B+树的例子，并指出它们之间的区别。（6分）

6. 举例说明栈和队列的应用。（6分）

三．在《数据结构》课程中，你学习了哪些算法？请至少列举20个算法名称。（10分）

南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

四、试编写对顺序表L进行归并排序的算法。（12分）

南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

五、已知二叉树T的结点结构为

其中，bal存储结点的平衡因子（bal=左子树高度-右子树高度），试编写算法求树T中各结点的平衡因子。（12分）

南师大数学与计算机学院计算机专业《数据结构》试题(A卷)2006630

六、设采用邻接表作为有向图的存储结构，试编写算法：计算有向图中每个顶点的出度和入度。（12分）