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

1、目錄目錄1選擇題2第一章緒論2第二章線性表4第三章棧和隊(duì)列5第四章串6第五章數(shù)組和廣義表7第六章樹(shù)和二叉樹(shù)7第七章圖9第八章查找11第九章排序12簡(jiǎn)答題15第一章緒論15第二章線性表20第三章棧和隊(duì)列22第四章串24第五章數(shù)組和廣義表24第六章樹(shù)和二叉樹(shù)26第七章圖31第八章查找33第九章排序34編程題36第一章緒論36第二章線性表36第三章棧和隊(duì)列46第四章串46第五章數(shù)組和廣義表46第六章樹(shù)和二叉樹(shù)46第七章圖46第八章查找46第九章排序51選擇題第一章緒論1. 數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科是針對(duì)什么問(wèn)題而產(chǎn)生的？（A ）A、針對(duì)非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題B、針對(duì)數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題C、數(shù)值計(jì)算與非數(shù)

2、值計(jì)算的問(wèn)題都針對(duì)D、兩者都不針對(duì)2. 數(shù)據(jù)結(jié)構(gòu)這門(mén)學(xué)科的研究?jī)?nèi)容下面選項(xiàng)最準(zhǔn)確的是（D ）A、研究數(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 ）A、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素，90分是數(shù)據(jù)項(xiàng)B、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，90分是數(shù)據(jù)元素C、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)對(duì)象，90分是數(shù)據(jù)項(xiàng)D、某班級(jí)的學(xué)生成績(jī)表是數(shù)據(jù)元素，90分是數(shù)據(jù)元素4. *數(shù)據(jù)結(jié)構(gòu)是指（A ）。A、數(shù)據(jù)元素的組織形式B、數(shù)據(jù)類(lèi)

3、型C、數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D、數(shù)據(jù)定義5. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同，稱之為（C ）。A、存儲(chǔ)結(jié)構(gòu)B、邏輯結(jié)構(gòu)C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D、順序存儲(chǔ)結(jié)構(gòu)6. 算法分析的目的是（C ）A、找出數(shù)據(jù)的合理性B、研究算法中的輸入和輸出關(guān)系C、分析算法效率以求改進(jìn)D、分析算法的易懂性和文檔型性7. 算法分析的主要方法（A ）。A、空間復(fù)雜度和時(shí)間復(fù)雜度B、正確性和簡(jiǎn)明性C、可讀性和文檔性D、數(shù)據(jù)復(fù)雜性和程序復(fù)雜性8. 計(jì)算機(jī)內(nèi)部處理的基本單元是（B ）A、數(shù)據(jù)B、數(shù)據(jù)元素C、數(shù)據(jù)項(xiàng)D、數(shù)據(jù)庫(kù)9. 數(shù)據(jù)在計(jì)算機(jī)內(nèi)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（B ）。

4、A、低 B、高C、相同D、不好說(shuō)10. 算法的時(shí)間復(fù)雜度取決于（ C ）A 、問(wèn)題的規(guī)模B、待處理數(shù)據(jù)的初始狀態(tài)C、問(wèn)題的規(guī)模和待處理數(shù)據(jù)的初始狀態(tài)D、不好說(shuō)11. 數(shù)據(jù)結(jié)構(gòu)既研究數(shù)據(jù)的邏輯結(jié)構(gòu)，又研究物理結(jié)構(gòu)，這種觀點(diǎn)（B ）。A、正確B、錯(cuò)誤C、前半句對(duì)，后半句錯(cuò)D、前半句錯(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)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)13. 線性表的順序存儲(chǔ)結(jié)構(gòu)是一種( )的存儲(chǔ)結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種（ A ）存儲(chǔ)結(jié)構(gòu)。A、隨機(jī)存取B、順序存取C、索引存取D、散列存取14. *下列

5、程序的時(shí)間復(fù)雜度是（A ）for (i=1; i<=n; +i)for (j=1; j<=n; +j) c ij=0;A、O(n2)B、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) C、O(

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

7、線性表中的元素時(shí)，應(yīng)采用什么存儲(chǔ)結(jié)構(gòu)？（A ）A、順序表B、單鏈表C、循環(huán)鏈表D、雙鏈表4. 在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)多少個(gè)元素。（C ）A、n-1B、n-iC、n-i+1D、n-i-15. 在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是( )。A、單鏈表定義而已B、指定表的起始位置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)是利用什么來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系（A）A、引

8、用B、串聯(lián)C、掛接D、指派8. 已知指針p指向單鏈表L中的某結(jié)點(diǎn)，則刪除其后繼結(jié)點(diǎn)的語(yǔ)句是（D ）9. *在單鏈表L中，指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是（B ）A、p = p.nextB、p.next!=null10. *在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是（C ）A、p.next=s; s.next=p.next;B、s.next = p.next; p.next=p.next.next;C、s.next = p.next; p.next = s;D、s.next=p; p.next=s;第三章 棧和隊(duì)列1. 棧、隊(duì)列通常采用兩種存儲(chǔ)結(jié)構(gòu)，它們是(B )A、散列方式和索引方式B、順序存儲(chǔ)結(jié)構(gòu)

9、和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)C、鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組D、線性和非線性存儲(chǔ)結(jié)構(gòu)2. 一個(gè)棧入棧序列是a,b,c,d, 則棧輸出序列不可能是(C )A、d,c,b,aB、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)過(guò)以下棧運(yùn)算后，x的值是（A）InitStack(s);Push(s,d);Push(s,e);Pop(s,x); Pop(s,x);GetTop(s,x);A、 d B

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

11、點(diǎn)10. 插入和刪除只能在一端進(jìn)行的線性表是（B）A、循環(huán)隊(duì)列 B、棧C、隊(duì)列 D、循環(huán)棧11. 插入和刪除分別在兩端端進(jìn)行的線性表是（C）A、循環(huán)隊(duì)列 B、棧C、隊(duì)列 D、循環(huán)棧12. 循環(huán)隊(duì)列為滿隊(duì)列的條件是：（B ）A、Q.front=0 B、 Q.（C、 Q.rear=0 D、第四章 串1. 關(guān)于串的敘述，錯(cuò)誤的是：（B）A串是字符有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的重要運(yùn)算 D串有用順序、鏈?zhǔn)絻煞N存儲(chǔ)方式2. 串長(zhǎng)度是指（B）A串所含不同字母數(shù)目 B串所含字符數(shù)目C串所含不同字符數(shù)目 D串所含非空格字符數(shù)目3. *若串S=”database”,其子串?dāng)?shù)目是（B）。A16

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

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

14、. 現(xiàn)有一深度為5的二叉樹(shù)，請(qǐng)問(wèn)其最多有（ D ）個(gè)結(jié)點(diǎn)。A. 32B. 5 C.30D. 318. 現(xiàn)有一深度為4的二叉樹(shù)，請(qǐng)問(wèn)其最多有（ A ）個(gè)結(jié)點(diǎn)。9. 在一棵二叉排序樹(shù)上按（ B ）遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。A. 先序B. 中序C.后序 D.頭序10. 在一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=（ C ）2n+111. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹(shù)，共有（B ）種不同的形態(tài)。12. 一棵含有n個(gè)結(jié)點(diǎn)的樹(shù)，（ A ）形態(tài)達(dá)到最大深度。A. 單支樹(shù)B. 二叉樹(shù)C.三叉樹(shù)叉樹(shù)13. 不含任何結(jié)點(diǎn)的空樹(shù)（ C ）。 .是一棵樹(shù);  &

15、#160;                      .是一棵二叉樹(shù);   .是一棵樹(shù)也是一棵二叉樹(shù);           .既不是樹(shù)也不是二叉樹(shù)14. 二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，所以(    C

16、60;    ) 。 .它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);           .它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);    .順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);  .順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用 15. 具有n(n>0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為(C )。 .log2(n)ù   . log2(n)

17、û   . log2(n)  +1     .log2(n)+1ù 16. 在一棵三元樹(shù)中度為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è)。 17. 有關(guān)二叉樹(shù)下列說(shuō)法正確的是（B ） A二叉樹(shù)的度為2                

18、   B一棵二叉樹(shù)的度可以小于2                           C二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2D二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為218. 在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（C ）。 A左子結(jié)點(diǎn)    B右子結(jié)點(diǎn)

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

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

21、6個(gè)頂點(diǎn)的無(wú)向圖至少有（ A ）條邊才能確保是一個(gè)連通圖。A 5 B 6 C 7 D 89. 對(duì)于一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣大小是（D ）A N B (N-1)2 C N-1 D N*N10. 一個(gè)具有N個(gè)頂點(diǎn)的無(wú)向圖中，要連通全部頂點(diǎn)至少要（ C ）條邊A N B N+1 C N-1 D N/211. *已知圖的鄰接矩陣如圖所示，則從頂點(diǎn)0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（ C ）。A0 2 4 3 1 5 6B0 1 3 6 5 4 2C0 1 3 4 2 5 6D0 3 6 1 5 4 212. 已知圖的鄰接表下圖所示，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ），按

22、深度優(yōu)先遍歷的結(jié)果是（ D ）。A0 1 3 2 B0 2 3 1C0 3 2 1 D0 1 2 313. 已知圖的鄰接表下圖所示，則從頂點(diǎn)0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ），按深度優(yōu)先遍歷的結(jié)果是（ ）。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 314. 當(dāng)在一個(gè)有序的順序表上查找一個(gè)數(shù)據(jù)時(shí)，既可用折半查找，也可用順序查找，但前者比后者的查找速度（ C ）。A必定快 B不一定C在大部分情況下要快 D取決于表遞增還是遞減15. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ A ）比較大小，查找結(jié)果是

23、失敗。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50第八章 查找1. 順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（B ）的線性表。A散列存儲(chǔ) B順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ) C壓縮存儲(chǔ) D索引存儲(chǔ)2. 在查找過(guò)程中，若同時(shí)還要增、刪工作，這種查找稱為（ B ）。A、 靜態(tài)查找 B、 動(dòng)態(tài)查找 C、 內(nèi)查找 D、 外查找3. 索引順序表的特點(diǎn)是順序表中的數(shù)據(jù)（ A ）。A、 有序 B、 無(wú)序 C、 塊間有序 D、 散列4. 采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為（C）A、 nB、n/2C、(n+1)/2D、(n-1)/25. *將10個(gè)元素散列到100000

24、0個(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、 8 B、 9 C、 10D、 117. 設(shè)有序表的關(guān)鍵字序列為1,3,9,12,32,41,45,62,75,77,82,95,100，當(dāng)采用二分查找法查找值為82的節(jié)點(diǎn)時(shí)，經(jīng)（ C ）次比較后查找成功。A、 1B、 2 C、 3D、 48. 設(shè)有100個(gè)元素，用折半查找法進(jìn)行查找時(shí)，最大、最小比較次

25、數(shù)分別時(shí)（ A ）A、 7,1B、6,1C、5,1D、8,1第九章 排序1. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在 （A） 情況下，與排序碼值總比較次數(shù)最少。A按排序碼值從小到大排列 B按排序碼值從大到小排列C隨機(jī)排列(完全無(wú)序) D基本按排序碼值升序排列2. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用冒泡(起泡)排序方法，在 （B） 情況下，與排序碼值總比較次數(shù)最多。A按排序碼值從小到大排列 B按排序碼值從大到小排列C隨機(jī)排列(完全無(wú)序) D基本按排序碼值升序排列3. 對(duì)n個(gè)不同的記錄按排序碼值從小到大次序重新排列，用直接插入排序方法，初

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

27、不同的記錄按排序碼值從小到大次序重新排列，用快速排序方法，在 （A） 情況下與排序碼值總比較次數(shù)最多。A按排序碼值從小到大排列 B按排序碼值從大到小排列C隨機(jī)排列(完全無(wú)序) D基本按排序碼值升序排列7. 用冒泡排序方法對(duì)n個(gè)記錄按排序碼值從小到大排序時(shí)，當(dāng)初始序列是按排序碼值從大到小排列時(shí)，與碼值總比較次數(shù)是 （D） 。An-1 Bn Cn+1 Dn(n-1)28. 下列排序方法中，與排序碼值總比較次數(shù)與待排序記錄的初始序列排列狀態(tài)無(wú)關(guān)的是 (D) 。A直接插入排序 B冒泡排序 C快速排序 D直接選擇排序9. 將6個(gè)不同的整數(shù)進(jìn)行排序，至少需要比較 (A) 次。A5 B6 C15 D2110

28、. 將6個(gè)不同的整數(shù)進(jìn)行排序，至多需要比較 (C) 次。A5 B6 C15 D2111. *若需要時(shí)間復(fù)雜度在O(nlog2n)內(nèi)，對(duì)整數(shù)數(shù)組進(jìn)行排序，且要求排序方法是穩(wěn)定的，則可選擇的排序方法是 (B) 。A快速排序 B歸并排序 C堆排序 D直接插入排序12. 當(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í)，無(wú)論待排序序列排列是否有

29、序，采用 （D）方法的時(shí)間復(fù)雜度都是O(n2)。A快速排序 B冒泡排序 C歸并排序 D直接選擇排序15. *堆是一種 (B) 排序。A插入 B選擇 C交換 D歸并16. *若一組記錄的排序碼值序列為40，80，50，30，60，70，利用堆排序方法進(jìn)行排序，初建的大頂堆是 (D) 。A80，40，50，30，60，70B80，70，60，50，40，30C80，70，50，40，30，60 D80，60，70，30，40，5017. 若一組記錄的排序碼值序列為50，80，30，40，70，60利用快速排序方法，以第一個(gè)記錄為基準(zhǔn)，得到一趟快速排序的結(jié)果為（B） 。A30，40，50，60，70

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

31、序 D堆排序22. *給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對(duì)其按字母的字典序列的次序進(jìn)行排列，希爾(Shell)排序的第一趟(d1=5)結(jié)果應(yīng)為（D）。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，H23. 給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對(duì)其按字母的字典序列的次序進(jìn)行排列，冒泡排序(大數(shù)下沉)的第一趟排序結(jié)果應(yīng)為（C）。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

32、，JDA，B，D，C，E，F(xiàn)，I，J，C，H24. 給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對(duì)其按字母的字典序列的次序進(jìn)行排列，快速排序的第一趟排序結(jié)果為（B）。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，H25. *給定排序碼值序列為F，B，J，C，E，A，I，D，C，H，對(duì)其按字母的字典序列的次序進(jìn)行排列，二路歸并排序的第一趟排序結(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，

33、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)的含義，并說(shuō)明四者的關(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)于記錄的“域”, 是數(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ù)

34、泛指所有。數(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)的含義，并舉例說(shuō)明數(shù)據(jù)的邏輯結(jié)構(gòu)通常有哪些。數(shù)據(jù)的邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間的邏輯關(guān)系。即用自然語(yǔ)言描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的，邏輯結(jié)構(gòu)有四種。（一個(gè)得分點(diǎn)）集合結(jié)構(gòu)： 僅同屬一個(gè)集合（結(jié)構(gòu)名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)）線性結(jié)構(gòu): 一對(duì)一（1:1) （結(jié)構(gòu)名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)） 樹(shù) 結(jié) 構(gòu): 一對(duì)多（1:n)（結(jié)構(gòu)名字0.5個(gè)得分點(diǎn)、舉例0.5得分點(diǎn)） 圖 結(jié) 構(gòu): 多對(duì)多 (m:n) （結(jié)構(gòu)名字

35、0.5個(gè)得分點(diǎn)、舉例0.5得分點(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大類(lèi)：順序、鏈?zhǔn)健⑺饕?、散列。（?個(gè)得分點(diǎn)，一個(gè)0.5得分點(diǎn)）區(qū)別：數(shù)據(jù)的邏輯結(jié)構(gòu)屬于用戶視圖，是面向問(wèn)題的，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)屬于具體實(shí)現(xiàn)的視圖，是面向計(jì)算機(jī)的。（一個(gè)得分點(diǎn)）聯(lián)系：一種數(shù)據(jù)的邏輯結(jié)構(gòu)可以用多種存儲(chǔ)結(jié)構(gòu)來(lái)存儲(chǔ)，而采用不同的存儲(chǔ)結(jié)構(gòu)其處理的效率往往不同。（一個(gè)得分點(diǎn)）評(píng)分標(biāo)準(zhǔn)：共5個(gè)得分點(diǎn)，按

36、照每段話各自標(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)）控制結(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ù)值問(wèn)

37、題，涉及到兩個(gè)正整數(shù)，因此使用基本的整數(shù)類(lèi)型就可以解決問(wèn)題。（一個(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）確定性：組成算法的操作必須清晰無(wú)二義性5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)評(píng)分標(biāo)準(zhǔn)，本題共5個(gè)得分點(diǎn)，每個(gè)要點(diǎn)一分。5. 簡(jiǎn)述算法的設(shè)計(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)

38、，本題共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分）樹(shù)形結(jié)構(gòu)：數(shù)據(jù)元素之間一對(duì)多的關(guān)系。（1.5分）圖形結(jié)構(gòu)：數(shù)據(jù)元素之間多對(duì)多的關(guān)系。（1.5分）8. 請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩個(gè)標(biāo)準(zhǔn)，以及各自作用。時(shí)間復(fù)雜度：評(píng)估算法運(yùn)行所需時(shí)間。（1.5+1分）空間復(fù)雜度：評(píng)估算法運(yùn)行時(shí)所需最大存儲(chǔ)空間。（1.5+1分）9

39、. 請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)結(jié)構(gòu)，以及他們的特點(diǎn)。（5分）（1）線性結(jié)構(gòu)：數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素。（2分）（2）樹(shù)結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。（1.5分）（3）圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素，零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。（1.5分）10. 評(píng)價(jià)算法的主要標(biāo)準(zhǔn)是什么？（1）算法實(shí)現(xiàn)所耗費(fèi)的時(shí)間（2分）（2）算法實(shí)現(xiàn)所耗費(fèi)的存儲(chǔ)空間，其中主要考慮輔助存儲(chǔ)空間。（2分）（3）算法應(yīng)易于理解、易于編碼、易于調(diào)試。（1分）11. 請(qǐng)說(shuō)出三種邏輯數(shù)據(jù)結(jié)構(gòu)，并分別畫(huà)圖表示它們。（a, 2分，b,c各1.5分）12. 算法的基本性質(zhì)有

40、哪些？并簡(jiǎn)述每個(gè)特性。(5分)（1）有窮性. . . . . （1分）（2）確定性. . . . . （1分）（3）可行性. . . . . （1分）（4）輸入性. . . . . （1分）（5）輸出性. . . . . （1分）13. 通常從那幾個(gè)方面來(lái)評(píng)價(jià)算法的質(zhì)量? (5分)通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：正確性、可讀性、健壯性和高效性。（少一個(gè)扣1分）14. 請(qǐng)描述線性數(shù)據(jù)結(jié)構(gòu)的兩種存儲(chǔ)方式，并說(shuō)出其各有什么特點(diǎn)。順序存儲(chǔ)：連續(xù)存儲(chǔ)，易于定位，不易于插入和刪除。分）鏈?zhǔn)酱鎯?chǔ)：非連續(xù)存儲(chǔ)，不易于定位，易于插入和刪除。分）15. 請(qǐng)問(wèn)算法的分析和評(píng)價(jià)的兩種方法，它們關(guān)注點(diǎn)各有什么不同？（簡(jiǎn)單

41、）空間效率：關(guān)注算法對(duì)內(nèi)存的占用度。分）時(shí)間效率：關(guān)注算法的運(yùn)算速度。分）第二章 線性表1. 請(qǐng)問(wèn)如果要插入一個(gè)數(shù)據(jù)到一個(gè)線性表中，順序表和鏈表哪個(gè)的效率高？為什么？鏈表的效率高（2分），因?yàn)轫樞虮硪苿?dòng)插入位置后的每一個(gè)元素的位置給新數(shù)據(jù)騰位置分）。鏈表只需要將前一個(gè)數(shù)據(jù)的指針指向新數(shù)據(jù)并將新數(shù)據(jù)的指針指向后一個(gè)數(shù)據(jù)即可分）。2. 線性表有哪些特點(diǎn)？1）除第一個(gè)和最后一個(gè)數(shù)據(jù)元素外，每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素和一個(gè)后繼數(shù)據(jù)元素；（2分）2）第一個(gè)數(shù)據(jù)元素沒(méi)有前驅(qū)數(shù)據(jù)元素；（1.5分）3）最后一個(gè)數(shù)據(jù)元素沒(méi)有后繼數(shù)據(jù)元素。（1.5分）3. 順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)有哪些? (中等)順序存儲(chǔ)結(jié)

42、構(gòu)的優(yōu)點(diǎn):（2.5分）存儲(chǔ)空間連續(xù)邏輯相鄰，物理相鄰可隨機(jī)存取任一元素缺點(diǎn):（2.5分）插入、刪除操作需要移動(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):（2.5分）不需預(yù)先分配空間，空間利用充分插入、刪除操作簡(jiǎn)單, 無(wú)需移動(dòng)大量的元素表容量易于擴(kuò)充缺點(diǎn):（2.5分）每個(gè)數(shù)據(jù)元素，除存儲(chǔ)本身信息外，還需空間存儲(chǔ)其直接后繼的信息邏輯相鄰，物理不一定相鄰不可隨機(jī)存取任一元素, 只能從鏈表頭依次查找.5. 有順序表A=(a0, a1, a2,.a8,a9,a19)，要在a8,a9之間插入一個(gè)元素a20，請(qǐng)描述其操

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

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

45、描述從一個(gè)單鏈表中刪除一個(gè)數(shù)據(jù)的刪除過(guò)程。（1）找到將被刪除數(shù)據(jù)的前一個(gè)結(jié)點(diǎn)p; （2分）（2）p的next指針指向被刪除數(shù)據(jù)的后一個(gè)結(jié)點(diǎn)；（2分）（3）將被刪除數(shù)據(jù)原來(lái)的next指針指向null; （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)問(wèn)答：這種數(shù)制轉(zhuǎn)換可以借助于哪種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)、及原因。答:棧。（2分）原因：（

46、3分）在進(jìn)行數(shù)值轉(zhuǎn)換時(shí)，其實(shí)質(zhì)是求余的過(guò)程，并且余數(shù)的倒序序列正是所求結(jié)果。棧是一種先進(jìn)后出的線性結(jié)構(gòu)，能夠滿足這種操作。3. 有一字符序列abcde依次按照某一線性結(jié)構(gòu)存儲(chǔ)，請(qǐng)回答以下問(wèn)題：（1）、如果該線性結(jié)構(gòu)是隊(duì)列，那么，寫(xiě)出出隊(duì)序列。（2）、如果該線性結(jié)構(gòu)是棧，那么，輸出序列可能是d,c,e,a,b嗎，為什么？（3）、如果該線性結(jié)構(gòu)是棧，且輸出序列是abcde。請(qǐng)寫(xiě)出操作過(guò)程。（push (x)：表示把x壓入棧內(nèi)；pop (x)：表示把x彈出棧）答：（1）、abcde（1分）（2）、不可能，因?yàn)椋篸是第一出棧字符，說(shuō)明a,b已別壓入棧內(nèi)；并且壓入棧的次序?yàn)閍bcde；由以上得出：ab出

47、棧的順序只能是b、a，而不是a、b。所以，出棧序列d,c,e,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)。相同點(diǎn)：棧和隊(duì)列都是只允許在表的端點(diǎn)處進(jìn)行插入、刪除操作的線性表。（2分）不同點(diǎn)：棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是后進(jìn)先出。（3分）5. 若依次讀入數(shù)據(jù)元素序列1、2、3，進(jìn)棧的過(guò)程中允許出棧，試寫(xiě)出各種可能的出棧序列。答:123、132、213、231、321（各1分）6. 如果入棧序列有組成, 請(qǐng)問(wèn)輸出

48、序列可能有哪些? (較難)輸出序列有5種：C B A, B C A, B A C, A C B , A B C（各1分）7. 如果有abcde五個(gè)數(shù)據(jù)依次全部存入，如果采用隊(duì)列和棧來(lái)進(jìn)行存儲(chǔ)，依次取出分別將獲得什么內(nèi)容。（簡(jiǎn)單）隊(duì)列：abcde （2.5分）棧: edcba （2.5分）8. 設(shè)將整數(shù) 1，2，3，4依次進(jìn)棧，能否得到1423出棧序列和1432?并說(shuō)明為什么不能得到或者如何得到。（中等）不能得到1423，但可以得到1432（2分）因?yàn)橐玫?必須將所有數(shù)據(jù)入棧，這樣將只能依次獲取到1432不能獲得1423。采用push、pop、push、push、push、pop、pop、po

49、p可以獲得1432。（3分）9. 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿？(可不考)循環(huán)隊(duì)列的優(yōu)點(diǎn)是可以克服順序隊(duì)列的"假上溢"現(xiàn)象，能夠使存儲(chǔ)隊(duì)列的向量空間得到充分的利用。（3分）采用犧牲一個(gè)元素空間的方法，循環(huán)隊(duì)列隊(duì)空的條件是front=rear，循環(huán)隊(duì)列隊(duì)滿的條件是：(rear+1)%M=front。（2分）第四章 串1. 對(duì)于字符串S=abcde，請(qǐng)問(wèn)：（簡(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

50、、 abcd、 bcde、 abcde、。（3分）2. 對(duì)于字符串S=12345，請(qǐng)問(wèn)：（簡(jiǎn)單）（1）字符串S的長(zhǎng)度是多少？（2）字符串S的子串有幾個(gè)，并列出所有子串？答：（1）、5 （1分）（2）、16，（1分）所有字串：1、2、3、4、5、 12、 23、 34 、45、123、 234、 345、 1234、 2345、 12345、。（3分）3. 請(qǐng)問(wèn)答：什么串的模式匹配？模式匹配算法有幾種？（簡(jiǎn)單）答：串的模式匹配是指子串的定位運(yùn)算，即在主串中查找子串第一次出現(xiàn)的位置。 模式匹配算法有兩種：簡(jiǎn)單匹配算法(Brute-Force)、KMP算法。（該題共4個(gè)得分點(diǎn)，答對(duì)串匹配定義或大意基

51、本相同，得 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）、*畫(huà)出數(shù)組iAry的順序存儲(chǔ)結(jié)構(gòu)。（規(guī)定：整型長(zhǎng)度為兩個(gè)字節(jié)）（1）、int iAry5= 10、20、30、40、50 （2 分）（2）、如下圖：（3分，根據(jù)情況，酌情扣分）2. 簡(jiǎn)述數(shù)組的定義、特點(diǎn)和分類(lèi)。（簡(jiǎn)單）定義：數(shù)組是n個(gè)相同數(shù)據(jù)類(lèi)型的數(shù)據(jù)元素a0,a1,a2,.,an-1構(gòu)成的有限集合。（1個(gè)得分點(diǎn)）特點(diǎn)：1）數(shù)組中各元素具有統(tǒng)一的

52、類(lèi)型；（1個(gè)得分點(diǎn)）2）數(shù)組元素的下標(biāo)一般具有固定的上界和下界，即數(shù)組一旦被定義，它的維數(shù)和維界就不再改變。（1個(gè)得分點(diǎn)）3數(shù)組的基本操作比較簡(jiǎn)單，除了結(jié)構(gòu)的初始化和銷(xiāo)毀之外，只有存取元素和修改元素值的操作。（1個(gè)得分點(diǎn)）分類(lèi)：按維度可分為一維數(shù)組、二維數(shù)組、多維數(shù)組（1個(gè)得分點(diǎn)）3. 已知一個(gè)二維數(shù)組A如下所示。（較難）（1）請(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ǔ)的地址為，每個(gè)元素的存儲(chǔ)空間大小為L(zhǎng)，則按照行優(yōu)先的方式和列優(yōu)先的方式分別存儲(chǔ)，其中

53、a22的地址loc(a22)分別為多少（2個(gè)得分點(diǎn)）行優(yōu)先：loc(a22)=+4L列優(yōu)先：loc(a22)=+3L（3）對(duì)于數(shù)組，除了順序存儲(chǔ)外，還有沒(méi)有其他存儲(chǔ)方式？沒(méi)有填無(wú)，若有，請(qǐng)說(shuō)明。有，鏈?zhǔn)酱鎯?chǔ)，如下圖所示（1個(gè)得分點(diǎn)）第六章 樹(shù)和二叉樹(shù)1. 有一樹(shù)，如下圖所示： （簡(jiǎn)單）請(qǐng)回答以下問(wèn)題：（1）樹(shù)的葉子結(jié)點(diǎn)及其度。（2）非終端結(jié)點(diǎn)及其度。（3）樹(shù)的深度。答： （1）、葉子結(jié)點(diǎn)有：D 、E、F、G，它們的度都為零。（2分）（2）、非終端結(jié)點(diǎn)有：A 度為3，B 度為2，C 度為1。（2分）（3）、樹(shù)的深度為3。（1分）2. 請(qǐng)回答：樹(shù)與二叉樹(shù)有什么區(qū)別？（中等）答：區(qū)別有兩點(diǎn)：(1)二叉樹(shù)的一個(gè)結(jié)點(diǎn)至多有兩個(gè)子樹(shù)，樹(shù)則不然。（2.5分）(2)二叉樹(shù)一個(gè)結(jié)點(diǎn)的子樹(shù)有左右之分，而樹(shù)的子樹(shù)沒(méi)有次序。（2.5分）3. 有一棵具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)。請(qǐng)問(wèn)：該滿二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)目是多少，并寫(xiě)出分析推理過(guò)程。（中等）答：(n+1)/2。（2分）分析過(guò)程：滿二叉樹(shù)中只有度為2和度為0的結(jié)點(diǎn)，故設(shè)葉子結(jié)點(diǎn)數(shù)目為：n