數(shù)據(jù)結(jié)構(gòu)考試試題

1、精選優(yōu)質(zhì)文檔-傾情為你奉上××科技大學(xué)成都學(xué)院二零零八至二零零九學(xué)年第一學(xué)期 數(shù)據(jù)結(jié)構(gòu) 課堂測(cè)試（60分鐘） 閉卷 考試時(shí)間：題號(hào)一二三總分評(píng)卷教師分?jǐn)?shù)一填空題（每空2分，共40分）；1. 數(shù)據(jù)結(jié)構(gòu)算法中，通常用時(shí)間復(fù)雜度和_空間復(fù)雜度_兩種方法衡量其效率。2. 下面程序段的時(shí)間復(fù)雜度為_(kāi)O(n2)_。(n>1) for(i = 1; i <= n; i+)for(j = 1; j <= i; j+) x = x + 1; 3. 靜態(tài)鏈表中指針表示的是_下一結(jié)點(diǎn)的地址_。4. 線型表、棧和隊(duì)列都是_線型_結(jié)構(gòu)，可以在線型表的_任意_位置插入和刪除元素；對(duì)于

2、棧只能在_棧頂_插入和刪除元素；對(duì)于隊(duì)列只能在_隊(duì)尾_插入元素和_隊(duì)頭_刪除元素。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有_n-1_個(gè)元素。6. 在一個(gè)長(zhǎng)度為n 的順序表中第i 個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_n-i+1_個(gè)元素。7. 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的_前驅(qū)_。8. 帶有一個(gè)頭結(jié)點(diǎn)的單鏈表head為空的條件是_head->next= =NULL_。9. 在棧頂指針為hs的鏈棧中，判斷?？盏臈l件是_hs= =NULL_。10. 在hq的鏈隊(duì)列中，判定只有一個(gè)結(jié)點(diǎn)的條件是_hq.front->next=hq.re

3、ar_。11. 非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p指向），滿足條件_p->next=head。12. 兩個(gè)串相等的充分必要條件是_串長(zhǎng)相等且對(duì)應(yīng)字符相等_。13. 空串是_長(zhǎng)度為0的串_，其長(zhǎng)度等于_0_。14. 空格串是_由空格字符組成的串_， 其長(zhǎng)度等于_空格的個(gè)數(shù)_ 。二單項(xiàng)選擇題（每題2分，共30分）；（說(shuō)明：請(qǐng)將答案填入下表中）題號(hào)12345678910答案AABBDBCBBC題號(hào)1112131415答案AACDD1. 若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（A）存儲(chǔ)方式最節(jié)省時(shí)間。A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循

4、環(huán)鏈表2. 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn)，則如下的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為：A表元編號(hào)結(jié)點(diǎn)表元間關(guān)系1a132a213a32A循環(huán)鏈表 B單鏈表 C雙向循環(huán)鏈表 D雙向鏈表3. 有六個(gè)元素6，5，4，3，2，1 的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（B ）A. 5 4 3 6 1 2 B. 3 4 6 5 2 1 C. 4 5 3 1 2 6 D. 2 3 4 1 5 64. 若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間V1.m，topi代表第i 個(gè)棧( i =1,2)棧頂，棧1 的底在v1，棧2 的底在Vm，則棧滿的條件是（B ）。A. top2-top1|=0 B. top1+1=top2 C

5、. top1+top2=m D. top1=top25. 數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，front為當(dāng)前隊(duì)列頭元素的前一位置，rear為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素的公式為(D)A. rearfront B.（nfrontrear）% nC. nrearfront D.（nrearfront）% n6. 設(shè)棧S 和隊(duì)列Q 的初始狀態(tài)為空，元素e1，e2，e3，e4,e5 和e6 依次通過(guò)棧S，一個(gè)元素出棧后即進(jìn)隊(duì)列Q，若6 個(gè)元素出隊(duì)的序列是e2，e4,e6,e5，e3,e1 則棧S 的容量至少應(yīng)該是( B)。A 6 B. 4 C. 3 D. 27. 在數(shù)據(jù)結(jié)構(gòu)中，從邏

6、輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ C）。 A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)8. 判定一個(gè)順序棧ST（最多元素為N）為空的條件是 （B ）。ASTtop ！= ST.baseBSTtop=ST.baseCSTtop！=N DSTtop=N9. 一個(gè)隊(duì)列的入列序列是1，2，3，4，則隊(duì)列的輸出序列是 B 。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,110. 判定一個(gè)循環(huán)隊(duì)列QU(最多元素為N)為空的條件是 C 。AQU.front= （QU.rear+1）%N BQU.front！= （QU.rear+1）%NCQU.fr

7、ont= QU.rear DQU.front！= QU.rear 11. 判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0）為滿隊(duì)列的條件是 A 。AQU.front= （QU.rear+1）%N BQU.front！= （QU.rear+1）%NCQU.front= QU.rear DQU.front！= QU.rear+112. 不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是 A Ahead=NULL Bhead - >next=NULL Chead- >next=head Dhead!=NULL13. 15.在雙向鏈表指針p 的結(jié)點(diǎn)前插入一個(gè)指針q 的結(jié)點(diǎn)操作是（C ）。A. p->L

8、link=q;q->Rlink=p;p->Llink->Rlink=q;q->Llink=q；B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;14. 從一個(gè)具有n個(gè)結(jié)點(diǎn)的

9、單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較_D_個(gè)結(jié)點(diǎn)。AnBn/2C(n1)/2D(n+1)/215. 設(shè)串s1=ABCDEFG,s2='PQRST',函數(shù)con(x,y)返回x和y串的連接串，subs（s,i,j）返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的字串， len(s)返回串s的長(zhǎng)度，則con(subs(s1,2,len(s2), subs(s1,len(s2),2)的結(jié)果串是 D A）BCDEF B）BCDEFG C）BCPQRST D）BCDEFEF三綜合題（每題6分，共30分）1. 線性表具有兩種存儲(chǔ)方式，即順序方式和鏈接方式?，F(xiàn)有一個(gè)具有五

10、個(gè)元素的線性表L=23，17，47，05，31，若它以單鏈表方式存儲(chǔ)在下列100119號(hào)地址空間中，每個(gè)結(jié)點(diǎn)由數(shù)據(jù)（占2個(gè)字節(jié)）和指針（占2個(gè)字節(jié),由大寫(xiě)字母表示）組成，如下所示：其中指針p，q，r，s，t的值分別為多少？該線性表的首結(jié)點(diǎn)起始地址為多少？末結(jié)點(diǎn)的起始地址為多少？(共6分)2. 答：p= 108 q = 116 r = 112 s= 0 或NULL t= 100 首址= 104 末址= 112 。3. 如果想將輸入的一個(gè)字符序列逆序輸出，如輸入“abcdef ”，輸出“fedcba”，請(qǐng)分析用線性表、堆棧和隊(duì)列等方式正確輸出的可能性？ (共6分)線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)

11、變量（j-）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。4. 寫(xiě)出刪除順序表中第i個(gè)元素的算法：(共6分)Status ListDelete_sq(SqList &L, int i, ElemType &e)Status del_sqllist(SqList &L,int i, ElemType &e) if (i < 1i > L.length) return ERROR; e= L.elemi; for (j=i+1;j<= L.length;j+) L.elemj-1= L.elem

12、j; -L.length; return OK; 5. 寫(xiě)出順序棧的入棧算法(共6分)Status Push(SqStack &S, SelemType e)void Push ( Stack &S, ElemType e ) /在棧頂之上插入元素e為新的棧頂元素p = new LNode ; / 建新的結(jié)點(diǎn)if(!p) exit(1) ; / 存儲(chǔ)分配失敗p -> data = e; p->next=S.top ;/ 鏈接到原來(lái)的棧頂S.top = p; / 移動(dòng)棧頂指針+S.length;/ 棧的長(zhǎng)度增1 / Push6. 寫(xiě)出鏈隊(duì)列的出隊(duì)列算法(共6分)Sta

13、tus DeQueue(LinkQueue &Q, QelemType &e) Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear = p) Q.rear = Q.front; free (p); return

14、 OK;××科技大學(xué)成都學(xué)院20082009學(xué)年第一學(xué)期中期試題數(shù)據(jù)結(jié)構(gòu)答案一 填空題（每題2分，共40分）；題號(hào)參考答案1空間復(fù)雜度2O(n2)3下一結(jié)點(diǎn)的地址4線型，任意，棧頂，隊(duì)尾，隊(duì)頭5n-16n-i+17前驅(qū)8head->next= =NULL9hs= =NULL10hq.front->next=hq.rear11p->next=head12串長(zhǎng)相等且對(duì)應(yīng)字符相等13長(zhǎng)度為0的串，014由空格字符組成的串，空格的個(gè)數(shù)二單項(xiàng)選擇題（每題2分，共30分）； 題號(hào)12345678910答案AABBDBCBBC題號(hào)1112131415答案AACDD三綜合

15、題（共30分）7. p= 108 q = 116 r = 112 s= 0 或NULL t= 100 首址= 104 末址= 112 。8. 線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j-）從表尾開(kāi)始打印輸出；堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。3Status del_sqllist(SqList &L,int i, ElemType &e) if (i < 1i > L.length) return ERROR; e= L.elemi; for (j=i+1;j<= L.length;j+) L.elemj-1= L

16、.elemj; -L.length; return OK; 4.void Push ( Stack &S, ElemType e ) /在棧頂之上插入元素e為新的棧頂元素p = new LNode ; / 建新的結(jié)點(diǎn)if(!p) exit(1) ; / 存儲(chǔ)分配失敗p -> data = e; p->next=S.top ;/ 鏈接到原來(lái)的棧頂S.top = p; / 移動(dòng)棧頂指針+S.length;/ 棧的長(zhǎng)度增1 / Push5 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

17、/用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;全真模擬試題（一）一、         單項(xiàng)選擇題（在每小題的4個(gè)備選答案中，選出正確的答案，并將其號(hào)碼填在題干的括號(hào)內(nèi)。每小題2分，共24

18、分）1  若某線性表中最常用的操作是取第i 個(gè)元素和找第i個(gè)元素的前趨元素，則采用（   4   ）存儲(chǔ)方式最節(jié)省時(shí)間。單鏈表      雙鏈表      單向循環(huán)       順序表2  串是任意有限個(gè)（  1     ）符號(hào)構(gòu)成的序列  

19、;      符號(hào)構(gòu)成的集合字符構(gòu)成的序列        字符構(gòu)成的集合3  設(shè)矩陣A（aij ，li,j 10）的元素滿足：aij0(ij, li, j 10)aij=0 (i<j, li, j 10)現(xiàn)將A的所有非0元素以行序?yàn)橹餍虼娣旁谑椎刂窞?000的存儲(chǔ)區(qū)域中，每個(gè)元素占有4個(gè)單元，則元素A95的首址為2340       2336 

20、;    2164      21604  如果以鏈表作為棧的存儲(chǔ)結(jié)構(gòu)，則退棧操作時(shí)（      ）     必須判別棧是否滿        對(duì)棧不作任何判別     必須判別棧是否空    

21、0;   判別棧元素的類型5  設(shè)數(shù)組Data0.m作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作的語(yǔ)句為（       ）front=front+1         front=(front+1)% mrear=(rear+1)%m       front=(front+1)%(

22、m+1)6  深度為6（根的層次為1）的二叉樹(shù)至多有（      ）結(jié)點(diǎn)。     64        32       31        637  將含100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每層上從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。編號(hào)為

23、49的結(jié)點(diǎn)X的雙親編號(hào)為（     ）24      25       23        無(wú)法確定8  設(shè)有一個(gè)無(wú)向圖G=（V，E）和G=（V，E）如果G為G的生成樹(shù)，則下面不正確的說(shuō)法是（       ）G為G 的子圖    

24、               G為G 的邊通分量G為G的極小連通子圖且V=V   G為G的一個(gè)無(wú)環(huán)子圖9  用線性探測(cè)法查找閉散列表，可能要探測(cè)多個(gè)散列地址，這些位置上的鍵值（   ）     一定都是同義詞        一定都不是同義詞 

25、; 都相同                 不一定都是同義詞10          二分查找要求被查找的表是（    3  ）     鍵值有序的鏈接表     

26、;鏈接表但鍵值不一定有序 鍵值有序的順序表     順序表但鍵值不一定有序11          當(dāng)初始序列已經(jīng)按鍵值有序，用直接插入算法對(duì)其進(jìn)行排序，需要循環(huán)的次數(shù)為（      ）n2                 

27、; nlog2n       log2n          n-112          堆是一個(gè)鍵值序列k1,k2, kn,對(duì)i=1,2,|_n/2_|,滿足(      )kik2ik2i+1      &

28、#160;         ki<k2i+1<k2ikik2i且kik2i+1(2i+1n)   kik2i 或kik2i+1(2i+1n)二、         判斷題（判斷下列各題是否正確，正確在括號(hào)內(nèi)打“V”，錯(cuò)的找“X”。每小題1分，共10分）1  雙鏈表中至多只有一個(gè)結(jié)點(diǎn)的后繼指針為空。（    ）

29、2  在循環(huán)隊(duì)列中，front指向隊(duì)列中第一個(gè)元素的前一位置，rear指向?qū)嶋H的隊(duì)尾元素，隊(duì)列為滿的條件是front=rear。（     ）3  對(duì)鏈表進(jìn)行插入和刪除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)。（      ）4  ?？梢宰鳛閷?shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言過(guò)程調(diào)用時(shí)的一種數(shù)據(jù)結(jié)構(gòu)。（    ）5  在一個(gè)有向圖的拓樸序列中，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b>。

30、(   )i6  對(duì)有向圖G，如果從任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問(wèn)每個(gè)頂點(diǎn)，則該圖一定是完全圖。(    )7  “順序查找法”是指在順序表上進(jìn)行查找的方法。（    ）8  向二叉排序樹(shù)插入一個(gè)新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)一定成為二叉排序樹(shù)的一個(gè)葉子結(jié)點(diǎn)。（）9  鍵值序列A，C，D，E，F(xiàn)，E，F(xiàn)是一個(gè)堆。10       &

31、#160;  二路歸并時(shí)，被歸并的兩個(gè)子序列中的關(guān)鍵字個(gè)數(shù)一定要相等。（）三、         填空題（每空2 分，共24分）1  設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是_；r=s;  r->next=null;。2  在單鏈表中，指針p  所指結(jié)點(diǎn)為最后一個(gè)結(jié)點(diǎn)的條件是_。3  設(shè)一個(gè)鏈棧的棧頂指針是ls，棧中結(jié)點(diǎn)格式為i

32、nfo | link ,?？盏臈l件是_.如果棧不為空，則退棧操作為p=ls；_；free(p);。4  已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)中有_ 個(gè)葉子的結(jié)點(diǎn)。5  樹(shù)有三種常用的存儲(chǔ)結(jié)構(gòu)，即孩子鏈表法、孩子兄弟鏈表法和_ .6  N個(gè)頂點(diǎn)的連通圖的生成樹(shù)有_條邊。7  一個(gè)有向圖G中若有弧<vi,vj>、<vj,vk>和<vi,vk>, 則在圖G的拓?fù)湫蛄兄?，頂點(diǎn)vi,vj和vk的相對(duì)位置為_(kāi)。8  設(shè)表中元素的

33、初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序方法對(duì)其進(jìn)行（按遞增排序），最省時(shí)間，最費(fèi)時(shí)間。9  下面是將鍵值為x 的結(jié)點(diǎn)插入到二叉排序樹(shù)中的算法，請(qǐng)?jiān)趧澗€處填上適當(dāng)?shù)膬?nèi)容。typedef struct pnode  int key;   struct pnode   *left,   *right;  pnode;void searchinsert(int x, pnode t )  /*t為二叉排序樹(shù)

34、根結(jié)點(diǎn)的指針*if (         )p=malloc(size);p->key=x;p->lchild=null;  p->rchild=null;t=p; else if (x<t->key) searchinsert(x,t->lchild)         else_;四、      

35、60;  應(yīng)用題（本題共分）1樹(shù)的后根遍歷方法是：若樹(shù)非空則（分）（1）依據(jù)次后根遍歷根的各個(gè)子樹(shù)，m;（2）訪問(wèn)根結(jié)點(diǎn)2.       將下圖的森林轉(zhuǎn)換為二叉樹(shù)。（分）3.       下圖表示一個(gè)地區(qū)的交通網(wǎng)，頂點(diǎn)表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費(fèi)的代價(jià)。怎樣選擇能夠溝通每個(gè)城市且總造價(jià)最省的n-1條公路，畫(huà)出所有可能的方案。（分） 圖7.11 遍歷無(wú)向圖 (a) 無(wú)向圖G6  

36、(b) 深度優(yōu)先搜索示例  (c) G6的鄰接表表示(c)表頭結(jié)點(diǎn)                      4已知一個(gè)無(wú)向圖的鄰接表如下圖所示。（本題分，每小題分）                &

37、#160;(1)    畫(huà)出這個(gè)圖。(2) 以v1為出發(fā)點(diǎn)，對(duì)圖進(jìn)行廣度優(yōu)先搜索，寫(xiě)出所有可能的訪問(wèn)序列。5.設(shè)n個(gè)元素的有序表為，為一個(gè)給定的值，二分查找算法如下：  int binsearch(sqlist R, keytype K)  j=1;h=n ;suc=0;   while(j<=h)&&(!suc)    mid =(j+h)/2;     switch

38、60;      case K=Rmid.key:  suc=1; break;        case K<Rmid.key:  h=mid-1; break;        case K>Rmid.key:  j=mid+1      

39、;        if (suc)  return(mid);  else return(0);將上述算法中劃線語(yǔ)句改為：K<Rmid.key:  h=mid.（）           改動(dòng)后，算法能否正常工作？請(qǐng)說(shuō)明原因。（）          

40、60;若算法不能正常工作，給出一個(gè)查找序列和一個(gè)出錯(cuò)情況的查找鍵值；若能正常工作，請(qǐng)給出一個(gè)查找序列和查找某個(gè)鍵值的比較次數(shù)。（本題分，每小題分）6.有一組鍵值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大進(jìn)行排序，請(qǐng)寫(xiě)出每趟的結(jié)果，并標(biāo)明在第一趟排序過(guò)程中鍵值的移動(dòng)情況。（本題分）五、設(shè)計(jì)題（共14分）1設(shè)棵二叉樹(shù)以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)為lchild |data |rchild 。設(shè)計(jì)一個(gè)算法，求在前根序列中處于第k個(gè)位置的結(jié)點(diǎn)。（本題分）2  設(shè)某單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為data |next,試畫(huà)出該鏈表的結(jié)構(gòu)圖，并用類語(yǔ)言編寫(xiě)算法判斷

41、該鏈表的元素是否是遞增的。（本題分）  全真模擬試題(一)參考答案一、單項(xiàng)選擇題1  2     3 分析：按題意，矩陣A是個(gè)三角矩陣，A I,j的首地址可用下列公式計(jì)算：          LOC（aij）=LOC(a11)+(k-1)*L        其中K為AI,j在A中的序號(hào)k=I*(I-1)/2+j，L為每個(gè)元素所占

42、的單元數(shù)。  所以有：LOC（aij）=2000+（9*（9-1）/2+5-1）*4=2000+160=2160。故為答案4     5678  分析：如果G為G的生成樹(shù)，那么G是G的子圖，也是G的無(wú)環(huán)子圖，并且還是G的極小連通子圖，且V=V，而連通分量則是指無(wú)向圖的極大連通子圖。故答案是錯(cuò)誤的。9  10。  11。   12。二、判斷題  1.v 2.x 3.v 4.v  5.x &

43、#160;6.x  7.x  8.v  9.v  10.x三、填空題1    R->next =s.2    P->next= = NULL3    Ls= =NULL 、ls=ls->link.4    12 分析： 設(shè)n1=2,n2=3,n3=4,       

44、60;樹(shù)的總結(jié)點(diǎn)數(shù)為n=n0+ n1+n2+n3        樹(shù)的分支數(shù)為n-1= n1+2n2+3n3         -得：-1= n2+2n3-n0        有n0=n2+2n3+1=3+2*4+1=125    雙親表示法。6    N-17 

45、   I,j,k.8    冒泡排序、快速排序9    T= =NULL、searchinsert(x,t->rchild).四、應(yīng)用題1    EBFGCKHIJDA。2    答案如圖應(yīng)用題I 9. 2.2 所示。    3    3分析：本題實(shí)際上是求最小生成樹(shù)問(wèn)題。由于釁中有兩條權(quán)值為6的邊，故可以得到兩種方案。答

46、案如圖應(yīng)用題I 9. 3.2 所示。4    答案：（1）答案如圖應(yīng)用題I 9. 4.2 所示。（2）v1 v2 v4 v5 v3  和   v1 v4 v2 v3 v5。5（1）經(jīng)過(guò)改動(dòng)以后，有可能出現(xiàn)死循環(huán)，比如當(dāng)查找的鍵值K小于有序表中的最小鍵值時(shí)，就會(huì)出現(xiàn)死循環(huán)。故算法不能正常進(jìn)行。   （2）假設(shè)有序表的查找序列為（2，3，4，5，6），當(dāng)待查的鍵值K=1時(shí)，出現(xiàn)死循環(huán)。6答案：

47、0;25     84     21      47       15       27      68      35     

48、 24第一趟  24     15     21      25      47       27      68      35  

49、60;   84第二趟  21     15     24      25      35       27      47     68 

50、     84第三趟  15     21     24      25      27      35       47     

51、; 68     84 得到   15      21     24      25       27       35      

52、; 47      68     84第一趟排序過(guò)程中鍵值的移動(dòng)情況如下：第一趟：         25    84    21     47      15   

53、60;  27     68     35     24 一次交換之后     24    84    21     47      15    &#

54、160; 27     68     35     25二次交換之后     24    25    21     47      15     &#

55、160;27     68     35     84                 24    25    21     47 

56、0;    15      27     68     35     84                 24    25    21     47      15      27     68     35 &