【正文】 別時(shí)（ A ）A、 7,1 B、6,1 C、5,1 D、8,1第九章 排序1. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在 （A ） 情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列 B．按排序碼值從大到小排列C．隨機(jī)排列(完全無序) D．基本按排序碼值升序排列3. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初始序列在 （A） 情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列 B．按排序碼值從大到小排列C．隨機(jī)排列(完全無序) D．基本按排序碼值升序排列5. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法在 （C） 情況下，與排序碼值總比較次數(shù)最少。A．按排序碼值從小到大排列 B．按排序碼值從大到小排列C．隨機(jī)排列(完全無序) D．基本按排序碼值升序排列7. 用冒泡排序方法對(duì)n個(gè)記錄按排序碼值從小到大排序時(shí)，當(dāng)初始序列是按排序碼值從大到小排列時(shí)，與碼值總比較次數(shù)是 （D） 。A．直接插入排序 B．冒泡排序 C．快速排序 D．直接選擇排序9. 將6個(gè)不同的整數(shù)進(jìn)行排序，至少需要比較 (A) 次。A．5 B．6 C．15 D．2111. *若需要時(shí)間復(fù)雜度在O(nlog2n)內(nèi)，對(duì)整數(shù)數(shù)組進(jìn)行排序，且要求排序方法是穩(wěn)定的，則可選擇的排序方法是 (B) 。A．快速排序 B．冒泡排序 C．歸并排序 D．直接選擇排序13. 當(dāng)待排序的整數(shù)是有序序列時(shí)，采用 （A）方法比較差，達(dá)到最壞情況下時(shí)間復(fù)雜度為O(n2)。A．快速排序 B．冒泡排序 C．歸并排序 D．直接選擇排序15. *堆是一種 (B) 排序。A．80，40，50，30，60，70 B．80，70，60，50，40，30C．80，70，50，40，30，60 D．80，60，70，30，40，5017. 若一組記錄的排序碼值序列為{50，80，30，40，70，60}利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)，得到一趟快速排序的結(jié)果為（B ） 。A．堆排序 B．直接選擇排序 C．歸并排序 D．快速排序19. 已知A[m]中每個(gè)數(shù)組元素距其最終位置不遠(yuǎn)，采用下列 (A) 排序方法最節(jié)省時(shí)間。A．歸并 B．堆 C．快速 D．直接選擇21. *在下列排序方法中不需要對(duì)排序碼值進(jìn)行比較就能進(jìn)行排序的是 （A） 。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}23. 給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)行排列，冒泡排序(大數(shù)下沉)的第一趟排序結(jié)果應(yīng)為（C ）。A．{B，F(xiàn)，C，J，A，E，D，I，C，H}B．{C，B，D，A，E，F(xiàn)，I，C，J，H}C．{B，F(xiàn)，C，E，A，I，D，C，H，J}D．{A，B，D，C，E，F(xiàn)，I，J，C，H}25. *給定排序碼值序列為{F，B，J，C，E，A，I，D，C，H}，對(duì)其按字母的字典序列的次序進(jìn)行排列，二路歸并排序的第一趟排序結(jié)果是（A ）。數(shù)據(jù)(Data):是對(duì)信息的一種符號(hào)表示。（一個(gè)得分點(diǎn)）數(shù)據(jù)元素(Data Element):是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理，相當(dāng)于表中的一條記錄。（一個(gè)得分點(diǎn)） 關(guān)系：包含關(guān)系：數(shù)據(jù)泛指所有。（一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)，總共5個(gè)得分點(diǎn)，每段話一個(gè)得分。數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。（一個(gè)得分點(diǎn)）集合結(jié)構(gòu)： 僅同屬一個(gè)集合（、）?線性結(jié)構(gòu): 一對(duì)一（1:1) （、）? 樹 結(jié) 構(gòu): 一對(duì)多（1:n) （、）? 圖 結(jié) 構(gòu): 多對(duì)多 (m:n) （、）?評(píng)分標(biāo)準(zhǔn)：每段話一個(gè)得分點(diǎn)，總共5個(gè)得分點(diǎn)。它依賴于計(jì)算機(jī)。（共2個(gè)得分點(diǎn)，）區(qū)別：數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問題的，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。（一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：共5個(gè)得分點(diǎn)，按照每段話各自標(biāo)注的得分點(diǎn)進(jìn)行評(píng)分。算法由操作、控制結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)3要素組成操作包含：算術(shù)運(yùn)算、關(guān)系比較、邏輯運(yùn)算、數(shù)據(jù)傳送（輸入、輸出、賦值）（一個(gè)得分點(diǎn)）例子中有關(guān)系比較和賦值計(jì)算的操作。（一個(gè)得分點(diǎn)）本例是數(shù)值問題，涉及到兩個(gè)正整數(shù)，因此使用基本的整數(shù)類型就可以解決問題。4. 簡(jiǎn)述算法的基本性質(zhì)1）輸入：0個(gè)或多個(gè)輸入2）輸出：1個(gè)或多個(gè)輸出3）有窮性：算法必須在有限步內(nèi)結(jié)束4）確定性：組成算法的操作必須清晰無二義性5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)評(píng)分標(biāo)準(zhǔn)，本題共5個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。6. 評(píng)價(jià)算法好壞的3條主要標(biāo)準(zhǔn)1）算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間。3）算法應(yīng)易于理解、易于編碼、易于調(diào)試等。7. 請(qǐng)簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)所研究的三種基本結(jié)構(gòu)，以及數(shù)據(jù)元素間的關(guān)系。（2分）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)多的關(guān)系。（）8. 請(qǐng)問算法的分析和評(píng)價(jià)的兩個(gè)標(biāo)準(zhǔn)，以及各自作用。（+1分）空間復(fù)雜度：評(píng)估算法運(yùn)行時(shí)所需最大存儲(chǔ)空間。（5分）（1）線性結(jié)構(gòu)：數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。（）（3）圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素，零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。（2分）（3）算法應(yīng)易于理解、易于編碼、易于調(diào)試。（a, 2分，b,）12. 算法的基本性質(zhì)有哪些？并簡(jiǎn)述每個(gè)特性。（少一個(gè)扣1分）14. 請(qǐng)描述線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲(chǔ)方式，并說出其各有什么特點(diǎn)。（1+）鏈?zhǔn)酱鎯?chǔ)：非連續(xù)存儲(chǔ)，不易于定位，易于插入和刪除。（1+）時(shí)間效率：關(guān)注算法的運(yùn)算速度。鏈表只需要將前一個(gè)數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個(gè)數(shù)據(jù)即可（）。（）3. 順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)有哪些? (中等)順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn):（）存儲(chǔ)空間連續(xù)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素缺點(diǎn):（）插入、刪除操作需要移動(dòng)大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴(kuò)充4. 單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)有哪些? (中等)單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn):（）不需預(yù)先分配空間，空間利用充分插入、刪除操作簡(jiǎn)單, 無需移動(dòng)大量的元素表容量易于擴(kuò)充缺點(diǎn):（）每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需空間存儲(chǔ)其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機(jī)存取任一元素, 只能從鏈表頭依次查找.5. 有順序表A=(a0, a1, a2,...a8,a9,…a19)，要在a8,a9之間插入一個(gè)元素a20，請(qǐng)描述其操作(思想)步驟。（2分） （2）、將新結(jié)點(diǎn)插入到空余位置10處。(中等)（1）然后將從位置11到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。根據(jù)順序表的存儲(chǔ)特點(diǎn)，要在表中某位置i插入一新數(shù)據(jù)元素，則要進(jìn)行如下兩步操作：（1）從位置i到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個(gè)存儲(chǔ)位置，為新插入結(jié)點(diǎn)騰出第i個(gè)位置；（2分）（2）將新數(shù)據(jù)x插入到空余位置i處。（1）然后將從位置i到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。（1） 找到將插入數(shù)據(jù)位置的前一個(gè)結(jié)點(diǎn)p。（2分）（3）p的next值等于q；（2分）10. 請(qǐng)描述從一個(gè)單鏈表中刪除一個(gè)數(shù)據(jù)的刪除過程。 （2分）（2）p的next指針指向被刪除數(shù)據(jù)的后一個(gè)結(jié)點(diǎn)；（2分）（3）將被刪除數(shù)據(jù)原來的next指針指向null。（簡(jiǎn)單）（1）線性表、棧和隊(duì)列都屬于線性結(jié)構(gòu)。（1分）（3）棧是一種先進(jìn)后出的線性表，隊(duì)列是一種先進(jìn)先出的線性表（2分）2. 在計(jì)算機(jī)進(jìn)行運(yùn)算時(shí)，需要把十進(jìn)制轉(zhuǎn)換為二進(jìn)制。答:棧。棧是一種先進(jìn)后出的線性結(jié)構(gòu)，能夠滿足這種操作。 （2）、如果該線性結(jié)構(gòu)是棧，那么，輸出序列可能是d,c,e,a,b嗎，為什么？ （3）、如果該線性結(jié)構(gòu)是棧，且輸出序列是abcde。（push (x)：表示把x壓入棧內(nèi)；pop (x)：表示把x彈出棧） 答：（1）、abcde（1分）（2）、不可能，因?yàn)椋篸是第一出棧字符，說明a,b已別壓入棧內(nèi)；并且壓入棧的次序?yàn)閍bcde；由以上得出：ab出棧的順序只能是b、a，而不是a、b。（2分）（3）、（2分）push (a)，pop (a)push (b)，pop (b)push (c)，pop (c)push (d)，pop (d)push (e)，pop (e)4. 簡(jiǎn)述棧和隊(duì)列的異同點(diǎn)。（2分）不同點(diǎn)：棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是后進(jìn)先出。答:12132123321（各1分）6. 如果入棧序列有ＡＢＣ組成, 請(qǐng)問輸出序列可能有哪些? (較難)輸出序列有5種：C B A, B C A, B A C, A C B , A B C（各1分）7. 如果有abcde五個(gè)數(shù)據(jù)依次全部存入，如果采用隊(duì)列和棧來進(jìn)行存儲(chǔ)，依次取出分別將獲得什么內(nèi)容。（中等）不能得到1423，但可以得到1432（2分）因?yàn)橐玫?必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到1432不能獲得1423。（3分）9. 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？(可不考)循環(huán)隊(duì)列的優(yōu)點(diǎn)是可以克服順序隊(duì)列的假上溢現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。（2分）第四章 串1. 對(duì)于字符串S=’abcde’，請(qǐng)問：（簡(jiǎn)單）（1）字符串S的長(zhǎng)度是多少？（2）字符串S的子串有幾個(gè)，并列出所有子串？答：（1）、5 （1分）（2）、16，（1分）所有字串：’a’、’b’、’c’、’d’、’e’、 ’ab’、 ’ bc’、 ’ cd’ 、’de’、’abc’、’ bcd’、 ’cde’、 ’abcd’、 ’bcde’、 ’abcde’、Φ。（3分） 3. 請(qǐng)問答：什么串的模式匹配？模式匹配算法有幾種？（簡(jiǎn)單）答：串的模式匹配是指子串的定位運(yùn)算，即在主串中查找子串第一次出現(xiàn)的位置。（該題共4個(gè)得分點(diǎn)，答對(duì)串匹配定義或大意基本相同，得 2 分；答對(duì)兩種匹配算，得 2 分，答錯(cuò)或少答一個(gè) 扣 1分）第五章 數(shù)組和廣義表1. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)組是最基本的結(jié)構(gòu)，請(qǐng)完成以下要求：（1）、定義一個(gè)能容納5個(gè)整型元素的數(shù)組iAry，且元素的值為50 。（規(guī)定：整型長(zhǎng)度為兩個(gè)字節(jié)）（1）、int iAry[5]={ 50 } （2 分）（2）、如下圖：（3分，根據(jù)情況，酌情扣分）2. 簡(jiǎn)述數(shù)組的定義、特點(diǎn)和分類。（1個(gè)得分點(diǎn)）特點(diǎn)：1）數(shù)組中各元素具有統(tǒng)一的類型；（1個(gè)得分點(diǎn)）2）數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。 （1個(gè)得分點(diǎn)）分類：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個(gè)得分點(diǎn)）3. 已知一個(gè)二維數(shù)組A如下所示。有，鏈?zhǔn)酱鎯?chǔ)，如下圖所示（1個(gè)得分點(diǎn)）第六章 樹和二叉樹1. 有一樹，如下圖所示： （簡(jiǎn)單）請(qǐng)回答以下問題：（1）樹的葉子結(jié)點(diǎn)及其度。（3）樹的深度。（2分）（2）、非終端結(jié)點(diǎn)有：A 度為3，B 度為2，C 度為1。（1分）2. 請(qǐng)回答：樹與二叉樹有什么區(qū)別？（中等）答：區(qū)別有兩點(diǎn)：(1)二叉樹的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹，樹則不然。（）3. 有一棵具有n個(gè)結(jié)點(diǎn)的滿二叉樹。（中等）答：(n+1)/2。又由于 n0= n2+1，n= n2+n0 ，所以可得出：n0=(n+1)/2 。中序:DBEAFC。()6. 有如下一顆樹其前序\中序\后序遍歷結(jié)果是什么? (中等)其前序遍歷結(jié)果是：A B D G C E F 其中序遍歷結(jié)果是：D G B A E C F其后序遍歷結(jié)果是：G D B E F C A ()7. 假定用于通信的電文由8個(gè)字符A、B、C、D、E、F、G、H組成，各字母在電文中出現(xiàn)概率為5％、25％、4％、7％、9％、12％、30％、8％。以這些權(quán)值構(gòu)成的霍夫曼樹，如下圖所示：請(qǐng)問答以下問題：（中等）（1）、參考霍夫曼樹，給字符A、B、C、D、E、F、G、H進(jìn)行編碼。（或者說發(fā)送的編碼序列是什么）答：（1）、A:0011，B:01，C:0010， D:1010，E:000， F:100，G:11，H:1011 （3分）（2）、1011 000 0010 1010 01 （2分）8. 請(qǐng)簡(jiǎn)述滿二叉樹、完全二叉樹的聯(lián)系。 （）（2）、滿二叉樹是指每一層結(jié)點(diǎn)數(shù)都達(dá)到了最大值，所有葉子結(jié)點(diǎn)均在最大層上；而完全二叉樹是遵循著滿二叉樹結(jié)點(diǎn)編號(hào)序列規(guī)律的一種樹。（） 度為3的節(jié)點(diǎn)有A, D。2. 寫出下面圖的鄰接矩陣答案3. 用鄰接表表示下圖的存儲(chǔ)結(jié)構(gòu)答案4. 已知如下的有向圖，請(qǐng)給出：① 每個(gè)頂點(diǎn)的入度和出度； ② 鄰接矩陣；③ 鄰接表；答案第八章 查找1. 什么是查找、靜態(tài)查找以及動(dòng)態(tài)查找？并說出關(guān)于靜態(tài)查找的幾種算法（簡(jiǎn)單）查找：給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。（）動(dòng)態(tài)查找：既查找，又改變（增減）集合內(nèi)的數(shù)據(jù)元素（）靜態(tài)查找的算法有：順序、二分、分塊查找（3個(gè)得分點(diǎn)）2. 請(qǐng)回答出四種查找方