1、。裝。訂。線。2011 年2012 年第 2 學期 信科 10 級數(shù)據(jù)結(jié)構(gòu)時間共 120 分鐘試卷 A 卷一、填空題（每題 1 分，共 15 分）1.數(shù)據(jù)結(jié)構(gòu)課程的主要內(nèi)容是數(shù)據(jù)的結(jié)構(gòu)、結(jié)構(gòu)以及它們之間的關(guān)系。2若頻繁地對線性表進行與刪除操作，該線性表應(yīng)采用結(jié)構(gòu)。棧的特點是 ，隊列的特點是。對于二維數(shù)組 floata54，計算：若數(shù)組 a 的起始地址為 2000，且每個數(shù)組元素長度為 4 個字節(jié)，數(shù)組元素 a32 的內(nèi)存地址為。深度為K 的二叉樹最多含有個結(jié)點，最少含有個結(jié)點。6稀疏矩陣一般采用方法進行壓縮。對廣義表A=（a,(b),c,d)）的運算：head(head(tail (A)的值是

2、。在哈希表中的查找中，評判一個哈希函數(shù)優(yōu)劣的兩個主要條件是和。9如果從一無向圖的任意頂點出發(fā)進行一次深度優(yōu)先搜索即可所有頂點，則該圖一定是 。10向一棵二叉排序樹中一個元素時，若元素的值小于根結(jié)點的值，則應(yīng)把它到根結(jié)點的上。11在一棵 AVL 樹中，每個結(jié)點的樹高度與右子樹高度之差的絕對值不超過。二、單向選擇題（每題 1 分，共 15 分）1計算機識別、A數(shù)據(jù)和加工處理的對象被統(tǒng)稱為。B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型2從一個長度為 n 的順序表中刪除第 i 個元素（1in），需向前移動個元素。A、 n-iB、n-i+1C、 n-i-1D i3設(shè)線性表最常用的操作是存取指定序號的元素，則采用

3、結(jié)構(gòu)最節(jié)省時間。A.順序表B.單鏈表C.雙鏈表D.結(jié)點的循環(huán)鏈表4堆的形狀是一棵。A.二叉排序樹B.滿二叉樹C.完全二叉樹D.平衡二叉樹5在一個鏈隊列中，假定 front 和 real 分別為隊頭和隊尾指針，則*s 結(jié)點的操作應(yīng)執(zhí)行。real=s; front=s;A、front-next=s;C、real-next=s;front=s;real=s;B、s-next=real;D、s-next=front;6帶權(quán)有向圖 G 用鄰接矩陣 A，則頂點 i 的出度等于 A 中。A.第i 行非無窮元和B.第iD.第I無窮元和C.第i 行非零且非無窮元素個數(shù)零且非無窮元素個數(shù)7由兩個棧共個向量空間的好

4、處是。A.減少存取時間,降低下溢發(fā)生的機率C.減少存取時間,降低上溢發(fā)生的機率B.節(jié)省D.節(jié)省空間,降低上溢發(fā)生的機率空間,降低下溢發(fā)生的機率8二叉樹中第 5 層上的結(jié)點個數(shù)最多為A.8B.15C.16D.329設(shè)串 S1=ABCDEFG,S2=PQRST,則運算 S=CONCAT（SUB（S1,2,LENGTH（S2）,SUB（S1，LENGTH（S2），）后結(jié)果為。A.BCQRB.BCDEFEFC.CDEFGD.BCDEF10棧與一般的線性表的區(qū)別在于()。得分閱卷人得分閱卷人題號12345678910總分得分閱卷人A、數(shù)據(jù)元素的類型不同B、運算是否受限制 C、數(shù)據(jù)元素的個數(shù)不同 D、邏輯

5、結(jié)構(gòu)不同11已知廣義表的表頭為 A，表尾為(B,C)，則此廣義表為A.（A,(B,C)）B.（A,B,C）C. (A,B,C)D.( A,B,C)12在中序線索二叉樹中，若某結(jié)點有右孩子，則該結(jié)點的直接后繼是。A.樹的最右下結(jié)點B.右子樹的最右下結(jié)點C.樹的最左下結(jié)點D.右子樹的最左下結(jié)點13快速排序在情況下失去其優(yōu)越性? A.被排序數(shù)據(jù)中含有多個相同排序碼C.被排序數(shù)據(jù)完全無序B.被排序數(shù)據(jù)已基本有序D.被排序數(shù)據(jù)中最大值和最小值相差懸殊14當執(zhí)行函數(shù)調(diào)用時，其局部變量的一般采用進行C、棧結(jié)構(gòu)。D、隊列結(jié)構(gòu)A、樹型結(jié)、靜態(tài)鏈表15. 用折半法進行查找時，要求線性表是。A順序表B.單鏈表C.順

6、序且有序D.有序表三、判斷題（每題 1 分，共 10 分）1靜態(tài)鏈表既有順序的優(yōu)點，又有動態(tài)鏈表的優(yōu)點，所以它存取表中第 i 個元素的時間與 i 無關(guān)。（）2不管棧采用何種結(jié)構(gòu)，只要棧不空，可以任意刪除一個元素。 （）3在求網(wǎng)的最小生成樹時，姆算法適用于稠密網(wǎng)，而算法使用于稀疏網(wǎng)。（）4一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。（）5一棵平衡樹一定是一棵二叉排序樹，反之，一棵二叉排序樹也一定是一棵平衡樹。(）6在哈希中,裝填因子a 的值越大,則發(fā)生的可能性就越大。（）7鄰接表只能用于有向圖的，鄰接矩陣對于有向圖和無向圖的都適用。（）8若一個有向圖的鄰接矩陣中,對角線以下元素均為 0,則

7、該圖的拓撲有序序列必定存在。（）9先刪除二叉排序樹中一個，再重新該，一定能得到原來的二叉排序樹。（10中序遍歷一棵二叉排序樹，就到結(jié)點的有序序列。（）四、簡答題（共 20 分）1列出你所學過的所有數(shù)據(jù)結(jié)構(gòu)，。（3 分）2簡述算法的五個重要特性。（5 分）3簡述使二叉排序樹由不平衡轉(zhuǎn)化為平衡的 4 個旋轉(zhuǎn)規(guī)則（4 分）4判斷（101, 88, 46, 70, 34, 39, 45, 58, 66, 10）是否為堆？若是，是大頂堆還是小頂堆？（4 分）5簡述拓撲排序的基本。 (4 分)五、應(yīng)用題（共 30 分）、已知一棵二叉樹的中序序列為 DBHEAFICG，先序序列為 ABDEHCFIG，請寫出

8、該二叉樹的后序序列。（4 分）下圖中給出由 7 個頂點組成的無向圖。（4 分）從頂點 1 出發(fā)， 對它進行遍歷，則：深度優(yōu)先遍歷得到的頂點序列是：廣度優(yōu)先遍歷得到的頂點序列是：得分閱卷人得分閱卷人得分閱卷人3給出一組關(guān)鍵字 T=（12，2，16，30，8，28，4，10，20，6，18），寫出用下列算法從小到大排序時第一趟結(jié)束時的序列：（3 分）1）冒泡排序：2）快速排序(選第一個為樞軸(分隔)：4已知線性表 (1，13，12，34，38，33，27，22,) ，采用的哈希函數(shù)為H(Key)=Key mod 11 ，若采用線性探測，構(gòu)造相應(yīng)的哈希表。（6 分）再散列的開放定址法解決012345

9、678910115右圖是一個具有 12 個活動的假想工程的 AOE 網(wǎng)。圖中有 8 個頂點，它們分別表示事件 V1 到 V8，其中 V1 表示工程開始，V8 表示工程結(jié)束，邊上的權(quán)值表示活動所需的時間，求：（）各頂點事件的最早和最遲發(fā)生時間；（）各活動的最早和最遲發(fā)生時間；（）關(guān)鍵活動和關(guān)鍵路徑；(7 分)6假設(shè)用于通訊的電a,b,c,d,e,f,g，h 等 8 個字母組成，字母在電文中出現(xiàn)的頻率分別為 0.03，0.12，0.07，0.04，0.02，0.08，0.11 和 0.10。求：（）畫出樹；（）為這些字母設(shè)計蔓編碼；（）求出帶權(quán)路徑長度。（分）1. 假設(shè)以結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾元素結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的隊列初始化、入隊列和出隊列的算法。要求：a、寫出鏈表的數(shù)