數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案——嚴(yán)蔚敏課后習(xí)題答案

1、第一章 緒論選擇題 1.組成數(shù)據(jù)的基本單位是（ ） （a）數(shù)據(jù)項（b）數(shù)據(jù)類型（c）數(shù)據(jù)元素（d）數(shù)據(jù)變量 2.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（ ）以及它們之間的相互關(guān)系。 （a）理想結(jié)構(gòu)，物理結(jié)構(gòu) （b）理想結(jié)構(gòu)，抽象結(jié)構(gòu) （c）物理結(jié)構(gòu)，邏輯結(jié)構(gòu) （d）抽象結(jié)構(gòu)，邏輯結(jié)構(gòu) 3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ） （a）動態(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) 4.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的 （）以及它們之間的（）和運算等的學(xué)科。 （a）數(shù)據(jù)元素（b）計算方法（c）邏輯存儲（d）數(shù)據(jù)映像 （a）結(jié)構(gòu) （b）

2、關(guān)系 （c）運算 （d）算法 5.算法分析的目的是（）。 （a） 找出數(shù)據(jù)結(jié)構(gòu)的合理性 （b）研究算法中的輸入和輸出的關(guān)系 （c）分析算法的效率以求改進（d）分析算法的易懂性和文檔性 6.計算機算法指的是（）,它必須具備輸入、輸出和（）等5個特性。 （a）計算方法（b）排序方法（c）解決問題的有限運算序列（d）調(diào)度方法 （a）可執(zhí)行性、可移植性和可擴充性（b）可行性、確定性和有窮性 （c）確定性、有窮性和穩(wěn)定性 （d）易讀性、穩(wěn)定性和安全性 二、判斷題 1.數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。（ ） 2.算法就是程序。（ ） 3.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（ ） 4.算法的五個特性為：有窮性、輸

3、入、輸出、完成性和確定性。（ ） 5.算法的時間復(fù)雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（ ） 三、填空題 1.數(shù)據(jù)邏輯結(jié)構(gòu)包括_、_、_ 和_四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_。 2.在線性結(jié)構(gòu)中,第一個結(jié)點_前驅(qū)結(jié)點,其余每個結(jié)點有且只有_個前驅(qū)結(jié)點；最后一個結(jié)點_后續(xù)結(jié)點,其余每個結(jié)點有且只有_個后續(xù)結(jié)點。 3.在樹形結(jié)構(gòu)中,樹根結(jié)點沒有_結(jié)點,其余每個結(jié)點有且只有_個前驅(qū)結(jié)點；葉子結(jié)點沒有_結(jié)點,其余每個結(jié)點的后續(xù)結(jié)點可以_。 4.在圖形結(jié)構(gòu)中,每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以_。 5.線性結(jié)構(gòu)中元素之間存在_關(guān)系,樹形結(jié)構(gòu)中元素之間存在_關(guān)系,圖形結(jié)構(gòu)中元素之間存在_關(guān)系

4、。6.算法的五個重要特性是_、_、_、_、_。 7.數(shù)據(jù)結(jié)構(gòu)的三要素是指_、_和_。 8.鏈?zhǔn)酱鎯Y(jié)構(gòu)與順序存儲結(jié)構(gòu)相比較,主要優(yōu)點是_。 9.設(shè)有一批數(shù)據(jù)元素,為了最快的存儲某元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu),為了方便插入一個元素,數(shù)據(jù)結(jié)構(gòu)宜用_結(jié)構(gòu)。 四、算法分析題 1.求下列算法段的語句頻度及時間復(fù)雜度 參考答案：選擇題1. c 2.c 3. c 4. a、b 5. c 6.c、b二、判斷題:1、 2、 3、 4、 5、三、填空題1、線性、樹形、圖形、集合 ；非線性（網(wǎng)狀） 2、沒有；1；沒有；1 3、前驅(qū)；1；后繼；任意多個 4、任意多個 5、一對一；一對多；多對多6、有窮性；確定性；可行性；

5、輸入；輸出 7、數(shù)據(jù)元素；邏輯結(jié)構(gòu)；存儲結(jié)構(gòu) 8、插入、刪除、合并等操作較方便 9、順序存儲；鏈?zhǔn)酱鎯?四、算法分析題for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;分析：該算法為一個二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因些，時間頻度t(n)=1+2+3+n=n*(n+1)/2有 1/4t(n)/n21，故它的時間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級相同。 2、分析下列算法段的時間頻度及時間復(fù)雜度 for （i=1;i=n;i+） for (j=1;j=i;j+) for ( k=1;knext=p;p-next

6、=s; （b） s-next=p-next;p-next=s;（c）s-next=p-next;p=s; （d）p-next=s;s-next=p;5.在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行（ ） （a）p-next=p-next-next; （b）p=p-next; p-next=p-next-next;（c）p-next=p-next; （d）p =p-next-next;6.下列有關(guān)線性表的敘述中，正確的是（ ） （a）線性表中的元素之間隔是線性關(guān)系 （b）線性表中至少有一個元素 （c）線性表中任何一個元素有且僅有一個直接前趨 （d）線性表中任何一個元素有且僅有一個直接后繼

7、7.線性表是具有n個（ ）的有限序列（n0)（a）表元素 （b）字符 （c）數(shù)據(jù)元素 （d）數(shù)據(jù)項 二、判斷題 1.線性表的鏈接存儲，表中元素的邏輯順序與物理順序一定相同。（ ） 2.如果沒有提供指針類型的語言，就無法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。（ ） 3.線性結(jié)構(gòu)的特點是只有一個結(jié)點沒有前驅(qū)，只有一個結(jié)點沒有后繼，其余的結(jié)點只有一個前驅(qū)和后繼。（ ） 4.語句p=p-next完成了指針賦值并使p指針得到了p指針?biāo)负罄^結(jié)點的數(shù)據(jù)域值。（ ） 5.要想刪除p指針的后繼結(jié)點，我們應(yīng)該執(zhí)行q=p-next ； p-next=q-next； free(q)。（ ） 三、填空題 1.已知p為單鏈表中的非首尾結(jié)點，在

8、p結(jié)點后插入s結(jié)點的語句為：_ 。2.順序表中邏輯上相鄰的元素物理位置( )相鄰， 單鏈表中邏輯上相鄰的元素物理位置_相鄰。 3.線性表l（a1，a2，.，an）采用順序存儲，假定在不同的n1個位置上插入的概率相同，則插入一個新元素平均需要移動的元素個數(shù)是_ 4.在非空雙向循環(huán)鏈表中，在結(jié)點q的前面插入結(jié)點p的過程如下： p-prior=q-prior;q-prior-next=p;p-next=q;_; 5.已知l是無表頭結(jié)點的單鏈表，是從下列提供的答案中選擇合適的語句序列，分別實現(xiàn)： （1）表尾插入s結(jié)點的語句序列是_(2) 表尾插入 s結(jié)點的語句序列是_p-next=s; p=l; l=

9、s; p-next=s-next; s-next=p-next; s-next=l; s-next=null; while(p-next!= q) p=p-next; while(p-next!=null) p=p-next; 四、算法設(shè)計題 1.試編寫一個求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。 2.已知帶有頭結(jié)點的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結(jié)點的c函數(shù)。 3.某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構(gòu)成一個循環(huán)鏈表，每個結(jié)點有價格、數(shù)量和鏈指針三個域?，F(xiàn)出庫（銷售）m臺價格為h的電視機，試編寫算法修改原鏈表。 4.某百貨公

10、司倉庫中有一批電視機，按其價格從低到高的次序構(gòu)成一個循環(huán)鏈表，每個結(jié)點有價格、數(shù)量和鏈指針三個域?，F(xiàn)新到m臺價格為h的電視機，試編寫算法修改原鏈表。 5.線性表中的元素值按遞增有序排列，針對順序表和循環(huán)鏈表兩種不同的存儲方式，分別編寫c函數(shù)刪除線性表中值介于a與b（ab）之間的元素。 6.設(shè)a=(a0,a1,a2,.,an-1),b=(b0,b1,b2,.,bm-1)是兩個給定的線性表,它們的結(jié)點個數(shù)分別是n和m,且結(jié)點值均是整數(shù)。 若n=m，且 ai= bi （0in ），則a=b； 若nm ，且ai=bi （0in ），則ab； 若存在一個j， jm ，jn ，且ai=bi （0ij ），

11、 若ajbj，則ab。 試編寫一個比較a和b的c函數(shù)，該函數(shù)返回 -1或 0或 1，分別表示 ab。 7.試編寫算法,刪除雙向循環(huán)鏈表中第k個結(jié)點。 8.線性表由前后兩部分性質(zhì)不同的元素組成(a0,a1,.,an-1,b0,b1,.,bm-1),m和n為兩部分元素的個數(shù),若線性表分別采用數(shù)組和鏈表兩種方式存儲,編寫算法將兩部分元素?fù)Q位成(b0,b1,.,bm-1,a0,a1,.,an-1),分析兩種存儲方式下算法的時間和空間復(fù)雜度。 9.用循環(huán)鏈表作線性表(a0,a1,.,an-1)和（b0,b1,.,bm-1）的存儲結(jié)構(gòu),頭指針分別為ah和bh，設(shè)計c函數(shù)，把兩個線性表合并成形如（a0,b0

12、,a1,b1,）的線性表，要求不開辟新的動態(tài)空間,利用原來循環(huán)鏈表的結(jié)點完成合并操作,結(jié)構(gòu)仍為循環(huán)鏈表,頭指針為head,并分析算法的時間復(fù)雜度。 10.試寫出將一個線性表分解為兩個帶有頭結(jié)點的循環(huán)鏈表，并將兩個循環(huán)鏈表的長度放在各自的頭結(jié)點的數(shù)據(jù)域中的c函數(shù)。其中,線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個循環(huán)鏈表中。 11.試寫出把線性鏈表改為循環(huán)鏈表的c函數(shù)。 12.己知非空線性鏈表中x結(jié)點的直接前驅(qū)結(jié)點為y,試寫出刪除x結(jié)點的c函數(shù)。 參考答案： 一、選擇題1. b 2.c 3. d 4. b 5. a 6.a 7、c二、判斷題參考答案：1、2、3、4

13、、5、三、填空題1、s-next=p-next; p-next=s; 2、一定；不一定 3、n/2 4、q-prior=p; 5、(1)6) 3)(2) 2) 9）1) 7)四、算法設(shè)計題1、#include stdio.h#include malloc.htypedef struct nodeint data; struct node *link;node;int aver(node *head)int i=0,sum=0,ave; node *p; p=head;while(p!=null)p=p-link;+i;sum=sum+p-data;ave=sum/i;return (ave);

14、2、#include stdio.h#include malloc.htypedef struct nodeint data; /* 假設(shè)數(shù)據(jù)域為整型 */struct node *link;node;void del_link(node *head,int x) /* 刪除數(shù)據(jù)域為x的結(jié)點*/node *p,*q,*s;p=head;q=head-link;while(q!=head)if(q-data=x)p-link=q-link;s=q;q=q-link;free(s); elsep=q;q=q-link;3、void del(node *head,float price,int nu

15、m)node *p,*q,*s;p=head;q=head-next;while(q-pricenext;if(q-price=price)q-num=q-num-num;else printf(無此產(chǎn)品);if(q-num=0)p-next=q-next;free(q);4、#include stdio.h#include malloc.htypedef struct nodefloat price;int num;struct node *next;node;void ins(node *head,float price,int num)node *p,*q,*s;p=head;q=hea

16、d-next;while(q-pricenext;if(q-price=price)q-num=q-num+num;elses=(node *)malloc(sizeof(node);s-price=price;s-num=num;s-next=p-next;p-next=s;5、順序表： 算法思想：從0開始掃描線性表，用k記錄下元素值在a與b之間的元素個數(shù)，對于不滿足該條件的元素，前移k個位置，最后修改線性表的長度。 void del（elemtype list，int *n，elemtype a，elemtype b） int i=0，k=0； while（i=a&listilink; /

17、* 假設(shè)循環(huán)鏈表帶有頭結(jié)點 */while(q!=head & q-datalink;while(q!=head & q-datalink;free(r); if(p!=q)p-link=q;6、#define maxsize 100int listamaxsize,listbmaxsize;int n,m;int compare(int a,int b)int i=0;while(ai=bi&in&im)i+;if(n=m&i=n) return(0);if(nm&i=m) return(1);if(in&im)if(aibi) return(1);7、void del(dunode*hea

18、d,int i)dunode *p;if(i=0)*head=*head-next;*head-prior=null;return(0); elsefor(j=0;jnext;if(p=null|ji) return(1);p-prior-next=p-next;p-next-prior=p-proir;free(p);return(0);8.順序存儲:void convert(elemtype list,int l,int h) /* 將數(shù)組中第l個到第h個元素逆置*/int i;elemtype temp;for(i=h;i=(l+h)/2;i+)temp=listi;listi=list

19、l+h-i;listl+h-i=temp;void exchange(elemtype list,int n,int m);convert(list,0,n+m-1);convert(list,0,m-1);convert(list,m,n+m-1);該算法的時間復(fù)雜度為o(n+m),空間復(fù)雜度為o(1)鏈接存儲:(不帶頭結(jié)點的單鏈表)typedef struct nodeelemtype data;struct node *link;node;void convert(node *head,int n,int m)node *p,*q,*r;int i;p=*head;q=*head;for

20、(i=0;ilink; /*q指向an-1結(jié)點 */r=q-link;q-link=null; while(r-link!=null)r=r-link; /*r指向最后一個bm-1結(jié)點 */*head=q;r-link=p; 該算法的時間復(fù)雜度為o(n+m),但比順序存儲節(jié)省時間(不需要移動元素,只需改變指針),空間復(fù)雜度為o(1)9.typedef struct nodeelemtype data;struct node *link;node;node*union(node*ah,node *bh)node*a,*b,*head,*r,*q;head=ah;a=ah;b=bh;while(a

21、-link!=ah&b-link!=bh)r=a-link;q=b-link;a-link=b;b-link=r;a=r;b=q;if(a-link=ah) /*a的結(jié)點個數(shù)小于等于b的結(jié)點個數(shù) */a-link=b;while(b-link!=bh)b=b-link;b-link=head;if(b-link=bh) /*b的結(jié)點個數(shù)小于a的結(jié)點個數(shù) */ r=a-link;a-link=b;b-link=r;return(head);該算法的時間復(fù)雜度為o(n+m),其中n和m為兩個循環(huán)鏈表的結(jié)點個數(shù).10. typedef struct nodeelemtype data;struct

22、node *link;node;void analyze(node *a） node*rh，*qh，*r,*q,*p； int i=0，j=0；/*i為序號是奇數(shù)的結(jié)點個數(shù) j為序號是偶數(shù)的結(jié)點個數(shù) */p=a； rh=（node *）malloc（sizeof（node）；/*rh為序號是奇數(shù)的鏈表頭指針 */qh=(node *)malloc(sizeof(node); /*qh為序號是偶數(shù)的鏈表頭指針 */r=rh;q=qh;while(p!=null)r-link=p;r=p;i+;p=p-link;if(p!=null)q-link=p;q=p;j+;p=p-link;rh-data

23、=i;r-link=rh;qh-data=j; q-link=qh; 11.typedef struct nodeelemtype data;struct node *link;node;void change(node*head)node*p;p=head; if(head!=null)while(p-link!=null)p=p-link;p-link=head;12.typedef struct nodeelemtype data;struct node *link;node;void del(node *x,node *y)node *p,*q;elemtype d1; p=y;q=x

24、;while(q-next!=null) /* 把后一個結(jié)點數(shù)據(jù)域前移到前一個結(jié)點*/ p-data=q-data;q=q-link;p=q;p-link=null; /* 刪除最后一個結(jié)點*/free(q);第三章 棧和隊列一、選擇題 1. 一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（ ）。（a） edcba（b）decba（c）dceab （d）abcde 2.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（ ）。（a） 線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu)（b）散列方式和索引方式（c）鏈表存儲結(jié)構(gòu)和數(shù)組 （d）線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)3.判定一個棧st(最多元素為m0)為空的條件是（ ）。

25、（a） st-top!=0 （b）st-top=0 （c）st-top!=m0 （d）st-top=m04.判定一個棧st(最多元素為m0)為棧滿的條件是（ ）。（a）st-top!=0 （b）st-top=0 （c）st-top!=m0-1（d）st-top=m0-15.一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是（ ）。（a）4,3,2,1（b）1,2,3,4（c）1,4,3,2（d）3,2,4,16.循環(huán)隊列用數(shù)組a0,m-1存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊列中的元素個數(shù)是（ ）（a）(rear-front+m)%m （b） rear-front+

26、1 （c）rear-front-1（d）rear-front7.棧和隊列的共同點是（ ）（a） 都是先進后出 （b）都是先進先出（c）只允許在端點處插入和刪除元素（d）沒有共同點8.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）。（a）abcd*+-（b）abc+*d- （c）abc*+d-（d）-+*abcd9.4個元素a1，a2，a3和a4依次通過一個棧，在a4進棧前，棧的狀態(tài)，則不可能的出棧序是（）(a)a4，a3，a2，a1(b)a3，a2，a4，a1 (c)a3，a1，a4，a2(d)a3，a4，a2，a110.以數(shù)組q0.m1存放循環(huán)隊列中的元素，變量rear和qulen分別指示循環(huán)

27、隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù)，隊列第一個元素的實際位置是（）(a)rearqulen(b)rearqulenm(c)mqulen (d)1（rearmqulen）% m二、填空題1.棧的特點是_,隊列的特點是_。2.線性表、棧和隊列都是_結(jié)構(gòu),可以在線性表的_位置插入和刪除元素，對于棧只能在_插入和刪除元素，對于隊列只能在_插入元素和_刪除元素。3.一個棧的輸入序列是12345,則棧有輸出序列12345是_。(正確/錯誤)4.設(shè)棧s和隊列q的初始狀態(tài)皆為空，元素a1，a2，a3，a4，a5和a6依次通過一個棧，一個元素出棧后即進入隊列q，若6個元素出隊列的順序是a3，a5，a

28、4，a6，a2，a1則棧s至少應(yīng)該容納_個元素。三、算法設(shè)計題 1.假設(shè)有兩個棧s1和s2共享一個數(shù)組stackm,其中一個棧底設(shè)在stack0處，另一個棧底設(shè)在stackm-1處。試編寫對任一棧作進棧和出棧運算的c函數(shù)push（x,i)和pop(i),i=l,2。其中i=1表示左邊的棧，,i=2表示右邊的棧。要求在整個數(shù)組元素都被占用時才產(chǎn)生溢出。2.利用兩個棧s1,s2模擬一個隊列時,如何用棧的運算來實現(xiàn)該隊列的運算?寫出模擬隊列的插入和刪除的c函數(shù)。 一個棧s1用于插入元素,另一個棧s2用于刪除元素.參考答案：一、選擇題1. c 2.a 3. b 4. b 5. b 6.b 7、c 8、

29、c 9、c 10、d 二、填空題1、先進先出；先進后出2、線性 ； 任何 ；棧頂；隊尾；對頭3、正確的 4、3三、算法設(shè)計題1.#define m 100elemtype stackm;int top1=0,top2=m-1;int push(elemtype x,int i)if(top1-top2=1) return(1); /*上溢處理*/elseif(i=1) stacktop1+=x;if(i=2)stacktop2-=x;return(0); int pop(elemtype *px,int i)if(i=1)if(top1=0) return(1);else top1-;*px=

30、stacktop1;return(0);elseif(i=2)if(top2=m-1) return(1);elsetop2+;*px=stacktop2;return(0);2.elemtype s1maxsize,s2mazsize;int top1,top2;void enqueue(elemtype x)if(top1=maxsize) return(1);elsepush(s1,x);return(0);void dequeue(elemtype *px)elemtype x;top2=0;while(!empty(s1)pop(s1,&x);push(s2,x);pop(s2,&x

31、);while(!empty(s2)pop(s2,&x);push(s1,x);第四章 串 一、選擇題 1.下列關(guān)于串的敘述中，正確的是（ ）(a)一個串的字符個數(shù)即該串的長度 (b)一個串的長度至少是1(c)空串是由一個空格字符組成的串 (d)兩個串s1和s2若長度相同，則這兩個串相等2.字符串a(chǎn)baaabab的nextval值為(? )(a)(0,1,01,1,0,4,1,0,1) (b)(0,1,0,0,0,0,2,1,0,1)(c)(0,1,0,1,0,0,0，1,1) (d)(0,1,0,1,0,1,0,1,1)3.字符串滿足下式,其中head和tail的定義同廣義表類似,如head

32、(xyz)= x,tail(xyz)= yz,則s=( )。 concat(head(tail(s),head(tail(tail(s)= dc。(a)abcd (b)acbd (c)acdb (d)adcb4.串是一種特殊的線性表,其特殊性表現(xiàn)在（ ）(a)可以順序存儲 (b)數(shù)據(jù)元素是一個字符(c)可以鏈?zhǔn)酱鎯?(d)數(shù)據(jù)元素可以是多個字符5設(shè)串s1=abcdefg,s2=pqrst,函數(shù)concat（x，y）返回x和y串的連接串，substr（s，i，j）返回串s從序號i開始的j個字符組成的字串，length（s）返回串s的長度，則concat（substr（s1，2，length（s2

33、），substr（s1，length（s2），2）的結(jié)果串是（ ）（a）bcdef (b) bcdefg (c)bcpqrst (d)bcdefef 二、算法設(shè)計 1.分別在順序存儲和一般鏈接存儲兩種方式下,用c語言寫出實現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy(s1,s2)。2.在一般鏈接存儲(一個結(jié)點存放一個字符)方式下,寫出采用簡單算法實現(xiàn)串的模式匹配的c語言函數(shù)int l_index(t,p)。參考答案：一、選擇題 1. a 2.b 3. d 4. d 5. d 二、算法設(shè)計 1.順序存儲： #include string.h#define maxn 100char smaxn;

34、int s_strlen(char s)int i;for(i=0;si!=0;i+);return(i);void s_strcpy(char s1,char s2) /4.3題int i;for(i=0;s1i!=0;i+)s2i=s1i;s2i=0;一般鏈接存儲： #include stdio.htypedef struct nodechar data;struct node *link;node;node *l_strcpy(node *s1) node *s2,*t1,*t2,*s;if(s1=null) return(null);elset1=s1;t2=(node *)mallo

35、c(sizeof(node);s2=t2;while(t1!=null)s=(node *)malloc(sizeof(node);s-data=t1-data;t2-link=s;t2=s;t1=t1-link;t2-link=null;s=s2;s2=s2-link;free(s);return(s2); 2.#include stdio.htypedef struct nodechar data;struct node *link;node;int l_index(node *t,node *p) node *t1,*p1,*t2;?int i;t1=t;i=1;while(t1!=nu

36、ll)p1=p;t2=t1-link;while(p1-data=t1-data&p1!=null) p1=p1-link;t1=t1-link;if(p1=null) return(i);i+;t1=t2;return(0);第五章 數(shù)組和廣義表一、選擇題 1. 常對數(shù)組進行的兩種基本操作是（ ）（a）建立與刪除（b）索引和修改（c）查找和修改（d）查找與索引2.二維數(shù)組m的元素是4個字符(每個字符占一個存儲單元)組成的串,行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,m按行存儲時元素m35的起始地址與m按列存儲時元素( ) 的起始地址相同。（a）m24（b）m34（c）m35（d）m44

37、3.數(shù)組a810中,每個元素a的長度為3個字節(jié),從首地址sa開始連續(xù)存放在存儲器內(nèi),存放該數(shù)組至少需要的單元數(shù)是（ ）。（a）80（b）100（c）240（d）2704.數(shù)組a810中,每個元素a的長度為3個字節(jié),從首地址sa開始連續(xù)存放在存儲器內(nèi),該數(shù)組按行存放時,元素a74的起始地址為（ ）。（a）sa+141（b）sa+144（c）sa+222（d）sa+2255.數(shù)組a810中,每個元素a的長度為3個字節(jié),從首地址sa開始連續(xù)存放在存儲器內(nèi),該數(shù)組按列存放時,元素a47的起始地址為（ ）。（a）sa+141（b）sa+180（c）sa+222（d）sa+2256.稀疏矩陣一般的壓縮存儲

38、方法有兩種,即（ ）。（a） 二維數(shù)組和三維數(shù)組（b）三元組和散列（c）三元組和十字鏈表 （d）散列和十字鏈表7.若采用三元組壓縮技術(shù)存儲稀疏矩陣,只要把每個元素的行下標(biāo)和列下標(biāo)互換,就完成了對該矩陣的轉(zhuǎn)置運算,這種觀點（ ）。（a）正確（b）錯誤8.設(shè)矩陣a是一個對稱矩陣,為了節(jié)省存儲,將其下三角部分按行序存放在一維數(shù)組b1,n(n-1)/2中,對下三角部分中任一元素ai,j(i=j),在一組數(shù)組b的下標(biāo)位置k的值是（ ）。（a）i(i-1)/2+j-1（b）i(i-1)/2+j（c）i(i+1)/2+j-1 (d)i(i+1)/2+j二、填空題 1.己知二維數(shù)組amn采用行序為主方式存儲,

39、每個元素占k個存儲單元,并且第一個元素的存儲地址是loc(a00),則a00的地址是_。2.二維數(shù)組a1020采用列序為主方式存儲,每個元素占一個存儲單元,并且a00的存儲地址是200,則a612的地址是_。3.有一個10階對稱矩陣a,采用壓縮存儲方式(以行序為主,且a00=1),則a85的地址是_。4.設(shè)n行n列的下三角矩陣a已壓縮到一維數(shù)組s1.n*(n+1)/2中,若按行序為主存儲,則aij對應(yīng)的s中的存儲位置是_。5.若a是按列序為主序進行存儲的46的二維數(shù)組,其每個元素占用3個存儲單元,并且a00的存儲地址為1000,元素a13的存儲地址為_,該數(shù)組共占用_個存儲單元。三、算法設(shè)計

40、1.如果矩陣a中存在這樣的一個元素aij滿足條件:aij是第i行中值最小的元素,且又是第j列中值最大的元素,則稱之為該矩陣的一個馬鞍點。編寫一個函數(shù)計算出1n的矩陣a的所有馬鞍點。2.n只猴子要選大王,選舉辦法如下:所有猴子按1,2,.,n編號圍坐一圈,從1號開始按1、2、.、m報數(shù),凡報m號的退出到圈外,如此循環(huán)報數(shù),直到圈內(nèi)剩下只猴子時,這只猴子就是大王。n和m由鍵盤輸入,打印出最后剩下的猴子號。編寫一程序?qū)崿F(xiàn)上述函數(shù)。3.數(shù)組和廣義表的算法驗證程序編寫下列程序:(1)求廣義表表頭和表尾的函數(shù)head()和tail()。(2)計算廣義表原子結(jié)點個數(shù)的函數(shù)count_gl()。(3)計算廣義

41、表所有原子結(jié)點數(shù)據(jù)域(設(shè)數(shù)據(jù)域為整型之和的函數(shù)sum_gl()。 參考答案：一、選擇題1. c 2.b 3. c 4. c 5. b 6.c 7、b 8、b 二、填空題1、loc(a00)+(n*i+j)*k 2、332 3、42 4、i*(i+1)/2+j+1 5、1039；72 三、算法設(shè)計題1.算法思想：依題意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,則該元素aij便是馬鞍點,找出所有這樣的元素,即找到了所有馬鞍點。因此,實現(xiàn)本題功能的程序如下:#include #define m 3#define n

42、4void minmax(int amn)int i1,j,have=0;int minm,maxn;for(i1=0;i1m;i1+)/*計算出每行的最小值元素,放入minm之中*/mini1=ai10;for(j=1;jn;j+)if(ai1jmini1) mini1=ai1j;for(j=0;jn;j+)/*計算出每列的最大值元素,放入maxn之中*/maxj=a0j;for(i1=1;i1max j) maxj=ai1j;for(i1=0;i1m;i1+)for(j=0;j=m*/for(j=0;jn;j+)aj=j+1;count=0;d=0;while(dn)for(j=0;jta

43、g=1;h-dd.sublist=creat_gl(s);elseh-tag=0;h-dd.data=ch;elseh=null;ch=*(*s);(*s)+;if(h!=null)if(ch=,)h-link =creat_gl(s);elseh-link=null;return(h);void prn_gl(node *p)if(p!=null)if(p-tag=1)printf();if(p-dd.sublist =null)printf( );elseprn_gl(p-dd.sublist );elseprintf(%c,p-dd.data);if(p-tag=1)printf();i

44、f(p-link!=null)printf(,);prn_gl(p-link);node *copy_gl(node *p)node *q;if(p=null) return(null);q=(node *)malloc(sizeof(node);q-tag=p-tag;if(p-tag)q-dd.sublist =copy_gl(p-dd.sublist );elseq-dd.data =p-dd.data;q-link=copy_gl(p-link);return(q);node *head(node *p) /*求表頭函數(shù) */return(p-dd.sublist); node *ta

45、il(node *p) /*求表尾函數(shù) */return(p-link);int sum(node *p) /*求原子結(jié)點的數(shù)據(jù)域之和函數(shù) */ int m,n;if(p=null) return(0);else if(p-tag=0) n=p-dd.data;else n=sum(p-dd.sublist);if(p-link!=null)m=sum(p-link);else m=0;return(n+m);int depth(node *p) /*求表的深度函數(shù) */int h,maxdh;node *q;if(p-tag=0) return(0);else if(p-tag=1&p-dd

46、.sublist=null) return 1;elsemaxdh=0;while(p!=null)if(p-tag=0) h=0;elseq=p-dd.sublist;h=depth(q);if(hmaxdh)maxdh=h;p=p-link;return(maxdh+1);main()node *hd,*hc;char s100,*p;p=gets(s);hd=creat_gl(&p);prn_gl(head(hd);prn_gl(tail(hd);hc=copy_gl(hd);printf(copy after:);prn_gl(hc); printf(sum:%dn,sum(hd);p

47、rintf(depth:%dn,depth(hd);第六章 樹和二叉樹一、選擇題 1.在線索化二叉樹中,t所指結(jié)點沒有左子樹的充要條件是（ ）（a）t-left=null （b）t-ltag=1（c）t-ltag=1且t-left=null（d）以上都不對2.二叉樹按某種順序線索化后,任一結(jié)點均有指向其前趨和后繼的線索,這種說法（a）正確 （b）錯誤 （c）不同情況下答案不確定3.二叉樹的前序遍歷序列中,任意一個結(jié)點均處在其子女結(jié)點的前面,這種說法（ ）(a)正確 (b)錯誤 （c）不同情況下答案不確定4.由于二叉樹中每個結(jié)點的度最大為2,所以二叉樹是一種特殊的樹,這種說法（ ）（a）正確 （b）錯誤 （c）不同情況下答案不確定5.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點,則此類二叉樹中所包含的結(jié)點數(shù)至少為（ ）。（a）2h （b）2h-1（c）2h+1（d）h+16.已知某二叉樹的后序遍歷序列是dabec。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（a）acbed （b）decab（c）deabc （d）cedba7.如果t2是由有序樹t轉(zhuǎn)換而來的二叉樹,那么t中結(jié)點的前序就是t2中結(jié)點的（ ）（a）前序（b）中序（c）后序（d）層次序8.某二叉樹的前序遍歷結(jié)點訪問順序是ab