東南大學十套數(shù)據(jù)結構試題及答案

1、數(shù)據(jù)結構試卷(一)三、計算題(每題6分，共24分)1. 在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A Ol.next,試 寫出該線性表。A 012345660507890344035720412. 請畫出下圖的鄰接矩陣和鄰接表。3. 己知一個圖的頂點集V和邊集E分別為：V二1, 2, 3, 4, 5, 6, 7;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;用克魯斯卡爾算法得到最小生成樹，試寫出在最小

2、生成樹中依次得到 的各條邊。4. 畫出向小根堆中加入數(shù)據(jù)4, 2, 5, & 3時，每加入一個數(shù)據(jù)后堆的 變化。四、閱讀算法(每題7分，共14分)1. LinkList mynote (LinkList L)/L是不帶頭結點的單鏈表的頭指針 if(L&&L->next)q二L； L=L>next； p=L；SI：while(p>next) p=p>next；S2：p >next二q； q->next=NULL；return L：請回答下列問題：(1) 說明語句S1的功能;(2) 說明語句組S2的功能；(3) 設鏈表表示的線性表為(出,

3、比，,&)，寫出算法執(zhí)行后的 返回值所表示的線性表。2. void ABC (BTNode * BT)if BT ABC (BT->left);ABC (BT->right); cout«BT->data<<，'該算法的功能是：五、算法填空(共8分)二叉搜索樹的查找一一遞歸算法：bool Find(BTreeNode* BST, ElemType& item)辻(BST二二NULL) return false; /查找失敗else if (item=BST->data) item=BST->data;/查找成功 ret

4、urn ;else if(item<BST->data) return Find (, item);else return Find (, item);/if六、編寫算法(共8分)統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。int CountX(LNode* HL, ElemType x)數(shù)據(jù)結構試卷(二)三、應用題(36分)1. 設一組初始記錄關鍵字序列為(45, 80, 48, 40, 22, 78),則分別給出 第4趟簡單選擇排序和第4趟直接插入排序后的結果。2. 設指針變量p指向雙向鏈表中結點A,指針變量q指向被插入結點B, 要求給出在結點A的后面插入結點B的操作序列(

5、設雙向鏈表中結點的 兩個指針域分別為11 ink和rlink)o3. 設一組有序的記錄關鍵字序列為(13, 18, 24, 35, 47, 50, 62, 83, 90),查找方法用二分查找，要求計算出查找關鍵字62時的比較次數(shù)并 計算出查找成功時的平均查找長度。4. 設一棵樹 T 中邊的集合為(A, B), (A, C), (A, D), (B, E), (C, F), (C, G),要求用孩子兄弟表示法(二叉鏈表)表示出該樹的存儲結構 并將該樹轉化成對應的二叉樹。5. 設有無向圖G,要求給出用普里姆算法構造最小生成樹所走過的邊的集 合。6. 設有一組初始記錄關鍵字為(45, 80, 48,

6、 40, 22, 78),要求構造一棵 二叉排序樹并給出構造過程。四、算法設計題(16分)1. 設有一組初始記錄關鍵字序列(K” K2,，KJ,要求設計一個算法能 夠在0(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的每個關鍵字均小于Ku右半部分的每個關鍵字均大于等于K,。2. 設有兩個集合A和集合B,要求設計生成集合C二AQB的算法，其中集 合A、B和C用鏈式存儲結構表示。數(shù)據(jù)結構試卷（三）二. 填空題1. 下列算法實現(xiàn)在順序散列表中查找值為X的關鍵字，請在下劃線處填 上正確的語句。struct recordint key; int others:;int hashsqsearch(

7、struct record hashtable ,int k)int i, j; j二i二k % P；while(hashtablej. key!=k&&hashtablej. flag!=0)j=() %m; if (i=j):return(-1);if ( ) return(j) ; else return(-1);2. 下列算法實現(xiàn)在二叉排序樹上查找關鍵值k,請在下劃線處填上正確的 語句。typedef struct node int key; struct node *lchild; struct node*rchiId;Jbitree;bitree *bstsearc

8、h(bitree *t, int k)if (t=0 ) return(0);else while (t!=0)if(t-key 二二k); else if (t->key>k)t二t一>lchild; else ;三、計算題(每題10分，共30分)1. 己知二叉樹的前序遍歷序列是AEFBGCDHIKJ ,中序遍歷序列是 EFAGBCHKIJD,畫出此二叉樹，并畫出它的后序線索二叉樹。2. 己知待散列的線性表為(36, 15, 40, 63, 22),散列用的一維地址空 間為0.6,假定選用的散列函數(shù)是H (K) = K mod 7,若發(fā)生沖突采用 線性探查法處理，試：(D計

9、算出每一個元素的散列地址并在下圖中填寫出散列表：'0123456(2)求出在查找每一個元素概率相等情況下的平均查找長度。3. 己知序列(10, 18, 4, 3, 6, 12, 1, 9, 18, 8)請用快速排序寫出 每一趟排序的結果。四、算法設計題(每題15分，共30分)1. 設計在單鏈表中刪除值相同的多余結點的算法。2. 設計一個求結點x在二義樹中的雙親結點算法。數(shù)據(jù)結構試卷(四)1. 設一組初始記錄關鍵字序列為(20, 18, 22, 16, 30, 19),則以20為中軸的一趟快速排序結果為o2. 設一組初始記錄關鍵字序列為(20, 18, 22, 16, 30, 19),則

10、根據(jù)這些初始關鍵字序列建成的初始堆為。3. 設某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結構，則頂點i和頂點j互為鄰接點的條件是o4. 設無向圖對應的鄰接矩陣為A,則A中第i上非0元素的個數(shù)第i列上非0元素的個數(shù)(填等于，大于或小于)。5. 設前序遍歷某二叉樹的序列為ABCD,中序遍歷該二叉樹的序列為BADC,則后序遍歷該二叉樹的序列為。6. 設散列函數(shù)H(k)=k mod p,解決沖突的方法為鏈地址法。要求在下列 算法劃線處填上正確的語句完成在散列表hashtalbe中查找關鍵字值 等于k的結點，成功時返回指向關鍵字的指針，不成功時返回標志0。 typedef struct node

11、 int key; struct node *next; lklist; void createlkhash(lklist *hashtable)int i, k; lklist *s;for(i=0;i<m;i+);for(i=0;i<n;i+)二(lklist *)malloc(sizeof(lklist); s->key二ai;k=ai % p; s->next二hashtable k.;三、計算題(每題10分，共30分)1、畫出廣義表LS=( ) , (e) , (a , (b , c , d )的頭尾鏈表存儲結 構。2、下圖所示的森林：(1) 求樹(a)的先根

12、序列和后根序列；(2) 求森林先序丿宇列和中序序列；(3) 將此森林轉換為相應的二叉樹；3、設散列表的地址范圍是0.9 ,散列函數(shù)為H (key) = (key 2+2) MOD 9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次 插入散列表的存儲結構。四、算法設計題(每題10分，共30分)1. 設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)， 要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈 表只包含同類字符。2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。3. 在鏈式存儲結構上建立一棵二叉排序樹。數(shù)據(jù)結構試卷(五)1. 下而程序段的

13、功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語 句。void bubble(int r Tn)for(i=l;i<=n-l; i+)for (exchange=O, j=0; j<； j+)if(rj>rj+1) (temp=rj+1 ;rj二temp;exchange二1；if (exchange=O) return；2. 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key; int others;int bisearch (struet record r , int k)int low二0, mid, high二n-

14、l;while(low二high)if (rmid. key=k) return(mid+1): else if ()high二mid-1;else low=mid+l:return(0);三、應用題(32分)1. 設某棵二叉樹的中序遍歷序列為DBEAC,前序遍歷序 列為ABDEC,要求給出該二叉樹的的后序遍歷序列。2. 設無向圖G (如右圖所示)，給出該圖的最小生成樹上邊的集合并計算最小生成樹各邊上的權值之和。3. 設一組初始記錄關鍵字序列為(15, 17, 18, 22, 35, 51, 60),要求計 算出成功查找時的平均查找長度。4. 設散列表的長度為8,散列函數(shù)H(k)=k mod

15、7,初始記錄關鍵字序列為 (25, 31, 8, 27, 13, 68),要求分別計算出用線性探測法和鏈地址法 作為解決沖突方法的平均查找長度。四、算法設計題(28分)1. 設計判斷兩個二叉樹是否相同的算法。2. 設計兩個有序單鏈表的合并排序算法。數(shù)據(jù)結構試卷（六）四、算法設計題（20分）1. 設計在順序有序表中實現(xiàn)二分查找的算法。2. 設計判斷二叉樹是否為二叉排序樹的算法。3. 在鏈式存儲結構上設計直接插入排序算法數(shù)據(jù)結構試卷（七）三、填空題（30分）1. 下面程序段的功能是實現(xiàn)一趟快速排序，請在下劃線處填上正確的語 句。struct record int key:datatype othe

16、rs:void quickpass （struct record r, int s, int t, int &i）int j=t; struct record x=r s: i=s;while(i<j)if (i<j)辻(i<j)while (i< j && r j. key>x. key)j=jl;ri=rj;i=i+l;wh 訂 e ()i 二 i+1;rj=ri;j=j-l;四、算法設計題（20分）1. 設計在鏈式結構上實現(xiàn)簡單選擇排序算法。2. 設計在順序存儲結構上實現(xiàn)求子串算法。3. 設計求結點在二義排序樹中層次的算法。數(shù)據(jù)結構試

17、卷(八)三、填空題(30分)1. 設一組初始記錄關鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50), 則以d=4為增量的一趟希爾排序結束后的結果為O2. 下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結點，請在下劃 線處填上正確的內容。typedef struet nodeint data;struct node *lchild;struct node*rchild;bitree;void bstinsert(bitree *&t,int k)辻(七二二。); t-da ta 二 k; t->lchild 二 t-rch 訂 d二0;elseif(t-&

18、gt;data>k)bstinsert (t->lchild, k) : else;3. 設指針變量p指向單鏈表中結點A,指針變量s指向被插入的結點X, 則在結點A的后面插入結點X需要執(zhí)行的語句序列:s->next=p->next;4. 設指針變量head指向雙向鏈表中的頭結點，指針變量p指向雙向鏈表中的第一個結點，則指針變量P和指針變量head之間的關系是P二和head二(設結點中的兩個指針域分別為11 ink和 rlink)o5. 設某棵二叉樹的中序遍歷序列為ABCD,后卜F遍歷序列為BADC,則其前序遍歷序列為O6. 完全二叉樹中第5層上最少有個結點，最多有個結點

19、。7. 設有向圖中不存在有向邊W,則其對應的鄰接矩陣A中的數(shù)組元素Ai j的值等于。8. 設一組初始記錄關鍵字序列為(49, 38, 65, 97, 76, 13, 27, 50), 則第4趟直接選擇排序結束后的結果為9. 設連通圖G中有n個頂點e條邊，則對應的最小生成樹上有條邊。10. 設有一組初始記錄關鍵字序列為(50, 16, 23, 68, 94, 70, 73),則將它們調整成初始堆只需把16與相互交換即可。四、算法設計題(20分)1. 設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。數(shù)據(jù)結構試卷（九）五、算法設計題（20

20、分）1. 設計計算二叉樹中所有結點值之和的算法。2. 設計將所有奇數(shù)移到所有偶數(shù)之前的算法。3. 設計判斷單鏈表中元素是否是遞增的算法。數(shù)據(jù)結構試卷(十)二、填空題(48分，其中最后兩小題各6分)1. 設指針變量P指向單鏈表中結點A,則刪除結點A的語句序列為：q=p->next； p->data=q-data； p->next二； feee (q):2. 數(shù)據(jù)結構從邏輯上劃分為三種基本類型：、和3. 設無向圖G中有n個頂點e條邊，則用鄰接矩陣作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為;用鄰接表作為圖的存儲結構進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度為4. 設散列

21、表的長度為8,散列函數(shù)H(k)=k% 7,用線性探測法解決沖突,則根據(jù)一組初始關鍵字序列(8, 15, 16, 22, 30, 32)構造出的散列表 的平均查找長度是o5. 設一組初始關鍵字序列為(38, 65, 97, 76, 13, 27, 10),則第3趟冒泡排序結束后的結果為o6. 設一組初始關鍵字序列為(38, 65, 97, 76, 13, 27, 10),則第3趟簡單選擇排序后的結果為o7. 設有向圖G中的有向邊的集合E=<1, 2>, <2, 3>, <1, 4>, <4, 5>,<5 , 3> , <4 , 6

22、> , <6 , 5>,則該圖的一個拓撲序列為8. 下面程序段的功能是建立二叉樹的算法，請在下劃線處填上正確的內容。typedefstructnode intdata;structnode*child; bitree ;void createbitree(bitree *&bt)scanf ( "%c ”，&ch);if (ch二二') : else bt= (bitree*)malloc(sizeof(bitree); bt->data=ch;: createbitree(bt->rchild);9. 下面程序段的功能是利用從尾

23、部插入的方法建立單鏈表的算法，請在下劃線處填上正確的內容。typedef struct node int data; struet node *next; lklist;void lklistcreate( *&head )for (i=l:i<=n;i+)p=(lklist*)malloc(sizeof(lklist);scanf(，&(p-data);p->next=0;if (i二二 1) head二q二p; else q-next二p;三、算法設計題（22分）1. 設計在鏈式存儲結構上合并排序的算法。2. 設計在二叉排序樹上查找結點X的算法。3. 設關鍵字序

24、列（姑，鮭，kA是堆，設計算法將關鍵字序列仏，,也,X）調整為堆。數(shù)據(jù)結構試卷（一）參考答案三、計算題（每題6分，共24分）'01111010110110102.鄰接矩陣：01111.線性表為：(78, 50, 40, 60, 34, 90)01110鄰接表如圖11所示:圖113. 用克魯斯卡爾算法得到的最小生成樹為：(1, 2) 3,(4, 6)4,(1,3) 5,(1, 4) 8,(2, 5) 10,(4, 7) 2034）共 14（ 4）四、讀算江龍每題7124. 見圖121. （1）查詢鏈表的尾結點（2）將第一個結點到鏈表的尾獻作為新的虜結置（3）返回的線性表為a3, an,

25、ai）2. 遞歸地后丿孚遍歷五、法填空（每空trueBST->leftBST->right六、編寫算法（8分）int CountX（LNode* HL, ElemType x） int i=0; LNode* p=HL;/i 為計數(shù)器 while（p!=NULL） if （P->data=x） i+;p二p->next;/while,出循環(huán)時i中的值即為x結點個數(shù):return i;/CountX數(shù)據(jù)結構試卷（二）參考答案三、應用題1. (22, 40, 45, 48, 80, 78), (40, 45, 48, 80, 22, 78)2. q->llink=p:

26、 q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;3. 2, ASL二91*1+2*2+3*4+4*2)二25/94. 樹的鏈式存儲結構略，二叉樹略5. E二(1, 3), (1, 2), (3, 5), (5, 6), (6, 4)6. 略四、算法設計題1. 設有一組初始記錄關鍵字序列(K】，K2,，KJ,要求設計一個算法 能夠在O(n)的時間復雜度內將線性表劃分成兩部分，其中左半部分的 每個關鍵字均小于K、，右半部分的每個關鍵字均大于等于K“void quickpass (int r, int s, int t

27、)int i=s, j=t, x=r s:while(i<j) while (i<j && rj>x) j=j-l; if (i<j) ri=rj;i=i+l;while (i<j && ri<x) i=i+l; if (i<j) rj=ri;j=j-l;ri=x;2. 設有兩個集合A和集合B,要求設計生成集合C=AAB的算法，其中集合A、B和C用鏈式存儲結構表示。typedef struet node int data; struct node *next;lklist:void intersection(lklist

28、 *ha, lklist *hb,lklist *&he)lklist *p, *q, *t;for(p=ha, hc=0;p!=0;p=p->next) for (q=hb;q!=0;q=q->next) if (q->data=p->data) break; if(q!=0) t=(lklist *)malloc(sizeof(lklist);t>data二p>data;t>next二he; hc=t;數(shù)據(jù)結構試卷(三)參考答案二. 填空題13. j+1, hashtablej. key=k14. return(t), t二t->rc

29、hild三、計算題1.2、H(36)=36 mod 7=1;乩(22)二(1+1) mod 7=2; .沖突H(15)=15 mod 7=1;-.沖突H：(22) = (2+1) mod 7=3;H, (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)01234566336152240(2) aslJ + 2 + 1 + 1 + 3=653、(8, 9, 4, 3, 6,1),10, (12, 18, 18)(1,6, 4, 3),8, (9),10,12, (18, 18)1, (3,

30、4, 6), & 9, 10, 12, 18, (18)1,3, (4, 6),8, 9, 10, 12, 18, 181,3, 4, 6, & 9, 10, 12, 18, 18四、算法設計題1. 設計在單鏈表中刪除值相同的多余結點的算法。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&head)lklist *p,*q, *s;for (p二head;p!=0;p二p->next)for (q二

31、p-next, s=q;q!二0;)if(q->data二二p->data)s->next二q->next;free (q);q二s-next;else s=q,q二q->next;2. 設計一個求結點x在二叉樹中的雙親結點算法。typedef struct nodedatatypedata; struct node*lchild, *rchild; bitree;bitree *q20; int r=0, f=0, flag=0;void preorder(bitree *bt, char x)if (bt!=0 && flag=0)if (bt

32、-data二二x) flagl; return;else r=(r+l)%20; q_r二bt; preorder(bt->lchild, x);preorder(bt->rchiId, x); void parent(bitree *bt, char x)int i;preorder(bt,x);for(i=f+l; i<=r; i+) if(qi->lchild->data二二x|qi->rchild->data) break;if (flag=0) printf("not found xn");else if (i<=r

33、) printfbt-data); else printf ("notparent");數(shù)據(jù)結構試卷（四）參考答案二、填空題1. (19, 18, 16, 20, 30, 22)2. (16, 18, 19, 20, 32, 22)3. Ai j=l4. 等于5. BDCA6. hashtable i=0, hash table k二s三、計算題1.2.(1) ABCDEF; BDEFCA； (2) ABCDEFGHIJK; BDEFCAIJKHG 林轉換為相應 的二叉樹；3. H(4)=H(5)二0, H(3)二H(6) =H(9) =2, H(8) =3, H(2)=H

34、(7) =6四、算法設計題1. 設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)，要 求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只 包含同類字符。typedef char datatype:typedef struet node datatype data; struct node *next;lklist;void split(lklist *head, lklist *&ha,lklist *&hb,lklist *&he) lklist *p; ha=O, hb=O, hc=O;for (p二head;p!=0;p二head)head

35、二p->next; p->next=0;if (p-data>二'A' && p->dataV Z)p->next=ha; ha二p;else if (p->da&& p->data< 9) p->next二hb; hb二p; else p->next二he; he二p;2. 設計在鏈式存儲結構上交換二叉樹中所有結點左右子樹的算法。typedef struct node int data; struct node *lchild, *rchild; bitree;void swapbit

36、ree(bitree *bt)bitree *p;if(bt二二0) return;swapbitree(bt->lchiId); swapbitree(bt->rchild); p=bt->lchild; bt->lchild=bt->rch訂d; bt->rchild二p;3. 在鏈式存儲結構上建立一棵二叉排序樹。#define n 10typedefstruetnodeint key;structnode*lchild, *rchild;bitree;void bstinsert(bitree *&bt, int key)if(bt二二0) b

37、t=(bitree*)malloc(sizeof(bitree);bt->key=key;bt->lchiId二bt->rchiId二0;else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild, key);void createbsttree(bitree *&bt)int i;for(i=l;i<=n;i+) bstinsert(bt, random(100);數(shù)據(jù)結構試卷(五)參考答案二、填空題1. n-i, rEj+l=rj2. mid二(

38、low+high)/2, r mid. key>k三、應用題2. DEBCA3. E二(1,5), (5,2), (5, 3), (3, 4),W=104. ASL二(l*l+2*2+3*4)/7二17/75. ASLI二7/6, ASL2二4/3四、算法設計題1. 設計判斷兩個二叉樹是否相同的算法。typedefstructnode datatype data; struct node*lchild, *rchild; bitree;int judgebitree (bitree *bt1,bitree *bt2)辻(btl=0 && bt2=0) return(1);

39、else if (btlO bt2二二0 btl->data! =bt2->data) return(0): elsereturn(judgebitree(btl->lchild, bt2->lchild)*judgebitree (btl->rc hi Id, bt2>rchild);2. 設計兩個有序單鏈表的合并排序算法。void mergelklist(lklist *ha,lklist *hb, lklist *&he)lklist *s二hc=0;while(ha!=0 && hb!=0)if(ha->data<

40、hb->data)if(sO) he二s二ha; else s-next二ha;s=ha;ha=ha->next;elseif(s二二0)he二s二hb;elses->next二hb;s=hb;hb二hb->next;if (ha二二0) s->next=hb; else s->next二ha;數(shù)據(jù)結構試卷(六)參考答案四、算法設計題1. 設計在順序有序表中實現(xiàn)二分查找的算法。struct record int key; int others:int bisearch(struct record r , int k)int low二0, mid, high二

41、nT ;while(low二high)mid二(low+high)/2;if(rmid key二二k) return(mid+l); else if(rmid key>k) high二mid-1; else low=mid+l;return (0);2. 設計判斷二叉樹是否為二叉排序樹的算法。int minnum二-32768, flag二1;typedef struct nodeint key; struct node *lchild, *rchild;bitree;void inorder (bitree *bt)if (bt!二0)inorder(bt->lchild); i

42、f(minnum>bt->key)flag=0;minnum二bt-key;inorder(bt->rchild);3. 在鏈式存儲結構上設計直接插入排序算法void straightinsertsort(lklist *&head)lklist *s,*p, *q； int t;if (head二二0head-next二二0) return;else for (q=head, p二head-next;p!二0;p二q-next)for(s二head;s!=q->next;s二s-next)if (s->data>p->data)break;i

43、f (s二二q-next)q二p;elseq-next二p->next;p->next二s-next;s-next二p;t=p->data;p->data二s->data;s->data二t;數(shù)據(jù)結構試卷（七）參考答案三. 填空題1. ij && ri key<x .key, r i =x四、算法設計題1. 設計在鏈式結構上實現(xiàn)簡單選擇排序算法。void simpleselectsorlklist(lklist *&head)lklist *p,*s; int min, t;if (head二二0head->next=0)

44、 return;for (q二head; q!二0;q二q->next)min=q->clata; s二q;for (p二q-next;p!=0;p二p->next)if(min>p->data)min=p->data; s二p;if(s!二q)t二s-data; s-data二q-data; q->data=t;2. 設計在順序存儲結構上實現(xiàn)求子串算法。void substring (char s , long start, long count, char t)long i,j,length=strlen(s):if (start<l sta

45、rt>length) printf(/'The copy position is wrong，z);else if (start+count-l>length) printf ("Too characters to be copied");else for (istart-l, j=0; i<s tart+cou ntT ; i+, j+) t j二 si; tj= '0' ;3. 設計求結點在二叉排序樹中層次的算法。int lev二0;typedefstructnode int key;structnode*lchild,*rch

46、ild;Jbitree:void level(bitree *bt, int x)if (bt!=0)lev+； if(bt-key二=x)return; else if (bt->key>x)level(bt>lchiId, x) ; else level (bt->rchild, x);數(shù)據(jù)結構試卷(八)參考答案三、填空題1. (49, 13, 27, 50, 76, 38, 65, 97)2. t二(bitree *)malloc(sizeof(bitree)，bstinsert(t->rchild, k)3. p->nex t二s4. head>

47、;rlink, p->11 ink5. CABD6. 1, 167. 08. (13, 27, 38, 50, 76, 49, 65, 97)9. nl10. 50四、算法設計題1. 設計一個在鏈式存儲結構上統(tǒng)計二叉樹中結點個數(shù)的算法。void countnode (bitree *bt，int &count)if (bt!=0)count+;countnode (bt->lchild, count);countnode (bt->rchild, count);2. 設計一個算法將無向圖的鄰接矩陣轉為對應鄰接表的算法。typedef struct int vertex

48、m; int edgemm;gadjmatrix;typedef struct nodelint info;int adjvertex; struct nodel*nextare;glinklistnode;typedef struct node2intvertexinfo;glinklistnode*f irstarc;glinkheadnode;void adjmatzrixtoadjlist (gadjmatrix gl , glinkheadnode g2)int i, j; glinklistnode *p;for(i二0;i<=n-l;i+) g2i firstare二0;for (i=0;i<=nl;i+) for(j=0;j<=nl;j+)if (gl. edgeij j=l)p二(glinklistnode*)mal