數(shù)據(jù)結(jié)構(gòu)試題及答案

1、?數(shù)據(jù)結(jié)構(gòu)?自考復(fù)習(xí)思考試題一鼻單項(xiàng)選擇題本大題共15小題每題2分,共30分 在毎小題列岀的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的*請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi).錯(cuò)選、多項(xiàng)選擇或未選均無(wú)分。1 假設(shè)將徽據(jù)結(jié)構(gòu)形式定義為二元組KR,其中K是數(shù)據(jù)元素的有限集合.那么R是K EA.操作的有限集合0OC.類型的宥限集合2.在長(zhǎng)度為n的順序我中刪除第n個(gè)元扌B映象的有限集合D.關(guān)茶的壽賒合皚時(shí).元董移動(dòng)的次數(shù)為A mi+】B. 1C. i+1D n-i篥 環(huán) U的單i"的頭指針為血述 那么瀏糠為空的判定條件是IA head=NULLB head->next=NTJLLCl head!mUL

2、LD head-next=head4.引起循環(huán)關(guān)列賦頭位置發(fā)生變化的操作啟A. 冊(cè)隊(duì)B.入隊(duì)C取隊(duì)頭元素D取隊(duì)尾元素5 著進(jìn)棧序死富陽(yáng)2.玉斗* S?6丄進(jìn)棧和出?？膳P需 那么不叮能出珊|J'列忍 )A. 2* 4* 31 1« 5* 66.字符串通常采用的兩種存儲(chǔ)方式敏A_散列存儲(chǔ)和盍引存儲(chǔ)B, 索引存餚和鏈?zhǔn)酱娑肅.順序存儲(chǔ)和鏈?zhǔn)酱?D敬列存儲(chǔ)和順序存鯨工設(shè)生弗長(zhǎng)為n麒式車孫為uXmWQ那么在匹配失敗悟況下樸素匹配算法迸行的無(wú)效位 移嵌數(shù)為EL n«mD. nU nm+l&二維數(shù)組A C12 18用列優(yōu)先的存儲(chǔ)方淑 假設(shè)每個(gè)元素各占3個(gè)存儲(chǔ)單元且第1個(gè)無(wú)

3、素的地址為150,那么元素A 9 7的地址為C. 435D 4389對(duì)廣義表LN乩b,cQ仗f執(zhí)行操作tailtail功的結(jié)果是f010. TFJR示的瞰序存赭黠構(gòu)表示的二買樹(shù)忌B.11. m個(gè)頂點(diǎn)的強(qiáng)建通圖申奎少會(huì)儆Ae n-1條有向邊C-11口-1/2條有向邊Bm條有向邊D. 1111-1條有向邊IX對(duì)關(guān)犍字序列(56* 2務(wù)78, 92. S3, 67,19, 34進(jìn)行熾量為3的一趟希爾掙序的結(jié)果為A(19歲 2 氛 56, 34> 78, 67, 88， 92)0.(19, 23j 34f 56, 67. 78, 8& 92)BQ弟 56, 78, 66® 88

4、> 92. 19 34)D4191 23, 67, 56. 349 78. 92. 88)G假設(shè)在9階3樹(shù)申插入關(guān)鍵字弓I起第點(diǎn)分裂,那么該箱點(diǎn)在播入前含有的關(guān)鍵字個(gè)數(shù)為A.4C. 8D. 914. 由同一黃鍵字集令構(gòu)埋的備棵;叉排序樹(shù)A.其不一定相同，II平均査找托度相同B其形蠡不一宦相阿普均查找長(zhǎng)度也不一定相阿U記形態(tài)均相同,但平均行找2度退相同 _ *D. 其形態(tài)均相同罰平均査找長(zhǎng)度也都相同15. ISAM文件和VSAM文件的區(qū)別之一是()A.前者是索刑順序文件，后者是索刖非順序文件 b川出只 海nm理u后春貝般應(yīng)I誦陣c.前者建立靜態(tài)濫引華檄引釘ID.前者的存儲(chǔ)介質(zhì)aaa,后者的

5、存儲(chǔ)介質(zhì)不晁磁盤二髦填空題(本大題共10小題，每空2分，共go分)16. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)肆機(jī)存儲(chǔ)器內(nèi)的表汞，稱為數(shù)據(jù)的17. 刪除與向循環(huán)鏈表中甲的前驅(qū)結(jié)點(diǎn)(存在)應(yīng)執(zhí)行的語(yǔ)句是1 &棧下溢是指在時(shí)遴行出棧操作«仗 已規(guī)$ub$tr(HleD)函數(shù)的功能是返回串&中第i個(gè)字符開(kāi)始長(zhǎng)度為len的子串，sulen(s)數(shù)的功能是邂同串s的長(zhǎng)度營(yíng)假設(shè)s= " ABCDEFGHUK懵=兩ABCD " /執(zhí)行運(yùn)算subs&Cs.strlenCt), strlen(t)W 的遞風(fēng)值為20.去除廣義表LS=(丸忌屈嚴(yán)& aj中第1個(gè)元素扌由其

6、余元素構(gòu)成的廣Jl表稱為L(zhǎng)S的2L完全二叉樹(shù)T的第5層貝有7牛緒就 那么該樹(shù)轉(zhuǎn)有個(gè)葉子第點(diǎn)眇排序.22-在有向閤申I以頂點(diǎn)*為終點(diǎn)的邊的數(shù)目稱為中的 23-當(dāng)黃擁字的取值范圍是實(shí)數(shù)集W.無(wú)袪進(jìn)抒箱排序和 24.產(chǎn)生沖究現(xiàn)象的兩個(gè)關(guān)鍵字稱為該披列函數(shù)的 25.假設(shè)散列文件中一個(gè)桶能存旗in個(gè)記錄那么桶亶溢HT的含文也 當(dāng)需要插入新的訕?shù)洉r(shí)，該桶中，三.解答題(本大題共4小題，每題為分，共20分)維 鮭以卿 呷啤鐘循環(huán)佻列曲元素.設(shè)費(fèi)jtn$ar和 啊硼指示循環(huán)隊(duì)列申隊(duì)尾元素的位置和元索的卜數(shù)祐(1) 寫出仏滿的條件表達(dá)式1Q)寫出賦空的條件表達(dá)式: 設(shè) m=40jeai-1 .queleiiRg

7、K頭元素的位置f寫岀-般悄況下隊(duì)頭元素位置的衷達(dá)式.27.一棵二又樹(shù)的中序序列為ABCDEFG.層序序列為BAFEGCD,請(qǐng)畫(huà)出該二叉樹(shù)$ ©28.涌出下掏所汞有向圖的所有強(qiáng)建過(guò)分出顧28用29】對(duì)7個(gè)關(guān)犍字進(jìn)殍快速排序胃在疑好的情況下僅需逬行10次關(guān)鍵字的比擬©假設(shè)關(guān)犍字集合為口占點(diǎn)?試舉出能到達(dá)上迷結(jié)果的初始關(guān)鍵字序殊(2) 對(duì)所舉序列進(jìn)行快速排序甲寫出排序過(guò)程.算法閱讀題(本大題共4小題克每題5分.共20分)30. 閱讀以下算法費(fèi)井答復(fù)以下問(wèn)題,設(shè)爛序我L=C3,7J144M51).寫出拗f nO(&L,之后的L； (2)設(shè)順序表LWJCM巴20,51)寫出執(zhí)

8、行f30(&LM)之后的Li簡(jiǎn)述算:法的功能諒void fiO(SeqList*L. DataTpe x)mti=0j;xiiile (i<L->lengtfi && x>L->data 訂 Ji+七； if(i<L->length && x=L->data i ) fbi(j=i-i-l ;j<L->length;j-H-)L->data j-1 =L->data j ; else for=L->lengtli;j>i ;j -)>L->data j =L->

9、;data 卜1詐 L->data i =x;L->length+;31. 己彌圖的鄰接表表示的堆武說(shuō)明如丘define MaxNiun 50“斟的最大頂點(diǎn)數(shù)typedef struct node oiiit adjvex;struct node next. EdgeNode；"邊表結(jié)點(diǎn)結(jié)構(gòu)描述typettef struct chai* veitex;EdgeNode *firstedge;"邊表頭扌旨針 rtexNode;.羽頂點(diǎn)表緒點(diǎn)蠟構(gòu)描述拠接表typedef struct *rertexNode adjlist Ma?<Nu:附國(guó)中當(dāng)前的頂點(diǎn)數(shù)和邊

10、數(shù) ALGraph制接表結(jié)構(gòu)描述下到鄴法輸出圖G的深度優(yōu)先生成樹(shù)或森林的邊.閱讀算法銅井崔空缺處填入會(huì)適的內(nèi)容使其成為一個(gè)完搭的算法。typedef enuin FALSE. TRUE) Boolean.Boolean Msited MaxNuni;void DF SF orest( ALGraph «G)int i;for(i=O;i<G->n;i+) Msited i=:foiXi=03<O->n,i+) if (!visited i ) DFSTree(Gi); oid DFSTree(ALGraph *G mt i) EdgeNode p;visite

11、d Ei =TRUE;p=G->adjlist i firstedge;wlule(p!=NULL)1 罠!visited p->adjvex )printf( r7G->adjlist 訂.vertex,G->adjlist p->adjvex , vertex)Ol:32. 闔讀以下算法發(fā)并答復(fù)以下問(wèn)題假設(shè)數(shù)?IIL 8 FQ5J6427,寫出執(zhí)行函數(shù)調(diào)W f32(L, 8)后的L；寫出止述崗數(shù)調(diào)用過(guò)程申迸行無(wú)素交換操作的總次數(shù)。void f32(int R ,int n)mt址forwhile (R 11 !=i) t=R R ill <R R 訂=R

12、 Li；R 訂=1；S3.己知帝頭結(jié)點(diǎn)的單鏈表中的關(guān)鍵字為整數(shù)為提高查找效率.需將它改建為采用拉鏈法處理沖突的散列表堆較散列表的快度為m散列函數(shù)為HaSh(key>kem.鏈表的結(jié)壷結(jié)構(gòu) 為:key tiext | »稱在空缺處填入適當(dāng)內(nèi)容?骰其成為=個(gè)完整煽誰(shuí)笹VQid B3 (LmkList L, LmkList H int m)也由帯頭結(jié)點(diǎn)的單鏈表L生成散列表H散列表空成之后原鏈表不再存在LmkList p、q; for (i=O;i<m;H)H i =；p=L->next; while(p)q=p->next; j 乎 >key%in;H j于(

13、3L五.算法設(shè)計(jì)題本大題10分34.假設(shè)以帶雙親指針的二JL鏈我作為二義樹(shù)的存儲(chǔ)結(jié)構(gòu)其結(jié)點(diǎn)結(jié)構(gòu)的類型說(shuō)明如卜所typedef char DataTpe*otypedef struct node ；DataType data, struct node *lchildl, *rchildt struct node +parent;於左右撲子指針 舟指向取親的指針 BiaTNtyp亡def BmTNode *BinTree.假設(shè)px為指向菲空二叉樹(shù)中某個(gè)結(jié)點(diǎn)的指th可借助該第構(gòu)求得px所播鰭點(diǎn)在二叉樹(shù)的中序 序列中的后繼作 就后維的不同情況簡(jiǎn)要表達(dá)實(shí)現(xiàn)求后継操作的方法星數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)答案D-S單項(xiàng)選擇

14、題1-( B )2(D)34 A )4( A )5( D )6 J C )7 ( C )8( A )9( B 10( A )1k( B )124 D )134 c )144 B )15X C )二 填空題本大趣共憶小題，每空2分.共20分16,存儲(chǔ)結(jié)構(gòu)億 q = p->pre;q->pre->next = p;op->pre 二 q->pre;feo( q);19 HDEFG""注意取引號(hào)不樹(shù)20_表尾 21.2 A(l-2)+M/2 葉予結(jié)就22. 523-基數(shù)24, 同義斕25. 己有m個(gè)同義詞記永 三、解答題(本大題共4小題每題5分*共2

15、0分)26 (1) quelen = m(2) quelen = 0(3) (13-19+40)%40 = 34(4) (rear - queien + m ) % m27.Bf A. F/E. GD28. 3 個(gè)：a - bcs dfg 29.我們知道，對(duì)n樺犍負(fù)序列進(jìn)行一趟快速排序.要進(jìn)行rM次比做 也就是棊準(zhǔn)和其他n-1個(gè)芙鍵字比擬.這里要求10矢 而7 " * 2氣3 - 1) = 1山 這就要求2趟快速排序后鼻算法睹束曠 所虬 列舉出來(lái)的序列*夏求在做partition的時(shí)驗(yàn) 正好將序列專分(1) 4 1 3 2 6 & 7 4 1 37652 fit 4 5376

16、12或 4 1 35627. (2自己列吧：)詠 算法閱讀題(本人題共4小甌 每題5分共20分)30(1)1-(37.114.15,20,51) L-(47#14,20.51)(3)在順序我L申查找數(shù)X沒(méi)找越h那么在適署的僅覽播入X.插入后 L依然疽序；31.(1) FALSE 初始化為未訪間DSFTree( G, ph>adjvex );"從相嘟結(jié)點(diǎn)越下讎?yán)m(xù)深度搜索(3) p = "next； 下一個(gè)未訝同的相鄰谿點(diǎn)32. L = W 2,3, 4, 5, 6,7;(2) 5 次(1) NULL祠始化p->next =和F面一旬売成頭插法(3) p= q；繼續(xù)遍歷La*®3L算法設(shè)計(jì)題(本大題10分)34nam 有右攢孔 那么其右薇予為其中序序列中的后継 找到.那么該結(jié)點(diǎn)的父錯(cuò)