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

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題匯總

1：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的（1）以及它們之間的（2）和元算等的科學(xué)。AB

（1）A,數(shù)據(jù)元素B計(jì)算方法C規(guī)律存儲(chǔ)D數(shù)據(jù)映像（2）A結(jié)構(gòu)B關(guān)系C運(yùn)算D算法

2：在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(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)

3數(shù)據(jù)的規(guī)律結(jié)構(gòu)是（）關(guān)系的整體。AA數(shù)據(jù)元素之間的規(guī)律B數(shù)據(jù)項(xiàng)之間的規(guī)律C數(shù)據(jù)類型之間

D存儲(chǔ)結(jié)構(gòu)之間

4,在計(jì)算機(jī)的存儲(chǔ)器中表示時(shí)，物理地址和規(guī)律地址一致并且是連續(xù)的，稱之為：（）。A規(guī)律結(jié)構(gòu)

B順序存儲(chǔ)結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D以上都對(duì)

5一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）B

A數(shù)據(jù)項(xiàng)B數(shù)據(jù)元素C數(shù)據(jù)結(jié)構(gòu)

D數(shù)據(jù)類型6數(shù)據(jù)運(yùn)算（

）。A

A，效率與采用何種存儲(chǔ)結(jié)構(gòu)有關(guān)。B是根據(jù)存儲(chǔ)結(jié)構(gòu)來定義的C有算術(shù)運(yùn)算和關(guān)系元算兩大類D必需用程序設(shè)計(jì)語言來描述

7數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指：（

）A數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)

B數(shù)據(jù)結(jié)構(gòu)C數(shù)據(jù)的規(guī)律結(jié)構(gòu)

D數(shù)據(jù)元素之間的關(guān)系

答：A

8在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是：（

）

A規(guī)律結(jié)構(gòu)

B存儲(chǔ)結(jié)構(gòu)C規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)

D物理結(jié)構(gòu)

答A

9數(shù)據(jù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求（）

A每個(gè)結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域B所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域C結(jié)點(diǎn)的最終一個(gè)數(shù)據(jù)域是指針類型

D每個(gè)結(jié)點(diǎn)有多少個(gè)后繼，就設(shè)多少個(gè)指針域答：A

10：以下說法中，不正確的是（

）A數(shù)據(jù)元素是數(shù)據(jù)的基本單位

B數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小克標(biāo)識(shí)單位C數(shù)據(jù)可由若干個(gè)數(shù)據(jù)元素構(gòu)成D數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成答：D11：（

）不是算法的基本特性。A可行性

B程度有限C在規(guī)定的時(shí)間內(nèi)完成

D確定性

答：B

12：計(jì)算機(jī)中算法指的是解決某一種問題的有限運(yùn)算序列，它必需具備輸入，輸出（

）

1

B

A可行性，可移植性和可擴(kuò)展性C確定性，有窮性和穩(wěn)定性答：B

13：一個(gè)算法具有（A可行性C確定性

）

B至少一個(gè)輸入D頑強(qiáng)性

）

B可行性，有窮性和確定性

D易讀性，穩(wěn)定性和確定性

14：下面關(guān)于算法的說法正確的是（A算法最終必需由計(jì)算機(jī)程序?qū)崿F(xiàn)

B為解決某問題的算法同為該問題編寫的程序含義是一致的。C算法的可行性是指指令不能有二義性D以上幾個(gè)都是錯(cuò)誤的。答：B

15：算法的時(shí)間繁雜度與（A問題規(guī)模答：A

16:算法的主要任務(wù)是分析（A算法是否具有較好的可讀性B算法中是否存在語言錯(cuò)誤C算法的功能是否符合設(shè)計(jì)要求D算法的執(zhí)行時(shí)間和問題規(guī)模之間的關(guān)系答：D

17：某算法的時(shí)間繁雜度O(n^2)，說明該算法的（A我那天規(guī)模是n^2答：C

18：算法分析的目的是（

）

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

C.分析算法的效率以求改進(jìn)D.分析算法的易讀性和文檔性

答：算法分析即算法效率分析，包括時(shí)間繁雜度和空間繁雜度分析，其目的是為了改進(jìn)算法效率。此題答案為C。

19.下述函數(shù)中漸進(jìn)時(shí)間繁雜度最小是＿＿。

A.T1(n)=nlbn+5000nB.T2(n)=n-8000nC.T3(n)=n-6000nD.T4(n)=2nlbn-7000lbn

答：T1(n)＝O(nlbn),T2(n)=O(n),T3(n)=O(n),T4(n)=O(nlbn)。其中T1(n)和T4(n)時(shí)間繁雜度的數(shù)量級(jí)一致，但當(dāng)n足夠大時(shí)，lbn>5000n/n-7000,即T1(n)2000lbn,即T1(n)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;

答：先要將*s結(jié)點(diǎn)的next指向*p之后的結(jié)點(diǎn)（s->next=p->next），然后將*p結(jié)點(diǎn)的next指向*s（p->next=s）。所以答案為B。

8.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使得依舊有序，其算法的時(shí)間繁雜度為______。A.O(Ibn)B.O(1)C.O(n2)D.O(n）

答：先要查找到插入結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)的指針，其時(shí)間繁雜度為O(n)。此題答案為D。

9.對(duì)于用一維數(shù)組d[1?.n]順序存儲(chǔ)的線性表，其算法的時(shí)間繁雜度為O(1)的操作是___、______。A.將n個(gè)結(jié)點(diǎn)從小到大排序B.從線性表中刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）C.查找第i個(gè)結(jié)點(diǎn)（1≤i≤n）D.求第i個(gè)結(jié)點(diǎn)（2≤i≤n）的前趨結(jié)點(diǎn)

答：A操作一般需要兩層循環(huán)，時(shí)間繁雜度為O(n2)或O(nIbn)；B操作需要移動(dòng)結(jié)點(diǎn)，時(shí)間繁雜度為O(n)；C操作可以直接由d[i]得到，時(shí)間繁雜度為O(1);D操作也可以直接由d[i-1]得到，時(shí)間繁雜度為O(1)。此題答案為C、D。

10.在一個(gè)單鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是____。D

A．p->next=p;B.p->next->next=p->next;C.p->next->next=p;Dp->next=p->next->next;11.在一個(gè)雙鏈表中，在*p結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)*s的操作是_____。BA．s->prior=p;p->next=s;p->next->prior=s;s->next=p->next;B.s->next=p->next;p->next->prior=s;p->next=s;s->prior=p;C.p->next=s;s->prior=p;s->next=p->next;p->next->prior=s;D.p->next->prior=s;s->next=p->next;s->prior=p;p->next=s;12.在一個(gè)雙鏈表中，刪除*p結(jié)點(diǎn)之后的一個(gè)結(jié)點(diǎn)的操作是_____。CA．p->next=p->next->next;p->next->next->prior=p;B．p->next->prior=p;p->next=p->next->next;C．p->next=p->next->next;p->next->prior=p;D．p->next->next=p->next;p->next->prior=p;

13在不帶頭結(jié)點(diǎn)（頭結(jié)點(diǎn)為*head）的單循環(huán)鏈表中，至少有一個(gè)結(jié)點(diǎn)的條件是＿①＿，尾結(jié)點(diǎn)為*p的條件是＿②＿。AD

A.head!=NULLB.head->next!=headC.p==NULLD.p->next==head

14在帶頭結(jié)點(diǎn)*head的單循環(huán)鏈表中，至少有一個(gè)結(jié)點(diǎn)的條件是＿①＿，尾結(jié)點(diǎn)*p的條件是＿②＿。BDAhead->next!=NULLBhead->next!=headCp==NULLDp->next==head2.4.2填空題

1．在線性表的順序存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過__物理存儲(chǔ)位置___決定的；在線性表的鏈接存儲(chǔ)中，元素之間的規(guī)律關(guān)系是通過___鏈域的指針值___決定的。2．帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件___head->next==NULL__.

3．在一個(gè)單鏈表head中，已知p指向其中的一個(gè)結(jié)點(diǎn)，若要?jiǎng)h除其后的一個(gè)結(jié)點(diǎn)，則執(zhí)行的運(yùn)算是_q=p->next;p->next=q->next;free(q)___.

4．在一個(gè)單鏈表head中，已知p指向其中的一個(gè)結(jié)點(diǎn)，若要在它之前插入一個(gè)結(jié)點(diǎn)，則執(zhí)行的運(yùn)算是s->next=p->next;p->next=s;;temp=p->data;p->data=s->data;s->data=temp;_

5

5．在一個(gè)雙鏈表dhead中，若要在*p結(jié)點(diǎn)之前插入一個(gè)結(jié)點(diǎn)*s,則執(zhí)行的運(yùn)算是__s->next=prior=p->prior;s->prior->next=q;s->next=p;p->prior=s;__.

6．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為__O(1)_,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間繁雜度為___O(n)_.

7．在n個(gè)元素的順序表中刪除任意一個(gè)元素所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為__（n-1）/2____8．在有n個(gè)元素的順序表中任意位置插入一個(gè)元素所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為_n/2_____2.4.3判斷題1．判斷以下表達(dá)的正確性。（1）分派給單鏈表的內(nèi)存單元地址必需是連續(xù)的。

（2）與順序表相比，在鏈表上實(shí)現(xiàn)順序訪問，其算法的效率比較低。（3）從長(zhǎng)度為n的順序表中刪除一個(gè)元素，所需時(shí)間都是O(n).（4）向順序表中插入一個(gè)元素，平均要移動(dòng)大約一半的元素。（5）凡是空的電鏈表都是不含任何結(jié)點(diǎn)的。

（6）假使單鏈表帶有頭結(jié)點(diǎn)，則插入操作永遠(yuǎn)不會(huì)改變頭結(jié)點(diǎn)指針的值。（7）在循環(huán)單鏈表中，任何一個(gè)結(jié)點(diǎn)的指針字段值都不可能為空。答：（1）錯(cuò)誤。分派給單鏈表的內(nèi)存單元地址可以是不連續(xù)的。

（2）錯(cuò)誤。在順序表和鏈表上實(shí)現(xiàn)順序訪問，時(shí)間繁雜度均為O(n)。

（3）錯(cuò)誤。刪除最終一個(gè)元素時(shí)，所需時(shí)間都是O(1)。但從長(zhǎng)度為n的順序表中刪除一個(gè)元素，平均時(shí)間是O(n)。（4）正確。（5）錯(cuò)誤。帶頭結(jié)點(diǎn)單鏈表為空時(shí)仍有一個(gè)頭結(jié)點(diǎn)。（6）正確。（7）正確。2．判斷以下表達(dá)的正確性。

（1）順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大且插入、刪除運(yùn)算效率高。（2）線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

（3）順序存儲(chǔ)結(jié)構(gòu)鼠疫靜態(tài)結(jié)構(gòu)而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。（4）由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活。（5）對(duì)于單鏈表來說，只有從頭結(jié)點(diǎn)開始才能掃描表中全部結(jié)點(diǎn)。

（6）對(duì)于循環(huán)鏈表來說，從表中任一結(jié)點(diǎn)出發(fā)都能通過前后移操作掃描整個(gè)循環(huán)鏈表。（7）雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前驅(qū)和后繼都很簡(jiǎn)單。

答：（1）錯(cuò)誤。順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大但插入、刪除運(yùn)算效率低。（2）錯(cuò)誤。順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)。（3）正確。（4）正確。（5）正確。（6）錯(cuò)誤。對(duì)于循環(huán)鏈表來說，從表中任一結(jié)點(diǎn)出發(fā)都能通過后移操作掃描整個(gè)循環(huán)鏈表，因無前驅(qū)指針，故不能進(jìn)行前移操作。（7）正確。2.4.4簡(jiǎn)答題

1．線性表中有兩種存儲(chǔ)結(jié)構(gòu)：一是順序表，二是鏈表，試問：

（1）假使有n個(gè)線性表同時(shí)共存，并且在處理過程中各表的長(zhǎng)度會(huì)董愛地發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此狀況下應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？為什么？

（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存取結(jié)構(gòu)？為什么？

答：（1）由于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以用任意的存儲(chǔ)空間倆存儲(chǔ)線性表中的各數(shù)據(jù)元素，且其存儲(chǔ)空間可以是連續(xù)的，也可以不連續(xù)；此外，這種存儲(chǔ)結(jié)構(gòu)對(duì)元素進(jìn)行插入和刪除操作時(shí)都無須移動(dòng)元素，而僅僅修改指針即可，多以很適用于線性表容量變化的狀況。

（2）由于順序存儲(chǔ)結(jié)構(gòu)一旦確定了起始位置，線性表中的任何一個(gè)遠(yuǎn)樹都可以進(jìn)行隨機(jī)存取，即存取速度較高；并且，由于線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，所以這一特點(diǎn)恰好避開了順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)，因此，應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)。

2．線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在做插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于需要的空間量難以估計(jì)，所以必需預(yù)先分派較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)展。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠戰(zhàn)勝上述三個(gè)弱點(diǎn)，試探討之。

6

答：（1）不一定。由于鏈?zhǔn)酱鎯?chǔ)需要額外的空間來存儲(chǔ)指針，所以要比順序存儲(chǔ)多占用空間。在空間允許的狀況下，鏈?zhǔn)酱鎯?chǔ)可以戰(zhàn)勝順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，但空間不允許時(shí)，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)會(huì)出現(xiàn)新的問題。3．在單鏈表和雙向鏈表中，能否從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到任一結(jié)點(diǎn)？

答：在單鏈表中只能由當(dāng)前結(jié)點(diǎn)訪問其后繼的任一結(jié)點(diǎn)，但因其沒有指向前驅(qū)的指針而無法訪問其前驅(qū)結(jié)點(diǎn)。在雙向鏈表中，由于當(dāng)前結(jié)點(diǎn)既有指向后繼結(jié)點(diǎn)的指針，又有指向前驅(qū)結(jié)點(diǎn)的指針，所以在雙向鏈表中可以由當(dāng)前結(jié)點(diǎn)出發(fā)訪問表中的任何一個(gè)結(jié)點(diǎn)。4．哪些鏈表從尾指針出發(fā)可以訪問到鏈表中的任意結(jié)點(diǎn)？

答：?jiǎn)窝h(huán)鏈表和雙循環(huán)鏈表可以從尾指針出發(fā)訪問到鏈表中的任意結(jié)點(diǎn)。

5．若較頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表宜采取何種存儲(chǔ)結(jié)構(gòu)？為什么？

5.若用s[1]~s[m]作為順序棧的存儲(chǔ)結(jié)構(gòu)，?？盏臉?biāo)志是棧指針top的值等于m+1，則每進(jìn)行一次______操作，需將top的值加1；每進(jìn)行一次______操作，需將top的值減1。答：這里以s[m]端作為棧底，s[1]端作為棧頂。此題答案：出棧；進(jìn)棧

6.若用不帶頭結(jié)點(diǎn)的單鏈表來表示鏈?zhǔn)綏＃瑒t創(chuàng)立一個(gè)空棧所要執(zhí)行的操作是_________。答：將單鏈表的頭結(jié)點(diǎn)指針賦空值

7.若用帶頭結(jié)點(diǎn)的單鏈表來表示鏈?zhǔn)綏?，則創(chuàng)立一個(gè)空棧所要執(zhí)行的操作是_________。答：將單鏈表的頭結(jié)點(diǎn)指針域賦空值

8.棧和隊(duì)列的區(qū)別僅在于_________。答：刪除元素（即出棧和出隊(duì)）的操作不同

9.若用Q[1]~Q[m]作為非循環(huán)順序隊(duì)列的存儲(chǔ)空間，則最多只能執(zhí)行_________次入隊(duì)操作。答：m10.若用Q[1]~Q[100]作為循環(huán)順序隊(duì)列的存儲(chǔ)空間，Q[f]、Q[r]分別表示隊(duì)首元素和下一個(gè)插入位置，則當(dāng)f=70,r=20時(shí)，隊(duì)列中共有_________個(gè)元素。答：MaxSize=100,元素個(gè)數(shù)=(f-r+MaxSize)%MaxSize=5011.順序隊(duì)列在實(shí)現(xiàn)的時(shí)候，尋常將數(shù)組看成是一個(gè)首尾相連的環(huán)，這樣做的目的是為避免產(chǎn)生__________現(xiàn)象。答：假溢出3.4.3

判斷題1.判斷以下表達(dá)的正確性。

（1）棧底元素是不能刪除的元素。（2）順序棧中元素值的大小是有序的。（3）在n個(gè)元素進(jìn)棧后，它們的出棧順序和進(jìn)棧順序一定正好相反。（4）棧頂元素和棧底元素有可能是同一元素。

（5）若用s[1]~s[m]表示順序棧的存儲(chǔ)結(jié)構(gòu)，則對(duì)棧的進(jìn)棧、出棧操作最多只能進(jìn)行m次。（6）棧是一種對(duì)進(jìn)棧、出棧操作總次數(shù)做了限制的線性表。（7）對(duì)順序棧進(jìn)行進(jìn)棧、出棧操作，不涉及元素的前、后移動(dòng)問題。

（8）棧是一種對(duì)進(jìn)棧、出棧操作的次序做了限制的線性表。（9）空棧沒有棧頂指針。（10）n個(gè)元素進(jìn)隊(duì)列的順序和出隊(duì)列的順序總是一致的。

（11）順序隊(duì)列中有多少元素，可以根據(jù)隊(duì)首指針的值和隊(duì)尾指針的值來計(jì)算。

（12）若用“隊(duì)首指針的值和隊(duì)尾指針的值相等〞作為循環(huán)順序隊(duì)列為空的標(biāo)志，則在設(shè)置一個(gè)空隊(duì)列時(shí)，只需給隊(duì)首指針和隊(duì)尾指針賦同一個(gè)值，不管什么值都可以。

（13）無論是順序隊(duì)列還是鏈接隊(duì)列，插入、刪除運(yùn)算的時(shí)間繁雜度都是O（1）。

（14）隊(duì)列若用不帶頭結(jié)點(diǎn)的非循環(huán)單鏈表來表示鏈?zhǔn)疥?duì)列，則可以用“隊(duì)首指針的值和隊(duì)尾指針的值相等〞作為隊(duì)空的標(biāo)志。

答：（1）錯(cuò)誤。棧底元素可以刪除。（2）錯(cuò)誤。順序棧是指用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧，棧中的元素不是有序的。（3）正確。后進(jìn)棧的元素先出棧，先出棧的元素后出棧。（4）正確。當(dāng)棧中只有一個(gè)元素時(shí)就是這種狀況。

（5）錯(cuò)誤。可以進(jìn)行任意屢屢的進(jìn)棧、出棧操作，但棧中最多只有m個(gè)元素。（6）錯(cuò)誤?？梢赃M(jìn)行任意屢屢的進(jìn)棧、出棧操作。（7）正確。

（8）錯(cuò)誤。只要棧不滿就可以進(jìn)行進(jìn)棧操作，只要棧不空就可以進(jìn)行出棧操作，并不規(guī)定進(jìn)棧、出棧操作的次序。（9）錯(cuò)誤。空棧指棧中沒有元素，但一定要有棧頂指針。

7

（10）正確。后進(jìn)隊(duì)的元素后出隊(duì)，先進(jìn)隊(duì)的元素先出隊(duì)。（11）正確。

（12）正確。由于無論出隊(duì)和入隊(duì)，都要進(jìn)行求余運(yùn)算，將隊(duì)首指針和隊(duì)尾指針轉(zhuǎn)化為有效的順序隊(duì)下標(biāo)值，另外，循環(huán)順序隊(duì)中的元素可以平行移動(dòng)，所以本表達(dá)是正確的。（13）正確。

（14）錯(cuò)誤。應(yīng)當(dāng)用“隊(duì)首指針的值和隊(duì)尾指針的值均為NULL〞作為隊(duì)空的標(biāo)志，隊(duì)首指針的值和隊(duì)尾指針的值相等表示隊(duì)列中有一個(gè)元素。2.判斷以下表達(dá)的正確性。

（1）棧和隊(duì)列都是限制存取端的線性表。

（2）即使對(duì)不含一致元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定一致。（3）消除遞歸不一定需要使用棧。

（4）棧的輸入序列為1，2，3，?，n，輸出序列為a1,a2,?,an,若ai=n(1ai+1>an。3.4.4

簡(jiǎn)答題

1.試各舉一個(gè)實(shí)例，用示意圖和簡(jiǎn)要說明闡述棧和隊(duì)列在程序設(shè)計(jì)中所起的作用。

答：棧的特點(diǎn)是后進(jìn)先出，所以在解決實(shí)際問題涉及后進(jìn)先出的狀況時(shí)，可以考慮使用棧。例如，表達(dá)式的括號(hào)匹配問題。設(shè)置一個(gè)棧，將讀到的左括號(hào)入棧，每讀入一個(gè)右括號(hào)，判斷棧頂是否為左括號(hào)，若是，則出棧；否則，表示不匹配。

隊(duì)列的特點(diǎn)是先進(jìn)先出。例如操作系統(tǒng)中的作業(yè)排隊(duì)，在允大量道程序運(yùn)行的計(jì)算機(jī)系統(tǒng)中，同時(shí)有幾個(gè)作業(yè)運(yùn)行。假使運(yùn)行的結(jié)果都需要通過輸出，那就要按請(qǐng)求輸出的先后次序排隊(duì)。每當(dāng)通道傳輸完畢并可以接受新的輸出任務(wù)時(shí)，隊(duì)頭的作業(yè)先從隊(duì)列中退出做輸出操作。凡是申請(qǐng)輸出的作業(yè)都從隊(duì)尾進(jìn)入隊(duì)列。

2.假定有4個(gè)元素A,B,C,D依次入棧，入棧過程中允許出棧，試寫出所以可能的出棧序列。答：當(dāng)輸入棧的元素為n個(gè)時(shí)，經(jīng)過棧運(yùn)算后可得到的輸出序列個(gè)數(shù)為：n=4時(shí)，出棧序列個(gè)數(shù)為1/5*8!/4!/4!=14種，如表3.1所列。

表3.1

以A開頭

ABCDABDCACBDACDBADCB

以B開頭BACDBADCBCADBCDABDCA以C開頭CBADCBDACDBA以D開頭DCBA

3．假設(shè)以S和X分別表示入棧和出棧操作，則初態(tài)和終態(tài)為?？盏娜霔：统鰲５牟僮餍蛄校梢员硎緸閮H由S和X組成的序列。稱可以實(shí)現(xiàn)的棧操作序列為合法序列（例如SXXS為合法序列，SXXXS為非法序列）。試給出區(qū)分給定序列為合法序列或非法序列的一般準(zhǔn)則，并證明：對(duì)同一輸入序列的兩個(gè)不同的合法序列不可能得到一致的輸出元素序列。

答：合法的棧操作序列必需滿足以下兩個(gè)條件：（1）（2）

在操作序列的任何前綴（從開始到任何一個(gè)操作時(shí)刻）中，S的個(gè)數(shù)不得少于X的個(gè)數(shù)。整個(gè)操作序列中S和X的個(gè)數(shù)相等。

出棧序列

要求證明：對(duì)同一輸入序列a1,a2,?,an的兩個(gè)不同的合法操作序列：

p=p1,p2,?,pj-1,pj,?,p2n,q=q1,q2,?,qj-1,?q2n,不可能得到一致的輸出元素序列。

證明：由于p!=q,所以一定存在一個(gè)j（1

24求最短路徑的迪克斯特拉算法的時(shí)間繁雜度為CA.O(n)B.O(n=e)C.O(n2)D.O(ne)9.4.2填空題

1．有n個(gè)結(jié)點(diǎn)的無向圖最多有_____條邊n（n-1）/22．有n個(gè)頂點(diǎn)的強(qiáng)連通有向圖G至少有___條n-1

3．在有n個(gè)頂點(diǎn)的有向圖中，每個(gè)頂點(diǎn)的度最大可達(dá)______2(n-1)

4、若無向圖G的頂點(diǎn)度數(shù)最小值大于等于時(shí)，G至少有一條回路。答：25、一個(gè)圖的表示法是唯一的，而表示法是不唯一的。

答：圖的表示法主要有鏈接矩陣和鄰接表，前者唯一，后者不唯一。此題答案為：①鏈接矩陣②鄰接表6、用鏈接矩陣A[1?n,1?n]存儲(chǔ)有向圖G，其第i行的所有元素之和等于頂點(diǎn)的。答：出度7、有n個(gè)頂點(diǎn)的有向圖G最多有條弧。答：n（n-1）

8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖。若才用鄰接表表示，則表頭向量的大小為＿所有連接表中的節(jié)點(diǎn)總數(shù)為答：①n②2e

9、已知一個(gè)有向圖的鄰接矩陣表示，刪除所有從第i個(gè)節(jié)點(diǎn)出發(fā)的弧的表示方法是答：將鄰接矩陣第i行全部置零

10、對(duì)于n個(gè)頂點(diǎn)的無向圖，采用鄰接矩陣表示，求圖中邊數(shù)的方法是，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相鄰的方法是，求任意一個(gè)頂點(diǎn)的度的方法是。

答：①鄰接矩陣中1的個(gè)數(shù)出于2②A[i][j]是否為1③吉薩該行中1的個(gè)數(shù)

11、對(duì)于n各頂點(diǎn)的有向圖。采用鄰接表表示，求圖中邊數(shù)的方法是，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相鄰的方法是，求任意一個(gè)頂點(diǎn)的度的方法是。

答：①鄰接矩陣中1的個(gè)數(shù)②A[i][j]是否為1③出度為該行中1的個(gè)數(shù)，入讀為該行列中1的個(gè)數(shù)12、對(duì)于n各頂點(diǎn)的無向圖。采用鄰接表表示，求圖中邊數(shù)的方法是，判斷任意兩個(gè)頂點(diǎn)i和j是否有邊相鄰的方法是，求任意一個(gè)頂點(diǎn)的度的方法是＿＿＿。

答：①鄰接表中結(jié)點(diǎn)個(gè)數(shù)（除表頭結(jié)點(diǎn)外）出于二②從i表頭結(jié)點(diǎn)開頭的鏈表中是否包含結(jié)點(diǎn)③以i表頭結(jié)點(diǎn)開頭的鏈表中的結(jié)點(diǎn)個(gè)數(shù)13、無向圖的連通分量是指。答：最大連通子圖

14、若無向圖中有m條邊；則表示該無向圖的鄰接表中就有結(jié)點(diǎn)。答：2m15、對(duì)n個(gè)頂點(diǎn)的圖來說，他的生成樹一定有條邊。答：n-116、連通分量是無向圖中的的連通子圖。答：極大17、一個(gè)連通圖的是一個(gè)微小連通子圖。答：生成樹

18、普里姆算法算法適用于求的網(wǎng)的最小生成樹，克魯斯卡爾算法適用于求的網(wǎng)的最小生成樹。答：①邊稠密②邊稀疏

19、可以進(jìn)行拓?fù)渑判虻挠邢驁D一定是。答：無環(huán)圖

20、從原點(diǎn)到匯點(diǎn)長(zhǎng)度最長(zhǎng)的路徑稱關(guān)鍵路徑，該路徑上的活動(dòng)成為。答：關(guān)鍵活動(dòng)9.4.3判斷題

1、判斷以下表達(dá)的正確性。

（1）n個(gè)頂點(diǎn)的無向圖至多有n(n-1)條邊

（2）在有向圖中，各頂點(diǎn)的入度和等于各頂點(diǎn)的出度之和。（3）鄰接矩陣只存儲(chǔ)了邊的信息，沒有存儲(chǔ)頂點(diǎn)的信息。

（4）對(duì)同一個(gè)有向圖來說，只保存出邊的鄰接表中結(jié)點(diǎn)的數(shù)目總是和只保存入邊的鄰接表中結(jié)點(diǎn)的數(shù)目一樣多。

（5）假使表示圖的鄰接矩陣是對(duì)稱矩陣，則該圖一定是無向圖。

（6）假使表示有向圖的鄰接矩陣是對(duì)稱矩陣，則該有向圖一定是完全有向圖（7）連通圖的生成樹包含了圖中所有頂點(diǎn)。

16

（8）對(duì)n個(gè)頂點(diǎn)的連通圖G來說，假使其中的某個(gè)子圖有n個(gè)頂點(diǎn)、n-1條邊，則該子圖一定是G的生成樹。

（9）最小生成樹是指邊數(shù)最少的生成樹。

（10）從n個(gè)頂點(diǎn)的連通圖中選取n-1條權(quán)值最小的邊，即可構(gòu)成最小生成樹。（11）強(qiáng)連通圖不能進(jìn)行拓?fù)渑判颉?/p>

（12）只要無向網(wǎng)絡(luò)中沒有權(quán)值一致的邊，其最小生成樹就是唯一的。（13）只要無向網(wǎng)絡(luò)中有權(quán)值一致的邊，其最小生成樹就不可能是唯一的。（14）關(guān)鍵路徑是有權(quán)值最大的變夠成的。

（15）假使表示某個(gè)鄰接圖的鄰接矩陣是不對(duì)稱矩陣，則該圖一定是有向圖。（16）求單源最短路徑的狄克斯特拉算法不適用于有回路的有向網(wǎng)絡(luò)。（17）求單源最短路徑的狄克斯特拉算法不適用于有負(fù)權(quán)邊的有向網(wǎng)絡(luò)。（18）最短路徑一定是簡(jiǎn)單路徑。

答：（1）錯(cuò)誤。n個(gè)頂點(diǎn)的無向圖之多有n(n-1)/2條邊。（2）正確。（3）正確。（4）正確。（5）錯(cuò)誤。如完全有向圖的鄰接矩陣是對(duì)稱矩陣。（6）錯(cuò)誤。（7）正確。（8）錯(cuò)誤（9）錯(cuò)誤（10）錯(cuò)誤，要求不能構(gòu)成回路（11）正確（12）正確（13）錯(cuò)誤（14）錯(cuò)誤（15）正確（16）錯(cuò)誤（17）正確（18）正確2．判斷以下表達(dá)的正確性

（1）連通分量是無向圖中的微小連通子圖。（2）強(qiáng)連通分量是有向圖中的極大強(qiáng)連通子圖。

（3）在一個(gè)有向圖的拓?fù)湫蛄兄?，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條狐。

（4）對(duì)有向圖G，假使以任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先探尋能訪問到每個(gè)頂點(diǎn)，則該圖一定是完全圖。

（5）無向圖中的極大連通子圖稱為連通分量。

（6）連通圖的廣度優(yōu)先探尋中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)。（7）圖的深度優(yōu)先探尋中一般要采用棧來暫存剛訪問過的頂點(diǎn)。（8）有向圖的遍歷不可采用廣度優(yōu)先探尋方法。答：（1）錯(cuò)誤。連通分量是無向圖中的極大連通子圖。

（2）正確（3）錯(cuò)誤。拓?fù)湫蛄许旤c(diǎn)a在頂點(diǎn)b之前并不一定存在弧。

（4）錯(cuò)誤。假使有向圖構(gòu)成雙向有向環(huán)時(shí)，則從任意頂點(diǎn)出發(fā)均能訪問到每個(gè)結(jié)點(diǎn)，但該圖卻非完全圖。（5）正確（6）正確（7）正確（8）錯(cuò)誤9.4.4簡(jiǎn)答題

1.無向圖和有向圖有哪幾種存儲(chǔ)結(jié)構(gòu)？各種結(jié)構(gòu)在圖中的不同操作（圖的遍歷、有向圖的拓?fù)渑判虻龋┲杏惺裁礃拥膬?yōu)越性？

答：無向圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表和鄰接多重表；有向圖的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣、鄰接表和十字鏈表。（1）（2）的。（3）（4）

十字鏈表：簡(jiǎn)單找到以頂點(diǎn)為頭或?yàn)槲驳幕。虼撕?jiǎn)單求得頂點(diǎn)的入度和出度。在有向圖的應(yīng)鄰接多重表：是無向圖的一種十分有效的存儲(chǔ)結(jié)構(gòu)，在其中簡(jiǎn)單求得頂點(diǎn)和邊的各種信息。

用中，十字鏈表是很有用的工具。2.回復(fù)一下關(guān)于圖的問題：

（1）有n個(gè)頂點(diǎn)的有向連通圖最多有多少條邊？最少有多少條邊？

17

鄰接矩陣：可判定圖中任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，并簡(jiǎn)單球的各個(gè)頂點(diǎn)的度。此外，鄰接鏈表：簡(jiǎn)單找到任意頂點(diǎn)的第一個(gè)鄰接點(diǎn)，但要判斷任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連，

對(duì)于圖的遍歷也是可行的。

則需探尋第i個(gè)及第j個(gè)鏈表，者不如鄰接矩陣便利。此外，對(duì)于圖的遍歷和有向圖的拓?fù)渑判蛞彩强尚?/p>

（2）表示一個(gè)有1000個(gè)結(jié)點(diǎn)、1000條邊的有向圖的鄰接矩陣有多少個(gè)矩陣元素？是否為稀疏矩陣？（3）對(duì)于一個(gè)有向圖，不用拓?fù)渑判?，如何判定圖中是否存在環(huán)？

答：（1）有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖最多有n（n-1）條邊（構(gòu)成一個(gè)有向完全圖的狀況）；最少有n條邊（n個(gè)頂點(diǎn)一次首尾相接構(gòu)成一個(gè)環(huán)的狀況）。

（2）這樣的矩陣共有1000個(gè)矩陣元素，不一定是稀疏矩陣，可能時(shí)特別矩陣（如n個(gè)頂點(diǎn)依次首尾相接構(gòu)成一個(gè)環(huán)時(shí)，假設(shè)頂點(diǎn)0到頂點(diǎn)1有弧，···，頂點(diǎn)i到頂點(diǎn)i-1有弧，···，頂點(diǎn)n-1到頂點(diǎn)0有弧，對(duì)應(yīng)的鄰接矩陣中元素A[i][j]有：j-i=1或i-j=n-1，這就是一個(gè)特別的矩陣，可以采用特別的矩陣，可以采用相關(guān)的壓縮方法存儲(chǔ)）。

（3）對(duì)于有向圖進(jìn)行深度優(yōu)先遍歷。假使從有向圖上某個(gè)頂點(diǎn)v出發(fā)的遍歷，DFS（v）終止之前出現(xiàn)一條從頂點(diǎn)u到頂點(diǎn)v的回邊，由于u在生成樹上是v的子孫，則有向圖中必定存在包含頂點(diǎn)v到頂點(diǎn)u的環(huán)。3.一個(gè)有向圖G的鄰接表存儲(chǔ)如圖9.5所示，要求：（1）畫出其鄰接矩陣存儲(chǔ)。123456789

（2）寫出圖的所有強(qiáng)連通分量。

abcdhiegf2

2457329263811.4補(bǔ)充練習(xí)題及參考答案

11.4.1單項(xiàng)選擇題

1.以下排序方法中，時(shí)間繁雜性不受數(shù)據(jù)初始狀態(tài)影響，恒為O（nlbn）的是（A）A.堆排序B.冒泡排序C.直接插入排序D.快速排序2.以下排序方法中，某一趟終止后未必能選出一個(gè)元素放在其最終位置上的是（C）A.堆排序B.冒泡排序C.直接插入排序D.快速排序3.以下排序方法中，在待排序的數(shù)據(jù)已經(jīng)成為有序時(shí),花費(fèi)時(shí)間反而最多的是（A）A.快速排序B.希爾排序C.冒泡排序D.堆排序

4.依次將待排序序列中的元素和有序子序列合并為一個(gè)新的有序子序列的排序方法是（B）A.快速排序B.插入排序C.冒泡排序D.堆排序5.若表R在排序前已按鍵值遞增順序排列,則(A)方法的比較次數(shù)最少.A.直接插入排序B.快速排序C.歸并排序D.選擇排序

18

6.已知表A中每個(gè)元素距其最終位置不遠(yuǎn),采用(B)方法最節(jié)省時(shí)間.

A.堆排序B.冒泡排序C.快速排序D.直接選擇排序7.以下排序方法中，關(guān)鍵字比較次數(shù)與記錄的初始排序無關(guān)的是（D）B.希爾排序B.冒泡排序C.插入排序D.選擇排序8.快速排序方法在(C)狀況下最不利發(fā)揮其優(yōu)點(diǎn).

A.要排序的數(shù)據(jù)量大B.要排序的數(shù)據(jù)中含有多個(gè)一致值C.要排序的數(shù)據(jù)已基本有序D.要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)

9.數(shù)據(jù)表A中有10000個(gè)元素,假使僅要求求出其中最大的10個(gè)元素,則采用(A)方法最省時(shí)間.A.堆排序B.希爾排序C.快速排序D.直接選擇排序

(只有堆排序每次輸出一個(gè)堆頂(即最大或最小值的元素),然后對(duì)堆進(jìn)行再調(diào)整,保證對(duì)頂元素是當(dāng)前剩下元素中最大或最小的,)

10.若一組記錄的排序碼為{46,79,56,38,40,84},則利用堆排序的方法建立的初始堆為()BA．79，46，56，38，40，80B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，38

11.若一組記錄的關(guān)鍵碼為{46,79,56,38,40,84},則利用快速排序的方法，以第1個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）

A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,79

答：對(duì)于{40,79,56,38,40,84},取出46，對(duì){79,56,38,40,84}進(jìn)行劃分，先將79與40交換，得到{40,56,38,79,84}，再將56與38交換，得到{40,38,56,79,84}，將46插入得到{40,38,46，56,79,84}。此題答案為C。

12.一組記錄的關(guān)鍵碼為{25，48，16,35,79,82,23,40,36,72}，其中，含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為（）

A．16,25,35,48,23,40,79,82,36,72B.16,25,35,48,79,82,23,36,40,72C.16,25,48,35,79,82,23,36,40,72D.16,25,35,48,79,23,36,40,72,82

答：對(duì)于{25，48，16,35,79,82,23,40,36,72}，{25，48}和{16，35}兩個(gè)子序列歸并得結(jié)果為{16,25,35,48}，{79,82}和{23,40}兩個(gè)子序列歸并后的結(jié)果為{23，40，79，82}，余下的兩個(gè)記錄不歸并，所以一趟歸并后的結(jié)果為{16,25,35,48,23,40,79,82,36,72}。此題答案為A。

13.已知10個(gè)數(shù)據(jù)元素為{54,28,16,34,73,62,95,60,26,43},對(duì)該數(shù)列按從小到大排序，經(jīng)過一趟冒泡排序后的序列為（）

A．16,28,34,54,73,62,60,26,43,95B.28,16,34,54,62,73,60,26,43,95C.28,16,34,54,62,60,73,26,43,95D.16,28,34,54,62,60,73,26,43,95答：冒泡排序每趟經(jīng)過比較交換從無序區(qū)中產(chǎn)生一個(gè)最大的元素，所以答案為B。

14.用某種排序方法對(duì)線性表{25，84，21，47，15，27，68，35，20}進(jìn)行排序時(shí)，元素序列的變化狀況如下：

(1)25,84,21,47,15,27,68,35,20(2)20,15,21,25,47,27,68,35,84(3)15,20,21,25,35,27,47,68,84(4)15,20,21,25,27,35,47,68,84其所采用的排序方法是（）

A.直接選擇堆序B.希爾排序C.歸并排序D.快速排序

答：從中看到，每趟從無序區(qū)中找出一個(gè)最大的元素定位，所以答案為A。

15.有一組序列{48,36,68,99,75,24,28,52}進(jìn)行快速排序，要求結(jié)果從小到大排序，則進(jìn)行一次劃分之后結(jié)果為（）

A.(24,28,36,)48,(52,68,75,99)B.(28,36,24,)48,(75,99,68,52)C.(36,68,99)48(75,24,28,52)D.(28,36,24)48,(99,75,68,52)

19

答：B

16.一下排序方法中，最好時(shí)間繁雜度為O(n)的依次是（1，2）。A．直接插入排序B.直接選擇排序C.冒泡排序D.快速排序答：1.A2.C

17.以下排序方法中，最壞時(shí)間繁雜度為O(n2)的依次是（1、2）。A．直接插入排序B.直接選擇排序C.堆排序D.歸并排序答：1.A2.B

18.以下排序方法中，平均時(shí)間繁雜度為O(n2)的依次是（1、2）。A．直接插入排序B.冒泡排序C.希爾排序D.基數(shù)排序答：1.A2.B11.4.2填空題

1.在對(duì)一組記錄{50,40,95,20,15,70,60,45,80}進(jìn)行直接選擇排