2011-2012-1-a-数据结构期末试卷(1)

《2011-2012-1-a-数据结构期末试卷(1)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2011-2012学年第一学期期末考试《数据结构》试卷（A）一、选择（共22分,每小题2分,把最恰当的答案编号填到答题卷的相应位置）1.下列程序段的时间复杂度是()。for(i=0;i=maxS

2、izeC.rear==(front+1)%maxSizeD.front==(rear+1)%maxSize3.若元素0、1、2依次进栈，允许进栈和出栈操作交替进行，则下列序列中不可能得到的出栈序列是()。A.012B.201C.021D.2104.若用邻接矩阵表示有向图，则其中每一行包含的″1″的个数为()。A．图中每个顶点的出度B．图中每个顶点的入度C．图中弧的条数D．图中连通分量的数目5.如果所有关键字都相等，那么插入排序算法的时间复杂度为()。A.O(1)B.O(n)C.O(nlogn)D.O(n2)6.下列排序算法中，平均时间复杂度为O(nlogn

3、)且占用额外空间最多的是()。A.堆排序B.插入排序C.归并排序D.快速排序7.若无向图G=（V,E）含有7个顶点，要保证图G都是连通的，则需要的边数最少是()。A.6B.15C.16D.218.若用数组S[N](S[0…N-1])作为两个栈S1和S2的共用存储结构，对任何一个栈，只有当S数组全满时才不能入栈操作。为这两个栈分配空间的最佳初始方案是。A.S1的栈底位置为-1，S2的栈底位置为N;B.S1的栈底位置为-1，S2的栈底位置为N/2;C.S1的栈底位置为0，S2的栈底位置为N/2;D.S1的栈底位置为N/2-1，S2的栈底位置为N/2。9.若一棵

4、二叉树的前序遍历序列和中序遍历序列分别为abecdf和beadcf，则该二叉树的后序遍历序列为()。A.ebadfcB.dfcebaC.ebdfcaD.fdecba10.排序方法中，从未排序序列中取出元素与已排列序列（初始时为空）中的元素作比较，将其放入已排列序列的正确位置上的方法，称为。A.选择排序B.插入排序C.冒泡排序D.快速排序11.下列序列中，()不是堆(heap).A.{100,98,85,82,80,77,66,60,40,20,10}B.{100,85,98,77,80,60,82,40,20,10,66}C.{10,20,40,60,66

5、,77,80,82,85,98,100}D.{100,85,40,77,80,60,66,98,82,10,20}locatedintheTomb,DongShenJiabang,deferthenextdayfocusedontheassassination.Linping,Zhejiang,1ofwhichliquorwinemasters(WuzhensaidinformationisCarpenter),whogotAfewbayonets,duetomissedfatal,whennightcame二、填空题(12分,请在空格中填上合适的答案)G

6、ivenanintegersequence25,40,11,97,59,30,87,73,21andsortingthemwithanincreasingorder,pleasecompletethreeproblems(asbelowshows)andfillthesolutionsinblanklinesontheanswersheet.(1)Afterthefirstrunofthemergesorting(归并排序),theintegersequenceis(4points):____________________________________

7、______________.(2)Afterthefirstrunoftheheapsorting(堆排序),theintegersequenceis(4points):__________________________________________________.(3)Afterthefirstrunofquicksorting(快速排序),theintegersequenceis(4points):__________________________________________________.三、简答题（共41分）1.(21Points)

8、Forthedigraph(有向图)Ggivenbelow,sho