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

1、第一章 緒論選擇題 1.組成數(shù)據(jù)的基本單位是（ ） （a）數(shù)據(jù)項(xiàng)（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）動(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) 4.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 （）以及它們之間的（）和運(yùn)算等的學(xué)科。 （a）數(shù)據(jù)元素（b）計(jì)算方法（c）邏輯存儲(chǔ)（d）數(shù)據(jù)映像 （a）結(jié)構(gòu) （b）

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

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

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

5、輸入；輸出 7、數(shù)據(jù)元素；邏輯結(jié)構(gòu)；存儲(chǔ)結(jié)構(gòu) 8、插入、刪除、合并等操作較方便 9、順序存儲(chǔ)；鏈?zhǔn)酱鎯?chǔ) 四、算法分析題for(i=1; i=n; i+)for(j =1; j =i ; j+)x=x+1;分析：該算法為一個(gè)二重循環(huán)，執(zhí)行次數(shù)為內(nèi)、外循環(huán)次數(shù)相乘，但內(nèi)循環(huán)次數(shù)不固定，與外循環(huán)有關(guān)，因些，時(shí)間頻度t(n)=1+2+3+n=n*(n+1)/2有 1/4t(n)/n21，故它的時(shí)間復(fù)雜度為(n2), 即(n)與n2 數(shù)量級(jí)相同。 2、分析下列算法段的時(shí)間頻度及時(shí)間復(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.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(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）線性表中至少有一個(gè)元素 （c）線性表中任何一個(gè)元素有且僅有一個(gè)直接前趨 （d）線性表中任何一個(gè)元素有且僅有一個(gè)直接后繼

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

8、p結(jié)點(diǎn)后插入s結(jié)點(diǎn)的語(yǔ)句為：_ 。2.順序表中邏輯上相鄰的元素物理位置( )相鄰， 單鏈表中邏輯上相鄰的元素物理位置_相鄰。 3.線性表l（a1，a2，.，an）采用順序存儲(chǔ)，假定在不同的n1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是_ 4.在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過(guò)程如下： p-prior=q-prior;q-prior-next=p;p-next=q;_; 5.已知l是無(wú)表頭結(jié)點(diǎn)的單鏈表，是從下列提供的答案中選擇合適的語(yǔ)句序列，分別實(shí)現(xiàn)： （1）表尾插入s結(jié)點(diǎn)的語(yǔ)句序列是_(2) 表尾插入 s結(jié)點(diǎn)的語(yǔ)句序列是_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è)計(jì)題 1.試編寫一個(gè)求已知單鏈表的數(shù)據(jù)域的平均值的函數(shù)（數(shù)據(jù)域數(shù)據(jù)類型為整型）。 2.已知帶有頭結(jié)點(diǎn)的循環(huán)鏈表中頭指針為head,試寫出刪除并釋放數(shù)據(jù)域值為x的所有結(jié)點(diǎn)的c函數(shù)。 3.某百貨公司倉(cāng)庫(kù)中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域?，F(xiàn)出庫(kù)（銷售）m臺(tái)價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。 4.某百貨公

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

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

12、,a1,b1,）的線性表，要求不開(kāi)辟新的動(dòng)態(tài)空間,利用原來(lái)循環(huán)鏈表的結(jié)點(diǎn)完成合并操作,結(jié)構(gòu)仍為循環(huán)鏈表,頭指針為head,并分析算法的時(shí)間復(fù)雜度。 10.試寫出將一個(gè)線性表分解為兩個(gè)帶有頭結(jié)點(diǎn)的循環(huán)鏈表，并將兩個(gè)循環(huán)鏈表的長(zhǎng)度放在各自的頭結(jié)點(diǎn)的數(shù)據(jù)域中的c函數(shù)。其中,線性表中序號(hào)為偶數(shù)的元素分解到第一個(gè)循環(huán)鏈表中,序號(hào)為奇數(shù)的元素分解到第二個(gè)循環(huán)鏈表中。 11.試寫出把線性鏈表改為循環(huán)鏈表的c函數(shù)。 12.己知非空線性鏈表中x結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)為y,試寫出刪除x結(jié)點(diǎn)的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è)計(jì)題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ù)域?yàn)檎?*/struct node *link;node;void del_link(node *head,int x) /* 刪除數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)*/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(無(wú)此產(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āi)始掃描線性表，用k記錄下元素值在a與b之間的元素個(gè)數(shù)，對(duì)于不滿足該條件的元素，前移k個(gè)位置，最后修改線性表的長(zhǎng)度。 void del（elemtype list，int *n，elemtype a，elemtype b） int i=0，k=0； while（i=a&listilink; /

17、* 假設(shè)循環(huán)鏈表帶有頭結(jié)點(diǎn) */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.順序存儲(chǔ):void convert(elemtype list,int l,int h) /* 將數(shù)組中第l個(gè)到第h個(gè)元素逆置*/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);該算法的時(shí)間復(fù)雜度為o(n+m),空間復(fù)雜度為o(1)鏈接存儲(chǔ):(不帶頭結(jié)點(diǎn)的單鏈表)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é)點(diǎn) */r=q-link;q-link=null; while(r-link!=null)r=r-link; /*r指向最后一個(gè)bm-1結(jié)點(diǎn) */*head=q;r-link=p; 該算法的時(shí)間復(fù)雜度為o(n+m),但比順序存儲(chǔ)節(jié)省時(shí)間(不需要移動(dòng)元素,只需改變指針),空間復(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é)點(diǎn)個(gè)數(shù)小于等于b的結(jié)點(diǎn)個(gè)數(shù) */a-link=b;while(b-link!=bh)b=b-link;b-link=head;if(b-link=bh) /*b的結(jié)點(diǎn)個(gè)數(shù)小于a的結(jié)點(diǎn)個(gè)數(shù) */ r=a-link;a-link=b;b-link=r;return(head);該算法的時(shí)間復(fù)雜度為o(n+m),其中n和m為兩個(gè)循環(huán)鏈表的結(jié)點(diǎn)個(gè)數(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為序號(hào)是奇數(shù)的結(jié)點(diǎn)個(gè)數(shù) j為序號(hào)是偶數(shù)的結(jié)點(diǎn)個(gè)數(shù) */p=a； rh=（node *）malloc（sizeof（node）；/*rh為序號(hào)是奇數(shù)的鏈表頭指針 */qh=(node *)malloc(sizeof(node); /*qh為序號(hào)是偶數(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) /* 把后一個(gè)結(jié)點(diǎn)數(shù)據(jù)域前移到前一個(gè)結(jié)點(diǎn)*/ p-data=q-data;q=q-link;p=q;p-link=null; /* 刪除最后一個(gè)結(jié)點(diǎn)*/free(q);第三章 棧和隊(duì)列一、選擇題 1. 一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是（ ）。（a） edcba（b）decba（c）dceab （d）abcde 2.棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ ）。（a） 線性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)（b）散列方式和索引方式（c）鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 （d）線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)3.判定一個(gè)棧st(最多元素為m0)為空的條件是（ ）。

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

26、1 （c）rear-front-1（d）rear-front7.棧和隊(duì)列的共同點(diǎn)是（ ）（a） 都是先進(jìn)后出 （b）都是先進(jìn)先出（c）只允許在端點(diǎn)處插入和刪除元素（d）沒(méi)有共同點(diǎn)8.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（ ）。（a）abcd*+-（b）abc+*d- （c）abc*+d-（d）-+*abcd9.4個(gè)元素a1，a2，a3和a4依次通過(guò)一個(gè)棧，在a4進(jìn)棧前，棧的狀態(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)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)

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

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

29、c 9、c 10、d 二、填空題1、先進(jìn)先出；先進(jìn)后出2、線性 ； 任何 ；棧頂；隊(duì)尾；對(duì)頭3、正確的 4、3三、算法設(shè)計(jì)題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)一個(gè)串的字符個(gè)數(shù)即該串的長(zhǎng)度 (b)一個(gè)串的長(zhǎng)度至少是1(c)空串是由一個(gè)空格字符組成的串 (d)兩個(gè)串s1和s2若長(zhǎng)度相同，則這兩個(gè)串相等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)可以順序存儲(chǔ) (b)數(shù)據(jù)元素是一個(gè)字符(c)可以鏈?zhǔn)酱鎯?chǔ) (d)數(shù)據(jù)元素可以是多個(gè)字符5設(shè)串s1=abcdefg,s2=pqrst,函數(shù)concat（x，y）返回x和y串的連接串，substr（s，i，j）返回串s從序號(hào)i開(kāi)始的j個(gè)字符組成的字串，length（s）返回串s的長(zhǎng)度，則concat（substr（s1，2，length（s2

33、），substr（s1，length（s2），2）的結(jié)果串是（ ）（a）bcdef (b) bcdefg (c)bcpqrst (d)bcdefef 二、算法設(shè)計(jì) 1.分別在順序存儲(chǔ)和一般鏈接存儲(chǔ)兩種方式下,用c語(yǔ)言寫出實(shí)現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy(s1,s2)。2.在一般鏈接存儲(chǔ)(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下,寫出采用簡(jiǎn)單算法實(shí)現(xiàn)串的模式匹配的c語(yǔ)言函數(shù)int l_index(t,p)。參考答案：一、選擇題 1. a 2.b 3. d 4. d 5. d 二、算法設(shè)計(jì) 1.順序存儲(chǔ)： #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;一般鏈接存儲(chǔ)： #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. 常對(duì)數(shù)組進(jìn)行的兩種基本操作是（ ）（a）建立與刪除（b）索引和修改（c）查找和修改（d）查找與索引2.二維數(shù)組m的元素是4個(gè)字符(每個(gè)字符占一個(gè)存儲(chǔ)單元)組成的串,行下標(biāo)i的范圍從0到4,列下標(biāo)j的范圍從0到5,m按行存儲(chǔ)時(shí)元素m35的起始地址與m按列存儲(chǔ)時(shí)元素( ) 的起始地址相同。（a）m24（b）m34（c）m35（d）m44

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

38、方法有兩種,即（ ）。（a） 二維數(shù)組和三維數(shù)組（b）三元組和散列（c）三元組和十字鏈表 （d）散列和十字鏈表7.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣,只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換,就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算,這種觀點(diǎn)（ ）。（a）正確（b）錯(cuò)誤8.設(shè)矩陣a是一個(gè)對(duì)稱矩陣,為了節(jié)省存儲(chǔ),將其下三角部分按行序存放在一維數(shù)組b1,n(n-1)/2中,對(duì)下三角部分中任一元素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采用行序?yàn)橹鞣绞酱鎯?chǔ),

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

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

41、表所有原子結(jié)點(diǎn)數(shù)據(jù)域(設(shè)數(shù)據(jù)域?yàn)檎椭偷暮瘮?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è)計(jì)題1.算法思想：依題意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,則該元素aij便是馬鞍點(diǎn),找出所有這樣的元素,即找到了所有馬鞍點(diǎn)。因此,實(shí)現(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+)/*計(jì)算出每行的最小值元素,放入minm之中*/mini1=ai10;for(j=1;jn;j+)if(ai1jmini1) mini1=ai1j;for(j=0;jn;j+)/*計(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é)點(diǎn)的數(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);第六章 樹(shù)和二叉樹(shù)一、選擇題 1.在線索化二叉樹(shù)中,t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是（ ）（a）t-left=null （b）t-ltag=1（c）t-ltag=1且t-left=null（d）以上都不對(duì)2.二叉樹(shù)按某種順序線索化后,任一結(jié)點(diǎn)均有指向其前趨和后繼的線索,這種說(shuō)法（a）正確 （b）錯(cuò)誤 （c）不同情況下答案不確定3.二叉樹(shù)的前序遍歷序列中,任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面,這種說(shuō)法（ ）(a)正確 (b)錯(cuò)誤 （c）不同情況下答案不確定4.由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2,所以二叉樹(shù)是一種特殊的樹(shù),這種說(shuō)法（ ）（a）正確 （b）錯(cuò)誤 （c）不同情況下答案不確定5.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn),則此類二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（ ）。（a）2h （b）2h-1（c）2h+1（d）h+16.已知某二叉樹(shù)的后序遍歷序列是dabec。中序遍歷序列是debac,它的前序遍歷序列是（ ）。（a）acbed （b）decab（c）deabc （d）cedba7.如果t2是由有序樹(shù)t轉(zhuǎn)換而來(lái)的二叉樹(shù),那么t中結(jié)點(diǎn)的前序就是t2中結(jié)點(diǎn)的（ ）（a）前序（b）中序（c）后序（d）層次序8.某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是ab