山東理工大學(xué)數(shù)據(jù)結(jié)構(gòu)期末試題及答案

1、10-11 學(xué)年 學(xué)年 第一學(xué)期 第一學(xué)期 計算機(jī)科學(xué)與技術(shù)專業(yè) 計算機(jī)科學(xué)與技術(shù)專業(yè) 張先偉、肖愛梅 張先偉、肖愛梅一、填空（每空 一、填空（每空 1 分，共 分，共 20 分） 分）1、深度為 、深度為 k 的完全二叉樹至少有 的完全二叉樹至少有 k 個結(jié)點，具有 個結(jié)點，具有 10 個葉結(jié)點的二叉樹中有 個葉結(jié)點的二叉樹中有 9 個度為 個度為 2 的結(jié)點。 的結(jié)點。2、設(shè)數(shù)組 、設(shè)數(shù)組 a[1..5,1..8]的基地址為 的

2、基地址為 200，每個元素占 ，每個元素占 2 個存儲單元，若以行序為主序順序存儲，則元素 個存儲單元，若以行序為主序順序存儲，則元素a[4,6]的存儲地址為 的存儲地址為 200+(3*8+5)*2=258。3、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是 、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是時間復(fù)雜度 時間復(fù)雜度和空間復(fù)雜度 空間復(fù)雜度。4、順序存儲結(jié)構(gòu)是通過 、順序存儲結(jié)構(gòu)是通過元素在存儲器中的相對位置 元素在存儲器中的相對位置表示元素之間

3、的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過 表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指示 指示元素存儲地址的指針 元素存儲地址的指針表示元素之間的關(guān)系的。 表示元素之間的關(guān)系的。5、要在一個單鏈表中 、要在一個單鏈表中 p 所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為 所指結(jié)點之后插入一個子鏈表，子鏈表第一個結(jié)點的地址為 s，子鏈表最后一 ，子鏈表最后一個結(jié)點的地址為 個結(jié)點的地址為 t, 則應(yīng)執(zhí)行操作： 則應(yīng)執(zhí)行操作：t->next=

4、p->next 和 P->next=s 。6、設(shè)有向圖 、設(shè)有向圖 G 的存儲結(jié)構(gòu)用鄰接矩陣 的存儲結(jié)構(gòu)用鄰接矩陣 A 來表示，則 來表示，則 A 中第 中第 i 行中所有非零元素個數(shù)之和等于頂點 行中所有非零元素個數(shù)之和等于頂點 i 的出度 出度，第 ，第 i 列中所有非零元素個數(shù)之和等于頂點 列中所有非零元素個數(shù)之和等于頂點 i 的入度 入度。7、對于表長為 、對于表長為 n 的順序存儲的線性表，訪問結(jié)點的時間復(fù)雜度為

5、的順序存儲的線性表，訪問結(jié)點的時間復(fù)雜度為 O(1)，刪除結(jié)點的時間復(fù)雜度為 ，刪除結(jié)點的時間復(fù)雜度為 O(n) 。8、將一棵有 、將一棵有 100 個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點 個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進(jìn)行編號，根結(jié)點編號為 編號為 1，則編號最大的非葉結(jié)點的編號為： ，則編號最大的非葉結(jié)點的編號為：509、己知有序表為 、己知有序表為(12，18，24

6、，35，47，50，62，83，90，115，134)，當(dāng)用折半查找法查找 ，當(dāng)用折半查找法查找 100 時， 時，需 3 次才能確定不成功。 次才能確定不成功。10、Dijkstra 最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按 最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按路徑長度遞增 路徑長度遞增次序依次產(chǎn)生。 次序依次產(chǎn)生。11、如果 、如果 T2 是由樹 是由樹 T1 轉(zhuǎn)換而來的二叉樹，那么 轉(zhuǎn)換而來的二叉樹，那

7、么 T1 中結(jié)點的后序遍歷就是 中結(jié)點的后序遍歷就是 T2 中結(jié)點的 中結(jié)點的中序 中序遍歷。 遍歷。12、廣義表 、廣義表 A= (d)則 Head(Tail(Head(Tail(Tail(A)))))的值為 的值為 d。13、設(shè)無向連通圖的頂點個數(shù)為 、設(shè)無向連通圖的頂點個數(shù)為 n，則該圖最少有 ，則該圖最少有 n-1 條邊，最多有 條邊，最多有 n(n-1)/2 條邊。 條邊。二、選擇（每題 二、選擇（每題 2 分，共 分，共 2

8、0 分 ）1、若需在 、若需在 O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是 的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是 C A． 快速排序 快速排序 B． 堆排序 堆排序 C． 歸并排序 歸并排序 D． 直接插入排序 直接插入排序 2、有五個元素按 、有五個元素按 5，4，3，2，1 的順序進(jìn)棧，問下列哪一個不是合法的出棧序列？ 的順序

9、進(jìn)棧，問下列哪一個不是合法的出棧序列？AA． 3 2 1 5 4 B． 4 5 3 1 2 C． 3 4 5 2 1 D． 2 3 4 1 53、無向圖 、無向圖 G=(V,E)，其中： ，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進(jìn)行深度優(yōu)先 ，對該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點序列正確的是

10、 遍歷，得到的頂點序列正確的是 DA．a(chǎn),b,e,c,d,f B．a(chǎn),c,f,e,b,d C．a(chǎn),e,b,c,f,d D．a(chǎn),e,d,f,c,b4、鏈表不具有的特點是 、鏈表不具有的特點是 BA．插入、刪除不需要移動元素 ．插入、刪除不需要移動元素 B．可隨機(jī)訪問任一元素 ．可隨機(jī)訪問任一元素 C．不必事先估計存儲空間 ．不必事先估計存儲空間 D．所需空間與線性表長度成正比 ．

11、所需空間與線性表長度成正比4、 （6 分） 分）采用哈希函數(shù) 采用哈希函數(shù) H(k)=3*k MOD 13，并用線性探測開放地址法處理沖突，在數(shù)列地址空間 ，并用線性探測開放地址法處理沖突，在數(shù)列地址空間[0..12]中對關(guān)鍵字序列 對關(guān)鍵字序列 22、41、53、46、30、13、1、67、51，構(gòu)造哈希表（畫示意圖） ，構(gòu)造哈希表（畫示意圖） 。5、（ 、（6 分） 分） 下圖為無向帶權(quán)圖，用 下圖為無向帶權(quán)圖，用克魯斯卡爾算法 克

12、魯斯卡爾算法構(gòu)造其最小生成樹，并寫出選邊的順序。 構(gòu)造其最小生成樹，并寫出選邊的順序。6、 （8 分）對關(guān)鍵字序列 分）對關(guān)鍵字序列{30,15,28,20,24,10,12,68,35}，（1）構(gòu)造一棵二叉排序樹； ）構(gòu)造一棵二叉排序樹；（2）對初始序列構(gòu)造一棵二叉平衡樹。 ）對初始序列構(gòu)造一棵二叉平衡樹。四、算法閱讀與設(shè)計題 四、算法閱讀與設(shè)計題(本大題共 本大題共 2 小題，共 小題，共 20 分)1、 （8 分）已知下列程序，

13、分）已知下列程序，Ls 指向帶頭結(jié)點的單鏈表。 指向帶頭結(jié)點的單鏈表。Typedefstruct node {DataType data;struct node * next;} * LinkList;void f30( LinkList Ls ){ LinkList p, q;q = Ls->next;if ( q p=qwhile ( p->next )p = p->next;p->next = q