數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題判斷填空選擇

1、 第一章一判斷題（）（1）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(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ù)項(xiàng)是數(shù)據(jù)的基本單位。（×）（5）數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。（）（6）數(shù)據(jù)的邏輯結(jié)構(gòu)是各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要而建立的。（）（7）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。（）（8）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（）（9）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。（）（10）算法是對(duì)解題方法和步驟

2、的描述。二填空題1數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算程序設(shè)計(jì)中計(jì)算機(jī)的操作對(duì)象以及它們之間的 關(guān)系 和運(yùn)算的學(xué)科。2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、 散列存儲(chǔ) 、索引存儲(chǔ) 。3數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們分別是：線性結(jié)構(gòu)和 非線性 結(jié)構(gòu)。4一個(gè)算法的空間復(fù)雜度是指該算法所耗費(fèi)的 存儲(chǔ)空間 ，它是該算法求解問題規(guī)模n的函數(shù)。5數(shù)據(jù)結(jié)構(gòu)有邏輯結(jié)構(gòu)和 存儲(chǔ)結(jié)構(gòu) 兩種結(jié)構(gòu)。6數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、散列存儲(chǔ)、 索引存儲(chǔ) 。7一個(gè)算法的效率可分為 時(shí)間 效率和空間效率。8數(shù)據(jù)元素是數(shù)據(jù)的 基本單位 。9數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的 邏輯結(jié)構(gòu) 、存儲(chǔ)結(jié)構(gòu)和算法。11數(shù)據(jù)的 邏輯

3、結(jié)構(gòu) 是獨(dú)立于計(jì)算機(jī)的。12數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的 關(guān)系 的有限集合。13樹形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在 一對(duì)多 的關(guān)系。14若一個(gè)算法中的語(yǔ)句頻度之和為T（n）=125n+3nlog2n，則算法的時(shí)間復(fù)雜度為 O（nlog2n） 。15數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、 存儲(chǔ)結(jié)構(gòu) 和算法。三選擇題1數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（ A ）及它們之間的相互聯(lián)系。 A. 存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu) B. 存儲(chǔ)和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯2執(zhí)行下列語(yǔ)句的時(shí)間復(fù)雜度為：（ B ）。s=0;for (i=1;i<=n; i+) s=s+i; A. O（1） B

4、. O（n） C. O（n2） D. O（n3）3數(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)4某程序的時(shí)間復(fù)雜度為（3n+log2n+n2+15）其數(shù)量級(jí)表示為（ B ） A. O（n） B. O（n2） C. O（log2n） D. O（nlog2n）5非線性結(jié)構(gòu)的數(shù)據(jù)元素之間存在（ B ）。 A. 一對(duì)多關(guān)系 B. 多對(duì)多關(guān)系 C. 多對(duì)一關(guān)系 D. 一對(duì)一關(guān)系6下列時(shí)間復(fù)雜度中最壞的是（ D ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）7

5、以下任何兩個(gè)結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是（ D ） A. 圖型結(jié)構(gòu) B. 線性結(jié)構(gòu) C. 樹型結(jié)構(gòu) D. 集合8鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ A ）。 A 分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B 只有一部分，存放結(jié)點(diǎn)值 C 只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D 分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元素9一個(gè)存儲(chǔ)結(jié)點(diǎn)存放一個(gè)（ B ） A. 數(shù)據(jù)項(xiàng) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)結(jié)構(gòu) D. 數(shù)據(jù)類型10下列時(shí)間復(fù)雜度中最好的是（ A ） A. O（1） B. O（ n） C. O（log2n） D. O（n2）11每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還

6、包含一組指針，該存儲(chǔ)方式是（ B ）存儲(chǔ)方式 A. 順序 B. 鏈?zhǔn)紺. 索引 D. 散列12下列算法的實(shí)際復(fù)雜度是（ D ） for (i=0;i<n;i+) for (j=0;i<n;j+) cij=i+j; A. O（1） B. O（ n） C. O（log2n） D. O（n2）13數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其內(nèi)（ B ）數(shù)據(jù)項(xiàng)。 A. 只能包括一個(gè) B. 可以包括多個(gè) C. 不包括 D. 可以包括也可以不包括14. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ C ）結(jié)構(gòu)；A. 存儲(chǔ) B. 物理 C. 邏輯 D. 物理和存儲(chǔ)15數(shù)據(jù)的邏輯結(jié)構(gòu)是（ A ）關(guān)系的整體A. 數(shù)

7、據(jù)元素之間邏輯 B. 數(shù)據(jù)項(xiàng)之間邏輯C. 數(shù)據(jù)類型之間 D. 存儲(chǔ)結(jié)構(gòu)之間第二章一判斷題（×）（1）鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。（×）（2）鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。（）（3）線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對(duì)象。（×）（4）鏈表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（×）（5）順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 （）（6）數(shù)組元素的存儲(chǔ)位置是下標(biāo)的線性函數(shù)。（）（7）在單鏈表中，元素的存儲(chǔ)位置用指針聯(lián)系，所以

8、可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。（×）（8）順序存儲(chǔ)線性表的插入和刪除操作不需要付出很大的代價(jià)，因?yàn)槠骄看我苿?dòng)僅一半的元素。（×）（9）順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。（×）（10）在單鏈表中，要取得某個(gè)元素，只要知道該元素的指針即可，因此單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。二填空題1順序表中邏輯上相鄰的元素在物理位置上 必須 相連。2在單鏈表中要在已知結(jié)點(diǎn)*P之前插入一個(gè)新結(jié)點(diǎn)，需找到*P的直接前趨結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為 O (n) 。3線性表是n個(gè)結(jié)點(diǎn)的 有限 集合。4鏈表相對(duì)于順序表的優(yōu)點(diǎn)有 插入、刪除 方便；缺點(diǎn)是存儲(chǔ)密度小。5鏈表

9、相對(duì)于順序表的優(yōu)點(diǎn)有插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度 小 。6順序表相對(duì)于鏈表的優(yōu)點(diǎn)是： 節(jié)省存儲(chǔ) 和隨機(jī)存取。7對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O（1） 。8在鏈表中邏輯上相鄰的元素的物理位置 不必 相連。9線性表中第一個(gè)結(jié)點(diǎn)沒有直接前趨，稱為 開始 結(jié)點(diǎn)。10在順序表中訪問任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O (1) 。11在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*P，其時(shí)間復(fù)雜度為 O (1) 。12在單鏈表中需知道 頭指針 才能遍歷整個(gè)鏈表。13在一個(gè)單鏈表中，在指針p所指向的結(jié)點(diǎn)之后插入指針s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=p->n

10、ext和p->next=s 操作。14在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移 n- i +1 個(gè)元素。 15在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨結(jié)點(diǎn)，另一個(gè)指向其 后繼 結(jié)點(diǎn)。三選擇題1用單鏈表方式存儲(chǔ)的線性表，存儲(chǔ)每個(gè)結(jié)點(diǎn)需要兩個(gè)域，一個(gè)數(shù)據(jù)域，另一個(gè)是（ B ）。A 當(dāng)前結(jié)點(diǎn)所在地址域 B 指針域 C 空指針域D 空閑域2在具有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)3設(shè)a，b，c為三個(gè)結(jié)點(diǎn)，p，

11、10，20，代表地址，則如下存儲(chǔ)結(jié)構(gòu)稱為（ B ）。a 10 c b 20 PA 循環(huán)鏈表 B 單鏈表 C雙向循環(huán)鏈表 D 雙向鏈表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)*m BB+i*m C B-i*m D B+(i+1)*m5單鏈表的存儲(chǔ)密度（ C ）。 A 大于1 B 等于1 C小于1 D 不能確定6在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O (1)的操作是（ A ）。A 訪問第i個(gè)結(jié)點(diǎn)(1<=i<-n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2<=i<=n)B 在第i個(gè)結(jié)點(diǎn)之后插入一個(gè)新

12、結(jié)點(diǎn)(1<=i<=n)C 刪除第i個(gè)結(jié)點(diǎn)(1<=i<=n)D 將n個(gè)結(jié)點(diǎn)從小到大排序7在線性表中（ B ）只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。A首元素 B 中間元素 C尾元素 D所有元素8指針P指向循環(huán)鏈表L的首元素的條件是（ D ）。AP= = L BL->next= = P CP->next= = NULL DP->next= = L9一維數(shù)組和線性表的區(qū)別是（ A ）。A 前者長(zhǎng)度固定，后者長(zhǎng)度可變 B 后者長(zhǎng)度固定，前者長(zhǎng)度可變C 兩者長(zhǎng)度都固定 D 兩者長(zhǎng)度都可變10指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（ D ）。AP= = L BP-

13、>prori= = L CP= = NULL DP->next= =L11一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ B ）A110 B108 C100 D12012兩個(gè)指針P和Q，分別指向單鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是（ ）。AP->next= =Q->next BP->next= = QCQ->next= = P DP= = Q13向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（ B ）個(gè)元素。A8 B63.5 C63 D714用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是（ C ）。

14、A 便于隨機(jī)存取 B 花費(fèi)的存儲(chǔ)空間比順序表少C 便于插入和刪除 D 數(shù)據(jù)元素的物理順序與邏輯順序相同15單鏈表的示意圖如下： LABCD P Q R 指向鏈表Q結(jié)點(diǎn)的后繼的指針是（ D ）AL BP CQ DR第三章一判斷題（）（1）大多數(shù)排序算法都有比較關(guān)鍵字大小和改變指向記錄的指針或移動(dòng)記錄本身兩種基本操作。（×）（2）快速排序在任何情況下都比其它排序方法速度快。（）（3）快速排序算法在每一趟排序中都能找到一個(gè)元素放在其最終位置上。（×）（4）如果某種排序算法不穩(wěn)定，則該排序方法就沒有實(shí)際應(yīng)用價(jià)值。（）（5）對(duì)n個(gè)記錄的進(jìn)行快速排序，所需要的平均時(shí)間是O（nlog2n

15、）。（×）（6）冒泡排序是不穩(wěn)定的排序。（）（7）冒泡排序的時(shí)間復(fù)雜度是O（n2）。（×）（8）堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無關(guān)。（）（9）對(duì)快速排序來說，初始序列為正序或反序都是最壞情況。（）（10）對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需的平均時(shí)間為O (nlog2n)。二填空題1 根據(jù)被處理的數(shù)據(jù)在計(jì)算機(jī)中使用不同的存儲(chǔ)設(shè)備，排序可分為： 內(nèi)排序 和外排序。2 評(píng)價(jià)排序算法優(yōu)劣的主要標(biāo)準(zhǔn)是 時(shí)間復(fù)雜性 和算法所需的附加空間。3插入排序、堆排序、歸并排序中，排序是不穩(wěn)定的有： 堆排序 。4在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入

16、排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較 3 次。5對(duì)n個(gè)關(guān)鍵字進(jìn)行冒泡排序，其可能的最小比較次數(shù)為： n-1 次。6內(nèi)排序是指整個(gè)排序過程，全部在計(jì)算機(jī)的 內(nèi)存 中進(jìn)行。7大多數(shù)排序算法都有兩個(gè)基本的操作： 比較 和移動(dòng)。8在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用 插入排序 較好。9在排序前，關(guān)鍵字值相等的不同記錄，排序后相對(duì)位置變化的排序方法，稱為 不穩(wěn)定 的排序方法。10若原始數(shù)據(jù)接近無序，則選用 快速排序 最好。11對(duì)于n個(gè)記錄的集合進(jìn)行歸并排序，所需要的平均時(shí)間為： O（log2n） 。12在插入排序、歸并排序、快速排序中，排序是不穩(wěn)定的有： 快速排序

17、 。13對(duì)一組記錄（54，35，96，21，12，72，60，44，80）進(jìn)行直接選擇排序時(shí)，第四次選擇和交換后，未排序記錄是 54，72，60，96，80 。14對(duì)于n個(gè)記錄的集合進(jìn)行，若對(duì)其進(jìn)行快速排序，在最壞的情況下所需要的時(shí)間是 O(n2) 。15在最壞情況下，在第i趟直接插入排序中，要進(jìn)行 i-1 次關(guān)鍵字的比較。三選擇題1每次從無序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，這種排序方法叫（ C ）。 A選擇 B交換 C插入 D歸并2快速排序方法在（ C ）情況下最不利于發(fā)揮其長(zhǎng)處。 A要排序的數(shù)據(jù)量太大 B要排序的數(shù)據(jù)中含有多個(gè)相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排

18、序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)3排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)（初始為空）的第一個(gè)記錄交換的排序方法，稱為: ( D )。A希爾排序 B歸并排序 C插入排序 D. 選擇排序4在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（ A ）。A直接插入 B冒泡排序 C希爾排序 D選擇排序5每次把待排序方的區(qū)間劃分為左、右兩個(gè)區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法叫做（ C ）。A冒泡排序 B堆排序 C快速排序 D. 歸并排序6排序是根據(jù)（ A ）的大小重新安排各元素的順序。 A關(guān)鍵字 B數(shù)組 C元素件 D結(jié)點(diǎn)7堆的形狀是

19、一棵（ D ）。A二叉排序樹 B滿二叉樹 C不是二叉樹 D. 完全二叉樹8穩(wěn)定的排序方法是指在排序前后，關(guān)鍵字值相等的不同記錄間的前后相對(duì)位置（ B ）。 A保持相反 B保持不變 C不定 D無關(guān)9下述幾種排序方法中，要求內(nèi)存量最大的是：（ D ）。 A插入排序 B選擇排序 C快速排序 D. 歸并排序10直接插入排序的方法是（ B ）的排序方法。 A不穩(wěn)定 B穩(wěn)定 C外部 D選擇11直接插入排序的方法要求被排序的數(shù)據(jù)（ B ）存儲(chǔ)。 A必須鏈表 B必須順序 C順序或鏈表 D可以任意12設(shè)有1000個(gè)無序元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用（ B ）排序法。A冒泡排序 B堆

20、排序 C快速排序 D. 歸并排序13用快速排序法對(duì)n個(gè)元素進(jìn)行排序時(shí)，最壞情況下的執(zhí)行時(shí)間為（ A ）AO（n2） BO（log2n） CO（nlog2n） D. O（n）14一個(gè)數(shù)據(jù)序列的關(guān)鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個(gè)數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為：（ C ）A （38，40，46，56，79，84） B（40，38，46，79，56，84） C（40，38，46，56，79，84） D（40，38，46，56，79，84）15用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 20，

21、15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（ D ）。 A選擇排序 B希爾排序 C歸并排序 D.快速排序第四章一判斷題（）（1）棧是運(yùn)算受限制的線性表。（）（2）在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢出。（×）（3）棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。（×）（4）空棧就是所有元素都為0的棧。（×）（5）一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。（）（6）一個(gè)棧的輸入序列為：A，B，C，D，通過入出棧操作可以

22、輸出序列：A，B，C，D。（×）（7）在C或C+語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN時(shí)表示隊(duì)滿。（）（8）鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。（）（9）在棧中插入或刪除一個(gè)元素應(yīng)遵守的“后進(jìn)先出”的原則。（）（10）進(jìn)位制的換算算法是棧的應(yīng)用。（）（11）隊(duì)列是限制在兩端進(jìn)行操作的線性表。（）（12）判斷順序隊(duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針均指向同一個(gè)結(jié)點(diǎn)。（×）（13）在鏈隊(duì)列做出隊(duì)操作時(shí)，會(huì)改變front指針的值。（）（14）在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front，其元素個(gè)數(shù)為rear- front。（）（15）隊(duì)列是一

23、種“先進(jìn)先出”的線性表。（×）（16）在循環(huán)鏈隊(duì)列中無上溢出現(xiàn)象。（×）（17）棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(gòu)。（）（18）棧和隊(duì)列都是屬于線性結(jié)構(gòu)。（×）（19）順序隊(duì)和循環(huán)隊(duì)的隊(duì)滿和隊(duì)空的判斷條件是一樣的。（）（20）在隊(duì)列中插入或刪除一個(gè)元素應(yīng)遵守的”先進(jìn)先出”的原則。二填空題1在棧中存取數(shù)據(jù)遵從的原則是： 后進(jìn)先出 。2在有n個(gè)元素的棧中，進(jìn)棧操作的時(shí)間復(fù)雜度為 O（1）。3后進(jìn)先出的線性表稱為 棧 。4在順序棧中，當(dāng)top=MAXLEN-1時(shí)，表示 棧滿 。5. 棧是輸入、輸出受限制的 線性表 。6在有n個(gè)元素的棧中，出棧操作的時(shí)間復(fù)雜度為 O（1）。7

24、在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為 棧頂 。8順序棧S存在數(shù)組S->data0.MAXLEN-1中，出棧操作時(shí)要執(zhí)行的語(yǔ)句有：S->top - 。9在順序棧中，當(dāng)棧頂指針top=-1時(shí)，表示 ?？?。10向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行 p->next=top； 和top=p； 操作。11同一棧的各元素的類型 相同 。12棧只能在 棧頂 插入和刪除元素。13已知順序棧S，在對(duì)S進(jìn)行出棧操作之前首先要判斷 棧是否空 。14若進(jìn)棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。15從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng) 棧頂

25、指針 。16在隊(duì)列中存取數(shù)據(jù)應(yīng)遵從的原則是 先進(jìn)先出 。17設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 O（n）。18在隊(duì)列中，允許插入的一端稱為 隊(duì)尾 。19設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則出隊(duì)操作的時(shí)間復(fù)雜度為 0（1） 。20設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)頭元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)空的標(biāo)志為 front=rear 。21隊(duì)列在進(jìn)行出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為 空 。22設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)頭元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為

26、MAXLEN，則隊(duì)滿標(biāo)志為 front=(rear+1)% MAXLEN 。23在一個(gè)鏈隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，則判斷該隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為： front=rear && front <>NULL 。24隊(duì)列結(jié)構(gòu)的元素個(gè)數(shù)是 可變的 。25設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為 0（1） 。26設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則入隊(duì)操作的時(shí)間復(fù)雜度為 0（1） 。27鏈隊(duì)列為空時(shí)，LQ->front->next= NULL 。28設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)頭元素

27、，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，當(dāng)rear<front時(shí)，隊(duì)列長(zhǎng)度是 MAXLEN-front 。29向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要移動(dòng)隊(duì)尾指針，然后再向指針?biāo)肝恢?寫入 新的元素。30隊(duì)列Q經(jīng)過InitQueue (Q)；InQueue (Q，a)； InQueue (Q，b)；GetHead (Q，x)后，x的值是 a 。三選擇題1順序棧判空的條件是（ C ） Atop=0 Btop=1 Ctop=-1 Dtop=m2設(shè)有編號(hào)為1，2，3，4的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，下列不可能的出站順序?yàn)?( D ) A1234 B12

28、43 C1324 D14233插入和刪除只能在一端進(jìn)行的線性表，稱為( C )。 A隊(duì)列 B循環(huán)隊(duì)列 C棧 D循環(huán)棧4鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是（ B ）。A插入操作根加方便 B通常不會(huì)出現(xiàn)棧滿的情況。C不會(huì)出現(xiàn)?？盏那闆r D刪除操作根加方便5在棧中，出棧操作的時(shí)間復(fù)雜度為( A )。 AO(1) BO(log2n) C0(n) DO(n2)6帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是（ A ） LSHABCD AA BB CC DD7元素A,B,C,D依次進(jìn)棧以后，棧頂元素是（ D ） AABB CC DD8順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用（ B ）存儲(chǔ)棧元素。 A鏈表B數(shù)組 C循環(huán)鏈

29、表 D變量9在C或C+語(yǔ)言中，一個(gè)順序棧一旦被聲明，其占用空間的大?。?A ）。 A已固定 B不固定 C可以改變 D動(dòng)態(tài)變化10當(dāng)棧中的元素為n個(gè)，做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明該棧的最大容量為（ C ）。 An-1 Bn+1 Cn Dn/211棧與一般線性表的區(qū)別在于 ( B )。 A數(shù)據(jù)元素的類型不同 B運(yùn)算是否受限制 C數(shù)據(jù)元素的個(gè)數(shù)不同 D邏輯結(jié)構(gòu)不同12設(shè)有一個(gè)順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果六個(gè)元素出棧的順序是B，D，C，F(xiàn)，E，A，則棧的容量至少應(yīng)是 ( A )。 A3 B4 C5 D 613在棧頂一端可進(jìn)行（ D ）操作。 A插入 B刪除 C進(jìn)棧 D插入和刪除

30、14從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行下列 ( D )命令。 Ax=top;top=top->next; Btop=top->next;x=top->data; Cx=top->data; Dx=top->data;top=top->next;15在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列 ( B )命令。 AHS->next=S; BS->next=HS->next;HS->next=S; CS->next=HS->next;HS=S; DS->ne

31、xt=HS;HS=HS->next;16在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原則是( A )。 A先進(jìn)先出 B后進(jìn)先出 C先進(jìn)后出 D隨意進(jìn)出17設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針，則人隊(duì)操作的時(shí)間復(fù)雜度為( C )。 AO(1) BO(log2n) CO(n) DO(n2)18一個(gè)循環(huán)隊(duì)列一旦說明，其占用空間的大小（ A ）。 A已固定 B可以變動(dòng) C不能固定 D動(dòng)態(tài)變化19當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為（ B ）。 An-2 Bn-1 Cn Dn+120設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為( A )。 AO

32、(1) BO (log2n) CO(n) DO(n2)21隊(duì)列是限定在（ D ）進(jìn)行操作的線性表。 A中間 B隊(duì)頭 C隊(duì)尾 D端點(diǎn)22若進(jìn)隊(duì)的序列為：A，B，C，D，則出隊(duì)的序列是（ C ）。 AB，C，D，ABA，C，B，D CA，B，C，DDC，B，D，A23從一個(gè)順序循環(huán)隊(duì)列刪除一個(gè)元素時(shí)，首先需要做的操作是（ B ）。 A隊(duì)頭指針減1 B取出隊(duì)頭指針?biāo)傅脑?C隊(duì)頭指針加1 D取出隊(duì)尾指針?biāo)傅脑?4. 在一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列中，隊(duì)頭指針指向隊(duì)頭元素的（ A ）位置。 A前一個(gè) B后一個(gè) C后面 D當(dāng)前25四個(gè)元素按：A，B，C，D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次OutQueue(Q)操

33、作后，隊(duì)頭元素是（ B ）。 A AB B C C D D26隊(duì)列中的元素個(gè)數(shù)是( B )。 A不變的B可變的C任意的D027設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。若想在鏈棧的棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列（ A ）操作。 As->next=top->next；top->next=sBtop->next=s Cs->next=top；top=top->nextDs->next=top；top=s28若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素

34、，再加入兩個(gè)元素后，front和rear的值分別為( B )。 A5和1 B4和2 C2和4 D1和529以下屬于隊(duì)列的操作有( D )。 A在隊(duì)首插入元素 B刪除值最小的元素 C按元素的大小排序 D判斷是否還有元素30.帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，LQ為空時(shí)（ A ） LQ->frontHABCD LQ->rearALQ->front= LQ->rear BLQ->rear=NULLCLQ->front!= LQ->rear DLQ->front=null第五章一判斷題（×）（1）串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。（×）（

35、2）串是n個(gè)字母的有限序列。（）（3）空串不等于空格串。（×）（4）如果兩個(gè)串含有相同的字符，則說明它們相等。（×）（5）如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說明前者是后者的子串。（）（6）串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（×）（7）“DT”是“DATA”的子串。（×）（8）空串與空格串是相同的。（×）（9）串中任意個(gè)字符組成的子序列稱為該串的子串。（）（10）子串的定位運(yùn)算稱為模式匹配。（）（11）n維的多維數(shù)組可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。（）（12）稀疏矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣元素的總數(shù)。（）（13）若采用三元組

36、壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算。（）（14）在稀疏矩陣的三元組表表示法中，每個(gè)三元組表示矩陣中數(shù)據(jù)元素的行號(hào)、列號(hào)和值。（）（15）上三角矩陣主對(duì)角線以上（不包括主對(duì)角線中的元素），均為常數(shù)C。（）（16）對(duì)稱矩陣、三角矩陣、稀疏矩陣都可以進(jìn)行壓縮存儲(chǔ)。（）（17）任何矩陣都可以進(jìn)行壓縮存儲(chǔ)。（）（18）在稀疏矩陣的三元組表表示法中，每個(gè)三元組表示矩陣中非零元素的行號(hào)、列號(hào)和值。（）（19）數(shù)組元素可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。（）(20）稀疏矩陣壓縮存儲(chǔ)就是為矩陣中非零元素分配一個(gè)存儲(chǔ)空間。二填空題1長(zhǎng)度為零的字符串稱為 空串 。2在串的運(yùn)算中

37、，EqualStr(aaa，aabb)的值為 < 0 。3串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為 順序串 。4串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱為 鏈?zhǔn)酱?。5求子串函數(shù)SubStr("Today is 30 July,2005",13,4)的結(jié)果是： July 。6設(shè)S="A:/document/mary.doc"，則len(s)= _ 20 。7由零個(gè)或多個(gè)字符組成的有限序列稱為 字符串 （或串）。8字符串按存儲(chǔ)方式可以分為：順序存儲(chǔ)、鏈接存儲(chǔ)和 堆分配存儲(chǔ) 。9設(shè)S=“A:/mydocument/text1.doc”，則strlen(S)= 23 。10在空串和空格串中，

38、長(zhǎng)度不為0的是 空格串 。11串順序存儲(chǔ)緊湊格式的優(yōu)點(diǎn)是： 空間利用率高 ,對(duì)串的字符處理效率低。12兩個(gè)串相等是指兩個(gè)串相長(zhǎng)度等，且對(duì)應(yīng)位置的 字符都相同 。13串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理 效率低 。14模式匹配成功的起始位置稱為： 有效位移 。15所有模式匹配不成功的起始位置稱為： 無效位移 。16.多維數(shù)組的順序存儲(chǔ)方式有行優(yōu)先順序存儲(chǔ)和 列優(yōu)先順序存儲(chǔ) 兩種。17.同一數(shù)組中各元素的長(zhǎng)度 相等 。18.在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計(jì)算公式算出，所以多維數(shù)組是一種 隨機(jī) 存取結(jié)構(gòu)。19. 在n維數(shù)組中的每一個(gè)元素最多可以有 n 個(gè)直接前驅(qū)。20.輸出二維

39、數(shù)組Amn中所有元素值的時(shí)間復(fù)雜度為 O(m*n) 。數(shù)組元素a0.20.3的實(shí)際地址上2000，元素長(zhǎng)度是4，則Loc1,2=2024 。21.數(shù)組的三元組存儲(chǔ)是對(duì) 稀疏矩陣 的壓縮存儲(chǔ)22.稀疏矩陣的三元組有 3 列。23.稀疏矩陣的三元組中第1列存儲(chǔ)的是數(shù)組中非零元素所在的 行數(shù) 。24.n階對(duì)稱矩陣，如果只存儲(chǔ)下三角元素，只需要 n（n-1）/2 個(gè)存儲(chǔ)單元。25.稀疏矩陣A如下圖所示，其非零元素存于三元組表中，三元組（4，1，5）按行優(yōu)先順序存儲(chǔ)在三元組表的第 6 項(xiàng)。8 0 0 0 0 00 11 0 0 0 00 0 0 6 0 00 3 0 07 0 0 5 0 00 00 0

40、 0 09 0稀疏矩陣AA=26.稀疏疏矩陣的壓縮存儲(chǔ)方法通常有三元組表和 十字鏈表 兩種。27 n階下三角矩陣，因?yàn)閷?duì)角線的上方是同一個(gè)常數(shù)，需要 n（n-1）/2+1 個(gè)存儲(chǔ)單元。28稀疏矩陣中有n個(gè)非零元素，則三元組有 n 行。29.稀疏矩陣的三元組中第2列存儲(chǔ)的是數(shù)組中非零元素所在的 列數(shù) 。30.稀疏矩陣的三元組中，第3列存儲(chǔ)的是稀疏數(shù)組中的 非零元素 。三選擇題1串是一種特殊的線性表，其特殊性體現(xiàn)在（ B ）。A.可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ) D數(shù)據(jù)元素可以是多個(gè)字符2設(shè)目標(biāo)串T="AABBCCDDEEFF"，P="CCD&quo

41、t;，則該模式匹配的有效位移為 ( C )。A2 B3 C4 D. 53設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱作( B )。 A.連接 B模式匹配 C.求子串 D求串長(zhǎng)4. S1="sdudent"，S2="SDUDENT"，執(zhí)行串比較函數(shù)EqualStr(S1,S2) 后的結(jié)果為( C )。 A0 B小于0 C大于0 D不確定5串的模式匹配是指（ D ）。A判斷兩個(gè)串是否相等B對(duì)兩個(gè)串比較大小C找某字符在主串中第一次出現(xiàn)的位置D找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置6樸素模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是( D )。 AO（m） B

42、O（n） C0（m+n） D0（m*n）7以下論斷正確的是( A )。 A""是空串，" "空格串 B"BEIJING"是"BEI JING"的子串 C"something"<"Somethig" D"BIT"="BITE"8. S1="Today is"，S2="30 July 2005"，執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為( A )。 A"Today is

43、 30 July 2005" B"30 July 2005" C"Today is" D"30 July 2005 Today is"9某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用（ B ）存儲(chǔ)方式最節(jié)省空間。 A鏈?zhǔn)?B順序 C堆結(jié)構(gòu) D無法確定10. S="Today is 30 July 2005"，LenStr(S)=( D )。 A18 B19 C20 D2111設(shè)有兩個(gè)串S1和S2，則EqualStr(S1,S2)運(yùn)算稱作( D )。 A. 串連接 B模式匹配 C. 求子串 D串比較12. S1="

44、;good"，S2="morning"，執(zhí)行串連接函數(shù)ConcatStr(S1,S2)后的結(jié)果為( A )。 A"goodmorning" B"good morning" C"GOODMORNING" D"GOOD MORNING"13在實(shí)際應(yīng)用中，要輸入多個(gè)字符串，且長(zhǎng)度無法預(yù)定，則應(yīng)該采用（ C ）存儲(chǔ)方式比較合適。 A鏈?zhǔn)?B順序 C堆結(jié)構(gòu) D無法確定14. 設(shè)串S1="I AM"，S2="A SDUDENT",則ConcatStr(S1,

45、S2)=( B )。 A"I AM" B"I AM A SDUDENT" C"IAMASDUDENT"D. "A SDUDENT"15. 以下論述正確的是（ C ）。 A空串與空格串是相同的B"tel"是"Teleptone"的子串 C空串是零個(gè)字符的串 D. 空串的長(zhǎng)度等于116. 在一個(gè)m維數(shù)組中，（ D ）恰好有m個(gè)直接前驅(qū)和m個(gè)直接界后繼。A.開始結(jié)點(diǎn) B總終端結(jié)點(diǎn) C.邊界結(jié)點(diǎn) D內(nèi)部結(jié)點(diǎn)17. 多維數(shù)組的體積與（ A ）無關(guān)。 A數(shù)組的基地址 B維數(shù) C各維的上下

46、界 D結(jié)點(diǎn)的大小18. 對(duì)下述矩陣進(jìn)行壓縮存儲(chǔ)后，失去隨機(jī)存取功能是（ D ）。 A對(duì)稱矩陣 B三角矩陣 C三對(duì)角矩陣 D稀疏矩陣19. 在按行優(yōu)先順序存儲(chǔ)的三元組表中，下述陳述錯(cuò)誤的是（ D ）。A 同一行的非零元，是按列號(hào)遞增次序存儲(chǔ)的B 同一列的非零元，是按行號(hào)遞增次序存儲(chǔ)的C 三元組表中三元組行號(hào)遞增的D 三元組表中三元組列號(hào)遞增的20. 以下（ C ）是稀疏矩陣的壓縮存儲(chǔ)方法。 A一維數(shù)組 B二維數(shù)組 C三元組表 D廣義表21. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)是為了（ B ）。 A降低運(yùn)算時(shí)間 B節(jié)約存儲(chǔ)空間 C便于矩陣運(yùn)算 D便于輸入和輸出22. 若數(shù)組A0.m0.n按列優(yōu)先順序存儲(chǔ)，則aij的地址為（ A ）。 ALOC(a