研究生入學(xué)考試2010年數(shù)據(jù)結(jié)構(gòu)考研輔導(dǎo)復(fù)習(xí)題匯總

?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第1章緒論

計(jì)算機(jī)與信息工程學(xué)院于江德1?數(shù)據(jù)結(jié)構(gòu)?研究?jī)?nèi)容是什么？1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的〔〕以及它們之間的〔〕和〔〕的學(xué)科。2?數(shù)據(jù)結(jié)構(gòu)?中的根本概念你清楚了嗎？2.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的根本概念中，表達(dá)正確的選項(xiàng)是〔〕。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。B.數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。C.任何一個(gè)算法的設(shè)計(jì)取決于選定邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴于采用的存儲(chǔ)結(jié)構(gòu)。D.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。3“數(shù)據(jù)結(jié)構(gòu)〞中的結(jié)構(gòu)指的是？3.“數(shù)據(jù)結(jié)構(gòu)〞中的“結(jié)構(gòu)〞指的是〔〕。A.數(shù)據(jù)的值B.數(shù)據(jù)元素的各數(shù)據(jù)項(xiàng)之間的關(guān)系C.數(shù)據(jù)的構(gòu)成D.數(shù)據(jù)元素之間的關(guān)系4數(shù)據(jù)的邏輯結(jié)構(gòu)如何描述？4.數(shù)據(jù)結(jié)構(gòu)的形式化定義：用一個(gè)二元組表示，記為：Data_Structure=〔D,S〕其中，D是數(shù)據(jù)元素的有限集〔即一個(gè)數(shù)據(jù)對(duì)象〕，S是該對(duì)象中所有數(shù)據(jù)元素之間的關(guān)系的有限集合。5數(shù)據(jù)結(jié)構(gòu)從邏輯上可分為？5.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為〔〕兩大類。A．動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B．順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)C．線性結(jié)構(gòu)、非線性結(jié)構(gòu)D．初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)6數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)6.以下哪一個(gè)術(shù)語(yǔ)與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？A．雙向鏈表B．棧C．線索二叉樹D．哈希表7數(shù)據(jù)結(jié)構(gòu)的根本類型7.以下數(shù)據(jù)結(jié)構(gòu)，〔〕是非線性數(shù)據(jù)結(jié)構(gòu)。A．隊(duì)列B．棧C．二叉樹D．字符串8順序存儲(chǔ)結(jié)構(gòu)8.

下述〔〕是順序存儲(chǔ)方式的優(yōu)點(diǎn)。

a．存儲(chǔ)密度大

b．插入運(yùn)算方便

c．刪除運(yùn)算方便d．?dāng)?shù)據(jù)元素交換方便99.抽象數(shù)據(jù)類型如何描述？抽象數(shù)據(jù)類型可用三元組〔D，S，P〕表示，其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的根本操作集。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉根本操作：〈根本操作的定義〉}ADT抽象數(shù)據(jù)類型名1010.關(guān)于1.3節(jié)的問題typedefStatusOK、ERRORElemType引用參數(shù)&結(jié)合例1-7思考：Triplet是？malloc〔〕注意函數(shù)格式11一個(gè)算法是？11．一個(gè)算法應(yīng)該是〔〕。A．程序B．問題求解步驟的描述C．要滿足五個(gè)根本特性D．A和C.12算法的時(shí)間復(fù)雜度12．某算法的時(shí)間復(fù)雜度為O(n2)，說明該算法的〔〕A問題規(guī)模是n2B執(zhí)行時(shí)間等于n2C執(zhí)行時(shí)間與n2成正比D問題規(guī)模與n2成正比13參考答案2、C3、D5、C6、B7、C8、D11、B12、C14你的問題？Thanks！15?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第2章線性表

計(jì)算機(jī)與信息工程學(xué)院于江德161.線性結(jié)構(gòu)的根本特征①集合中必存在唯一的一個(gè)“第一元素〞；②集合中必存在唯一的一個(gè)“最后元素〞；③除第一元素之外，均有唯一的前驅(qū)；④除最后元素之外，均有唯一的后繼。線性結(jié)構(gòu)是假設(shè)干數(shù)據(jù)元素構(gòu)成的有序〔次序〕集17順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)2.

線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)分別是______。()A.順序存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)B.順序存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)C.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)D.隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)、順序存取的存儲(chǔ)結(jié)構(gòu)183.

一批數(shù)據(jù)用順序存儲(chǔ)結(jié)構(gòu)，第一個(gè)元素的存儲(chǔ)地址是200，且每個(gè)元素長(zhǎng)度為2，那么第5個(gè)元素的存儲(chǔ)地址是()A、210

B、208C、200

D、22019

一、線性表的順序表示用一組地址連續(xù)的存儲(chǔ)單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址，稱作線性表的基地址20以“存儲(chǔ)位置相鄰〞表示有序?qū)?lt;ai-1，ai>即：LOC(ai)=LOC(ai-1)+l一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置LOC(ai)=

LOC(a1)+(i-1)×l

↑基地址214.從具有n個(gè)結(jié)點(diǎn)的單鏈表中查找值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均需比較(

)個(gè)結(jié)點(diǎn)。

A)n

B)n/2

C)(n-1)/2

D)(n+1)/2225.單鏈表中，增加頭結(jié)點(diǎn)的目的是為了(

)。A)方便運(yùn)算的實(shí)現(xiàn)

B)用于標(biāo)識(shí)單鏈表

C)使單鏈表中至少有一個(gè)結(jié)點(diǎn)

D)用于標(biāo)識(shí)起始結(jié)點(diǎn)的位置236、各種存儲(chǔ)結(jié)構(gòu)的描述順序表單鏈表雙向鏈表靜態(tài)鏈表24二、順序映像的C語(yǔ)言描述#defineLIST_INIT_SIZE100//線性表存儲(chǔ)空間的初始分配量#defineLISTINCREMENT10//線性表存儲(chǔ)空間的分配增量typedefstruct{

}SqList;//俗稱順序表ElemType*elem;//存儲(chǔ)空間基址int

length;//當(dāng)前長(zhǎng)度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

//(以sizeof(ElemType)為單位)25

用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。一、線性鏈表的相關(guān)概念以元素(數(shù)據(jù)元素的映象)+指針(指示直接后繼的存儲(chǔ)位置)=結(jié)點(diǎn)(這兩局部信息組成數(shù)據(jù)元素ai的映象)以“結(jié)點(diǎn)的序列〞表示線性表稱作鏈表26

以線性鏈表第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性鏈表的地址，稱作線性表的頭指針頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)〞，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針空指針線性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?7

typedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域}LNode,*LinkList;

二、結(jié)點(diǎn)和單鏈表的C語(yǔ)言描述LinkListL；//L為單鏈表的頭指針數(shù)據(jù)域指針域data*next28structLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域};

typedef

structLNode

LNode;

typedef

LNode

*LinkList;

下面的描述和上頁(yè)的等同嗎？LinkListL；//L為單鏈表的頭指針29結(jié)構(gòu)體成員如何訪問？1、結(jié)構(gòu)體變量中成員的訪問

例如：LNodea； a.data;a.next;2、結(jié)構(gòu)體指針?biāo)附Y(jié)點(diǎn)中成員的訪問

例如：LNode*p；或LinkListp； p->data;p->next;30

2.3.3雙向鏈表typedefstructDuLNode{ElemTypedata;

//數(shù)據(jù)域

structDuLNode*prior;

//指向前驅(qū)的指針域

structDuLNode*next;

//

指向后繼的指針域}

DuLNode,*DuLinkList;31四、靜態(tài)鏈表動(dòng)態(tài)鏈表鏈表中的結(jié)點(diǎn)空間都是動(dòng)態(tài)申請(qǐng)和釋放的。在有些高級(jí)語(yǔ)言〔如BASIC〕中，沒有提供指針類型，此時(shí)假設(shè)仍想采用鏈表作為線性表存儲(chǔ)結(jié)構(gòu)，該如何實(shí)現(xiàn)?那么只能借助一維數(shù)組和游標(biāo)(Cursor)來模擬鏈表，這種鏈表稱為“靜態(tài)鏈表〞。32#defineMAXSIZE 1000 typedefstruct{ElemTypedata;int cur;}Component,SLinkList[MAXSIZE];靜態(tài)鏈表的描述：337、單鏈表中〔1〕帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的單鏈表L判空條件有何不同？ 帶頭結(jié)點(diǎn)：L->next=NULL 不帶頭結(jié)點(diǎn)：L=NULL〔2〕p->data=ai，那么p->next->data=? p->next->data=ai+1348、插入和刪除操作的實(shí)現(xiàn)順序表單鏈表循環(huán)鏈表雙向鏈表雙向循環(huán)鏈表靜態(tài)鏈表359.在一個(gè)有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是()

A.O(1)B.O(n)C.O(n*n)

D.O(nlog2n)3610.假設(shè)某線性表最常用的操作是存取任一指定序號(hào)的元素和在表尾進(jìn)行插入和刪除運(yùn)算，那么利用〔〕存儲(chǔ)方式最節(jié)省時(shí)間。A．順序表B．雙向鏈表C．帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表D．單循環(huán)鏈表3711.

某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，那么采用〔〕存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．僅有頭指針的單循環(huán)鏈表C．雙鏈表D．僅有尾指針的單循環(huán)鏈表3812.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，那么選用()最節(jié)省時(shí)間。A.單鏈表B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表3913．假設(shè)某表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)或刪除最后一個(gè)結(jié)點(diǎn)。那么采用〔〕存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表4014．鏈表不具有的特點(diǎn)是〔〕A．插入、刪除不需要移動(dòng)元素B．可隨機(jī)訪問任一元素C．不必事先估計(jì)存儲(chǔ)空間D．所需空間與線性表長(zhǎng)度成正比4115．靜態(tài)鏈表中指針表示的是〔〕。A．內(nèi)存地址B．?dāng)?shù)組下標(biāo)C．下一元素地址D．左、右孩子地址42算法設(shè)計(jì)題：1.設(shè)計(jì)算法，求帶頭結(jié)點(diǎn)的單循環(huán)鏈表的表長(zhǎng)。2.單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)。3.寫一算法，將帶有頭結(jié)點(diǎn)的非空單鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請(qǐng)新的鏈結(jié)點(diǎn)。4.單鏈表L,寫一算法，返回其倒數(shù)第K個(gè)結(jié)點(diǎn)。5.寫一算法，將一帶有頭結(jié)點(diǎn)的單鏈表就地逆置，即要求逆置在原鏈表上進(jìn)行，不允許重新構(gòu)造新鏈表。43設(shè)L是帶頭結(jié)點(diǎn)的單鏈表(線性表的長(zhǎng)度不包括頭結(jié)點(diǎn))。intLength_LinkList1(LinkListL){LNode*p=L;/*p指向頭結(jié)點(diǎn)*/intj=0;while(p->next){p=p->next;j++}/*p所指的是第j個(gè)結(jié)點(diǎn)*/returnj;}44單鏈表L，寫一算法，刪除其重復(fù)結(jié)點(diǎn)。voidpur_LinkList(LinkListH){LNode*p,*q,*r;p=H->next;/*p指向第一個(gè)結(jié)點(diǎn)*/

if(p==NULL)return;while(p->next){q=p;while(q->next)/*從*p的后繼開始找重復(fù)結(jié)點(diǎn)*/{if(q->next->data==p->data){r=q->next;/*找到重復(fù)結(jié)點(diǎn)，用r指向，刪除*r*/q->next=r->next;

free(r);}elseq=q->next;}p=p->next;/*p指向下一個(gè)，繼續(xù)*/}}45寫一算法，將一帶有頭結(jié)點(diǎn)的單鏈表就地逆置voidLinkList_reverse(LinkList&L){

LinkList

p,q,s; p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next) { q->next=p;p=q; q=s;s=s->next; } q->next=p;s->next=q;L->next=s;}46寫一算法，將帶有頭結(jié)點(diǎn)的非空單鏈表中數(shù)據(jù)域值最小的那個(gè)結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請(qǐng)新的鏈結(jié)點(diǎn)。voiddelinsert(LinkList&L){ p=L->next; //p是鏈表的工作指針 pre=L; //pre指向鏈表中數(shù)據(jù)域最小值結(jié)點(diǎn)的前驅(qū) q=p; //q指向數(shù)據(jù)域最小值結(jié)點(diǎn)，初始假定是第一結(jié)點(diǎn) while(p->next!=NULL) { if(p->next->data<q->data) //找到新的最小值結(jié)點(diǎn) { pre=p; q=p->next;} p=p->next; } if(q!=L->next) //假設(shè)最小值是第一元素結(jié)點(diǎn)，那么不需再操作 { pre->next=q->next; //將最小值結(jié)點(diǎn)從鏈表上摘下 q->next=L->next; //將q結(jié)點(diǎn)插到鏈表最前面 L->next=q; }}47編寫一個(gè)算法來交換單鏈表中指針P所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)，HEAD是該鏈表的頭指針，P指向該鏈表中某一結(jié)點(diǎn)。LinkedListExchange〔LinkedListHEAD，LinkedListp〕∥HEAD是單鏈表頭結(jié)點(diǎn)的指針，p是鏈表中的一個(gè)結(jié)點(diǎn)。本算法將p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)交換。{q=head->next；∥q是工作指針，指向鏈表中當(dāng)前待處理結(jié)點(diǎn)。pre=head；∥pre是前驅(qū)結(jié)點(diǎn)指針，指向q的前驅(qū)。while〔q!=null&&q!=p〕{pre=q；q=q->next；}∥未找到p結(jié)點(diǎn)，后移指針。if〔p->next==null〕printf〔“p無后繼結(jié)點(diǎn)\n〞〕;∥p是鏈表中最后一個(gè)結(jié)點(diǎn)，無后繼。Else∥處理p和后繼結(jié)點(diǎn)交換{q=p->next；∥暫存p的后繼。pre->next=q；∥p前驅(qū)結(jié)點(diǎn)的后繼指向p的后繼。p->next=q->next；∥p的后繼指向原p后繼的后繼。q->next=p；∥原p后繼的后繼指針指向p。}}∥算法結(jié)束。48參考答案2~5、DBDA9、B10、A11、D12、D13、D14、B15、B49你的問題？Thanks！50?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第3章棧和隊(duì)列

計(jì)算機(jī)與信息工程學(xué)院于江德51特殊線性表?xiàng)５亩x操作特性ADT定義根本操作實(shí)現(xiàn)時(shí)間性能隊(duì)列順序棧鏈?zhǔn)綏１容^存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)隊(duì)列定義操作特性ADT定義循環(huán)隊(duì)列鏈?zhǔn)疥?duì)列存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)根本操作實(shí)現(xiàn)時(shí)間性能52棧的特性：后進(jìn)先出〔LIFO〕1.

輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過的棧操作為〔〕A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop53棧的特性：后進(jìn)先出〔LIFO〕2.

有六個(gè)元素按6，5，4，3，2，1的順序進(jìn)棧，問以下哪一個(gè)不是合法的出棧序列？〔〕A.543612B.453126C.346521D.23415654棧的特性：后進(jìn)先出〔LIFO〕3.

假設(shè)一個(gè)棧的入棧序列是1,2,3,......n，其輸出序列為p1,p2,p3,......pn，假設(shè)p1=n，那么pi為〔 〕A.i B.n-iC.n-i+1 D.不確定55棧的特性：后進(jìn)先出〔LIFO〕4.

假設(shè)一個(gè)棧的輸入序列為1，2，3...n，輸出序列的第一個(gè)元素是i，那么第j個(gè)輸出元素是〔〕A.i-j-1B.i-j C.j-i+1 D.不確定56棧的特性：后進(jìn)先出〔LIFO〕5.

設(shè)abcdef以所給的次序進(jìn)棧，假設(shè)在進(jìn)棧操作時(shí)，允許退棧操作,那么下面得不到的序列為〔〕。南京理工大學(xué)1996一、9〔2分〕A．fedcbaB.bcafedC.dcefbaD.cabdef57棧的特性：后進(jìn)先出〔LIFO〕6.

假設(shè)元素a,b,c,d,e,f依次進(jìn)棧，允許進(jìn)棧、退棧操作交替進(jìn)行。但不允許連續(xù)三次進(jìn)行退棧工作，那么不可能得到的出棧序列是〔

〕A：dcebfa

B：cbdaef

C：bcaefd

D：afedcb587.設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用〔〕數(shù)據(jù)結(jié)構(gòu)最正確。A．線性表的順序存儲(chǔ)結(jié)構(gòu)B.隊(duì)列C.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.棧598.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)那么依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是

A)棧

B)隊(duì)列C)樹

D)圖609.假設(shè)棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個(gè)棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，那么棧滿的條件是〔〕。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]61隊(duì)列的特性：先進(jìn)先出〔FIFO〕10.

某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作，但僅允許在一端進(jìn)行出隊(duì)操作，那么不可能得到的順序是〔〕A：bacde

B：dbaceC：dbcae

D：ecbad6211．輸入序列為abcd經(jīng)過輸出受限的雙向隊(duì)列后能得到的輸出序列有〔〕。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不對(duì)6312．假設(shè)以1234作為雙端隊(duì)列的輸入序列，那么既不能由輸入受限的雙端隊(duì)列得到，也不能由輸出受限的雙端隊(duì)列得到的輸出序列是()。A.1234B.4132C.4231D.42136413.設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。假設(shè)每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，那么棧S的容量至少是A)1B)2C)3D)46514.向一個(gè)帶頭結(jié)點(diǎn)HS的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，那么執(zhí)行〔 〕A.HS->next=s; B.s->next=HS->next;HS->next=s;C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next6615.一個(gè)循環(huán)隊(duì)列Q最多可存儲(chǔ)m個(gè)元素，其頭尾指針分別是front和rear，那么判定該循環(huán)隊(duì)列為滿的條件是〔〕A.Q.rear-Q.front==mB.Q.rear!=Q.frontC.Q.front==(Q.rear+1)%mD.Q.front==Q.rear%m+16716.

循環(huán)隊(duì)列用數(shù)組A[0..m-1]存放其元素值，其頭尾指針分別為front和rear，那么當(dāng)前元素個(gè)數(shù)為〔〕。A．(rear–front+m)modmB．rear-front+1C．(front–rear+m)modmD．rear-front6817.假設(shè)用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再參加兩個(gè)元素后，rear和front的值分別為多少？()A.1和5B.2和4C.4和2D.5和16918．用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí),其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn),其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，那么在進(jìn)行刪除操作時(shí)()。A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭,隊(duì)尾指針都可能要修改70參考答案1、BCCDD6、DDBBC11、ECCBC16、ABD71你的問題？Thanks！72?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第5章數(shù)組和廣義表

計(jì)算機(jī)與信息工程學(xué)院于江德73二維數(shù)組的特點(diǎn)：2個(gè)下標(biāo)，每個(gè)元素ai,j受到兩個(gè)關(guān)系〔行關(guān)系和列關(guān)系〕的約束：一個(gè)m×n的二維數(shù)組可以看成是m行的一維數(shù)組，或者n列的一維數(shù)組。N維數(shù)組的特點(diǎn)：n個(gè)下標(biāo)，每個(gè)元素受到n個(gè)關(guān)系約束一個(gè)n維數(shù)組可以看成是由假設(shè)干個(gè)n－1維數(shù)組組成的線性表。a11a12…a1n

a21a22…a2n

……

aij…

am1am2…amn

Amn=74數(shù)組的順序存儲(chǔ)二維數(shù)組A[m][n]按行優(yōu)先尋址計(jì)算方法，每個(gè)數(shù)組元素占據(jù)d個(gè)地址單元。設(shè)數(shù)組的基址為L(zhǎng)OC(a11)：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*d設(shè)數(shù)組的基址為L(zhǎng)OC(a00)：LOC(aij)=LOC(a00)+(i*n+j)*d75數(shù)組的順序存儲(chǔ)二維數(shù)組A[m][n]按列優(yōu)先尋址計(jì)算方法，每個(gè)數(shù)組元素占據(jù)d個(gè)地址單元。設(shè)數(shù)組的基址為L(zhǎng)OC(a11)：LOC(aij)=LOC(a11)+((j-1)*m+i-1)*d設(shè)數(shù)組的基址為L(zhǎng)OC(a00)：LOC(aij)=LOC(a00)+(j*m+i)*d761.

二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。假設(shè)A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素〔〕的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]772.

二維數(shù)組N的每個(gè)元素占4個(gè)存儲(chǔ)單元，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，N按行存儲(chǔ)時(shí)元素N[3][5]的起始地址與N按列存儲(chǔ)時(shí)元素〔 〕的起始地址相同。A.N[2][4] B.N[3][4]C.N[3][5] D.N[4][4]785.3.1特殊矩陣的壓縮存儲(chǔ)特殊矩陣是指非零元素或零元素的分布有一定規(guī)律的矩陣。特殊矩陣的壓縮存儲(chǔ)主要是針對(duì)階數(shù)很高的特殊矩陣。為節(jié)省存儲(chǔ)空間，對(duì)可以不存儲(chǔ)的元素，如零元素或?qū)ΨQ元素，不再存儲(chǔ)。對(duì)稱矩陣〔上三角矩陣、下三角矩陣〕三對(duì)角矩陣79對(duì)稱矩陣的壓縮存儲(chǔ)設(shè)有一個(gè)nn的對(duì)稱矩陣A。在矩陣中，aij=aji該矩陣中數(shù)組元素的下標(biāo)有何特征？80為節(jié)約存儲(chǔ)空間，只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線及對(duì)角線以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)。數(shù)組B共有n+(n-1)++1=n*(n+1)/2個(gè)元素。81上三角矩陣下三角矩陣82下三角矩陣Ba00a10a11a20a21a22a30a31a32……an-1n-1

012345678n(n+1)/2-1假設(shè)ij,數(shù)組元素A[i][j]在數(shù)組B中的存放位置為1+2++i+j=(i+1)*i/2+j前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)83假設(shè)i<j，數(shù)組元素A[i][j]在矩陣的上三角局部,在數(shù)組B中沒有存放，可以找它的對(duì)稱元素A[j][i]：=j*(j+1)/2+i注：書上P95公式〔5-3〕i和j的范圍

84上三角矩陣Ba00a01a02a03a11a12a13a22a23

a33

0123456789假設(shè)ij，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為 n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素總數(shù)第i行第j個(gè)元素前元素個(gè)數(shù)n=485

假設(shè)ij，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j假設(shè)i>j，數(shù)組元素A[i][j]在矩陣的下三角局部，在數(shù)組B中沒有存放。因此，找它的對(duì)稱元素A[j][i]。A[j][i]在數(shù)組B的第(2*n-j-1)*j/2+i的位置中找到。86三對(duì)角矩陣的壓縮存儲(chǔ)Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

01234567891087三對(duì)角矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為0。總共有3n-2個(gè)非零元素。將三對(duì)角矩陣A中三條對(duì)角線上的元素按行存放在一維數(shù)組B中，且a00存放于B[0]。在三條對(duì)角線上的元素aij

滿足

0in-1,i-1ji+1在一維數(shù)組B中A[i][j]在第i行，它前面有3*i-1個(gè)非零元素,在本行中第j列前面有j-i+1個(gè)，所以元素A[i][j]在B中位置為k=

2*i+j。883.

設(shè)n階方陣是一個(gè)上三角矩陣，那么需存儲(chǔ)的元素個(gè)數(shù)為〔〕A．nB．n*nC．n*n/2 D．n(n+1)/2894.

設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，那么a85〔即該元素下標(biāo)ij=85〕的地址為〔〕。A.13B.33C.18D.40905.

假設(shè)對(duì)n階對(duì)稱矩陣A[1..n，1..n]以行序?yàn)橹餍蚍绞较聦⑵湎氯堑脑亍舶ㄖ鲗?duì)角線上的所有元素〕依次存放于一維數(shù)組B[1..n(n+1)/2]中，那么在B中確定aij(i<j)的位置k的關(guān)系為〔〕。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i91參考答案1、BBDBB92你的問題？Thanks！93?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第6章樹和二叉樹

計(jì)算機(jī)與信息工程學(xué)院于江德94樹形結(jié)構(gòu)樹樹的定義根本術(shù)語(yǔ)ADT定義樹的遍歷：先序遍歷后序遍歷層序遍歷二叉樹雙親表示法孩子表示法相互轉(zhuǎn)換存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)孩子兄弟表示法二叉樹的定義二叉樹的性質(zhì)特殊二叉樹二叉樹的性質(zhì)二叉樹的四種遍歷方法滿二叉樹完全二叉樹二叉鏈表順序存儲(chǔ)線索鏈表三叉鏈表遍歷算法實(shí)現(xiàn)基于遍歷的其他算法95二叉樹的遍歷1.

一棵二叉樹的先序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，那么后序遍歷結(jié)果為〔 〕A.CBEFDA B.FEDCBAC.CBEDFA D.不確定96二叉樹的遍歷2.

某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，那么先序遍歷序列為〔〕。A．a(chǎn)cbedB．decabC．deabcD．cedba97二叉樹的遍歷3.

對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用()次序的遍歷實(shí)現(xiàn)編號(hào)。A．先序B.中序C.后序D.從根開始按層次遍歷98二叉樹的遍歷4.

二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK；中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是()A．EB．FC．GD．H99二叉樹的遍歷5.

某二叉樹的先序和后序序列正好相反，那么該二叉樹一定是〔〕的二叉樹。A.空或只有一個(gè)結(jié)點(diǎn)B．高度等于其結(jié)點(diǎn)數(shù)C．任一結(jié)點(diǎn)無左孩子D．任一結(jié)點(diǎn)無右孩子100二叉樹的遍歷5’.

某二叉樹的先序和后序序列正好相反，那么該二叉樹一定是〔〕的二叉樹。A．所有的結(jié)點(diǎn)均無左孩子B．所有的結(jié)點(diǎn)均無右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．是任意一棵二叉樹101二叉樹的遍歷6.

設(shè)n，m為一棵二叉樹的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是〔〕A.n在m的右方 B.n是m的祖先C.n在m的左方 D.n是m的子孫1027.具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中有〔 〕個(gè)度為2的結(jié)點(diǎn)。A.8 B.9 C.10 D.111038.樹中所有結(jié)點(diǎn)的度的和等于所有結(jié)點(diǎn)數(shù)加〔〕。A．0 B．1C．－1 D．21049.在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是〔 〕A．t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不對(duì)10510.

由權(quán)值為9、2、5、7的四個(gè)葉子構(gòu)造一棵哈夫曼樹，該樹的帶權(quán)路徑長(zhǎng)度為〔〕A．23B.37C.44D.4610611．將有關(guān)二叉樹的概念推廣到三叉樹，那么一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度〔〕A．4B．5C．6D．710712．一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為〔〕.A．11B．10C．11至1025之間D．10至1024之間10813.設(shè)森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為N1，N2和N3。與森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是〔〕。A．N1B．N1+N2C．N3D．N2+N310914.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1那么T中的葉子數(shù)為〔〕A．5B．6C．7D．811015.設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為n,森林F中第一棵樹的結(jié)點(diǎn)個(gè)數(shù)是〔〕A．m-nB．m-n-1C．n+1D．條件缺乏，無法確定11116.

假設(shè)一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn)個(gè)數(shù)是〔〕A．9B．11C．15D．不確定11217.一棵完全二叉樹上有1000個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是〔〕A．250B．500C．254D．505E．以上答案都不對(duì)113問:設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，那么它有個(gè)葉子結(jié)點(diǎn)，有個(gè)度為2的結(jié)點(diǎn)，有個(gè)結(jié)點(diǎn)只有非空左子樹，有個(gè)結(jié)點(diǎn)只有非空右子樹。48948810由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說明有1個(gè)結(jié)點(diǎn)只有非空左子樹；而完全二叉樹中不可能出現(xiàn)只有非空右子樹的結(jié)點(diǎn)(0個(gè))。答：易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=log2n＋1=10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511

(完全二叉樹的前k-1層肯定是滿的)所以末層葉子數(shù)為1000-511=489個(gè)。114請(qǐng)注意葉子結(jié)點(diǎn)總數(shù)≠末層葉子數(shù)！還應(yīng)當(dāng)加上第k-1層〔靠右邊〕的0度結(jié)點(diǎn)個(gè)數(shù)。分析：k層的489個(gè)葉子的父結(jié)點(diǎn)占上層的245個(gè)結(jié)點(diǎn)〔489/2)上層〔k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！另一法：可先求2度結(jié)點(diǎn)數(shù),再由此得到葉子總數(shù)。首先，k-2層的28-1〔255〕個(gè)結(jié)點(diǎn)肯定都是2度的〔完全二叉〕另外，末層葉子〔剛剛已求出為489〕所對(duì)應(yīng)的雙親也是度＝2，〔共有489/2＝244個(gè)〕。所以，全部2度結(jié)點(diǎn)數(shù)為255(k-2層)＋244(k-1層)=499個(gè)；總?cè)~子數(shù)＝2度結(jié)點(diǎn)數(shù)＋1=500個(gè)。第i層上的滿結(jié)點(diǎn)數(shù)為2i-1所以，全部葉子數(shù)＝489(末層)＋11(k-1層)=500個(gè)。度為2的結(jié)點(diǎn)＝葉子總數(shù)－1=499個(gè)。11518．設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A．不確定B．2nC．2n+1D．2n-118‘．有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為()A．不確定B．2nC．2n+1D．2n-111619.有關(guān)二叉樹以下說法正確的選項(xiàng)是〔〕A．二叉樹的度為2B．一棵二叉樹的度可以小于2C．二叉樹中至少有一個(gè)結(jié)點(diǎn)的度為2D．二叉樹中任何一個(gè)結(jié)點(diǎn)的度都為211720.一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，那么這棵二叉樹最少有()結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+111821.一棵樹高為K的完全二叉樹至少有〔〕個(gè)結(jié)點(diǎn)A．2k–1B.2k-1–1C.2k-1D.2k11922.對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用()次序的遍歷實(shí)現(xiàn)編號(hào)。A．先序B.中序C.后序D.從根開始按層次遍歷12023.樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的().A.先序序列B.中序序列C.后序序列12124.假設(shè)二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用()遍歷方法最適宜。A．前序B．中序C．后序D．按層次12225.在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序〔〕A．都不相同B．完全相同C．先序和中序相同，而與后序不同D．中序和后序相同，而與先序不同12326.假設(shè)X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，那么x的前驅(qū)為()A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)12427.引入二叉線索樹的目的是〔〕A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹中方便的進(jìn)行插入與刪除C．為了能方便的找到雙親D．使二叉樹的遍歷結(jié)果唯一12528.n個(gè)結(jié)點(diǎn)的線索二叉樹上含有的線索數(shù)為〔〕A．2nB．n－lC．n＋lD．n12629.設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。假設(shè)F中有n個(gè)非終端結(jié)點(diǎn)，那么B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有〔〕個(gè)。A．n-1B．nC．n+1D．n+212730.一棵有n個(gè)結(jié)點(diǎn)的二叉樹，按層次從上到下，同一層從左到右順序存儲(chǔ)在一維數(shù)組A[1..n]中，那么二叉樹中第i個(gè)結(jié)點(diǎn)〔i從1開始用上述方法編號(hào)〕的右孩子在數(shù)組A中的位置是〔〕A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．條件不充分，無法確定12831.設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，那么它有〔〕個(gè)度為2的結(jié)點(diǎn)。A．488B．489C．499D．500129參考答案1、ADCCB〔5‘、C〕6、CBCBC11、CCDDA16、BBDBB21、CCBCB26、CACCD31、C130你的問題？Thanks！131?數(shù)據(jù)結(jié)構(gòu)?〔C語(yǔ)言版〕

第7章圖

計(jì)算機(jī)與信息工程學(xué)院于江德132圖結(jié)構(gòu)圖的定義根本術(shù)語(yǔ)ADT定義圖的遍歷：鄰接矩陣鄰接表存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)完全圖度、入度、出度權(quán)、網(wǎng)路徑、回路連通圖、強(qiáng)連通圖生成樹最小生成樹最短路徑重要應(yīng)用拓?fù)渑判蜿P(guān)鍵路徑1331.

有n個(gè)結(jié)點(diǎn)的無向圖的邊數(shù)最多為〔〕A．n+1B．n(n-1)/2 C．n(n+1) D．2n(n+1)1342.

無向圖中一個(gè)頂點(diǎn)的度是指圖中〔〕A．通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B．通過該頂點(diǎn)的回路數(shù)C．與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目D．與該頂點(diǎn)連通的頂點(diǎn)數(shù)1352’.

無向圖中一個(gè)頂點(diǎn)的度是指圖中〔〕A．通過該頂點(diǎn)的簡(jiǎn)單路徑數(shù)B．通過該頂點(diǎn)的回路數(shù)C．與該頂點(diǎn)相鄰接的頂點(diǎn)數(shù)D．與該頂點(diǎn)連通的頂點(diǎn)數(shù)1363.

在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和與圖的邊數(shù)的比是〔〕A．1:2B．1:1 C．2:1 D．4:11374.

在無向圖中定義頂點(diǎn)Vi與Vj之間的路徑為從Vi到達(dá)Vj的一個(gè)〔〕。A．頂點(diǎn)序列 B．邊序列C．權(quán)值總和D．邊的條數(shù)1385.

在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要〔〕條邊。A．n B.n+1 C.n-1 D.n/21396.

假設(shè)G是一個(gè)具有36條邊的非連通無向圖〔不含自回路和多重邊〕，那么圖G至少有〔〕個(gè)頂點(diǎn)。A．11B.10C.9D.81407.

以下哪一種圖的鄰接矩陣是對(duì)稱矩陣？〔 〕A.有向圖 B.無向圖 C.AOV網(wǎng) D.AOE網(wǎng)1418.簡(jiǎn)單無向圖的鄰接矩陣是對(duì)稱的，可以對(duì)其進(jìn)行壓縮存儲(chǔ)。假設(shè)無向圖G有n個(gè)結(jié)點(diǎn)，其鄰接矩陣為A[1…n,1…n]，且壓縮存儲(chǔ)在B[1…k]，那么k的值至少為〔〕。A．n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/21429.一個(gè)含有n個(gè)頂點(diǎn)和e條邊的簡(jiǎn)單無向圖，在其鄰接矩陣存儲(chǔ)結(jié)構(gòu)中共有〔〕個(gè)零元素。A．eB.2eC.n2-eD.n2-2e14310.假設(shè)采用鄰接矩陣來存儲(chǔ)簡(jiǎn)單有向圖，那么其某一個(gè)頂點(diǎn)i的入度等于該矩陣〔〕。A．第i行中值為1的元素個(gè)數(shù)B.所有值為1的元素個(gè)數(shù)C．第i行及第i列中值為1的元素總個(gè)數(shù)D．第i列中值為1的元素個(gè)數(shù)14411.

下面關(guān)于圖的存儲(chǔ)的表達(dá)中，哪一個(gè)是正確的?！病矨．用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān),而與邊數(shù)無關(guān)B．用鄰接矩陣法存儲(chǔ)圖,占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān),而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)C．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與邊數(shù)無關(guān)D．用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間數(shù)只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)14512．要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要〔〕條邊。A．n-lB．nC．n+lD．2n14613．在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)〔〕倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的〔〕倍。A．1/2B．2C．1D．414714.以下說法不正確的選項(xiàng)是〔〕。A．圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次B．遍歷的根本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個(gè)遞歸過程14815.無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的選項(xiàng)是〔〕。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b149注：南京理工大學(xué)以前的題16.設(shè)圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？〔〕aebdfcacfdebaedfcbaefdcbaefdbcA．5個(gè)B．4個(gè)C．3個(gè)D．2個(gè)150在生成樹的構(gòu)造過程中，圖中n個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹上的頂點(diǎn)集U和尚未落在生成樹上的頂點(diǎn)集V-U，那么應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。一般情況下所添加的頂點(diǎn)應(yīng)滿足以下條件:UV-U151〔1〕初始狀態(tài)：U={u0},〔u0∈V〕，TE={},〔2〕從E中選擇頂點(diǎn)分別屬于U、V-U兩個(gè)集合、且權(quán)值最小的邊〔u0,v0)，將頂點(diǎn)v0歸并到集合U中，邊〔u0,v0)歸并到TE中；〔3〕直到U=V為止。此時(shí)TE中必有n-1條邊，T＝(V,{TE})就是最小生成樹。設(shè)：N=〔V,E〕是個(gè)連通網(wǎng)，另設(shè)U為最小生成樹的頂點(diǎn)集，TE為最小生成樹的邊集。構(gòu)造步驟:普利姆〔Prim〕算法152例：1465231565546362364251[注]：在最小生成樹的生成過程中，所選的邊都是一端在V-U中，另一端在U中。153設(shè)計(jì)思路：①增設(shè)一輔助數(shù)組Closedge[n]，每個(gè)數(shù)組分量都有兩個(gè)域：要求：使Closedge[i].lowcost=min((u,vi))uU計(jì)算機(jī)內(nèi)怎樣實(shí)現(xiàn)Prim〔普里姆〕算法？Prime算法特點(diǎn):

將頂點(diǎn)歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)。故采用鄰接矩陣作為圖的存儲(chǔ)表示。adjvexlowcostvi在U中的鄰點(diǎn)uClosedge[i]V-U中頂點(diǎn)viu與vi之間對(duì)應(yīng)的邊權(quán)從u1~um中挑154vexlowcostvexlowcostvexlowcostvexlowcostvexlowcostvexlowcostV-UU65432vclosedge1423561655536426具體例如：{1}{2,3,4,5,6}1611151∞1∞{1,3}{2,4,5,6}035153634{1,3,6}{2,4,5}35062360{1,3,6,4}{2,5}3503600{1,3,6,4,2}{5}00002300000{1,3,6,4,2,5}{}13起點(diǎn)46245235123456顯然，Prim算法的時(shí)間效率＝O(n2)155步驟：(1)首先構(gòu)造一個(gè)只有n個(gè)頂點(diǎn)但沒有邊的非連通圖T={V,},圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。(2)當(dāng)在邊集E中選到一條具有最小權(quán)值的邊時(shí),假設(shè)該邊的兩個(gè)頂點(diǎn)落在T中不同的連通分量上，那么將此邊參加到生成樹的邊集合T中；否那么將此邊舍去，重新選擇一條權(quán)值最小的邊。(3)如此重復(fù)下去，直到所有頂點(diǎn)在同一個(gè)連通分量上為止。此時(shí)的T即為所求〔最小生成樹〕?？唆斔箍?Kruskal)算法:設(shè)N={V,E}是有n個(gè)頂點(diǎn)的連通網(wǎng)，Kruskal算法采用鄰接表作為圖的存儲(chǔ)表示156Kruskal〔克魯斯卡爾〕算法例：146523156554636215432135246157普里姆算法克魯斯卡爾算法時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍比較兩種算法158有向無環(huán)圖的應(yīng)用①AOV網(wǎng)(ActivityOnVertexNetwork)—用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)AOV網(wǎng)定義：假設(shè)用有向圖表示一個(gè)工程，在圖中用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系。Vi必須先于活動(dòng)Vj進(jìn)行。那么這樣的有向圖叫做用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOV網(wǎng)。②AOE網(wǎng)(ActivityOnEdges)—用邊表示活動(dòng)的網(wǎng)絡(luò)AOE網(wǎng)定義：如果在無環(huán)的帶權(quán)有向圖中，用有向邊表示一個(gè)工程中的活動(dòng)，用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間，用頂點(diǎn)表示事件，那么這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOE網(wǎng)。有兩種常用的活動(dòng)網(wǎng)絡(luò)〔ActivityNetwork〕：159AOV網(wǎng)絡(luò)的用途：7.5.1拓?fù)渑判蚶?：教學(xué)方案的制定AOV網(wǎng)絡(luò)假設(shè)用于教學(xué)方案的制定，可以解決：哪些課程是必須先修的，哪些課程是可以并行學(xué)習(xí)的。預(yù)備知識(shí)：拓?fù)渑判蚴裁唇型負(fù)渑判?？由某個(gè)集合上的一個(gè)偏序得到的該集合上的一個(gè)全序，這個(gè)操作稱之為拓?fù)渑判?。直觀看，偏序指集合中僅有局部成員之間可比較，而全序指集合中全體成員之間均可比較。實(shí)質(zhì)：對(duì)一個(gè)有向無環(huán)圖中的頂點(diǎn)排成一個(gè)具有前后次序的線性序列。160進(jìn)行拓?fù)渑判虻姆椒ǎ狠斎階OV網(wǎng)絡(luò)。令n為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn),并輸出之;

從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊;

重復(fù)以上2、3步,直到：全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿?；或：圖中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。拓?fù)渑判蛩惴ǎ褐貜?fù)選擇沒有直接前驅(qū)的頂點(diǎn)。

161abcdefghk64521187244用邊表示活動(dòng)的網(wǎng)〔AOE網(wǎng)〕例如:源點(diǎn)匯點(diǎn)6174頂點(diǎn)：事件；有向邊：活動(dòng)有向邊對(duì)應(yīng)的權(quán)：活動(dòng)持續(xù)的時(shí)間162AOE網(wǎng)絡(luò)的用途：常用于大型工程的方案管理。利用AOE網(wǎng)絡(luò)可以解決以下兩個(gè)問題：(1)完成整個(gè)工程至少需要多少時(shí)間。(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?(2)為縮短完成工程所需的時(shí)間,應(yīng)當(dāng)加快哪些活動(dòng)?或者說，哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？7.5.2關(guān)鍵路徑163整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑。abcdefghk64521187244例如:“關(guān)鍵活動(dòng)〞指的是：該弧上的權(quán)值增加將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加。顯然……源點(diǎn)匯點(diǎn)6174164

如何求關(guān)鍵活動(dòng)？“關(guān)鍵活動(dòng)〞有何特征？該活動(dòng)的最早開始時(shí)間=該活動(dòng)的最遲開始時(shí)間jkdut165假設(shè)第i條弧為<j,k>,那么對(duì)第i項(xiàng)活動(dòng)而言“活動(dòng)(弧)〞的最早開始時(shí)間e(i):e(i)=ve(j);“活動(dòng)(弧)〞的最遲開始時(shí)間l(i):l(i)=vl(k)–dut(<j,k>);事件發(fā)生時(shí)間的計(jì)算公式:ve(源點(diǎn))=0;ve(k)=Max{ve(j)+dut(<j,k>)}vl(匯點(diǎn))=ve(匯點(diǎn));vl(j)=Min{vl(k)–dut(<j,k>)}“事件(頂點(diǎn))〞的最早發(fā)生時(shí)間ve(j)ve(j)=從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度;“事件(頂點(diǎn))〞的最遲發(fā)生時(shí)間vl(k)vl(k)=關(guān)鍵路徑長(zhǎng)度-從頂點(diǎn)k到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度;166求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計(jì)算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9頂點(diǎn)VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng)ell-e00002266046258377077071031616014140033167求從源點(diǎn)到其余各點(diǎn)的最短路徑的算法的根本思想:依最短路徑的長(zhǎng)度遞增的次序求得各條路徑源點(diǎn)v1…其中，從源點(diǎn)到頂點(diǎn)v1的最短路徑是所有最短路徑中長(zhǎng)度最短者。思考：該路徑有何特點(diǎn)？v2求最短路徑的迪杰斯特拉算法：一般情況下，Dist[k]=<源點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>或者=<源點(diǎn)到其它頂點(diǎn)的路徑長(zhǎng)度>+<其它頂點(diǎn)到頂點(diǎn)k的弧上的權(quán)值>設(shè)置輔助數(shù)組Dist，其中每個(gè)分量Dist[k]表示當(dāng)前所求得的從源點(diǎn)到其余各頂點(diǎn)k的最短路徑。168在這條路徑上，必定只含一條弧，且這條弧的權(quán)值最小。(v1)

下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):路徑長(zhǎng)度最短的最短路徑的特點(diǎn):它只可能有兩種情況:或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；

或者是，從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)。其余最短路徑的特點(diǎn)：再下一條路徑長(zhǎng)度次短的最短路徑的特點(diǎn):它可能有三種情況：或者是，直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是，從源點(diǎn)經(jīng)過頂點(diǎn)v1，再到達(dá)該頂點(diǎn)(由兩條弧組成)；或者是,從源點(diǎn)經(jīng)過頂點(diǎn)v2,再到達(dá)該頂點(diǎn)〔由兩條弧或三條弧〕。它或者是直接從源點(diǎn)到該點(diǎn)(只含一條弧)；或者是，從源點(diǎn)經(jīng)過已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。169迪杰斯特拉(Dijkstra)算法思想按路徑長(zhǎng)度遞增次序產(chǎn)生最短路徑算法：把V分成兩組：(1) S：已求出最短路徑的頂點(diǎn)的集合(2) V-S=T：尚未確定最短路徑的頂點(diǎn)集合求解的過程是將T中頂點(diǎn)按最短路徑遞增的次序參加到S中，保證(1)從源點(diǎn)V0到S中各頂點(diǎn)的最短路徑長(zhǎng)度都不大于從V0到T中任何頂點(diǎn)的最短路徑長(zhǎng)度(2)每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離值S中頂點(diǎn)：從V0到此頂點(diǎn)的最短路徑長(zhǎng)度T中頂點(diǎn)：從V0到此頂點(diǎn)的只包括S中頂點(diǎn)作中間頂點(diǎn)的最短路徑長(zhǎng)度依據(jù)：可以證明V0到T中頂點(diǎn)Vk的最短路徑，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點(diǎn)到Vk的路徑權(quán)值之和〔反證法可證〕170(v0,v2)+(v2,v3)<(v0,v3)終點(diǎn)

從v0到各終點(diǎn)的dist值和最短路徑v1v2v3v4v5vjS之外的當(dāng)前最短路徑之頂點(diǎn)60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}10{v0,v2}∞

30{v0,v4}100{v0,v5}∞∞∞∞例3：v2v4v3v5100{v0,v5}012345dist[w]01234510{v0,v2}50{v0,v4,v3}30{v0,v4}17117.

在圖采用鄰接表存儲(chǔ)時(shí)，求最小生成樹的Prim算法的時(shí)間復(fù)雜度為()。A.O(n) B.O(n+e)C.O(n2)D.O(n3)17218.下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點(diǎn)和邊，初始為〔1〕，下面步驟重復(fù)n-1次:a：〔2〕；b：〔3〕；最后：〔4〕。CABA〔1〕．A．VT，ET為空B．VT為所有頂點(diǎn)，ET為空C．VT為網(wǎng)中任意一點(diǎn)，ET為空D．VT為空，ET為網(wǎng)中所有邊〔2〕．A.選i屬于VT，j不屬于VT，且〔i，j〕上的權(quán)最小B．選i屬于VT，j不屬于VT，且〔i，j〕上的權(quán)最大C．選i不屬于VT，j不屬于VT，且〔i，j〕上的權(quán)最小D．選i不屬于VT，j不屬于VT，且〔i，j〕上的權(quán)最大〔3〕．A．頂點(diǎn)i參加VT，〔i,j〕參加ETB.頂點(diǎn)j參加VT，〔i,j〕參加ETC.頂點(diǎn)j參加VT，〔i,j〕從ET中刪去D．頂點(diǎn)i,j參加VT，〔i,j〕參加ET〔4〕．A．ET中為最小生成樹B．不在ET中的邊構(gòu)成最小生成樹C．ET中有n-1條邊時(shí)為生成樹，否那么無解D．ET中無回路時(shí)，為生成樹，否那么無解17319.有向圖G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={<v1,v2>，<v1,v3>，<v1,v4>，<v2,v5>，<v3,v5>，<v3,v6>，<v4,v6>，<v3,v7>，<v6,v7>}，G的拓?fù)湫蛄惺恰病?。A．v1,v3,v4,v6,v2,v5,v7B．v1,v3,v2,v6,v4,v5,v7C．v1,v3,v4,v5,v2,v6,v7D．v1,v2,v5,v3,v4,v6,v717420.一個(gè)有向無環(huán)圖的拓?fù)渑判蛐蛄小病呈俏ㄒ坏?。A．一定B．不一定17521.在有向圖G的拓?fù)湫蛄兄?，假設(shè)頂點(diǎn)Vi在頂點(diǎn)Vj之前，那么以下情形不可能出現(xiàn)的是〔〕。A．G中有弧<Vi，Vj>B．G