2017年全国硕士研究生统一入学考试自命题试题（B卷）********************************************************************************************学科、专业名称：计算机科学与技术、软件工程研究方向：计算机系统结构081201，计算机软件与理论081202，计算机应用技术081203，软件工程083500，计算机技术(专业学位)085211，软件工程(专业学位)085212考试科目名称及代码：数据结构830考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。一、单项选择题(每题2分，共30分)1.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,12.循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear,则当前队列中的元素个数是()。A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front3.平衡二叉树的平均查找长度是()。A.O(n2）B.O(nlog2n）C.O(n）D.O(log2n）4.设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。A.N1-1B.N2-1C.N2+N3D.N1+N35.计算机内部数据处理的基本单元是（）。A.数据B.数据元素C.数据项D.数据库6.设按照从上到下、从左到右的顺序从1开始对完全二叉树的结点进行顺序编号，则编号为i结点的左孩子结点的编号为（）。A.2i+1B.2iC.i/2D.2i-17.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和8.设一组初始记录关键字序列为(16,25,12,30,47,11,23,36,9,18,31)，则以增量d=5的一趟希尔排序结束后的结果为（）。A.11,23,12,9,18,16,25,36,30,47,31B.11,23,12,9,16,18,25,36,47,30,31C.16,23,12,9,11,18,25,36,30,47,31C.9,11,12,16,18,23,25,30,36,47,319.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。A.nB.n-1C.mD.m-110.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A.2m-1B.2mC.2m+1D.4m11.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H(K)=K%9作为散列函数，则散列地址为1的元素有（）个。A．1B．2C．3D．4考试科目：数据结构共5页，第1页12.下面程序的时间复杂为（）。for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++){t=t*j；s=s+t；}}A．O(n)B.O(n2)C.O(n3)D.O(n4)13.对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为()。A．0B．1C．nD．n+114.设无向图G中边的集合E={(a,b)，(a,e)，(a,c)，(b,e)，(e,d)，(d,f)，(f,c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。A.aebcfdB.acfebdC.aedfcbD.aedfbc15.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。A.p->next=s；s->prior=p；p->next->prior=s；s->prior=p->nest；B.s->prior=p;s->next=p->next;p->next=s;s->next->prior=s;C.p->prior=s；p->nest->prior=s；s->prior=p；s->next=p->prior；D.s->prior=p；s->next=p->next；p->next=s；p->next->prior=s；二．填空题(每空2分，共20分)1.采用堆排序、快速排序、冒泡排序，对初态为有序的表，最省时间的是。2.设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为。3.当待排记录序列按关键字顺序有序时，直接插入排序和冒泡排序能达到的时间复杂度，快速排序的时间性能退化为(以第一个关键字为枢轴)。4.判定顺序栈是否为空的条件是，判定顺序栈是否为满的条件是。5.当向B-树中插入关键字时,可能引起结点的,最终可能导致整个B-树的高度增加。6.设散列表的长度为8，散列函数H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是。7.设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有个。三．判...
