電大數(shù)據(jù)結(jié)構(gòu)(本)期末考試1

一、單項選擇題，在括號內(nèi)填寫所選擇的標(biāo)號(每小題1分，共12分)一、單項選擇題，在括號內(nèi)填寫所選擇的標(biāo)號(每小題1分，共12分)計算機專業(yè)數(shù)據(jù)結(jié)構(gòu)試題2005年1月題號二三四五六分?jǐn)?shù)1.下面算法的時間復(fù)雜度為(A.O(1)B.O(n)C.O(n2)2.在一個長度為n的順序表中順序查找一個值為x的元素時，在等概率的情況下，搜索成功時同元素的平均比較次數(shù)為()。A.nC.(n+1)/23.帶頭結(jié)點的單鏈表first為空的判定條件是()。4.已知L是一個不帶表頭的單鏈表的表頭指針，在表首插入結(jié)點*p的操作是()。5.設(shè)循環(huán)隊列的結(jié)構(gòu)是若有一個Queue類型的隊列Q,試問判斷隊列滿的條件應(yīng)為()。B.Q.front-Q.rear==MD.Q.front==(Q.rear+1)%M6.設(shè)有一個廣義表A((x,(a,b)),(x,(a,b),y)),運算Head(Head(Tail(A)))的執(zhí)行結(jié)C.(x,(a,b))7.在一棵完全二叉樹中，若編號為i的結(jié)點存在左子女，則左子女結(jié)點的編號為()。假定樹根結(jié)點的編號為0。C.2i+18.對長度為10的順序表進行搜索，若搜索前面5個元素的概率相同，均為1/8,搜索后面5個元素的概率相同，均為3/40,則搜索任一元素的平均搜索長度為()。A.5.59.向一棵AVL樹插入元素時，可能引起對最小不平衡子樹的左單或右單旋轉(zhuǎn)的調(diào)整過A.210.對于有向圖，其鄰接矩陣表示比鄰接表表示更易于()。A.求一個頂點的入度B.求一個頂點的出邊鄰接點C.進行圖的深度優(yōu)先遍歷D.進行圖的廣度優(yōu)先遍歷11.設(shè)有向圖有n個頂點和e條邊，采用鄰接表作為其存儲表示，在進行拓?fù)渑判驎r，總的計算時間為()。A.O(nlog?e)C.O(n?)D12.在10階B樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最少為()。A.05.設(shè)鏈棧中結(jié)點的結(jié)構(gòu)為(data,link),棧頂指針為top,則向該鏈棧插入一個新結(jié)點*P7.在一棵高度為h的完全二叉樹中，最少含有個結(jié)點。假定樹根結(jié)點的高度為0。8.從有序表(12,18,30,43,56,78,82,95)中折半搜索56和78元素時，其搜索長度分別11.給定一組數(shù)據(jù)對象的關(guān)鍵碼為(46,79,56,38,40,84},則利用堆排序方法建立的初始誤(每小題1分，共12分)7.鄰接矩陣適用于稀疏圖(邊數(shù)遠(yuǎn)小于頂點數(shù)的平方),鄰接表適用于稠密圖(邊數(shù)接近A[5][8]在B中的存放位置：2.有7個帶權(quán)結(jié)點，其權(quán)值分別為3,7,8,2,6,3.已知圖G=(V,E),其中E={<a,b>,<b,a>,<c,b>,<c,d>,<d,e>,<請問該圖的鄰接表中，每個頂點單鏈表各有多少邊結(jié)點。4.已知一個AOV網(wǎng)絡(luò)的頂點集V和邊集E分別為：E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<45.已知有一個數(shù)據(jù)表為{30,18,20,15,38,12,44,53,46,18°,26,86},給出進行歸并排序五、算法分析題(每小題6分，共18分)五、算法分析題(每小題6分，共18分)1.設(shè)字符串類St'g具有下列操作：intLength()//計算字符串的長度//提取字符串第k個字符的值若字符串Tar的值為“ababcabcacbab”,Pat的值為“abcac”時，(1)給出下面算法執(zhí)行后返回的結(jié)果；(2)給出下面算法的功能。{“String.h”unknown(String&Tar,String&.Pat)coi=0;i<=Tar.Length()-Pat.Lenintj=0;if(Tar.getData(i+j)==Pat.getif(j==Pat.Length())returni;return—1;}2.已知二叉樹中的結(jié)點類型BinTreeNode定義為：structBinTreeNode{ElemType其中data為結(jié)點值域，left和right分別為指向左、右子女結(jié)點的指針域。下面函數(shù)的功能是返回二叉樹BT中值為X的結(jié)點所在的層號。根據(jù)題意按標(biāo)號把合適的內(nèi)容填寫到算法后面相應(yīng)標(biāo)號的位置。{-1;//空樹的層號為一1elseif(BT->data==X)return0;//根結(jié)點的層號為0//向子樹中查找X結(jié)點intcl=NodeLevel(BT//若樹中不存在X結(jié)點則返回一1}3.假定一個有向無權(quán)圖采用鄰接矩陣存儲，請指出下面算法的功能。Template<classvoidGraph<Type>::unknown(inti)for(j=0;j<CurrentNodes;j++){//CurrentNodes為圖中的頂點數(shù)if(Edge[i][j]){d++;Edgeif(Edge[i][i]){d++;EdgeCurrentEdges-=d;//CurrentEdges1.請寫出在循環(huán)隊列上進行插入操作的算法。要求若插入成功則返回true,否則返回boolEnCQueue(CyclicQueue&.Q,ElemTypex)(/*編寫該函數(shù)體*/}明編寫出求一棵二叉樹中結(jié)點總數(shù)的遞歸算法，該中央廣播電視大學(xué)2004—2005學(xué)年度第一學(xué)期“開放本科”期末考試計算機專業(yè)數(shù)據(jù)結(jié)構(gòu)試題答案及評分標(biāo)準(zhǔn)(供參考)2005年1月5.p->link=top6.重數(shù)1.錯2.對3.對4.對5.對6.對7.錯8.對9.錯10.對11.錯12.對數(shù)組B中的存放位置為(2*n-I-1)*1/2+J,4.評分標(biāo)準(zhǔn)：若與答案完全相同得6分，若仍為一種拓?fù)湫蛄袆t得3分，其他則酌情處(1)returncl+1//2分(2)NodeLevel(BT->right,X)//2分(3)(c2>=0)