【殷人昆】计算机数据结构复习指导（清航考研）

dehetuodao

计算机统考复习中的数据结构复习指导

殷人昆 北京清航教育校长 清华大学计算机系教授

一、总体分析

计算机科学与技术学科全国硕士研究生统一入学考试已经进行了两次。数据结构部分的考试范围要求掌握：

1，基本数据结构的知识

2，算法设计和编程的能力

3，综合应用算法和数据结构的技能

从考试的命题来看，2010年比2009年的题目难度要大一些。在这里，我对2009年考题与2010年考题的考试范围进行了简单的比较：

A, 选择题部分，请参考表1

2009年	2010年
1.队列与缓冲区	1.进栈与出栈序列
2.栈与队列的操作	2.双端队列的出队序列
3.几种二叉树遍历的方式	3.后序线索二叉树的表示
4.完全二叉树的性质	4.平衡二叉树的插入
5.平衡二叉树的定义	5.K叉树叶结点的计算
6.森林的二叉树表示	6.Huffman树的定义和特点
7.无向连通图的定义	7.无向连通图的最少边数
8.m阶B树的定义	8.拓扑排序序列
9.堆的定义和插入方法	9.折半查找的性能分析
10.几种排序方法	10.快速排序递归次数

表1

2010年选择题还有一道题（11题）是对几种排序方法的考察。

由表1我们可以总结出，在选择题部分，各主要知识点分布如下，请参考表2：

考察内容	2009年	2010年
栈、队列与双端队列	2	2
树与二叉树、森林	4	4
图	1	2
查找	1	1
排序	2	2

表2

B，综合应用题部分的试题范围如下：

2009年	2010年
41.求解图的最短路径	41.散列表构造、数据存储及性能分析
42.算法设计：在单链表中求倒数第k个结点位置	42.算法设计：将一维数组中所有元素循环左移p位

总体上讲，2009年的试题较简单，2010年的试题比较复杂，且难度稍大，但平时教学中应当都教过，或练习都做过。

二、2010
年考试改卷的基本情况

2010年考试改卷的大概情况如下：

客观题是机改，数据结构部分总分22分，平均得分约为17分，失分较多的是

第2题（双端队列）

第5题（K叉树叶结点的计算）

第8题（拓扑排序的序列个数）

第10题（快速排序递归次数）；

主观题是人改，数据结构部分总分23分

第41题10分，平均得分5分，失分最多的是

计算散列表长度（2分），多数考生未得分。

将给定元素存储到散列表中（6分），平均得3分。如果第1问错了，不影响第2问得分；但可惜散列函数有不少同学选择不完全对。

计算平均查找长度（2分），平均得1分。

第42题是算法设计题13分，平均得6～8分，失分最多的是算法效率达不到要求。

许多考生成绩差的主要原因：

1，本科数据结构课程学习不够扎实；

2，考前复习不够充分；

3，考试时审题不仔细，急于给出答案，未严格推导。

三、2010年考试试卷分析

由于篇幅有限，在此只例举综合题两道大题进行分析。

二、综合应用题

41题：（10分）将关键字序列{ 7, 8, 30, 11, 18, 9, 14 } 散列存储到散列表中，散列表的存储空间是一个下标从 0 开始的一个一维数组散列，函数为：

H(key) = (key´3) MOD 7

处理冲突采用线性探测再散列法，要求装载因子为 0.7

问题：
(1) 请画出所构造的散列表。

(2) 分别计算等概率情况下，查找成功和查找不成功的平均查找长度。

解答：这是一道常规的数据结构题目。实际上要做三步工作：计算表的长度，从而将 7 个数据存储到散列表中，最后计算等查找概率情形下，查找成功和查找不成功的平均查找长度。

(1) 根据题意，表的装载因子为a = n/m = 0.7，n = 7，因此有m = n/a = 10，即表长度为m = 10。

分别计算各个数据元素的散列地址：

H(7) = (7*3) mod 7 = 0，一次比较到位

H(8) = (8*3) mod 7 = 3，一次比较到位

H(30) = (30*3) mod 7 = 6，一次比较到位

H(11) = (11*3) mod 7 = 5，一次比较到位

H(18) = (18*3) mod 7 = 5，冲突，= 6，冲突，

= 7，三次比较到位

H(9) = (9*3) mod 7 = 6，冲突，= 7，冲突，

= 8，三次比较到位

H(14) = (14*3) mod 7 = 0，冲突，= 1，二次比较到位

根据以上得到的各数据元素的散列地址，可以得到如下散列表：图1

file:///C:/DOCUME~1/ADMINI~1/LOCALS~1/Temp/ksohtml/wps_clip_image-28951.png

图1

42题：（13分）设将n (n > 1) 个整数存放到一维数组 R中。设计一个在时间和空间两方面尽可能高效的算法。将 R 中的序列循环左移 p（0 < p < n）个位置，即将 R 中的数据由 (a0, a1, ……an-1) 变换为(ap, ap-1, …an-1, a0, a1, …, ap-1)。要求：

(1) 给出算法的基本设计思想。

(2) 根据设计思想，采用C或C++或JaVa语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

解答：此算法即有名的海豚算法。

解法一（标准答案）

算法基本思路是首先把序列{ a0, a1, ..., ap, …, an-1 }逆转为{an-1, an-2, ..., ap, …,a0 }，再分别逆转{ an-1, an-2, ..., ap }和{ ap-1, ap-2, …,a0 }，最后得到{ ap, ap+1, …, an-1, a0, …, ap-1}。

(1) 逆转算法

void reverse ( int A[ ], int left, int right ) {

int n = right-left+1;

if ( n <= 1 ) return;

if ( n <= 1 ) return;

for ( int i = 0; i < n/2; i++ ) {

      int temp = A;

      A = A[n-i-1];

      A[n-i-1] = temp;

}

}

(2) 循环左移算法

void sift_Left ( int a[ ], int n, int p ) {

  reverse ( a, 0, n-1 );

  reverse ( a, 0, n-p-1 );

      reverse ( a, n-p, n-1 );

}

第一个 reverse 函数执行了3n/2次数据移动，使用了一个辅助存储；第二个 reverse 函数执行了3(n-p)/2次数据移动，使用了一个辅助存储；第三个reverse 函数执行了3p/2次数据移动，使用了一个辅助存储；总共执行了3n次数据移动，使用了1个辅助存储。

解法二（利用最大公约数） 清华阅卷组给出

如果n与p不互质，一次循环左移只涉及间隔为p

如果n与p不互质，一次循环左移只涉及间隔为p的部分数据元素，可先求n与p的最大公约数m,再做m次循环左移，每次比上次右错一位，从而实现所有数据元素的循环左移。例如，n = 10，p = 4，m = 2，做 2 次循环左移。第1次涉及位置0-4-8-2-6，第2次涉及位置1-5-9-3-7。

(1) 求n与p的最大公约数的算法

int GCD( int n, int p ) {

//函数用辗转相除法计算n与p的最大公约数, 若n

//与p互质, 则函数返回1.

  if ( n < p ) { int temp = n;  n = p;  p = temp; }

  int r = n % p;

  while ( r != 0 ) { n = p;  p = r;  r = n % p; }

      return p;

}

(2) 循环左移算法

void sift_k ( int a[ ], int n, int p ) {

  if ( !p ) return;

  int i, j, m, k, temp;

  m = GCD(n, p);

  for ( k = 0; k < m; k++ ) {

temp = a[k];  i = k;  j = (i +p) % n;

      while ( j != k ) {

   a = a[j];  i = j;  j = ( j+p ) % n;

       }

       a = temp;

  }

}

解法三（解法二的改进型） 清航考研给出

调用子程序需要花费较多的时间和空间代价，本算法省去了计算最大公约数，仅利用一个控制变量控制循环左移的次数，效果更好。

void siftLeft_p ( int a[ ], int n, int p ) {

if ( !p ) return;

int i, j;  int temp;  int count = 0, k = 0;  

while ( count < n ) {

       i = k;  temp = a;  j = (i+p) % n;

       while ( j != k ) {

   a = a[j];  i = j;  j = (i+p) % n;

   count++;

       }

       a = temp;  count++;

       k++;

}

}

设m为n与p的最大公约数，则最内层while循环执行m次，每次循环执行n/m+1次数据移动，包括与temp的相互传送2次，总的数据移动次数为m*(n/m+1) = n+m。

特别地，当p = n时，m = n，最内层while循环不执行，总的数据移动次数2n，做了n次与temp的传出和传入；当p = 0时，总的数据移动次数为0。算法用了一个附加存储temp。

解法四（被扣了分的算法）

很多考生使用了一个附加数组，先暂存子序列

{ a0, a1, ..., ap }，再把序列中后面的n-p个数据元素前移，得{ ap, …, an-1 }；最后把暂存到临时数组中的子序列拷贝到an-1后面，得到结果：

{ ap, …, an-1, a0, a1, ..., ap }

由于使用的附加空间较多，相应也扣了一些分。算法移动元素的次数为n+p；特别地，当n = p 时，算法移动元素的次数为2n。