本科計算機信息第三學(xué)期數(shù)據(jù)結(jié)構(gòu)參考答案

1、數(shù)據(jù)結(jié)構(gòu)模擬卷 A、選擇題1. 在一個長度為 n 的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（ A ）。2A. O（n）B. O（n/2）C. O（1）D. O（n 2）2. 帶頭結(jié)點的單鏈表 first 為空的判定條件是： （ B ）。A. first = NULL;B. first->link = NULL;C. first->link = first;D. first != NULL;3. 從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。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)4. 在系統(tǒng)實現(xiàn)遞歸調(diào)用時需利用遞歸工作記

2、錄保存實際參數(shù)的值。 在傳值參數(shù)情形， 需為 對應(yīng)形式參數(shù)分配空間， 以存放實際參數(shù)的副本； 在引用參數(shù)情形，需保存實際參數(shù)的D ），在被調(diào)用程序中可直接操縱實際參數(shù)。A. 空間B. 副本 C. 返回地址 D. 地址5. 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（ D ）。A.廣義表 B. 二叉樹 C. 稀疏矩陣 D.串6. 以下屬于邏輯結(jié)構(gòu)的是（ C ）。7.A.順序表 B. 哈希表 C. 有序表D.單鏈表對于長度為 9 的有序順序表， 若采用折半搜索，在等概率情況下搜索成功的平均搜索長19度為（ C ）的值除以 9。A. 20B. 18C. 25D. 228. 在有向圖中每個頂點的度等于該頂點的（

3、 C ）。A. 入度B. 出度C. 入度與出度之和D. 入度與出度之差9. 在基于排序碼比較的排序算法中， （ C）算法的最壞情況下的時間復(fù)雜度不高于O(nlog 2n) 。A. 起泡排序 B. 希爾排序 C. 歸并排序D. 快速排序B ）的查找速度。10.當(dāng)a的值較小時，散列存儲通常比其他存儲方式具有（A.較慢B.較快C.相同 D.不同二、填空題1. 二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個數(shù)組元素最多有 2_個直接前驅(qū)（或直接后繼）。2. 將一個n階三對角矩陣A的三條對角線上的元素按行壓縮存放于一個一維數(shù)組B中，A00存放于B0中。對于任意給定數(shù)組元素BK，它應(yīng)是A中第_.（K+1）/3_行

4、的元素。3. 鏈表對于數(shù)據(jù)元素的插入和刪除不需移動結(jié)點，只需改變相關(guān)結(jié)點的指針域的值。4. 在一個鏈?zhǔn)綏Ｖ?，若棧頂指針等于NULL則為空棧_。5. 主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的返回_地址。6. 在一棵樹中，_葉子_結(jié)點沒有后繼結(jié)點。7. 一棵樹的廣義表表示為a （b （c, d （e, f）, g （h） ）, i （j, k （x, y），結(jié)點 f的層數(shù)為 3。假定根結(jié)點的層數(shù)為 0。8. 在一棵AVL樹（高度平衡的二叉搜索樹）中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過1_。9. n （n > 0）

5、個頂點的無向圖最多有 n（n-1）/2_條邊，最少有_0條邊。10. 在索引存儲中，若一個索引項對應(yīng)數(shù)據(jù)對象表中的一個表項（記錄），則稱此索引為_稠密索引，若對應(yīng)數(shù)據(jù)對象表中的若干個表項，則稱此索引為_稀疏索引。三、判斷題1. 數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的（對）2. 鏈?zhǔn)酱鎯υ诓迦牒蛣h除時需要保持物理存儲空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序（錯）3. 在用循環(huán)單鏈表表示的鏈?zhǔn)疥犃兄校梢圆辉O(shè)隊頭指針，僅在鏈尾設(shè)置隊尾指針（對）4. 通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高（錯）5. 一個廣義表的表尾總是一個廣義表（對）6. 當(dāng)從

6、一個小根堆（最小堆）中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止（對）7. 對于一棵具有 n個結(jié)點，其高度為 h的二叉樹，進(jìn)行任一種次序遍歷的時間復(fù)雜度為O（h）（錯）8. 存儲圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點個數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)(錯)9. 直接選擇排序是一種穩(wěn)定的排序方法(錯)10閉散列法通常比開散列法時間效率更高(錯)四、運算題1. 設(shè)有一個10 10的對稱矩陣A,將其下三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么A85存放于B中什么位置。解：根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I > J

7、時，任意元素 AIJ在一維數(shù)組B中的存放位置為I * (I + 1) / 2 + J，因此，A85在數(shù)組B中位置為8 * (8 + 1) / 2 + 5 = 41 。2. 這是一個統(tǒng)計單鏈表中結(jié)點的值等于給定值x的結(jié)點數(shù)的算法，其中while循環(huán)有錯,請重新編寫出正確的while循環(huán)。int cou nt ( ListNode * Ha, ElemType x ) / Ha為不帶頭結(jié)點的單鏈表的頭指針int n = 0;while ( Ha->li nk != NULL ) Ha = Ha->li nk;if ( Ha->data = x ) n+;return n;解：wh

8、ile ( Ha != NULL ) if ( Ha->data = x )n+;Ha = Ha->link ;3. 已知一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列:A, B, C, D, E, F, G, H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：解：后序序列：C, B, F, E, I, J, H, G, D, A4. 已知一個有序表 (15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )順序存儲于一維數(shù)組a12中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34, 56,

9、 58, 63, 94時的比較次數(shù)。元素值比較次數(shù)34565863943456586394021344解：判斷結(jié)果元素值比較次數(shù)5. 設(shè)散列表為 HT17,待插入關(guān)鍵碼序列為 Jan, Feb, Mar, Apr, May, June, July,Aug, Sep, Oct, Nov, Dec ，散列函數(shù)為 H (key) = li 2，其中，i是關(guān)鍵碼第個字母在字母表中的序號?，F(xiàn)采用線性探查法解決沖突。字母ABCDEFGHIJKLM序號12345678910111213字母NOPQRSTUVWXYZ序號14151617181920212223242526 試畫出相應(yīng)的散列表;H(Jan) =

10、 _10 2 = 5，成功.H(Feb) = _6 2 = 3，成功H(Mar) = I113 2 = 6，成功H(Apr) = _1 2 = 0 ,成功.H(May) = I113 2 = 6，= 7，成功，H(June) = I110 2 = 5，= 6,=7，=8，成功H(July)=I110 2 = 5，=6，= 7，=8，= 9，成功.H(Aug)=:_1 2 = 0，=1，成功H(Sep) = ll_19 2 = 9，=:10,成功H(Oct)=_15 2 = 7，=8，= 9，=10，= 11，成功H(Nov)=I114 2 = 7，=8，= 9，=10，= 11，= 12，成功

11、H(Dec)=H4 2 = 2，成功.相應(yīng)的散列表:AprAugDecFebJanMarMayJuneJulySepOctNov012345678910111213 (1) (5)(2)(5)(6)(2)計算等概率下搜索成功的平均搜索長度;1/12 * (1 + 2 + 1 + 1 + 1 + 1 + 2 + 4 + 5 + 2 + 5 + 6) = 31 / 12五、算法設(shè)計題已知二叉樹中的結(jié)點類型用BinTreeNode表示，被定義為：struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中 data為結(jié)點值域，

12、leftChild 和rightChild分別為指向左、右子女結(jié)點的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點。int BTreeCo unt ( Bi nTreeNode* BT );解：int BTreeCo unt ( Bi nTreeNode* BT ) if ( BT = NULL ) return 0;2 分else return BTreeCount ( BT ->leftChild ) + BTreeCount ( BT ->rightChild ) + 1 ;4分?jǐn)?shù)據(jù)結(jié)構(gòu)模擬卷 B一、單項

13、選擇題1以下與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)的術(shù)語是（C ）。A.循環(huán)隊列B.鏈表C.哈希表D.棧2以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是線性結(jié)構(gòu)（D ）。A.廣義表B.二叉樹C.稀疏矩陣D.串3以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（B ）。A.棧B.哈希表C.線索樹D.雙向鏈表4在下面的程序段中，對 x 的賦值語句的頻度為（ C ）。FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A O（2n）B O（n） CO（n2）D O（log 2n）5. 下面關(guān)于線性表的敘述中，錯誤的是哪一個（B ）。A. 線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B. 線性表采用順序存儲，便于進(jìn)行插入和

14、刪除操作。C. 線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D. 線性表采用鏈接存儲，便于插入和刪除操作。6. 線性表是具有n個（C ）的有限序列（n>0）。A.表元素B .字符 C .數(shù)據(jù)元素 D .數(shù)據(jù)項E.信息項7. 若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運算， 則利用（ A ）存儲方式最節(jié)省時間。A.順序表B .雙鏈表C.帶頭結(jié)點的雙循環(huán)鏈表D .單循環(huán)鏈表8. 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節(jié)省運算時間。A.單鏈表B 僅有頭指針的單循環(huán)鏈表C 雙鏈表D僅有尾指針的單循環(huán)鏈表9.

15、 下面給出的四種排序法中 （ D ） 排序法是不穩(wěn)定性排序法。A. 插入 B.冒泡C.二路歸并 D. 堆積10.下列排序算法中，其中(D)是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序11.已知一算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為(D )。A. -A+B*C/DE B. -A+B*CD/E C. -+*ABC/DE D. -+A*BC/DE12.算術(shù)表達(dá)式a+b* (c+d/e )轉(zhuǎn)為后綴表達(dá)式后為( B )。A. ab+cde/* Babcde/+*+ Cabcde/*+ D . abcde

16、*/+二、填空題，在橫線處填寫合適內(nèi)容1. 數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)包括順序、鏈接、索引和散列等四種。2. 在程序運行過程中可以擴(kuò)充的數(shù)組是_動態(tài) 分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。3. 在鏈表中進(jìn)行插入和刪除 操作的效率比在順序存儲結(jié)構(gòu)中進(jìn)行相同操作的效率高。后出先進(jìn)_表。遞歸的對象。結(jié)點f的層數(shù)為4. 棧是一種限定在表的一端進(jìn)行插入和刪除的線性表，又被稱為5. 如果一個對象部分地包含自己，或自己定義自己，則稱這個對象是6. 一 棵樹的 廣義表 表示為 a(b(c,d(e,f),g(h),i(j,k(x,y)3。假定樹根結(jié)點的層數(shù)為0。7. 一棵樹按照左子女-右兄弟表示法轉(zhuǎn)換成對應(yīng)的

17、二叉樹，則該二叉樹中樹根結(jié)點肯定沒有右子女。8. 向一棵二叉搜索樹中插入一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它插入到根 結(jié)點的_左子樹上。9. 設(shè)圖 G=(V,E)，V=1,2,3,4, E=<1,2>,<1,3>,<2,4>,<3,4>，從頂點 1 出發(fā)，對圖 G進(jìn)行廣度優(yōu)先搜索的序列有 2種。10. 每次直接或通過基準(zhǔn)元素間接比較兩個元素，若出現(xiàn)逆序排列就交換它們的位置，這種排序方法叫做 交換排序。11. 快速排序在平均情況下的空間復(fù)雜度為_ O（log 2n） _ 。12. 若對長度 n=10000 的線性表進(jìn)行二級索引存儲，每級索

18、引表中的索引項是下一級 20 個 表項的索引，則一級索引表的長度為 _500。三、判斷題1. 在順序表中進(jìn)行順序搜索時， 若各元素的搜索概率不等， 則各元素應(yīng)按照搜索概率的降序 排列存放，則可得到最小的平均搜索長度（ 對 ）2. 在二叉搜索樹中，若各結(jié)點的搜索概率不等，使得搜索概率越小的結(jié)點離樹根越近，則 得到的是最優(yōu)二叉搜索樹（錯 ）3. 對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動都能使整個工程提前完成（錯）4. 直接選擇排序是一種穩(wěn)定的排序方法（錯）5. 閉散列法通常比開散列法時間效率更高（ 錯 ）6. 數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的（對）7. 順序表和一維數(shù)組

19、一樣，都可以按下標(biāo)隨機（或直接）訪問（對）8. 在一個順序存儲的循環(huán)隊列中 , 隊頭指針指向隊頭元素的后一個位置（ 錯 ）9. 用非遞歸方法實現(xiàn)遞歸算法時一定要使用遞歸工作棧（錯 ）10. 在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)行中序遍歷和后 序遍歷，則具有相同的結(jié)果（ 對 ）四、運算題1. 設(shè)有一個二維數(shù)組 A1020 ，按行存放于一個連續(xù)的存儲空間中， A00 的存儲地址 是 200，每個數(shù)組元素占 1 個存儲字，則 A62 的存儲字地址是多少。A62 的存儲字地址： 322答案說明：按行存儲時，計算 Aij 地址的公式為LOC（i,j）=LOC（0,0）+（i*n

20、+j）*d其中首地址 LOC（0,0）=200, 每個數(shù)組元素的存儲占用數(shù) d=1, 二維數(shù)組的列數(shù) n=20， 根據(jù)題意，元素 A62 的存儲地址為LOC（6,2）=200+（6*20+2）*1=3222. 已知一棵二叉樹的中序和后序序列如下，求該二叉樹的高度（假定空樹的高度為 -1 ）和度為 2、度為 1 及度為 0 的結(jié)點個數(shù)。中序序列： c,b,d,e,a,g,i,h,j,f后序序列：c,e,d,b,i,j,h,g,f,a 求解一下問題：高度： 4度為2的結(jié)點數(shù)：3度為1的結(jié)點數(shù)：3度為0的結(jié)點數(shù)：43. 假定一組記錄為(36,75,83,54,12,67,60,40)，將按次序把每個

21、結(jié)點插入到初始為空的一棵AVL樹中，請回答在插入時需進(jìn)行“左單旋轉(zhuǎn)”、“右單旋轉(zhuǎn)”、“先左后右雙旋轉(zhuǎn)”、“先右后左雙旋轉(zhuǎn)”，“不調(diào)整”的結(jié)點數(shù)各是多少？左單旋轉(zhuǎn)結(jié)點個數(shù)：1右單旋轉(zhuǎn)結(jié)點個數(shù)：0先左后右雙旋轉(zhuǎn)結(jié)點個數(shù)：1先右后左雙旋轉(zhuǎn)結(jié)點個數(shù)：0不調(diào)整結(jié)點個數(shù)：64. 已知一個帶權(quán)圖的頂點集 V和邊集G分別為:V=0,1,2,3,4,5,6;E=(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,(4,5)6,(4,6)6,(5,6)12;試根據(jù)迪克斯特拉(Dijkstra)算法求出從頂點0到其余各頂點的最短路徑，在下面填寫

22、對應(yīng)的路徑長度。頂點：路徑長度:01610142521315. 已知一個數(shù)據(jù)表為36,25,25*,62,40,53，請寫出在進(jìn)行快速排序的過程中每次劃分后 數(shù)據(jù)表的變化。(0) 36 25 25* 62 40 53(1) 25* 25 36 62 40 53(2) 25* 25 36 53 40 62(3) 25* 25 36 40 53 62五、算法設(shè)計題1設(shè)有一個表頭為 first 的單鏈表。試設(shè)計一個算法，通過遍歷一趟鏈表，將鏈表中所有 結(jié)點按逆序鏈接。解答 1template <class Type > void List <Type>: : Tnerse()

23、 if (first= NULL )return ;ListNode <Type >* p=first link ; , *pr =NULL ; While (p !=NULL ) First t link =pr ;Pr =first ;first =p ;p =p t link; first ->link =pr ;解答 2 template <class Type > void List <Type>: : Tnerse() ListNode <Type >* p , *head = new ListNode <Type >

24、; ( ) ; While (first ! = NULL ) P=first ;first = first tlink;ptlink =headtlink ; headtlink =p; first = head t link ; delete head ;數(shù)據(jù)結(jié)構(gòu)模擬卷 C一、單項選擇題1數(shù)據(jù)結(jié)構(gòu)是（D ）。A. 種數(shù)據(jù)類型B. 數(shù)據(jù)的存儲結(jié)構(gòu)C. 一組性質(zhì)相同的數(shù)據(jù)元素的集合D. 相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合 2算法分析的目的是（ B ）。A. 辨別數(shù)據(jù)結(jié)構(gòu)的合理性B. 評價算法的效率C. 研究算法中輸入與輸出的關(guān)系D. 鑒別算法的可讀性3. 在線性表的下列運算中，不

25、.改變數(shù)據(jù)元素之間結(jié)構(gòu)關(guān)系的運算是（ D ）。A.插入B.刪除C.排序D.定位4. 若進(jìn)棧序列為 1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)的出棧序列 為（ B ）。A. 3， 2， 6，1，4，5B. 3，4，2， 1，6，5C. 1， 2， 5，3，4，6D. 5，6，4， 2，3，15. 設(shè)串 sl= " Data Structures with Java " ,s2= it，則子串定位函數(shù)index（s1,s2）的值為（ D ）。A.15B.16C.17D.186. 二維數(shù)組 A89 按行優(yōu)先順序存儲，若數(shù)組元素 A23 的存儲地址為 1087，

26、A47的存儲地址為 1153，則數(shù)組元素 A67的存儲地址為（ A ）。A.1207B.1209C.1211D.1213A ）。7. 在按層次遍歷二叉樹的算法中，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)是（B.棧A.隊列C.線性表D.有序表&在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系（B ）。A.不一定相同B.都相同C.都不相同D.互為逆序9. 若采用孩子兄弟鏈表作為樹的存儲結(jié)構(gòu)，則樹的后序遍歷應(yīng)采用二叉樹的（C ）。A層次遍歷算法B.前序遍歷算法C.中序遍歷算法D.后序遍歷算法10若用鄰接矩陣表示一個有向圖，則其中每一列包含的1 的個數(shù)為（A ）。A.圖中每個頂點的入度B.圖中每

27、個頂點的出度C.圖中弧的條數(shù)D.圖中連通分量的數(shù)目11. 圖的鄰接矩陣表示法適用于表示（C ）。A.無向圖B.有向圖C.稠密圖D.稀疏圖12在對n個關(guān)鍵字進(jìn)行直接選擇排序的過程中，每一趟都要從無序區(qū)選出最小關(guān)鍵字元素，則在進(jìn)行第i趟排序之前，無序區(qū)中關(guān)鍵字元素的個數(shù)為（ D ）。A. iB. i+1C. n-iD. n-i+1二、填空題1 .棧是特殊的線性表，其運算遵循后進(jìn)先出的原則。2. _棧 是限定僅在表尾進(jìn)行插入或刪除操作的線性表。3. 一個棧的輸入序列是：1, 2, 3則不可能的棧輸出序列是 _3, 1, 2。4. 二叉樹由一根結(jié)點、左子樹、右子樹_三個基本單元組成。5. 在二叉樹中，

28、指針p所指結(jié)點為葉子結(jié)點的條件是P->Lchild=NULL &&P->Rchild=NULL。6. 具有256個結(jié)點的完全二叉樹的深度為9。7 .已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該 樹有 12個葉子結(jié)點。&若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的_比較和記錄的移動。則最省時間的是9.分別采用堆排序， 快速排序，冒泡排序和歸并排序，對初態(tài)為有序的表,_冒泡排序算法，最費時間的是_快速排序_算法。10. 不受待排序初始序列的影響，時間復(fù)雜度為0(M)的排序算法是_選擇排序 ,在排序算法的最后一趟開始之前， 所有元素都可能不在其最終位置上的排序算法是_歸并排序 三、解答題a,(b,c),畫出該廣義表的圖形表示。2.已知二叉樹的先序序列和中序序列分別為HDACBGF和ADCBHFEG(1 )畫出該二叉樹；3已知帶權(quán)