大数据结构考精彩试题2.doc

《大数据结构考精彩试题2.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每答题纸都要写上和学号。一、单项选择题（每小题1.5分，20小题，共计30分）1.以下数据结构中属非线性结构。A.栈B.串C.队列D.平衡二叉树2.以下算法的时间复杂度为。voidfunc(intn){inti=0,s=0;while(s<=n){i++;s=s+i;}}A.O(n)B.O()C.O(nlog2n)D.O(log2n)3.在一个双链表中，删除p所指节点（非首、尾节点）的操作是。A.p->prior->next=p->next;p->ne

2、xt->prior=p->prior;B.p->prior=p->prior->prior;p->prior->prior=p;C.p->next->prior=p;p->next=p->next->next;D.p->next=p->prior->prior;p->prior=p->prior->prior;4.设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为。A.一定是2B.一定是1C.不可能是1D.以上都不对5.在数据处理过程中常需要保存一些中间数据，如

3、果要实现后保存的数据先处理，则应采用来保存这些数据。A.线性表B.栈C.队列D.单链表6.中缀表达式a*(b+c)-d的对应的后缀表达式是。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd7.设栈s和队列q的初始状态都为空，元素a、b、c、d、e和f依次通过栈s，一个元素出栈后即进入队列q，若6个元素出队的序列是b、d、c、f、e、a，则栈s的容量至少应该存多少个元素？A.2B.3C.4D.58.设循环队列中数组的下标是0～N-1，其队头队尾指针分别为f和r（f指向队首元素的前一位置，

4、r指向队尾元素），则其元素个数为。A.r-fB.r-f-1C.(r-f)％N+1D.(r-f+N)％N9.若将n阶上三角矩阵A按列优先顺序压缩存放在一维数组B[1..n(n+1)/2]中，A中第一个非零元素a1,1存于B数组的b1中，则应存放到bk中的非零元素ai,j（1≤i≤n，1≤j≤i）的下标i、j与k的对应关系是。A.B.C.D.10.一棵节点个数为n的m（m≥3）次树中，其分支数是。A.nhB.n+hC.n-1D.h-111.设森林F对应的二叉树为B，B中有m个节点，其根节点的右子树的节点个数为n，

5、森林F中第一棵树的节点个数是。A.m-nB.m-n-1C.n+1D.条件不足，无法确定12.一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为。A.CBEFDAB.FEDCBAC.CBEDFAD.不确定13.在一个具有n个顶点的有向图中，构成强连通图时至少有条边。A.nB.n+lC.n-1D.n/214.对于有n个顶点的带权连通图，它的最小生成树是指图中任意一个。A.由n-1条权值最小的边构成的子图B.由n-l条权值之和最小的边构成的子图C.由n-l条权值之和最小的边构成的连

6、通子图D.由n个顶点构成的极小连通子图，且边的权值之和最小15.对于有n个顶点e条边的有向图，求单源最短路径的Dijkstra算法的时间复杂度为。A.O(n)B.O(n+e)C.O(n2)D.O(ne)16.一棵深度为k的平衡二叉树，其每个非叶子节点的平衡因子均为0，则该树共有个节点。A.2k-1-1B.2k-1C.2k-1+1D.2k-117.对线性表进行折半查找时，要求线性表必须。A.以顺序方式存储B.以方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链表方式存储，且节点按关键字有序排序18.假设

7、有k个关键字互为同义词，若用线性探测法把这k个关键字存入哈希表中，至少要进行次探测。A.k-1B.kC.k+1D.k(k+1)/219.以下排序算法中，某一趟排序结束后未必能选出一个元素放在其最终位置上的是。A.堆排序B.冒泡排序C.直接插入排序D.快速排序20.以下排序方法中，不需要进行关键字的比较。A.快速排序B.归并排序C.基数排序D.堆排序二、问答题（共3小题，每小题10分，共计30分）1.已知一棵度为m的树中有n1个度为1的节点，n2个度为2的节点，…，nm个度为m的节点，问该树中有多少个叶子节点?

8、2.设数据集合D={1,12,5,8,3,10,7,13,9}，试完成下列各题：（1）依次取D中各数据，构造一棵二叉排序树bt；（2）如何依据此二叉树bt得到D的一个有序序列；（3）画出在二叉树bt中删除12后的树结构。3.一个有n个整数的数组R[1..n]，其中所有元素是有序的，将其看成是一棵完全二叉树，该树构成一个堆吗？若不是，请给一个反例，若是，请说明理由。三、算法设计题（共计40分）1.设A