數(shù)據(jù)結(jié)構(gòu)強(qiáng)化習(xí)題課匯總

精選優(yōu)質(zhì)文檔-----傾情為你奉上精選優(yōu)質(zhì)文檔-----傾情為你奉上專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)精選優(yōu)質(zhì)文檔-----傾情為你奉上專(zhuān)心---專(zhuān)注---專(zhuān)業(yè)緒論考點(diǎn)1數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)數(shù)據(jù)的邏輯結(jié)構(gòu)是指（），數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指（）分析：數(shù)據(jù)結(jié)構(gòu)包括三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)的運(yùn)算。其中，邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，存儲(chǔ)結(jié)構(gòu)是指邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。解答：數(shù)據(jù)元素之間的邏輯關(guān)系；數(shù)據(jù)的邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)。在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為：（A）A線(xiàn)性和非線(xiàn)性結(jié)構(gòu)B緊湊和非緊湊結(jié)構(gòu)C動(dòng)態(tài)和靜態(tài)結(jié)構(gòu)D內(nèi)部和外部結(jié)構(gòu)分析：數(shù)據(jù)結(jié)構(gòu)中，邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。線(xiàn)性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存儲(chǔ)結(jié)構(gòu)。線(xiàn)性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，所有結(jié)點(diǎn)之間的存儲(chǔ)單元地址可連續(xù)可不連續(xù)。邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、所含結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)。關(guān)鍵考點(diǎn)點(diǎn)評(píng)：線(xiàn)性結(jié)構(gòu)的特征，有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)，所有結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)和后繼。棧和隊(duì)列。非線(xiàn)性結(jié)構(gòu)的結(jié)點(diǎn)有多個(gè)前驅(qū)或后繼，樹(shù)和圖。數(shù)據(jù)結(jié)構(gòu)在物理上可以分為（）存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。分析：物理存儲(chǔ)解答：順序下列術(shù)語(yǔ)中，（）與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)A循環(huán)隊(duì)列B堆棧C散列表D單鏈表解答：A（）不是算法所必須具備的特性A有窮性B確定性C高效性D可行性分析：算法的五個(gè)重要特征：有窮性、確定性、可行性、輸入和輸出。解答：C考點(diǎn)2時(shí)間復(fù)雜度計(jì)算設(shè)n是描述問(wèn)題規(guī)模的非負(fù)整數(shù)，下面程序段的時(shí)間復(fù)雜度是（）線(xiàn)性表考點(diǎn)1線(xiàn)性表的基本概念線(xiàn)性表是n個(gè)（）的有限序列。A字符B數(shù)據(jù)元素C由數(shù)據(jù)項(xiàng)D信息項(xiàng)解析：解答B(yǎng)線(xiàn)性表是一個(gè)（）。A有限序列，可以為空B有限序列，不能為空C無(wú)限序列，可以為空D無(wú)限序列，不能為空解答A關(guān)鍵考點(diǎn)點(diǎn)評(píng)：對(duì)于非空線(xiàn)性表有且僅有一個(gè)開(kāi)始結(jié)點(diǎn)，沒(méi)有直接前驅(qū)，有且僅有一個(gè)直接后繼；有且僅有一個(gè)終結(jié)結(jié)點(diǎn)，沒(méi)有直接后繼，有且僅有一個(gè)直接前驅(qū)；其余的內(nèi)部結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和后繼單鏈表不能隨機(jī)存取元素原因是：要得到元素的存儲(chǔ)地址，必須（）解答：從起始結(jié)點(diǎn)開(kāi)始掃描以得到其地址注：順序表可以，但是鏈表不行考點(diǎn)2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)下述（）是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)A插入運(yùn)算方便B可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示C存儲(chǔ)密度大D刪除運(yùn)算方便解答：C線(xiàn)性表的（）存儲(chǔ)結(jié)構(gòu)是隨機(jī)存儲(chǔ)結(jié)構(gòu)。分析：隨機(jī)存儲(chǔ)結(jié)構(gòu)代表可以直接訪(fǎng)問(wèn)其中的任意一個(gè)元素。解答：順序關(guān)鍵考點(diǎn)點(diǎn)評(píng)：順序存儲(chǔ)：把線(xiàn)性表的結(jié)點(diǎn)按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。一般可以用數(shù)組實(shí)現(xiàn)。設(shè)線(xiàn)性表有n個(gè)元素，以下操作中，（）在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率更高A輸出第i個(gè)元素值B交換第一個(gè)第二個(gè)元素的值C順序輸出所有元素D輸出與給定值x相等的元素在線(xiàn)性表中的序號(hào)解答：A若某線(xiàn)性表最常用的操作是存取任意指定序號(hào)的元素和最后進(jìn)行插入和刪除運(yùn)算，則利用（）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表B雙鏈表C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D單循環(huán)鏈表解答：A若長(zhǎng)度為n的線(xiàn)性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度是（）AO（0）BO（1）CO（n）DO（n*n）分析：順序表的插入算法中，當(dāng)n個(gè)空間已滿(mǎn)時(shí)，可申請(qǐng)?jiān)僭黾臃峙鋗個(gè)空間。若申請(qǐng)失敗，則說(shuō)明系統(tǒng)沒(méi)有（）可分配的存儲(chǔ)空間。Am個(gè)Bm個(gè)連續(xù)的Cn+m個(gè)Dn+m個(gè)連續(xù)的解答：D簡(jiǎn)述線(xiàn)性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)的比較對(duì)于順序存儲(chǔ)的線(xiàn)性表，設(shè)其長(zhǎng)度為n，在任何位置上插入或刪除都是等概率的。插入一個(gè)元素時(shí)大約要移動(dòng)表中（）元素。An/2B(n+1)/2C(n-1)/2Dn解答A設(shè)順序表的長(zhǎng)度為n，并設(shè)從表中刪除元素的概率相等。則在平均情況下，從表中刪除一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)是（）A(n-1)/2Bn/2Cn(n-1)/2Dn(n+1)/2解答A在n個(gè)結(jié)點(diǎn)的線(xiàn)性表的數(shù)組實(shí)現(xiàn)中，算法的時(shí)間復(fù)雜性是O(1)的操作是：A訪(fǎng)問(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以上都不對(duì)解答：A順序存儲(chǔ)的線(xiàn)性表A，其數(shù)據(jù)元素為整型，編寫(xiě)算法，將A拆成B和C兩個(gè)表，使A中元素值大于等于0的存入B，小于0存入C。要求：（1）表B和C另外設(shè)置存儲(chǔ)空間。（2）B和C不另外設(shè)置，而利用A的空間?？键c(diǎn)3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以下關(guān)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的敘述，（）是不正確的。A結(jié)點(diǎn)除自身信息外還包括指針域，因此存儲(chǔ)密度小于順序結(jié)構(gòu)B邏輯上相鄰的結(jié)點(diǎn)物理上不必相鄰C可以通過(guò)計(jì)算直接確定i個(gè)結(jié)點(diǎn)的存儲(chǔ)位置D插入刪除操作方便，不必移動(dòng)結(jié)點(diǎn)解答：C鏈表不具備的特點(diǎn)是（）A可隨機(jī)訪(fǎng)問(wèn)任一個(gè)元素B插入和刪除時(shí)不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與線(xiàn)性表長(zhǎng)度成正比分析：A是順序表的特點(diǎn)，鏈表的元素不可以直接隨機(jī)訪(fǎng)問(wèn)，一般是從鏈表的起始位置依次搜索得到答案：A線(xiàn)性表可用順序表或者鏈表存儲(chǔ)，它們有什么優(yōu)缺點(diǎn)？如果有n個(gè)表同時(shí)并存，并且在處理過(guò)程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，表得到總數(shù)也可能自動(dòng)改變，在這種情況下應(yīng)該選用哪種存儲(chǔ)表示分析：考點(diǎn)4單鏈表及其基本操作對(duì)鏈表設(shè)置表頭結(jié)點(diǎn)的作用是什么解答：一般來(lái)說(shuō)，設(shè)置表頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)，而且，頭結(jié)點(diǎn)也可以用來(lái)存儲(chǔ)一些鏈表的基本信息，如鏈表長(zhǎng)度等。對(duì)給定的n個(gè)元素，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是：分析：在不申請(qǐng)額外存儲(chǔ)空間的前提下，建立一個(gè)n元素的有序單鏈表是時(shí)間復(fù)雜度是O(n*n)，因?yàn)閷?duì)任意一個(gè)元素，插入單鏈表中合適位置的開(kāi)銷(xiāo)是O(n)，對(duì)n個(gè)元素則是O(n*n)將長(zhǎng)度為n的單鏈表接在長(zhǎng)度為m的單鏈表之后的算法的時(shí)間復(fù)雜度是：分析：由于將長(zhǎng)度為n的單鏈表連接在長(zhǎng)度為m的單鏈表之后的操作，需要把長(zhǎng)度為m的單鏈表遍歷一遍，找到最后一個(gè)結(jié)點(diǎn)，所以時(shí)間復(fù)雜度我O(m)設(shè)計(jì)一個(gè)算法intincrease(LinkList*L)，判定帶頭結(jié)點(diǎn)單鏈表L是否是遞增的，若是返回1，否則返回0.有一個(gè)無(wú)頭結(jié)點(diǎn)的單鏈表，結(jié)點(diǎn)有數(shù)據(jù)域data，指針域next，表頭指針為h，通過(guò)遍歷鏈表，將鏈表中所有的鏈表方向逆轉(zhuǎn)。要求逆轉(zhuǎn)后的鏈表的表頭指針h指向原鏈表的最后一個(gè)結(jié)點(diǎn)。算法如下請(qǐng)?zhí)羁?。關(guān)鍵考點(diǎn)點(diǎn)評(píng)：在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行：答案：A在單向鏈表中p結(jié)點(diǎn)的后面插入新結(jié)點(diǎn)s，應(yīng)執(zhí)行語(yǔ)句：答案：s->next=p->next;p->next=s已知線(xiàn)性表中的元素以值遞增有序排列，并以單鏈表作為存儲(chǔ)結(jié)構(gòu)。編寫(xiě)算法，刪除表中所有值相同的元素，同時(shí)釋放被刪除的結(jié)點(diǎn)空間。設(shè)有序表以帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)。請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，實(shí)現(xiàn)在該表內(nèi)插入一個(gè)新元素的操作。要求插入后，仍為有序表。假定每個(gè)結(jié)點(diǎn)有兩個(gè)域，element和link，元素為整型，link具有指向后繼結(jié)點(diǎn)的指針類(lèi)型，要求使用類(lèi)型說(shuō)明定義單鏈表結(jié)構(gòu)，并實(shí)現(xiàn)函數(shù)。編寫(xiě)逆向輸出的不帶頭結(jié)點(diǎn)的單向鏈表中數(shù)據(jù)域的遞歸算法。設(shè)表中有四個(gè)結(jié)點(diǎn)，從表頭至表尾其數(shù)據(jù)域分別為10,30,20,40作圖表示出該算法的執(zhí)行過(guò)程。設(shè)該鏈表的結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型名稱(chēng)為list，結(jié)點(diǎn)的數(shù)據(jù)域和指針域的名稱(chēng)分別是data和next，不必寫(xiě)出list的定義考點(diǎn)5循環(huán)鏈表及其基本操作某線(xiàn)性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間A非循環(huán)的單鏈表B僅有頭指針的單循環(huán)鏈表C非循環(huán)的雙鏈表D僅有尾指針的單循環(huán)鏈表答案：D有一個(gè)含頭結(jié)點(diǎn)的單循環(huán)鏈表，頭指針為head，則判斷其是否為空的條件是：答案：head->next==head設(shè)線(xiàn)性表非空，采用下列（）所描述的鏈表可以在O（1）時(shí)間內(nèi)在表尾插入一個(gè)新結(jié)點(diǎn)。A帶表頭結(jié)點(diǎn)的單鏈表，一個(gè)鏈表指針指向表頭結(jié)點(diǎn)B帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個(gè)鏈表指針指向表頭結(jié)點(diǎn)C不帶表頭結(jié)點(diǎn)的單鏈表，一個(gè)鏈表指針指向表的第一個(gè)結(jié)點(diǎn)D不帶表頭結(jié)點(diǎn)的單循環(huán)鏈表，一個(gè)鏈表指針指向表的第一個(gè)結(jié)點(diǎn)分析：這里用O（1）時(shí)間插入的方法是，在表頭結(jié)點(diǎn)后面插入一個(gè)新表頭，然后把原來(lái)表頭改成新的結(jié)點(diǎn)。解答：B考點(diǎn)6雙鏈表及其基本操作N表示線(xiàn)性表中當(dāng)前元素的數(shù)目，p表示指針的存儲(chǔ)單元大小，E表示數(shù)據(jù)元素的存儲(chǔ)單元大小，D表示可以在數(shù)組中存儲(chǔ)的線(xiàn)性表元素的最大數(shù)目，那么使用順序表所需空間大小為（），使用雙向鏈表（不考慮頭結(jié)點(diǎn)）所需空間的大小為（）分析：考察線(xiàn)性表存儲(chǔ)空間的計(jì)算。解答：ED，（2P+E）n解答：B指針p指向雙向鏈表的某個(gè)結(jié)點(diǎn)，在指針p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)。結(jié)點(diǎn)結(jié)構(gòu)：prior-data-next，操作序列是：分析：鏈表中插入結(jié)點(diǎn)的順序是一般先處理被插入者解答：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;考點(diǎn)7單鏈表的應(yīng)用考點(diǎn)8單循環(huán)鏈表的應(yīng)用設(shè)計(jì)一個(gè)將單循環(huán)鏈表逆置的算法函數(shù)考點(diǎn)9其他鏈表及特殊算法判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表s是否對(duì)稱(chēng)相等的算法如下所示，請(qǐng)?zhí)羁?。棧和?duì)列考點(diǎn)1棧和隊(duì)列的基本概念判斷：線(xiàn)性表、棧和隊(duì)列的邏輯結(jié)構(gòu)完全相同解答：正確判斷：棧和隊(duì)列都是線(xiàn)性表，只是在插入和刪除時(shí)受到一些限制。分析：棧和隊(duì)列是兩種特殊的線(xiàn)性表，他們的邏輯結(jié)構(gòu)與線(xiàn)性表相同只是其運(yùn)算規(guī)則較線(xiàn)性表有更多的限制，故又稱(chēng)他們?yōu)檫\(yùn)算受限的線(xiàn)性表解答：正確判斷：在鏈隊(duì)列中，除了隊(duì)頭指針外，還必須設(shè)隊(duì)尾指針，否則無(wú)法進(jìn)行隊(duì)列的插入操作。解答：正確關(guān)鍵考點(diǎn)點(diǎn)評(píng)：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。注意：增加指向鏈表上的最后一個(gè)結(jié)點(diǎn)的尾指針，便于在表尾作插入操作。循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判斷它的空和滿(mǎn)。以下的敘述中，正確的是：A線(xiàn)性表的線(xiàn)性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B二維數(shù)組是其數(shù)據(jù)元素為線(xiàn)性表的線(xiàn)性表C棧的操作方式是先進(jìn)先出D隊(duì)列的操作方式是先進(jìn)后出解答：B執(zhí)行（）操作時(shí)，需要使用隊(duì)列作為輔助存儲(chǔ)空間A查找哈希表B廣度優(yōu)先搜索圖C先序遍歷二叉樹(shù)D深度優(yōu)先搜索圖分析：考察上述幾種操作在額外空間上的需求。查找哈希表和先序遍歷二叉樹(shù)不需要比較額外的空間；而深度優(yōu)先搜索圖則可以利用遞歸的方法，使用堆棧，而不使用隊(duì)列作為輔助存儲(chǔ)空間；只有廣度優(yōu)先搜索圖需要用到隊(duì)列作為輔助存儲(chǔ)空間。解答：B考點(diǎn)2入棧出棧分析元素abcde依次進(jìn)入初始為空的棧中，若元素進(jìn)棧后可停留，可出棧，直到所有元素都出棧，則在所有可能的出棧序列中，以元素d開(kāi)頭的序列個(gè)數(shù)是：A3B4C5D6分析：該題考查堆棧的進(jìn)出問(wèn)題，出棧順序必為d-c-b-a-，e的順序不定，在任意一個(gè)“-”上都有可能。故可能以d開(kāi)頭的序列個(gè)數(shù)是4解答：B當(dāng)入隊(duì)序列為1、2、3時(shí)，出隊(duì)序列可以是什么？當(dāng)入棧序列為1、2、3時(shí)，出棧序列可以是什么？解答：出隊(duì)序列為123，出棧序列可以是123,132,231,213,321考點(diǎn)3棧的基本操作利用棧求表達(dá)式的值時(shí)，設(shè)立操作數(shù)棧OPND，設(shè)OPND只有兩個(gè)存儲(chǔ)單元，在下列表達(dá)式中，不發(fā)生上溢的是：A．a(chǎn)-b*(c-d)B.(a-b)*c-dC.(a-b*c)-dD.(a-b)*(c-d)分析：只有B的運(yùn)算順序是依次向右，不需要暫存其他的操作數(shù)來(lái)配合運(yùn)算優(yōu)先順序解答：B2.向一個(gè)棧頂指針為top的鏈棧中插入一個(gè)s結(jié)點(diǎn)，則執(zhí)行：A．top->next=sBs->next=top->next;top->next=sC.s->next=top;top=sD.s->next=top;top=top->next解答：C關(guān)鍵考點(diǎn)點(diǎn)評(píng)：3.用不帶頭結(jié)點(diǎn)的鏈表表示隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)A僅修改頭指針B僅修改尾指針C頭尾指針都要修改D頭尾指針可能都要修改解答：A4．當(dāng)兩個(gè)棧共享一個(gè)空間時(shí)，棧用一維數(shù)組stack（0，n-1）表示，梁棧頂指針?lè)謩e為top[1]和top[2],則棧滿(mǎn)時(shí)的條件為：分析：兩個(gè)棧共享一個(gè)空間時(shí)，由于棧底是固定的且有兩個(gè)，所以棧底一定是該空間的兩個(gè)邊，然后數(shù)據(jù)存放在中間，所以棧滿(mǎn)的時(shí)候就是兩個(gè)棧頂挨著的時(shí)候。解答：top[1]=top[2]+1考點(diǎn)4棧在遞歸中的應(yīng)用一個(gè)遞歸的定義可以用遞歸過(guò)程求解，也可以用非遞歸過(guò)程求解，但是單從運(yùn)行時(shí)間上來(lái)看，通常遞歸過(guò)程要比非遞歸過(guò)程：A較快B較慢C相同D無(wú)法比較分析：遞歸過(guò)程中通常會(huì)引入一些元素的反復(fù)計(jì)算，而且有堆棧壓縮開(kāi)銷(xiāo)，所以通常來(lái)說(shuō)，遞歸過(guò)程要滿(mǎn)解答：B在遞歸程序調(diào)用過(guò)程中，遞歸工作棧包含了哪些數(shù)據(jù)？考點(diǎn)5棧的應(yīng)用將中綴表達(dá)式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價(jià)的后綴表達(dá)式ab+acd+e/f-*-g+時(shí)，用棧來(lái)存放暫時(shí)還不能確定運(yùn)算次序的操作符，若棧初試為空，則轉(zhuǎn)換過(guò)程中同時(shí)保存在棧中的操作符的最大個(gè)數(shù)是：分析：解答：5在將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式和計(jì)算后綴表達(dá)式的算法中，都需要使用堆棧。對(duì)于前者，進(jìn)入堆棧的元素為表達(dá)式中的：___，而對(duì)于后者，進(jìn)入堆棧的元素為:___。中綴表達(dá)式(a+b)/c-(f-d/e)所對(duì)應(yīng)的后綴表達(dá)式是：___。解答：二元運(yùn)算符，操作數(shù)，ab+c/fde/--已知num為無(wú)符號(hào)十進(jìn)制整數(shù)，請(qǐng)寫(xiě)一非遞歸算法，該算法依次輸出num對(duì)應(yīng)的r進(jìn)制的各位數(shù)字。要求算法中用到的堆棧采用線(xiàn)性鏈表存儲(chǔ)結(jié)構(gòu)（1<r<10）?？键c(diǎn)6隊(duì)列的實(shí)現(xiàn)與應(yīng)用設(shè)棧s和隊(duì)列q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧s。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列q，且7個(gè)元素的出隊(duì)序列是bdcfeag，則棧s的容量至少為：A1B2C3D4分析：考查棧的最大遞歸深度。棧是先進(jìn)后出解答：C在一個(gè)鏈隊(duì)列里，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的運(yùn)算是：Af->next=s;f=s;Br->next=s;r=s;Cs->next=r;r=s;Ds->next=f;f=s;分析：考查隊(duì)列的入隊(duì)操作，即在隊(duì)尾追加一個(gè)元素。解答：B關(guān)鍵考點(diǎn)點(diǎn)評(píng)：若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3.當(dāng)從隊(duì)列中刪除一個(gè)元素，再加上兩個(gè)元素后，rear和front的值為：A1和5B2和4C4和2D5和1分析：出隊(duì)一個(gè)元素時(shí)處理front執(zhí)行的操作是front=(front+1)%queuesize,入隊(duì)一個(gè)元素時(shí)處理rear執(zhí)行的操作是rear=(rear+1)%queuesize解答：B單循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則進(jìn)隊(duì)時(shí)間復(fù)雜度為：AO(n)BO(1)CO(n*n)DO(nlogn)分析：考查鏈表表示隊(duì)列的基本知識(shí)。隊(duì)列的入隊(duì)操作是把新增的結(jié)點(diǎn)插入當(dāng)前隊(duì)列的隊(duì)尾處因?yàn)樵撽?duì)列只設(shè)置了隊(duì)頭指針，沒(méi)有尾指針，因此必須要從頭指針處一步一步遍歷到隊(duì)尾，讓隊(duì)列的尾指針指向新增結(jié)點(diǎn)，從而完成入隊(duì)操作。因此遍歷的過(guò)程可以很容易的得到是n次。解答：A樹(shù)和二叉樹(shù)考點(diǎn)1樹(shù)的概念在一棵度為4的樹(shù)T中，若有20個(gè)度為4的結(jié)點(diǎn)，10個(gè)度為3的結(jié)點(diǎn)，1個(gè)度為2的結(jié)點(diǎn)，10個(gè)度為1的結(jié)點(diǎn)，則樹(shù)T的葉結(jié)點(diǎn)個(gè)數(shù)是：A41B82C113D122分析：考查樹(shù)結(jié)點(diǎn)的特性。設(shè)樹(shù)中度為i的結(jié)點(diǎn)數(shù)分別為Ni，樹(shù)中結(jié)點(diǎn)總數(shù)是N，則樹(shù)中各結(jié)點(diǎn)的度之和等于N-1（設(shè)邊數(shù)為B，N個(gè)結(jié)點(diǎn)的樹(shù)，除了根結(jié)點(diǎn)，每一個(gè)結(jié)點(diǎn)都有一個(gè)邊進(jìn)入，則B=N-1；然而邊又是由每個(gè)結(jié)點(diǎn)分出去的，則B=0*N0+1*N1+2*N2（這個(gè)算的其實(shí)就是度之和）……..）所以N=1+0*N0+1*N1+2*N2+3*N3+4*N4=N0+N1+N2+N3+N4.根據(jù)題中數(shù)據(jù)，就可以得到N0=82，就是葉子結(jié)點(diǎn)個(gè)數(shù)。解答：B一棵t叉樹(shù)中要么是葉子結(jié)點(diǎn)，要么是有t個(gè)分支的非葉子結(jié)點(diǎn)。設(shè)該t叉樹(shù)葉子結(jié)點(diǎn)個(gè)數(shù)為s，非葉子結(jié)點(diǎn)個(gè)數(shù)為n，寫(xiě)出n和s的關(guān)系式。分析：t叉樹(shù)有n個(gè)非葉子結(jié)點(diǎn)，即分支數(shù)為n*t（一個(gè)分支出去就是一個(gè)結(jié)點(diǎn)），總的結(jié)點(diǎn)數(shù)為n*t+1，總的結(jié)點(diǎn)數(shù)就是葉子結(jié)點(diǎn)和非葉子結(jié)點(diǎn)之和，為s+n,故n*t+1=s+n,即s=(t-1)n+1解答：s=(t-1)n+1考點(diǎn)2二叉樹(shù)若一棵完全二叉樹(shù)有768個(gè)結(jié)點(diǎn)，則該二叉樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)是：A257B258C384D385分析：該題考查二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，葉節(jié)點(diǎn)數(shù)為n，則度為2的結(jié)點(diǎn)數(shù)為n-1，度為1的結(jié)點(diǎn)數(shù)為0或1，本題中為1（總結(jié)點(diǎn)數(shù)為偶數(shù)），即2n=768解答：C已知一棵完全二叉樹(shù)的第六層（設(shè)根為第一層）有8個(gè)葉結(jié)點(diǎn)，則完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多是：A39B52C111D119分析：該題考查二叉樹(shù)特點(diǎn)。完全二叉樹(shù)比起滿(mǎn)二叉樹(shù)只是在最下面一層的右邊缺少了部分葉節(jié)點(diǎn)，而最后一層之上是滿(mǎn)二叉樹(shù)，并且只有最后兩層上有葉節(jié)點(diǎn)。第六層有葉節(jié)點(diǎn)，則完全二叉樹(shù)高度可能為6或7，顯然樹(shù)高為7時(shí)結(jié)點(diǎn)更多。若第6層有8個(gè)葉節(jié)點(diǎn)，則前6層為滿(mǎn)二叉樹(shù)，而第7層缺失了8*2=16個(gè)葉節(jié)點(diǎn)，故完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多為2^7-1-16=111。（滿(mǎn)二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是2^h-1）解答：C下列二叉排序樹(shù)中，滿(mǎn)足平衡二叉樹(shù)定義的是：分析：平衡二叉樹(shù)的左右子數(shù)高度之差不超過(guò)1解答：B若一棵二叉樹(shù)有1001個(gè)結(jié)點(diǎn)，且無(wú)度為1的結(jié)點(diǎn)，則葉節(jié)點(diǎn)個(gè)數(shù)為：A498B499C500D501分析：設(shè)葉節(jié)點(diǎn)個(gè)數(shù)為x，則有（1001-x）*2+1=1001解答：D在完全二叉樹(shù)中，含有n個(gè)葉子節(jié)點(diǎn)，當(dāng)1度結(jié)點(diǎn)數(shù)為1時(shí)，該樹(shù)的高度為：（），當(dāng)1度結(jié)點(diǎn)數(shù)為0時(shí)該樹(shù)高度為：（）設(shè)二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)為left—data—bf—right，定義二叉樹(shù)結(jié)點(diǎn)的平衡因子bf(T)=hl-hr,寫(xiě)一遞歸算法；確定二叉樹(shù)tree中非葉子結(jié)點(diǎn)的個(gè)數(shù)。當(dāng)一棵有n(n<100)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按順序存儲(chǔ)方式存儲(chǔ)在bt[1….n],試寫(xiě)一算法，求出二叉樹(shù)中結(jié)點(diǎn)值分別為x和y的兩個(gè)結(jié)點(diǎn)的最近的公共祖先的結(jié)點(diǎn)的值。二叉樹(shù)的順序存儲(chǔ)表示為：TypedefcharSqBiTree[101];SqBiTreebt;考點(diǎn)3二叉樹(shù)的遍歷某二叉樹(shù)的先序序列和中序序列正好相反，則該二叉樹(shù)一定具有（）的特征。A二叉樹(shù)為空或只有一個(gè)結(jié)點(diǎn)B若二叉樹(shù)不為空，則任一結(jié)點(diǎn)不能同時(shí)擁有左兒子和右兒子C若二叉樹(shù)不為空，則任一結(jié)點(diǎn)沒(méi)有左兒子D若二叉樹(shù)不為空，則任一結(jié)點(diǎn)沒(méi)有右兒子分析：考查二叉樹(shù)的遍歷，先序遍歷為：根，左，右；中序遍歷為：左，根，右。解答：D任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在先序中序和后序遍歷中的相對(duì)次序：A不改變B改變C不能確定D以上都不對(duì)分析：無(wú)論是哪種遍歷，都是按照先左后右的順序進(jìn)行訪(fǎng)問(wèn)，所以葉子結(jié)點(diǎn)遍歷過(guò)程的相對(duì)順序是固定的解答：A判斷：如果某二叉樹(shù)的先序遍歷和中序遍歷序列相同，則該二叉樹(shù)中除了葉子結(jié)點(diǎn)外的所有結(jié)點(diǎn)都沒(méi)有左子樹(shù)解答：正確一棵非空的二叉樹(shù)先序和后序序列正好相反，則該二叉樹(shù)一定滿(mǎn)足：A其中任意一個(gè)結(jié)點(diǎn)均無(wú)左孩子B其中任意一個(gè)結(jié)點(diǎn)均無(wú)右孩子C其中只有一個(gè)葉子結(jié)點(diǎn)D其中度為2的結(jié)點(diǎn)最多只有一個(gè)分析：先序是按照根左右順序，后序是按照左右根順序。所以如果某個(gè)結(jié)點(diǎn)同時(shí)有左右兩個(gè)結(jié)點(diǎn)，關(guān)于這個(gè)節(jié)點(diǎn)的遍歷就不能保證先序和后序正好相反，所以每個(gè)結(jié)點(diǎn)只有一個(gè)子樹(shù)，所以就是只有一個(gè)葉子結(jié)點(diǎn)的情況。解答：C某二叉樹(shù)的先序和后序序列正好相反，則該二叉樹(shù)一定是（）的二叉樹(shù)。A空或只有一個(gè)結(jié)點(diǎn)B任一結(jié)點(diǎn)只有左孩子C高度等于其結(jié)點(diǎn)數(shù)D任一結(jié)點(diǎn)只有右孩子分析：后序和先序序列相反說(shuō)明每個(gè)結(jié)點(diǎn)只有一個(gè)孩子解答：C有一鏈?zhǔn)蕉鏄?shù)btree，結(jié)點(diǎn)結(jié)構(gòu)為（lchild,data,rchild）。分別設(shè)計(jì)如下算法。A用高級(jí)語(yǔ)言描述鏈?zhǔn)蕉鏄?shù)的存儲(chǔ)結(jié)構(gòu)；B計(jì)算二叉樹(shù)中度為0的結(jié)點(diǎn)數(shù)目；C計(jì)算二叉樹(shù)的深度；D后序遍歷二叉樹(shù)。解答：寫(xiě)出二叉樹(shù)中序遍歷的非遞歸算法?？键c(diǎn)4樹(shù)與森林已知一棵2011個(gè)結(jié)點(diǎn)的樹(shù)其葉子結(jié)點(diǎn)個(gè)數(shù)為116，該樹(shù)對(duì)應(yīng)的二叉樹(shù)中無(wú)右孩子的非葉子結(jié)點(diǎn)個(gè)數(shù)是：A115B116C1895D1896分析：本題可采用特殊情況解法。設(shè)題意中的樹(shù)如圖所示，則對(duì)應(yīng)的二叉樹(shù)中僅有前115個(gè)葉子結(jié)點(diǎn)有右孩子，即有1896個(gè)結(jié)點(diǎn)無(wú)右孩子，即有1895個(gè)非葉子結(jié)點(diǎn)無(wú)右孩子。解答：C設(shè)F是由T1T2T3三棵樹(shù)組成的森林，與F對(duì)應(yīng)的二叉樹(shù)B。若T1T2T3的結(jié)點(diǎn)數(shù)分別是n1n2n3，則二叉樹(shù)B的左子樹(shù)中有（）個(gè)結(jié)點(diǎn)，B的右子樹(shù)有（）個(gè)結(jié)點(diǎn)。分析：樹(shù)和森林的自己的兒子結(jié)點(diǎn)就是二叉樹(shù)中的左子樹(shù)中的結(jié)點(diǎn)，兄弟結(jié)點(diǎn)或者兄弟樹(shù)都是自己的右子樹(shù)的結(jié)點(diǎn)。解答：n1-1;n2+n3一棵二叉樹(shù)的中序遍歷序列為BCDAFEHJIG,后序遍歷序列為DCBFJIHGEA，要求：a畫(huà)出此二叉樹(shù)b將二叉樹(shù)轉(zhuǎn)換為樹(shù)或森林考點(diǎn)5哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)是葉子結(jié)點(diǎn)____最短的二叉樹(shù)解答：帶權(quán)路徑長(zhǎng)度對(duì)下面給出的數(shù)據(jù)序列，構(gòu)造一棵哈夫曼樹(shù)，并求出其帶權(quán)路徑長(zhǎng)度。（18,15,7,6,12,23,10,5,4）已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符：ABCDEFGH，其出現(xiàn)頻率分別為5,29,7,8,14,23,3和11.試構(gòu)造一棵哈夫曼樹(shù)寫(xiě)出計(jì)算其WPL的算式和計(jì)算結(jié)果寫(xiě)出其中每一個(gè)字符的哈夫曼編碼第五章圖考點(diǎn)1圖的基本概念和相關(guān)術(shù)語(yǔ)若無(wú)向圖G=（V，E）中含有7個(gè)頂點(diǎn)，則保證圖G在任何情況下都是連同的，需要的邊數(shù)最少是：A6B15C16D21分析：首先明確一下，完全圖是圖有最多的邊數(shù)，無(wú)向圖的完全圖邊數(shù)為n*(n-1)/2，（完全圖一定是連通圖，但是連通圖不一定是完全圖）要保證無(wú)向圖G在任何情況下都是連通的，即任意變動(dòng)圖G中的邊，G始終保持連通，首先需要G的任意6個(gè)頂點(diǎn)構(gòu)成完全連通子圖G1，需要6*5/2=15條邊，然后再增添一條邊將第七個(gè)結(jié)點(diǎn)與G1連接，共需16條邊。21條是最多的情況，是構(gòu)成了完全圖。解答：C下列關(guān)于無(wú)向連通圖特性的敘述中，正確的是：所有頂點(diǎn)的度之和為偶數(shù)邊數(shù)大于頂點(diǎn)個(gè)數(shù)減1至少有一個(gè)頂點(diǎn)的度為1A只有（1）B只有（2）C（1）和（2）D（1）和（3）分析：該題考查無(wú)向連通圖的特性，每條邊都連接了兩個(gè)結(jié)點(diǎn)，則在計(jì)算頂點(diǎn)的度時(shí)，這條邊被計(jì)算了兩次，故所有頂點(diǎn)度之和為邊數(shù)的兩倍，顯然必為偶數(shù)。（2）和（3）不一定正確。例如，對(duì)頂點(diǎn)數(shù)N>=1的無(wú)向完全圖，不存在一個(gè)頂點(diǎn)的度為1，并且邊數(shù)與頂點(diǎn)數(shù)的差要大于1.解答：A以下關(guān)于圖的敘述中，正確的是：A強(qiáng)連通有向圖的任何頂點(diǎn)到其他所有頂點(diǎn)都有弧B任意圖頂點(diǎn)的入度等于出度C有向完全圖一定是強(qiáng)連通有向圖D有向圖的邊集的子集和頂點(diǎn)集的子集可構(gòu)成原有向圖的子圖分析：首先明確強(qiáng)連通圖的概念：有向圖中任意兩個(gè)頂點(diǎn)u，v之間，存在u到v路徑，也存在v到u的路徑（注意不是?。?。完全圖：邊最多的圖。完全有向圖：n(n-1)條邊。強(qiáng)連通圖不一定任何兩個(gè)頂點(diǎn)之間都有弧。邊的子集中某條邊的兩個(gè)頂點(diǎn)如果不在頂點(diǎn)集的子集中，則不可以構(gòu)成圖解答：C判斷：強(qiáng)連通分量是無(wú)向圖的極大強(qiáng)連通子圖。分析：有向圖解答：錯(cuò)誤關(guān)鍵考點(diǎn)點(diǎn)評(píng)在無(wú)向圖中定義頂點(diǎn)Vi與Vj之間的路徑為從Vi到Vj的一個(gè)：Ａ頂點(diǎn)序列Ｂ邊序列Ｃ權(quán)值總和Ｄ邊的條數(shù)分析：路徑是一個(gè)頂點(diǎn)的序列解答：Ａ考點(diǎn)2圖的存儲(chǔ)方式對(duì)于存儲(chǔ)為鄰接矩陣的有向圖，其邊數(shù)等于鄰接矩陣的：____解答：非零元素個(gè)數(shù)在含有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，非零元素的個(gè)數(shù)是：AeB2eCn*n-eDn*n-2e分析：矩陣本身共有n*n個(gè)元素，而每條邊在矩陣中被記錄2次，非零元素個(gè)數(shù)為2e解答：DN個(gè)頂點(diǎn)的無(wú)向連通圖用用鄰接矩陣表示時(shí)，該矩陣至少有___個(gè)非零元素。分析：n個(gè)頂點(diǎn)的連通圖至少有n-1條邊。解答：2*(n-1)已知一個(gè)圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是____解答：將矩陣的第i行全部賦值為0.下面關(guān)于圖的存儲(chǔ)的敘述中，正確的是：A鄰接矩陣法，占用的存儲(chǔ)空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)B鄰接矩陣法，占用的存儲(chǔ)空間大小只與邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無(wú)關(guān)C鄰接表法，占用的存儲(chǔ)空間大小只與頂點(diǎn)數(shù)有關(guān)，與邊數(shù)無(wú)關(guān)D鄰接表法，占用的存儲(chǔ)空間大小只與邊數(shù)有關(guān)，與頂點(diǎn)數(shù)無(wú)關(guān)分析：鄰接矩陣法，矩陣大小為n*n，n為頂點(diǎn)數(shù)，所以占用的存儲(chǔ)空間只與頂點(diǎn)數(shù)有關(guān)。鄰接表法，有邊表和頂點(diǎn)表，所以占用的存儲(chǔ)空間大小與頂點(diǎn)數(shù)和邊數(shù)都有關(guān)。解答：A對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖，若采用鄰接表表示，則表向量（頂點(diǎn)表）的大小為:___，所有關(guān)于頂點(diǎn)的鄰接表（邊表）的結(jié)點(diǎn)總數(shù)是：____.解答：n；2e考點(diǎn)3圖的深度優(yōu)先遍歷對(duì)稀疏圖進(jìn)行DFS遍歷時(shí)，應(yīng)該采用_____作為其存儲(chǔ)結(jié)構(gòu)。分析：若一個(gè)有n個(gè)結(jié)點(diǎn)和e條邊的圖采用鄰接表作為其存儲(chǔ)結(jié)構(gòu)，其深度優(yōu)先遍歷的時(shí)間復(fù)雜度是O(n+e),采用鄰接矩陣表示，時(shí)間復(fù)雜度是O(n*n)。稀疏圖連邊少，所以采用鄰接表，時(shí)間復(fù)雜度低。解答：鄰接表已知一個(gè)有向圖如圖所示，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷，不可能得到的DFS序列是：___AadbefcBadcefbCadcbfeDadefcb分析：A中，在遍歷到結(jié)點(diǎn)b時(shí)，沒(méi)有服從深度優(yōu)先就繼續(xù)遍歷c或者f，轉(zhuǎn)而回溯到d進(jìn)行廣度遍歷，違背了DFS算法的原則。解答：A考點(diǎn)4圖的廣度優(yōu)先遍歷對(duì)有n個(gè)結(jié)點(diǎn)，e條邊且使用鄰接表存儲(chǔ)的有向圖進(jìn)行廣度優(yōu)先遍歷，則其算法時(shí)間復(fù)雜度是：___AO(n)BO(e)C(n+e)D(n*e)分析：每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過(guò)程實(shí)際上是通過(guò)邊或弧找鄰接點(diǎn)的過(guò)程，而結(jié)點(diǎn)共n個(gè)，邊共n條，全部把這些邊和點(diǎn)遍歷一遍解答：C采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的___解答：層次遍歷用鄰接表表示的圖進(jìn)行廣度優(yōu)先遍歷時(shí)通常采用___結(jié)構(gòu)實(shí)現(xiàn)算法。Ａ棧Ｂ隊(duì)列Ｃ二叉樹(shù)Ｄ圖解答：Ｂ針對(duì)圖示給出的無(wú)向連通圖，求解一下問(wèn)題：畫(huà)出該圖的鄰接矩陣基于該鄰接矩陣，給出以頂點(diǎn)1為起點(diǎn)的廣度優(yōu)先遍歷序列和廣度優(yōu)先生成樹(shù)畫(huà)出一棵最小代價(jià)生成樹(shù)。分析和解答：考點(diǎn)5最小生成樹(shù)判斷：無(wú)向圖中任何一個(gè)邊數(shù)最少且連通所有頂點(diǎn)的子圖都是該無(wú)向圖的生成樹(shù)分析：生成樹(shù)的定義為：如果連通圖G的一個(gè)子圖是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖稱(chēng)為G的生成樹(shù)。解答：正確關(guān)鍵考點(diǎn)點(diǎn)評(píng)：最小生成樹(shù)的定義：對(duì)于連通的帶權(quán)圖G，其生成樹(shù)也是帶權(quán)的。生成樹(shù)T各邊的權(quán)值總和成為該樹(shù)的權(quán)。權(quán)最小的生成樹(shù)稱(chēng)為G的最小生成樹(shù)。對(duì)于無(wú)向圖生成樹(shù)，下列說(shuō)法不正確的是：A生成樹(shù)是遍歷的產(chǎn)物B從同一地點(diǎn)出發(fā)所得的生成樹(shù)不同C生成樹(shù)是圖的極小連通子圖D不同遍歷方法所得的生成樹(shù)不同分析：從同一地點(diǎn)出發(fā)但是遍歷算法不同，所得生成樹(shù)也不同解答：B寫(xiě)出圖的鄰接矩陣并用普里姆算法從A出發(fā)求其最小生成樹(shù)。分析和解答：求出帶權(quán)圖G的最小生成樹(shù)。分析和解答：考點(diǎn)6單源最短路徑用迪杰斯特拉算法，求解圖中從V1到其余各頂點(diǎn)的最短路徑，寫(xiě)出算法求解過(guò)程的每一步。分析：先將V1進(jìn)入集合S（s是已經(jīng)求得最短路徑的點(diǎn)集合），然后依次尋找從S中點(diǎn)到V-S中點(diǎn)的當(dāng)前最短路徑，然后從這些當(dāng)前最短路徑中尋找最小的，將點(diǎn)進(jìn)入S，依次下去。解答：考點(diǎn)7拓?fù)渑判驅(qū)D進(jìn)行拓?fù)渑判?，可以得到不同的拓?fù)湫蛄械膫€(gè)數(shù)是：___A4B3C2D1分析：從第一個(gè)入度為0的點(diǎn)開(kāi)始，去掉它并且去掉它的連邊，然后再去掉新產(chǎn)生的入度為0的點(diǎn)。依次下去。分別有：abced，abecd，aebcd解答：B在拓?fù)渑判蛑?，拓?fù)湫蛄械淖詈笠粋€(gè)點(diǎn)必定是____的頂點(diǎn)解答：沒(méi)有后繼（出度為0）判斷：如果有向圖G=（V，E）的拓