數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)答案一、選擇填空下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)？()線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。JB)線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元。線性表采用鏈接存儲(chǔ)，便于插入和刪除操作。若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用()存儲(chǔ)方式最節(jié)省時(shí)間。JA)順序表 8)雙鏈表C)帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D)單循環(huán)鏈表鏈表不具有的特點(diǎn)是()。人)插入、刪除不需要移動(dòng)元素 JB)可隨機(jī)訪問任一元素C)不必事先估計(jì)存儲(chǔ)空間 D)所需空間與線性長度成正比若長度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為()(1<=i<=n+1)。A)O(0)B)O(1)VC)O(n) D)O(n2)線性表(a1,a2,...,an)以鏈接方式存儲(chǔ)時(shí)，訪問第i位置元素的時(shí)間復(fù)雜度為()。A)O(i)B)O(1) VC)O(n)D)O(i-1)對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是()A)head==NULLB)head—next==NULL VC)head—next==headD)head!=NULL在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：()。A)p->next=s;s->next=p->next;VB)s->next=p->next;p->next=s;C)p->next=s;p->next=s->next;D)p->next=s->next;p->next=s;設(shè)指針變量p指向單鏈表結(jié)點(diǎn)A，則刪除結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B需要的操作為()。VA)p->next=p->next->next B)p=p->nextC)p=p->next->next D)p->next=p()又稱為FIFO表；()又稱為FILO表。VA)隊(duì)列B)散列表VC)棧 D)哈希表對(duì)于棧操作數(shù)據(jù)的原則是()。先進(jìn)先出VB)后進(jìn)先出 C)后進(jìn)后出 D)不分順序用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除操作時(shí)( )。VA)僅修改隊(duì)頭指針 B)僅修改隊(duì)尾指針C)隊(duì)頭、隊(duì)尾指針都要修改 D)隊(duì)頭、隊(duì)尾指針都可能要修改假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，其頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為()。VA)(rear-front+m)%mB)rear-front+1 C)(front-rear+m)%mD)(rear-front)%m棧和隊(duì)列的共同點(diǎn)是()。都是先進(jìn)先出 B)都是先進(jìn)后出VC)只允許在端點(diǎn)處插入和刪除元素 D)沒有共同點(diǎn)設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1，e2,e3,e4,e5和e6依次通過棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1則棧S的容量至少應(yīng)該是()。A)6B)4VC)3D)2設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1,每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。A）12 VB）33 C）18 D）40由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（）A）2 B）3 C）4VD）5二叉樹中第i（iN1）層上的結(jié)點(diǎn)數(shù)最多有（）個(gè)。A）2iB）2i 7C）2i-1 D）2i-1在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。A）不確定 B）2nC）2n+1VD）2n-1一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?、或?yàn)?,則這棵二叉樹最少有（）結(jié)點(diǎn)。A）2h VB）2h-1 C）2h+1 D）h+1若一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是（）。A）9 VB）11 C）15 D）不確定樹的后根遍歷序列等同于該樹對(duì)應(yīng)的二叉樹的（）。A）先序序列 VB）中序序列C）后序序列D）層序序列在二叉樹結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（）。A）都不相同 VB）完全相同C）先序和中序相同，而與后序不同 D）中序和后序相同，而與先序不同下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（）A）有向圖 VB）無向圖 C）AOV網(wǎng)D）AOE網(wǎng)在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)（2）倍，在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)出度之和的（1）倍。A）1/2 VB）2 VC）1 D）4一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（）條邊。由n個(gè)頂點(diǎn)組成的有向圖，最多可以有（）條邊。A）n*n B）2n VC）n（n-1）VD）n（n-1）/2下列說法不正確的是（）。A） 圖的遍歷是從給定的源點(diǎn)出發(fā)每一個(gè)頂點(diǎn)僅被訪問一次B） 遍歷的基本算法有兩種：深度遍歷和廣度遍歷VC） 圖的深度遍歷不適用于有向圖D） 圖的深度遍歷是一個(gè)遞歸過程下面哪一方法可以判斷出一個(gè)有向圖是否有環(huán)（回路）（）。A）深度優(yōu)先遍歷 VB）拓?fù)渑判?C）求最短路徑D）求關(guān)鍵路徑下列算法中，（）算法用來求圖中每對(duì)頂點(diǎn)之間的最短路徑。A）Dijkstra VB）Floyed C）PrimD）Kruskal關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中（）。VA）從源點(diǎn)到匯點(diǎn)的最長路徑 B）從源點(diǎn)到匯點(diǎn)的最短路徑C）最長回路 D）最短回路若查找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的連續(xù)順序文件中采用順序查找法查找一個(gè)記錄，其平均查找長度ASL為（）。A）（n-1）/2 B）n/2 VC）（n+1）/2 D）n下面關(guān)于二分查找的敘述正確的是 （ ）。A） 表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B） 表必須有序，而且只能從小到大排列C表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型VD） 表必須有序，且表只能以順序方式存儲(chǔ)

折半查找的時(shí)間復(fù)雜性為( )。A)O(n2) B)O(n) C)O(nlogn)VD)O(logn)當(dāng)采用分快查找時(shí)，數(shù)據(jù)的組織方式為 ( )。A)數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序VB)數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊(除最后一塊外)中數(shù)據(jù)個(gè)數(shù)需相同34,下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是( )。A)哈希函數(shù)構(gòu)造的越復(fù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小除留余數(shù)法是所有哈希函數(shù)中最好的VC)不存在特別好與壞的哈希函數(shù)，要視情況而定若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可35.下面給出的四種排序法中()排序法是不穩(wěn)定性排序法。A)A)插入B)冒泡二路歸并 VD)堆36,穩(wěn)定的排序方法是36,穩(wěn)定的排序方法是()。A)直接插入排序和快速排序VB)折半插入排序和起泡排序C)C)簡單選擇排序和四路歸并排序D)樹形選擇排序和shell排序37,有一組數(shù)據(jù)37,有一組數(shù)據(jù)(15，9，7，8，20，-1，為()(按遞增序)。VA)下面的B，C，D都不對(duì)。4)用快速排序的劃分方法進(jìn)行一趟劃分后數(shù)據(jù)的排序B)9，7，8，4，-1，7，15，20C)C)20，15，8，9，7，-1，4，7D)9，4，7，8，7，-1，15，2038,設(shè)有一個(gè)文件有200個(gè)記錄，按分塊查找法查找記錄，如分成10塊，每塊20個(gè)記錄，用二分查找法查索引表，用順序查找法查塊內(nèi)記錄，則平均查找長度為)。A)8)4 B)10)5 C)13)4 VD)1639,快速排序在最壞情況下的時(shí)間復(fù)雜性為()。A)O(nlog2n) VB)O(n2) C)O(n) D)O(nlogn)二、填空一個(gè)算法的效率可分為時(shí)間效率和空間效率。線性表L=(a1,a2,???,an用數(shù)組表示，假定插入、刪除表中任一元素的概率相同，則插入、刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是 和(n-1)/2 。對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為OOL，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(n)。順序存儲(chǔ)結(jié)構(gòu)是通過元素在計(jì)算機(jī)內(nèi)“物理位置相鄰"表示元素之間的邏輯關(guān)系的，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針表示元素之間的邏輯關(guān)系的。帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是： p-next=head。當(dāng)兩個(gè)棧共享一存儲(chǔ)區(qū)時(shí)，棧利用一維數(shù)組stack(1,n)表示，兩棧頂指針為top1與top2，則當(dāng)棧1空時(shí)，top1為1，棧2空時(shí)，top2為n，棧滿時(shí)為top1+top2==n。順序棧S用data[1))n]存儲(chǔ)數(shù)據(jù)，棧頂指針是top，則值為x的元素入棧的操作是—笙)top++=x。已知鏈隊(duì)列Q的頭尾指針分別是f和r，則將值x入隊(duì)的操作序列是p->data=e;p->next=NULL;Q)r->next=p;Q)r=p;。稀疏矩陣的存儲(chǔ)策略是只存儲(chǔ) 非零元素。稀疏矩陣的存儲(chǔ)方法主要有兩個(gè)：一個(gè)是二元組，另一個(gè)是十字鏈表示法。二叉樹由― ，左子樹、右子樹 三個(gè)基本單元組成。一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有,n1=0 個(gè)度為1的結(jié)點(diǎn)、有01)/2,(叫+2%)個(gè)分支(非終端)結(jié)點(diǎn)和(>=%+%+%,n0=n2+1),(n+1)/2個(gè)葉子，該滿二叉樹的深度為log2(n+1)。設(shè)F是由T1,T2,T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，已知T1,T2,T3的結(jié)點(diǎn)數(shù)分別為n1，n2和n3則二叉樹B的左子樹中有n1-1個(gè)結(jié)點(diǎn)，右子樹中有n2+n3個(gè)結(jié)點(diǎn)。線索二叉樹的左線索指向其前驅(qū)右線索指向其 后繼。設(shè)一棵Huffman樹有6個(gè)葉結(jié)點(diǎn)，權(quán)值分別為3、4、7、14、15、20，則根節(jié)點(diǎn)的權(quán)值是63當(dāng)初始記錄序列按關(guān)鍵字有序或基本有序時(shí)，快速排序算法的時(shí)間復(fù)雜性為O(m)。在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為—n±1 。設(shè)一棵完全二叉樹具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹有 500 個(gè)葉子結(jié)點(diǎn)，有499個(gè)度為2的結(jié)點(diǎn)，有個(gè)度為1的結(jié)點(diǎn)。若用n表示圖中頂點(diǎn)數(shù)目，則有n*(n-1)/2 條邊的無向圖成為完全圖。19,設(shè)無向圖G有n個(gè)頂點(diǎn)和e條邊，每個(gè)頂點(diǎn)Vi的度為di(1v=iv=n〉，則e=1/2^^dii=1在有n個(gè)頂點(diǎn)的有向圖中，若要使任意兩點(diǎn)間可以互相到達(dá)，則至少需要n*(n-1)條弧。在圖G的鄰接表表示中，每個(gè)頂點(diǎn)鄰接表中所含的結(jié)點(diǎn)數(shù)，對(duì)于無向圖來說等于該頂點(diǎn)的度：對(duì)于有向圖來說等于該頂點(diǎn)的出度。順序查找n個(gè)元素的順序表，若杳找成功，則比較關(guān)鍵字的次數(shù)最多為n次：當(dāng)使用監(jiān)TOC\o"1-5"\h\z視哨時(shí)，若杳找失敗，則比較關(guān)鍵字的次數(shù)為 n+1 。在順序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為 4 。對(duì)于長度為255的表，采用分塊查找，每塊的最佳長度為 16 。已知二叉排序樹的左右子樹均不為不，則左子樹 上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)值，右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值。動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有插入和刪除運(yùn)算，而后者不包含這兩種運(yùn)算。為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是設(shè)計(jì)一個(gè)好的哈希函數(shù)和選擇一個(gè)處理沖突的方法 。若不考慮基數(shù)排序，則在排序過程中，主要進(jìn)行的兩種基本操作是關(guān)鍵字的比較和記錄的移動(dòng)。屬于不穩(wěn)定排序的有希爾、快速、選擇、堆排序 。

NULL3.寫出下列二叉樹的前序，中序，后序遍歷序列及對(duì)應(yīng)的森林。解答：前序：-+解答：前序：-+a*bc中序：a+b*c-d/后序：abc*+de//de4,試將森林F={T1,T2,T3,T4}轉(zhuǎn)換為一棵二叉樹。5.已知葉子結(jié)點(diǎn)值2，3，5，65.已知葉子結(jié)點(diǎn)值2，3，5，6，9,11，構(gòu)造哈夫曼樹，計(jì)算其帶權(quán)路徑長度。解答:L=4*2+3+3*2=1716,設(shè)一棵樹T中邊的集合為｛(A, B), (A,C), (A, D), (B, E), (C, F), (C,G)｝，要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。解答:7.已知有向圖G=(V,E),解答:7.已知有向圖G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}E={vV1,V2>,vV1,V3>,vV1,V4>,vV2,V5>,vV3,V5>,vV3,V6>,vV4,V6>,vV5,V7>,vV6,V7>},G的拓?fù)湫蛄惺?)。8,有7個(gè)頂點(diǎn)(8,有7個(gè)頂點(diǎn)(v1,v2,v3,v4,v5,v6,v7)的有向圖的鄰接矩陣如右圖。請(qǐng)回答相關(guān)問題:解答:(1)82538888828888888135888885888888839888888588oo8ooooOO(2)寫出從v1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。深度優(yōu)先遍歷：V1V2V6V7V3V4V5廣度優(yōu)先遍歷：V1V2V3V4V6V5V7已知如圖所示的有向圖，請(qǐng)給出該圖的:

（1） 每個(gè)頂點(diǎn)的入/出度;（2） 鄰接矩陣；頂點(diǎn)123456入度32頂點(diǎn)123456入度321122出度022313（4）逆鄰接表。888888188188818881881811188888118818鄰接矩陣0112A->0->3A01->->12->->45->A5A23->1->5A23 ->3A34->2->5->6A34 ->1A45->0A453->5A56->0->1->4A56 ->2->3A鄰接表逆鄰接表設(shè)無向圖G（所下圖所示），要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列，找出下面網(wǎng)絡(luò)的最小生成樹。解答：深度優(yōu)先:：網(wǎng)絡(luò)的最小生成樹。解答：深度優(yōu)先:：ABDFCEG廣度優(yōu)先：ABDCEFG11,分別說明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。解答：Huffman算法：最優(yōu)二叉樹，樹的帶權(quán)路徑最短。Dijkstra算法：求單源最短路徑Prim算法：求最小生成樹Kruskal算法：求最小生成樹

123456ve0438710vl044891012.已知圖G如圖所示。（1）（2）（3）解答：0畫出圖G的鄰接表；畫出從頂點(diǎn)1出發(fā)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；寫出圖G的拓?fù)渑判蛄校?->1->2->3A2->4A3->412.已知圖G如圖所示。（1）（2）（3）解答：0畫出圖G的鄰接表；畫出從頂點(diǎn)1出發(fā)的深度優(yōu)先生成樹和廣度優(yōu)先生成樹；寫出圖G的拓?fù)渑判蛄校?->1->2->3A2->4A3->4->5A4->5A5->5->6A6->6A7A123456（1）(2)(3)13.，2,3,4,5,6,7已知AOE網(wǎng)如下，試求其關(guān)鍵路徑。要求寫出計(jì)算過程。2S=4&8=15-446解答:14.（1） 按表中元素的順序依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹，并求出在等概率情況下查找成功的平均查找長度。（2） 按表中元素的順序進(jìn)行插入生成一棵AVL樹，畫出該樹。并求出在等概率情況下查找成功的平均查找長度。解答：ASL=(1+2*2+3*3+4)/12=18/7

ASL=(1+2*2+3*4)/12=17/710,25,50,99｝是堆嗎？若不是，創(chuàng)建一個(gè)堆。解答：15,假定一個(gè)線性表為L=(18,75,60,43,54,90,46,31,58,73,15,34)進(jìn)行散列存儲(chǔ)，采用的Hash函數(shù)為H(K)=Kmod13,當(dāng)發(fā)生沖突時(shí)用線性探測(cè)法處理沖突，設(shè)HashASL=(1+2*2+3*4)/12=17/710,25,50,99｝是堆嗎？若不是，創(chuàng)建一個(gè)堆。解答：解答：0123456789101112345415431831466058757390ASL=(7+!*2+4**/22=25/1212114141[89,27,52,90,15,28,100,72]解答：一趟：89[72,27,52,28,15,89,100,90]二趟：72[15,27,52,28,72]89[100,90]三趟：15[,27,52,28] 7289[100,90]四趟：15 27[,52,28] 7289[100,90]五趟：15 27 [28,52]7289 [100,90]六趟：15 2728527289[90,100]16.用快速排序方法對(duì)下列整數(shù)序列進(jìn)行排序，寫出中間及最后結(jié)果。17,序列｛40，38,60,95,76,四、算法設(shè)計(jì)題已知L為帶頭結(jié)點(diǎn)的單鏈表，設(shè)計(jì)一個(gè)算法計(jì)算數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)個(gè)數(shù)。intcount(LinkListLa,ElemTypex)(〃計(jì)數(shù)x出現(xiàn)的次數(shù)LinkListp=La->next;//p為工作指針intn=0;while(p)(if(p->data==x)n++;p=p->next;}returnn;}設(shè)L為有序順序表，試編寫一個(gè)算法刪除L中的重復(fù)元素。要求不要另開辟數(shù)據(jù)存儲(chǔ)空間。例如：L=(1，1，2,4,4，9，9，9)，執(zhí)行算法后L=(1，2,4，9)intdelduplicate(inta[],intn)(inti,j,k,count;i=0;while(i<n)(j=i+1;count=0;while(j<n&&a[j]==a[i])(j++;count++;}if(count!=0)(for(k=j;k<n;k++)a[k-count]=a[k];}n=n-count;i++;}returnn;}假設(shè)一個(gè)人算術(shù)表達(dá)式包含圓括弧，編寫一個(gè)判別表達(dá)式中括弧是否正確匹配的算法。Statusmatching(SqStackS,stringexp){intstate=1;inti=0;SElemTypee;while(i<strlen(exp)&&state){switch(exp[i]){case'(':{push(S,exp[i]);break;

}