2009考研数据结构试题点评.doc

2009年考研计算机专业综合考试数据结构试题点评
2009年考研计算机专业综合考试是统一命题后的首次考试。本次考试统考科目包括四门计算机专业课：数据结构、计算机组成原理、操作系统和计算机网络，这四门课程合在一起称为计算机科学专业基础综合，共150分。其中数据结构占45分。总体上来看，2009年的考研数据结构试题注重对基础知识的考察。重点考察的是对基本知识点、基本概念的理解。在基础题中又有拔高，重点考察了对基础知识的应用能力、应变能力和实际动手能力。题目总的来说不难，没有出现超出考试大纲的题目。
下面我们对2009的考研数据结构试题进行简要的点评。
一、单项选择题，每小题2分，共80分。
单选题覆盖了大纲列出的各章的知识点，主要考察对各种数据结构、基本查找和排序算法的基本概念和特点的理解以及灵活运用。1-10题是数据结构部分的试题。
1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是
A.栈 B.队列 C.树 D.图
点评：此题考察对各种数据结构的特点的理解及应用。栈的特点是后进先出。队列的特点是先进先出。树的特点是除根以外的结点有且只有唯一的前驱（双亲）。图是最复杂的数据结构，它的任一结点都可以有多个前驱和后继。据题意“输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据”，处理应是先来先服务，因此答案为B。
2.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是
A．1 B.2 C.3 D.4
点评：此题考察对栈和队列的特点及基本操作的应用。根据元素的出队顺序可知元素的进栈、出栈顺序，从而判断栈中同时容纳多少元素，得出栈的容量。因bdcfeag依次出队，故元素的出栈顺序也是这样的，那么他们在栈中操作顺序依次为：a入栈、b入栈、b出栈、c入栈、d入栈、d出栈、c出栈、e入栈、f入栈、f出栈、e出栈、a出栈、g入栈、g出栈。这其间栈中数据最多有3个。因此答案为C。
3.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，7，5，6，1,2，4，则其遍历方式是

A．LRN B.NRL C.RLN D.RNL
点评：此题考察对二叉树的六种遍历的理解及应用。二叉树有六种遍历方式：先序遍历、中序遍历、后序遍历。每种遍历访问根结点的顺序不一样。先序遍历先访问根，中序遍历中间访问根，后序遍历最后访问根。一般教材中都是先左子树，后右子树，但该题用另一种方式，先右子树，后左子树。从遍历得到的序列中第一个遍历出来的元素是3，可知是中序遍历，因此答案是D。
4.下列二叉排序树中，满足平衡二叉树定义的是
A．B. C. D.
点评：此题考察对平衡二叉树的定义的掌握，平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。因此答案为B。
5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是
A．39 B.52 C.111 D.119
点评：此题考察对完全二叉树的定义的理解及对二叉树每层最大结点个数的计算。完全二叉树第一层到倒数第二层结点个数均达到每层的最大值，2i-1(i为层数)，第6层有8个叶结点，说明这棵完全二叉树最多7层，第6层的32个结点有24（32-8）结点有孩子结点，孩子结点最多有48个（24*2）,所以完全二叉树的结点数最多为：1+2+4+8+16+32+48=111。故答案为C。
6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是
I．父子关系 II.兄弟关系 III. u的父结点与v的父结点是兄弟关系
A.只有II B.I和II C.I和III D.I、II和III
点评：此题考察森林转化为二叉树时结点之间的关系的变化。根据森林转化为二叉树的转化过程可知，一个结点ｕ和它的第二个孩子结点ｖ转化为二叉树后就变为结点u是结点v的父结点的父结点，同一个结点的第一个孩子u和第三个孩子v转化为二叉树后也变为结点u是结点v的父结点的父结点，因此可以推出u和v在原来的森林中要么是父子关系，要么是兄弟关系。因此答案是B。
7.下列关于无向连通图特性的叙述中，正确的是
I．所有顶点的度之和为偶数 II.边数大于顶点个数减1
III.至少有一个顶点的度为1
A.只有I B. 只有II C.I和II D.I和III
点评：此题考察图的度与边的关系、无向连通图特性。在图中所有顶点的度之和为边数的2倍，而连通图中边数不为零，所以一定是偶数。N个顶点的无向连通图至少有n-1条边，顶点的度至少是1。因此答案为A。
8.下列叙述中，不符合m阶B树定义要求的是
A．根节点最多有m棵子树 B.所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接
点评：此题考察对m阶B树的定义的理解与应用。B树是一种多叉平衡查找树。一棵m阶的B树，或为空树，或为满足下列特性的m叉树：
①树中每个结点至多有m棵子树；
②若根结点不是叶子结点，则它至少有两棵子树；
③除根之外的所有非叶子结点至少有「m/2]棵子树；
　　④所有的非叶子结点中包含下列数据信息
　　　(n，A0，K1，A1，K2，A2，…，Kn，An)
　　其中：Ki(i=1，2，…，n)为关键字，且Ki<Ki+1(i=1，2，…，n-1)：Ai(i=0，1，…，n)为指向子树根结点的指针，且Ai-1所指子树中所有结点的关键字均小于Ki(i=1，2，…，n)，An所指子树中所有结点的关键字均大于Kn，n（「m/2]-1≤n≤m-1）为关键字的个数（或n+1为子树个数）
⑤所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。据此定义可知答案为D。
9.已知关键序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是
A．3，5，12，8，28，20，15，22，19
B. 3，5，12，19，20，15，22，8，28
C．3，8，12，5，20，15，22，28，19
D. 3，12，5，8，28，20，15，22，19
点评：此题考察对堆调整算法--“筛选”算法的应用。筛选算法要求根的左右子树必须是堆。把3插入后，关键序列变为5，8，12，19，28，20，15，22，3，以5为根的左右子树的堆结构可能被破坏，因此必须重建堆，从n/2个结点开始调用筛选算法，直到第一个结点，就可重建堆。答案为A。
10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是
A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序
点评：此题考察对各种排序方法的步骤、特点的理解及应用。起泡排序第i趟结束后可以把第i大的数放到正确位置。插入排序第i趟结束后前i个元素是有序的，但不一定是这些元素的最后位置。选择排序第i趟结束后可以把第i小的数放到正确位置。二路归并排序第i趟结束后可以得到长度为2i 的有序子序列。故答案为B。
二、综合应用题
综合应用题主要考察综合运用基本知识分析问题、解决问题的能力。41-42为数据结构部分的题。一道问答题、一道算法设计题。
41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假定从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；
②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；
③重复步骤②，直到u是目标顶点时为止。
请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。
点评：此题考察对最短路径的理解及应用。最短路径就是从初始顶点到目标顶点之间的路径上权值和最小的路径。题目中的方法在选择顶点时并没有找到下一条权值最下的边，所以该方法求得的路径不一定是最短路径。例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径为A→B→C，事实上其最短路径为 A→D→C。

42.（15分）已知一个带有表头结点的单链表，结点结构为
data
link

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data值，并返回1；否则，只返回0。要求：
（1） 描述算法的基本设计思想
（2） 描述算法的详细实现步骤
（3） 根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。
点评：此题是一道算法设计题，算法设计是数据结构课程的一个重点内容，也是一个难点。此题考察对单链表的基本运算的理解及灵活运用。一般教材中在单链表中查找结点都是从头数第i个结点，而本题中要倒数第k个结点，难度就大了，要把单链表的基本运算进行改写，关键在于要查倒数第K个位置上的结点，此时需要两个流动指针，一个整型变量，
从链表头向后遍历，其中指针P1指向当前遍历的结点，指针P指向P1所指向结点的前K个结点，如果P1之前没有K个结点，那么P指向表头结点。用整型变量i表示当前遍历了多少结点，当i>k时，指针P随着每次遍历，也向前移动一个结点。当遍历完成时，P或者指向表头就结点，或者指向链表中倒数第k个位置上的结点。
算法描述：
int LocateElement(linklist list,int k)
{
P1=list->link;
P=list;
i=1;
while(P1)
{
P1=P1->link;
i++;
if(i>k) P=P->next; //如果i>k,则p也往后移
}
if(P==list) return 0; //说明链表没有k个结点
else
{
printf(“%d\n“,P->data);
return 1;
}
}