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

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