2009-2010全国考研试题

12020/2/5一、单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。请在答题卡上将所选项的字母涂黑。22020/2/51.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是()A.栈B.队列C.树D.图32020/2/52.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是()A.1B.2C.3D.442020/2/53.给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是()A.LRNB.NRLC.RLND.RNL52020/2/54.下列二叉排序树中，满足平衡二叉树定义的是()62020/2/55.已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是()A.39B.52C.111D.11972020/2/56.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是()Ⅰ.父子关系Ⅱ.兄弟关系Ⅲ.u的父结点与v的父结点是兄弟关系A.只有ⅡB.Ⅰ和ⅡC.Ⅰ和ⅢD.Ⅰ、Ⅱ和Ⅲ82020/2/57.下列关于无向连通图特性的叙述中，正确的是()Ⅰ.所有顶点的度之和为偶数Ⅱ.边数大于顶点个数减1Ⅲ.至少有一个顶点的度为1A.只有ⅠB.只有ⅡC.Ⅰ和ⅡD.Ⅰ和Ⅲ92020/2/59.已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是（）A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19102020/2/510.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）A.起泡排序B.插入排序C.选择排序D.二路归并排序112020/2/51．若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b122020/2/52．某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是（）A.b,a,c,d,eB.d,b,a,c,eC.d,b,c,a,eD.e,c,b,a,d132020/2/53.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（）142020/2/54.在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）A.13、48B.24、48C.24、53D.24、90152020/2/55.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是A.41B.82C.113D.122162020/2/56.对n（n≥2）个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（）A.该树一定是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶结点的权值一定不小于下一层任一结点的权值172020/2/57.若无向图G=（V，E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是（）A.6B.15C.16D.21182020/2/58.对下图进行拓扑排序，可以得到不同拓扑序列的个数是（）A.4B.3C.2D.1abced192020/2/59.已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多是（）A.4B.5C.6D.7202020/2/510.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）A.递归次数与初始数据的排列次序无关B.每次划分后，先处理较长的分区可以减少递归次数C.每次划分后，先处理较短的分区可以减少递归次数D.递归次数与每次划分后得到的分区的处理顺序无关212020/2/5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.基数排序222020/2/5二、综合应用题：41－47小题，共70分。请将答案写在答题纸指定位置上。232020/2/541.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点v,加入到最短路径中，修改当前顶点u=v；③重复步骤②，直到u是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。242020/2/5上述方法不能求得最短路径。离u最近未必离初始顶点最近。例如，下图求v0到v1的最短路径，按题目所给方法得45（v0-v2-v3-v1）,并非最短路径。详细证明请参照Dijkstra或Floyd算法。252020/2/542.（15分）已知一个带有表头结点的单链表，结点结构为(data,link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求：⑴描述算法的基本设计思想；⑵描述算法的详细实现步骤；⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C++或JAVA语言实现），关键之处请给出简要注释。262020/2/5算法思想：设指针q指向链表,指针p指向链表第一元素，q是p的前驱（广义）。p向后移动k个结点后，p和q相距k。之后同步移动指针p和q，到p=null时，q指向倒数第k个结点。另一算法是链表结点入栈，弹出第k个结点，不如前者性能好。算法的主要语句段如下：p=list-link;//p指向当前待处理元素q=list;//若成功,q指向倒数第k个元素i=1;while(p&&ik){i++;p=p-link;}//指针p指向链表第k个结点if(p==null){printf(“不存在\n”);return0;}//所给k太大while(p){q=q-link;p=p-link;}//向链表尾同步移动指针p和qreturn1;//q指向倒数第k个结点272020/2/541．（10分）将关键字序列（7,8,30,11,18,9,14）散列存储到散列表中，散列表的存储空间是一个下标从0开始的一维数组,散列函数为：H（key）=(key×3)MOD7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。（1）请画出所构造的散列表。（2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。282020/2/5由装填因子为0.7，表中记录数为7个，可知散列表长度为10散列函数为：H(key)=(keyx3)MOD7线性探测再散列函数为：(H(key)+di)MOD10其中：di=（1，2，3……9）所构造散列表如下：长度表中的记录数/散列表α7148113018912111330123456789292020/2/5ASLSS=1/7(4*1+2*1+2*3)=12/7=1.71ASLUN=1/10(3+2+1+2+1+5+4+3+2+1)=2.47148113018912111330123456789302020/2/542、（13分）设将n（n1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移P（0Pn）个位置，即将R中的数据由（X0,X1,…,Xn-1）变换为（XP,Xp+1,…,Xn-1,X0,X1,…,Xp-1）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。312020/2/5解法一：(1)算法设计思想：按照下标0到p-1、p到n-1、0到n-1的顺序，将这三段分别逆置，最后的结果即为所求。(2)voidleftshift(intR[],intp,intn){elemtypet;//t和数组R中的元素具有相同类型for(i=0;ip/2;i++)//逆置0..p-1段{t=R[i];R[i]=R[p-1-i];R[p-1-i]=t;}for(i=p;i(n+p)/2;i++)//逆置p..n-1段{t=R[i];R[i]=R[n-1-i+p];R[n-1-i+p]=t;}for(i=0;in/2;i++)//逆置0..n-1段，即整个数组逆置{t=R[i];R[i]=R[n-1-i];R[n-1-i]=t;}}//算法初始调用:leftshift(R,p,n)，各参数意义如上。(3)算法执行了两趟逆置，时间复杂度为O(n);用了一个辅助变量空间，空间复杂度为O(1)。讨论：若采用直接左移p位，空间复杂度仍为O(1)，但时间复杂度为O(np)。322020/2/5解法二：（1）建立一个可以放下p个整数的辅助队列，将数组R中的前p个整数依次进入辅助队列，将R中后面的n-p个整数依次前移p个位置，将辅助队列中的数据依次出队，依次放入R中第n-p个整数开始的位置。332020/2/5（2）使用c语言描述算法如下：voidShift(int*pR,intn,intp)//pR是指向数组R的指针，n为存放的整数个数，//p为循环左移的个数{inttemp[p];//辅助数组，存放要移出的整数。inti=0;while(ip){temp[i]=pR[i];i++;}//将R中前p个数据存入辅助数组中。i=0;while(in-p){pR[i]=pR[p+i];i++;}//将R中从第p个整数开始的整数前移p个位置。i=0;while(ip){pR[n-p+i]=temp[i];i++;}//将辅助数组中的p个数据放到R中第n-p个数据的后面。}（3）所设计的算法的时间复杂度为O(n),空间复杂度为O(p)