2007年硕士研究生入学考试试题答案
─────────────────────────────────
科目编号： 科目名称：
一、填空题（每题2分，共30分）
1. 线性结构和非线性结构 2. O(n2) 3. 长度相等且对应位置上的字符相等 4. 3
5. 节省存储空间 6. 33 7. 128； 7 8. 45 9. SXSSXSXX 10. 双亲表示法、孩子表示法、孩子兄弟表示法、多重链表表示法（回答三个得全分） 11. 49 12. 从源点到汇点的最长路径
13. 边较多的稠密图、边较少的稀疏图
14. 排序前后在外存，排序时数据调入内存的排序方法
15. 值均匀分布于表空间以减少冲突；函数尽可能简单以方便计算 二、简答题（每题5分，共30分）
1.对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较? 答：设变量max和min用于存放最大元和最小元(的位置)，第一次取两个元素进行比较，大的放入max，小的放入min。从第2次开始，每次取一个元素先和max比较，如果大于max则以它替换max，并结束本次比较；若小于max则再与min相比较，在最好的情况下，一路比较下去都不用和min相比较，所以这种情况下，至少要进行n-1次比较就能找到最大元和最小元。
2.为什么有序的单链表不能进行折半查找?
答：因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。
3. 循环队列的优点是什么？如何判别它的空和满？
答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使存储队列的空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是少用一个元素的空间，每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满；二是设置一计数器记录队列中元素总数，不仅可判别空和满，还可以得到队列中元素的个数。三是另设一布尔变量来区别队列的空和满。
4. 在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？
答：以下分3种链表讨论：
（1）单链表。当已知指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋，因此无法删去该结点。
（2）双链表。由于这样的链表提供双向链表，因此根据已知结点可以查找到其直接前
共 页 第1页
趋和直接后继，从而可以删除该结点。
（3）单循环链表。根据已知结点位置，可以直接得到其后相邻的结点（直接后继），又因为是循环链表，所以可以通过查找得到p结点的直接前趋，因此可以删去p所指结点。
5. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？
答：通常有两条标准：第一条是算法所需的存储空间量；第二条是算法所需的时间。 对于算法所需的时间又涉及以下几点：
1） 程序运行时所需输入的数据总量； 2） 对源程序进行编译所需的时间； 3） 计算机执行每条指令所需的时间； 4） 程序中的指令重复执行的次数。
6．在线性表顺序存储结构中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。 三、综合应用题（共42分）
1 （12分）给定一个关键字序列{24，19，32，43，38，6，13，22}， （1）建成二叉排序树，并求在查找成功的情况下，其平均查找长度。（3分） （2）对所建的二叉排序树进行何种操作可得到有序序列？（2分）
（3）请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程；（3分）
（4）快速排序、堆排序、归并排序中哪一种方法使用的辅助空间最少？最坏情况下哪种方法的时间复杂度最差？（4分） 【解答】
快速排序的第一趟结果为{22，19，13，6，24，38，43，12}； 堆排序时所建立的初始小顶堆如图所示：
242461932196191343386132238321322383224224343
归并排序的过程如下：
24 19 32 43 38 6 13 22
[19 24] [32 43] [6 38] [13 22] [19 24 32 43] [6 13 32 38] [6 13 19 22 24 32 38 43]
三种排序方法所需辅助空间：堆是O(1)，快速排序是O(log2n)，归并排序是O(n)，可
共 页 第2页
见堆排序所需辅助空间较少。三种排序方法所需时间：堆是O(nlog2n)，快速排序是O(n)，归并排序是O(nlog2n)。可见快速排序时间复杂度最差。
2．（6分）对二叉树中的结点进行按层次顺序(每一层自左至右)的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
3．（8分）假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为
{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}. (1)为这8个字母设计哈夫曼编码。（4分）
(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少? （4分） 解： (1)哈夫曼编码
2
根据上图可得编码表：
a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000
(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%
其平均码长是等长码的87%。 所以平均压缩率为13%。 4．（8分）设无向图G如图所示,
共 页 第3页
(1) 请画出图G的邻接表, 并在此基础上求从A出发的深度优先和广度优先遍历的序列。（4分）
(2)在深度、广度优先遍历算法中,各使用了哪些数据结构. （4分）
A 4 3 6 B C
5 8 8 5 D 6 E
4 6 F
．解答：
2 4 3 3 A
B 3 6 4 8 5 5 C 4 5 5 2
D 5 6 6 4 E
F 6 6
从A出发的深度优先：A B C D E F 广度优先遍历的序列：A B C D E F 深度优先遍历算法利用了“栈”
广度优先遍历算法利用了“队列” 5．（8分）解答下面的问题：
(1) 画出在递增有序表A[1..11]中进行折半查找的判定树。（2分） (2) 当实现插入排序过程时，可以用折半查找来确定第i个元素在前i-1个元素中的可能插入位置，这样做能否改善插入排序的时间复杂度？为什么？（4分） (3) 折半查找的平均查找长度是多少？（2分） 解答：（1）判定树
共 页 第4页
(2)不能。折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变，时间
2
复杂度仍为O(n)。
(3)折半查找的平均查找长度为：ASL=（1+2+2+3+3+3+3+4+4+4+4）/11=33/11=3 四、算法设计题（共48分）
1. 已知有序整数序列用链表存储。阅读下面算法example，并回答下列问题： （1）写出执行example（a,b）的返回值,其中a和b分别为指向存储整数序列{2，4，5，7，9，12}和存储整数序列{2，4，5，7，9}的链表的头指针；(4分) （2）简述算法example的功能；(4分)
（3）写出算法example的时间复杂度。(4分) typedef struct node { int data;
struct node *next; }
int example(LinkList ha, LinkList hb) { /*LinkList是带有头结点的单链表 */
/*ha和hb分别为指向存储两个有序整数集合的链表的头指针 */ LinkList pa,pb; pa=ha->next; pb=hb->next;
while(pa && pb && pa->data==pb->data) { pa=pa->next; pb=pb->next; }
if(pa==NULL && pb==NULL) return 1; else return 0; }
(1) 执行example（a,b）的返回值：0
(2) 判断两个整数序列是否相等，相等返回1，否则返回0 (3) Min(n,m)，其中m,n分别为两个表的表长。
2. 一棵n个结点的完全二叉树以向量作为存储结构，试写一非递归算法实现对该树的前序
共 页 第5页
遍历。（12分）
解：以向量为存储结构的完全二叉树，其存储在向量中的结点其实是按层次遍历的次序存放的，算法：
#define M 100 /*设结点数不超过100*/
typedef char DataType;/*设结点数据类型为char*/ typedef DataType BinTree[M]; void Preorder(BinTree T)
{ /*前序遍历算法*/
int n=T[0]; /* T[0]放置结点数目*/ int p[M]; /*设置一队列存放结点值*/ int i,j;
for(i=1;i<=n;i++) {
if (i==1) /*根结点*/ j=1;
else if(2*j<=n) /*左子树*/ j=2*j;
else if(j%2==0&&j printf(\"%c\ /*打印结点值*/ } } 3.（12分）试设计一个用开放定址法解决冲突的散列表上查找一个指定结点的算法。要求给出表的存储结构。 ＃define m <哈希表长度> ＃define NULLKEY <代表空记录的关键字值> typedef int KeyType; typedef struct { KeyType key; … } RecordType ; typedef RecordType HashTable[m] ; int HashSearch( HashTable ht, KeyType K) {p0=hash(K); if (ht[p0].key==NULLKEY) return (-1); 共 页 第6页 else if (ht[p0].key==K) return (p0); else /* 用线性探测再散列解决冲突 */ { for (i=1; i<=m-1; i++) { pi=(p0+i) % m; if (ht[pi ].key==NULLKEY) return (-1); else if (ht[pi].key==K) return (pi); } return (-1); } } 4.(12分) 试设计算法判断一个无向图是否连通，如果不连通请给出连通分量的个数。 ＃define True 1 ＃define False 0 ＃define Error -1 /*出错*/ ＃define Ok 1 int visited[MAX-VERTEX-NUM]; /*访问标志数组*/ void TraverseGraph (Graph g) { int count=0; for (vi=0; vi void DepthFirstSearch（Graph g, int v0） /*深度遍历v0所在的连通子图*/ { visit（v0）； visited[v0]=True； /*访问顶点v0， 并置访问标志数组相应分量值*/ w=FirstAdjVertex(g, v0); while ( w!=-1) /*邻接点存在*/ { if(!visited[w]) DepthFirstSearch(g, w); /*递归调用DepthFirstSearch*/ w=NextAdjVertex(g, v0, w); /*找下一个邻接点*/ } } /*DepthFirstSearch*/ 共 页 第7页 因篇幅问题不能全部显示，请点此查看更多更全内容