數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題（附答案）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題（附答案）一、算法設(shè)計(jì)題（每題15分，共60分）

答題要求：

①用自然語言說明所采用算法的思想；

②給出每個(gè)算法所需的數(shù)據(jù)結(jié)構(gòu)定義，并做必要說明；③寫出對應(yīng)的算法程序，并做必要的解釋。

1、有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，每個(gè)結(jié)點(diǎn)包括兩個(gè)域，一個(gè)是整型域info，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)的指針域next。假設(shè)單鏈表已建立，設(shè)計(jì)算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點(diǎn)，使得info域相等的結(jié)點(diǎn)只保存一個(gè)。

3、約瑟夫環(huán)問題（Josephus問題）是指編號為1、2、…，n的n（n>0）個(gè)人按順時(shí)針方向圍坐成一圈，現(xiàn)從第s個(gè)人開始按順時(shí)針方向報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，…，如此重復(fù)直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法，模擬此過程。

4、編程實(shí)現(xiàn)單鏈表的就地逆置。

23．在數(shù)組A[1..n]中有n個(gè)數(shù)據(jù)，試建立一個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個(gè).

5、設(shè)計(jì)一個(gè)盡可能的高效算法輸出單鏈表的倒數(shù)第K個(gè)元素。

3、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（15分）

（1）下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO

（2）通過對（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。

5、設(shè)從鍵盤輸入一整數(shù)的序列：a1,a2,a3，?，an,試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲輸入的整數(shù)，當(dāng)ai≠-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對異常狀況（入棧滿等）給出相應(yīng)的信息。

設(shè)有一個(gè)背包可以放入的物品重量為S，現(xiàn)有n件物品，重量分別為W1，W2，...，Wn。問能否從這n件物品中選擇若干件放入背包，使得放入的重量之和正好是S。設(shè)布爾函數(shù)Knap(S，n)表示背包問題的解，Wi(i=1,2,...，n)均為正整數(shù)，并已順序存儲地在數(shù)組W中。請?jiān)谝韵滤惴ǖ南聞澗€處填空，使其正確求解背包問題。

Knap(S，n)若S=0

則Knap←true

否則若（S0且n1)個(gè)整數(shù)存放到一維數(shù)組R中。設(shè)計(jì)一個(gè)盡可能高效（時(shí)間、空間）的算

法，將R中保存的序列循環(huán)左移p（08.給定nxm矩陣A[a..b,c..d],并設(shè)A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).設(shè)計(jì)一算法判定X的值是否在A中,要求時(shí)間繁雜度為O(m+n)。【

22.給定有m個(gè)整數(shù)的遞增有序數(shù)組a[1..m]和有n個(gè)整數(shù)的遞減有序數(shù)組b[1..n]，試寫出算法:將數(shù)組a和b歸并為遞增有序數(shù)組c[l..m+n]。(要求：算法的時(shí)間繁雜度為O(m+n))

4、要求二叉樹按二叉鏈表形式存儲，（15分）

（1）寫一個(gè)建立二叉樹的算法。（2）寫一個(gè)判別給定的二叉樹是否是完全二叉樹的算法。

3、已知一棵二叉樹的中序遍歷結(jié)果為：DBFEAGHCI，后序遍歷結(jié)果為：DFEBHGICA。（1）畫出這棵二叉樹，并寫出它的前序遍歷結(jié)果；（2）將這棵二叉樹轉(zhuǎn)換成等價(jià)的森林或樹。

24.將二叉樹bt中每一個(gè)結(jié)點(diǎn)的左右子樹互換的C語言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分別為進(jìn)隊(duì)，出隊(duì)和判別隊(duì)列是否為空的函數(shù)，請?zhí)顚懰惴ㄖ械每瞻滋?，完成其功能?/p>

typedefstructnode

{intdata;structnode*lchild,*rchild;}btnode;voidEXCHANGE(btnode*bt){btnode*p,*q;

if(bt){ADDQ(Q,bt);

while(!EMPTY(Q))

{p=DELQ(Q);q=(1)___;p->rchild=(2)___;(3)___=q;

if(p->lchild)(4)___;if(p->rchild)(5)___;}

}}

25.設(shè)t是給定的一棵二叉樹，下面的遞歸程序count(t)用于求得:二叉樹t中具有非空的左,右兩個(gè)兒子的結(jié)點(diǎn)個(gè)數(shù)N2;只有非空左兒子的個(gè)數(shù)NL;只有非空右兒子的結(jié)點(diǎn)個(gè)數(shù)NR和葉子結(jié)點(diǎn)個(gè)數(shù)N0。N2、NL、NR、N0都是全局量，且在調(diào)用count(t)之前都置為0.typedefstructnode

{intdata;structnode*lchild,*rchild;}node;intN2,NL,NR,N0;voidcount(node*t)

{if(t->lchild!=NULL)if(1)___N2++;elseNL++;elseif(2)___NR++;else(3)__;

if(t->lchild!=NULL)(4)____;if(t->rchild!=NULL)(5)____;}

26.樹的先序非遞歸算法。voidexample(b)

btree*b;

{btree*stack[20],*p；inttop;if(b!=null)

{top=1;stack[top]=b;while(top>0)

{p=stack[top];top--;printf(“%d〞,p->data);if(p->rchild!=null){(1)___;(2)___;}

if(p->lchild!=null)(3)___;(4)__;

}}}}

27.由二叉樹的前序遍歷和中序遍歷序列能確定唯一的一棵二叉樹，下面程序的作用是實(shí)現(xiàn)由已知某二叉樹的前序遍歷和中序遍歷序列，生成一棵用二叉鏈表表示的二叉樹并打印出后序遍歷序列，請寫出程序所缺的語句。

#defineMAX100typedefstructNode

{charinfo;structNode*llink,*rlink;}TNODE;charpred[MAX],inod[MAX];main(intargc,int**argv)

{TNODE*root;

if(argcinfo=(1)_______;

for((2)_______;rposllink=restore(ppos+1,(4)_______,k);

ptr->rlink=restore((5)_______+k,rpos+1,n-1-k);returnptr;}

postorder(TNODE*ptr){if(ptr=NULL)return;

postorder(ptr->llink);postorder(ptr->rlink);printf(“%c〞,ptr->info);}

28.證明由二叉樹的中序序列和后序序列，也可以唯一確定一棵二叉樹。

29.①試找出滿足以下條件的二叉樹

1）先序序列與后序序列一致2）中序序列與后序序列一致

3）先序序列與中序序列一致4）中序序列與層次遍歷序列一致

30.設(shè)一棵二叉樹的結(jié)點(diǎn)結(jié)構(gòu)為(LLINK,INFO,RLINK),ROOT為指向該二叉樹根結(jié)點(diǎn)的指針，p和q分別為指向該二叉樹中任意兩個(gè)結(jié)點(diǎn)的指針，試編寫一算法ANCESTOR（ROOT，p,q,r）,該算法找到p和q的最近共同祖先結(jié)點(diǎn)r。

31.設(shè)T是一棵滿二叉樹，編寫一個(gè)將T的先序遍歷序列轉(zhuǎn)換為后序遍歷序列的遞歸算法。32.請?jiān)O(shè)計(jì)一個(gè)算法，要求該算法把二叉樹的葉子結(jié)點(diǎn)按從左到右的順序連成一個(gè)單鏈表，表頭指針為head。二叉樹按二叉鏈表方式存儲，鏈接時(shí)用葉子結(jié)點(diǎn)的右指針域來存放單鏈表指針。分析你的算法的時(shí)、空繁雜度。

33.設(shè)兩棵二叉樹的的根結(jié)點(diǎn)地址分別為p和q，采用二叉鏈表的形式存儲這兩棵樹上所有的結(jié)點(diǎn)。請編寫程序，判斷它們是否相像。

34.一棵二叉樹以二叉鏈表來表示，求其指定的某一層k(k>1)上的葉子結(jié)點(diǎn)的個(gè)數(shù)。35.二叉樹T的中序遍歷序列和層次遍歷序列分別是BAFDGCE和ABCDEFG，試畫出該二叉樹，并寫出由二叉樹的中序遍歷序列和層次遍歷序列確定二叉樹的算法。36.設(shè)二叉樹的結(jié)點(diǎn)結(jié)構(gòu)是（Lc,data,Rc），其中Lc、Rc分別為指向左、右子樹根的指針，data是字符型數(shù)據(jù)。試寫出算法，求任意二叉樹中第一條最長的路徑長度，并輸出此路徑上各結(jié)點(diǎn)的值。

2、假設(shè)以鄰接矩陣作為圖的存儲結(jié)構(gòu)，編寫算法判別在給定的有向圖中是否存在一個(gè)簡單有向回路，若存在，則以頂點(diǎn)序列的方式輸出該回路（找到一條即可）。（注：圖中不存在頂點(diǎn)到自己的弧）

5、給定n個(gè)村莊之間的交通圖，若村莊i和j之間有道路，則將頂點(diǎn)i和j用邊連接，邊上的Wij表示這條道路的長度，現(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使離醫(yī)院最遠(yuǎn)的村莊到醫(yī)院的路程最短?試設(shè)計(jì)一個(gè)解答上述問題的算法，并應(yīng)用該算法解答如下圖的實(shí)例。（20分）21219563104426763241、對圖1所示的連通網(wǎng)G，請用Prim算法構(gòu)造其最小生成樹（每選取一條邊畫一個(gè)圖）。

圖1連通網(wǎng)G

4、已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，

E={,,,,,,,,}寫出G的拓?fù)渑判虻慕Y(jié)果。

37.在有向圖G中，假使r到G中的每個(gè)結(jié)點(diǎn)都有路徑可達(dá)，則稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)。編寫一個(gè)算法完成以下功能：（1）．建立有向圖G的鄰接表存儲結(jié)構(gòu)；（2）．判斷有向圖G是否有根，若有，則打印出所有根結(jié)點(diǎn)的值。

38．二部圖（bipartitegraph）G=（V，E）是一個(gè)能將其結(jié)點(diǎn)集V分為兩不相交子集V1和V2=V-V1的無向圖，使得：V1中的任何兩個(gè)結(jié)點(diǎn)在圖G中均不相鄰，V2中的任何結(jié)點(diǎn)在圖G中也均不相鄰。（1）．請各舉一個(gè)結(jié)點(diǎn)個(gè)數(shù)為5的二部圖和非二部圖的例子。（2）．請用C或PASCAL編寫一個(gè)函數(shù)BIPARTITE判斷一個(gè)連通無向圖G是否是二部圖，并分析程序的時(shí)間繁雜度。設(shè)G用二維數(shù)組A來表示，大小為n*n（n為結(jié)點(diǎn)個(gè)數(shù)）。請?jiān)诔绦蛑屑颖匾慕忉?。若有必要可直接利用堆?；蜿?duì)列操作?！?/p>

39．我們可用“破圈法〞求解帶權(quán)連通無向圖的一棵最小代價(jià)生成樹。所謂“破圈法〞就是“任取一圈，去掉圈上權(quán)最大的邊〞，反復(fù)執(zhí)行這一步驟，直到?jīng)]有圈為止。請給出用“破圈法〞求解給定的帶權(quán)連通無向圖的一棵最小代價(jià)生成樹的詳細(xì)算法，并用程序?qū)崿F(xiàn)你所給出的算法。注：圈就是回路。

40.請編寫一個(gè)判別給定二叉樹是否為二叉排序樹的算法，設(shè)二叉樹用llink-rlink法存儲。

41.假設(shè)K1，?，Kn是n個(gè)關(guān)鍵詞，試解答：

試用二叉查找樹的插入算法建立一棵二叉查找樹，即當(dāng)關(guān)鍵詞的插入次序?yàn)镵1，K2，?，Kn時(shí)，用算法建立一棵以LLINK/RLINK鏈接表示的二叉查找樹。

42.給出折半查找的遞歸算法，并給出算法時(shí)間繁雜度性分析。

43.寫出從哈希表中刪除關(guān)鍵字為K的一個(gè)記錄的算法，設(shè)哈希函數(shù)為H，解決沖突的方法為鏈地址法。

44.在用除余法作為散列函數(shù)、線性探測解決沖突的散列表中，寫一刪除關(guān)鍵字的算法，要求將所有可以前移的元素前移去填充被刪除的空位，以保證探測序列不致于斷裂。

45.假設(shè)一棵平衡二叉樹的每個(gè)結(jié)點(diǎn)都標(biāo)明白平衡因子b,試設(shè)計(jì)一個(gè)算法，求平衡二叉樹的高度。

46.有一個(gè)100*100的稀疏矩陣，其中1%的元素為非零元素，現(xiàn)要求用哈希表作存儲結(jié)構(gòu)。

（1）請你設(shè)計(jì)一個(gè)哈希表

（2）請寫一個(gè)對你所設(shè)計(jì)的哈希表中給定行值和列值存取矩陣元素的算法；并對你的算法所需時(shí)間和用一維數(shù)組（每個(gè)分量存放一個(gè)非零元素的行值，列值，和元素值）作存儲結(jié)構(gòu)時(shí)存取元素的算法.

2、畫出向小頂堆中參與數(shù)據(jù)4,2,5,8,3,6,10,1時(shí)，每參與一個(gè)數(shù)據(jù)后堆的變化。

47.冒泡排序算法是把大的元素向上移（氣泡的上?。部梢园研〉脑叵蛳乱疲馀莸南鲁粒┱埥o出上浮和下沉過程交替的冒泡排序算法。48.有n個(gè)記錄存儲在帶頭結(jié)點(diǎn)的雙向鏈表中，現(xiàn)用雙向起泡排序法對其按上升序進(jìn)行排序，請寫出這種排序的算法。（注：雙向起泡排序即相鄰兩趟排序向相反方向起泡）49.6.有一種簡單的排序算法，叫做計(jì)數(shù)排序（countsorting）。這種排序算法對一個(gè)待排序的表(用數(shù)組表示)進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。必需注意的是，表中所有待排序的關(guān)鍵碼互不一致，計(jì)數(shù)排序算法針對表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵碼比該記錄的關(guān)鍵碼小，假設(shè)針對某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的適合的存放位置即為c。(1)(3分)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義;

(2)(7分)使用Pascal或C語言編寫實(shí)現(xiàn)計(jì)數(shù)排序的算法；(3)(4分)對于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少?

(4)(3分)與簡單項(xiàng)選擇擇排序相比較，這種方法是否更好?為什么?

50.9．設(shè)有一個(gè)數(shù)組中存放了一個(gè)無序的關(guān)鍵序列K1、K2、?、Kn?，F(xiàn)要求將Kn放在將元素排序后的正確位置上，試編寫實(shí)現(xiàn)該功能的算法，要求比較關(guān)鍵字的次數(shù)不超過n。51.借助于快速排序的算法思想，在一組無序的記錄中查找給定關(guān)鍵字值等于key的記錄。設(shè)此組記錄存放于數(shù)組r[l..h]中。若查找成功，則輸出該記錄在r數(shù)組中的位置及其值，否則顯示“notfind〞信息。請編寫出算法并簡要說明算法思想。

52.二路插入排序是將待排關(guān)鍵字序列r[1..n]中關(guān)鍵字分二路分別按序插入到輔助向量d[1..n]前半部和后半部（注:向量d可視為循環(huán)表），其原則為，先將r[l]賦給d[1]，再從r[2]記錄開始分二路插入。編寫實(shí)現(xiàn)二路插入排序算法。

二、算法設(shè)計(jì)題（每題15分，共60分）

1、有一個(gè)帶頭結(jié)點(diǎn)的單鏈表，每個(gè)結(jié)點(diǎn)包括兩個(gè)域，一個(gè)是整型域info，另一個(gè)是指向下一個(gè)結(jié)點(diǎn)的指針域next。假設(shè)單鏈表已建立，設(shè)計(jì)算法刪除單鏈表中所有重復(fù)出現(xiàn)的結(jié)點(diǎn)，使得info域相等的結(jié)點(diǎn)只保存一個(gè)。#includetypedefchardatatype;typedefstructnode{datatypedata;structnode*next;}listnode;

typedeflistnode*linklist;

/**//*刪除單鏈表中重復(fù)的結(jié)點(diǎn)*//**/linklistdeletelist(linklisthead){listnode*p,*s,*q;p=head->next;while(p){s=p;

q=p->next;while(q)

if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else

{s=q;/*找與P結(jié)點(diǎn)值一致的結(jié)點(diǎn)*/q=q->next;}

p=p->next;}

returnhead;}

3、約瑟夫環(huán)問題（Josephus問題）是指編號為1、2、…，n的n（n>0）個(gè)人按順時(shí)針方向圍坐成一圈，現(xiàn)從第s個(gè)人開始按順時(shí)針方向報(bào)數(shù)，數(shù)到第m個(gè)人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，…，如此重復(fù)直到所有的人全部出列為止?，F(xiàn)要求采用循環(huán)鏈表結(jié)構(gòu)設(shè)計(jì)一個(gè)算法，模擬此過程。#includetypedefintdatatype;typedefstructnode{datatypedata;structnode*next;}listnode;

typedeflistnode*linklist;

voidjose(linklisthead,ints,intm)

{linklistk1,pre,p;intcount=1;pre=NULL;

k1=head;/*k1為報(bào)數(shù)的起點(diǎn)*/while(count!=s)/*找初始報(bào)數(shù)起點(diǎn)*/{pre=k1;

k1=k1->next;count++;}

while(k1->next!=k1)/*當(dāng)循環(huán)鏈表中的結(jié)點(diǎn)個(gè)數(shù)大于1時(shí)*/{p=k1;/*從k1開始報(bào)數(shù)*/count=1;

while(count!=m)/*連續(xù)數(shù)m個(gè)結(jié)點(diǎn)*/{pre=p;

p=p->next;count++;}

pre->next=p->next;/*輸出該結(jié)點(diǎn)，并刪除該結(jié)點(diǎn)*/printf(\free(p);

k1=pre->next;/*新的報(bào)數(shù)起點(diǎn)*/}

printf(\輸出最終一個(gè)結(jié)點(diǎn)*/free(k1);}

main()

{linklisthead,p,r;intn,s,m,i;printf(\scanf(\printf(\scanf(\printf(\scanf(\if(ndata=n;r=head;

for(i=n-1;i>0;i--)/*建立剩余n-1個(gè)結(jié)點(diǎn)*/{p=(linklist)malloc(sizeof(listnode));p->data=i;p->next=head;

head=p;}

r->next=head;/*生成循環(huán)鏈表*/jose(head,s,m);/*調(diào)用函數(shù)*/}}

4、voidLinkList_reverse(Linklist為簡化算法,假設(shè)表長大于2{

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;//把L的元素逐個(gè)插入新表表頭}

q->next=p;s->next=q;L->next=s;}//LinkList_reverse

23、[題目分析]此題要求建立有序的循環(huán)鏈表。從頭到尾掃描數(shù)組A，取出A[i]（0next=h;//形成空循環(huán)鏈表for(i=0;inext;

while(p!=hp=p->next;}//查找A[i]的插入位置

if(p==h||p->data!=A[i])//重復(fù)數(shù)據(jù)不再輸入{s=(LinkedList)malloc(sizeof(LNode));

s->data=A[i];pre->n