數(shù)據(jù)結(jié)構(gòu)課后答案

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課后答案第1章緒論

1．簡(jiǎn)述以下概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、規(guī)律結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類(lèi)型。

答案：數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫(huà)等通過(guò)特別編碼定義后的數(shù)據(jù)。

數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中尋常作為一個(gè)整體進(jìn)行考慮和處理。在有些狀況下，數(shù)據(jù)元素也稱(chēng)為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹(shù)中棋盤(pán)的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。

數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號(hào)、姓名、性別等都是數(shù)據(jù)項(xiàng)。

數(shù)據(jù)對(duì)象：是性質(zhì)一致的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合N={0，±1，±2，?}，字母字符數(shù)據(jù)對(duì)象是集合C={‘A’，‘B’，?，‘Z’，‘a(chǎn)’，‘b’，?，‘z’}，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。

數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)〞的數(shù)據(jù)元素的集合，“結(jié)構(gòu)〞就是指數(shù)據(jù)元素之間存在的關(guān)系。

規(guī)律結(jié)構(gòu)：從規(guī)律關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的規(guī)律結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。

存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱(chēng)為物理結(jié)構(gòu)。

抽象數(shù)據(jù)類(lèi)型：由用戶(hù)定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱(chēng)。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操作的集合。

2．試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，表達(dá)其規(guī)律結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、專(zhuān)業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的規(guī)律結(jié)構(gòu)，即線性結(jié)構(gòu)。

這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。假使用連續(xù)的存儲(chǔ)單元(如用數(shù)組表示)來(lái)存放這些記錄，則稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)；假使存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)行鏈接，則稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

即一致的規(guī)律結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。

3．簡(jiǎn)述規(guī)律結(jié)構(gòu)的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)

數(shù)據(jù)元素之間除了“屬于同一集合〞的關(guān)系外，別無(wú)其他關(guān)系。例如，確定一名學(xué)生是否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。

（2）線性結(jié)構(gòu)

數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)依照其入學(xué)報(bào)到的時(shí)間先后順序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。

（3）樹(shù)結(jié)構(gòu)

數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每位組長(zhǎng)管理多名組員，從而構(gòu)成樹(shù)形結(jié)構(gòu)。

（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)

數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。

其中樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。

四類(lèi)基本規(guī)律結(jié)構(gòu)關(guān)系圖

4．存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？答案：

（1）順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的規(guī)律關(guān)系，尋常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類(lèi)型來(lái)描述。

（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)尋常借助于程序設(shè)計(jì)語(yǔ)言的指針類(lèi)型來(lái)描述。

5．選擇題

（1）在數(shù)據(jù)結(jié)構(gòu)中，從規(guī)律上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。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)答案：C

（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（）。A．存儲(chǔ)結(jié)構(gòu)B．存儲(chǔ)實(shí)現(xiàn)C．規(guī)律結(jié)構(gòu)D．運(yùn)算實(shí)現(xiàn)答案：C

（3）尋常要求同一規(guī)律結(jié)構(gòu)中的所有數(shù)據(jù)元素具有一致的特性，這意味著（）。A．?dāng)?shù)據(jù)具有同一特點(diǎn)

B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要一致，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類(lèi)型要一致C．每個(gè)數(shù)據(jù)元素都一樣

D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等答案：B

（4）以下說(shuō)法正確的是（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位B．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

D．一些表面上很不一致的數(shù)據(jù)可以有一致的規(guī)律結(jié)構(gòu)答案：D

解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元

素的集合。

（5）算法的時(shí)間繁雜度取決于（）。A．問(wèn)題的規(guī)模B．待處理數(shù)據(jù)的初態(tài)C．計(jì)算機(jī)的配置D．A和B答案：D解釋?zhuān)核惴ǖ臅r(shí)間繁雜度不僅與問(wèn)題的規(guī)模有關(guān)，還與問(wèn)題的其他因素有關(guān)。如某些排序的算法，

其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞以及平均時(shí)間繁雜度的評(píng)價(jià)。

（6）以下數(shù)據(jù)結(jié)構(gòu)中，（）是非線性數(shù)據(jù)結(jié)構(gòu)

A．樹(shù)B．字符串C．隊(duì)列D．棧答案：A

6．試分析下面各程序段的時(shí)間繁雜度。（1）x=90;y=100;

while(y>0)if(x>100)

{x=x-10;y--;}elsex++;

答案：O(1)

解釋?zhuān)撼绦虻膱?zhí)行次數(shù)為常數(shù)階。

（2）for(i=0;i1

y=0;

while(x≥(y+1)*(y+1))y++;答案：O(n)

解釋?zhuān)赫Z(yǔ)句y++;的執(zhí)行次數(shù)為?n?。

第2章線性表

1．選擇題

（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（）。

A．110B．108C．100D．120答案：B

解釋?zhuān)喉樞虮碇械臄?shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。

（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間繁雜度是O(1)的操作是（）。A．訪問(wèn)第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2≤i≤n）B．在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（1≤i≤n）C．刪除第i個(gè)結(jié)點(diǎn)（1≤i≤n）D．將n個(gè)結(jié)點(diǎn)從小到大排序答案：A

解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間繁雜度都是O(n2)，排序的時(shí)間繁雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間繁雜度是O(1)。

（3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（）。

A．8B．63.5C．63D．7答案：B

解釋?zhuān)浩骄苿?dòng)的元素個(gè)數(shù)為：n/2。

（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（）。

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)所占單元數(shù)答案：A

（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（）。A．必需是連續(xù)的B．部分地址必需是連續(xù)的C．一定是不連續(xù)的D．連續(xù)或不連續(xù)都可以答案：D

（6）線性表Ｌ在（）狀況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。

A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值Ｂ．需不斷對(duì)Ｌ進(jìn)行刪除插入C．Ｌ中含有大量的結(jié)點(diǎn)Ｄ．Ｌ中結(jié)點(diǎn)結(jié)構(gòu)繁雜答案：B

解釋?zhuān)烘湵碜畲蟮膬?yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲(chǔ)密度（）。

A．大于1B．等于1C．小于1D．不能確定答案：C

解釋?zhuān)捍鎯?chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。

（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．nB．2n-1C．2nD．n-1答案：A

解釋?zhuān)寒?dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）其次個(gè)表中的元素，只需要用其次個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。

（9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（）個(gè)元素。

A．n-iB．n-i+1C．n-i-1D．I答案：B

(10)線性表L=(a1，a2,??an)，以下說(shuō)法正確的是（）。A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．線性表中至少有一個(gè)元素

C．表中諸元素的排列必需是由小到大或由大到小

D．除第一個(gè)和最終一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。答案：D

(11)創(chuàng)立一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間繁雜度是（）。

A．O(1)B．O(n)C．O(n2)D．O(nlog2n)答案：C

解釋?zhuān)簡(jiǎn)捂湵韯?chuàng)立的時(shí)間繁雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定適合的插入位置，所以時(shí)間繁雜度是O(n2)。

(12)以下說(shuō)法錯(cuò)誤的是（）。

A．求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低

B．順序存儲(chǔ)的線性表可以隨機(jī)存取

C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)答案：D

解釋?zhuān)烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。

(13)在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（）。A．s->next=p+1;p->next=s;

B．(*p).next=s;(*s).next=(*p).next;C．s->next=p->next;p->next=s->next;D．s->next=p->next;p->next=s;答案：D

(14)在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（）。A．p->next->prior=p->prior;p->prior->next=p->next;B．p->next=p->next->next;p->next->prior=p;C．p->prior->next=p;p->prior=p->prior->prior;

D．p->prior=p->next->next;p->next=p->prior->prior;

答案：A

(15)在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（）。A．p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q;D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;答案：C

第3章棧和隊(duì)列

1．選擇題

（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（）種狀況。A．5，4，3，2，1B．2，1，5，4，3C．4，3，1，2，5D．2，3，5，4，1答案：C

解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的狀況。

（2）若已知一個(gè)棧的入棧序列是1，2，3，?，n，其輸出序列為p1，p2，p3，?，pn，若p1=n，則pi為（）。

A．iB．n-iC．n-i+1D．不確定答案：C

解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，?，n，而輸出序列的第一個(gè)元素為n，說(shuō)明1，2，3，?，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，?，pi=n-i+1。

（3）數(shù)組Ｑ［ｎ］用來(lái)表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（）。

A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n答案：D

解釋?zhuān)簩?duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（此題為n），然后與MAXSIZE（此題為n）求余，即（n+r-f)%n。

（4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（）。

A．x=top->data;top=top->link；B．top=top->link;x=top->link；C．x=top;top=top->link；D．x=top->link；答案：A

解釋?zhuān)簒=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。

（5）設(shè)有一個(gè)遞歸算法如下

intfact(intn){//n大于等于0if(n解釋?zhuān)何宸N狀況如下：

AABCABABABBCCCC（3）一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。A．250B．500C．254D．501答案：D

解釋?zhuān)涸O(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹(shù)的性質(zhì)可得B=0或1，又由于C為整數(shù)，所以B=0，C=500，A=501，即有501個(gè)葉子結(jié)點(diǎn)。

（4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（）。

A．11B．10C．11至1025之間D．10至1024之間答案：C

解釋?zhuān)喝裘繉觾H有一個(gè)結(jié)點(diǎn)，則樹(shù)高h(yuǎn)為1025；且其最小樹(shù)高為?log21025?+1=11，即h在11至1025之間。

（5）深度為h的滿(mǎn)m叉樹(shù)的第k層有（）個(gè)結(jié)點(diǎn)。(1=A．棧B.隊(duì)列C.樹(shù)D．圖答案：B

解釋?zhuān)簭V度優(yōu)先遍歷尋常借助隊(duì)列來(lái)實(shí)現(xiàn)算法，深度優(yōu)先遍歷尋常借助棧來(lái)實(shí)現(xiàn)算法。（9）用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，尋常借助（）來(lái)實(shí)現(xiàn)算法。A．棧B.隊(duì)列C.樹(shù)D．圖答案：A

解釋?zhuān)簭V度優(yōu)先遍歷尋常借助隊(duì)列來(lái)實(shí)現(xiàn)算法，深度優(yōu)先遍歷尋常借助棧來(lái)實(shí)現(xiàn)算法。（10）深度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的（）。

A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷答案：A

（11）廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的（）。

A．先序遍歷B．中序遍歷C．后序遍歷D．層次遍歷答案：D

（12）圖的BFS生成樹(shù)的樹(shù)高比DFS生成樹(shù)的樹(shù)高（）。

A．小B．相等C．小或相等D．大或相等答案：C

解釋?zhuān)簩?duì)于一些特別的圖，譬如只有一個(gè)頂點(diǎn)的圖，其BFS生成樹(shù)的樹(shù)高和DFS生成樹(shù)的樹(shù)高相等。一般的圖，根據(jù)圖的BFS生成樹(shù)和DFS樹(shù)的算法思想，BFS生成樹(shù)的樹(shù)高比DFS生成樹(shù)的樹(shù)高小。

（13）已知圖的鄰接矩陣如圖6.30所示，則從頂點(diǎn)v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（）。

圖6.30鄰接矩陣

（14）已知圖的鄰接表如圖6.31所示，則從頂點(diǎn)v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（），按深度優(yōu)先遍歷的結(jié)果是（）。

圖6.31鄰接表

A．0132B．0231C．0321D．0123

答案：D、D

（15）下面（）方法可以判斷出一個(gè)有向圖是否有環(huán)。

A．深度優(yōu)先遍歷B．拓?fù)渑判駽．求最短路徑D．求關(guān)鍵路徑答案：B2．應(yīng)用題

（1）已知圖6.32所示的有向圖，請(qǐng)給出：

①每個(gè)頂點(diǎn)的入度和出度；②鄰接矩陣；③鄰接表；④逆鄰接表。

圖6.32有向圖圖6.33無(wú)向網(wǎng)

答案：

（2）已知如圖6.33所示的無(wú)向網(wǎng)，請(qǐng)給出：①鄰接矩陣；②鄰接表；③最小生成樹(shù)

答案：

①③

??43?????????4?559?????35?5???5?

????55?7654???9?7?3?????????63?2????????5?2?6????54??6????②a→b4→c3

b→a4→c5→d5→e9c→a3→b5→d5→h5d→b5→c5→e7→f6→g5→h4

e→b9→d7→f3f→d6→e3→g2g→d5→f2→h6

（3）已知圖的鄰接矩陣如圖6.34所示。試分別畫(huà)出自頂點(diǎn)1出發(fā)進(jìn)行遍歷所得的深度優(yōu)先生成樹(shù)和廣度優(yōu)先生成樹(shù)。

（4）有向網(wǎng)如圖6.35所示，試用迪拉算法求出從頂點(diǎn)a到其他各頂點(diǎn)間的最徑，完成表6.9。圖6.28鄰接矩陣

杰斯特短路

圖6.34鄰接矩陣圖6.35有向網(wǎng)

表6.9D終點(diǎn)bcdei=115(a,b)2(a,c)12(a,d)∞

i=215(a,b)12(a,d)10(a,c,e)i=315(a,b)11(a,c,f,d)10(a,c,e)i=415(a,b)11(a,c,f,d)i=515(a,b)i=615(a,b)fgS終點(diǎn)集{a,c}{a,c,f}{a,c,f,e}{a,c,f,e,d}∞∞6(a,c,f)∞16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g){a,c,f,e,d,g}{a,c,f,e,d,g,b}

（5）試對(duì)圖6.36所示的AOE-網(wǎng)：

①求這個(gè)工程最早可能在什么時(shí)間終止；

②求每個(gè)活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間；

③確定哪些活動(dòng)是關(guān)鍵活動(dòng)

圖6.36AOE-網(wǎng)

答案：按拓?fù)溆行虻捻樞蛴?jì)算各個(gè)頂點(diǎn)的最早可能開(kāi)始時(shí)間Ve和最遲允許開(kāi)始時(shí)間Vl。然后再計(jì)算各個(gè)活動(dòng)的最早可能開(kāi)始時(shí)間e和最遲允許開(kāi)始時(shí)間l，根據(jù)l-e=0?來(lái)確定關(guān)鍵活動(dòng)，從而確定關(guān)鍵路徑。

1?VeVl00el

0172?19190003?1515151504?293719278191905?38381527126?43432937838380-e17此工程最早完成時(shí)間為43。關(guān)鍵路徑為

第7章查找

1．選擇題

（1）對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率一致，則平均查找長(zhǎng)度為（）。A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C

解釋?zhuān)嚎偛檎掖螖?shù)N=1+2+3+?+n=n(n+1)/2，則平均查找長(zhǎng)度為N/n=(n+1)/2。（2）適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（）。

A．鏈接方式存儲(chǔ)，元素?zé)o序B．鏈接方式存儲(chǔ)，元素有序C．順序方式存儲(chǔ)，元素?zé)o序D．順序方式存儲(chǔ)，元素有序答案：D

解釋?zhuān)赫郯氩檎乙缶€性表必需采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。

（3）假使要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，最好采用()查找法。A．順序查找B．折半查找C．分塊查找D．哈希查找答案：C

解釋?zhuān)悍謮K查找的優(yōu)點(diǎn)是：在表中插入和刪除數(shù)據(jù)元素時(shí)，只要找到該元素對(duì)應(yīng)的塊，就可以在該塊內(nèi)進(jìn)行插入和刪除運(yùn)算。由于塊內(nèi)是無(wú)序的，故插入和刪除比較簡(jiǎn)單，無(wú)需進(jìn)行大量移動(dòng)。假使線性表既要快速查找又經(jīng)常動(dòng)態(tài)變化，則可采用分塊查找。

（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（）比較大小，查找結(jié)果是失敗。

A．20，70，30，50