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

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

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

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

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

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

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

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

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

9、進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？AA． 3 2 1 5 4 B． 4 5 3 1 2 C． 3 4 5 2 1 D． 2 3 4 1 53、無(wú)向圖 、無(wú)向圖 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)}，對(duì)該圖進(jìn)行深度優(yōu)先 ，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是

10、 遍歷，得到的頂點(diǎn)序列正確的是 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、鏈表不具有的特點(diǎn)是 、鏈表不具有的特點(diǎn)是 BA．插入、刪除不需要移動(dòng)元素 ．插入、刪除不需要移動(dòng)元素 B．可隨機(jī)訪問(wèn)任一元素 ．可隨機(jī)訪問(wèn)任一元素 C．不必事先估計(jì)存儲(chǔ)空間 ．不必事先估計(jì)存儲(chǔ)空間 D．所需空間與線性表長(zhǎng)度成正比 ．

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

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

13、分）已知下列程序，Ls 指向帶頭結(jié)點(diǎn)的單鏈表。 指向帶頭結(jié)點(diǎn)的單鏈表。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