數(shù)據(jù)結(jié)構(gòu)試卷A及答案___黃河科技學(xué)院

1、數(shù)據(jù)結(jié)構(gòu)課程試題(A卷一、單選題(每小題1分,共20分1.串是任意有限個(。A. 符號構(gòu)成的序列B. 字符構(gòu)成的序列C. 符號構(gòu)成的集合D. 字符構(gòu)成的集合2.對于鍵值序列20,73,71,23,74,16,05,68,76,103用篩選法建堆,開始結(jié)點的鍵值是(。A. 103B. 74C. 20D. 233.若在線性表中采用二分法查找元素,該線性表應(yīng)該(。A.元素按值有序B.元素按值有序,且采用順序存儲結(jié)構(gòu)C. 采用順序存儲結(jié)構(gòu)D.元素按值有序,且采用鏈?zhǔn)酱鎯Y(jié)構(gòu)4.一個具有n個頂點的有向圖,若采用鄰接矩陣表示,則該鄰接矩陣中第i行非零元素的個數(shù)是Vi的(。A. 入度B.出度C.度D.路徑長

2、度5.在一個單鏈表中,若p所指結(jié)點不是最后結(jié)點,在p之后插入s 所指結(jié)點,則執(zhí)行的操作是(。A. p-next=s;s-next=pB. s-next=p-next; p-next=sC.s-next=p; p-next=sD. s-next=p-next;p=s6.在雙鏈表中刪除指針P所指結(jié)點的后繼結(jié)點,最多需修改的指針域的個數(shù)為(。A. 4B. 2C. 1D. 67.若一棵二叉樹具有20個度為2的結(jié)點,則該二叉樹的葉子結(jié)點個數(shù)是(。A. 20B. 10C. 21D. 不確定8.假設(shè)h(key,h1(key是不同的散列函數(shù),散列表沖突的條件是(。A.keyi keyj, h(keyi=h(k

3、eyjB.keyi keyj, h(keyi=h1(keyjC.h(keyi =h(keyjD.h1(keyi =h(keyj9.在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為(。A.4B.5C.6D.710.串的長度是(。A.串中不同字母的個數(shù)B.串中不同字符的個數(shù)C.串中所含字符的個數(shù)D.串中所含字母的個數(shù)11.處理沖突的兩類主要方法是(。A.線性探查法和基數(shù)轉(zhuǎn)換法B.除余法和折疊法C.建溢出區(qū)法和不建溢出區(qū)法D.拉鏈法和開地址法12.鏈棧與順序棧相比,有一個較明顯的優(yōu)點是(。A .通常不會出現(xiàn)棧滿的情況B .通常不會出現(xiàn)?？盏那闆rC .插入操作更加方

4、便D . 刪除操作更加方便13.具有20個頂點的有向完全圖的邊數(shù)是(。A.19B.190C.380D. 10014.平衡二叉排序樹的平衡因子為(。A. 0,-1,1B. 0,1,2C. 1,2,-1D.2,4,315.一個隊列的入隊序列是A,B,C,D,則隊列的輸出序列是(。A. D,C,B,AB. A,B,C,DC. A,D,C,BD. C,B,D,A16.循環(huán)單鏈表head的尾指針p滿足(。A. p->next=NULLB.p=NULLC.p->next=headD.p=head17.如果以鏈表作為棧的存儲結(jié)構(gòu),則入棧操作時(。A. 必須判別棧是否滿B. 對棧不作任何判定C.

5、必須判別棧是否空D. 判別棧元素的類型18.計算機算法必須具備的三個特性(。A.可執(zhí)行性、可移植性、可擴充性B. 可執(zhí)行性、確定性、有窮性C. 確定性、有窮性、穩(wěn)定性D. 易讀性、穩(wěn)定性、安全性19.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為(兩大類。A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)20.下面的程序段的時間復(fù)雜度為(。for (i=1;i<=n;i+for (j=1;j<=n;j+y=y+1;nA. O(2nB.O(n2C. O(nD.O(log2二、判斷題(每小題1分,共10分1.線性表的鏈接存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。(2. 棧和隊列都

6、是線性表,只是操作受到了一些限制。 ( 3. 棧和隊列的存儲方式,既可以是順序方式,又可以是鏈?zhǔn)椒绞健? 4.哈夫曼樹是帶權(quán)外部路徑長度最短的二叉樹,路徑上權(quán)值較大的結(jié)點離根較近。(5. 連通圖一定是無向完全圖。(6.二叉樹有五種基本形態(tài)。(7.冒泡排序算法是穩(wěn)定的。(8.數(shù)據(jù)項是構(gòu)成數(shù)據(jù)的基本單位。(9.構(gòu)建散列表時,沖突是可以避免的。(10.利用有向無環(huán)圖的鄰接表構(gòu)建拓撲排序時,需借助棧。(三、綜合分析題(每小題10分,共60分1.已知序列10,18,4,3,6,12,20,9,15,1,請采用冒泡排序法對該序列進行升序排序,畫出具體過程。2.設(shè)有一組關(guān)鍵字序列:29,12,23,22,1

7、3,20,18,30,采用散列函數(shù)H(key=keyMOD10,采用線性探查法解決碰撞,試在09的散列地址空間中對該關(guān)鍵字序列構(gòu)造散列表,并求出在等。概率的情況下,此散列表的成功的平均查找長度ASLsucc3.已知無向圖如圖所示,(1畫出圖的鄰接表。(2從A開始,給出一棵廣度優(yōu)先生成樹。 數(shù)據(jù)結(jié)構(gòu)課程試題答案及評分標(biāo)準(zhǔn)(A卷一、單選題(每小題1分,共20分01-05.BBBBB 06-10.ACACC11-15. DACAB 16-20.CCBCB二、判斷題(每小題1分,共10分1-5.XVVVX 6-10.VVXXV三、綜合分析題(每小題10分,共60分1.110,4,3,6,12,18,9

8、,15,1,|20 2分24,3,6,10,12,9,15,1,|18,20 1分33,4,6,10,9,12,1,|15,18,20 1分43,4,6,9,10,1,|12,15,18,20 1分53,4,6,9,1,|10, 12,15,18,20 1分63,4,6,1,|9,10, 12,15,18,20 1分73,4,1,|6,9,10, 12,15,18,20 1分83,1,|4,6,9,10, 12,15,18,20 1分91,|3,4,6,9,10, 12,15,18,20 1分2.h(29=29MOD10=9h(12=12MOD10=2h(23=23MOD10=3h(22=22MOD10=2h(13=13MOD10=3h(20=20MOD10=