资源描述:
《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