廣東工業(yè)大學(xué)2015數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題剖析

1、考試題型：選擇題、填空題、簡(jiǎn)答題、算法填空、算法設(shè)計(jì)、附加題第一章緒論1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是 _ 答案： CB. 數(shù)據(jù)類型D.數(shù)據(jù)變量A. 數(shù)據(jù)項(xiàng)C.數(shù)據(jù)元素2. 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系被稱為 _B. 數(shù)據(jù)的基本操作D. 數(shù)據(jù)的邏輯結(jié)構(gòu)C.程序的算法A. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3. 在定義 ADT 時(shí)，除數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系外，還需說明 _A. 數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)C.基本操作B. 算法4. 抽象數(shù)據(jù)類型的三個(gè)組成部分分別是：數(shù)據(jù)對(duì)象， _數(shù)據(jù)關(guān)系 _，基本操作。第二章線性數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)1.1.對(duì)定義“ int a2 ；”的正確描述是（）。A 、定義一維數(shù)組a，包含 a1 和 a2

2、兩個(gè)元素B、定義一維數(shù)組a，包含 a0 和 a1 兩個(gè)元素C、定義一維數(shù)組a，包含 a0 、 a1 和 a2 三個(gè)元素D、定義一維數(shù)組a，包含 a(0)、 a(1)和 a(2)三個(gè)元素2. 具有后進(jìn)先出特點(diǎn)的結(jié)構(gòu)是 _。A ） 棧B ） 隊(duì)列C） 線性表D） 數(shù)組3. 具有先進(jìn)先出特點(diǎn)的結(jié)構(gòu)是 _。A ） 棧B ） 隊(duì)列C） 線性表D） 數(shù)組第三章線性結(jié)構(gòu)的順序存儲(chǔ)和實(shí)現(xiàn)1. 已知棧 S = (l , b , c , y) ，Pop( S,e )操作之后棧 S 的結(jié)果是 _。答案示例 ： (a,b,c)或 ()2.已知棧 S = (u,b,m,k,v)，Push( S, c )操作之后棧 S

3、的結(jié)果是 _。答案示例： (a,b,c)或 ()3. 用 S 表示入棧操作， X 表示出棧操作，若元素入棧的順序是 (d,l,g,k,a)，為了得到 (d,g,l,k,a)出棧序列，用相應(yīng)的S 和 X 表示的操作串為 _。答案示例： SSXXS4. 3.1.5、用 S 表示入棧操作， X 表示出棧操作， 若元素入棧的順序是 (e,n,d,c,z)，為了得到 (d,z,c,n,e)出棧序列，用相應(yīng)的S 和 X 表示的操作串為 _。答案示例： SSXXS5. 3.2.1、已知隊(duì)列 Q = (q,v,d,m,e,c)，EnQueue( Q, y )操作之后隊(duì)列 Q 的結(jié)果是_。答案形式：（ a,b）

4、6. 若用一個(gè)長(zhǎng)度為 7 的數(shù)組來表示循環(huán)隊(duì)列， 且當(dāng)前 front 和 rear 的值分別是 0和 1 則該隊(duì)列的長(zhǎng)度是 _。7. 若用一個(gè)長(zhǎng)度為 6 的數(shù)組來表示循環(huán)隊(duì)列， 且當(dāng)前 front 和 rear 的值分別是 1和 3 當(dāng)從隊(duì)列中刪除 2 個(gè)元素，再加上 4 個(gè)元素后， rear 和 front 的值分別為_和 _。8. 以下操作不屬于隊(duì)列的操作是： _B. 構(gòu)造空隊(duì)列A. 隊(duì)尾添加一個(gè)元素D. 刪除隊(duì)列中部的元素9. 在隊(duì)列中，允許進(jìn)行插入操作的一端稱為 _A. 隊(duì)首B. 隊(duì)尾D. 棧底10. 一個(gè)棧的入棧序列是 a,b,c,d,e，則棧的不可能的輸出序列是 _A.edcbaB

5、.decbaD.abcdeC.dceab11. 下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？ _B. 插入運(yùn)算方便A. 存儲(chǔ)密度大C.刪除運(yùn)算方便D. 可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示12. 線性表是一種邏輯結(jié)構(gòu)，下面的的敘述中哪一個(gè)是錯(cuò)誤的？_A. 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。D. 線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。B. 線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。13. 若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。_D. 單循環(huán)鏈表B. 雙鏈表A. 順序表C.帶頭

6、結(jié)點(diǎn)的雙循環(huán)鏈表第四章線性結(jié)構(gòu)的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn)1. 如果用不帶頭結(jié)點(diǎn)的鏈表表示隊(duì)列，則在做刪除元素操作時(shí)， （）_B. 僅修改尾指針C.頭尾指針都要修改D. 僅將被刪除元素結(jié)點(diǎn)的next 域置為 nullA. 僅修改頭指針2. 鏈?zhǔn)綄?shí)現(xiàn)中隊(duì)列為空時(shí)， front 和 rear 指針是否可以相等： _C.不清楚D. 以上都不A. 可以相等B. 不可以相等3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中是否存在“空間已滿”的情況？ _A. 存在C.不一定B. 不存在第五章排序基礎(chǔ)1. 基數(shù)排序的時(shí)間復(fù)雜度是 _C.O(nlog n)D.O(d(n+rd)B.O(log n)A.O(n*n)2. 對(duì)序列 74,29,58,6

7、3,90,98,41執(zhí)行升序的簡(jiǎn)單插入算法， 寫出排序中各趟的結(jié)果是 _。3. 對(duì)序列 13,25,96,76,75,47,8執(zhí)行降序的希爾排序算法， 增量序列為（ 5，3，1），寫出排序中各趟的結(jié)果是 _。4.5.插入排序算法是（穩(wěn)定或不穩(wěn)定）_的排序算法。給定關(guān)鍵字序列 483， 35，126，86， 678，257， 513，750， 680， 226，執(zhí)行三趟希爾排序，設(shè)增量序列為5,3,1 ，請(qǐng)依次寫出每一趟的排序結(jié)果。第六章哈希表1. 設(shè)哈希表長(zhǎng) m=14，哈希函數(shù) H(key)=key%11。表中已有 4 個(gè)結(jié)點(diǎn)： addr (15)=4; addr (38)=5; addr (

8、61)=6; addr (84)=7；如用二次探測(cè)再散列處理沖突， 關(guān)鍵字為 49 的結(jié)點(diǎn)的地址是 _。A.8D.9C.5B.32. 解決散列法中出現(xiàn)的沖突問題常采用的方法是 _B. 數(shù)字分析法、除余法、線性探測(cè)法C.數(shù)字分析法、線性探測(cè)法、多重散列法D. 線性探測(cè)法、多重散列法、鏈地址法A. 數(shù)字分析法、除余法、平方取中法3. 設(shè)哈希函數(shù)為 H(k)=key MOD 7，用線性探測(cè)法處理沖突。請(qǐng)畫出依次插入元素 81， 80，6，83，7， 13，45 后，該哈希表的狀態(tài)，在各元素下面標(biāo)出其沖突次數(shù)，并求出等概率情況下查找成功的 平均查找長(zhǎng)度 是 _。 (若平均長(zhǎng)度小數(shù)超過兩位，請(qǐng)保留兩位！

9、 )4. 設(shè)哈希函數(shù)為 H(k)=key MOD 7，用二次探測(cè)法處理沖突。請(qǐng)畫出依次插入元素 1，71， 99，20，9， 27，75 后，該哈希表的狀態(tài)，在各元素下面標(biāo)出其沖突次數(shù)，并求出等概率情況下查找成功的平均查找長(zhǎng)度是 _。5. 將關(guān)鍵字序列： (19,14,1,29,20,23,57,11,10)，存入用數(shù)組 A0.12 實(shí)現(xiàn)的哈希表(見下表 )，設(shè)哈希函數(shù)為： H0= key MOD 11 ，按線性探測(cè)再散列法處理沖突： Hi=(H0+di ) MOD 13 。要求：(1) 填寫關(guān)鍵字序列的存儲(chǔ)情況；0123456789101112(2) 請(qǐng)寫出在哈希表 A 中查找給定值 K=5

10、7 的過程中，所求得的哈希地址序列。第七章遞歸1. 在有 5 個(gè)互不相同元素的有序表 A1. 5中折半查找值等于 A1 的元素，被比較的元素的下標(biāo)依次為 _。2. 在序列 2, 5, 8, 11, 18 , 23, 31, 39, 46, 55, 79, 92, 99中，用折半查找（二分查找）算法查找是否存在關(guān)鍵字 13，寫出相應(yīng)的各趟結(jié)果。并寫出以 C 語言描述的完整算法，測(cè)試通過3. 在對(duì)長(zhǎng)度為 7 的有序表進(jìn)行折半查找， 其等概率時(shí)查找成功的平均查找長(zhǎng)度是_。結(jié)果保留三位有效數(shù)字4. 對(duì)序列 31,35,19,34,77,30,0 執(zhí)行升序的歸并排序，寫出三次調(diào)用過程 Merge的排序結(jié)

11、果是 _。5. 歸并排序算法的平均時(shí)間復(fù)雜度是 _，最壞情況時(shí)間復(fù)雜度是 _，輔助存儲(chǔ)空間是 _。6. 對(duì)序列 46,19,47,12,35,23,7, 1, 99, 62, 57, 86執(zhí)行升序的一趟快速排序，設(shè)其中第一個(gè)元素 46 為樞軸，寫出一趟快速排序結(jié)果是_。并寫出以 C 語言描述的完整算法，測(cè)試通過7. 對(duì)序列 35,20,88,6,54,60,80執(zhí)行升序的快速排序， 寫出三次調(diào)用過程 Partition的排序結(jié)果是 _。8. 快速排序算法的平均時(shí)間復(fù)雜度是 _，最壞情況時(shí)間復(fù)雜度是 _，輔助存儲(chǔ)空間是 _。9. 某內(nèi)排序方法的穩(wěn)定性是指 _B.該排序算法允許有相同的關(guān)鍵字記錄A

12、. 該排序算法不允許有相同的關(guān)鍵字記錄C.平均時(shí)間為0（ n log n ）的排序方法D.執(zhí)行排序算法之后，相等的關(guān)鍵字的原有位置順序不變。10. 針對(duì)下述快速排序算法，請(qǐng)進(jìn)行代碼填空。int Partition (SqList &L,int low,int high)int pivotkey;L.r0 = L.rlow;pivotkey = L.rlow.key;while(_(1)_)while(low=pivotkey)_(2)_;L.rlow = L.rhigh;while(lowhigh&L.rlow.key=pivotkey)_(3)_;L.rhigh = L.rlow;L.rlo

13、w = L.r0;return low;void QSort (RedType & R,int s,intt )if(s 3）B 樹，若不為空樹， 則樹中的每個(gè)結(jié)點(diǎn)至多有 _棵子樹。A.m-1B.mC.m+1D.以上都不是4. 并查集的合并操作所需的時(shí)間主要取決于樹的 _；有兩種方法可優(yōu)化算法效率，分別是 _和_；5.在一棵 m 階 B 樹中，若某結(jié)點(diǎn)的原有關(guān)鍵字個(gè)數(shù)等于_，則插入一個(gè)新關(guān)鍵字將導(dǎo)致該結(jié)點(diǎn)分裂；若某結(jié)點(diǎn)及相鄰兄弟結(jié)點(diǎn)的原有的關(guān)鍵字的個(gè)數(shù)等于 _，則刪除一個(gè)關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并。第十章圖1. 任何一個(gè)帶權(quán)的無向連通圖的最小生成樹 _A. 只有一棵B.有一棵或多棵C.一定有多棵D.

14、 可能不存在2. 具有 N 個(gè)頂點(diǎn)的無向圖至多有（）條邊。 _A. NB. N*(N 1)C. N*(N 1)/2D. 2N3. 有 n 個(gè)頂點(diǎn)的無權(quán)無向圖 , 采用鄰接數(shù)組表示 , 圖中的邊數(shù)與鄰接矩陣中非零元素之和的關(guān)系是 _A.1 / 2B. 相等C.2 倍D. 不確定4. 不帶權(quán)的有向圖中頂點(diǎn) V i 的度等于其鄰接矩陣中 _；A .第 i 行中的非0 元的個(gè)數(shù)；B. 第 i 列中的非 0 元的個(gè)數(shù)；C. 第 i 行中的非 0 元的個(gè)數(shù) + 第 i 列中的非 0 元的個(gè)數(shù)；D. 不能確定5. 已知無向圖 G 如圖所示，從頂點(diǎn) A 開始，分別寫出深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。6.

15、包含 8 個(gè)頂點(diǎn)的連通圖的生成樹有 _個(gè)頂點(diǎn)， _條邊。7. 已知某無向圖對(duì)應(yīng)的鄰接矩陣如下所示， 可得該圖有 _個(gè)頂點(diǎn) , _條邊，其中頂點(diǎn) E 的度是 _。8.已知某有向圖對(duì)應(yīng)的鄰接矩陣如下所示，可得該圖有_個(gè)頂點(diǎn) _條邊，其中頂點(diǎn) F 的出度是 _，入度是 _，度是 _。9. 已知圖 G 如圖所示，其對(duì)應(yīng)的鄰接表共有 _個(gè)頭結(jié)點(diǎn)， _個(gè)表結(jié)點(diǎn)。10. 已知某圖的鄰接矩陣如圖所示，從頂點(diǎn)A 出發(fā)對(duì)圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列為 _。從頂點(diǎn) A 出發(fā)對(duì)圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列為 _。分別寫出 DFS 和 BFS 用 C 語言描述的算法。11. 已知某圖的鄰接表如圖所示， 從頂點(diǎn) A 出發(fā)對(duì)圖進(jìn)行廣度優(yōu)先搜索， 得到的頂點(diǎn)序列為