數(shù)據(jù)結(jié)構(gòu)模擬題.

1、數(shù)據(jù)結(jié)構(gòu)模擬題( 5)一、填空題1 、 的結(jié)點數(shù)為2 、:06 分，每題 02 分一棵樹的廣義表表示為 a(b(c,d(e,f),g(h),i(j,k(x,y) ，結(jié)點 k 的所有祖先 個。在一棵 AVL 樹中，每個結(jié)點的左子樹高度與右子樹高度之差的絕對值不超過 。3、 二、單選題 4 、在 n(n >0) 個頂點的連通無向圖中所有頂點的度數(shù)之和最少為 。:10 分，每題 02 分一個記錄 r 理論上占有的存儲空間的大小等于所有域類型長度之和，實際上占有的存儲空間的大小即記錄長度為 ( )A:所有域長度之和B:最大域所占字節(jié)長度C:D:siz任意一個域長度 eof(r) 的值5 、A:將

2、遞歸求解過程改變?yōu)榉沁f歸求解過程的目的是( )。 提高速度B:改善可讀性C:增強健壯性D:提高可維護性6 、對長度為 n 的單鏈有序表，若搜索每個元素的概率相等，則搜索任一元素的搜索成功的平均搜索長度為 ( ) A:n/2B:(n+1)/2C:(n-1)/2D:n/47 、 A:圖的深度優(yōu)先搜索類似于樹的( )次序遍歷。 先根B:中根C:后根D:層次8 、A:0B:1C:3D:4在 10 階 B 樹中根結(jié)點所包含的關(guān)鍵碼個數(shù)最少為( )。三、判斷題 :10 分，每題 01 分9 、 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為兩大類：線性結(jié)構(gòu)和非線性結(jié)構(gòu)10 、如果采用如下方式定義一維字符數(shù)組：const

3、 int maxSize = 30;char amaxSize; 則這種數(shù)組在程序執(zhí)行過程中不能擴充。11 、 在對雙向循環(huán)鏈表做刪除一個結(jié)點的操作時，應(yīng)先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點鏈接好再執(zhí)行釋放結(jié)點操作。12 、 每次從隊列中取出的是具有最高優(yōu)先權(quán)的元素 , 這種隊列就是優(yōu)先級隊列。13 、 進行折半搜索的表必須是順序存儲的有序表。14 、 假定有兩個用單鏈有序表表示的集合，則這兩個集合的交運算可得到一個新的 集合單鏈表，其長度小于等于參加運算的任意一個集合單鏈表的長度。15 、 用邊表示活動的網(wǎng)絡(luò)( AOE 網(wǎng))的關(guān)鍵路徑是指從源點到終點的路徑長度最長 的路徑。16 、 對于 AO

4、E網(wǎng)絡(luò)，任一關(guān)鍵活動延遲將導(dǎo)致整個工程延遲完成。17 、 圖中各個頂點的編號是人為的，不是它本身固有的，因此可以根據(jù)需要進行改 變。18 、 圖的廣度優(yōu)先搜索算法通常采用非遞歸算法求解。四、中型計算題 :10 分，每題 10 分19 、 假定一個大根堆為 (64,38,55,20,15,44,18,12) ，則從中刪除一個元素后得到 的堆為五、小型計算題 :40 分，每題 08 分20 、 設(shè)有一個二維數(shù)組 A1020 ，按行存放于一個連續(xù)的存儲空間中， A00 的存儲地址是 200，每個數(shù)組元素占 1 個存儲字，則 A62 的地址是多少。21、假定一組記錄為 (40,28,16,56,50,

5、32,30,63)，按次序插入每個結(jié)點生成一棵 AVL樹，根據(jù)插入過程填寫下表， 在相應(yīng)位置填寫所需要的調(diào)整類型： “左單旋轉(zhuǎn)” 、“右單旋轉(zhuǎn)” 、 “先左后右雙旋轉(zhuǎn)” 、“先右后左雙旋轉(zhuǎn)” ，若不需要旋轉(zhuǎn)則填寫“無” 。22 、 已知一個圖的頂點集 V 和邊集 G分別為：V=1,2,3,4,5,6;E=<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,6,5> 假定該圖采用鄰接表表示，每個頂點鄰接表中的邊結(jié)點都是按照終點序

6、號(即 dest 域的值)從大到小的次序鏈接的，試按照遍歷算法寫出：(1)從頂點 1 出發(fā)進行深度優(yōu)先搜索所得到的頂點序列；(2)從頂點 1 出發(fā)進行廣度優(yōu)先搜索所得到的頂點序列。23 、已知一個 AOE網(wǎng)絡(luò)的頂點集 V 和邊集 G 分別為：V=0,1,2,3,4,5;E=<0,1>2,<0,2>15,<1,3>12,<1,4>9,<2,1>4,<2,4>11,<3,5>5,<4,5>10; 若存儲它采用鄰接表，則按主教材中介紹的求關(guān)鍵路徑的方法，依次寫出所 有的關(guān)鍵活動 (用邊表示) ，并求出關(guān)鍵

7、路徑長度 (提示： 先畫出對應(yīng)的圖形， 然后再運算) 。 所有關(guān)鍵活動： 關(guān)鍵路徑長度24 、設(shè)散列表的長度 m=11，散列函數(shù)為 H(K)=K modm ， 采 用 線 性 探 查 法 解 決 沖 突 ， 被 依 次 插 入 的 關(guān) 鍵 碼 序 列 為 1,13,12,34,38,33,27,22 。根據(jù)構(gòu)成的散列表回答：(1)在等概率的情況下，搜索成功時的平均搜索長度；(2)在等概率的情況下，搜索失敗時的平均搜索長度。六、綜合題 :20 分，每題 10 分寫出下列程序段的輸出結(jié)果 :void main() stack S;char x,y;S.InitStack( );X='c&#

8、39;y='k'S.Push(x); S.Push('a'); S.Push(y);S.Pop(S,x); S.Push('t'); S.Push('s');While(!S.IsEmpty() S.Pop(y); cout<<y;Cout<<y<<endl;/main運行結(jié)果：26 、已知二叉樹中的結(jié)點類型 BinTreeNode 定義為 :struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中 data 為結(jié)點值域， left 和 right 分別為指向左、右子女結(jié)點的指針域。下面函 數(shù)的功能是從二叉樹 BT中查找值為 X 的結(jié)點，若查找成功則返回結(jié)點地址，否則返回空。 請在劃有橫線的地方填寫合適內(nèi)容。BinTreeNode* BTF(BinTreeNode* BT, ElemType x)if(BT=NULL) _(1);else if( BT->data=x) _(2);else BinTreeNode* t;if(t=