大數(shù)據(jù)結(jié)構(gòu)精彩試題及問(wèn)題詳解10

1、若將數(shù)據(jù)結(jié)構(gòu)形式定義為二元組A.操作的有限集合C.類型的有限集合在長(zhǎng)度為n的順序表中刪除第iA.n-i+1C.i+1若不帶頭結(jié)點(diǎn)的單鏈表的頭指針為A.head=NULLC.head!=NULL數(shù)據(jù)結(jié)構(gòu)自考復(fù)習(xí)思考試題。10一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫(xiě)在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無(wú)分。（K,R）,其中K是數(shù)據(jù)元素的有限集合，則R是K上（）映象的有限集合D.關(guān)系的有限集合個(gè)元素（1<i<n）時(shí)，元素移動(dòng)的次數(shù)為（）B. iD.n-ihead，則該鏈表為空的判定條件是（）B.head-&g

2、t;next=NULL4. D.head->next=head引起循環(huán)隊(duì)列隊(duì)頭位置發(fā)生變化的操作是（）A.出隊(duì)B.入隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素若進(jìn)棧序列為1,2,3,4,5,6,且進(jìn)棧和出棧可以穿插進(jìn)行，則不可能出現(xiàn)的出棧序列是（）5,B.3，2,4,1,6,55,D.2，3,5,1,6,46.字符串通常米用的兩種存儲(chǔ)方式是（）A.散列存儲(chǔ)和索引存儲(chǔ)C.順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)B.索引存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)D.散列存儲(chǔ)和順序存儲(chǔ)7.設(shè)主串長(zhǎng)為n,模式串長(zhǎng)為m（詐n）,則在匹配失敗情況下，樸素匹配算法進(jìn)行的無(wú)效位移次數(shù)為（）A.mB.n-mC.n-m+1D.n8.二維數(shù)組A1218采用列優(yōu)先的存儲(chǔ)方

3、法，若每個(gè)元素各占3個(gè)存儲(chǔ)單元，且第1個(gè)元素的地址為150,則元素A97的地址為（）A.429B.432C.435D.4389.對(duì)廣義表L=(a,b),(c,d),(e,f)執(zhí)行操作tail(tail(L)的結(jié)果是()A.(e,f)B.(e,f)c.(f)D.()10.卜列圖示的順序存儲(chǔ)結(jié)構(gòu)表示的二義樹(shù)是()12. 6AjBCDE|IF0I2345678910111211.n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有(n-1條有向邊n(n-1)/2條有向邊)B.n條有向邊D.n(n-1)條有向邊對(duì)關(guān)鍵字序列(56,23,78,92,88,67,19,34)進(jìn)行增量為3的一趟希爾排序的結(jié)果為()(19,23,5

4、6,34,78,67,88,92)B.(23,56,78,66,88,92,19,34)(19,23,34,56,67,78,88,92)D.(19,23,67,56,34,78,92,88)若在9階B-樹(shù)中插入關(guān)鍵字引起結(jié)點(diǎn)分裂，貝U該結(jié)點(diǎn)在插入前含有的關(guān)鍵字個(gè)數(shù)為A.4B.5C.8D.9由同一關(guān)鍵字集合構(gòu)造的各棵二叉排序樹(shù)()其形態(tài)不一定相同，但平均查找長(zhǎng)度相同其形態(tài)不一定相同，平均查找長(zhǎng)度也不一定相同其形態(tài)均相同，但平均查找長(zhǎng)度不一定相同其形態(tài)均相同，平均查找長(zhǎng)度也都相同ISAM文件和VSA吸件的區(qū)別之一是()前者是索引順序文件，后者是索引非順序文件前者只能進(jìn)行順序存取，后者只能進(jìn)行隨機(jī)

5、存取前者建立靜態(tài)索引結(jié)構(gòu)，后者建立動(dòng)態(tài)索引結(jié)構(gòu)前者的存儲(chǔ)介質(zhì)是磁盤(pán)，后者的存儲(chǔ)介質(zhì)不是磁盤(pán)二、填空題(本大題共10小題，每空2分，共20分)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的。13. 刪除雙向循環(huán)鏈表中*p的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語(yǔ)句是。14. 棧下溢是指在時(shí)進(jìn)行出棧操作。已知substr(s,i,len)函數(shù)的功能是返回串s中第i個(gè)字符開(kāi)始長(zhǎng)度為len的子串，strlen(s)函數(shù)的功能是返回串s的長(zhǎng)度。若s="ABCDEFGHIJK,t="ABCD，執(zhí)行運(yùn)算substr(s,strlen(t),strlen(t)后的返回值為。15. 去除廣義表LS=(a

6、1,a2,a3,，an)中第1個(gè)元素，由其余元素構(gòu)成的廣義表稱為L(zhǎng)S的已知完全二叉樹(shù)T的第5層只有7個(gè)結(jié)點(diǎn)，則該樹(shù)共有個(gè)葉子結(jié)點(diǎn)。16. 在有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目稱為v的。17. 當(dāng)關(guān)鍵字的取值范圍是實(shí)數(shù)集合時(shí)，無(wú)法進(jìn)行箱排序和排序。18. 產(chǎn)生沖突現(xiàn)象的兩個(gè)關(guān)鍵字稱為該散列函數(shù)的。假設(shè)散列文件中一個(gè)桶能存放m個(gè)記錄，則桶“溢出”的含義是，當(dāng)需要插入新的記錄時(shí)，該桶中。19. 三、解答題(本大題共4小題，每小題5分，共20分)假設(shè)以數(shù)組seqnm存放循環(huán)隊(duì)列的元素，設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的位置和元素的個(gè)數(shù)。寫(xiě)出隊(duì)滿的條件表達(dá)式；寫(xiě)出隊(duì)空的條件表達(dá)式；

7、設(shè)m=40,rear=13,quelen=19,求隊(duì)頭元素的位置；(4)寫(xiě)出一般情況下隊(duì)頭元素位置的表達(dá)式。20. 已知一棵二叉樹(shù)的中序序列為ABCDEFG層序序列為BAFEGCD請(qǐng)畫(huà)出該二叉樹(shù)。21. 畫(huà)出下圖所示有向圖的所有強(qiáng)連通分量。22. 顧28圈對(duì)7個(gè)關(guān)鍵字進(jìn)行快速排序，在最好的情況下僅需進(jìn)行10次關(guān)鍵字的比較。(2) 假設(shè)關(guān)鍵字集合為1,2,3,4,5,6,7，試舉出能達(dá)到上述結(jié)果的初始關(guān)鍵字序列;對(duì)所舉序列進(jìn)行快速排序，寫(xiě)出排序過(guò)程。23. 四、算法閱讀題(本大題共4小題，每小題5分，共20分)閱讀下列算法，并回答問(wèn)題：(3) 設(shè)順序表L=(3,7,11,14,20,51)，寫(xiě)出

8、執(zhí)行f30(&L,15)之后的L;設(shè)順序表L=(4,7,10,14,20,51)，寫(xiě)出執(zhí)行f30(&L,10)之后的L;簡(jiǎn)述算法的功能。voidf30(SeqList*L,DataTypex)inti=0,j;while(i<L->length&&x>L->datai)i+;if(i<L->length&&x=L->datai)for(j=i+1;j<L->length;j+)L->dataj-1:=L->data:j:;L->length-;elsefor(j=L->

9、length;j>i;j-)L->data:j:=L->dataj-1:;L->datai=x;L->length+;24. 已知圖的鄰接表表示的形式說(shuō)明如下：#defineMaxNum50/圖的最大頂點(diǎn)數(shù)typedefstructnode(intadjvex;/鄰接點(diǎn)域structnode*next;/鏈指針域EdgeNode;/邊表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct(charvertex;/頂點(diǎn)域EdgeNode*firstedge;/邊表頭指針VertexNode;/頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)描述typedefstruct(VertexNodeadjlistMaxN

10、um；/鄰接表intn,e;/ALGraph;/鄰接表結(jié)構(gòu)描述圖中當(dāng)前的頂點(diǎn)數(shù)和邊數(shù)下列算法輸出圖G的深度優(yōu)先生成樹(shù)(或森林)的邊。閱讀算法，并在空缺處填入合適的內(nèi)容，使其成為一個(gè)完整的算法。typedefenum(FALSE,TRUEBoolean;BooleanvisitedMaxNum;voidDFSForest(ALGraph*G)(inti;for(i=0;i<G->n;i+)visited門(mén)=(1);for(i=0;i<G->n;i+)if(!visited:i:)DFSTree(G,i);voidDFSTree(ALGraph*G,inti)(EdgeNo

11、de*p;visited:i:=TRUE;p=G->adjlisti.firstedge;while(p!=NULL)(2) if(!visitedp->adjvex)(printf("<%c,%c>',G->adjlisti.vertex,G->adjlistp->adjvex.vertex);_J；25. 閱讀下列算法，并回答問(wèn)題：假設(shè)數(shù)組L8=3,0,5,1,6,4,2,7，寫(xiě)出執(zhí)行函數(shù)調(diào)用f32(L,8)后的L;(2)寫(xiě)出上述函數(shù)調(diào)用過(guò)程中進(jìn)行元素交換操作的總次數(shù)。voidf32(intR口,intn)inti,t;for(i

12、=0;i<n-1;i+)while(R:i:!=i)t=RRi門(mén);RRi門(mén)=Ri:;R:i:=t;已知帶頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)，為提高查找效率，需將它改建為采用拉鏈法處理沖突的散列表。設(shè)散列表的長(zhǎng)度為mx散列函數(shù)為Hash(key)=key%m。鏈表的結(jié)點(diǎn)結(jié)構(gòu)為：|keynext|。請(qǐng)?jiān)诳杖碧幪钊脒m當(dāng)內(nèi)容，使其成為一個(gè)完整算法。voidf33(LinkListL,LinkListH,intm)/由帶頭結(jié)點(diǎn)的單鏈表L生成散列表H,散列表生成之后原鏈表不再存在inti,j;LinkListp,q;for(i=0;i<m;i+)H:i:=(1);p=L->next;whil

13、e(p)q=p->next;j=p->key%m;；Hj:=p；free(L);五、算法設(shè)計(jì)題(本大題10分)假設(shè)以帶雙親指針的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，其結(jié)點(diǎn)結(jié)構(gòu)的類型說(shuō)明如下所示：typedefcharDataType;typedefstructnodeDataTypedata;structnode*lchild,*rchild;/左右孩子指針structnode*parent;/指向雙親的指針BinTNode;typedefBinTNode*BinTree;若px為指向非空二:叉樹(shù)中某個(gè)結(jié)點(diǎn)的指針，可借助該結(jié)構(gòu)求得px所指結(jié)點(diǎn)在二叉樹(shù)的中序序列中的后繼。(1) 就后繼的不

14、同情況，簡(jiǎn)要敘述實(shí)現(xiàn)求后繼操作的方法；編寫(xiě)算法求px所指結(jié)點(diǎn)的中序序列后繼，并在算法語(yǔ)句中加注注釋。1. 數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)答案一、單項(xiàng)選擇題(B)(D)(A)(A)(D)(C)(C)(A)(B)(A)(B)(D)(C)(B)(C)二、填空題(本大題共10小題，每空2分，共20分)存儲(chǔ)結(jié)構(gòu)q=p->pre;q->pre->next=p;p->pre=q->pre;2. free(q);?？铡盌EFG”/注意雙引號(hào)不能少表尾2A(I-2)+M/2葉子結(jié)點(diǎn).入度基數(shù)同義詞已有m個(gè)同義詞記錄三、解答題(本大題共4小題，每小題5分，共20分)(1)quelen=m(2)quel

15、en=0(13-19+40)%40=34(rear-quelen+m)%m27.B/AF/EG/CD3個(gè)：a、bce、dfg29.我們知道，對(duì)n個(gè)關(guān)鍵自序列進(jìn)行一趟快速排序，要進(jìn)行n-1次比較，也就是基準(zhǔn)和其他n-1個(gè)關(guān)鍵字比較。這里要求10次，而7-1+2*(3-1)=10，這就要求2趟快速排序后，算法結(jié)束。所以，列舉出來(lái)的序列，要求在做partition的時(shí)候，正好將序列平分(1)4132657或4137652或4537612或4135627.自己列吧:)四、算法閱讀題(本大題共4小題，每小題5分，共20分)30.(1)L=(3,7,11,14,15,20,51)L=(4,7,14,20,51)在順序表L中查找數(shù)x,找到，則刪除x,沒(méi)找到，則在適當(dāng)?shù)奈恢貌迦離,插入后，L依然有序.31.FALSE/初始化為未訪問(wèn)DSFTree(G,p->adjvex);/從相鄰結(jié)點(diǎn)往下繼續(xù)深度搜索p=p->next;/下一個(gè)未訪問(wèn)的相鄰結(jié)點(diǎn)32.L=(0,1,2,3,4,5,6,7；(2)5次33.NULL/初始化p->next=Hj/和下面一句完成頭插法p=q;/繼續(xù)遍歷L五、算法設(shè)計(jì)題(本大題10分)34.1)*px有右孩子，則其右孩子為其中序序列中的后繼*px無(wú)右孩子，從*px開(kāi)始