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的容量至少是 A1 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，则其遍历方式是 ALRN B.NRL C.RLN D.RNL 点评：此题考察对二叉树的六种遍历的理解及应用。二叉树有六种遍历方式：先序遍历、中序遍历、后序遍历。每种遍历访问根结点的顺序不一样。先序遍历先访问根，中序遍历中间访问根，后序遍历最后访问根。一般教材中都是先左子树，后右子树，但该题用另一种方式，先右子树，后左子树。从遍历得到的序列中第一个遍历出来的元素是3，可知是中序遍历，因此答案是D。4.下列二叉排序树中，满足平衡二叉树定义的是 AB. C. D. 点评：此题考察对平衡二叉树的定义的掌握，平衡二叉树又称AVL树，它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差的绝对值不超过1。因此答案为B。5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 A39 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)为关键字，且Kik时，指针P随着每次遍历，也向前移动一个结点。当遍历完成时，P或者指向表头就结点，或者指向链表中倒数第k个位置上的结点。算法描述： int LocateElement(linklist list,int k) P1=list-link; P=list; i=1;while(P1) P1=P1-link; i+; if(ik) P=P-next; /如果ik,则p也往后移 if(P=list) return 0; /说明链表没有k个结点 else printf(“%dn“,P-data); return 1;