復(fù)習(xí)題.doc(數(shù)據(jù)結(jié)構(gòu)).doc

一、 選擇題一：（） 1、用單鏈表的方式存儲線性表每個節(jié)點需要一個數(shù)據(jù)域和一個（ ）。A.本節(jié)點的地址域 B.指針域 C.空指針域 D.空閑域2、一棵n個節(jié)點的二叉樹其空指針域的個數(shù)是（ ）。A.n B.n+1 C.n-1 D.不能確定3、在隊列棧存取數(shù)據(jù)應(yīng)遵守的原則是（ ）。A.先進先出 B. 先進后出 C.隨意進出 D. 后進先出4、設(shè)有編號為1、2、3、4的四輛列車，順序進入一個棧式結(jié)構(gòu)的站臺，下列不可能的出站順序為（）。A.1234 B.1243 C.1324 D.14235、若4個元素按A、B、C、D順序入隊Q，隊尾元素是（）。A.A B.B C.C D.D6、空串與空白串（）。A.相同 B.不相同 C.可能相同 D.無法確定7、廣義表（A,B,E,F,G）的表尾是（）。A.（B,E,F,G） B.() C. （A,B,E,F,G） D.(G)8、具有3個節(jié)點的樹有（）種不同形態(tài)。A.3 B.4 C.5 D.29、某二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC,則先序遍歷序列為（）。A.ACBED B.DECAB C.DEABC D.CEDBA10、有8個節(jié)點的無向圖最多有（）條邊。A.14 B.28 C.56 D.11211、采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為。A.n B.n/2 C.(n+1)/2 D.(n-1)/212、100個元素采用二分法查找時，最大的比較次數(shù)是（ ）。A.2 B.7 C.4 D.513、下列排序方法中，不屬于插入排序的是（）。A.希爾排序 B.冒泡排序（屬于交換排序） C.直接插入排序 D.二分插入排序14、下述幾種排序方法中，平均查找長度最小的是（）。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序15、指針P指向循環(huán)鏈表L的尾元素的條件是（）。A.P = L B.L-next = P C.P-next = NULL D.P-next = L選擇題一答案題號123456789101112131415答案BBADDBADDBCBBCD選擇題二1、非線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在（ ）。A.一對一關(guān)系 B.一對多關(guān)系 C.多對多關(guān)系 D.B或C2、單鏈表的存儲密度（ ）。A.大于1 B.等于1 C.小于1 D.不能確定3、在線性表中（ ）只有一個直接前驅(qū)和一個直接后繼。A.首元素 B.中間元素 C.尾元素 D.所有元素4、設(shè)有編號為1、2、3、4的四輛列車，順序進入一個棧式結(jié)構(gòu)的站臺，下列不可能的出站順序為（）。A.1234 B.1243 C.1324 D.14235、若4個元素按A、B、C、D順序入隊Q，隊頭元素是（）。A.A B.B C.C D.D6、一個循環(huán)隊列一旦說明，其占用的空間大?。ǎ?。A.已固定 B.可以變動 C.不能固定 D.動態(tài)變化第2 頁 共 8 頁7、若串S = “software”，其子串?dāng)?shù)目是（）。A.8 B.37 C.36 D.98、節(jié)點前序為ABC的不同二叉樹有（）種形態(tài)。A.3 B.4 C.5 D.69、某二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC,則先序遍歷序列為（）。A.ACBED B.DECAB C.DEABC D.CEDBA10、在一個圖中所有頂點的度數(shù)之和等于圖的邊數(shù)的（）倍。A.1/2 B.1 C.2 D.411、查找表是以（）為查找結(jié)構(gòu)的。A.集合 B.圖 C.樹 D.文件12、有一個有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值為82的節(jié)點時，經(jīng)（）次比較后查找成功。A.2 B.3 C.4 D.513、在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排序次序無關(guān)的是（）。A.希爾排序 B.冒泡排序 C.插入排序 D.選擇排序14、下述幾種排序方法中，平均查找長度最小的是（）。A.插入排序 B.選擇排序 C.快速排序 D.歸并排序第 3 頁 共 8 頁15、指針P指向循環(huán)鏈表L的首元素的條件是（）。A.P = L B.L-next = P C.P-next = NULL D.P-next = L選擇題二答案題號123456789101112131415答案DCBDAACCDCACDCB選擇題三1在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為。 A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) 2算法分析的兩個主要方面是。 A空間復(fù)雜性和時間復(fù)雜性 B正確性和簡明性 C. 可讀性和文檔性 D數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 3計算機算法它必具備輸入、輸出和等五個特性。 A可執(zhí)行性、可移植性和可擴充性。 B可執(zhí)行性、確定性和有窮性 C確定性、有窮性和穩(wěn)定性 D易讀性、穩(wěn)定性和安全性 4線性表若采用鏈表存儲結(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址。 A必須是連續(xù)的 B部分地址必須是連續(xù)的 C. 一定是不連續(xù)的 D連續(xù)不連續(xù)都可以 5一個向量第一個元素的存儲地址是100，每個元素的長度為2則第5個元素的地址是。 A110 B。108 C100 D120 6棧和隊列的共同點是。 A都是先進后出 B都是先進先出 C. 只允許在端點處插入和刪除元素 D沒有共同點 7在一單鏈表中，若p結(jié)點不是最后結(jié)點，在p之后插入s結(jié)點，則執(zhí)行。 Asnext：p；pnext：s； Bsnext：pnext；pnext：s； Csnext：pnext；p：s； Dpnext：s；snext：p； 8在一單鏈表中，若刪除p結(jié)點的后續(xù)結(jié)點，則執(zhí)行。 Apnext：pnextnext； Bp：pnext；pnext：pnextnext； Cpnext：=pnext； Dp：pnextnext 9串是一種特殊的線性表，其特殊性體現(xiàn)在。 A可以順序存儲 B數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D數(shù)據(jù)元素可以是多個字符 10結(jié)點數(shù)為N的二叉樹有個空閑指針。 AN BN+1 C2N DN-1 11設(shè)有兩個串s和t，求t在s中首次出現(xiàn)的位置的運算稱作。 A連接 B模式匹配 C求子串 D求串長 12在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊。 A只有右子樹上的所有結(jié)點 B只有右子樹上的部分結(jié)點 C 只有左子樹上的部分結(jié)點 D只有左子樹上的所有結(jié)點 13樹最適合用來表示。 A有序數(shù)據(jù)元素 B無序數(shù)據(jù)元素 C元素之間具有分支層次關(guān)系的數(shù)據(jù) D元素之間無聯(lián)系的數(shù)據(jù) 14一個有n個頂點的無向圖最多有條邊。 An Bn(n一1) Cn(n一1)2 D2n 15在一個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。 An Bn+1 Cn一1 Dn2 16對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是。 An B(n一1) 2 Cn-1 Dn * n 17對線性表進行二分查找時，要求線性表必須。 A以順序方式存儲 B以鏈接方式存儲 C以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序 D以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排序 18采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度ASL為。 An Bn2 C(n+1)2 D(n一1)2 19設(shè)哈希表長m14，哈希函數(shù)H(key)key MOD ll。表中已有4個結(jié)點： addr(15)=4 addr(38)=5 addr(61)6 addr(84)7 其余地址為空 如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是。 A8 B3 C5 D9 20一組記錄的關(guān)鍵碼為(46，79，56，38，40，84)，則利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果為。 A38，40，46，56，79，84 B40，38，46，79，56，84 C40，38，46，56，79，84D40，38，46，84，56，79 選擇題三答案題號1234567891011121314151617181920答案CABDBCBABBBACCCDACDC二、 填空題：（共10小題，每小題2分，共20分） 1數(shù)據(jù)邏輯結(jié)構(gòu)包括、和三種類型，樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為。 2算法的五個重要特性是、。 3下面程序段的時間復(fù)雜度是。 for i：1 to n dO for j：l to n dO Ai,j：0；4棧的特點是，隊列的特點是。 5一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是。6設(shè)有C+定義的二維數(shù)組A68，每個元素占4個字節(jié)，按行優(yōu)先順序存放，A的起始地址為100，則元素A14的地址是，元素A47的地址是 。 7按照二叉樹的定義，具有3個結(jié)點的二叉樹有種。8深度為5的二叉樹至多有個結(jié)點。 9、查找算法按查找表在查找過程中是否可進行插入和刪除操作可分為查找和查找。10、排序算法在排序過程中如果能完全保證排序關(guān)鍵字值相同的記錄在排序前后的次序不變，則稱這類排序算法是的排序算法.反之，如果不能保證排序關(guān)鍵字值相同的記錄在排序前后的次序不變，則稱這類排序算法是的排序算法. 三 判斷題：（共5小題，每小題2分，共10分）1、從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。2、順序存儲的線性表可以實現(xiàn)隨機存取。3、棧是運算受限制的線性表。4、完全二叉樹一定是滿二叉樹。5、圖可以沒有邊但不能沒有頂點。6、在線性表的順序結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)，與該元素的位置有關(guān)。7、隊列是一種“后進先出”的線性表。8、串的長度不能為0。9、對有序表而言，采用二分查找，總比順序查找法速度快。10、快速排序在任何情況下都比其它排序方法速度快。21、算法是對解題方法和步驟的描述。22、單鏈表的每個節(jié)點都恰好包含一個指針域。23、隊是運算受限制的線性表。24、樹結(jié)構(gòu)中每個節(jié)點最多只有一個直接前驅(qū)。25、有向圖不能進行廣度優(yōu)先搜索遍歷。26、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)先與順序存儲結(jié)構(gòu)。27、隊列是一種“后進后出”的線性表。28、串中不可以包含有空白字符。29、二分查找法要求待查表的關(guān)鍵字的值必須是有序的。30、冒泡排序是不穩(wěn)定的排序。31空串與空格串是相同的，這種說法。 A正確 B不正確 32二叉樹的左右子樹的位置總是可以交換的，這個斷言是。 A正確的 B錯誤的 33連通圖一定是完全圖，反之亦然。這個斷言是。 A正確的 B錯誤的 34在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查法方法是哈希查找。A正確的 B錯誤的 35、基數(shù)排序是穩(wěn)定的排序算法。A 正確的 B錯誤的判斷題答案題號12345678910答案TTTFTTFFTF題號21222324252627282930答案TFTTFFFFTF題號3132333435答案FFFTT四、問答題：（10）1、（1）寫出下圖從V1 開始的深度優(yōu)先搜索序列。（2）寫出下圖從V1 開始的廣度優(yōu)先搜索序列； 2、指出樹和二叉樹的主要差別？3、二叉樹遍歷：分別寫出下圖所示二叉樹的前序、中序、后序遍歷序列。（10分） 4、已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11.先畫出赫夫曼樹的示意圖，再根據(jù)該樹依次寫出這8種字符的赫夫曼編碼。 5、給定一個權(quán)集W=4,5，7,8,6,12,18，請畫出相應(yīng)的哈夫曼樹，并計算其帶權(quán)路徑長度。6、已知一棵二叉樹的先序序列與中序序列分別為： 先序序列： A B C D E F G H I 中序序列： B C A E D G H F I試恢復(fù)該二叉樹。并寫出它的的后序遍歷序列。7、已知一個無向圖的頂點集為a,b,c,d,e,其鄰接矩陣如下： 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0畫出該圖的圖形。根據(jù)鄰接矩陣寫出從a出發(fā)進行深度優(yōu)先搜索遍歷的序列。8、設(shè)棧S中的數(shù)據(jù)是：2 4 6 8，寫出當(dāng)e=4時運行下列函數(shù)后棧S中的數(shù)據(jù)。void algo2(SqStack *S,int e)/利用輔助棧T刪除S棧中的元素SqStack *T;int d;StackInitiate (T);while(StackNotEmpty(S)Pop(S,&d);if(d!=e) Push(T,d);while(StackNotEmpty(T)Pop(T,&d);Push(S,d);五、編程題：（10分）1、 用C語言寫出快速排序算法。2、 用C語言寫出二分查找算法。3、寫出順序表的插入、刪除函數(shù)4、寫出鏈表的插入、刪除函數(shù)5、寫出直接插入排序函數(shù)6、寫出鏈隊的出隊