苏州大学2000年硕士研究生入学考试数据结构与程序设计

2000年攻读硕士学位研究生入学考试试题
学科，专业：…………研究方向：………….考试科目：数据结构及程序设计
算法请用类 PASCAL或类C 语言编写，程序请用PASCAL 或类C语言编写
一．填空（15分）
1．已知一棵二叉树的前根序列是BEFCGDH，中根序列是FEBGCHD，则后根序列必为（ ）。
2．设二叉树根结点的层次为1，深度为K的二叉树至多有（ ）个结点。
3．ISAM文件是（ ）文件，VSAM文件是（ ）文件。
二．若在三对角线矩阵A中，三条对角线组成的带状区域按行的顺序放在一维数组中，即a11放在B[1]中，a12放在B[2]中，……，写一个地址公式，由B[1]的地址Loc（B[1]）确定aij的地址Loc（A[i，j]）。（10分）

a11 a12
a21 a22 a23
A= a32 a33 a34

a n-1 n-1 a n-1 n
a n n-1 a n n

 

三．设一篇短文中出现的字符D={S，I，P，Q，T}，每个字符出现的次数为F={10，29，4，9，5}
1．如何对上面的诸字符进行二进制编码，使得
（1） 该短文的总长度最短；
（2） 为了译码，任一字符的编码不应是另一字符的编码的前缀。
2． 按你得出的字符编码，将二进制字串‘000100011010100’进行译码（译成字符）。
（15分）
四．试编写广度优先遍历图的算法。（10分）

五．已知二叉树前根遍历序列的后根遍历序列，试编写生成该二叉树的算法。算法的输入为二个以字符串形式表示的前根遍历序列和后根遍历序列，算法的输出为该二叉树，用根结点指针表示。（10分）

六．生成一个按蛇形方式排列自然数1，2，3，4，……，n（n+1）/2的上三角N阶方阵，N阶方阵用二维数组表示，试编写程序。（10分）
N=5的N阶方阵的上三角为：
1 3->4 10->11
2 5 9 12
6 8 13
7 14
15
七．选取哈希函数H（k）=(3k)MOD 11,d1=H(k),di=(di-1 + (7k)MOD 10 + 1)MOD 11 (i=1,2,3……)。试在0到10的地址空间里对关键字序列（22，41，53，46，30，13，01，67）构造哈希表，并求在等概情况下查找成功与不成功时的平均查找长度。（15分）

八．有若干条红色，黄色的色条随机摆满一行，试用复杂度为O（n）的算法把他们按颜色有序摆放（颜色相同放在一起），最多使用一个单元的额外附加空间。（15分）