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

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

2、遞歸求解過程改變?yōu)榉沁f歸求解過程的目的是( )。 提高速度B:改善可讀性C:增強(qiáng)健壯性D:提高可維護(hù)性6 、對(duì)長(zhǎng)度為 n 的單鏈有序表，若搜索每個(gè)元素的概率相等，則搜索任一元素的搜索成功的平均搜索長(zhǎng)度為 ( ) 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é)點(diǎn)所包含的關(guān)鍵碼個(gè)數(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í)行過程中不能擴(kuò)充。11 、 在對(duì)雙向循環(huán)鏈表做刪除一個(gè)結(jié)點(diǎn)的操作時(shí)，應(yīng)先將被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鏈接好再執(zhí)行釋放結(jié)點(diǎn)操作。12 、 每次從隊(duì)列中取出的是具有最高優(yōu)先權(quán)的元素 , 這種隊(duì)列就是優(yōu)先級(jí)隊(duì)列。13 、 進(jìn)行折半搜索的表必須是順序存儲(chǔ)的有序表。14 、 假定有兩個(gè)用單鏈有序表表示的集合，則這兩個(gè)集合的交運(yùn)算可得到一個(gè)新的 集合單鏈表，其長(zhǎng)度小于等于參加運(yùn)算的任意一個(gè)集合單鏈表的長(zhǎng)度。15 、 用邊表示活動(dòng)的網(wǎng)絡(luò)( AOE 網(wǎng))的關(guān)鍵路徑是指從源點(diǎn)到終點(diǎn)的路徑長(zhǎng)度最長(zhǎng) 的路徑。16 、 對(duì)于 AO

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

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

6、號(hào)(即 dest 域的值)從大到小的次序鏈接的，試按照遍歷算法寫出：(1)從頂點(diǎn) 1 出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點(diǎn)序列；(2)從頂點(diǎn) 1 出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點(diǎn)序列。23 、已知一個(gè) AOE網(wǎng)絡(luò)的頂點(diǎn)集 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; 若存儲(chǔ)它采用鄰接表，則按主教材中介紹的求關(guān)鍵路徑的方法，依次寫出所 有的關(guān)鍵活動(dòng) (用邊表示) ，并求出關(guān)鍵

7、路徑長(zhǎng)度 (提示： 先畫出對(duì)應(yīng)的圖形， 然后再運(yùn)算) 。 所有關(guān)鍵活動(dòng)： 關(guān)鍵路徑長(zhǎng)度24 、設(shè)散列表的長(zhǎng)度 m=11，散列函數(shù)為 H(K)=K modm ， 采 用 線 性 探 查 法 解 決 沖 突 ， 被 依 次 插 入 的 關(guān) 鍵 碼 序 列 為 1,13,12,34,38,33,27,22 。根據(jù)構(gòu)成的散列表回答：(1)在等概率的情況下，搜索成功時(shí)的平均搜索長(zhǎng)度；(2)在等概率的情況下，搜索失敗時(shí)的平均搜索長(zhǎng)度。六、綜合題 :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運(yùn)行結(jié)果：26 、已知二叉樹中的結(jié)點(diǎn)類型 BinTreeNode 定義為 :struct BinTreeNode ElemType data; BinTreeNode *left, *right;其中 data 為結(jié)點(diǎn)值域， left 和 right 分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函 數(shù)的功能是從二叉樹 BT中查找值為 X 的結(jié)點(diǎn)，若查找成功則返回結(jié)點(diǎn)地址，否則返回空。 請(qǐng)?jiān)趧澯袡M線的地方填寫合適內(nèi)容。BinTreeNode* BTF(BinTreeNode* BT, ElemType x)if(BT=NULL) _(1);else if( BT->data=x) _(2);else BinTreeNode* t;if(t=