河南工業(yè)大學(xué)2013軟件工程12級

1、II河劃/ dT上孥2012至2013學(xué)年第2 學(xué)期II數(shù)據(jù)結(jié)構(gòu)試卷A卷7.A. 5B. 6C. 7D. 8已知廣義表為A（a,b,c）,（d,e,f）,從A中取出原子e的運(yùn)算是（）。A. Tail(Head(A)B. Head(Tail(A)C.Head(Tail(Head(Tail(A) D.Head(Head(Tail(Tail(A):號學(xué)復(fù)查總分:8.9.所有答案必須寫在答題紙上10.對于具有e條邊的無向圖，它的鄰接表中共有（）個邊結(jié)點(diǎn)。A. e-1B. e+1C.2eD. 3e已知一個有向圖的鄰接矩陣表示，A.將鄰接矩陣的第i行刪除C.將鄰接矩陣的第i列刪除要刪除所有從第i個結(jié)點(diǎn)發(fā)出

2、的邊，應(yīng)該：（）。B.將鄰接矩陣的第i行元素全部置為0D.將鄰接矩陣的第i列元素全部置為0在順序表（3, 6, 8,10,12,15,16,18, 21, 25, 30 ）中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：（）。:名姓一、選擇題（共15題，每小題1分，共15分） 1.下列關(guān)于線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)的結(jié)點(diǎn)地址說法正確的是（）。A.前者一定連續(xù)，后者一定不連續(xù)B.兩者可連續(xù)可不連續(xù)C. 前者一定連續(xù)，后者不一定連續(xù)H前者不一1連續(xù)！后者一定連續(xù)11.12.2.在一個單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在它們之間插入結(jié)點(diǎn)s，則執(zhí)行（）。A. s一next = p一next

3、; p一next = s;C. pnext = snext; snext = p;A.2B.3C. 4D. 5假設(shè)以第一個元素為樞軸，則第一次劃分的結(jié)果是：（對字符序列）。A. (A, C, D, F, H, M, P, Q, R, S, X, Y)C.(F, H, C, D, P, A, M, Q, R, S, Y, X)一個棧的入棧順序是1、2、3、4、5，A. 5、 4、 3、 2、 1B.(Q, H, C, Y, P, A, M, S, R, D, F, X)進(jìn)行快速排序，B. (A, F, H, C, D, P, M, Q, R, S, Y X)D.(P, A, M, F, H, C

4、, D, Q, S, Y, R, X)則此棧不可能的輸出順序為（）。4、 5、 3、 2、 1B. pnext = s; snext = q;D. q一next = s; s一next = p;13.C.4、3、5、1、2D.1、2、3、4、5在長為n的順序表中，刪除第i個元素（1MiMn+1）需要向前移動（）個元素。.級班業(yè)專3.4.II5設(shè)有兩個串t和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做（）。A.求子串B.模式匹配C.串替換D.串連接在循環(huán)隊列中用數(shù)組A0.m-1存放隊列元素，其隊頭和隊尾指針分別為front和rear，則當(dāng)1前隊列中的元素個數(shù)是（A.（front - rear + 1）

5、 % mC(front - rear + m) % m卜面程序段的時間復(fù)雜度為）。B. (rear - front + 1) % mD(rear - front + m) % m）。A. n-iB. n-i+1C.n-i-1D.i14.卜面是三個關(guān)于有向圖運(yùn)算的敘述：（）。（1）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果必定是唯一的（2）求兩個指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個（些）是正確的？（）。A.只有（1）B. (1)和(2)C.都正確D.都不正確稱名院學(xué)for(int i=0; im; i+)for(int j=0; jn; j+)A.

6、O(m2)B. O(n2)aij = i*j；C. O(m*n)DO(m+n)15已知一棵完全二叉樹中共有768個結(jié)點(diǎn)，則該樹中共有（）個葉子結(jié)點(diǎn)。A383B384C385D3866一棵具有35個結(jié)點(diǎn)的完全二叉樹的高度為（）。假定空樹的高度為-1。二、判斷題（共10題，每小題1分，共10分）（敘述正確的打心錯誤的打X）1.當(dāng)向一個最小堆插入一個具有最小值的元素時，需要將該元素逐層向上調(diào)整直至到到堆頂位置為止。（）IF料牛牛游甲圖適合于鄰接矩陣作為存儲結(jié)構(gòu)。（）哈希查找法中處理沖突問題的解決方法最常用的一般是除留余數(shù)法。（）在一棵二叉樹中，若每個結(jié)點(diǎn)都只有左孩子而無右孩子，則對其進(jìn)行中序遍歷和后

7、序遍歷 所得到的序列相同。（）在順序表中，邏輯上相鄰的兩個元素在物理位置上不一定相鄰。（）:號在二叉樹中，若某個結(jié)點(diǎn)只有一棵子樹，此時把該子樹看成左子樹或者右子樹都是一樣的。密 （）1 1仙一品人品匾揶志多條關(guān)鍵路徑，只要通過提高其中一條關(guān)鍵路徑上的關(guān)鍵活動速度， 請就能導(dǎo)致整個工程縮短工期。（）不 8.在線索二叉樹中，通過線索可以找到任意結(jié)點(diǎn)的前驅(qū)和后繼。（）要 9.赫夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點(diǎn)距離根結(jié)點(diǎn)一般較近。（）名10.在一個有向圖中，所有結(jié)點(diǎn)的入度之和等于所有結(jié)點(diǎn)的出度之和。（）在三、應(yīng)用題（共6題，共55分）密封 1. （12分）對于給定的5個權(quán)值W=9, 5,

8、13, 3, 6,請構(gòu)造其對應(yīng)的一顆Huffman樹；并 墨曷用勺妙又路彳4 V沽以及各結(jié)點(diǎn)的Huffman編碼。線2.（10分）已知一顆二叉樹的先序遍歷序列和中序遍歷序列分別為ABEFIJDGH和EBIFJAGDH.內(nèi) 要求：（1）畫出該二叉樹；（2）寫出該二叉樹的后序遍歷序列級班業(yè)專答 3. （6分）使用普里姆算法構(gòu)造出下圖的最小生成樹，要求畫出中間步驟。稱名院學(xué)4. （10 分）已知一組關(guān)鍵字（19,14,23,1,68,20,24）,哈希函數(shù)為：H（key）=key MOD 13,哈希 表長m=16,假設(shè)每條記錄查找概率相等，用線性探測再散列法處理沖突，構(gòu)造出哈希表并給 出平均查找長度

9、ASLO5. （10分）求下圖的關(guān)鍵路徑，要求寫出求解的過程。開 始 頂占八、al0=27U 成 頂 占八、6. （7 分）已知待排序的關(guān)鍵字序列為（100, 56, 160, 75, 230, 140, 180, 65, 98, 880）, 請畫出根據(jù)以上序列建立一個大頂堆的過程及結(jié)果。四、算法設(shè)計題（共2題，每小題10分，共20分）1.已知帶頭結(jié)點(diǎn)的單鏈表L,要求：編寫一個帶頭結(jié)點(diǎn)的單鏈表的逆置算法，即將原表中的第 一個結(jié)點(diǎn)逆置后變成最后一個結(jié)點(diǎn)，原表中第二個結(jié)點(diǎn)變成倒數(shù)第二個結(jié)點(diǎn)，依次類推，直至 將原表中的最后一個結(jié)點(diǎn)變成第一個結(jié)點(diǎn)。單鏈表的類型定義如下。typedef struct LNode ElemType data;struct LNode *next; LNode,