數(shù)據(jù)結(jié)構(gòu)考試試題庫含答案解析

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題集含答案錯(cuò)誤! 未定義書簽。錯(cuò)誤! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未

2、定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。錯(cuò)誤 ! 未定義書簽。目錄目錄 選擇題 第一章緒論 第二章 線性表 第三章 棧和隊(duì)列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 簡(jiǎn)答題 第一章緒論 第二章 線性表 第三章 棧和隊(duì)列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 編程題 第一章緒論 第二章線性表 第三章 棧和隊(duì)列 第四章 串 第五章 數(shù)組和廣義表第六章 樹和二叉樹第七章 圖 第八章 查找 第九章 排序 A、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素， 日某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)

3、對(duì)象， C某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象， D某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素，4. *數(shù)據(jù)結(jié)構(gòu)是指（A ） 。A數(shù)據(jù)元素的組織形式C數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)5. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，A存儲(chǔ)結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)6. 算法分析的目的是（ C ）A找出數(shù)據(jù)的合理性BC分析算法效率以求改進(jìn)口7. 算法分析的主要方法（ A ） 。A、空間復(fù)雜度和時(shí)間復(fù)雜度C可讀性和文檔性選擇題第一章緒論1. 數(shù)據(jù)結(jié)構(gòu)這門學(xué)科是針對(duì)什么問題而產(chǎn)生的？（ A ）A、針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問題B、針對(duì)數(shù)值計(jì)算的程序設(shè)計(jì)問題C數(shù)值計(jì)算與非數(shù)值計(jì)算的問題都針對(duì)D、兩者都不針對(duì)2. 數(shù)據(jù)結(jié)構(gòu)這門學(xué)科的研究?jī)?nèi)容下面選項(xiàng)最準(zhǔn)確的是（ D ）A

4、、研究數(shù)據(jù)對(duì)象和數(shù)據(jù)之間的關(guān)系B、研究數(shù)據(jù)對(duì)象C研究數(shù)據(jù)對(duì)象和數(shù)據(jù)的操作D、研究數(shù)據(jù)對(duì)象、數(shù)據(jù)之間的關(guān)系和操作3. 某班級(jí)的學(xué)生成績(jī)表中查得張三同學(xué)的各科成績(jī)記錄， 其中數(shù)據(jù)結(jié)構(gòu)考了 90分，那么下面關(guān)于數(shù)據(jù)對(duì)象、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)描述正確的是（ C ）90 分是數(shù)據(jù)項(xiàng)90 分是數(shù)據(jù)元素90 分是數(shù)據(jù)項(xiàng)90 分是數(shù)據(jù)元素B、數(shù)據(jù)類型D數(shù)據(jù)定義物理地址與邏輯地址不相同， 稱之為 （ C ）B、邏輯結(jié)構(gòu)D順序存儲(chǔ)結(jié)構(gòu)研究算法中的輸入和輸出關(guān)系分析算法的易懂性和文檔型性B、正確性和簡(jiǎn)明性H數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8 .計(jì)算機(jī)內(nèi)部處理的基本單元是（B ）R數(shù)據(jù)元素C、數(shù)據(jù)項(xiàng)D、數(shù)據(jù)庫9 .數(shù)據(jù)在計(jì)算機(jī)內(nèi)有

5、鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上, 鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（B ）。A、低R高G相同D不好說10 .算法的時(shí)間復(fù)雜度取決于（C ）日待處理數(shù)據(jù)的初始狀態(tài)D不好說A、問題的規(guī)模C問題的規(guī)模和待處理數(shù)據(jù)的初始狀態(tài)11 .數(shù)據(jù)結(jié)構(gòu)既研究數(shù)據(jù)的邏輯結(jié)構(gòu)，又研究物理結(jié)構(gòu)，這種觀點(diǎn)（ B ）A、正確B、錯(cuò)誤C前半句對(duì)，后半句錯(cuò)H前半句錯(cuò)，后半句對(duì)12 .在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C ）A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu)13.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種種（A ）存儲(chǔ)結(jié)構(gòu)。B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)Dk內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)（）的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是B、順序存取A

6、、隨機(jī)存取14. *下列程序的時(shí)間復(fù)雜度是（A ）for (i=1; i<=n; +i)for (j=1； j<=n; +j)c ij=0;A、O(n2)R O(n)C、O(2n) D O(2n2)15. *下列程序的空間復(fù)雜度是(A )for (i=1; i<=n; +i)for (j=1; j<=m; +j)c ij=0;A、O(m*n)B O(m+n)C、O(m-n) D O(m/n)16. *求下列程序段的時(shí)間復(fù)雜度（B）for(i=1; i<=n ;i + + )for(j=1;j<=n ;j + + ) x=x+1;A、O(n2)B 、O(n)

7、C 、。D 、O(0)第二章線性表1 .關(guān)于線性表的說法不正確的是？ （ D）A、存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素（開始結(jié)點(diǎn)）日存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素（終端結(jié)點(diǎn)）C除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)D除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼2 .關(guān)于順序表的說法不正確的是？ （ D ）A、邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰日可以隨機(jī)存取表中任一元素，方便快捷C在線性表中插入某一元素時(shí)，往往需要移動(dòng)大量元素D在線性表中刪除某一元素時(shí)，無需移動(dòng)大量元素3 .當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快 的速度存取線

8、性表中的元素時(shí)，應(yīng)采用什么存儲(chǔ)結(jié)構(gòu)? （ A ）A順序表 R單鏈表C、循環(huán)鏈表 D、雙鏈表4 .在一個(gè)長度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)， 需向后移動(dòng)多少個(gè)元素。（C ）A、n-1 B、n-i C n-i+10 n-i-15 .在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（）oA、單鏈表定義而已 已 指定表的起始位置C為雙向鏈表做準(zhǔn)備 D、為循環(huán)鏈表做準(zhǔn)備6 .根據(jù)線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針數(shù)，將線性鏈表分成（C）A、單鏈表與循環(huán)鏈表B、單鏈表與十字鏈表C單鏈表與雙鏈表D循環(huán)鏈表與多鏈表7 .鏈接存儲(chǔ)的特點(diǎn)是利用化”表示數(shù)據(jù)元素之間的邏輯關(guān)系（A ）A引

9、用B、串聯(lián)C、掛接D、指派8 .已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語句是（D）9 . A、p = R p=null G =null D> =在單鏈表L中，指針p所指結(jié)點(diǎn) 有后繼結(jié)點(diǎn)的條件是（B ）A p=B、！=null10 . G =null D =在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是（C ）A、=s；=； R =;=、 =;=s;D、=p； =s；第三章棧和隊(duì)列1. 棧、隊(duì)列通常采用兩種存儲(chǔ)結(jié)構(gòu)，它們是（B ）A、散列方式和索引方式B、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C鏈表存儲(chǔ)結(jié)和數(shù)組D、線性和非線性存儲(chǔ)結(jié)構(gòu)2. 一個(gè)棧入棧序列是a,b,c,d,則棧輸出序列不可能是（C

10、）A d,c,b,a B c,d,b,aC、d,c,a,b D 、a,b,c,d3. 判斷順序棧（最多結(jié)點(diǎn)數(shù)為m為棧滿的條件是（D ）A top=0 B 、top!=m C 、top!=0 D 、top=m4. 棧存取數(shù)據(jù)原則（或棧特點(diǎn)）是（B ）A、后進(jìn)后出 B、后進(jìn)先出C、先進(jìn)先出 D 、隨意進(jìn)出5. *經(jīng)過以下棧運(yùn)算后，x的值是（A ）InitStack（s）;Push（s,d）;Push（s,e）;Pop（s,x）;Pop（s,x）;GetTop（s,x）;A、dB 、eC 、xD 、s6. 一個(gè)隊(duì)列的進(jìn)隊(duì)序列為：a, b, c, d,則出隊(duì)序列是：（A）A a, b, c, dB、

11、d , c, b, aC a, d, c, bD、 c , b, d, a7. 循環(huán)隊(duì)列為空隊(duì)列的條件是：（ D）A、 =0B 、 Q. （ rear+1）%MaxSize=C、 =0D、 =8. 在存儲(chǔ)結(jié)構(gòu)上，如果用帶頭節(jié)點(diǎn)單鏈表實(shí)現(xiàn)隊(duì)列（假定front 和 rear 分別為隊(duì)首和隊(duì)尾指針） ，則刪除一個(gè)結(jié)點(diǎn)的操作為（ A ） 。A、 = B、 rear=C、 rear=D、 front=9. 棧和隊(duì)列共同點(diǎn)是（ C ）A、先進(jìn)后出日先進(jìn)先出C允許在端點(diǎn)處進(jìn)行操作線性表D無共同點(diǎn)10. 插入和刪除只能在一端進(jìn)行的線性表是（ B ）A循環(huán)隊(duì)列B 、棧C隊(duì)列 D 、循環(huán)棧11. 插入和刪除分別在

12、兩端端進(jìn)行的線性表是（ C ）A循環(huán)隊(duì)列B 、棧C隊(duì)列 D 、循環(huán)棧12. 循環(huán)隊(duì)列為滿隊(duì)列的條件是： （ B ）A、 =0B 、 Q. （ rear+1）%MaxSize=C、 =0D、 =1. 關(guān)于串的敘述，錯(cuò)誤的是：A.串是字符有限序列C.模式匹配是串的重要運(yùn)算2. 串長度是指（ B ）A.串所含不同字母數(shù)目BC.串所含不同字符數(shù)目D第四章 串（ B ）B.空串是由空格構(gòu)成的串D 串有用順序、鏈?zhǔn)絻煞N存儲(chǔ)方式串所含字符數(shù)目串所含非空格字符數(shù)目3. *若串S=” database” ,其子串?dāng)?shù)目是（ B ）。A 16 B 37 C 8 D 364. 設(shè)用S1是用S子申，則求S1在S中定位運(yùn)

13、算稱為（B ）A.求子串 B .串匹配 C ,聯(lián)接 D .求串長5. 設(shè)有串 s1=” welcome to zdsoft colleage! ”和 s2=” so” , 那么 s2 在 s1 中的索引位置是（ C ）A 12 B 14 C 13 D 106. *若串 S=“software “ , 其子串的數(shù)目是（ B ） 。A 8 B 37 C 36 D 9第五章 數(shù)組和廣義表第六章 樹和二叉樹1. 假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30 個(gè)，則葉子結(jié)點(diǎn)數(shù)為（ B ）個(gè)。A. 15B. 16C. 17D. 472. 假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（C ）

14、 。A. 3B. 4C. 5D. 63. 在一棵二叉樹上第 4 層的結(jié)點(diǎn)數(shù)最多為（ D ） 。A. 2B. 4C. 6D. 84. 用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中 R1.n ，結(jié)點(diǎn) Ri 若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（ B ） 。A. R2i+1 B. R2iC. Ri/2D. R2i-15. 設(shè)n, m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（B ）。A. n在m右方B. n 在m左方C.n是m的祖先D.n是m的子孫6. 下面敘述正確的是（D ）。A.二叉樹是特殊的樹B.二叉樹等價(jià)于度為 2的樹C.完全二叉樹必為滿二叉樹D.二叉樹的左右子樹有次

15、序之分7 .現(xiàn)有一深度為5的二叉樹，請(qǐng)問其最多有（D ）個(gè)結(jié)點(diǎn)。A. 32B.5D. 318 .現(xiàn)有一深度為4的二叉樹，請(qǐng)問其最多有（A ）個(gè)結(jié)點(diǎn)。A. 15B. 169 .在一棵二叉排序樹上按（B ）遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。A.先序B.中序C.后序D.頭序10 .在一棵二叉樹中，度為0的結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,則n0= （ C ）A. n+1 B.n+2+111 .由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有（A. 4B. 512 . 一棵含有n個(gè)結(jié)點(diǎn)的樹，（A ）A.單支樹 B.二叉樹13 .不含任何結(jié)點(diǎn)的空樹（C ）。A .是一棵樹； 樹；C.是一棵樹也是一棵二叉樹；14 .二叉樹

16、是非線性數(shù)據(jù)結(jié)構(gòu)，所以（A .它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)； 儲(chǔ)；C .順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ)D .順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用+1B ）種不同的形態(tài)形態(tài)達(dá)到最大深度。C.三叉樹 叉樹B .是一棵二叉D.既不是樹也不是二叉樹C）。B.它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存15 .具有n（n>0）個(gè)結(jié)點(diǎn)的完全二叉樹的深度為(C )A .log2(n)B .10g2(n)C .10g2(n)+1D .log2(n)+116 .在一棵三元樹中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的 結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（D ）個(gè)。A. 4B. 517 .有關(guān)二叉樹下列說法正確的是（B

17、）A.二叉樹的度為 2B, 一棵二叉樹的度可以小于2C.二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D.二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為218 .在完全二叉樹中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒（C ）。A.左子結(jié)點(diǎn)B.右子結(jié)點(diǎn)C.左子結(jié)點(diǎn)和右子結(jié)點(diǎn)D.左子結(jié)點(diǎn)，右子結(jié)點(diǎn)和兄弟結(jié)點(diǎn)19 .在下列情況中，可稱為二叉樹的是（B ）A.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的樹B.哈夫曼樹C.每個(gè)結(jié)點(diǎn)至多有兩棵子樹的有序樹D.每個(gè)結(jié)點(diǎn)只有一棵右子樹第七章圖1 .圖的深度優(yōu)先遍歷類似于二叉樹的（A ）。A.先序遍歷B .中序遍歷 C .后序遍歷D .層次遍歷2 .已知一個(gè)圖如圖所示，若從頂點(diǎn)a出發(fā)按深度優(yōu)先遍歷，則可能得到的一種 頂點(diǎn)序列為

18、（C）A. abecdfB. acfebdC. aebcfd D. aedfcb3 .若從無向圖的任意一個(gè)頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索可以訪問圖中所有的頂點(diǎn)，則該圖一定是（B ）圖。A.非連通B .連通 C .強(qiáng)連通 D .有向4 .在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的（ C ）倍。A 1/2 B 15 .在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（ B ） 倍。A1/2B1 C2 D36 . 一個(gè)有N個(gè)頂點(diǎn)的有向圖最多有（ B ）條邊。AN B N（N-1） C N（n-1）/2 D 2N7 .具有4個(gè)頂點(diǎn)的無向完全圖有（A ）條邊。A 6B12C18 D 208 .具

19、有6個(gè)頂點(diǎn)的無向圖至少有（A ）條邊才能確保是一個(gè)連通圖。A 5 B 6 C 7 D 89 .對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣表示，則該矩陣大小是 （D ）A N B （N-1）2 C N-1 D N*N10 . 一個(gè)具有N個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少要（ C ）條邊A N BN+1CN-1 D N/211. *已知圖的鄰接矩陣如圖所示，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)果是0 111 10 0 110 0 0 110 010 11 0 0 0 1110 01 0 10 0 11 0 01 1 00 1 01 0 10 1 0A. 0243 1 56B. 0 1 36542C

20、. 0 1 342 56D. 036 1 54212 .已知圖的鄰接表下圖所示，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（）, 按深度優(yōu)先遍歷的結(jié)果是（D ）0A. 0 132 B . 02 3 1 C .032 1 D ,012313 .已知圖的鄰接表下圖所示，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（）, 按深度優(yōu)先遍歷的結(jié)果是（）。A. 0 132 B0231 C , 03210 12 314 . 當(dāng)在一個(gè)有序的順序表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ C ） 。A.必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減15 . 折半查找有序表（

21、4， 6， 10， 12， 20， 30， 50， 70， 88， 100） 。若查找表中元素58，則它將依次與表中（A ）比較大小，查找結(jié)果是失敗。A 20， 70， 30， 50B 30， 88， 70， 50C 20， 50D 30， 88， 50第八章 查找1. 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（ B ）的線性表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)2. 在查找過程中，若同時(shí)還要增、刪工作，這種查找稱為（ B ） 。A、靜態(tài)查找B 、 動(dòng)態(tài)查找 C 、 內(nèi)查找 D 、 外查找3. 索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)（ A ） 。A、有序 B 、 無序C、 塊間有序 D 、

22、 散列4. 采用順序查找方法查找長度為 n 的線性表時(shí)， 每個(gè)元素的平均查找長度為（ C）A、 n B、 n/2 C、 （n+1）/2D、 （n-1）/25. *將 10個(gè)元素散列到 1000000個(gè)單元的哈希表，則（ C ）產(chǎn)生沖突。A、 一定會(huì) B 、一定不會(huì)C 、仍可能會(huì) D 、以上都不對(duì)6. *散列表的地址區(qū)間為016,散列函數(shù)H（k尸k%17,采用線性探測(cè)法解決地址沖突，將關(guān)鍵字26、 25、 72、 38、 1、 18、 59依次存儲(chǔ)到散列表中。元素59 存放在散列表中的地址為（ A ）A、 8B、 9C、 10 D、 117. 設(shè)有序表的關(guān)鍵字序列為 1,3,9,12,32,41

23、,45,62,75,77,82,95,100， 當(dāng)采用二分查找法查找值為 82 的節(jié)點(diǎn)時(shí)，經(jīng)（ C ）次比較后查找成功。A、 1B、 2C、 3D、 48. 設(shè)有 100 個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大、最小比較次數(shù)分別時(shí) （ A ）A、7,1 B 、 6,1C、 5,1 D、 8,1第九章 排序1. 對(duì) n 個(gè)不同的記錄按排序碼值從小到大次序重新排列， 用冒泡 （ 起泡 ） 排序方法，初始序列在（A ） 情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列2. 對(duì) n 個(gè)不同的記錄按排序碼值從小到

24、大次序重新排列， 用冒泡 （ 起泡 ） 排序方法，在（ B）情況下，與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列3. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初始序列在（ A）情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列4. 對(duì) n 個(gè)不同的記錄按排序碼值從小到大次序重新排列， 用直接插入排序方法，初始序列在（ B）情況下，與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .

25、按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列5. 對(duì) n 個(gè)不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法在（ C）情況下，與排序碼值總比較次數(shù)最少。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列6. 對(duì) n 個(gè)不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法，在（ A）情況下與排序碼值總比較次數(shù)最多。A.按排序碼值從小到大排列B .按排序碼值從大到小排列C.隨機(jī)排列（完全無序） D .基本按排序碼值升序排列7. 用冒泡排序方法對(duì)n 個(gè)記錄按排序碼值從小到大排序時(shí)， 當(dāng)初始序列是按排

26、序碼值從大到小排列時(shí)，與碼值總比較次數(shù)是( D)。A n-1 B n C n+1 D n(n-1) 28. 下列排序方法中， 與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無關(guān)的是 (D)。A.直接插入排序B .冒泡排序C .快速排序D .直接選擇排序9. 將 6 個(gè)不同的整數(shù)進(jìn)行排序，至少需要比較(A)次。A5B6C15D2110. 將 6個(gè)不同的整數(shù)進(jìn)行排序，至多需要比較(C)次。A5B6C15D2111. *若需要時(shí)間復(fù)雜度在O(nlog 2n) 內(nèi)，對(duì)整數(shù)數(shù)組進(jìn)行排序，且要求排序方法是穩(wěn)定的，則可選擇的排序方法是(B)。A.快速排序B .歸并排序 C .堆排序 D .直接插入排序1

27、2. 當(dāng)待排序的整數(shù)是有序序列時(shí)，采用 (B) 方法比較好，其時(shí)間復(fù)雜度為O(n)。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序13. 當(dāng)待排序的整數(shù)是有序序列時(shí)，采用(A)方法比較差，達(dá)到最壞情況下時(shí)間復(fù)雜度為O(n2) 。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序14. 當(dāng)待排序的整數(shù)是有序序列時(shí)，無論待排序序列排列是否有序，采用( D)方法的時(shí)間復(fù)雜度都是O(n2) 。A.快速排序B .冒泡排序 C .歸并排序D .直接選擇排序15. *堆是一種 (B) 排序。A.插入 B .選擇 C .交換 D .歸并16. *若一組記錄的排序碼值序列為 40 ， 8

28、0， 50， 30， 60， 70 ，利用堆排序方法進(jìn)行排序，初建的大頂堆是(D )。A80，40，50，30 ，60，70B80 ， 70，60， 50，40 ， 30C80，70，50，40 ，30，60D80 ， 60，70， 30，40 ， 5017. 若一組記錄的排序碼值序列為 50 ， 80， 30， 40， 70， 60 利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)，得到一趟快速排序的結(jié)果為（ B ） 。A30，40， 50， 60 ，70， 80B40 ， 30， 50，80， 70 ， 60C 50，30， 40， 70 ，60， 80D40 ， 50， 30，70， 60 ， 80

29、18. * 下列幾種排序方法中要求輔助空間最大的是（ C ） 。A.堆排序B .直接選擇排序C .歸并排序 D .快速排序19. 已知 Am 中每個(gè)數(shù)組元素距其最終位置不遠(yuǎn)，采用下列 （A） 排序方法最 節(jié)省時(shí)間。A.直接插入B .堆 C .快速 D .直接選擇20. *設(shè)有10000個(gè)互不相等的無序整數(shù)，若僅要求找出其中前10個(gè)最大整數(shù)，最好采用（ B）排序方法。A.歸并 B .堆 C .快速 D .直接選擇21. *在下列排序方法中不需要對(duì)排序碼值進(jìn)行比較就能進(jìn)行排序的是（ A）A:基數(shù)排序B .快速排序C .直接插入排序D .堆排序22. *給定排序碼值序列為F ， B， J， C， E

30、， A， I ， D， C， H ，對(duì)其按字母的字典序列的次序進(jìn)行排列，希爾 （Shell） 排序的第一趟 （d1=5） 結(jié)果應(yīng)為（ D ）A B ，B C，F(xiàn)， C， J ， A， E， D， I ， C， HB， D， A， E， F， I ， C， J， HH， JC B ， F， C， E， A， I ， D， C，D A ，B， D， C， E， F， I ， J ， C， H23. 給定排序碼值序列為F, B, J, C, E, A, I, D, C, H,對(duì)其按字母的字典序列的次序進(jìn)行排列，冒泡排序（ 大數(shù)下沉 ） 的第一趟排序結(jié)果應(yīng)為（ C ） 。ABJ，A，C，HBCA，E，

31、J，HCBE，A，H，JDAC，E，C，H24. 給定排序碼值序列為F, B, J, C, E, A, I, D, C, H,對(duì)其按字母的字典序列的次序進(jìn)行排列，快速排序的第一趟排序結(jié)果為（ B ） 。A B ，B C，F(xiàn)， C， J ， A， E， D， I ， C， HB， D， A， E， F， I ， C， J， HH， JC B ， F， C， E， A， I ， D， C，D A ，B， D， C， E， F， I ， J ， C， H25. *給定排序碼值序列為 F ， B， J， C， E， A， I ， D， C， H ，對(duì)其按字母的字典序列的次序進(jìn)行排列，二路歸并排序的第一

32、趟排序結(jié)果是（ A ） 。AB ，F(xiàn)，C，J ，A，E，D，I ，C，HBC，B，D，A，E，F(xiàn)，I ，C，J，HCB ，F(xiàn)，C，E，A，I ，D，C，H，JDA ，B，D，C，E，F(xiàn)，I ，J ，C，H簡(jiǎn)答題第一章緒論1. 請(qǐng)分別給出數(shù)據(jù)、 數(shù)據(jù)對(duì)象、 數(shù)據(jù)元素、 數(shù)據(jù)項(xiàng)的含義， 并說明四者的關(guān)系。數(shù)據(jù) （Data）: 是對(duì)信息的一種符號(hào)表示。在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。 （一個(gè)得分點(diǎn)）數(shù)據(jù)元素 （Data Element）: 是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理，相當(dāng)于表中的一條記錄。 （一個(gè)得分點(diǎn)）數(shù)據(jù)項(xiàng)：相當(dāng)于記錄的

33、“域” , 是數(shù)據(jù)的不可分割的最小單位, 如學(xué)號(hào)（一個(gè)得分點(diǎn)）數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集. 例如 : 同一個(gè)班的所有學(xué)生記錄集合。 （一個(gè)得分點(diǎn)）關(guān)系：包含關(guān)系：數(shù)據(jù)泛指所有。數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集，由數(shù)據(jù)元素組成，數(shù)據(jù)元素是由數(shù)據(jù)項(xiàng)組成。 （一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)，總共 5 個(gè)得分點(diǎn)，每段話一個(gè)得分。2. 請(qǐng)給出數(shù)據(jù)的邏輯結(jié)構(gòu)的含義，并舉例說明數(shù)據(jù)的邏輯結(jié)構(gòu)通常有哪些。數(shù)據(jù)的邏輯結(jié)構(gòu)： 指數(shù)據(jù)元素之間的邏輯關(guān)系。 即用自然語言描述數(shù)據(jù)， 它與數(shù)據(jù)的存儲(chǔ)無關(guān)，是獨(dú)立于計(jì)算機(jī)的，邏輯結(jié)構(gòu)有四種。 （一個(gè)得分點(diǎn)）集合結(jié)構(gòu)： 僅同屬一個(gè)集合（結(jié)構(gòu)名字個(gè)得分點(diǎn)、舉例得分點(diǎn)）線

34、性結(jié)構(gòu) :一對(duì)一（ 1:1） （結(jié)構(gòu)名字個(gè)得分點(diǎn)、舉例得分點(diǎn)）樹 結(jié) 構(gòu):一對(duì)多（ 1:n） （結(jié)構(gòu)名字個(gè)得分點(diǎn)、舉例得分點(diǎn)）圖 結(jié) 構(gòu): 多對(duì)多 （m:n） （結(jié)構(gòu)名字個(gè)得分點(diǎn)、舉例得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：每段話一個(gè)得分點(diǎn)，總共 5 個(gè)得分點(diǎn)。什么是數(shù)據(jù)的物理結(jié)構(gòu)？有哪些物理結(jié)構(gòu)？數(shù)據(jù)的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)有什么區(qū)別與聯(lián)系？數(shù)據(jù)的物理結(jié)構(gòu)： 物理結(jié)構(gòu)亦稱存儲(chǔ)結(jié)構(gòu)， 是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示（或映像） 。它依賴于計(jì)算機(jī)。 （一個(gè)得分點(diǎn)）存儲(chǔ)結(jié)構(gòu)可分為 4 大類：順序、鏈?zhǔn)健⑺饕?、散列?（共 2 個(gè)得分點(diǎn)，一個(gè)得分點(diǎn)）區(qū)別： 數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖， 是面向問題的， 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬

35、于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。 （一個(gè)得分點(diǎn)）聯(lián)系： 一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來存儲(chǔ)， 而采用不同的存儲(chǔ)結(jié)構(gòu)其處理的效率往往不同。 （一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：共 5 個(gè)得分點(diǎn)，按照每段話各自標(biāo)注的得分點(diǎn)進(jìn)行評(píng)分。3. 求兩個(gè)正整數(shù)m, n中的最大數(shù)MAX勺算法（ 1 ）若 m > n 則 max=m（ 2 ）若 m <= n 則 max=n請(qǐng)根據(jù)上述算法解釋一下算法的組成要素有哪些，分別是什么。算法由操作、控制結(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)）

36、控制結(jié)構(gòu)包含：順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)（一個(gè)得分點(diǎn)）例子中有選擇結(jié)構(gòu)（一個(gè)得分點(diǎn)）數(shù)據(jù)結(jié)構(gòu)： 算法操作的對(duì)象是數(shù)據(jù)， 數(shù)據(jù)間的邏輯關(guān)系、 數(shù)據(jù)的存儲(chǔ)方式及處理方式就 是數(shù)據(jù)結(jié)構(gòu)。 （一個(gè)得分點(diǎn)）本例是數(shù)值問題，涉及到兩個(gè)正整數(shù)，因此使用基本的整數(shù)類型就可以解決問題。 （一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：本題共 6 個(gè)得分點(diǎn)，每段話一個(gè)得分點(diǎn)。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)一分。5. 簡(jiǎn)述算法的設(shè)

37、計(jì)要求1、正確性（correctness）2、可讀性（readability）3、健壯性（robustness）4、通用性（generality）5、效率與存儲(chǔ)的要求（執(zhí)行算法所耗費(fèi)的存儲(chǔ)空間、執(zhí)行算法所耗費(fèi)的時(shí)間）評(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í)間。2）算法實(shí)現(xiàn)所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。3）算法應(yīng)易于理解、易于編碼、易于調(diào)試等。評(píng)分標(biāo)準(zhǔn)，本題共 3 個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。7. 請(qǐng)簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)所研究的三種基本結(jié)構(gòu)，以及數(shù)據(jù)元素間的關(guān)系。線性結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)一的關(guān)系。（ 2分）樹形結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)

38、多的關(guān)系。（分）圖形結(jié)構(gòu)：數(shù)據(jù)元素之間多對(duì)多的關(guān)系。（分）8. 請(qǐng)問算法的分析和評(píng)價(jià)的兩個(gè)標(biāo)準(zhǔn)，以及各自作用。時(shí)間復(fù)雜度：評(píng)估算法運(yùn)行所需時(shí)間。 （ +1 分）空間復(fù)雜度：評(píng)估算法運(yùn)行時(shí)所需最大存儲(chǔ)空間。+1 分）5 分）9. 請(qǐng)說出三種邏輯數(shù)據(jù)結(jié)構(gòu)，以及他們的特點(diǎn)。（ 1 ）線性結(jié)構(gòu)：數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。 （ 2 分）（ 2 ）樹結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。（分）（ 3 ）圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素，零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。 （分）10. 評(píng)價(jià)算法的主要標(biāo)準(zhǔn)是什么？（ 1 ）算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間（

39、2 分）（ 2 ）算法實(shí)現(xiàn)所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。（ 2 分）（ 3 ）算法應(yīng)易于理解、易于編碼、易于調(diào)試。（ 1 分）11. 請(qǐng)說出三種邏輯數(shù)據(jù)結(jié)構(gòu)，并分別畫圖表示它們。（ a, 2 分， b,c 各分）12. 算法的基本性質(zhì)有哪些？并簡(jiǎn)述每個(gè)特性。 （5 分 ）1 ）有窮性 （1 分）2 ）確定性 （ 1 分）3 ）可行性 （ 1 分）4 ）輸入性 （ 1 分）5 ）輸出性 （ 1 分）13. 通常從那幾個(gè)方面來評(píng)價(jià)算法的質(zhì)量? （5 分 ）通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：正確性、可讀性、健壯性和高效性。 （少一個(gè)扣 1 分）14. 請(qǐng)描述線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲(chǔ)方式，并說

40、出其各有什么特點(diǎn)。順序存儲(chǔ)：連續(xù)存儲(chǔ)，易于定位，不易于插入和刪除。 （ 1+分）鏈?zhǔn)酱鎯?chǔ)：非連續(xù)存儲(chǔ)，不易于定位，易于插入和刪除。 （ 1+分）15. 請(qǐng)問算法的分析和評(píng)價(jià)的兩種方法，它們關(guān)注點(diǎn)各有什么不同？（簡(jiǎn)單）空間效率：關(guān)注算法對(duì)內(nèi)存的占用度。 （ 1+分）時(shí)間效率：關(guān)注算法的運(yùn)算速度。（ 1+分）第二章 線性表1. 請(qǐng)問如果要插入一個(gè)數(shù)據(jù)到一個(gè)線性表中， 順序表和鏈表哪個(gè)的效率高？為什么？鏈表的效率高 （ 2 分） ， 因?yàn)轫樞虮硪苿?dòng)插入位置后的每一個(gè)元素的位置給新數(shù)據(jù)騰位置（分） 。鏈表只需要將前一個(gè)數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個(gè)數(shù)據(jù)即可（分） 。2. 線性表有哪些

41、特點(diǎn)？1）除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素； （ 2 分）2）第一個(gè)數(shù)據(jù)元素沒有前驅(qū)數(shù)據(jù)元素； （分）3）最后一個(gè)數(shù)據(jù)元素沒有后繼數(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) :

42、（分）每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需空間存儲(chǔ)其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機(jī)存取任一元素 , 只能從鏈表頭依次查找.5. 有順序表A=（a0, a1, a2,a8,a9, - 19）,要在a8,a9之間插入一個(gè)元素 a20,請(qǐng)描述其操作（思想）步驟。（中等）插入思想或步驟： 根據(jù)順序表的存儲(chǔ)特點(diǎn)， 要在表中某位置10 插入一新數(shù)據(jù)元素 , 則要進(jìn)行如下兩步操作：（ 1） 、 從位置 10 到表尾位置的所有數(shù)據(jù)元素均要從后至前依次向后移一個(gè)存儲(chǔ)位置，為新插入結(jié)點(diǎn)騰出第 10 個(gè)位置。 （ 2 分）（ 2） 、將新結(jié)點(diǎn)插入到空余位置10 處。 2 分）（ 3）表長度加1.（

43、1 分）6. 有順序表A=（a0, a1, a2,a8,a9, - 19）,要?jiǎng)h除一個(gè)元素 a9,請(qǐng)描述其 操作 （ 思想 ） 步驟。 （ 中等 ）（ 1 ）然后將從位置11 到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。 （ 3 分）（ 2）表長度減1.（ 2 分）7. 請(qǐng)描述在順序表中第i 個(gè)位置插入新的數(shù)據(jù)x 操作過程。根據(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 處。 （ 2 分）（ 3

44、 ）表長度加1.（ 1 分）8. 請(qǐng)描述在順序表中刪除第i 個(gè)位置的數(shù)據(jù)的過程。（ 1 ）然后將從位置i 到表尾的所有數(shù)據(jù)元素依次向前移一個(gè)存儲(chǔ)位置。 （ 3 分）（ 2 ）表長度減1.（ 2 分）9 .請(qǐng)描述在一個(gè)單鏈表中插入一個(gè)數(shù)據(jù)q的插入過程(1)找到將插入數(shù)據(jù)位置的前一個(gè)結(jié)點(diǎn)p; (1分)(2) q的next值等于p的next值；(2分)(3) p的next值等于q； (2分)10 .請(qǐng)描述從一個(gè)單鏈表中刪除一個(gè)數(shù)據(jù)的刪除過程。(1)找到將被刪除數(shù)據(jù)的前一個(gè)結(jié)點(diǎn)p； (2分)(2) p的next指針指向被刪除數(shù)據(jù)的后一個(gè)結(jié)點(diǎn)；(2分)(3)將被刪除數(shù)據(jù)原來的next指針指向null;

45、(1分)第三章棧和隊(duì)列1 .請(qǐng)簡(jiǎn)述線性表、棧和隊(duì)列三者之間的聯(lián)系。(簡(jiǎn)單)(1)線性表、棧和隊(duì)列都屬于線性結(jié)構(gòu)。(2分)(2)棧和隊(duì)列都是特殊的線性表，并且都有順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)兩種存儲(chǔ)方式。(1分)(3)棧是一種先進(jìn)后出的線性表，隊(duì)列是一種先進(jìn)先出的線性表(2分)2 .在計(jì)算機(jī)進(jìn)行運(yùn)算時(shí)，需要把十進(jìn)制轉(zhuǎn)換為二進(jìn)制。請(qǐng)問答：這種數(shù)制轉(zhuǎn)換 可以借助于哪種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)、及原因。答：棧。(2分)原因：(3分)在進(jìn)行數(shù)值轉(zhuǎn)換時(shí)，其實(shí)質(zhì)是求余的過程，并且余數(shù)的倒序序列正是所求結(jié)果。棧是一種先進(jìn)后出的線性結(jié)構(gòu)，能夠滿足這種操作。3 .有一字符序列abcde依次按照某一線性結(jié)構(gòu)存儲(chǔ)，請(qǐng)回答以下問題：1 1)

46、、如果該線性結(jié)構(gòu)是隊(duì)列，那么，寫出出隊(duì)序列。2 2)、如果該線性結(jié)構(gòu)是棧，那么，輸出序列可能是d,c,e,a,b 嗎，為什么？3 3)、如果該線性結(jié)構(gòu)是棧，且輸出序列是abcde。請(qǐng)寫出操作過程。(push(x):表示把x壓入棧內(nèi)；pop (x):表示把x彈出棧)答：4 1)、abcde 11 分)5 2)、不可能，因?yàn)椋篸是第一出棧字符，說明 a,b已別壓入棧內(nèi)；并且壓入棧的次序?yàn)閍bcde ;由以上得出：ab出棧的順序只能是 b、a,而不是a、b。所以，出棧序列d,c,e,a,b 是不可能的。(2分)6 3)、(2 分)push (a) , pop (a)push (b)pop (b)pu

47、sh ,pop （c）push （d） , pop （d）push （e） , pop （e）7 .簡(jiǎn)述棧和隊(duì)列的異同點(diǎn)。相同點(diǎn)：棧和隊(duì)列都是只允許在表的端點(diǎn)處進(jìn)行插入、刪除操作的線性表。（2分）不同點(diǎn)：棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是后進(jìn)先出。（3分）8 .若依次讀入數(shù)據(jù)元素序列1、2、3,進(jìn)棧的過程中允許出棧，試寫出各種可 能的出棧序列。答:123、132、213、231、321 （各 1 分）9 .如果入棧序列有ABC組成，請(qǐng)問輸出序列可能有哪些？（較難）輸出序列有5種：CBA,BCA,BAC,ACB,ABC （各 1 分）10 如果有abcde五個(gè)數(shù)據(jù)依次全部存入，如果采用隊(duì)列和棧來進(jìn)

48、行存儲(chǔ)，依次 取出分別將獲得什么內(nèi)容。（簡(jiǎn)單）隊(duì)列：abcde （分）棧：edcba （分）11 設(shè)將整數(shù)1 , 2, 3, 4依次進(jìn)棧，能否得到1423出棧序列和1432?并說明為 什么不能得到或者如何得到。（中等）不能彳#到1423,但可以得到1432 （2分）因?yàn)橐玫?必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到1432不能獲得1423。采用push、pop、push、push、push、pop、pop、pop 可以獲得 1432。（3 分）12 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？（可不考）循環(huán)隊(duì)列的優(yōu)點(diǎn)是可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空

49、間得到充分的利用。（3分）采用犧牲一個(gè)元素空間的方法，循環(huán)隊(duì)列隊(duì)空的條件是 front=rear :循環(huán)隊(duì)列隊(duì)滿的條件是：（rear+1）%M=front 。 （2分）第四章串1 .對(duì)于字符用S=' abcde',請(qǐng)問：（簡(jiǎn)單）（1）字符串S的長度是多少？（2）字符串S的子串有幾個(gè)，并列出所有子串？答：（1）、5（1 分）（2）、16, （1 分）所有字串：a'、 b'、 c'、 d'、 e'、 ab'、 bc'、 cd' 、 de' 、 abc'、'bcd '、' cde&

50、#39;、' abcd'、' bcde'、' abcde'、。（3 分）2 .對(duì)于字符用S=' 12345',請(qǐng)問：（簡(jiǎn)單）（1）字符串S的長度是多少？（2）字符串S的子串有幾個(gè)，并列出所有子串？答：（1）、5（1 分）（2）、16, （1 分）所有字串：1、 2'、 3'、 4'、 5、 12、 23'、 34 、 45' 、 ' 123'、'234 '、' 345'、' 1234'、' 2345'、'

51、 12345'、。（3 分）3 .請(qǐng)問答：什么用的模式匹配？模式匹配算法有幾種？（簡(jiǎn)單）答：串的模式匹配是指子串的定位運(yùn)算，即在主串中查找子串第一次出現(xiàn)的位置。模式匹配算法有兩種：簡(jiǎn)單匹配算法（Brute-Force） 、KM法。（該題共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 ,且元素的值為10、20、30、40、50。（2）、*畫出數(shù)組iAry的順序存儲(chǔ)結(jié)構(gòu)。（規(guī)定：整型長度為兩個(gè)字節(jié)）（1）、int

52、iAry5= 10、20、30、40、50 （2 分）（2）、如下圖：（3分，根據(jù)情況，酌情扣分 ）2 .簡(jiǎn)述數(shù)組的定義、特點(diǎn)和分類。（簡(jiǎn)單）定義：數(shù)組是n個(gè)相同數(shù)據(jù)類型的數(shù)據(jù)元素a0,a1,a2,an-1構(gòu)成的有限集合。（1個(gè)得分點(diǎn)）特點(diǎn)：1）數(shù)組中各元素具有統(tǒng)一的類型；（1個(gè)得分點(diǎn)）2）數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。（1個(gè)得分點(diǎn)）3數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷毀之外，只有存取元素和修改元素值的操作。 （1個(gè)得分點(diǎn)）分類：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個(gè)得分點(diǎn)）3 .已知一個(gè)二維數(shù)組A如下所示。（較難）（1）

53、請(qǐng)按照行優(yōu)先、列優(yōu)先的方式進(jìn)行順序存儲(chǔ)，給出順序存儲(chǔ)的序列（2個(gè)得分點(diǎn)）行優(yōu)先：a11a12a13a21a22a23列優(yōu)先：a11a21a12a22a13a23（2）若a11在內(nèi)存中存儲(chǔ)的地址為a ,每個(gè)元素的存儲(chǔ)空間大小為L,則按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲(chǔ)，其中a22的地址10c（a22）分別為多少（2個(gè)得分點(diǎn)）行優(yōu)先：10c（a22）= a +4L列優(yōu)先：10c（a22）= a +3L（3）對(duì)于數(shù)組，除了順序存儲(chǔ)外，還有沒有其他存儲(chǔ)方式？沒有填無，若有，請(qǐng)說明。有，鏈?zhǔn)酱鎯?chǔ)，如下圖所示（1個(gè)得分點(diǎn)）第六章樹和二叉樹1 .有一樹，如下圖所示：（簡(jiǎn)單）請(qǐng)回答以下問題：（1）樹的葉子結(jié)點(diǎn)及其度。（2）非終端結(jié)點(diǎn)及其度。（3）樹的深度。答：（1）、葉子結(jié)點(diǎn)有：D、E、F、G,它們的度都為零。（2分）（2）、非終端結(jié)點(diǎn)有：A度為3, B度為2, C度為1。（2分）（3）、樹的深度為3。（1分）2 .請(qǐng)回答：樹與二叉樹