第一篇：嚴(yán)蔚敏 數(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ù)據(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ì)問題中計(jì)算機(jī)的（①）以及它們之間的（②）和運(yùn)算等的學(xué)科。

①（A）數(shù)據(jù)元素（B）計(jì)算方法（C）邏輯存儲(chǔ)（D）數(shù)據(jù)映像

②（A）結(jié)構(gòu)（B）關(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）解決問題的有限運(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è)特性為：有窮性、輸入、輸出、完成性和確定性。（）

5.算法的時(shí)間復(fù)雜度取決于問題的規(guī)模和待處理數(shù)據(jù)的初態(tài)。（）

三、填空題

1.數(shù)據(jù)邏輯結(jié)構(gòu)包括________、________、_________ 和_________四種類型,其中樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為_____。

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.在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有_______結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有_______個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒有________結(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)系,樹形結(jié)構(gòu)中元素之間存在______關(guān)系,圖形結(jié)構(gòu)中元素之間存在_______關(guān)系。

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.求下列算法段的語句頻度及時(shí)間復(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；后繼；任意多個(gè)

4、任意多個(gè)

5、一對(duì)一；一對(duì)多；多對(duì)多

6、有窮性；確定性；可行性；輸入；輸出

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/4≤T(n)/n2≤1，故它的時(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;k<=j;k++)x=i+j-k;

分析算法規(guī)律可知時(shí)間頻度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)由于有1/6 ≤ T（n）/ n3 ≤1，故時(shí)間復(fù)雜度為Ｏ(n3)

第二章 線性表

一、選擇題

1.一個(gè)線性表第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是()（A）110（B）108（C）100（D）120 2.向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)（）個(gè)元素。

（A）64（B）63（C）63.5（D）7 3.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，其地址（）。

(A)必須是連續(xù)的(B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的(D)連續(xù)與否均可以

4.在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行（）

（A）s->next=p;p->next=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.線性表是具有n個(gè)（）的有限序列（n≠0)

（A）表元素（B）字符（C）數(shù)據(jù)元素

（D）數(shù)據(jù)項(xiàng)

二、判斷題

1.線性表的鏈接存儲(chǔ)，表中元素的邏輯順序與物理順序一定相同。（）

2.如果沒有提供指針類型的語言，就無法構(gòu)造鏈?zhǔn)浇Y(jié)構(gòu)。（）

3.線性結(jié)構(gòu)的特點(diǎn)是只有一個(gè)結(jié)點(diǎn)沒有前驅(qū)，只有一個(gè)結(jié)點(diǎn)沒有后繼，其余的結(jié)點(diǎn)只有一個(gè)前驅(qū)和后繼。（）

4.語句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)，在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的語句為：_______________________。

2.順序表中邏輯上相鄰的元素物理位置()相鄰，單鏈表中邏輯上相鄰的元素物理位置_________相鄰。

3.線性表L＝（a1，a2，...，an）采用順序存儲(chǔ)，假定在不同的n＋1個(gè)位置上插入的概率相同，則插入一個(gè)新元素平均需要移動(dòng)的元素個(gè)數(shù)是________________________ 4.在非空雙向循環(huán)鏈表中，在結(jié)點(diǎn)q的前面插入結(jié)點(diǎn)p的過程如下：

p->prior=q->prior;q->prior->next=p;p->next=q;______________________;

5.已知L是無表頭結(jié)點(diǎn)的單鏈表，是從下列提供的答案中選擇合適的語句序列，分別實(shí)現(xiàn)：

（1）表尾插入s結(jié)點(diǎn)的語句序列是_______________________________(2)表尾插入 s結(jié)點(diǎn)的語句序列是_______________________________

1.p->next=s;2.p=L;3.L=s;

4.p->next=s->next;

5.s->next=p->next;6.s->next=L;7.s->next=null;

8.while(p->next!= Q)? p=p-next;9.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.某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成一個(gè)循環(huán)鏈表，每個(gè)結(jié)點(diǎn)有價(jià)格、數(shù)量和鏈指針三個(gè)域。現(xiàn)出庫（銷售）m臺(tái)價(jià)格為h的電視機(jī)，試編寫算法修改原鏈表。

4.某百貨公司倉庫中有一批電視機(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（a≤b）之間的元素。

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（0≤i

若n

若存在一個(gè)j，jB。

試編寫一個(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),頭指針分別為ah和bh，設(shè)計(jì)C函數(shù)，把兩個(gè)線性表合并成形如（a0,b0,a1,b1,…）的線性表，要求不開辟新的動(dòng)態(tà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)鏈表的長度放在各自的頭結(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、×

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.h” typedef struct node {int 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);}

2、#include “stdio.h” #include “malloc.h” typedef struct node { int 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);} else { p=q;q=q->link;} } }

3、void del(NODE *head,float price,int num){ NODE *p,*q,*s;p=head;q=head->next;while(q->price

next;} 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.h” typedef struct node { float price;int num;struct node *next;}NODE;void ins(NODE *head,float price,int num)

{ NODE *p,*q,*s;p=head;q=head->next;while(q->price

next;} if(q->price==price)q->num=q->num+num;else { s=(NODE *)malloc(sizeof(NODE));s->price=price;s->num=num;s->next=p->next;p->next=s;} }

5、順序表：

算法思想：從0開始掃描線性表，用k記錄下元素值在a與b之間的元素個(gè)數(shù)，對(duì)于不滿足該條件的元素，前移k個(gè)位置，最后修改線性表的長度。

void del（elemtype list[]，int *n，elemtype a，elemtype b）

{ int i=0，k=0；

while（i=a&&list[i]<=b)k++;else list[i-k]=list[i];

i++;} *n=*n-k;/* 修改線性表的長度*/ } 循環(huán)鏈表: void del(NODE *head,elemtype a,elemtype b){ NODE *p,*q;p= head;q=p->link;/* 假設(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 100 int listA[MAXSIZE],listB[MAXSIZE];int n,m;int compare(int a[],int b[]){ int i=0;

while(a[i]==b[i]&&im&&i==m)return(1);if(ib[i])return(1);}

7、void del(DUNODE **head,int i){ DUNODE *p;if(i==0){ *head=*head->next;*head->prior=NULL;return(0);}

Else {for(j=0;jnext;if(p==NULL||j>i)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=list[i];list[i]=list[l+h-i];list[l+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 node { elemtype data;struct node *link;}NODE;void convert(NODE **head,int n,int m){ NODE *p,*q,*r;int i;p=*head;q=*head;for(i=0;i

q=q->link;/*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 node { elemtype 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->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 node { elemtype data;struct 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=i;r->link=rh;qh->data=j;q->link=qh;} 11.typedef struct node { elemtype 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 node { elemtype data;struct node *link;}NODE;void del(NODE *x,NODE *y){ NODE *p,*q;elemtype d1;p=y;q=x;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)為空的條件是（）。（A）ST-〉top!=0（B）ST-〉top==0（C）ST-〉top!=m0（D）ST-〉top=m0 4.判定一個(gè)棧ST(最多元素為m0)為棧滿的條件是（）。（A）ST->top!=0（B）ST->top==0（C）ST->top!=m0-1（D）ST->top==m0-1 5.一個(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,1 6.循環(huán)隊(duì)列用數(shù)組A[0,m-1]存放其元素值,已知其頭尾指針分別是front和rear則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是（）

（A）(rear-front+m)%m（B）rear-front+1（C）rear-front-1（D）rear-front 7.棧和隊(duì)列的共同點(diǎn)是（）

（A）都是先進(jìn)后出（B）都是先進(jìn)先出

（C）只允許在端點(diǎn)處插入和刪除元素（D）沒有共同點(diǎn) 8.表達(dá)式a*(b+c)-d的后綴表達(dá)式是（）。

（A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd 9.4個(gè)元素a1，a2，a3和a4依次通過一個(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，a1 10.以數(shù)組Q[0..m－1]存放循環(huán)隊(duì)列中的元素，變量rear和qulen分別指示循環(huán)隊(duì)列中隊(duì)尾元素的實(shí)際位置和當(dāng)前隊(duì)列中元素的個(gè)數(shù)，隊(duì)列第一個(gè)元素的實(shí)際位置是（）(A)rear－qulen(B)rear－qulen＋m

(C)m－qulen

(D)1＋（rear＋m－qulen）% 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依次通過一個(gè)棧，一個(gè)元素出棧后即進(jìn)入隊(duì)列Q，若6個(gè)元素出隊(duì)列的順序是a3，a5，a4，a6，a2，a1則棧S至少應(yīng)該容納_____個(gè)元素。

三、算法設(shè)計(jì)題

1.假設(shè)有兩個(gè)棧s1和s2共享一個(gè)數(shù)組stack[M],其中一個(gè)棧底設(shè)在stack[0]處，另一個(gè)棧底設(shè)在stack[M-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)算來實(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、C

9、C

10、D

二、填空題

1、先進(jìn)先出；先進(jìn)后出

2、線性 ； 任何 ；棧頂；隊(duì)尾；對(duì)頭

3、正確的 4、3

三、算法設(shè)計(jì)題

1.#define M 100 elemtype stack[M];int top1=0,top2=m-1;int push(elemtype x,int i){

if(top1-top2==1)return(1);/*上溢處理*/ else if(i==1)stack[top1++]=x;if(i==2)stack[top2--]=x;return(0);}

int pop(elemtype *px,int i){ if(i==1)if(top1==0)return(1);else { top1--;*px=stack[top1];return(0);} else if(i==2)if(top2==M-1)return(1);else { top2++;*px=stack[top2];return(0);} } 2.elemtype s1[MAXSIZE],s2[MAZSIZE];int top1,top2;void enqueue(elemtype x){

if(top1==MAXSIZE)return(1);else { push(s1,x);return(0);}} void dequeue(elemtype *px){ elemtype x;top2=0;while(!empty(s1)){ pop(s1,&x);push(s2,x);} pop(s2,&x);while(!empty(s2)){ pop(s2,&x);push(s1,x);} } 第四章 串

一、選擇題

1.下列關(guān)于串的敘述中，正確的是（）

(A)一個(gè)串的字符個(gè)數(shù)即該串的長度(B)一個(gè)串的長度至少是1

(C)空串是由一個(gè)空格字符組成的串(D)兩個(gè)串S1和S2若長度相同，則這兩個(gè)串相等 2.字符串“abaaabab”的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(‘xyz’)= ‘x’,tail(‘xyz’)= ‘yz’,則s=()。concat(head(tail(s)),head(tail(tail(s))))= ‘dc’。

(A)abcd(B)acbd(C)acdb(D)adcb 4.串是一種特殊的線性表,其特殊性表現(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開始的J個(gè)字符組成的字串，LENGTH（S）返回串S的長度，則CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的結(jié)果串是（）

（A）BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF

二、算法設(shè)計(jì)

1.分別在順序存儲(chǔ)和一般鏈接存儲(chǔ)兩種方式下,用C語言寫出實(shí)現(xiàn)把串s1復(fù)制到串s2的串復(fù)制函數(shù)strcpy(s1,s2)。

2.在一般鏈接存儲(chǔ)(一個(gè)結(jié)點(diǎn)存放一個(gè)字符)方式下,寫出采用簡單算法實(shí)現(xiàn)串的模式匹配的C語言函數(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 100 char s[MAXN];int S_strlen(char s[]){

int i;for(i=0;s[i]!='