數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題總結(jié)

填空題1.文件可按其記錄的類型不同而分成兩類，操作系統(tǒng)文件和數(shù)據(jù)庫文件。2.數(shù)據(jù)庫文件按記錄中關(guān)鍵字的多少可分成(單關(guān)鍵字文件)和(多關(guān)鍵字文件)兩種文件。3.文件由(記錄)組成，記錄由(數(shù)據(jù)項(xiàng))組成。4.從用戶觀點(diǎn)看，文件的邏輯結(jié)構(gòu)通?？梢詤^(qū)分為兩類：一類是如DBASE中數(shù)據(jù)庫文件那樣的文件組織結(jié)構(gòu)，稱為(數(shù)據(jù)庫)文件；另一種是諸如用各種文字處理軟件編輯成的文本文件，稱為(文本)文件。

從文件在存儲器上的存放方式來看，文件的物理結(jié)構(gòu)往往可區(qū)分為三類，即(順序組織)、(隨機(jī)組織)、(鏈組織)。

B+樹適用于組織(隨機(jī)組織)的索引結(jié)構(gòu)，

m階B+樹每個結(jié)點(diǎn)至多有(m)

除根結(jié)點(diǎn)外每個結(jié)點(diǎn)至少有((m/2)向上取整)個兒子，根結(jié)點(diǎn)至少有(2)個兒子，有k個兒子的結(jié)點(diǎn)必有(k)個關(guān)鍵碼。5.物理記錄之間的次序由指針相鏈表示的順序文件稱為(串聯(lián)文件)6.順序文件中，要存取第I個記錄，必須先存取(第I-1)個記錄。7.索引順序文件既可以順序存取，也可以(隨機(jī))存取。8.建立索引文件的目的的(提高查找速度)。9.索引順序文件是最常用的文件組織之一，通常用(樹)結(jié)構(gòu)來組織索引。10.倒排文件的主在優(yōu)點(diǎn)在于(檢索記錄塊)。11.檢索是為了在文件中滿足一定條件的記錄而設(shè)置的操作。檢索可以按(關(guān)鍵字)檢索，也可以按(記錄號)檢索；

按(記錄號)檢索又可以有(順序)檢索和(直接)檢索。12.哈希檢索的技術(shù)的關(guān)鍵是(構(gòu)造哈希函數(shù))和(解決沖突的方法)。結(jié)構(gòu)來組織索引。13.VSAM系統(tǒng)是由(索引集)、(順序集)、(數(shù)據(jù)集)構(gòu)成的。14.VSAM(虛擬存儲存取方法)文件的優(yōu)點(diǎn)是：動態(tài)地(分配和釋放存儲空間)，不需要文件進(jìn)行(重組)，并能較快地(對插入的記錄)進(jìn)行查找。一～五章選擇題一學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的主要目的是(C)。

A．處理數(shù)據(jù)計算問題B．研究程序設(shè)計技巧

C．選取適宜數(shù)據(jù)結(jié)構(gòu)，寫出更有效的算法D．是計算機(jī)硬件課程的根底數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的邏輯存儲以及它們之間的(B)和運(yùn)算的科學(xué)。

A．結(jié)構(gòu)B．關(guān)系C．運(yùn)算D．算法在計算機(jī)中存儲一個數(shù)據(jù)元素的位串稱為(A)。

A.結(jié)點(diǎn)B.數(shù)據(jù)項(xiàng)C.數(shù)據(jù)字段D.字符串算法指的是(C)

A.計算機(jī)程序B.排序算法

C.解決問題的有限運(yùn)算序列D.解決問題的計算方法(D)是數(shù)據(jù)不可分割的最小單位。

A．?dāng)?shù)據(jù)結(jié)構(gòu)B．?dāng)?shù)據(jù)對象C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)項(xiàng)數(shù)據(jù)結(jié)構(gòu)有(D)種根本邏輯結(jié)構(gòu)。

A.1B.2C.3在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成(C)。

A．動態(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)通常所說的時間復(fù)雜度是指(B)。

A．語句的頻度和B．算法的時間消耗C．漸近時間復(fù)雜度D．最壞時間復(fù)雜度(C)是數(shù)據(jù)的根本單位。

A．?dāng)?shù)據(jù)結(jié)構(gòu)B．?dāng)?shù)據(jù)項(xiàng)C．?dāng)?shù)據(jù)元素D．?dāng)?shù)據(jù)類型數(shù)據(jù)元素是數(shù)據(jù)的根本單位，其內(nèi)(C)數(shù)據(jù)項(xiàng)。

A.只能包括一個B.不包含C.可以包含多個D.必須包含多個計算機(jī)算法必須具有輸入、輸出和(A)等五個特性。

A．可執(zhí)行性、確定性、有窮性B可執(zhí)行性、可移植性、可擴(kuò)充性

C．確定性、有窮性和穩(wěn)定性D．易讀性、穩(wěn)定性和平安性以下時間復(fù)雜度中最好的是(A)。

A.O(1)B.O(n)C.O(log2n)D.O(n^2)對于反復(fù)屢次使用的程序，應(yīng)盡是選用(B)算法。

A．節(jié)約空間B．節(jié)約時間C．簡明易懂D．容易調(diào)試對于反復(fù)屢次使用的程序，應(yīng)盡是選用(B)算法。

A．節(jié)約空間B．節(jié)約時間C．簡明易懂D．容易調(diào)試以下說法不正確的選項(xiàng)是(D)。

A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的根本單位

B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識單位

C．?dāng)?shù)據(jù)可由假設(shè)干個數(shù)據(jù)元素構(gòu)成

D．?dāng)?shù)據(jù)項(xiàng)可由假設(shè)干個數(shù)據(jù)元素構(gòu)成計算機(jī)算法指的是(C)。

A．計算方法和運(yùn)算結(jié)果B．排序方法C．解決某一問題的有限序列D．調(diào)度方法以下時間復(fù)雜度中最壞的是(D)。

A.O(1)B.O(n)C.O(log2n)D.O(n^2)根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，以下四類根本的邏輯結(jié)構(gòu)反映了四類根本的數(shù)據(jù)組織形式，其中解釋錯誤的選項(xiàng)是(A)。

A．集合中任何兩個結(jié)點(diǎn)之間都有邏輯關(guān)系但組織形式松散

B．線性結(jié)構(gòu)中結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一條“鎖鏈”

C．樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)像自然界中的樹

D．圖狀結(jié)構(gòu)中的各個結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個結(jié)點(diǎn)都可以鄰接以下四種根本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是(A)。

A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)某算法的時間消耗為T(n)=100n+10log2n+n2+10，該算法的時間復(fù)雜度為(A)：

A．O(n2)B．O(n3)C．O(n)D．O(1)一般而言，最適合描述算法的語言是(C)。

A．自然語言B．計算機(jī)程序語言C．介于自然語言和程序設(shè)計語言之間的語言D．?dāng)?shù)學(xué)公式研究數(shù)據(jù)結(jié)構(gòu)就是研究(D)。

A．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)

B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)

C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)

D．?dāng)?shù)據(jù)的邏輯和存儲結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)以下四種根本的邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是(A)。

A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)評價一個算法時間性能的主要標(biāo)準(zhǔn)是(D)。D．算法的時間復(fù)雜度一個算法必須保證執(zhí)行有限步之后結(jié)束，這是算法的(A)特性。

A．有窮性B．確定性C．可行性D．輸出邏輯關(guān)系是指數(shù)據(jù)元素間的(C)。

A.類型B.存儲方式C.結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)研究數(shù)據(jù)結(jié)構(gòu)就是研究(D)。

A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)

B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)

C．?dāng)?shù)據(jù)的邏輯和存儲結(jié)構(gòu)

D．?dāng)?shù)據(jù)的邏輯和存儲結(jié)構(gòu)及其數(shù)據(jù)在運(yùn)算上的實(shí)現(xiàn)算法分析的兩個主要方面是(A)。

A．空間復(fù)雜性和時間復(fù)雜性B．正確性和簡明性

C．可讀性和文檔性D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜性用類C語言描寫的算法(B)。

A.可以直接在計算機(jī)上運(yùn)行B.可以描述解題思想和根本框架

C.不能改寫成C語言程序D.與C語言無關(guān)邏輯結(jié)構(gòu)是(A)關(guān)系的整體。

A.數(shù)據(jù)元素之間邏輯B.數(shù)據(jù)項(xiàng)之間邏輯C.數(shù)據(jù)類型之間D.存儲結(jié)構(gòu)之間要求同一邏輯結(jié)構(gòu)的所有數(shù)據(jù)元素具有相同特性，這意味著(B)。

A.數(shù)據(jù)元素具有同一的特點(diǎn)

B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個數(shù)要相同,而且對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

C.每個數(shù)據(jù)元素都一樣式

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個數(shù)要相等算法分析的目的是(C)。

A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入與輸出的關(guān)系

C.分析算法的效率以求改良D.分析算法的易懂性和文檔性數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存儲D．關(guān)系數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存儲D．關(guān)系一個存儲結(jié)點(diǎn)存放一個(B)。

A.數(shù)據(jù)項(xiàng)B.數(shù)據(jù)元素C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)類型算法能正確地實(shí)現(xiàn)預(yù)定功能的特性稱為(A)。

A.正確性B.易讀性C.健壯D.高效率數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(K，R)，其中K是(B)的有限集合。

A．算法B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)操作D．邏輯結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(K，R)，其中，R是K上(D)的有限集合。

A．操作B．映象C．存儲D．關(guān)系數(shù)據(jù)結(jié)構(gòu)被形式化地定義為(K，R)，其中K是(B)的有限集合。

A．算法B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)操作D．邏輯結(jié)構(gòu)以下說法不正確的選項(xiàng)是(A)。

A．?dāng)?shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間的邏輯結(jié)構(gòu)

B．?dāng)?shù)據(jù)類型可看成是程序設(shè)計語言中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)

C．?dāng)?shù)據(jù)項(xiàng)是組成數(shù)據(jù)元素的最小標(biāo)識單位

D．?dāng)?shù)據(jù)的抽象運(yùn)算不依賴具體的存儲結(jié)構(gòu)算法原那么上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成，這是算法的(C)。

A．有窮性B．確定性C．可行性D．輸出二線性表L=(a1,a2,…ai,…,an),以下說法正確的選項(xiàng)是(D)。

A.每個元素都有一個直接前驅(qū)和直接后繼

B.線性表中至少要有一個元素

C.表中諸元素的排列順序必須是由小到大或由大到小的

D.除第一個元素和最后一個元素外其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼對線性表進(jìn)行二分法查找，其前提條件是(A)。

A．線性表以順序方式存儲，并且按關(guān)鍵碼值排好序

B．線性表以順序方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序

C．線性表以鏈接方式存儲，并且按關(guān)鍵碼值排好序

D．線性表以鏈接方式存儲，并且按關(guān)鍵碼值的檢索頻率排好序?qū)τ谥辉诒淼氖孜矁啥诉M(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為(C)。

A.順序表B.用頭指針表示的單循環(huán)鏈表

C.用尾指針表示的單循環(huán)鏈表D.單鏈表線性表的順序存儲結(jié)構(gòu)是一種(A)的存儲結(jié)構(gòu)。

A．隨機(jī)存取B．順序存取C．索引存取D．散列存取用數(shù)組表示線性表的優(yōu)點(diǎn)是(B)。

A.便于插入和刪除操作B.便于隨機(jī)存取

C.可以動態(tài)地分配存儲空間D.不需要占用一片相鄰的存儲空間在線性表的以下存儲結(jié)構(gòu)中,讀取元素花費(fèi)時間最少的是(D)。

A.單鏈表B.雙鏈表C.循環(huán)鏈表D.順序表線性結(jié)構(gòu)中的一個結(jié)點(diǎn)代表一個(A)。

A.數(shù)據(jù)元素B.數(shù)據(jù)項(xiàng)C.數(shù)據(jù)D.數(shù)據(jù)結(jié)構(gòu)對于順序表,以下說法錯誤的選項(xiàng)是(A)。

A.順序表是用一維數(shù)組實(shí)現(xiàn)的線性表,數(shù)組的下標(biāo)可以看成是元素的絕對地址

B.順序表的所有存儲結(jié)點(diǎn)按相應(yīng)數(shù)據(jù)元素元素間的邏輯關(guān)系決定的次序依次排列

C.順序表的特點(diǎn)是:邏輯結(jié)構(gòu)中相鄰的結(jié)點(diǎn)在存儲結(jié)構(gòu)中仍相鄰

D.順序表的特點(diǎn)是:邏輯上相鄰的元素,存儲在物理位置也相鄰的單元中假設(shè)某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，那么采用(A)存儲方式最節(jié)省時間。

A．單鏈表B．雙鏈表C．單向循環(huán)D．順序表線性表是(A)。

A.一個有限序列，可以為空B.一個有限序列，不可以為空

C.一個無限序列，可以為空D.一個無限序列，不可以為空在(C)運(yùn)算中，使用順序表比鏈表好。

A．插入B．刪除C．根據(jù)序號查找D．根據(jù)元素值查找在循環(huán)雙向鏈表的p所指的結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是(D)。

A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;

B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;

C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;

D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;(D)適合作為經(jīng)常在首尾兩端操作線性表的存儲結(jié)構(gòu)。

A.順序表B.單鏈表C.循環(huán)鏈表D.雙向鏈表對于順序表的優(yōu)缺點(diǎn),以下說法錯誤的選項(xiàng)是(C)。

A.無需為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲空間

B.可以方便地隨機(jī)存取表中的任何一結(jié)點(diǎn)

C.插入和刪除操作較方便

D.由于順序表要求占用連續(xù)的空間,存儲分配只能預(yù)先進(jìn)行(靜態(tài)分配)設(shè)非空單鏈表的數(shù)據(jù)字段為data，指針字段為next，指針p指向單鏈表中第i個結(jié)點(diǎn)，s指向已生成的新結(jié)點(diǎn)，現(xiàn)將s結(jié)點(diǎn)插入到單鏈表中，使其成為第i+1個結(jié)點(diǎn)，以下算法段能正確完成上述要求的是(C)。

A.s->next=p->next=s；

B.p->next=s；s->next=p->next；

C.s->next=p->next；p->next=s；交換p->data和s->data；

D.p=s；s->next=p線性表中各元素之間的關(guān)系是(C)關(guān)系。

A.層次B.網(wǎng)狀C.有序D.集合在長度為n的順序表的第i〔1≤i≤n+1〕各位置上插入一個元素，元素的移動次數(shù)為(D)。

A.n-(i-1)B.n-iC.iD.i-1在一個單鏈表HL中,假設(shè)要在指針q所指結(jié)點(diǎn)的后面插入一個由指針p所指向的結(jié)點(diǎn)，那么執(zhí)行(D)。

A．q->next=p->next;p->next=q;

B．p->next=q->next;q=p;

C．q->next=p->next;p->next=p;

D．p->next=q->next;q->next=p;不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(A)

A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)滿足(C)。

A．p->next=NULLB．p=NULLC．p->next=headD．p=head順序表是線性表的(B)。

A.鏈?zhǔn)酱鎯Y(jié)構(gòu)B.順序存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)線性表中哪些元素只有一個直接前驅(qū)和一個直接后繼(C)。

A.首元素B.尾元素C.中間元素D.所有的元素在長度為n的順序存儲的線性表中，刪除第i個元素(1≤i≤n)時，需要從前向后依次前移(A)個元素。

A．n-IB．n-i+1C．n-i-1D．i在一個單鏈表中，假設(shè)p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，那么執(zhí)行(D)。

A．s->next=p;p->next=s;B．s->next=p->next;p->next=s;

C．s->next=p->next;p=s;D．p->next=s;s->next=p;從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需平均比擬(B)個結(jié)點(diǎn)。

A．nB．n/2C．(n-1)/2D．(n+1)/2假設(shè)left和right為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針字段，現(xiàn)要把一個指針s所指的新結(jié)點(diǎn)作為非空雙鏈表中q所指結(jié)點(diǎn)〔中間結(jié)點(diǎn)〕的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，那么以下算法段能正確完成上述要求的是(C)。

A.q->right=s；s->left=q；q->right->left=s；s->right=q->right；

B.s->left=q；q->right=s；q->right->left=s；s->right=q->right；

C.s->left=q;s-right=q->right;q->right-left=s;q->right=s;

D.以上都不對下面給出的算法段是把一個q所指新結(jié)點(diǎn)作為非空雙向鏈表中的p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)插入到該雙鏈表中，能正確完成要求的算法段是(A)。

A．q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;

B．p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;

C．q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q;

D．以上都不對循環(huán)鏈表的主要優(yōu)點(diǎn)是(D)。

A.不再需要頭指針了

B.某個結(jié)點(diǎn)的位置后,容易找到它的直接前驅(qū)

C.在進(jìn)行插入、刪除操作時,能更好地保證鏈表不斷開

D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表在單鏈表的一個結(jié)點(diǎn)中有(A)個指針。

A.1B.2C.0在一個單鏈表中，刪除p所指的直接后繼的操作是(A)。

A．p->next=p->next->next;B．p=p->next->next;

C．p=p->next;D．p->next->next=p->next;帶有頭結(jié)點(diǎn)的單鏈表head為空的判定條件是(B)。

A．head==NULLB．head->next==NULL

C．head->next==headD．head!=NULL將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復(fù)雜度為(C)。

A．O(1)B．O(n)C．O(m)D．O(m+n)下面關(guān)于線性表的表達(dá)中，錯誤的選項(xiàng)是(B)。

A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元

B.線性表采用順序存儲，便于進(jìn)行插入和刪除操作

C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元

D.線性表采用鏈接存儲，便于插入和刪除操作一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是(B)。

A.O(1)B.O(n)C.O(n^2)D.O(log2n)在單循環(huán)鏈表中，用尾指針取代頭指針的作用是(D)。

A．方便查找中間結(jié)點(diǎn)B．方便查找終端結(jié)點(diǎn)

C．方便查找開始結(jié)點(diǎn)D．查找開始結(jié)點(diǎn)和終端結(jié)點(diǎn)同樣方便在一個單鏈表中，q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前趨結(jié)點(diǎn)，假設(shè)在p和q之間插入s結(jié)點(diǎn)，那么執(zhí)行的操作序列是。(C)。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;D.p->next=s;s->next=q;帶有頭結(jié)點(diǎn)的單循環(huán)鏈表head為空的判定條件是(C)。

A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間(A)。

A.分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放表示結(jié)點(diǎn)關(guān)系的指針

B.只有一局部，存放結(jié)點(diǎn)值

C.只有一局部，存放表示結(jié)點(diǎn)關(guān)系的指針

D.分兩局部，一局部存放結(jié)點(diǎn)值，另一局部存放結(jié)點(diǎn)所占單元數(shù)線性表〔L〕經(jīng)運(yùn)算InitList〔L〕后，函數(shù)IEmpty〔L〕的值是(C)。

A.0B.falseC.1D.Null以下關(guān)于鏈?zhǔn)酱鎯Y(jié)構(gòu)的表達(dá)中，(C)是不正確的。

A.結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲密度小于順序存儲結(jié)構(gòu)

B.邏輯上相鄰的結(jié)點(diǎn)物理上不必鄰接

C.可以通過計算直接確定第i個結(jié)點(diǎn)的存儲地址

D.插入、刪除運(yùn)算操作方便，不必移動結(jié)點(diǎn)在等概率情況下，順序表的插入操作要移動(B)結(jié)點(diǎn)。

A．全部B．一半C．三分之一D．四分之一在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新的結(jié)點(diǎn)并仍然有序的時間復(fù)雜度是(B)。

A．O(1)B．O(n)C．O(n^2)D．O(log2n)單鏈表中，增加頭結(jié)點(diǎn)的作用是(A)。

A.方便運(yùn)算的實(shí)現(xiàn)B.用于標(biāo)志單鏈表

C.使單鏈表中至少有一個結(jié)點(diǎn)D.用于標(biāo)志起始結(jié)點(diǎn)兩指針p和q，分別指向單鏈表的兩個元素，p所指元素是q所指元素的前驅(qū)的條件是(A)。

A.p->next==qB.q->next==pC.p==qD.p->next==null線性表采用鏈?zhǔn)酱鎯r，其地址(D)。

A.必須是連續(xù)的B.一定是不連續(xù)的

C.局部地址必須是連續(xù)的D.連續(xù)與否均可以以下關(guān)于線性表的說法不正確的選項(xiàng)是(C)。

A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型

B.線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的

C.線性表中的每個結(jié)點(diǎn)都有且只有一個直接前驅(qū)和直接后繼

D.存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前驅(qū)和直接后繼在具有n個結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)(A)的操作，其算法的時間復(fù)雜度都是O(n)。

A．遍歷鏈表和求鏈表的第I個結(jié)點(diǎn)B．在地址為p的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)C．刪除開始結(jié)點(diǎn)D．刪除地址為p的結(jié)點(diǎn)的后繼結(jié)點(diǎn)指針P所指的元素是雙向循環(huán)鏈表L的尾元素的條件是(D)。

A.P==LB.p==nullC.p->prior==LD.p->next==L對順序表上的插入、刪除算法的時間復(fù)雜度分析來說，通常以(B)為標(biāo)準(zhǔn)操作。

A．條件判斷B.結(jié)點(diǎn)移動C.算術(shù)表達(dá)式D.賦值語句兩個指針p和q分別指向雙向循環(huán)鏈表L兩個元素，p所指元素是q所指元素的后繼的條件是(B)。

A.p==qB.q->next==pC.p->next==qD.q->next==p->next線性表的鏈接實(shí)現(xiàn)有利于(A)運(yùn)算。

A.插入B.讀表元C.查找D.定位用單鏈表的方式存儲的線性表，存儲每一個結(jié)點(diǎn)需要兩個域，一個是數(shù)據(jù)域，另一個是(B)。

A.當(dāng)前結(jié)點(diǎn)所在地址域B.指針域C.空指針域D.空閑域在雙向鏈表的一個結(jié)點(diǎn)中有(B)個指針。

A.1B.2C.0指針p指向線性鏈表L首元素的條件是(A)。

A.p=LB.L->next=pC.p->next=LD.p->next=null對線性表，在(B)情況下應(yīng)當(dāng)采用鏈表表示。

A．經(jīng)常需要隨機(jī)在存取元素B．經(jīng)常需要進(jìn)行插入和刪除

C．表中元素需要占據(jù)一片連續(xù)的存儲空間D．表中元素的個數(shù)不變假設(shè)某線性表中，最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，那么采用(C)存儲方式最省時。

A.單鏈表B.僅有頭指針的單循環(huán)鏈表

C.雙鏈表D.僅有尾指針的單循環(huán)鏈表線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種(B)的存儲結(jié)構(gòu)。

A．隨機(jī)存取B．順序存取C．索引存取D．散列存取用鏈接方式存儲的隊(duì)列，在進(jìn)行刪除運(yùn)算時(D)。

A．僅修改頭指針B．僅修改尾指針

C．頭、尾指針都要修改D．頭、尾指針可能都要修改在順序表中，只要知道(D)，就可在相同時間內(nèi)求出任一結(jié)點(diǎn)的存儲地址。

A．基地址B．結(jié)點(diǎn)大小C．向量大小D．基地址和結(jié)點(diǎn)大小三4個元素進(jìn)S棧的順序是A、B、C、D，進(jìn)行兩次Pop〔S，x〕操作后，棧頂元素的值是(B)。

A．AB．BC．CD．D表達(dá)式a*(b+c)-d的后綴表達(dá)式是(B)。

A.abcdd+-B.abc+*d-C.abc*+d-D.-+*abcd從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值，那么執(zhí)行(D)。

A.x=HS;HS=HS->next;B.x=HS->data;

C.HS=HS->next;x=HS->data;D.x=HS->data;HS=HS->next;當(dāng)循環(huán)隊(duì)列Sq是滿隊(duì)列時，存放隊(duì)列元素的數(shù)組data有n個元素，那么data中存放個隊(duì)列元素(A)。

A．nB．n-1C．n-2D隊(duì)列操作的原那么是(B)。

A．先進(jìn)先出B．先進(jìn)后出C．只能進(jìn)行插入D．只能進(jìn)行刪除隊(duì)列的特點(diǎn)是(A)。

A．先進(jìn)先出B．后進(jìn)先出C.先進(jìn)后出D．不進(jìn)不出隊(duì)列是限定在(C)處進(jìn)行插入操作的線性表。

A．端點(diǎn)B．隊(duì)頭C．隊(duì)尾D．中間和順序棧相比，鏈棧有一個比擬明顯的優(yōu)勢是(A)。

A.通常不會出現(xiàn)棧滿的情況B.通常不會出現(xiàn)?？盏那闆r

C.插入操作更容易實(shí)現(xiàn)D.刪除操作更容易實(shí)現(xiàn)經(jīng)過以下運(yùn)算后GetHead〔Q〕的值是(B)。

InitQueue〔Q〕；EnQueue〔Q，a〕；EnQueue(Q,b〕；OutQueue〔Q，x〕；

A．a(chǎn)B．bC．1D．2鏈棧ls是空棧的條件是(A)。

A．ls==nullB．ls->next==nullC．Ls==0D．ls->next==ls判定一個順序棧ST〔最多元素為m0〕為空的條件是(B)。

A．ST.top<>ST.baseB．ST.top==ST.base

C．ST.top<>m0D．ST.top==m0判定一個循環(huán)隊(duì)列QU(最多元素為m0)為空的條件是(C)。

A．QU.front==〔QU.rear+1〕%m0B．QU.front！=〔QU.rear+1〕%m0

C．QU.front==QU.rearD．QU.front判定一個循環(huán)隊(duì)列QU(最多元素為m0)為滿的條件是(A)。

A．QU.front==〔QU.rear+1〕%m0B．QU.front！=〔QU.rear+1〕%m0

C．QU.front==QU.rearD．QU.front如果以鏈表作為棧的存儲結(jié)構(gòu),那么出棧操作時(C)

A.必須判別棧是否滿B.判別棧元素的類型

C.必須判別棧是否空D.對棧不做任何判別假設(shè)一個棧的入棧序列是1,2,3,…,n,其輸出序列為p1,p2,p3,…,pn,假設(shè)p1=n,那么pi為(C)。

A.IB.n=IC.n-I+1D.不確定設(shè)計一個判別表達(dá)式中左、右括號是否配對出現(xiàn)的算法,采用()數(shù)據(jù)結(jié)構(gòu)最正確(B)。

A.線性表的順序存儲結(jié)構(gòu)B.棧

C.隊(duì)列D.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)順序棧存儲空間的實(shí)現(xiàn)使用(B)。

A．鏈表B．?dāng)?shù)組C．循環(huán)鏈表D．變量順序棧是空棧的條件是(A)。

A．top==0B．top==1C．top==-1D同一個棧內(nèi)各元素的類型(A)。

A．必須一致B．可以不一致C．不能一致D．不必不一致向一個棧頂指針為HS的鏈棧中插入一個s所指結(jié)點(diǎn)時，那么執(zhí)行(C)。

A.HS->next=s;B.s->next=HS->next;HS->next=s;

C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next;循環(huán)隊(duì)列Sq是空隊(duì)列的條件是(A)。

A．Sq->rear==Sq->frontB．(Sq->rear+1〕％maxsize==Sq->front

C．Sq->rear==0D．Sq->front==0循環(huán)隊(duì)列Sq是滿隊(duì)列的條件是(B)。

A．Sq->rear==Sq->frontB．〔Sq->rear+1〕％maxsize==Sq->front

C．Sq->rear==0D．Sq->front==0一個隊(duì)列的入對序列是1,2,3,4,那么隊(duì)列的輸出序列是(B)。

A.4,3,2,1B.1,2,3,4C.1,4,3,2D.一個順序棧一旦說明，其占用空間的大小(A)。

A．已固定B．可以改變C．不能固定D．動態(tài)變化一個棧的入棧序列(順序)是a,b,c,d,e,那么棧不可能的輸出序列是(C)。

A.edcbaB.decbaC.dceabD.abcde一個棧的入棧序列是1,2,3,4,那么棧的可能的輸出序列是(B)。

A.1,4,2,3B.2,1,4,3C.4,2,1,3D.一個棧的入棧序列是a,b,c,d,e,那么棧的不可能的輸出序列是(C)。

A.edcbaB.decbaC.dceabD.abcde以下說法正確的選項(xiàng)是(A)。

A.因鏈棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況

B.因順序棧本身沒有容量限制，故在用戶內(nèi)存空間的范圍內(nèi)不會出現(xiàn)棧滿情況

C.對于鏈棧而言，在棧滿狀態(tài)下，如果再進(jìn)行入棧操作，那么會發(fā)生“上溢”

D.對于順序棧而言，在棧滿狀態(tài)下，如果再進(jìn)行入棧操作，那么會發(fā)生“下溢”元素A、B、C、D依次進(jìn)順序棧后，棧頂元素是(D)。

A．AB．BC．CD．D在計算遞歸函數(shù)時,如不使用遞歸過程，那么一般情況下必須借助(A)數(shù)據(jù)結(jié)構(gòu)

A.棧B.樹C.雙向隊(duì)列D.順序表在棧頂一端可進(jìn)行的全部操作是(C)。

A．插入B．刪除C．插入和刪除D．進(jìn)棧棧操作的原那么是(B)。

A．先進(jìn)先出B．先進(jìn)后出C．只能進(jìn)行插入D．只能進(jìn)行刪除棧的特點(diǎn)是(B)。

A．先進(jìn)先出B．后進(jìn)先出C．后進(jìn)后出D．不進(jìn)不出棧和隊(duì)列的共同點(diǎn)是(C)。

A.都是先進(jìn)后出發(fā)B.都是先進(jìn)先出

C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)棧是限定在(C)處進(jìn)行插入或刪除操作的線性表。

A．端點(diǎn)B．棧底C．棧頂D．中間棧是一個(B)線性表結(jié)構(gòu)。

A．不加限制的B．加了限制的C．推廣了的D．非棧與一般線性表區(qū)別主要在方面(D)。

A．元素個數(shù)B．元素類型C．邏輯結(jié)構(gòu)D．插入、刪除元素的位置四設(shè)串s1=’ABCDEFG’,s2=’PQRST’,函數(shù)con(x,y)返回x和y串的連接串,subs(s,i,j)返回串s的從序號i的字符開始的j個實(shí)際字符組成的子串,len(s)返回串s的長度,那么con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的結(jié)果是(D)。

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF串是任意有限個〔C〕

A符號構(gòu)成的序列B符號構(gòu)成的集合C字符構(gòu)成的序列D字符構(gòu)成的集合設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作(B)

A.連接B.模式匹配C.求子串D.求串長說串是一種特殊的線性表，那么其特殊性表現(xiàn)在(C)。

A.串是可以順序存儲的B.串是可以鏈接存儲的

C.串中的每一個結(jié)點(diǎn)由一個字符組成D.串中的結(jié)點(diǎn)是多個字符組成的五常對數(shù)組進(jìn)行的兩種根本操作是(C)。

A.建立與刪除B.索引和修改C.查找和修改D.查找和索引對矩陣壓縮存儲是為了〔B〕。

A.方便運(yùn)算B.節(jié)省時間C.方便存儲D.提高運(yùn)算速度二維數(shù)組M的成員是6個字符〔每個字符占一個存儲單元〕組成的串，行下標(biāo)I的范圍從0到8，列下標(biāo)j的范圍從1到10，如M按行優(yōu)先方式存儲，元素M[8][5]的起始位置與當(dāng)M按列優(yōu)先方式存儲時的(B)元素的起始地址一致。

A.M[8][5]B.M[3][10]C.M[5][8]D.M[0][9]二維數(shù)組M的成員是6個字符〔每個字符占一個存儲單元〕組成的串，行下標(biāo)I的范圍從0到8，列下標(biāo)j的范圍從1到10，那么M的第8列和第5行共占(A)個字節(jié)。

A.108B.114C.54二維數(shù)組M的成員是6個字符〔每個字符占一個存儲單元〕組成的串，行下標(biāo)I的范圍從0到8，列下標(biāo)j的范圍從1到10，那么存在M至少需要(D)個字節(jié)。

A.90B.180C.240二維數(shù)組M的元素是4個字符〔每個字符占一個存儲單元〕組成的串，行下標(biāo)I的范圍從0到4，列下標(biāo)j的范圍從0到5，M按行存儲時元素M[3][5]的起始地址與M按列存儲時元素(B)的起始地址相同。

A.M[2][4]B.M[3][4]C.M[3][5]D.M[4][4]假設(shè)采用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)(B)。

A.正確B.錯誤設(shè)矩陣A是一個對稱矩陣，為了節(jié)省空間，將其下三角矩陣按行序存放在一維數(shù)組B[1，n〔n+1〕/2]中，對下三角局部中任一元素aij〔i≥j〕，在一維數(shù)B中下標(biāo)k的值是(B)。

A．i〔i-1〕/2+j-1B．i〔i-1/2+jC．i〔i+1〕/2+j-1D．i〔i+1〕/2+j數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)I從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是(C)。

A.50B.100C.240數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)I從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A[5][8]的起始地址為__B__。

A.SA+141B.SA+180C.SA+141D.數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)I從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A[8][5]的起始地址為(C)。

A.SA+141B.SA+144C.SA+222D.數(shù)組的根本操作主要包括(C)。

A．建立與刪除B．索引與修改C．訪問與修改D．訪問與索引稀疏矩陣一般的壓縮存儲方法有兩種，即(C)。

A.二維數(shù)組和三維數(shù)組B.三元組和散列C.三元組和十字鏈D.散列和十字鏈表判斷題1．線性表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。()2．采用線性探測法處理沖突的散列表中，所有同義詞〔其沖突的元素〕在表中相鄰。 (×)3．調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。 (×)4．調(diào)用一次廣度優(yōu)先遍歷可以訪問到圖中的所有頂點(diǎn)。 (√)5．堆是完全二叉樹，完全二叉樹不一定是堆。 (×)6．對鏈表進(jìn)行插入和刪除操作時不必移動鏈表中結(jié)點(diǎn)。 (√)7．分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。 (√)8．快速排序是排序算法中平均性能最好的一種排序。 (√)9．滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹(√)10．冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。 (√)11．任何有向網(wǎng)拓?fù)渑判虻慕Y(jié)果是唯一的。 (×)12．入棧操作和入隊(duì)列操作在鏈?zhǔn)酱鎯Y(jié)構(gòu)上實(shí)現(xiàn)時不需要考慮棧溢出的情況。 (×)13．假設(shè)一個葉子結(jié)點(diǎn)是某二叉樹的中序遍歷序列的最后一個結(jié)點(diǎn)，那么它必是該二叉樹的先序遍歷序列中的最后一個結(jié)點(diǎn)。 (√)14．設(shè)一棵二叉樹的先序序列和后序序列，那么能夠唯一確定出該二叉樹的形狀。 ()15．設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，那么二叉樹BT中一定沒有右子樹。 ()16．順序表查找指的是在順序存儲結(jié)構(gòu)上進(jìn)行查找。 ()17．算法的效率越高越好。 ()18．外部排序過程主要局部分為兩個階段：生成初始?xì)w并段和對歸并段進(jìn)行逐趟歸并。 ()19．希爾排序算法的時間復(fù)雜度為O(n^2)。 ()20．線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。 ()21．用鄰接矩陣法存儲圖時，所占用的空間大小僅與圖中結(jié)點(diǎn)個數(shù)有關(guān)。 ()22．用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，那么其所占用的存儲空間與圖中頂點(diǎn)數(shù)無關(guān)而與圖中邊數(shù)有關(guān)。 ()23．有向圖的鄰接表和逆鄰接表中表結(jié)點(diǎn)的個數(shù)不一定相等。()24．棧和隊(duì)列的存儲方式既可是順序方式，也可是鏈接方式。()25．中序遍歷二叉排序樹可以得到一個有序的序列。 ()26．子串“ABC”在主串“AABCABCD”中的位置為2。 ()完成以下操作(二)

15．設(shè)無向圖G如以下圖所示，給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權(quán)值之和。

16．設(shè)有無向圖G，要求給出用普里姆算法(克魯斯卡爾算法，兩個算法都做)構(gòu)造最小生成樹所走過的邊的集合。

三、思考以下算法設(shè)計設(shè)計一個算法，功能是在帶頭結(jié)點(diǎn)的單鏈表head中刪除數(shù)據(jù)域值最小的結(jié)點(diǎn)。structNode

{

int

Data;

Node*next;

};

void

deleteNode(Node*head,intKeyData)

//KeyData需要刪除的結(jié)點(diǎn)的值

{

Node*p=head;

while(p->next!=NULL)

{

if(p->next->Data==KeyData)

p->next=p->next->next;

p=p->next;

}}有一種簡單的排序算法，叫做計數(shù)排序〔countsorting〕。這種排序算法對一個待排序的表〔用數(shù)組表示，表中所有待排序的關(guān)鍵字互不相同〕進(jìn)行排序，并將排序結(jié)構(gòu)存放到另一個新的表中。計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關(guān)鍵字比該記錄的關(guān)鍵字小。假設(shè)對某一個記錄，統(tǒng)計出計數(shù)值為C，那么，這個記錄在新的有序表中的適宜的存放位置即為C。實(shí)現(xiàn)計數(shù)排序的算法。試以單鏈表為存儲結(jié)構(gòu)實(shí)現(xiàn)簡單項(xiàng)選擇擇排序的算法。voidLinkList_Select_Sort(LinkList&L)//單鏈表上的簡單項(xiàng)選擇擇排序算法{for(p=L;p->next->next;p=p->next)

{

q=p->next;x=q->data;

for(r=q,s=q;r->next;r=r->next)//在q后面尋找元素值最小的結(jié)點(diǎn)

if(r->next->data<x)

{

x=r->next->data;

s=r;

}

if(s!=q)//找到了值比q->data更小的最小結(jié)點(diǎn)s->next

{p->next=s->next;s->next=q;

t=q->next;q->next=p->next->next;

p->next->next=t;

}//交換q和s->next兩個結(jié)點(diǎn)

}//for}//LinkList_Select_Sort編寫一個雙向起泡的排序算法，即相鄰兩趟向相反方向起泡。voidBubble_Sort2