數(shù)據(jù)的相關(guān)試題

1、1 / 14一、單選題 (每小題 2 分，共 12 分)1.在一個(gè)單鏈表 HL 中，若要向表頭插入一個(gè)由指針p 指向的結(jié)點(diǎn)，則執(zhí)行 ( ) 。A HL = ps p 一next = HLB p 一next = HL; HL= p3C . p 一next = Hl; p= HL;D . p 一next = HL 一next;HL 一next = p；2. n 個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有()。A.n l 條有向邊 B.n 條有向邊C.n(n1)2 條有向邊D.n(n 一 1)條有向邊3. 從一棵二叉搜索樹(shù)中查找一個(gè)元素時(shí)，其時(shí)刻復(fù)雜度大致 為 ( ) 。A.O(1) B.O(n)C.O(1Ogzn

2、) D.O(n2)4 由權(quán)值分不為 3，8，6，2，5 的葉子結(jié)點(diǎn)生成一棵哈夫 曼樹(shù)，2 / 14它的帶權(quán)路徑長(zhǎng)度為 ( ) 。A 24 B 48C 72 D 535當(dāng)一個(gè)作為實(shí)際傳遞的對(duì)象占用的存儲(chǔ)空間較大并可能需 要修改時(shí)， 應(yīng)最好把它講明為 ( ) 參數(shù)， 以節(jié)約參數(shù)值的傳輸 時(shí)刻和存儲(chǔ)參數(shù)的空間。A. 整形 B. 引用型C.指針型 D.常值引用型6向一個(gè)長(zhǎng)度為 n 的順序表中插人一個(gè)新元素的平均時(shí)刻復(fù) 雜度為 ( ) 。A O(n) B O(1)C O(n2) D O(10g2n)二、填空題 (每空 1 分，共 28 分)1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、 、和四種。2在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元

3、素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一3 / 14個(gè)域?qū)?yīng)不同，各自分不為域和域。3中綴表達(dá)式 3 十 x*（2.4 56） 所對(duì)應(yīng)的后綴 表達(dá)式為。4在一棵高度為 h 的 3 叉樹(shù)中，最多含有結(jié)點(diǎn)。5假定一棵二叉樹(shù)的結(jié)點(diǎn)數(shù)為 18，則它的最小深度為，最大深度為6在一棵二叉搜索樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié) 點(diǎn)的值一定該結(jié)點(diǎn)的值， 右子樹(shù)上所有結(jié)點(diǎn)的值一定 該結(jié)點(diǎn)的值。7當(dāng)向一個(gè)小根堆插入一個(gè)具有最小值的元素時(shí)，該元素 需要逐層調(diào)整，直到被調(diào)整到位置為止。8表示圖的三種存儲(chǔ)結(jié)構(gòu)為、和。9.對(duì)用鄰接矩陣表示的具有n 個(gè)頂點(diǎn)和 e 條邊的圖進(jìn)行任一種遍歷時(shí)，其時(shí)刻復(fù)雜度為一一，對(duì)用鄰接表表示的圖進(jìn)行任一種遍歷

4、時(shí)，其時(shí)刻復(fù)雜度為一一。4 / 1410.從有序表（12，18，30，43，56，78，82，95）中依次二分查找 43 和 56 元素時(shí)，其查找長(zhǎng)度分不為一一和-11.假定對(duì)長(zhǎng)度 n= 144 的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的長(zhǎng)度均為，則進(jìn)行索引順序查找的平均查找長(zhǎng)度為一一，時(shí)刻復(fù)雜度為-12 .一棵 B樹(shù)中的所有葉子結(jié)點(diǎn)均處在一一上。13 .每次從無(wú)序表中順序取出一個(gè)元素，把這插入到有序表中的適當(dāng)位置，此種排序方法叫做排序； 每次從無(wú) 序表中選擇出一個(gè)最小或最大元素，把它交換到有序表 的一端，此種排序方法叫做排序。14 .快速排序在乎均情況下的時(shí)刻復(fù)雜度為一一，最壞情況下的時(shí)刻復(fù)

5、雜度為 三、運(yùn)算題 （每小題 6 分，共 24 分）1 假定一棵二叉樹(shù)廣義表表示為 a（b（c ，d），c（ ，8） ，分不寫(xiě)出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。先序：中序；5 / 14后序：2.已知一個(gè)帶權(quán)圖的頂點(diǎn)集 V 和邊集 G 分不為：V = 0 , 1, 2, 3, 4, 5；E=（0， 1）8， （0， 2）5， （0， 3）2， （1， 5）6， （2，3）25， （2，4）13, （3, 5）9, （4, 5）10 ,則求出該圖的最小生成樹(shù)的權(quán)。最小生成樹(shù)的權(quán)；3假定一組記錄的排序碼為 （46 , 79, 56, 38, 40, 84, 50, 42） ,則利用堆排序方

6、法建立的初始堆為。4有 7 個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分不為 3，7，8，2，6， 10，14，試以它們?yōu)槿~子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，求出該樹(shù)的帶 權(quán)路徑長(zhǎng)度、高度、雙分支結(jié)點(diǎn)數(shù)。帶權(quán)路徑長(zhǎng)度： 高度： 雙分支結(jié)點(diǎn)數(shù)：四、閱讀算法，回答問(wèn)題 (每小題 8 分，共 16 分)6 / 141 VOldAC(List&L)InitList(L) ；InsertRear(L;25) ；InsertFront(L ，50) ；IntaL4 = 5, 8, 12, 15, 36;for(i nti = 0; i5; i+)if (ai%2= 0)1 nsertFront(L , ai);elselnsert

7、Rear(L ，ai) ；該算法被調(diào)用執(zhí)行后，得到的線性表 L 為：2 void AG(Queue&Q)InitQueue(Q) ；7 / 14inta5= 6 , 12, 5, 15, 8;for(int i=0;i5; i+)QInsert(Q, ai);QInsert(Q，QDelete(Q) ；QInsert(Q, 20)；QInsert(Q, QDelete(Q) 十 16) ；while(!QueueEmpty(Q)coutQDelete(Q) ”；該算法被調(diào)用后得到的輸出結(jié)果為：五、算法填空, 在畫(huà)有橫線的地點(diǎn)填寫(xiě)合適的內(nèi)容 (每小題 6 分,共 12 分 )1 從一維數(shù)組 An) 中二分查找關(guān)鍵字為 K 的元素的遞歸算法，若查找成功則返回對(duì)應(yīng)元素的下標(biāo)，否則返回一1。IntBinsch(ElemTypeA，Intlow ，int high ， KeyTypeK)if(low= hig