2021年北京化工大学考研842数据结构考试样题.pdf
第1页共8页 北京化工大学2XXX年攻读硕士学位研究生入学考试数据结构试题注意事项1.答案必须写在答题纸上,写在试卷上均不给分。2.答题时可不抄题,但必须写清题号。3.答题必须用蓝、黑墨水笔或圆珠笔,用红色笔或铅笔均不给分。一、单项选择题:140小题,每小题2分,共80分。下列每题给出的选项中,只有一个选项是最符合题目要求的。请在答题卡上将所选 项的字母涂黑。1.设n是描述问题规模的非负整数,下面程序片段的时间复杂度是x=2;while(xn/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是A.1B.2C.3D.43.若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替进行。 但不允许连续三次进行退栈工作,则不可能得到的出栈序列是A:dcebfaB:cbdaefC:dbcaefD:afedcb4.某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作,则不可能得到的顺序是A:bacdeB:dbaceC:dbcaeD:ecbad5.元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d开头的序列个数是 第2页共8页 A.3B.4C.5D.66.已知循环队列存储在一维数组A0.n-1中,且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要求第一个进入队列的元素存储在A0处,则初始时front和rear的值分别是A.0,0B.0,n-1C.n-1,0D.n-1,n-17.给定二叉树图所示。设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是ALRNB.NRLC.RLND.RNL 8.下列二叉排序树中,满足平衡二叉树定义的是9.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是A39B.52C.111D.119 10.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是 第3页共8页 I父子关系II.兄弟关系III.u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III11.下列线索二叉树中(用虚线表示线索),符合后序线索树定义的是 12.在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树,在新平衡二叉树中,关键字37所在结点的左、右子结点中保存的关键字分别是A:13,48B:24,48C:24,53D:24,9013.在一棵度为4的树T中,若有20个度为4的结点,10个度为3 的结点,1个度为2的结点,10个度为1的结点,则树T的叶节点个数是A:41B:82C:113D:122 第4页共8页 14.对n(n大于等于2)个权值均不相同的字符构成哈夫曼树,关于该树的叙述中,错误的是A:该树一定是一棵完全二叉树B:树中一定没有度为1的结点C:树中两个权值最小的结点一定是兄弟结点D:树中任一非叶结点的权值一定不小于下一级任一结点的权值15.若一棵完全二叉树有768个结点,则该二叉树中叶结点的个数是A.257B.258C.384D.38516.若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1,则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4, 3,2,117.已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是A.115B.116C.1895D.189618.对于下列关键字序列,不可能构成某二叉排序树中一条查找路径的序列是A.95,22,91,24,94,71B.92,20,91,34,88,35C.21,89,77,29,36,38D.12,25,71,68,33,3419.下列关于无向连通图特性的叙述中,正确的是 I所有顶点的度之和为偶数II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB.只有IIC.I和IID.I和III20.若无向图G-(V.E)中含7个顶点,则保证图G在任何情况下都是连通的,则需要的边数最少是A:6B:15C:16D:2121.对下图进行拓扑排序,可以得到不同的拓扑序列的个数是 第5页共8页 A:4B:3C:2D:122.下列关于图的叙述中,正确的是.回路是简单路径.存储稀疏图,用邻接矩阵比邻接表更省空间.若有向图中存在拓扑序列,则该图不存在回路A.仅B.仅、C.仅D.仅、23.下列叙述中,不符合m阶B-树定义要求的是A.根节点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接 24.已知一个长度为16的顺序表L,其元素按关键字有序排列,若采用折半查找法查找一个不存在的元素,则比较次数最多是A:4B:5C:6D:725.为提高散列(Hash)表的查找效率,可以采取的正确措施是.增大装填(载)因子.设计冲突(碰撞)少的散列函数.处理冲突(碰撞)时避免产生聚集(堆积)现象A.仅B.仅C.仅、D.仅、26.已知关键序列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,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,1927.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是A起泡排序B.插入排序C.选择排序D.二路归并排序28.采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述 第6页共8页 中,正确的是A:递归次数与初始数据的排列次序无关B:每次划分后,先处理较长的分区可以减少递归次数C:每次划分后,先处理较短的分区可以减少递归次数D:递归次数与每次划分后得到的分区处理顺序无关29.对一组数据(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:基数排序 30.为实现快速排序算法,待排序序列宜采用的存储方式是A.顺序存储B.散列存储C.链式存储D.索引存储31.已知序列25,13,10,12,9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是A.1B.2C.4D.532.一个栈的入栈序列为1234,以下出栈序列不可能得到的是:A.1324B.2341C.4312D.342133.若一个二叉树具有10个度为2的结点,则度为0的结点的个数 为:A.9B.10C.11D.不确定34.下列有关图遍历的说法中不正确的是:A连通图的深度优先搜索是一个递归过程。B图的广度优先搜索中邻接点的寻找具有“先进先出”的特征。C非连通图不能用深度优先搜索法。D图的遍历要求每一顶点仅被访问一次。 第7页共8页 35.若已知待排序序列基本有序,则效率最高的排序方法是:A.直接插入排序B.直接选择排序C.快速排序D.归并排序36.对一棵完全二叉树按层次遍历序进行递增编号,根结点编号为1,那么编号为49的结点的左子的编号是:A.98B.99C.50D.4837.下列序列中不符合堆的定义的是:A.acdghmpqrxB.acmdhpxgorC.adprcqxmhgD.adcmpghxrq 38.下列排序方法中,相同关键字元素的顺序不会被改变的排序方法是:A.希尔排序法B.堆排序法C.快速排序D.归并排序法39.在有n个叶结点的哈夫曼树上,结点总数为:A.2nB.2n+1C.2n-1D.不确定40.由3个结点可以构成多少种不同形态的二叉树:A.4B.5C.6D.7二、综合应用题:4145小题,共70分。请将答案写在答题纸指定位置上。 41.(15分)已知两个单调递增的整数序列,分别存放在数组A和B中,序列长度分别为na和nb,请编写算法,将两个序列归并成一个单调递减的序列,存放到目标数组C中。已知两个序列中无相同的元素。参考算法代码形式如下:intMerge(intC,intA,intna,intB,intnb). 第8页共8页 42.(10分)已知一组字符及其权值如下:a:29,b:17,c:9,d:22,e:66,f:21,g:15,h:5,i:11,j:19,k:30,l:18请构造相应的哈夫曼树,画出结果哈夫曼树即可。43.(15分)已知带权有向图如下所示,请用Floyd算法计算该图中每两点间的最短路径及长度,写出计算过程和结果。10 231539208145444.(15分)已知输入序列如下:7,3,5,2,4,1,10,6,8,9请根据该输入序列创建平衡二叉树,写出创建过程及结果。45.(15分)已知待排序序列如下:5,3,10,7,8,6,1,12,9,4,11,2请写出用堆排序法对其进行升序排序的排序过程(依序写出每一趟交换的结果和调整的结果,不必写出调整的具体过程)。