【文章內(nèi)容簡介】 1. 請分別簡答順序存儲結(jié)構(gòu)與鏈?zhǔn)酱鎯Y(jié)構(gòu)的構(gòu)造原理以及它們的特點(diǎn)。 答：線性表的順序存儲結(jié)構(gòu)是在存儲器中用一片地址連續(xù)的存儲單元依次存 放線性 表中的數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系通過數(shù)據(jù)元素的存儲地址直接反映。在這種存儲結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素在物理位置上也一定相鄰。 2. 對二叉樹中的結(jié)點(diǎn)進(jìn)行按層次順序（每一層自左至右）的訪問操作稱為二叉樹的層次遍歷，遍歷所得到的結(jié)點(diǎn)序列稱為二叉樹的層次序列。現(xiàn)已知一棵二叉樹的層次序列為ABCDEFGHIJ，中序序列為 DBGEHJACIF，請畫出該二叉樹。 【解答】 3. 已知無向圖 G=(V,E) ，其中，頂點(diǎn)集合為 V={v1,v2,v3,v4,v5,v6,v7}, ，邊的集合為 {(v1,v2),(v1,v3),(v2,v1),(v2,v4),(v2,v6),(v3,v1),(v4,v2),(v4,v7),(v5,v4),(v5,v6),(v6,v2),(v6,v2),(v7,v4)},請先給出鄰接表結(jié)構(gòu)，然后分別給出根據(jù)該 鄰接表從頂點(diǎn) v1 出發(fā)進(jìn)行深度優(yōu)先搜索與廣度優(yōu)先搜索后的頂點(diǎn)序列。 【解答】 鄰接表結(jié)構(gòu)： 深度優(yōu)先搜索序列為： v1， v2， v4， v5， v6， v7， v3 廣度優(yōu)先搜索序列為： v1， v2， v3， v4， v6， v5， v7 4. 用寬度優(yōu)先搜索和深度優(yōu)先搜索對如圖所示的無向圖 G進(jìn)行遍歷 (從頂點(diǎn) 1 出發(fā) )， 給出遍歷序列 【解答】搜索本題圖的寬度優(yōu)先搜索的序列為： 12， 4， 3， 6， 5， 8， 7，深度優(yōu)先搜索的序列 為： 1， 2， 6， 4， 5， 7， 8， 30 5. 指出下列算法的時(shí)間復(fù)雜度。 sum1(int n) { int p=1,sum=0,1。 for(i=1。i=n。i++) { p*=I。 sum+=p。 } return(sum)。 } 【解答】 sum1()的嵌套最深層語句： p*=I。 sum+=p。 它的頻度為 n 次，所以其時(shí)間復(fù)雜度是 O(n)。 6. 對于一個(gè)棧，給出輸入項(xiàng) A,B,C。如果輸入項(xiàng)序列由 A,B,C 所組成，試給出全部可能的輸出序列。 【解答】 ABC， ACB， BAC， BCA， CBA 7. 有 n 個(gè)頂點(diǎn)的無向連通圖至少有多少條邊？有 n 個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說明 。 【解答】 n 個(gè)頂點(diǎn)的無向連通圖至少有 n1 條邊， n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有 n 條邊。例如： 8. 請分別敘述在一個(gè)連續(xù)順序文件中采用順序查找法、折半查找法和分塊查找法查找一個(gè)記錄，該文件記錄應(yīng)該滿足什么要求？ 【解答】 采用順序查找法：文件中記錄可以任意次序存放。 采用折半查找法：文件中的記錄必須按照關(guān)鍵字值從小到大或從大到小有序存放。 采用分塊查找法：將文件分成若干段，每一塊中的記錄可以任意存放，但塊與塊之間必須按照關(guān)鍵字從小到大或從大到小的次序存放，即前一塊中 的所有記錄的關(guān)鍵字值必須小于后一塊中所有記錄的關(guān)鍵字值。 9. 試對右圖所示的 AOE 網(wǎng)絡(luò) : (1) 這個(gè)工程最早可能在什么時(shí)間結(jié)束。 (2) 求每個(gè)活動的最早開始時(shí)間 e( )和最遲開始時(shí)間 l( )。 (3) 確定哪些活動是關(guān)鍵活動。 【解答】按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開始時(shí)間 Ve 和最遲允許開始時(shí)間 Vl。然后再計(jì)算各個(gè)活動的最早可能開始時(shí)間 e 和最遲允許開始時(shí)間 l，根據(jù) l e = 0? 來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。 此工程最早完成時(shí)間為 43。 關(guān)鍵 路徑為 1, 33, 22, 55, 6 10. 何為數(shù)據(jù)的邏輯結(jié)構(gòu)？何為數(shù)據(jù)的存儲結(jié)構(gòu)？一般情況下，兩者之間有什么聯(lián)系？這種聯(lián)系是如何反映的？ 【解答】 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間在客觀世界中所具有的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式。在數(shù)據(jù)的順序存儲與鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常要能夠反映數(shù)據(jù)所具有的邏輯結(jié)構(gòu)。在順序存儲結(jié)構(gòu)中，通過數(shù)據(jù)元素的存儲地址來直接反映數(shù)據(jù)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯Y(jié)構(gòu)則是通過指針來間接反映數(shù)據(jù)元素之間的邏輯關(guān)系。 11．分別寫出如圖所示 各二叉樹的前序、中序和后序序列 【解答】： （ 1）前序 （ a） 12357864 （ b） 124735689 （ 2）中序 (a ) 17583624 (b) 472153869 （ 3）后序 (a ) 78563421 (b) 742589631 12. 畫出下圖所示的 AOV網(wǎng)的所有拓?fù)溆行蛐蛄小? 【解答】 ADBECF ADBEFC ADEBCF ADEBFC DABECF DABEFC DAEBCF DAEBFC 13. 何為數(shù)據(jù)的邏輯結(jié)構(gòu)？何為數(shù)據(jù)的存儲結(jié)構(gòu)？一般情況下，兩者之間有什么聯(lián)系？這種聯(lián)系是如何反映的？ 【解答】 數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間在客觀世界中所具有的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式。在數(shù)據(jù)的順序存儲與鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常要能夠反映數(shù)據(jù)所具有的邏輯結(jié)構(gòu)。在順序存儲結(jié)構(gòu)中，通過數(shù)據(jù)元素的存儲地址來直接反映數(shù)據(jù)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯Y(jié)構(gòu)則是通過指針來間接反映數(shù)據(jù)元素之間的邏輯關(guān)系 14 . 已知序列 (35， 70， 12， 26， 90， 41， 66， 58)，請寫出對該序列采用泡排序方法 進(jìn)行升序排序時(shí)各趟的結(jié)果。 【解答】 原始序列： 35， 78， 12， 26， 90， 41， 66， 58 第 — 趟后： 35， 12， 26， 78， 41， 66， 58， 90 第二趟后： 12， 26， 35， 41， 66， 58， 78， 90 第三趟后： 12， 26， 35， 41， 58， 66， 78， 90 第四趟后： 12， 26， 35， 41， 58， 66， 78， 90 15. 何為數(shù)據(jù)的邏輯結(jié)構(gòu)？何為數(shù)據(jù)的存儲結(jié)構(gòu)？一般情況下，兩者之間有什么聯(lián)系？這種聯(lián)系是如何反映的？ 【解答】 數(shù) 據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間在客觀世界中所具有的邏輯關(guān)系。數(shù)據(jù)的存儲結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式。在數(shù)據(jù)的順序存儲與鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常要能夠反映數(shù)據(jù)所具有的邏輯結(jié)構(gòu)。在順序存儲結(jié)構(gòu)中，通過數(shù)據(jù)元素的存儲地址來直接反映數(shù)據(jù)元素之間的邏輯關(guān)系，而鏈?zhǔn)酱鎯Y(jié)構(gòu)則是通過指針來間接反映數(shù)據(jù)元素之間的邏輯關(guān)系。 16．給定一組權(quán)值 : 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長度的擴(kuò)充 4叉樹 , 要求該 4叉樹中所有內(nèi)部結(jié)點(diǎn)的度都是 4, 所有外部結(jié)點(diǎn)的度都是 0。這棵擴(kuò)充 4 叉樹的帶權(quán)外部路徑長度是多少 ? 【解答】 仿照霍夫曼樹的構(gòu)造方法來構(gòu)造擴(kuò)充 4 叉樹，每次合并 4 個(gè)結(jié)點(diǎn)。 17. 已知序列 (35， 78， 12， 26， 66， 41， 66， 58)，請寫出對該序列采用選擇排序方法進(jìn)行升序排序時(shí)各趟的結(jié)果。 【解答】 原始序列： 35， 78， 12， 26， 90， 41， 66， 58 第 — 趟后： 12， 78， 35， 26， 90， 41， 66， 58 第二趟后： 12， 26， 35， 78， 90， 41， 66， 58 ， 第三趟后： 12， 26， 35， 78， 90， 41， 66， 58 第四趟后： 12， 26， 35， 41， 90， 78， 66， 58 第五趟后： 12， 26， 35， 41， 58， 78， 66， 90 第六趟后： 12， 26， 35， 41， 58， 66， 78， 90 第七趟后： 12， 26， 35， 41， 58， 66， 78， 90 18. 數(shù)據(jù)邏輯結(jié)構(gòu)包括哪三種類型？樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為什么？ 【解答】 包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線 性結(jié)構(gòu) 19 . 請分別敘述在一個(gè)連續(xù)順序文件中采用順序查找法、折半查找法和分塊查找法查找一個(gè)記錄，該文件記錄應(yīng)該滿足什么要求？ 【解答】 采用順序查找法：文件中記錄可以任意次序存放。 采用折半查找法：文件中的記錄必須按照關(guān)鍵字值從小到大或從大到小有序存放。 采用分塊查找法：將文件分成若干段，每一塊中的記錄可以任意存放，但塊與塊之間必須按照關(guān)鍵字從小到大或從大到小的次序存放，即前一塊中的所有記錄的關(guān)鍵字值必須小于后一塊中所有記錄的關(guān)鍵字值。 20. 有向圖的鄰接表如下 試給出至少兩個(gè)拓?fù)湫蛄小? 【解答】 V1 V2 V3 V4 V5 V6 V1 V3 V2 V4 V5 V6 五、算法題 1. 已知非空雙向循環(huán)鏈表最左邊那個(gè)鏈結(jié)點(diǎn)的指針為 list,請寫一逆置該雙向循環(huán)鏈表的算法 【解答】 2. 借助棧將輸入任意一個(gè)非負(fù)的十進(jìn)制數(shù) ,打印輸出與其等值的八進(jìn)制。 【解答】 conversion( ) {InitStack(s)。 scanf(%d,n)。 while(n) {Push(S,n%8)。 n=n/8。 } while(!StackEmpty(s)) {Pop(s,X)。 priintf(%d,X) } } 3. 設(shè)有一個(gè)表頭指針為 h的單鏈表。試設(shè)計(jì)一個(gè)算法，通過遍歷一趟鏈表，將鏈表中所有結(jié)點(diǎn)的鏈接方向逆轉(zhuǎn)，如下圖所示。要求逆轉(zhuǎn)結(jié)果鏈表的表頭指針 h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。 解答 1】 templateclass Type void ListType :: Inverse ( ) { if ( first == NULL ) return。 ListNodeType *p = first→ link。, *pr = NULL。 while ( p != NULL ) { first→ link = pr。 //逆轉(zhuǎn) first 指針 pr = first。 first = p。 p = p→ link。 //指針前移 } } 【解答 2】 templateclass Type void ListType :: Inverse ( ) { ListNodeType *p, *head = new ListNodeType ( )。 while ( first != NULL ) { p = first。 first = first→ link。 //摘下 first 鏈頭結(jié)點(diǎn) p→ link = head→ link。 head→ link = p。 //插入 head 鏈前端 } first = head→ link。 delete head。 //重置 first } 4. 有 — 個(gè)循環(huán)雙鏈表，每個(gè)結(jié)點(diǎn)由兩個(gè)指針 (nght 和 left)以及關(guān)鍵字 (key)構(gòu)成， p指向其中某一結(jié)點(diǎn)，編寫一個(gè)函數(shù)從該循環(huán)雙鏈表中刪除 p 所指向的結(jié)點(diǎn)。 【解答】 本題的關(guān) 鍵是找出 p 所指結(jié)點(diǎn)的前后結(jié)點(diǎn)，這可以循環(huán)指針找到。實(shí)現(xiàn)本題功能的函數(shù)如下： struct dlist { int key。 struct dlist *left,*right。 } void delnode(p) struct dlist *p。 { struct dlist *q,*r。 q=p。 while(qright!=p)q=qright。 r=p。 while(rleft!=p)r=rleft。 qright=r。 rleft=q。free(p)。 } while(rleft!=p)r=rleft。 qright=r。 rleft=q。free(p)。 } 5. 已知一個(gè)順序表Ａ中的元素按值非遞減有序，編寫一個(gè)函數(shù)插入一個(gè)元素Ｘ后保持該順序表是有序的 【解答】 define MAX 100 typedef int vector[MAX] void insert(vector A,int n,x) { int,j。 if(x=A[n])A[n+1]=x。 else { i=1。 while(x=A[i])i++。 for(j=n。j=i。j)A[j+1]=A[j]。 A[i]=x。 n++。 } } 6. 試寫出后序遍歷二