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

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