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 点评：此题考察对二叉树的六种遍历的理解及应用。二叉树有六种...
