2021数据结构考研数据结构与C语言考研名校考研真题

2021数据结构考研数据结构与C语言考研名校考研真题一、名校考研真题解析为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。［2009年联考真题］A.栈B.队歹I」C.树D.图【答案】B!~【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。100.设哈希表长M=14，哈希函数H(KEY)=KEYMOD11。表中已有4个结点：addr(15)=4,ADDR(38)=5,ADDR(61)=6,ADDR(84)=7,其余地址为空，如用二次探测再哈希法解决冲突，关键字为49的结点的地址是( )。［东华大学考研真题］A.8C.5D.9【答案】D!~【解析】15,38,61,84用哈希函数H(key)=key%11计算后得地址:4,5,6,749计算后为5,发生冲突.用二次探测再散列法解决冲突:1:(key+1八2)%11=(49+1)%11=6，仍然发生冲突.2:(key-1-2)%11=(49-1)%11=4，仍然发生冲突.3:(key+2八2)%11=(49+4)%11=9，不再发生冲突.101.设栈S和队列Q的初始状态均为空，元素2,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是()。［2009年联考真题］A.1B.2C.3D.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.LRNB.NRLC.RLND.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.39B.52C.111D.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）x2=111o106.下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（ ）。［北京航空航天大学考研真题］A.选择排序法B.插入排序法C.快速排序法D.堆排序法【答案】A!~【解析】选择排序的基本思想是：第i趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1](0<i<n-1)，该趟排序则是从当前无序区中选出关键字最小的记录R[k],将它与无序区的第1个记录R[i]交换，使R[0..i]和R[i+1..n-1]分别变为新的有序区和新的无序区。107.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是( )。[2009年联考真题]I.父子关系口.兄弟关系m.u的父结点与v的父结点是兄弟关系A.只有IB.I和口C.I和田D.I、口和田【答案】B!~【解析】首先，在二叉树中，若结点u是结点v的父结点的父结点，那接下来根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中:情况（1），在原来的森林中情况（1），在原来的森林中u是v的父结点的父结点;情况（2），在森林中u是v的父结点;，在森林中u是v的父结点的兄弟;，在森林中u与v是兄弟关系。由此可知，题目中的I、口是正确的。108.下列关于无向连通图特性的叙述中，正确的是（ ）。［2009年联考真题］I.所有的顶点的度之和为偶数口.边数大于顶点个数减1田.至少有一个顶点的度为1A.只有IB.只有口C.I和口D.工和田【答案】A!~【解析】在图中，顶点的度TD()之和与边的数目满足关系式： 二2e(n为图的总结点数，e为总边数)，因此，1项正确。对于口、田项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图(1)所示，“边数大于顶点个数减1”的反例如下图(2)所示。

CM?109.设被排序的结点序列共有N个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为()。［上海交通大学考研真题］A.O(N),O(N),O(N)B.O(N),O(N*log2N),0(N*log2N)C.O(N),O(N*log2N),0(N2)D.O(N2),O(N*log2N),0(N2)【答案】C!~【解析】因为该序列中的结点已经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为0(N)。对于采用归并法，它是一种稳定的排序方法，它的时间复杂度为O（Nlog2N）。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为O（N2）。110.下列叙述中，不符合m阶B树定义要求的是（ ）。［2009年联考真题］A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接【答案】D!~【解析】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B+树的定义，而B-树中没有。因此，D项是错误的。111.已知关键字序列5,8,12,19字8,20,15,22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。［2009年联考真题］A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【答案】A!~【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）~（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。<5>20112.有些排序算法在每趟排序过程中，都会有一个元素被放置在其最终的位置上，下列算法不会出现此情况的是（ ）。［北京交通大学考研真题］A.希尔排序B.堆排序C.起泡排序D.快速排序【答案】A!~【解析】选择排序、起泡排序和堆排序一趟排序后，在序列首部或尾部应该有最大或最小值。113.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）。［2009年联考真题］A.起泡排序B.插入排序C.选择排序D.二路归并排序【答案】B!~【解析】经过两趟排序后，A项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B项插入排序的结果是前三个数有序即可；C项选择排序结果是两个最小的元素在最前面按顺序排好；D项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B项正确。在有向图的邻接表存储结构中，顶点V在链表中出现的次数是（ ）。［北京理工大学考研真题］A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v的边数【答案】B!~【解析】在有向图中，第j个链表中的结点个数只是顶点vi的出度，为求入度，必须遍历整个邻接表。因此顶点v在链表中出现的次数是顶点v的入度。83.若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。［2010年联考真题］A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b【答案】D!~【解析】4个选项所给序列的进、出栈操作序列分别为：选项A.Push,Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Pop选项B.Push,Push,Push,Pop,Pop,Push,Pop,Pop,Push,Pop,Push,Pop选项C.Push,Push,Pop,Push,Pop,Pop,Push,Push,Pop,Push,Pop,Pop选项D.Push,Pop,Push,Push,Push,Push,Push,Pop,Pop,Pop,Pop,Pop按照题目要求，不允许连续三次进行退栈操作，所以D项所给序列为不可能得到的出栈顺序。.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是（）。[2010年联考真题]A.b,a,c,d,eB.d,b,a,c,eC.d,b,c,a,eD.e,c,b,a,d【答案】C!~【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。假设L代表从左端入队，R代表从右端入队，出队都是从左端L出。四个选项所给序列的进队操作序列分别为：选项A.aL（或aR）,bL,cR,dR,eR选项B.aL（或aR）,bL,cR,dL,eR选项C.不可能出现选项D.aL（或aR）,bL,cL,dR,eL.已知有向图6=（丫〃），其中V={V1,V2,V3,V4,V5,V6,V7},E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>，<V3，V5>，<V3，V6>，<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。［北京航空航天大学考研真题］A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.%、匕，峰，%，％，乂，叫【答案】A!~【解析】设G=（V，E）是一个具有n个顶点的有向图，V中顶点序列v1，v2，…，vn，能被称为拓扑序列的条件：若<vi，于是图中的边（即从顶点vi到3有一条路径），则在序列中顶点vi必须排在顶点七之前。根据上面拓扑序列的定义，就可以得出G的拓扑序列是V1，V3，V4，V5，V2，V5.V7。.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。［2010年联考真题］【答案】D!~【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息、，解题思路较简单。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。所以正确选项为D。.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是( )。［2010年联考真题］379037A.13、48B.24、48C.24、53D.24、90【答案】C!~【解析】题目中，插入48以后，树根结点的平衡因子由-1变为-2，失去平衡。这属于RL（先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：0）插入的后,调整前 0）先右旋转 0）再左旋转显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24,53。.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ ）。［南京理工大学考研真题］A.G中有弧＜Vi,Vj＞B.G中有一条从Vi到Vj的路径C.G中没有弧＜Vi,VJD.G中有一条从Vj到Vi的路径【答案】D【解析】若想实现图的一个拓扑排序，需要满足的一个条件为：若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。又因为若G中有一条从Vj到Vi的路径，则在拓扑序列中Vi不可能在Vj前。89.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）。［2010年联考真题］A.41B.82C.113D.122【答案】B!~【解析】根据二叉树的性质3的推广公式：N0=l+N2+2N3+...+（m-1）Nm可直接在将数据带入公式，即No=l+N2+2N3+3N4=l+1x1+2x10+3x20=82o树T的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。69.已知循环队列存储在一维数组A［0…n-1］中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A［0］处，则初始时front和rear的值分别是（ ）。［2011年联考真题］A.0,0B.0,n-1C.n-1,0D.n-1,n-1【答案】B!~【解析】题目要求队列非空时front和rear分别指向队头元素和队尾元素，若初始时队列为空，且要求第1个进入队列的元素存储在A［0］处，则此时front和rear的值都为0。由于进队操作要执行（rear+1）%n，则初始时front的值为0、rear的值为n-1。70.设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。［西安电子科技大学考研真题］A.n-1B.nC.n+1D.n+2【答案】C!~【解析】B中右指针为空的点，就是森林中的每棵树中的每个非终端结点最右边那个子树的根结点，也可以说是每棵树的每一棵子树的每一层的最后一个结点。每个非终端结点都有一个最右边的结点（X）,转化成二叉树的时候，X就是那个右指针为空的点，所以F中N个非终端结点就对应着N个B中右指针为空的结点。还有一个结点，就是森林中最右边那个树的根结点（T）,如果这个森林只有一棵树，这个结点就是这棵树的根结点，这个结点不是任何结点的最右边的孩子，但是转化成二叉树B的时候，他的右指针可以是为空。所以答案的n+L71.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。［2011年联考真题］A.257B.258C.384D.385【答案】C!~【解析】由n=n0+n1+n2和n0=n2+1可知,n=2n0-1+n1,即2n0-1+n1二768,显然n1=1,2no=768，则n0=384，所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为［768/2］,故非叶子结点数为384，而叶子结点的个数为768-384=384。（［乂］表示不大于x的最大整数，比如［3.14］=3）。72.若一棵二叉树的前序遍历序列和后序遍历序列分别为l,2,3,4和4,3,2,1,则该二叉树的中序遍历序列不会是（ ）。［2011年联考真题］A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4