數(shù)據(jù)結(jié)構(gòu)練習(xí)題與答案

1、9.設(shè)有6個(gè)結(jié)點(diǎn)的無向圖，該圖至少應(yīng)有 ()條邊才能確保是一個(gè)連通圖。 數(shù)據(jù)結(jié)構(gòu)練習(xí)題（一） 、單選題 1. 棧和隊(duì)列的共同特點(diǎn)是（） A. 只允許在端點(diǎn)處插入和刪除元素 B. 都是先進(jìn)后出 C. 都是先進(jìn)先出 D. 沒有共同點(diǎn) 4. 設(shè)有一個(gè)二維數(shù)組Am n，假設(shè)A00 676（io），每個(gè)元素占一個(gè)空間，問A33 進(jìn)制表示。 存放位置在644（io），A22存放位置在 （10）存放在（）位置。腳注（10）表示用10 2.用方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（） A. 僅修改頭指針 B. 頭、尾指針都要修改 C. 僅修改尾指針 D. 頭、尾指針可能都要修改 3. 以下數(shù)據(jù)結(jié)構(gòu)中（） 是非線性結(jié)

2、構(gòu)。 A. 隊(duì)列B. 棧C. 線性表D.二叉樹 678 C . 692 D . 696 5. 樹最適合用來表示（） A.有序數(shù)據(jù)元素B. 無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù) 6. 二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（） k A . 2 -1B.2K+1C.2K-1 D. 2 k-1 7. 若有18個(gè)元素的有序表存放在一維數(shù)組 A19中，第一個(gè)元素放 A1中，現(xiàn)進(jìn)行二 分查找，則查找 A: 3 的比較序列的下標(biāo)依次為（） A. 1, 2, 3 B. 9 , 5, 2, 3 C. 9, 5, 3D. 9 , 4, 2, 3 8. 對(duì)于線性表（7, 34, 55,

3、25, 64, 46, 20, 10）進(jìn)行散列存儲(chǔ)時(shí)，若選用 H （K） =K %9作為散列函數(shù)，則散列地址為1的元素有（ ）個(gè)。 A . 1 B . 2 C . 3 D . 4 A.5B.6C.7D.8 、填空題 1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： 、和。 2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log 2n+14n)/ n2,其數(shù)量級(jí)表示為 。 3. 假定一棵樹的廣義表表示為A(C, D(E，F(xiàn)，G，H( I，J)，則樹中所含的結(jié)點(diǎn)數(shù)為 個(gè)，樹的深度為，樹的度為。 4. 若用鏈表存儲(chǔ)一棵二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指 針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹共

4、有 個(gè)指針域，其中有 個(gè) 指針域是存放了地址，有個(gè)指針是空指針。 5. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn) 分別有個(gè)和個(gè)。 6. AOV網(wǎng)是一種的圖。 7. 在一個(gè)具有n個(gè)頂點(diǎn)的無向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有 向完全圖中，包含有 條邊。 8. 假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù) 的元素成為一個(gè)子表，則得到的四個(gè)子表分別為、 、和。 9. 在快速排序、堆排序、歸并排序中， 排序是穩(wěn)定的。 三、計(jì)算題 1.在如下數(shù)組A中存儲(chǔ)了一個(gè)線性表，表頭指針為 A 0. next，試寫

5、出該線性表。 60 50 78 90 34 40 3 5 7 2 0 4 1 data n ext 2. 請(qǐng)畫出下圖的鄰接矩陣和鄰接表。 E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。 4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。 四、閱讀算法 1. LinkList mynote(LinkList L) /L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針 if(

6、L p=L; 51 :while(p next) p=p next ; 52 :p next=q ; q next=NULL; return L; 請(qǐng)回答下列問題： (1 )說明語句S1的功能； (2) 說明語句組S2的功能； (3) 設(shè)鏈表表示的線性表為(a,a2,an),寫出算法執(zhí)行后的返回值所表示的線性表。 2. void ABC(BTNode * BT) if BT ABC (BT-left); ABC (BT-right); coutdatadata) item=BST-data;查找成功 return ; else if(itemdata) return Find(,item);

7、else return Find(,item); /if 六、編寫算法 統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int Cou ntX(LNode* HL,ElemType x) 8. 數(shù)據(jù)結(jié)構(gòu)練習(xí)題(二) 、選擇題 1 下面關(guān)于線性表的敘述錯(cuò)誤的是()。 (A) 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 (B) 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間 (C) 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn) (D) 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn) 2 設(shè)哈夫曼樹中的葉子結(jié)點(diǎn)總數(shù)為m若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該哈夫曼樹中總共 有()個(gè)空指針域。 (A) 2m-1(B

8、) 2m(C) 2m+1(D) 4m 3. 設(shè)順序循環(huán)隊(duì)列 Q0 : M-1的頭指針和尾指針分別為F和R,頭指針F總是指向隊(duì)頭元素 的前一位置，尾指針 R總是指向隊(duì)尾元素的當(dāng)前位置，則該循環(huán)隊(duì)列中的元素個(gè)數(shù)為 ()。 (A) R-F (B) F-R (C) (R-F+M) % M (D) (F-R+M) % M 4. 設(shè)某棵二叉樹的中序遍歷序列為 序列為()。 ABCD前序遍歷序列為 CABD則后序遍歷該二叉樹得到 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5. 設(shè)某完全無向圖中有 n個(gè)頂點(diǎn), 則該完全無向圖中有( )條邊。 (A) n(n-1)/2 (B) n(

9、n-1) 2 (C) n 2 (D) n -1 6. (A) 9 (B) 10 (C) 11 (D) 12 7. 設(shè)某有向圖中有 n個(gè)頂點(diǎn)，則該有向圖對(duì)應(yīng)的鄰接表中有( )個(gè)表頭結(jié)點(diǎn)。 (A) n-1 (B) n (C) n+1 (D) 2n-1 設(shè)某棵二叉樹中有 2000個(gè)結(jié)點(diǎn)，則該二叉樹的最小高度為 設(shè)一組初始記錄關(guān)鍵字序列(5 , 2, 6, 3, 8)，以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快 速排序的結(jié)果為( (B) 3 , 2, 5, 8, 6 (A) 2 , 3, 5, 8, 6 (D) 2 , 3, 6, 5, 8 (C) 3 , 2, 5, 6, 8 二、填空題 1. 為了能有效

10、地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問題是 和 。 2. 下面程序段的功能實(shí)現(xiàn)數(shù)據(jù)x進(jìn)棧，要求在下劃線處填上正確的語句。 typedef struct int s100; int top; sqstack; void push(sqstack else ; 3. 中序遍歷二叉排序樹所得到的序列是 序列(填有序或無序)。 4. 設(shè)某棵二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為Nb，度數(shù)為1的結(jié)點(diǎn)數(shù)為N，則該二叉樹中度數(shù)為 2的結(jié)點(diǎn)數(shù)為;若采用二叉鏈表作為該二叉樹的存儲(chǔ)結(jié)構(gòu)，則該二叉樹中共 有個(gè)空指針域。 5. 設(shè)某無向圖中頂點(diǎn)數(shù)和邊數(shù)分別為n和e，所有頂點(diǎn)的度數(shù)之和為d，則e=。 6. 設(shè)一組初始記錄關(guān)鍵字序

11、列為(55，63，44, 38, 75，80，31，56)，則利用篩選法建立 的初始堆為。 7. 已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下：從頂點(diǎn) 1出發(fā)，DFS遍歷的輸出序列是 , BFS遍歷的輸出序列是 圉的鄰撞轟再諸結(jié)構(gòu) 三、應(yīng)用題 1. 設(shè)一組初始記錄關(guān)鍵字序列為(45 , 80, 48, 40, 22, 78)，則分別給出第4趟簡(jiǎn)單選擇 排序和第4趟直接插入排序后的結(jié)果。 2. 設(shè)指針變量p指向雙向鏈表中結(jié)點(diǎn)A,指針變量q指向被插入結(jié)點(diǎn) B,要求給出在結(jié)點(diǎn) A 的后面插入結(jié)點(diǎn) B的操作序列(設(shè)雙向鏈表中結(jié)點(diǎn)的兩個(gè)指針域分別為llink和rlink )。 3. 設(shè)一組有序的記錄關(guān)鍵字序列為(1

12、3 , 18, 24, 35, 47, 50, 62, 83, 90)，查找方法用 二分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長(zhǎng) 度。 4. 設(shè)一棵樹 T 中邊的集合為(A , B), (A , C), (A , D), (B, E) , (C , F) , (C , G)，要求 用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲(chǔ)結(jié)構(gòu)并將該樹轉(zhuǎn)化成對(duì)應(yīng)的二叉樹。 5. 設(shè)有無向圖G,要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。 6. 設(shè)有一組初始記錄關(guān)鍵字為(45 , 80 , 48 , 40 , 22 , 78),要求構(gòu)造一棵二叉排序樹并給 出構(gòu)造過程。 數(shù)

13、據(jù)結(jié)構(gòu)練習(xí)題(三) 、選擇題 1 設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為 A=(D, R)，D=01, 02， 03， 04, 05， 06， 07, 08, 09，R=r，r=，, ，則數(shù)據(jù)結(jié)構(gòu) A是()。 (A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu) (C)物理結(jié)構(gòu) (D)圖型結(jié)構(gòu) 2下面程序的時(shí)間復(fù)雜度為() for (i=1 , s=0; i=n ; i+ ) t=1 ; for(j=1 ; jn ext ;p-data=q-data ;p_n ext=q _n ext ;free(q); (B) q= =p-n ext ;q-data=p-data ;p_n ext=q _n ext ;free(q); (

14、C) q= =p_next ;p_n ext=q _n ext ;free(q); (D) q= =p_next ;p-data=q-data ;free(q); 4.設(shè)有 n個(gè)待排序的記錄關(guān)鍵字，貝恠堆排序中需要( )個(gè)輔助記錄單元。 (A) 1 (B) n (C) nlog 2n (D) n 2 5.設(shè)一組初始記錄關(guān)鍵字為(20, 15, 14, 18, 21, 36, 40, 10)，則以20為基準(zhǔn)的一趟快 速排序結(jié) 束后白 1 勺結(jié)果為 () 。 (A) 10 , 15, 14, 18, 20, 36, 40, 21 (B) 10 , 15, 14, 18, 20, 40, 36, 2

15、1 (C) 10 , 15, 14, 20, 18, 40, 36, 2l (D)15 , 10, 14, 18, 20, 36, 40, 21 6.設(shè)無向圖G中有n個(gè)頂點(diǎn)e條邊，則其對(duì)應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別 為()。 (A) n , e(B) e , n(C) 2n , e(D) n , 2e 7. 設(shè)某強(qiáng)連通圖中有 n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有()條邊。 (A) n(n-1)(B) n+1(C) n(D) n(n+1) int others; int hashsqsearch(struct record hashtable ,i nt k) int i,j; j=i=k

16、 % p; while (hashtablej.key!=k if (i=j) return(-1); if () return(j); else return(-1); 14. 下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k,請(qǐng)?jiān)谙聞澗€處填上正確的語句。 typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree; bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0) if (t-key=k); else if (t

17、-keyk) t=t-lchild; else; 三、計(jì)算題 1. 已知二叉樹的前序遍歷序列是AEFBGCDHIKJ中序遍歷序列是EFAGBCHKIJ，畫出此二叉 樹。 2. 已知待散列的線性表為(36, 15, 40, 63, 22),散列用的一維地址空間為0 . 6，假定 選用的散列函數(shù)是H( K) = K mod 7，若發(fā)生沖突采用線性探查法處理，試： (1 )計(jì)算出每一個(gè)元素的散列地址并在下圖中填寫出散列表： 0123456 (2 )求出在查找每一個(gè)元素概率相等情況下的平均查找長(zhǎng)度。 3. 已知序列(10, 18, 4, 3, 6, 12, 1, 9, 18, 8)請(qǐng)用快速排序?qū)懗雒恳?/p>

18、趟排序的結(jié)果。 四、算法設(shè)計(jì)題 1. 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。 2. 設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。 數(shù)據(jù)結(jié)構(gòu)練習(xí)題(四) 一、選擇題 1 設(shè)一維數(shù)組中有 n個(gè)數(shù)組元素，則讀取第i個(gè)數(shù)組元素的平均時(shí)間復(fù)雜度為()。 2 (A) 0(n)(B) 0(nlog 2n)(C) 0(1)(D) 0(n ) 2 設(shè)一棵二叉樹的深度為k，則該二叉樹中最多有()個(gè)結(jié)點(diǎn)。 kk1k (A) 2k-1(B) 2(C) 2 -(D) 2 -1 3設(shè)某無向圖中有 n個(gè)頂點(diǎn)e條邊，則該無向圖中所有頂點(diǎn)的入度之和為()。 (A) n(B) e(C) 2n(D) 2e 4. 在二叉排序樹中插

19、入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為()。 (A) 0(1)(B) 0(n)(C) O(log ?n) (D) 0(n 2) 5. 設(shè)某有向圖的鄰接表中有n個(gè)表頭結(jié)點(diǎn)和 m個(gè)表結(jié)點(diǎn)，則該圖中有()條有向邊。 (A) n(B) n-1(C) m(D) m-1 6. 設(shè)一組初始記錄關(guān)鍵字序列為(345 , 253, 674, 924, 627),則用基數(shù)排序需要進(jìn)行() 趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。 (A) 3(B) 4(C) 5(D) 8 7. 設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則退棧操作()。 (A)必須判別棧是否為滿(B)必須判別棧是否為空 (C)判別棧元素的類型(D)對(duì)棧不作任何判別 st

20、ruct node *n ext; lklist; void createlkhash(lklist *hashtable) int i,k; Iklist *s; for(i=0;im;i+); for(i=0;ikey=ai; k=ai % p; s-next=hashtablek; 三、計(jì)算題 1、下圖所示的森林： (1) 求樹(a)的先根序列和后根序列； (2) 求森林先序序列和中序序列； (3) 將此森林轉(zhuǎn)換為相應(yīng)的二叉樹； 2、設(shè)散列表的地址圍是0.9 ，散列函數(shù)為 H (key) (key 2 +2)MOD 9,并采用鏈表 處理沖突，請(qǐng)畫出元素 7、4、5、3、6、2、8、9依次

21、插入散列表的存儲(chǔ)結(jié)構(gòu)。 四、算法設(shè)計(jì)題 1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要求利用原單鏈表 中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。 2. 設(shè)計(jì)在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上交換二叉樹中所有結(jié)點(diǎn)左右子樹的算法。 3. 在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉排序樹。 數(shù)據(jù)結(jié)構(gòu)練習(xí)題(五) 一、選擇題 1 數(shù)據(jù)的最小單位是()。 (A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量 2 .設(shè)一組初始記錄關(guān)鍵字序列為(50, 40, 95, 20，15，70, 60，45)，則以增量d=4的一 趟希爾排序結(jié)束后前 4條記錄關(guān)鍵字為( )。 (A) 40 ,50,20

22、, 95(B) 15 ,40,60,20 (C) 15 ,20,40, 45(D)45 ,40,15,20 3 .設(shè)一組初始記錄關(guān)鍵字序列為(25 , 50, 15, 35 , 80 , 85 , 20 , 40 , 36 , 70)，其中含有 5個(gè)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的 結(jié)果為()。 (A) 15 , 25 , 35 , 50 , 20 , 40 , 80 , 85 , 36 , 70 (B) 15 , 25 , 35 , 50 , 80 , 20 , 85 , 40 , 70 , 36 (C) 15 , 25 , 35 , 50 , 80

23、, 85 , 20 , 36 , 40 , 70 (D) 15 , 25 , 35 , 50 , 80 , 20 , 36 , 40 , 70 , 85 4. 設(shè)一個(gè)有序的單鏈表中有n個(gè)結(jié)點(diǎn)，現(xiàn)要求插入一個(gè)新結(jié)點(diǎn)后使得單鏈表仍然保持有序， 則該操作的時(shí)間復(fù)雜度為()。 2 (A) O(log 2n)(B) 0(1)(C) O(n )(D) O(n) 5 .設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較()次。 (A) 25(B) 10(C) 7(D) 1 6 .設(shè)連通圖 G 中的邊集 E=(a , b) , (a , e) , (a , c) , (b , e) , (e ,

24、d) , (d , f) , (f , c), 則從頂點(diǎn)a出發(fā)可以得到一種深度優(yōu)先遍歷的頂點(diǎn)序列為()。 (A) abedfc(B) acfebd(C) aebdfc(D) aedfcb 7.設(shè)輸入序列是1、2、3、n ,經(jīng)過棧的作用后輸出序列的第一個(gè)元素是n ,則輸出 序列中第i個(gè)輸出元素是()。 (A) n-i (B) n-1-i (C) n+1-i (D)不能確定 i=n _1; i+) for(excha nge=0,j=0; jrj+1)temp=rj+1;rj=temp;excha nge=1; if (excha nge=0) retur n; 8. 下面程序段的功能是實(shí)現(xiàn)二分查

25、找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語句。 struct recordi nt key; int others; int bisearch(struct record r , i nt k) int low=0,mid,high=n-1; while(lowleft BST-right 六、編寫算法 int Cou ntX(LNode* HL,ElemType x) 為計(jì)數(shù)器 int i=0; LNode* p=HL;/i while(p!=NULL) if (P-data=x) i+; p=p-n ext; /while,出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù) return i; /Cou ntX 數(shù)據(jù)結(jié)

26、構(gòu)練習(xí)題（二）參考答案 、選擇題 1.D 2.B 3.C4.A5.A 6.C 7.B 8.C 、 填空題 1. 構(gòu)造一個(gè)好的 HASH函數(shù)，確定解決沖突的方法 2. stack.top+ ,stack.sstack.top=x 3. 有序 4. N0-1 , 2N0+N 5. d/2 6. (31 , 38, 54, 56, 75, 80, 55, 63) 7. (1 , 3, 4, 5, 2) , (1 , 3 , 2 , 4 , 5) 三、 應(yīng)用題 1. (22 , 40, 45, 48, 80, 78), (40, 45, 48, 80, 22, 78) 2. q-llink=p; q-

27、rlink=p-rlink; p-rlink-llink=q; p-rlink=q; 3. 2,ASL=91*1+2*2+3*4+4*2)=25/9 4. 樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)略，二叉樹略 5. E=(1 , 3) , (1 , 2) , (3 , 5) , (5 , 6) , (6 , 4) 6. 略 數(shù)據(jù)結(jié)構(gòu)練習(xí)題（三）參考答案 一、選擇題 1.B 2.B 3.A 4.A 5.A 6.D 7.C 8.B 二、填空題 1. 順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 2. 9, 501 3. 5 4. 出度，入度 5. 0 6. e=d 7. 中序 8. 7 9. 0(1) 10. i/2，2i+1 11. (

28、5 ， 16， 71， 23， 72， 94, 73) 12. (1，4，3, 2) 13. j+1， hashtablej.key=k 14. return(t) ， t=t-rchild 三、計(jì)算題 2、H(36)=36 mod 7=1; H 2(22)=(2+1) mod 7=3; .沖突 H(15)=15 mod 7=1;.沖突 Hi (15)=(1+1) mod 7=2; H(40)=40 mod 7=5; H(63)=63 mod 7=0; H(22)=22 mod 7=1;.沖突 (1)0123456 63 36 15 22 40 12113 (2) ASL=1 1 31.6 5

29、 3、(8,9,4,3,6,1),10,(12,18,18) _ (1,6,4,3),8,(9),10,12,(18,18)_ 1, (3,4,6),8,9,10,12,18,(18) 1.3, (4,6),8,9,10,12,18,18_ 1.3, 4,6,8,9,10,12,18,18 _ 四、算法設(shè)計(jì)題 1. 設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。 typedef int datatype; typedef struct node datatype data; struct node *n ext;lklist; void delredundant(lklist * for(p=he

30、ad;p!=0;p=p-n ext) for(q=p-n ext,s=q;q!=0;) if (q-data=p-data) s-n ext=q _n ext; free(q);q=s-n ext; else s=q,q=q_n ext; 2. 設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)算法。 typedef struct node datatype data; struct node *lchild,*rchild; bitree; bitree *q20; int r=0,f=0,flag=0; void preorder(bitree *bt, char x) if (bt!=0 retur

31、n; elser=(r+1)%20;qr=bt;preorder(bt-lchild,x); preorder(bt-rchild,x); void pare nt(bitree *bt,char x) int i; preorder(bt,x); break; for(i=f+1; ilchild_data=x | qi-rchild-data) if (flag=0) printf(not found xn); else if (idata); else prin tf( not pare nt); 數(shù)據(jù)結(jié)構(gòu)練習(xí)題（四）參考答案 、選擇題 1. C2. D 3. D 4. B 5. C 6

32、. A7. B 8. A 9. C 10. A 二、填空題 2 1. O(n ) , O(nlog 2n) 2. 3 k-1 3. 2 4. n/2 5. 50, 51 6. m-1, (R-F+M)%M 7. n+1-i , n-i 8. (19 , 18, 16, 20, 30, 22) 9. (16 , 18, 19, 20, 32, 22) 10. Aij=1 11. 等于 12. BDCA 13. hashtablei=O , hashtablek=s 三、計(jì)算題 1. (1) ABCDEF; BDEFCA ; (2) ABCDEFGHIJK; BDEFCAIJKHG 林轉(zhuǎn)換為相應(yīng)的

33、二叉樹; 2. H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=H(7)=6 0 1 2 3 4 5 6 7 8 9 四、算法設(shè)計(jì)題 1. 設(shè)單鏈表中有僅三類字符的數(shù)據(jù)元素（大寫字母、數(shù)字和其它字符），要求利用原單鏈表 中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。 typedef char datatype; typedef struct node datatype data; struct node *n ext;lklist; void split(lklist *head,lklist * ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) head=p-n ext; p-n ext=0; if (p-data=A ha=p; else if (p-data=0hb=p; else p-next=hc; hc=p; 2. 設(shè)計(jì)