研究生入學考試2010年數(shù)據(jù)結(jié)構考研輔導復習題匯總

?數(shù)據(jù)結(jié)構?〔C語言版〕

第1章緒論

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

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

a．存儲密度大

b．插入運算方便

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

第2章線性表

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

線性表的順序存儲結(jié)構和鏈式存儲結(jié)構分別是______。()A.順序存取的存儲結(jié)構、順序存取的存儲結(jié)構B.順序存取的存儲結(jié)構、隨機存取的存儲結(jié)構C.隨機存取的存儲結(jié)構、隨機存取的存儲結(jié)構D.隨機存取的存儲結(jié)構、順序存取的存儲結(jié)構183.

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

B、208C、200

D、22019

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

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

a1a2

…ai-1ai

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

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

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

)個結(jié)點。

A)n

B)n/2

C)(n-1)/2

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

)。A)方便運算的實現(xiàn)

B)用于標識單鏈表

C)使單鏈表中至少有一個結(jié)點

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

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

length;//當前長度int

listsize;//當前分配的存儲容量

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

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

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

a1a2…...an^頭指針頭指針有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點〞，以指向頭結(jié)點的指針為鏈表的頭指針空指針線性表為空表時，頭結(jié)點的指針域為空27

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

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

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

structLnode*next;//指針域};

typedef

structLNode

LNode;

typedef

LNode

*LinkList;

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

例如：LNodea； a.data;a.next;2、結(jié)構體指針所指結(jié)點中成員的訪問

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

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

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

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

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

free(r);}elseq=q->next;}p=p->next;/*p指向下一個，繼續(xù)*/}}45寫一算法，將一帶有頭結(jié)點的單鏈表就地逆置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é)點的非空單鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點。voiddelinsert(LinkList&L){ p=L->next; //p是鏈表的工作指針 pre=L; //pre指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū) q=p; //q指向數(shù)據(jù)域最小值結(jié)點，初始假定是第一結(jié)點 while(p->next!=NULL) { if(p->next->data<q->data) //找到新的最小值結(jié)點 { pre=p; q=p->next;} p=p->next; } if(q!=L->next) //假設最小值是第一元素結(jié)點，那么不需再操作 { pre->next=q->next; //將最小值結(jié)點從鏈表上摘下 q->next=L->next; //將q結(jié)點插到鏈表最前面 L->next=q; }}47編寫一個算法來交換單鏈表中指針P所指結(jié)點與其后繼結(jié)點，HEAD是該鏈表的頭指針，P指向該鏈表中某一結(jié)點。LinkedListExchange〔LinkedListHEAD，LinkedListp〕∥HEAD是單鏈表頭結(jié)點的指針，p是鏈表中的一個結(jié)點。本算法將p所指結(jié)點與其后繼結(jié)點交換。{q=head->next；∥q是工作指針，指向鏈表中當前待處理結(jié)點。pre=head；∥pre是前驅(qū)結(jié)點指針，指向q的前驅(qū)。while〔q!=null&&q!=p〕{pre=q；q=q->next；}∥未找到p結(jié)點，后移指針。if〔p->next==null〕printf〔“p無后繼結(jié)點\n〞〕;∥p是鏈表中最后一個結(jié)點，無后繼。Else∥處理p和后繼結(jié)點交換{q=p->next；∥暫存p的后繼。pre->next=q；∥p前驅(qū)結(jié)點的后繼指向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é)構?〔C語言版〕

第3章棧和隊列

計算機與信息工程學院于江德51特殊線性表棧棧的定義操作特性ADT定義根本操作實現(xiàn)時間性能隊列順序棧鏈式棧比較存儲結(jié)構邏輯結(jié)構隊列定義操作特性ADT定義循環(huán)隊列鏈式隊列存儲結(jié)構邏輯結(jié)構根本操作實現(xiàn)時間性能52棧的特性：后進先出〔LIFO〕1.

輸入序列為ABC，可以變?yōu)镃BA時，經(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棧的特性：后進先出〔LIFO〕2.

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

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

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

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

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

〕A：dcebfa

B：cbdaef

C：bcaefd

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

A)棧

B)隊列C)樹

D)圖609.假設棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(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隊列的特性：先進先出〔FIFO〕10.

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

B：dbaceC：dbcae

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

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

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

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

a21a22…a2n

……

aij…

am1am2…amn

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

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

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

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

84上三角矩陣Ba00a01a02a03a11a12a13a22a23

a33

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

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

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

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

滿足

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

2*i+j。883.

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

設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，那么a85〔即該元素下標ij=85〕的地址為〔〕。A.13B.33C.18D.40905.

假設對n階對稱矩陣A[1..n，1..n]以行序為主序方式下將其下三角的元素〔包括主對角線上的所有元素〕依次存放于一維數(shù)組B[1..n(n+1)/2]中，那么在B中確定aij(i<j)的位置k的關系為〔〕。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é)構?〔C語言版〕

第6章樹和二叉樹

計算機與信息工程學院于江德94樹形結(jié)構樹樹的定義根本術語ADT定義樹的遍歷：先序遍歷后序遍歷層序遍歷二叉樹雙親表示法孩子表示法相互轉(zhuǎn)換存儲結(jié)構邏輯結(jié)構存儲結(jié)構邏輯結(jié)構孩子兄弟表示法二叉樹的定義二叉樹的性質(zhì)特殊二叉樹二叉樹的性質(zhì)二叉樹的四種遍歷方法滿二叉樹完全二叉樹二叉鏈表順序存儲線索鏈表三叉鏈表遍歷算法實現(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.

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

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

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

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

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

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

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

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

第7章圖

計算機與信息工程學院于江德132圖結(jié)構圖的定義根本術語ADT定義圖的遍歷：鄰接矩陣鄰接表存儲結(jié)構邏輯結(jié)構完全圖度、入度、出度權、網(wǎng)路徑、回路連通圖、強連通圖生成樹最小生成樹最短路徑重要應用拓撲排序關鍵路徑1331.

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

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

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

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

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

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

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

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

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

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

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

重復以上2、3步,直到：全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或：圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時AOV網(wǎng)絡中必定存在有向環(huán)。拓撲排序算法：重復選擇沒有直接前驅(qū)的頂點。

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

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

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

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

從v0到各終點的dist值和最短路徑v1v2v3v4v5vjS之外的當前最短路徑之頂點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.

在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為()。A.O(n) B.O(n+e)C.O(n2)D.O(n3)17218.下面是求連通網(wǎng)的最小生成樹的prim算法：集合VT，ET分別放頂點和邊，初始為〔1〕，下面步驟重復n-1次:a：〔2〕；b：〔3〕；最后：〔4〕。CABA〔1〕．A．VT，ET為空B．VT為所有頂點，ET為空C．VT為網(wǎng)中任意一點，ET為空D．VT為空，ET為網(wǎng)中所有邊〔2〕．A.選i屬于VT，j不屬于VT，且〔i，j〕上的權最小B．選i屬于VT，j不屬于VT，且〔i，j〕上的權最大C．選i不屬于VT，j不屬于VT，且〔i，j〕上的權最小D．選i不屬于VT，j不屬于VT，且〔i，j〕上的權最大〔3〕．A．頂點i參加VT，〔i,j〕參加ETB.頂點j參加VT，〔i,j〕參加ETC.頂點j參加VT，〔i,j〕從ET中刪去D．頂點i,j參加VT，〔i,j〕參加ET〔4〕．A．ET中為最小生成樹B．不在ET中的邊構成最小生成樹C．ET中有n-1條邊時為生成樹，否那么無解D．ET中無回路時，為生成樹，否那么無解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的拓撲序列是〔〕。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.一個有向無環(huán)圖的拓撲排序序列〔〕是唯一的。A．一定B．不一定17521.在有向圖G的拓撲序列中，假設頂點Vi在頂點Vj之前，那么以下情形不可能出現(xiàn)的是〔〕。A．G中有弧<Vi，Vj>B．G