2021数据结构考研数据结构与C语言考研名校考研
真题
一、
名校考研真题解析
为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。[2009年联考真题] A．栈 B．队列 C．树 D．图
【答案】B ！~
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结
构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
100．设哈希表长M=14，哈希函数H（KEY）=KEY MOD 11。表中已有4个结点：ADDR（15）=4，ADDR（38）=5，ADDR（61）=6，ADDR（84）=7，其余地址为空，如用二次探测再哈希法解决冲突，关键字为49的结点的地址是（ ）。[东华大学考研真题] A．8
B．3 C．5 D．9
【答案】D ！~
【解析】15，38，61，84用哈希函数H（key）=key计算后得地址:4,5,6,7 49计算后为5,发生冲突. 用二次探测再散列法解决冲突: 1:（key+1^2）=（49+1）=6,仍然发生冲突. 2:（key-1^2）=（49-1）=4,仍然发生冲突. 3:（key+2^2）=（49+4）=9,不再发生冲突.
101．设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是（ ）。[2009年联考真题] A．1 B．2 C．3 D．4
【答案】C ！~
【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队
顺序即为人队顺序。在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b，表明栈内还有元素a，b出栈前的深度为2；第二个出栈元素为d，栈内元素为a和c，d出栈前的深度为3；c出栈后，剩余元素为a，c出栈前的深度为2；f出栈
后，剩余元素为a和e，f出栈前的深度为3；e出栈后，剩余元素为a，e出栈前的深度为2；a出栈后，无剩余元素，a出栈前的深度为1；g出栈后，无剩余元素，g出栈前的深度为1。所以栈容量至少是3。
102．给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）。[2009年联考真题] A．LRN B．NRL C．RLN D．RNL
【答案】D ！~
【解析】对“二叉树”而言，一般有三条搜索路径：
①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历； ③先右（子树）后左（子树）的遍历。
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR、中序遍历LNR、后序遍历LRN，第3种搜索路径方式则是不常使用的NRL、RNL、RLN。本题考查的是第3种搜索路径方式的一种情况。
根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D。
103．排序算法的稳定性是指（ ）。[北京理工大学考研真题] A．经过排序之后，能使值相同的数据保持原顺序中的相对位置不变 B．经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变 C．算法的排序性能与被排序元素的数量关系不大 D．算法的排序性能与被排序元素的数量关系密切
【答案】A ！~
【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记
录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。
104．下列二叉排序树中，满足平衡二叉树定义的是（ ）。[2009年联考真题]
【答案】B ！~
【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过
1的二叉树。A项中根结点的平衡因子是2；B项中每个结点的平衡因子的绝对值均不超过1；C项中根结点的平衡因子是-2；D项中根结点的平衡因子是3。 105．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。[2009年联考真题] A．39 B．52 C．111 D．119
【答案】C ！~
【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下
层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，高度为6的满二叉树的结点数是26-1＝63。又根据二叉树的性质1可知，题目中二叉树的第6层结点数是25＝32个结点，已知有8个叶子结点，那么其余32-8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可达26-1+（25-8）×2＝111。
106．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。[北京航空航天大学考研真题]
2021数据结构考研数据结构与C语言考研名校考研真题
