《考研数据结构试题点评》由会员分享，可在线阅读，更多相关《考研数据结构试题点评（10页珍藏版）》请在金锄头文库上搜索。
1、2010 年考研计算机专业综合考试 数据结构试题点评2010 年考研计算机专业综合考试是统一命题后的第二次考试。本次考试统考科目仍然 包括四门计算机专业课： 数据结构、 计算机组成原理、操作系统 和计算机网络，这四门课程 合在一起称为计算机科学专业基础综合，共 150 分。其中数据结构仍然占 45 分。总体上来看， 2010 年的考研数据结构试题仍然注重对基础知识的考察。重点考察的是 对基本知识点、基本概念的理解及应用。题目的难度适中，没有出现超出考试大纲的题目， 也没有一眼就能看出答案的题目； 在基础题中又有拔高， 本次考试并非考查基本概念的填空， 考题比较灵活，重点考察了对基础知识的应用能
2、力、应变能力和实际动手能力。与 2009 年 的考研数据结构试题相比，难度略有提高，考察的内容更加深入、灵活，并且有针对性。下面我们对 2010 的考研计算机专业综合考试进行简要的分析。一、单项选择题这部分共有 40个选择题，每题 2分，共 80分。单选题覆盖了大纲列出的各章的知识点， 主要考察对各种数据结构、 基本查找和排序算 法的基本概念和特点的理解以及灵活运用。1-11题是数据结构部分的试题。1. 若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三 次进行退栈工作，则不可能得到的出栈序列是（ ）A. dcebfaB. cbdaefC. bcaefdD. af
3、edcb点评： 此题考察对栈的基本操作（进栈、退栈）的理解和应用。栈的特点是后进先出。若元素a、b、c、d、e、f依次进栈，要得到出栈序列 afedcb，需要进行的操作为：a进栈，a 出栈，b，c，d，e，f分别进栈，然后f,e，d，c，b分别依次出栈，连续出栈操作超过3次。故答案为 D。2. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到 的顺序是（ ）A. bacdeB. dbaceC. dbcaeD. ecbad点评：此题考察对可以两端入队， 一端出队的队列的操作。 一般教材中讨论的队列都是一端入队，一端出队，而本题中的队列可以两端入队，一端出队，入队出队操作要
4、复杂一些,是对教材内容的深化。对于序列dbcae,要先得到d, a, b, c必须先从一端入队，d再从另端入队，d出队得到序列中的d,但队列是先进先出，下面要得到b,而b是在a之后进队的,C。只有a先出队，b才能出队，故得不到所要求的序列。所以答案为3. 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（Nul1点评：此题考察对后序线索树的定义的理解。先得到后序序列为dbca，然后在后序线索DoA.13 ,48B.24,48C.24,53D.24,90树中将空的左孩子域指向其后序前驱，空的右孩子域指向其后序后继，因此答案为4. 在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二
5、叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点保存的关键字分别是（点评:此题考察对平衡二叉树插入操作的理解及应用，要熟悉平衡二叉树调整平衡的种旋转方法。 48插入后作为 37的右孩子， 此时破坏了二叉树的平衡，需旋转，旋转类型为 RL 型，根据RL型的操作可知答案为 C。5. 在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则数T的叶结点个数是（）A. 41B. 82C. 113D. 122点评： 此题考察对树中度、结点、 叶子结点个数的计算。一般教材中多是对二叉树的讨论，二叉树性质3有结论：no= n2+1。而本题是一棵度为4
6、的树，因此需要引深。no=n2+2*ns+3*n 4+1=1+2*10+3*20+1=82。故答案为 B。6. 对n（n2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）A. 该树一定是一棵完全二叉树B. 树中一定没有度为1的结点C. 树中两个权值最小的结点一定是兄弟结点D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值点评： 此题考察对哈夫曼树的特性的理解。根据哈夫曼算法哈夫曼树中没有度为1的结点，两个权值最小的结点一定是兄弟结点， 任一非叶结点的权值一定不小于下一层任一结点 的权值，但 哈夫曼树不是一棵 完全二叉树。因此答案是 A。7. 若无向图G=（V , E）
7、中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边 数最少是（ ）A. 6B. 15C. 16D. 21点评：此题考察对图的连通性的理解。一个有n个顶点的图要连通至少需要 n-1条边。故答案是 A。8. 对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）A. 4B. 3C. 2D. 1点评：此题考察对拓扑序列的理解。拓扑序列不唯一。根据拓扑序列的求法可知此题有3个不同的拓扑序列。故答案为B。9. 已知一个长度为16的顺序表L,其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（）A. 4B. 5C. 6D. 7点评：此题考察对折半查找最坏情况下的查找长
8、度的理解。折半查找的查找过程可用一棵判定树来表示，折半查找失败时的过程对应判定树中从根结点到某个含空指针的结点的路径，因此，折半查找失败时关键字的比较次数最多不超过判定树的深度。n个结点的判定树的深度和n个结点的完全二叉树的深度相等，均为-log 2n+1。故答案为B。10. 采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是（）A. 递归次数与初始数据的排列次序无关B. 每次划分后，先处理较长的分区可以减少递归次数C. 每次划分后，先处理较短的分区可以减少递归次数D. 递归次数与每次划分后得到的分区处理顺序无关点评：此题考察对递归方式下的快速排序算法的理解与应用。快速排序的
9、递归的次数与 初始数据的排列顺序有关，递归次数与每次划分后得到的分区处理顺序无关。故答案为D。11. 对一组数据（2，12，16，88, 5，10）进行排序，若前三趟排序结果如下：（）第一趟：2，12，16，5，10，88第二趟： 2，12，5，10，16， 88第三趟： 2，5，10，12，16， 88 则采用的排序方法可能是A. 起泡排序B. 希尔排序C. 归并排序D. 基数排序点评：此题考察对各种排序方法的步骤、特点的理解及应用。起泡排序第i 趟结束后可以把第 i 大的数放到正确位置。希尔排序第 i 趟结束后把相距为某一值的同一组中元素排好 序。归并排序第 i 趟结束后可以得到长度为 2
10、i 的有序子序列。 基数排序第 i 趟按第 i 位分配 收集。 故答案为 A。二、综合应用题综合应用题主要考察综合运用基本知识分析问题、解决问题的能力。 41-42 为数据结构 部分的题。 出题风格仍然沿用第一次的出题风格，一道问答题、一道算法设计题。41. (10分)将关键字序列( 7、8、30、11、18、9、14)散列 存储到散列表中，散列 表的存储空间是一个下标从0开始的一维数组，散列函数：H(key)=(key X3) MOD T ,处理冲突采用线性探测再散列法，要求装填(载)因子为0.7。问题：( 1)请画出所构造的散列表；(2)分别计算等概率情况下查找成功和查找不成功的平均查找长
11、度。点评： 此题考察对 散列表相关知识的理解及应用， 要求能够构造散列表， 并且能够计算 等概率情况下查找成功和查找不成功的平均查找长度。(1)本题中涉及到装填(载)因子 a，在散列函数中还有一个未知数 T (可认为是散 列表的长度)。因此需先求出 T。a =数据个数/表长，由装载因子0.7，数据总数7个可知 存储空间长度为10即T =10。所以，散列函数为 H(key)=(key X3) MOD 10 ,线性探测再散列 函数为：Hi=( H(key)+d i) MOD 10 , (di=1,2,3,9)因此，各数据的下标为：H(7)=(7*3) MOD 10=1H(8)=(8*3) MOD
12、10=4H(30)=(30*3) MOD 10=0H(11)=(11*3) MOD 10=3H(18)=(18*3) MOD 10=4H1=(H(18)+1) MOD 10=5H(9)=(9*3) MOD 10=7H(14)=(14*3) MOD 10=2构造的散列表为：地址0123456789关键字30714118189(2)在等概率情况下，手工计算查找成功时的平均查找长度可用下列公式计算:ASL succ=1表中装入的元素个数nCi按照上述公式，在等概率情况下，查找成功时的平均查找长度为:查找成功的 ASL=( 1+1 + 1 + 1+2+1 + 1)/7=8/7在等概率情况下，查找不成功
13、时的平均查找长度是指在表中查找不到待查记录，但找到 插入位置的平均探测次数， 它是表中所有可能散列的位置上要插入新记录时为找到空位置的 探测次数的平均值。在等概率情况下，手工计算查找不成功时的平均查找长度可用下列公式 计算：ASL unsucc=1哈希函数取值个数Cii 1其中，Ci为哈希函数取值为i时查找不成功的比较次数。查找不成功的情况：(1)遇到空单元(2)按处理冲突的方法完全探测一遍后仍未找到。0到r-1相当于r个不成功查找的入口，从每个入口进入后，直到确定查找不成功为止，其 关键字比较次数就是与该入口对应的不成功查找长度。在本题中，在线性探测再散列法处理冲突得到的哈希表中查找，假设待
14、查的关键字k不在该表中，若 H(k)=O，将HTO中的关键字和k比较后发现HTO为空，即查找不成功， 比较次数为1 ；若H(k)=1，则必须将HT0.5中的关键字和k比较后，再与HT6中的关键 字比较时发现HT6为空，查找失败，比较次数为7,同理，位置2, 3,，5, 6的比较次数分别为6, 5,，2, 1次，位置7, 8, 9的比较次数分别为 2, 1 , 1，因此，在等概率 情况下，查找不成功时的平均查找长度为查找不成功的 ASL= ( 7+6+5+4+3+2+1+2+1+1 )/10=3.242. (13分)设将n ( n1)个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能
15、高效的算法，将R中保存的序列循环左移p(0pn)个位置，即将 R中的数据由(X0,X1,x-1)变换为(Xp,Xp+1,X|-1,X0,X1,X-1)。要求：( 1)给出算法的基本设计思想。(2)根据设计思想，采用C或C+或JAVA语言描述算法，关键之处给出注释。( 3)说明设计算法的时间复杂度和空间复杂度。点评： 此题是一道算法设计题， 算法设计是数据结构课程的一个重点内容， 也是一个难 点。此题考察对顺序表的基本运算的理解及灵活运用、 时间复杂度和空间复杂度的概念及应 用。要求时间和空间两方面都尽量最优的情况下， 实现数组的循环左移， 还要求算法的时间、 空间的复杂度。具体要求给出算法思想，并且能用C、C+、Java描述该算法。思想可以描述为：建立一个可以存放P个整数的辅助队列，将数组 R中的前p个整数依次进队；将 R中后面的 n-p
