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

1、一、單選題(每小題2分，共12分) 1在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行( )。 A HLps p一nextHL B p一nextHL；HLp3 C p一nextHl；pHL； D p一nextHL一next;HL一nextp； 2n個(gè)頂點(diǎn)的強(qiáng)連通圖中至少含有( )。 A.nl條有向邊 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) D.O(n2) 4由權(quán)值分不為3，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹(shù)，它的帶權(quán)路徑長(zhǎng)度為(

2、)。 A24 B48C 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ù)雜度為( )。 AO(n) BO(1) CO(n2) DO(10g2n)二、填空題(每空1分，共28分) 1數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為、和四種。 2在廣義表的存儲(chǔ)結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個(gè)域?qū)?yīng)不同，各自分不為域和域。 3中綴表達(dá)式 3十x*(2.456)所對(duì)應(yīng)的后綴表達(dá)式為。 4在一棵高度為h的3叉樹(shù)中，最多含有結(jié)點(diǎn)。 5

3、假定一棵二叉樹(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)行任一種遍歷時(shí)，其時(shí)刻復(fù)雜度為。 10從有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分不為和 11假定對(duì)長(zhǎng)度n144的線性表進(jìn)行索引順序查找，并假定每個(gè)子表的

4、長(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ù)雜度為 。 三、運(yùn)算題(每小題6分，共24分) 1假定一棵二叉樹(shù)廣義表表示為a(b(c，d)，c(，8)，分不寫(xiě)出對(duì)它進(jìn)行先序、中序、后序和后序遍歷的結(jié)果。 先序： 中序； 后序： 2已知一個(gè)帶權(quán)圖的頂點(diǎn)集V和邊集G分不為： V0，1，2，3，4，5； E=(0，1

5、)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)，則利用堆排序方法建立的初始堆為。 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分) 1VOldAC(List&L) InitList(L)； InsertRear(L;25)； In

6、sertFront(L，50)； IntaL45，8，12，15，36; for(inti0; i5; i+) if (ai20)InsertFront(L，ai)； elselnsertRear(L，ai)； 該算法被調(diào)用執(zhí)行后，得到的線性表L為： 2void AG(Queue&Q) InitQueue(Q)； inta56，12，5，15，8； for(int i0;i5; i+)QInsert(Q，ai)； QInsert(Q，QDelete(Q)； QInsert(Q，20)； QInsert(Q，QDelete(Q)十16)； while(!QueueEmpty(Q)coutQDel

7、ete(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(lowhigh) int mid(low+high)2； if(KAmid.key)； else if (KdataX)return 1; 根結(jié)點(diǎn)的層號(hào)為1 向子樹(shù)中查找x結(jié)點(diǎn) else int clNodeLevel(BT一left，X)； if(cl1)return cl+

8、1; int c2 ； if； 若樹(shù)中不存在X結(jié)點(diǎn)則返回o else return 0； 六、編寫(xiě)算法(8分) 按所給函數(shù)聲明編寫(xiě)一個(gè)算法，從表頭指針為HL的單鏈表中查找出具有最大值的結(jié)點(diǎn)，該最大值由函數(shù)返回，若單鏈表為空則中止運(yùn)行。 EIemType MaxValue(LNOde*HL);答案:一、單選題(每小題2分，共12分) 評(píng)分標(biāo)準(zhǔn)；選對(duì)者得2分，否則不得分。 1B 2B 3C 4D 5B 6A 二、填空題(每空1分，共28分) 1順序結(jié)構(gòu) 鏈接結(jié)構(gòu) 索引結(jié)構(gòu) 散列結(jié)構(gòu)(次序無(wú)先后) 2值(或data) 子表指針(或sublist) 33 x 24 56一*十 4(3h一1)2 5 5

9、 18 6小于 大于(或大于等于) 7向上 堆頂 8鄰接矩陣 鄰接表 邊集數(shù)組(次序無(wú)先后) 9O(n2) O(e) 10 1 3 1113 O( ) 12同一層 13插人 選擇 14O(nlog2n) O(n2) 三、運(yùn)算題(每小題6分，共24分) 1先序：a，b，c，d，e，f，e 2分 中序：c，b，d，a，f，8，e 2分 后序：c，d，b，e，f，e，a 2分 2最小生成樹(shù)的權(quán)：31 6分 3(84，79，56，42，40，46，50，38) 6分 4帶權(quán)路徑長(zhǎng)度：131 3分 高度：5 2分 雙分支結(jié)點(diǎn)數(shù)：6 1分四、閱讀算法，回答問(wèn)題(每小題8分，共16分) 評(píng)分標(biāo)準(zhǔn)：每小題正確得8分，出現(xiàn)一處錯(cuò)誤扣4分，兩處及以上錯(cuò)誤不得分。 1(36，12，8，50，25，5，15) 25 15 8 6 20 28五、算法填空，在畫(huà)有橫線的地點(diǎn)填寫(xiě)合適的內(nèi)容(每小題6分，共12分) 1feturn mid 2分 returnBinsch(A，low，mid一1，K) 2分 returnBmsch(A，mid+1，high，K) 2分 2NodeLevel(BT一right，X) 3分 (c2=1)returnc2十1 3分六、編寫(xiě)算法(8分) 評(píng)分標(biāo)準(zhǔn)：請(qǐng)參考語(yǔ)句后的注釋?zhuān)蛞勒涨闆r酌情給分。 ElemType