數(shù)據(jù)結(jié)構(gòu)習(xí)題講解

《數(shù)據(jù)結(jié)構(gòu)習(xí)題講解》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)習(xí)題講解（78頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第 1章 緒論 一、 判斷題 1. 數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。 （√） 2. 一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。 （√） 3. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 （） 4. 數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。 （） 5. 程序和算法原則上沒(méi)有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。 （） 6. 從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 （√） 7. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象。 （√） 8. 數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式

2、。 （√） 9. 數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。 （） 10. 算法是對(duì)解題方法和步驟的描述。 （√） 二、填空題 1. 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲(chǔ)結(jié)構(gòu) 兩種結(jié)構(gòu)。 2. 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu) 。 3. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu) 。 4. 樹形結(jié)構(gòu) 和圖形結(jié)構(gòu) 合稱為非線性結(jié)構(gòu)。 5. 在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有 1 個(gè)前驅(qū)結(jié)點(diǎn)。 6. 在圖

3、形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個(gè) 。 7. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu) 。 8. 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ) 。 9. 線性結(jié)構(gòu)中的元素之間存在一對(duì)一 的關(guān)系。 10. 樹形結(jié)構(gòu)中的元素之間存在一對(duì)多 的關(guān)系。 11. 圖形結(jié)構(gòu)的元素之間存在多對(duì)多 的關(guān)系。 12. 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法（或運(yùn)算） 3 個(gè)方面的內(nèi)容。 13.

4、 數(shù)據(jù)結(jié)構(gòu)被定義為（ D， R），其中 D 是數(shù)據(jù)的有限集合， R是 D 上的關(guān)系 有限集合。 14. 算法是一個(gè)有窮指令 的集合。 15. 算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法 。 16. 一個(gè)算法的時(shí)間復(fù)雜度是算法 輸入規(guī)模 的函數(shù)。 17. 算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間 ，它是該算法求解問(wèn)題規(guī)模的 n 的函數(shù)。 18. 若一個(gè)算法中的語(yǔ)句頻度之和為 T(n)=6n+3nlog 2 n, 則算法的時(shí)間復(fù)雜度為 O（ nlog

5、 n）。 2 19. 若一個(gè)算法的語(yǔ)句頻度之和為 T(n)=3n+nlog 2+n2, 則算法的時(shí)間復(fù)雜度為 O（ n2） 。 20. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序問(wèn)題中計(jì)算機(jī)的操作對(duì)象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。 三、選擇題 1 1. 數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（ A）及它們之間的相互關(guān)系。 A．存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu) B ．存儲(chǔ)和抽象 C ．聯(lián)系和抽象 D ．聯(lián)系與邏輯 2. 在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C）。 A．動(dòng)態(tài)結(jié)

6、構(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)。 3. 數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（ C）。 A．存儲(chǔ)結(jié)構(gòu) B ．邏輯結(jié)構(gòu) C ．順序存儲(chǔ)結(jié)構(gòu) D ．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 4. 非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)（ D）。 A．無(wú)直接前驅(qū)結(jié)點(diǎn)． B ．無(wú)直接后繼結(jié)點(diǎn)． C．只有一個(gè)直接前驅(qū)結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn) D．可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn) 5. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ A）。 A．分兩部分，一部分存放結(jié)點(diǎn)的值，另一個(gè)部分存放

7、表示結(jié)點(diǎn)間關(guān)系的指針。 B．只有一部分，存放結(jié)點(diǎn)的值。 C ．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針。 D．分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放結(jié)點(diǎn)所占單元素 6. 算法的計(jì)算量大小稱為算法的（ C）。 A．現(xiàn)實(shí)性 B ．難度 C ．時(shí)間復(fù)雜性 D ．效率 7. 數(shù)據(jù)的基本單位（ B）。 A．?dāng)?shù)據(jù)結(jié)構(gòu) B ．?dāng)?shù)據(jù)元素 C ．?dāng)?shù)據(jù)項(xiàng) D ．文件 8. 每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間里，這種存儲(chǔ)結(jié)構(gòu)稱為（ A）結(jié)構(gòu)。 A．順序結(jié)構(gòu) B ．鏈?zhǔn)浇Y(jié)構(gòu) C ．索引結(jié)構(gòu)

8、 D ．散列結(jié)構(gòu) 9. 每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是（ B）。 A．順序 B ．鏈?zhǔn)? C ．索引 D ．散列 10. 以下任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有邏輯關(guān)系的是（ D）。 2 A．圖形結(jié)構(gòu) B ．線性結(jié)構(gòu) C ．樹形結(jié)構(gòu) D ．集合 11. 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是（ C）。 A．物理結(jié)構(gòu) B ．存儲(chǔ)結(jié)構(gòu) C ．邏輯結(jié)構(gòu) D ．邏輯和存儲(chǔ)結(jié)構(gòu) 12. 下列 4 種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（ A）。

9、 A．集合 B ．線性結(jié)構(gòu) C ．樹形結(jié)構(gòu) D ．圖形結(jié)構(gòu) 13. 與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（ A）。 A．邏輯結(jié)構(gòu) B ．存儲(chǔ)結(jié)構(gòu) C ．邏輯實(shí)現(xiàn) D ．存儲(chǔ)實(shí)現(xiàn) 14. 每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，存儲(chǔ)結(jié)點(diǎn)存放在連續(xù)的存儲(chǔ)空間，另外有一組指明結(jié)點(diǎn)存儲(chǔ)位置的表，該存儲(chǔ)方式是（ C）存儲(chǔ)方式。 A．順序 B ．鏈?zhǔn)?C ．索引 D ．散列 15. 算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的（ A）。 A．正確性 B ．易讀性 C ．健壯性 D ．高效性 16. 算法

10、在發(fā)生非法操作時(shí)可以作出相應(yīng)處理的特性稱為算法的（ C）。 A．正確性 B ．易讀性 C ．健壯性 D ．高效性 17. 下列時(shí)間復(fù)雜度中最壞的是（ D）。 A． O（ 1） B.O （ n） C.O( log 2n) D.O(n 2) 18. 下列算法的時(shí)間復(fù)雜度是（ D）。 for(i=0;i

11、 空間復(fù)雜性和時(shí)間復(fù)雜性 B. 正確性和簡(jiǎn)明性 C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 3 20. 計(jì)算機(jī)算法必須具備輸入、輸出和（ C）。 A. 計(jì)算方法 B. 排序方法 C. 解決問(wèn)題的有限運(yùn)算步驟 D. 程序設(shè)計(jì)方法

12、 4 第 2 章 線性表 一、判斷題 1. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。 （） 2. 鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。 （） 3. 在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。 （√） 4. 順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。 （） 5. 線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向 前移動(dòng)。 （） 6. 順序

13、表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 （） 7. 線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。 （√） 8. 線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 （√） 9. 順序表結(jié)構(gòu)適宜進(jìn)行順序存取，而鏈表適宜進(jìn)行隨機(jī)存取。 （） 10. 插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。（） 二、填空題 1. 順序表中邏輯上相鄰的元素在物理位置上必須相鄰。 2. 線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一關(guān)系。 3. 順序表相對(duì)于鏈表的優(yōu)點(diǎn)是節(jié)

14、省存儲(chǔ)和隨機(jī)存取。 4. 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便。 5. 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的 元素時(shí)，應(yīng)采用 順序 存儲(chǔ)結(jié)構(gòu)。 6. 順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O（ 1）。 7. 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小。 8. 在雙向鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *P，其時(shí)間復(fù)雜度為 O（1）。 9. 在單向鏈表中要在已知結(jié)點(diǎn) *P 之前插入一個(gè)新結(jié)點(diǎn)，需找到 *P 的直接前驅(qū)結(jié)點(diǎn)的地址，其查找的 時(shí)間復(fù)雜度為 O(n) 。 10. 在單向

15、鏈表中需知道頭指針才能遍歷整個(gè)鏈表。 11. 線性表中第一個(gè)結(jié)點(diǎn)沒(méi)有直接前驅(qū)，稱為開始結(jié)點(diǎn)。 12. 在一個(gè)長(zhǎng)度為 n 的順序表中刪除第 i 個(gè)元素，要移動(dòng)n-i 個(gè)元素。 13. 在一個(gè)長(zhǎng)度為 n 的順序表中，如果要在第 i 個(gè)元素前插入一個(gè)元素，要后移 n-i+1個(gè)元素。 14. 在無(wú)頭結(jié)點(diǎn)的單向鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其他結(jié)點(diǎn)的存儲(chǔ)地址存放在 前趨結(jié)點(diǎn)的指針域中。 15. 線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用 鏈子 存儲(chǔ)結(jié)構(gòu)。 16. 在線性表中的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯

16、關(guān)系是通過(guò) 指針 決定。 5 17. 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其 前趨 結(jié)點(diǎn)，另一個(gè)指向其后繼 結(jié)點(diǎn)。 18. 對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用 鏈?zhǔn)? 存儲(chǔ)結(jié)構(gòu)為宜。 19. 雙向鏈表中，設(shè) P 是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為 p->prior->next=p->next； p->next->prior=p->prior 20. 在如圖所示的鏈表中，若在指針 P 所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為 a 和 b 的兩個(gè)結(jié)點(diǎn)，

17、則可用語(yǔ) 句 S->next->next=p->next和 P-> next=S ；來(lái)實(shí)現(xiàn)該操作。 p ∧ a b s 三、 選擇題 1. 在具有 n 個(gè)結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)（ A ）的操作，其算法的時(shí)間復(fù)雜度都是 O(n). A. 遍歷鏈表或求鏈表的第 i 個(gè)結(jié)點(diǎn) B. 在地址為 P 的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) C. 刪除開始結(jié)點(diǎn) D. 刪除地址為 P 的結(jié)點(diǎn)的后繼結(jié)點(diǎn) 2. 設(shè) a、 b、 c 為 3 個(gè)結(jié)點(diǎn)，

18、p、10、 20 分別代表它們的地址，則如下的存儲(chǔ)結(jié)構(gòu)稱為（ B ）。 p a 10 b 20 c ∧ A．循環(huán)鏈表 B ．單向鏈表 C ．雙向循環(huán)鏈表 D ．雙向鏈表 3. 單向鏈表的存儲(chǔ)密度（ C ）。 A. 大于 1 B. 等于 1 C. 小于 1 D. 不能確定 6 4. 已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占 m個(gè)存儲(chǔ)單元，若第一個(gè)結(jié)點(diǎn)的地址為 B，則第 i 個(gè)結(jié)點(diǎn) 的地址為（ A ）。 A.B+(i-1)

19、 m B.B+i m C.B-i m D.B+(i+1) m 5. 在有 n 個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為（ B ）。 A． O（ 1） B.O （ n） C. O(n 2) D.O( log 2n) 6. 設(shè) front 、 rear 分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，則指針 P 所指的元素是雙循環(huán)鏈表 L 的 尾元素的條件是（ D ）。 A.P= =L B.P->front= =L C.P= =NULL D.P->rear= =L

20、 7. 兩個(gè)指針 P 和 Q，分別指向單向鏈表的兩個(gè)元素， P 所指元素是 Q所指元素前驅(qū)的條件是（B ） A ．P->next= =Q->next B.P->next= =Q C.Q->next= =P D.P==Q 8. 用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是（ C ）。 A ．便于隨機(jī)存取 B．花費(fèi)的存儲(chǔ)空間比順序表少 C．便于插入和刪除 D ．?dāng)?shù)據(jù)元素的物理順序與邏輯順序相同 9. 在單鏈表中，增加頭結(jié)點(diǎn)的目的是（ C ）。 A ．使單鏈表至少有一個(gè)結(jié)點(diǎn) B ．標(biāo)志表中首結(jié)

21、點(diǎn)的位置 C．方便運(yùn)算的實(shí)現(xiàn) D ．說(shuō)明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 10. 下面關(guān)于線性表的敘述中，錯(cuò)誤的是（ D ）關(guān)系。 A ．順序表必須占一片地址連續(xù)的存儲(chǔ)單元 B．順序表可以隨機(jī)存取任一元素 C．鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元 D．鏈表可以隨機(jī)存取任一元素 11. L 是線性表，已知 LengthList(L) 的值是 5，經(jīng) DelList(L ， 2) 運(yùn)算后， LengthList(L) 的值是（ C ）。 A ． 2 B ． 3 C ． 4 D ． 5 12. 單向鏈表的示意圖如下：

22、L A B C D ∧ 7 P Q R 指向鏈表 Q結(jié)點(diǎn)的前驅(qū)的指針是（ B ）。 A． L B ． P C ． Q D ．R 13. 設(shè) p 為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則 *p 的直接前驅(qū)（ C ）。 A．找不到 B ．查找時(shí)間復(fù)雜度為 O（ 1） C．查找時(shí)間復(fù)雜度為 O（ n） D．查找結(jié)點(diǎn)的次數(shù)約為 n 14. 等概率

23、情況下，在有 n 個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為（ 8 ）。 A． n B.(n-1)/2 C.n/2 D.(n+1)/2 15. 在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其余各結(jié)點(diǎn)的是（ C ）。 A. 雙向鏈表 B. 單循環(huán)鏈表 C.單向鏈表 D. 雙向循環(huán)鏈表 16. 在順序表中，只要知道（ D ），就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。 A. 基地址 B. 結(jié)點(diǎn)大小 C. 向量大小 D. 基地址和結(jié)點(diǎn)大小 17. 在雙向鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為（

24、A ）。 A． O（ 1） B.O （ n） C. O(n 2) D.O( log 2n) 18. 鏈表不具備的特點(diǎn)是（ A ）。 A．隨機(jī)訪問(wèn) B. 不必事先估計(jì)存儲(chǔ)空間 C. 插入刪除時(shí)不需要移動(dòng)元素 D. 所需空間與線性表成正比 19. 以下關(guān)于線性表的論述，不正確的為（ C ）。 A. 線性表中的元素可以是數(shù)字、字符、記錄等不同類型 B. 線性順序表中包含的元素個(gè)數(shù)不是任意的 C. 線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼 D. 存在這樣的線性表，即表中沒(méi)有任何結(jié)點(diǎn) 2

25、0. 在（ B ）的運(yùn)算中，使用順序表比鏈表好。 A. 插入 B. 根據(jù)序號(hào)查找 C. 刪除 D. 根據(jù)元素查找 8 第 3 章 棧 一、 判斷 1. 是運(yùn)算受限制的 性表。 （√） 2. 在 空的情況下，不能作出 操作，否 生下溢。 （√） 3. 一定是 序存 的 性 構(gòu)。 （） 4. 的特點(diǎn)是“后 先出”。 （√） 5. 空 就是所有元素都 0 的 。 （） 6. 在 C（或 C++）

26、 言中 序 的 度 MAXLEN， top=MAXLEN 表示 。 （） 7. 與 序 相比，其特點(diǎn)之一是通常不會(huì)出 的情況。 （√） 8. 一個(gè) 的 入序列 ： A， B， C， D，可以得到 出序列： C， A， B， D。 （） 9. 定 就是循 定 。 （） 10. 將十 制數(shù) 二 制數(shù)是 的典型 用之一。 （√） 二、填空 1. 在 構(gòu)中，允 插入、 除的一端稱 棧頂 。 2. 在 序 中，當(dāng) 指 top=-1 ，表示 空 。 3. 在有

27、 n 個(gè)元素的 中， 操作 復(fù) 度 O （ 1） 。 4. 在 中，出 操作 復(fù) 度 O（ 1） 。 5. 已知表達(dá)式，求它的后 表達(dá)式是 棧 的典型 用。 6. 在一個(gè) 中，若 指 等于 NULL， 表示 空 。 7. 向一個(gè) 指 top 的 插入一個(gè)新 點(diǎn) *p ， 行 p->next=top;top=p ；操作。 8. 序 S 存 在數(shù) S->data[0 ? MAXLEN-1]中， 操作 要 行的 句有： S->top++ 。 ( 或 S->top+1)

28、 S->data[S->top]=x 9. 鏈棧 LS，指向 元素的指 是 LS->next 。 10. 從一個(gè) 除元素 ，首先取出 棧頂元素 ，然后再移 指 。 11. 由于 的操作只在 表的 部 行，所以沒(méi)有必要 置 頭 點(diǎn)。 12. 已知 序 S，在 S 操作之前首先要判斷 是否 。 13. 已知 序 S，在 S 出 操作之前首先要判斷 是否空 。 14. 若內(nèi)在空 充足， 鏈 可以不定 運(yùn)算。 15. 鏈棧 LS 空的條

29、件是 LS->next=NULL 。 16. 鏈棧 LS 的 元素是 表的 首 元素。 17. 同一 的各元素的 型 相同 。 18. 若 的次序是 A、 B、 C、 D、E， 行 3 次出 操作以后， 元素 B 。 19. A+B/C-D*E 的后 表達(dá)式是 ABC/+DE*- 。 20. 4 個(gè)元素 A、 B、 C、D 序 S ， 行兩次 Pop(S,x) 運(yùn)算后， x 的 是C 。 9 三、

30、選擇題 1. 插入和刪除操作只能在一端進(jìn)行的線性表，稱為（ C ）。 A．隊(duì)列 B ．循環(huán)隊(duì)列 C ．棧 D ．循環(huán)棧 2. 設(shè)有編號(hào)為 1， 2。 3， 4 的 4 輛列車，順序進(jìn)入一個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出站順序?yàn)? （ D）。 A． 1234 B ． 1243 C ． 1324 D ． 1423 3. 如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則出棧操作時(shí)（ B ）。 A．必須判別棧是否滿 B ．必須判別棧是否為空 C ．必須判別棧元素類型 D ．棧可不做任何判別

31、 4. 元素 A、 B、 C、 D 依次進(jìn)棧以后，棧頂元素是（D ） A． A B ． B C ． C D ． D 5. 順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（B ）存儲(chǔ)元素。 A．鏈表 B ．?dāng)?shù)組 C ．循環(huán)鏈表 D ．變量 6. 在 C（或 C++）語(yǔ)言中，一個(gè)順序棧一旦被聲明，其占用空間的大?。?A ）。 A．已固定 B ．不固定 C ．可以改變 D ．動(dòng)態(tài)變化 7. 帶頭結(jié)點(diǎn)的鏈棧 LS 的示意圖如下，棧頂元素是（A ）。 LS H A B C D ∧ A． A B ． B C

32、 ． C D ．D 8. 鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（ B ）。 A. 插入操作更加方便 B. 通常不會(huì)出現(xiàn)棧滿的情況 C. 不會(huì)出現(xiàn)?？盏那闆r D. 刪除操作更加方便 9. 從一個(gè)棧頂指針為 top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 （ d ）命令。 A． x=top;top->next; B.top=top->next;x=top->data C.x=top->data; D.x=top->data;top=top->next

33、 10. 在一個(gè)棧頂指針為 HS的鏈棧中，將一個(gè) S 指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列（B ）命令。 A.HS->next=S B.S->next=HS->next;HS->next=S; C.S->next=HS->next;HS=S; D.S->next=HS=HS->next 11. 4 元素按 A、 B、 C、D 順序進(jìn) S 棧，執(zhí)行兩次 Pop(S， x) 運(yùn)算后，棧頂元素的值是（ B ）。 A． A B ． B C ． C D ． D 12. 元素 A、 B、 C、 D 依次進(jìn)棧以后，棧底元素是（A ）。

34、 A． A B ． B C ． C D ． D 13. 經(jīng)過(guò)下列棧的運(yùn)算后，再執(zhí)行 ReadTop(s) 的值是（ A ）。 InitStack(s);Push(s ， a); Push(s ，b);Pob(s); 10 A. a B.b C.1 D.0 14. 經(jīng)過(guò)下列棧的運(yùn)算后， x 的值是（ B ）。 InitStack(s) （初始化棧） ; Push(s ，a); Push(s ， b); ReadTop(s) ； Pob(s ， x); A. a B.b C.1 D.0 15. 經(jīng)過(guò)下列棧的運(yùn)算后，

35、 x 的值是（ B ）。 InitStack(s) （初始化棧） ; Push(s,a); Pob(s ， x); Push(s,b); Pob(s ， x); A.a B.b C.1 D.0 16. 經(jīng)過(guò)下列棧的運(yùn)算后 ,SEmpty(s) 的值是（ C ）。 InitStack(s) （初始化棧） ; Push(s,a); Push(s,b); Pob(s ， x); Pob(s ， x); A.a B.b C.1 D.0 17. 向順序棧中輸入元素時(shí)（ B ）。 A．先存入元素，后移動(dòng)棧頂指針B．先移動(dòng)棧頂指

36、針，后存入元素 C．誰(shuí)先誰(shuí)后無(wú)關(guān)緊要 D ．同時(shí)進(jìn)行 18. 初始化一個(gè)空間大小為 5 的順序棧 S 后， S->top 的值是（ B ）。 A． 0 B ．-1 C ．不再改變 D ．動(dòng)態(tài)變化 19. 設(shè)有一個(gè)入棧的次序 A、 B、 C、 D、 E，則棧不可能的輸出序列是（C ）。 A． EDCBA B ．DECBA C ． DCEAB D ． ABCDE 20. 設(shè)有一個(gè)順序棧 S，元素 A、 B、 C、 D、 E、 F 依次進(jìn)棧，如果 6 個(gè)元素出棧的順序是 B、 D、 C、 F、 E、A，則棧的容量至少應(yīng)是（ A ）。 A．

37、3 B ．4 C ． 5 D ． 6 11 第 4 章 隊(duì)列 一、判斷題 1. 隊(duì)列是限制在兩端進(jìn)行操作的線性表。 （√） 2. 判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個(gè)結(jié)點(diǎn)。 （√） 3. 在鏈隊(duì)列上做出隊(duì)操作時(shí)，會(huì)改變 front 指針的值。 （） 4. 在循環(huán)隊(duì)列中，若尾指針 rear 大于頭指針 front ，其

38、元素個(gè)數(shù)為 rear-front 。 （√） 5. 在單向循環(huán)鏈表中，若頭指針為 h，那么 p 所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。 （） 6. 鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。 （√） 7. 在循環(huán)鏈隊(duì)列中無(wú)溢出現(xiàn)象。 （） 8. 棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。 （） 9. 在隊(duì)列中允許刪除的一端稱為隊(duì)尾。 （） 10. 順序隊(duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的。 （） 二、填空題 1. 在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是 先進(jìn)先出 。 2. 隊(duì)列 是被限定為只能在

39、表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除運(yùn)算線性表。 3. 在隊(duì)列中，允許插入的一端稱為 隊(duì)尾 。 4. 在隊(duì)列中，允許刪除的一端稱為 隊(duì)首（或隊(duì)頭） 。 5. 隊(duì)列在進(jìn)行出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為 空 。 6. 順序隊(duì)列在進(jìn)行入隊(duì)操作時(shí)，首先在判斷隊(duì)列是否為 滿 。 7. 順序隊(duì)列初始化后，初始化后，front=rear= -1 。 8. 解決順序隊(duì)列“假溢出”的方法是采用 循環(huán)隊(duì)列 。 9. 循環(huán)隊(duì)列的隊(duì)指針為 front ，隊(duì)尾指針為 r

40、ear ，則隊(duì)空的條件為 front= =rear 。 10. 鏈隊(duì)列 LQ為空時(shí)， LQ->front->next= NULL 。 11. 設(shè)長(zhǎng)度為 n 的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 O(n) 。 12. 設(shè)長(zhǎng)度為 n 的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)尾指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 O(1) 。 13. 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 空 。 14. 設(shè)循環(huán)隊(duì)列的頭指針 front 指向隊(duì)首元素，尾指針 rear 指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列

41、的最 大空間為 MAXLEN，則隊(duì)滿標(biāo)志為 front= =(rear+1)%MAXLEN 。 15. 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為 front ，隊(duì)尾指針為 rear ，則判斷隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為front= =rear 或 front! 。 16. 向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷 隊(duì)尾指針 ，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。 17. 讀隊(duì)首元素的操作 不改變或不影響隊(duì)列元素的個(gè)數(shù)。 18. 設(shè)循環(huán)隊(duì)列的容量為 40（序號(hào) 0～ 39），現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)的運(yùn)算后， front=11

42、 ，rear=19 ， 則循環(huán)隊(duì)列中還有 8 個(gè)元素。 12 19. 隊(duì)列 Q，經(jīng)過(guò)下列運(yùn)算： InitQueue(Q)( 初始化隊(duì)列 ) ； InQueue(Q,a) ； InQueue(Q,b) ； OutQueue(Q,x) ； ReadFront(Q,x) ； QEmpty(Q)；后的值是 8 。 20. 隊(duì)列 Q經(jīng)過(guò) InitQueue(Q)( 初始化隊(duì)列 ) ； InQueue(Q,a) ； InQueue(Q,b) ；ReadFront(Q,x) 后， x 的值 是a

43、。 三、選擇題 1. 隊(duì)列是限定在（ D）進(jìn)行操作的線性表。 A．中間者 B. 隊(duì)首 C. 隊(duì)尾 D. 端點(diǎn) 2. 隊(duì)列中的元素個(gè)數(shù)是（ B）。 A．不變的 B. 可變的 C. 任意的 D.0 3. 同一隊(duì)列內(nèi)的各元素的類型（ A）。 A. 必須一致 B. 不能一致 C. 可以不一致 D. 不限制 4. 隊(duì)列是一個(gè)（ C）線性表結(jié)構(gòu)。 A. 不加限制的 B. 推廣了的 C. 加了限制的 D. 非 5. 當(dāng)利用大小為 n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為（

44、B）。 A.n-2 B.n-1 C.n D.n+1 6. 一個(gè)循環(huán)隊(duì)列一旦說(shuō)明，其占用空間的大?。? A）。 A. 已固定 B. 可以變動(dòng) C. 不能固定 D. 動(dòng)態(tài)變化 7. 循環(huán)隊(duì)列占用的空間（ A）。 A. 必須連續(xù) B. 不必連續(xù) C. 不能連續(xù) D. 可以不連續(xù) 8. 存放循環(huán)隊(duì)列元素的數(shù)組 data 有 10 個(gè)元素，則 data 數(shù)組的下標(biāo)范圍是（ B）。 A.0 ～ 10 B.0 ～ 9 C.1 ～ 9 D.1 ～ 10 9. 若進(jìn)隊(duì)的序列為 A、 B、 C、 D，則出隊(duì)

45、的序列是（ C）。 A.B 、 C、 D、 A B.A 、 C、 B、 D C.A 、 B、 C、 D D.C 、 B、 D、 A 10. 4 個(gè)元素按 A、 B、 C、 D 順序連續(xù)進(jìn)隊(duì) Q，則隊(duì)尾元素是（ D） A． A B ． B C ． C D ． D 11. 4 個(gè)元素按 A、 B、 C、 D 順序連續(xù)進(jìn)隊(duì) Q，執(zhí)行一次 QutQueue(Q) 操作后，隊(duì)頭元素是（ B）。 A.A B.B C.C D.D 12. 4 個(gè)元素按 A、 B、 C、 D 順序連續(xù)進(jìn)隊(duì) Q，執(zhí)行 4 次 QutQueue(Q) 操作后，再執(zhí)行 QEmpt

46、y(Q)；后的值是（ B）。 A.0 B.1 C.2 D.3 13. 隊(duì)列 Q，經(jīng)過(guò)下列運(yùn)算后， x 的值是（ B）。 InitQueue(Q)( 初始化隊(duì)列 ) ； InQueue(Q,a) ； InQueue(Q,b) ； OutQueue(Q,x) ； ReadFront(Q,x) ； A.a B.b C.0 D.1 14. 循環(huán)隊(duì)列 SQ隊(duì)滿的條件是（ B）。 A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front 13 C.SQ->rear= =0 D.

47、SQ->front= =0 15. 設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)： data 為數(shù)據(jù)域， next 為指針域，且 top 是棧頂指針，若想在鏈棧的棧頂插入 一個(gè)由指針 s 所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（ A）操作。 A.s->next=top->next;top->next=s; B.top->next=s; C.s->next=top;top->next; D.s->next=top;top=s; 16. 帶頭結(jié)點(diǎn)的鏈隊(duì) LQ 示意圖如下，鏈隊(duì)列的隊(duì)頭元素是（ A）。 LQ->front H A B C D ∧

48、 LQ->rear A ．A B ． B C ． C D ． D 17. 帶頭結(jié)點(diǎn)的鏈隊(duì)列 LQ示意圖如下，指向鏈隊(duì)列的隊(duì)頭指針是（ C）。 LQ->front H A B C D ∧ LQ->rear A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18. 帶頭結(jié)點(diǎn)的鏈隊(duì)列 LQ示意圖如下 , 在進(jìn)行進(jìn)隊(duì)的運(yùn)算時(shí)指針 LQ->frnot(A). LQ->front H A B C

49、 D ∧ LQ->rear A. 始終不改變 B. 有時(shí)改變 C. 進(jìn)隊(duì)時(shí)改變 D. 出隊(duì)時(shí)改變 14 19. 隊(duì)列 Q，經(jīng)過(guò)下列運(yùn)算后，再執(zhí)行 QEmpty(Q)的值是（ C）。 InitQueue(Q)( 初始化隊(duì)列 ) ； InQueue(Q,a) ； InQueue(Q,b) ； OutQueue(Q,x) ； ReadQueue(Q,x) ； A.a B.b C.0 D.1 20. 若用一個(gè)大小為 6 數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 front 和 rear 的值分別為 3 和 0，

50、當(dāng)從隊(duì)列中刪除一 個(gè)元素，再加入兩個(gè)元素后， front 和 rear 的值分別為（ B）。 A.5 和 1 B.4 和 2 C.2 和 4 D.1 和 5 15 第 5 章 串 一、

51、判斷題 1. 串是 n 個(gè)字母的有限序列。 （） 2. 串的數(shù)據(jù)元素是一個(gè)字符。 （√） 3. 串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。 （） 4. 如果兩個(gè)串含有相同的字符，則說(shuō)明它們相等。 （） 5. 如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說(shuō)明前者是后者的子串。 （） 6. 串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。 （√） 7. “ DT”是“ DATA”的子串。 （） 8. 串中任意個(gè)字符組成的子序列稱為該串的子串。 （） 9. 子串的定位運(yùn)算稱為模式匹配。 （√） 10. 在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。 （√）

52、 二、填空題 1. 由零個(gè)或多個(gè)字符組成的有限序列稱為 字符串（或串） 。 2. 字符串按存儲(chǔ)方式可以分為順序存儲(chǔ)、鏈接存儲(chǔ)和 堆分配存儲(chǔ) 。 3. 串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為 順序串 。 4. 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是 空間利用率低 。 5. 串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理 效率低 。 6. 串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是 空間利用率 。 7. 在 C 或 C++語(yǔ)言中，以字符 \0 表示串值的終結(jié)。 8. 空格串的長(zhǎng)度等于 空格的個(gè)數(shù) 。 9. 在空

53、串和空格串中，長(zhǎng)度不為 0 的是 空格串 。 10. 兩個(gè)串相等是指兩個(gè)串長(zhǎng)度相等，且對(duì)應(yīng)位置的 字符都相同。 11. 設(shè)“ S=My Music ”，則 LenStr(s)= 8 。 12. 兩個(gè)字符串分別為； S1=” Today is ”、 S2=” 30 July ， 2005”， ConcatStr(S 1， S2) 的結(jié)果是 Today is 30 July,2005 。 13. 求子串函數(shù) SubStr( “ Today is 30 July ， 2005”， 13，4) 的結(jié)果是 J

54、uly 。 14. 在串的運(yùn)算中， EqualStr(aaa,aab) 的返回值 <0 。 15. 在串的運(yùn)算中， EqualStr(aaa,aaa) 的返回值 0 。 16. 在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為 模式 。 17. 模式匹配成功的起始位置稱為 有效位移 。 18. 設(shè) S=” abccdcdccbaa ”， T=” cdcc ”，則第 6 次匹配成功。 19. 設(shè) S=” c:/mydocument/text1.doc ”， T=” mydont”，則字符定位的位置為0

55、 。 20. 若 n 為主串長(zhǎng)度， m為子串長(zhǎng)度， n>>m，則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為 (n-m+1)*m 。 16 三、選擇題 1. 串是和種特殊的線性表，其特殊體現(xiàn)在（ B）。 A．可能順序存儲(chǔ) B ．?dāng)?shù)據(jù)元素是一個(gè)字符 C．可以鏈接存儲(chǔ) D ．?dāng)?shù)據(jù)元素可以是多個(gè)字符 2. 某串的長(zhǎng)度小于一常數(shù)，則采用（ B）存儲(chǔ)方式最節(jié)省空間。 A．鏈?zhǔn)? B ．順序 C ．堆結(jié)構(gòu) D ．無(wú)法確定 3. 以下論述正確的是（ C）。

56、 A．空串與空格串是相同的 B．” tel ”是” Teleptone ”的子串 C．空串是零個(gè)字符的串 D ．空串的長(zhǎng)度等于 1 4. 以下論述正確的是（ B）。 A．空串與空格串是相同的 B．” ton ”是” Teleptone ”的子串 C．空格串是有空格的串 D ．空串的長(zhǎng)度等于 1 5. 以下論斷正確的是（ A）。 A．全部由空格組成的串是空格串 B ．” BEUIJING”是” BEI JING ”的子串 C．” something ” <” Something ” D ．” BIT ” =”BITE” 6

57、. 設(shè)有兩個(gè)串 S1 和 S2，則 EqualStr （ S1， S2）運(yùn)算稱作（ D）。 A．串連接 B ．模式匹配 C ．求子串 D ．串比較 7. 串的模式匹配是指（ D）。 A．判斷兩個(gè)串是否相等B ．對(duì)兩個(gè)串比較大小 C．找某字符在主串中第一次出現(xiàn)的位置D．找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置 8. 若字符串” ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用 1 個(gè)字節(jié)，每個(gè)指針占用 2 個(gè)字節(jié)。則該字 符串的存儲(chǔ)密度為（ D）。 A． 20% B ． 40

58、% C ． 50% D ．33.3% 9. 若字符串” ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)指針占用 2 個(gè)字節(jié)，若希望存儲(chǔ)密度為 50%，則每個(gè)結(jié) 點(diǎn)應(yīng)存儲(chǔ)（ A）個(gè)字符。 A.2 B.3 C.4 D.5 10. 設(shè)串 S =” IAM”， S =”A SDUDENT”，則 ConcatStr(S 1 ， S )= （B）。 1 2 2 A．” I AM ” B. ” I AM A S

59、DUDENT” C. ” IAMASDUDENT” D. ”A SDUDENT” 11. 設(shè) S=””，則 LenStr(S)= （A）。 A.0 B.1 C.2 D.3 12. 設(shè)目標(biāo)串 T=” AABBCCDDE”，模式 P=”ABCDE”，則該模式匹配的有效位移為（A）。 A.0 B.1 C.2 D.3 13. 設(shè)目標(biāo)串 T=” AABBCCDDEEFF”，模式 P=” CCD”，則該模式匹配的有效位移為（D）。 A.2 B.3 C.4 D.5 1

60、4. 設(shè)目標(biāo)串 T=” aabaababaabaa”，模式 P=” abab”，模式匹配算法的外層循環(huán)進(jìn)行了（D）次。 A.1 B.9 C.4 D.5 15. 模式匹配算法在最壞情況下的時(shí)間復(fù)雜是（ D）。 17 A.O(m) B.O(n) C.O(m+n) D.O(m n) 16. S=” morning ” , 執(zhí)行求子串函數(shù) SubSur(S,2,2) 后結(jié)果為（ B）。 A. ” mo” B. ” or ” C. ” in ” D. ” ng” 1

61、7. S =” good”， S ” morning ”，執(zhí)行串連接函數(shù) ConcatStr(S S ) 后結(jié)果為（ A）。 1 2 1， 2 A. ”goodmorning ”B. ” good morning ” C. ”GOODMORNING”D. ” GOODMORNING” 18. S =” good” , S 2 =” morning ”執(zhí)行函數(shù) SubSur(S ,4,LenStr(S 1 )) 后的結(jié)果為（ B）。 1 2 A

62、. ” good” B. ”ning ” C. ” go” D. ”morn” 19. 設(shè)串 S1=” ABCDEFG”， S2=” PQRST”，則 ConcatStr（ SubStr(S 1， 2，LenStr（ S2））， SubStr(S 1， LenStr （ S2）， 2））的結(jié)果串為（ D）。 A. BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 20. 若串 S=” SOFTWARE”，其子串的數(shù)目最多是（ C）。 A． 35 B.36 C.37 D.38

63、 18 第 6 章 多 數(shù) 和廣 表 一、判斷 1. n 多 數(shù)可以 n-1 數(shù) 元素 成的 性 構(gòu)。 （√） 2. 稀疏矩 中非零元素的個(gè)數(shù) 小于矩 元素的 數(shù)。 （√） 3. 上三角矩 主 角 以上（不包括主 角 的元素），均 常數(shù) C。 （） 4. 數(shù) 元素可以由若干

64、數(shù)據(jù) 成。 （√） 5. 數(shù) 的三元 表存 是 稀疏矩 的 存 。 （√） 6. 任何矩 都可以 行 存 。 （） 7. 廣 表是 性表的推廣，所以廣 表也是 性表。 （） 8. 廣 表 LS=（ a0， a1，?? an-1 ）， an-1 是其表尾。 （） 9. 廣 表（（ a， b） a， b）的表 和表尾是相等的。 （√） 10. 一個(gè)廣 表的表尾 是一個(gè)廣 表。 （√） 二、填空 1. 多 數(shù) 的 序存 方式有按行 先 序存 和 按 先 序存 兩種。 2. 在多 數(shù) 中，數(shù)據(jù)

65、元素的存放地址可以直接通 地址 算公式算出，所以多 數(shù) 是一 種 隨機(jī) 存取 構(gòu)。 3. 在 n 數(shù) 中的每一個(gè)元素最多可以有 n 個(gè)直接前 。 4. 出二 數(shù) A[n][m] 中所有元素 的 復(fù) 度 n(n*m) 。 5. 數(shù) 元素 a[0 ? 2][0 ? 3] 的 地址是 2000，元素 度是 4， LOC[1， 2]= 2024 。 6. 稀疏矩 的三元 有 3 列。 8 0 0 0

66、0 0 7. 稀疏矩 的三元 中第 1 列存 的是數(shù) 中非零元素所在的 行數(shù)。 11 0 0 0 0 8. n 稱矩，如果只存 下三角元素，只需要 n(n-1)/2 0 個(gè)存 元。 9. 稀疏矩 A 如 6-19 所示，其非零元素存三元 表中，三元 （ 4，1， 5）按列0 先0 順0序存6儲(chǔ)在0三元0 表的第 4 。 0 3 0 0 7 0 10. 稀疏疏矩 的 存 方法通常有三元 表和 十字 表 兩種。 11. 任何一個(gè)非空廣 表的表尾必定是廣 表（或子表） 。 0 5 0 0 0 0 12. tail(head((a ， b)(c ， d)= b 。 13. 廣 表（（ a， b，c）） 將 c 分離出來(lái)的