《數(shù)據(jù)結(jié)構(gòu)》課后題及答案

第一章緒論

一、選擇題

1、（）是數(shù)據(jù)的基本單位。

A）數(shù)據(jù)結(jié)構(gòu)B）數(shù)據(jù)元素C）數(shù)據(jù)項D）數(shù)據(jù)類型

2、以下說法不正確的是（）。

A）數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間的邏輯結(jié)構(gòu)。

B）數(shù)據(jù)類型可看成是程序設(shè)計語言中已實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。

C）數(shù)據(jù)項是組成數(shù)據(jù)元素的最小標(biāo)識單位。

D）數(shù)據(jù)的抽象運算不依賴具體的存儲結(jié)構(gòu)。

3、計算機算法是解決問題的有限運算序列,它具備輸入、輸出和（）等5個特性。

A）可執(zhí)行性、可移植性和可擴充性B）可行性、確定性和有窮性

C）確定性、有窮性和穩(wěn)定性D）易讀性、穩(wěn)定性和安全性

4、一般而言，最適合描述算法的語言是（）。

A）自然語言B）計算機程序語言

C）介于自然語言和程序設(shè)計語言之間的偽語言D）數(shù)學(xué)公式

5、通常所說的時間復(fù)雜度指（）。

A）語句的頻度B）算法的時間消耗

C）漸近時間復(fù)雜度D）最壞時間復(fù)雜度

6、A算法的時間復(fù)雜度為0（/）,B算法的時間復(fù)雜度為0（2〉，則說明（）。

A）對于任何數(shù)據(jù)量，A算法的時間開銷都比B算法小

B）隨著問題規(guī)模n的增大，A算法比B算法有效

C）隨著問題規(guī)模n的增大，B算法比A算法有效

D）對于任何數(shù)據(jù)量，B算法的時間開銷都比A算法小

7、算法分析的目的是（）。

A）找出數(shù)據(jù)結(jié)構(gòu)的合理性B）研究算法中的輸入和輸出的關(guān)系

C）分析算法的效率以求改進(jìn)D）分析算法的易懂性和文檔性

8、下面程序段的時間復(fù)雜度為（）。

for（i=0;i<m;i++）

for（j=0;j<n;j++）

a[i][j]=i*j；

A）0（m2）B）O（n2）C)O(m*n)D)O(m+n)

9、下面算法的時間復(fù)雜度為（)。

intf（intn）

{if(n==0IIn==1)return1;elsereturnn*f(n-1);}

A)0(1)B)0(n)C)0(n2)D)0(n!)

二、填空題

1、數(shù)據(jù)的（）結(jié)構(gòu)依賴于計算機語言。

2、在線性結(jié)構(gòu)中，第一個結(jié)點（）前驅(qū)結(jié)點，其余每個結(jié)點有且只有（）個前驅(qū)結(jié)

點；最后一個結(jié)點（）后繼結(jié)點；其余每個結(jié)點有且只有（）個后繼結(jié)點。

3、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有（）結(jié)點，其余每個結(jié)點有且只有（）個前驅(qū)結(jié)點；葉

子結(jié)點沒有（）結(jié)點，其余每個結(jié)點的后繼結(jié)點可以（）。

4、在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點之間分別存在著（）、

）和（）的關(guān)系。

5、評價一個算法優(yōu)劣的兩個主要指標(biāo)是（）和（）。

6、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為（）、（）、（）和（）四種。

7、數(shù)據(jù)的存儲結(jié)構(gòu)被分為（）、（）、（）、（）四種.

8、算法的時間復(fù)雜度除了與問題的規(guī)模有關(guān)外，還與輸入實例的（）有關(guān)。

三、問答題與算法題

1、簡述下列概念：

數(shù)據(jù)元素：

數(shù)據(jù)結(jié)構(gòu)：

數(shù)據(jù)類型：

數(shù)據(jù)的邏輯結(jié)構(gòu)及其4種類型：

數(shù)據(jù)的存儲結(jié)構(gòu)及其4種方式：

2、設(shè)兩個算法在同一臺機器上執(zhí)行，其執(zhí)行時間分別是仔和2口，要使前者快于后者，n

至少需要多大？

3、有時為比較兩個同數(shù)量級的算法優(yōu)劣，須突出主項的常數(shù)因子，而將低次項用“0“記號

表示。如：ST,（n）=1.39nlogn+100n+256=1.39nlogn+0（n）;

T2（n）=2.0nlogn-2n=2.0nlogn-0（n）;

這兩個式子表示，當(dāng)n足夠大時，「（11）優(yōu)于12（11）,因為前者的系數(shù)因子小于后者。請用

此方法表示下列函數(shù)，并指出當(dāng)n足夠大時，哪?個較優(yōu)，哪一個較劣。

22

（I）T,（n）=5n-3n+60logn;（2）T2（n）=3n+1000n+3logn;

z2

（3）T3（n）=8n+3logn;（4）T4（n）=1.5n+O（n）。

4、計算執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為。

for（i=l;i<=n;i++）

for（j=l;jv=i;j++）S;

第二章線性表

一、選擇題

1、線性表是具有n個（）的有限序列。

A）數(shù)據(jù)項；B）數(shù)據(jù)元素；C）數(shù)據(jù)對象；D）表元素。

2、以下關(guān)于線性表的說法不正確的是（）。

A）線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。

B）線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的。

C）線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼。

D）存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼。

3、線性表的順序存儲結(jié)構(gòu)是一種（）的存儲結(jié)構(gòu)。

A）隨機存取B）順序存取C）索引存取D）散列存取

4、在順序表中，只要知道（），就可在相同時間內(nèi)求出任一結(jié)點的存儲地址。

A）基地址B）結(jié)點大小C）線性表大小D）基地址和結(jié)點大小

5、下面關(guān)于線性表的敘述中，錯誤的是哪一個？（）

A）線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。

B）線性表采用順序存儲，便于進(jìn)行插入和刪除操作。

0線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。

D）線性表采用鏈接存儲，便于插入和刪除操作。

6、線性表采用鏈表存儲時其存儲地址要求（

A）必須是連續(xù)的；B）部分地址必須是連續(xù)的；

C）必須是不連續(xù)的；D）連續(xù)和不連續(xù)都可以。

7、一個長度為n的線性表順序存儲，向第i個元素（lWiWn+1）之前插入一個新元素時，需

要從后向前依次后移（）個元素。

A）n-iB）n-i+1C）n-i-1D）i

8、（）運算中，使用順序表比鏈表好。

A）插入B）刪除C）根據(jù)序號查找D）根據(jù)元素值查找

9、向具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是（）。

2

A）0（1）B）O（n）C）0（n）D）O（log2n）

10、在一個長度為n的順序存儲的線性表中，刪除第i個元素（iWiWn）時，需要從前向后依

次前移（）個元素。

A）n-iB）n-i+1C）n-i-1D）i

11、在一個長度為n的線性表中順序查找值為x的元素時，平均查找長度（即x同元素的平

均比較次數(shù)，假定查找每個元素的概率都相等）為（）。

A）nB）n/2C）（n+l）/2D）（n-l）/2

12、在一個帶頭結(jié)點的單鏈表HL中，若要向表頭插入一個山指針p指向的結(jié)點，則

執(zhí)行的語句是（）。

A）HL=p;p->next=HL;B）p->next=HL;HL=p;

C）p->next=HL;p=HL;D）p->next=HL->next;HL->next=p;

13、在一個單鏈表HL中，若要在指針q所指的結(jié)點的后面插入一個由指針p所指的結(jié)點，

則執(zhí)行（）o

A）q->next=p->next;p->next=q;B）p->next=q->next;q=p;

C）q->next=p->next;p->next=q;D）p->next=q->next;q->next=p;

14、在一個單鏈表HL中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點，則執(zhí)行（）。

A）p=q->next;p->next=q->next;B）p=q->next;q->next=p;

C)p=q->next;q->next=p->next;D)q->next=q->next->next;q->next=q;

15、在雙向鏈表中，在指針p所指的結(jié)點前插入一個指針q所指的結(jié)點，操作是()。

A)p->Prior=q;q->Next=p;p->Prior->Next=q;q->Prior=q；

B)p->Prior=q;p->Prior->Next=q;q->Next=p;q->Prior=p->Prior;

C)q->Next=p;q->Prior=p->Prior;p->Prior->Next=q;p->Prior=q;

D)q->Prior=p->Prior;q->Next=q;p->Prior=q;p->next=q;

二、填空題

1、對于一個具有n個結(jié)點的單鏈表，在已知結(jié)點*p的后插入一個新結(jié)點的時間復(fù)雜度為

(），在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為（)?

2、根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成

（）和（）o

3、順序存儲結(jié)構(gòu)是通過（）表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過（）表

示元素之間的關(guān)系的。

4、對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改（）個指針，單鏈表為

(）個。

5、循環(huán)單鏈表的最大優(yōu)點是（）。

6、在無頭結(jié)點的單鏈表中，第1個結(jié)點的地址存放在頭指針中,其他結(jié)點的存儲地址存放

在（）結(jié)點的next域中。

7、帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是（

8、當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作,但要求以最快的速度存取

線性表中的元素時，應(yīng)采用（）存儲結(jié)構(gòu)。

9、求順序表和單鏈表的長度算法的時間復(fù)雜度分別是（)和(）。

10、順序表存儲結(jié)構(gòu)的優(yōu)點是（)、(）、

（）;缺點是（）。

11、單鏈表存儲結(jié)構(gòu)的優(yōu)點是（）、（）;缺點是

（）、（）。

12、在單鏈表中，設(shè)置頭結(jié)點的作用是（）。

13、鏈接存儲的特點是利用（）來表示數(shù)據(jù)元素之間的邏輯關(guān)系。

14、帶頭結(jié)點的雙循環(huán)鏈表DL為空表的條件是：（）。

15、以下算法的功能是：在一個非遞減的順序及中，刪除所有值相等的多余元素。在畫線處

填上適當(dāng)?shù)恼Z句，將程序補充完整。

#definemaxlen100

typedefstruct{

elemtypea[maxlenJ;

intlength;

}sqlist;

voiddelequil(sqlist&S)

{intj=l,i=2;

while()

{if(S.a[i]!=S.a[j])

i++；

16.設(shè)雙鏈表的結(jié)點的存儲結(jié)構(gòu)如下：刪除鏈表中指針p所指結(jié)點的兩步主要操作是:

P

LlinkDataRlink

)，)°

三、問答題與算法題

1、試描述頭指針、頭結(jié)點、首結(jié)點的區(qū)別、并說明頭指針和頭結(jié)點的作用。

2、何時選用順序表、何時選用鏈表作為線性表的存儲結(jié)構(gòu)為宜?

3、為什么在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針更好?

4、下述算法的功能是什么？

LinkListABC(LinkListL){〃L是無頭結(jié)點單鏈表

if(L&&L->next)

{Q=L;L=L->next;P=L;

while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

returnL;

5、寫出下圖雙鏈表中對換值為23和15的兩個結(jié)點相互位置時修改指針的有關(guān)語句。

結(jié)點結(jié)構(gòu)為：(prior,data,next)

回叵

6、VoidAA(SqList&L,inti,intx)

{if(i>=1&&i<=Length(L))

{FOR(j=Length(L);j>=i;j--)

AU+1]=AU];

A[i]=x;

elseexit(ERROR);

假定調(diào)用該算法時線性表L的內(nèi)容為(15,26,37,48,55),i為3,x為51,則調(diào)用返回

后該單鏈表的內(nèi)容變?yōu)槭裁矗?/p>

7^重寫建立單連表的算法CreatList_L(Linklist&L,intn),要求順序輸入n個元素的值(即先

輸入aba2…).

CreatList_L(LinkList&L；intn)

8、設(shè)順序表L是一個遞減有序表，試寫一算法，插入元素x,插入后仍保持L的有序性。

Voidsinsert(Sqlist&S,intx)

9、寫一算法，在帶頭組卓的單鏈表上實現(xiàn)線性表的求表長ListLenglh(L)運算。

intListLength(LinkListL)

10、寫出從一個帶頭箏卓的單鏈表中刪除其值等于給定值x的結(jié)點的算法函數(shù)。

Intdelete(LinkList&L,intx){

11、已知遞增有序的兩個帶頭箏卓的單鏈表La,Lb分別存儲了一個非空集合A,B。設(shè)計算

法實現(xiàn)求兩個集合的并集的運算A=AUB

voidmergelist(linklist&La,linklistLb)

12、設(shè)計算法將不帶表頭結(jié)點的單向鏈表就地逆轉(zhuǎn)。

13、刪除整數(shù)數(shù)組中值相等的多余整數(shù)(只保留第一次出現(xiàn)的那個整數(shù))。

VoiddelDuplicate(intA[],int&n)

第三章棧和隊列

一、選擇題

1、對于棧，操作數(shù)據(jù)的原則是()。

A)先進(jìn)先出B)后進(jìn)先出C)后進(jìn)后出D)不分順序

2、一般情況下，將遞歸算法轉(zhuǎn)換成非遞歸應(yīng)通過設(shè)置()實現(xiàn)。

A)數(shù)組；B)線性表；C)隊列；D)棧。

3、棧和隊列的共同點是()

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

C)只允許在端點處插入和刪除元素D)沒有共同點

4、若棧的入棧序列是abcde,則棧的不可能的輸出序列是()。

A)edcbaB)decbaC)dceabD)abcde

5、在對棧的操作中，能改變棧的結(jié)構(gòu)的是()。

A)StackLength(S)B)StackEmpty(S)C)GetTop(S)D)ClearStack(S)

6、在一個棧頂指針為HS的鏈棧中將一個S指針?biāo)傅慕Y(jié)點入棧，執(zhí)行()。

A)HS->next=s;B)S->next=HS->next;HS->next=s;

C)S->next=HS;HS=s;D)S->next=HS;HS=HS->next;

7、若已知一個棧的入棧序列是1,2,3,...?n,其輸出序列是pl,p2,p3,...，pn,若pl=n,

則pi=()o

A)IB)n-iC)n-i+lD)不確定

8、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前尾指針rear和頭指針front的值分別為

0和3,當(dāng)從隊列中刪除?個元素，再加入兩個元素后，尾指針rear和頭指針front的值分

別是()o

A)1和5；B)2和4；C)4和2；D)5和1。

9、要使輸入序列為ABC變?yōu)樾蛄蠦AC時，使用的棧操作序列為()

A)push,pop,push,pop,push,popB)push,push,push,pop,pop,pop

C)push,push,pop,pop,push,popD)push,pop,push,push,pop,pop

10、設(shè)用一個大小m=60的順序表A[m]表示一個循環(huán)隊列，如果當(dāng)前的尾指針rear=32,

頭指針front=15,則當(dāng)前循環(huán)隊列的元素個數(shù)是()。

A)42；B)16；C)17；D)41o

11、設(shè)用順序表a[n]表示循環(huán)隊列，頭、尾指針分別為front和rear,則判斷隊列為空的條

件是()，判斷隊列滿的條件是()o

(1)A)a.front+1==a.rear；B)a.front==a.rear+1；

C)a.front==0；D)a.front==a.rearo

(2)A)(a.rear-1)%n=a.front；B)(a.rear+1)%n=a.front；

C)a.rear=(a.front-1)%n；D)a.rear=(a.front+1)%n。

12、循環(huán)隊列存儲在數(shù)組中，則入隊時的操作為()o

A)rear=rear+1B)rear=(rear+l)mod(m-1)

C)rear=(rear+1)modmD)rear=(rear+l)mod(m+1)

13、在解決計算機主機與打印機之間速度不匹配問題時通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū)，主:機

將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則從該緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該

是一個()結(jié)構(gòu)。

A)棧；B)隊列；C)數(shù)組；D)線性表。

14、設(shè)棧用向量V[l..n]存儲,初始棧頂指針top為n+1,則下面x進(jìn)棧的正確操作是()。

A.V[++top]=x;B.V[top++]=x;

C.V[—top]=x;D.V[top--]=x;

15、若棧采用順序存儲方式存儲,現(xiàn)兩棧共享空間top[i]代表第i個棧（i=1,2）

棧頂，棧1的底在v[l],棧2的底在V[m],則棧滿的條件是（）o

A.|top[2]-top[l]=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[l]=top[2]

16.表達(dá)式a*（b+c）-d的后綴表達(dá)式是（）?！灸暇├砉ご髮W(xué)2001一、2（L5分）】

A.abcd*+-B.abc+*d~C.abc*+d-D.-+*abcd

二、填空題

1、在棧中，可進(jìn)行插入和刪除操作的一端稱（）。

2、在作進(jìn)棧運算時,應(yīng)先判別棧是否（），在作退棧運算時應(yīng)先判別棧是否（）。當(dāng)

棧中元素為n個，作進(jìn)棧運算時發(fā)生上溢,則說明該棧的最大容量為（）。

3、棧的特點是（）,隊列的特點是（）。

4、由于鏈棧的操作只在鏈表頭部進(jìn)行，所以沒有必要設(shè)置（）結(jié)點。

5、帶頭結(jié)點的單鏈表L是空表的條件是（）；順序棧S是空棧的條件是

（）;順序棧S滿的條件是（）；不帶頭結(jié)點的鏈棧L是空棧

的條件是（）；循環(huán)隊列Q是空隊列的條件是（）；循

環(huán)隊列Q是滿隊列的條件是（）

6、用數(shù)組Q（其下標(biāo)在0…n-1之間，共有n個元素）表示?個循環(huán)隊列，front為當(dāng)前隊

頭元素的前一個位置，rear為隊尾元素的位置，假設(shè)隊列中的元素個數(shù)總小于n,則求隊列

中元素個數(shù)的公式是（）。

7、設(shè)元素入棧的順序是1、2、3....n,則所有可能的出棧序列共有（）種。

8、在具有n個單元的循環(huán)隊列中，隊滿時共有（）個元素。

9、設(shè)有一個空棧，棧頂指針為1000H（十六進(jìn)制），現(xiàn)有輸入序列為1,2,3,4,5,經(jīng)過

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是（）,而棧頂指針值是

（）H。（設(shè)棧為順序棧，每個元素占4個字節(jié)）

10、用PUSH表示入棧操作，POP表示出棧操作，若元素入棧的順序為1234,為了得到1342

的出棧順序，相應(yīng)的PUSH和POP的操作串為（）。

三、問答題與算法題

1、設(shè)將整數(shù)1.2,3,4依次進(jìn)棧,若入、出棧次序為Push（s,l）,Pop（s,xl）,Push（s,2）,Push（s,3）,

Pop（s,x2）,Pop（s,x3）,Push（s,4）,Pop（s,x4），則出棧的數(shù)字序列為何？

2、設(shè)用不帶頭結(jié)點的單鏈表表示棧，請分別寫出入棧和出棧的算法。

（1）intpush_L（Linkstack&sSelemTypee）

(2)intpop_L(Linkstack&sSelemType&e)

3、假設(shè)用帶頭結(jié)點的單循環(huán)鏈表表示隊列，并設(shè)置一個指向尾結(jié)點的指針(無頭指針)，請

分別寫出隊列的入隊和出隊算法。

(l)intEnQueue_L(Queueptr&QLQelemTypee)

⑵intDeQueue_L(Queueptr&QLQelemType&e)

4、指出下述程序段的功能是什么？

(1)voidabc1(Stack&S)

(

inti,arr[64],n=0;

while(!StackEmpty(S)){Pop(S,e);arr[n++]=e};

for(i=0,i<n;i++)Push(S,arr[i]);

(2)Voidabc2(StackS1,Stack&S2);

{initstack(tmp);

while(!StackEmpty(SI))

{pop(Sl,x);Push(tmp,x);}

while(!StackEmpty(tmp))

{Pop(tmp,x);Push(Sl,x);Push(S2,x);}

(3)voidabc3(Stack&S,intm)

{InitStack(T);

while(!StackEmpty(S))

{Pop(S,e);if(e!=m)Push(T,e);}

while(!StackEmpty(T))

{Pop(T,e);Push(S,e);)

(4)voidabc4(Queue&Q)

{InitStack(S);

while(!QueueEmpty(Q))

{DeQueue(Q,x);Push(S,x);}

while(!StackEmpty(S))

{Pop(S,x);EnQueue(Q,x);)

)

(5)voidinvert1(LinkList&L)。

{P=L；

initstack(S);

while(p)〃鏈表中的元素全部進(jìn)棧

{push(S,p->data);

p=p->next;

)

p=L;〃利用原來的鏈表只修改數(shù)據(jù)域的值(反序)

while(!stackempt(S))

{pop(S,e);

p->data=e;

p=p->next;

)

returnOK;

5、回文是指正讀反讀均相同的字符序列，如"abba"和"abdba”均是回文，但“good”不是回文。

試寫一個算法判定給定的用帶去綃，卓的單鏈表表示的字符串是否為回文。

Inthwl(linklistL)

6、寫一個將不帶頭結(jié)點的鏈棧S中所有結(jié)點均刪去的算法

voidClearStack(LinkStack&S)o

7、寫一個返回不帶頭結(jié)點的鏈棧S中結(jié)點個數(shù)的算法.

intStacksize(LinkStackS)。

8、利用棧操作，寫一個算法把一個不帶頭結(jié)點的鏈表的元素反序存放(同第二章12題，這

里要求利用棧操作)。

voidinvert2(LinkList&L)。

9、試將下列遞歸過程改寫為非遞歸過程。

voidtest(int&sum)

{intx；

scanf(x)；

if(x=0)sum=0

else{test(sum);sum+=x;}

printf(sum)；

)

10、從鍵盤上輸入一個逆波蘭表達(dá)式，用偽碼寫出其求值程序。規(guī)定：逆波蘭表達(dá)式的長度

不超過一行，以$符作為輸入結(jié)束，操作數(shù)之間用空格分隔，操作符只可能有+、-、*、/四種

運算。例如:23434+2*$

第四章串

一、選擇題

1、串是一種特殊的線性表，其特殊性體現(xiàn)在()。

A)可以順序存儲B)數(shù)據(jù)元素是一個字符

C)可以鏈接存儲D)數(shù)據(jù)元素可以是多個字符

2、有兩個串P和Q,求P在Q中首次出現(xiàn)的位置的運算稱()。

A)模式匹配B)連接C)求子串D)求串長

3、設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串(非

空且不同于S本身)的個數(shù)為()。

A)n2B)(n72)+(n/2)C)(n2/2)+(n/2)-lD)(n72)-(n/2)T

4、設(shè)串sl='ABCDEFG；s2=PQRST,,函數(shù)concat(x,y)返回x和y串的連接串，subString(s,i,j)

返回串s的從序號i的字符開始的j個字符組成的子串，Strlength(s)返回串s的長度，則

concat(subString(s1,2,Strlength(s2)),subString(s1,Strlength(s2),2)))的結(jié)果串是()。

A)BCDEFB)BCDEFGC)BCPQRSTD)BCDEFEF

5、順序串中，根據(jù)空間分配方式的不同，可分為()。

A)直接分配和間接分配B)靜態(tài)分配和動態(tài)分配

C)順序分配和鏈?zhǔn)椒峙銬)隨機分配和固定分配

6、設(shè)串S="abcdefgh”，則S的所有非平凡子串(除空串和S自身的串)的個數(shù)是()。

A)8；B)37；C)36；D)35o

7、設(shè)主串的長度為n,模式串的長度為m,則串匹配的KMP算法時間復(fù)雜度是()。

A)O(m)；B)O(n)；C)O(m+n)；D)O(n*m)。

8、已知串S='aaab',其Next數(shù)組值為()。

A.0123B.1123C.1231D.1211

二、填空題

1、在空串和空格串中，長度不為0的是()。

2、空格串是指(),其長度等于()。

3、按存儲結(jié)構(gòu)不同，串可分為()、()、()?

4、C語言中，以字符()表示串值的終結(jié)。

5、在塊鏈串中，為了提高存儲密度，應(yīng)該增大().

6、假設(shè)每個字符占1個字節(jié)，若結(jié)點大小為4的鏈串的存儲密度為50%,則其每個指針占

()個字節(jié)。

7、串操作雖然較多，但都可通過五種操作()、()、()、

()、()構(gòu)成的最小子集中的操作來實現(xiàn)。

8、設(shè)串S='IlikecomputerT='com',則Length(S)=()。Index(S,T,l)=()

9、在KMP算法中，next|j］只與()串有關(guān)，而與()串無關(guān)。

10、字符串'ababaaab)的nextval函數(shù)值為()。

11＞兩個字符串相等的充分必要條件是()。

12.實現(xiàn)字符串拷貝的函數(shù)strcpy為：

voidstrcpy(char*s,char*t)/*copyttos*/

{while()；}

三、問答題與算法題

1、簡述下列每對術(shù)語的區(qū)別:

空串和空格串：

串常量和串變量：

主串和子串：

目標(biāo)串和模式串。

2、在C語言中假設(shè)有如下的串說明：

charsH30J="Stocktom",s2[30J="March51999",s3[30J,

(1)在執(zhí)行下列語句后，s3的值是什么？

strcpy(s3,sl);strcat(s3,",");strcat(s3,s2);

(2)調(diào)用函數(shù)strcmp(sl,s2)的返回值是什么？

(3)調(diào)用函數(shù)strcmp(sl[5],"Ton")的返回值是什么？

(4)調(diào)用函數(shù)strlen(strcat(sl,s2))的返回值是什么?

3、利用C的庫函數(shù)strlen,strcpy和strcat寫一算法voidStrlnsert(char*S,char*T,inti),將串

T插入到串S的第i個位置上。若i大于S的長度，則插入不執(zhí)行。

voidStrlnsert(char*S,char*T,inti)

4、利用C的庫函數(shù)strlen和strcpy(或strcpy)寫一算法voidStrDelete(char*S,inti,

intm)刪去串S中從位置i開始的連續(xù)m個字符。若iestrlen(S),則沒有字符被刪除；若

i+m》strlen(S),則將S中從位置i開始直至末尾的字符均刪去。

voidStrDelete(char*S,inti,intm)〃串刪除

5、若S和T是用結(jié)點大小為1的帶頭結(jié)點的單鏈表存儲的兩個串，試設(shè)計一個算法找出S

中第一個不在T中出現(xiàn)的字符。

Intindexst(LinkListS,linkLintT)

6、在KMP算法中,求下列模式串的next。］。

(1)'abaabcac'(2)'aaabaaba'

7、設(shè)目標(biāo)為t='abcaabbabcabaacbacba',模式為p=<abcabaa,

(1)計算模式p的naxtval函數(shù)值;

(2)不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時每一趟的匹配過程。

11.寫一個遞歸算法來實現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。

第五章數(shù)組與廣義表

一、選擇題

1、稀疏矩陣的一般壓縮方法是()?

A)二維數(shù)組B)廣義表C)三元組表D)一維數(shù)組

a\\a\n

2、設(shè)矩陣A=...........是一個對稱矩陣，為了節(jié)省空間，將其下三角部分按行優(yōu)先

存放在一維數(shù)組B中。對下三角矩陣中任一元素atJ(i>=j),在一維數(shù)組B中下標(biāo)k的值是

()。

A)i(i-l)/2+j-lB)i(i-l)/2+jC)i(i+l)/2+j-lD)i(i+l)/2+j

3、在稀疏矩陣的三元組表示法中，每個三元組表示()。

A)矩陣中數(shù)據(jù)元素的行號、列號和值B)矩陣中非零元素的值

C)矩陣中非零元素的行號和列號D)矩陣中非零元素的行號、列號和值

4、對稀疏矩陣進(jìn)行壓縮存儲是為了()。

A)便于進(jìn)行矩陣運算B)便于輸入和輸出

C)節(jié)約存儲空間D)降低運算的時間復(fù)雜度

5、假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100],設(shè)每個數(shù)據(jù)元素占2個存

儲單元，基地址為10,則L0C[5,5]=()。

A)808B)818C)1010D)1020

6、設(shè)有數(shù)組A[i,j],數(shù)組的每個元素長度為3字節(jié)，i的值為1到8,j的值為1到10,

數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為

()o

A)BA+141B)BA+180C)BA+222D)BA+225

7、廣義表是線性表的推廣，它們之間的區(qū)別在于()o

A)能否使用子表B)能否使用原子項

C)表的長度D)是否能為空

8、已知廣義表L=((x,y,z),a,(u,t,w)),從L表中取出原子項t的運算是()。

A.head(tail(tail(L)))B.tail(head(head(tail(L))))

C.head(tai1(head(tail(L))))D.head(tail(head(tail(tail(L)))))

9、已知廣義表：A=(a,b),B=(A,A),C=(a,(b,A),B),下列運算的結(jié)果是：

tail(head(tai1(C)))=()。

A)(a)B)AC)aD)(b)E)bF)(A)

10、廣義表運算式Tail(((a,b),(c,d)))的操作結(jié)果是()。

A)()B)c,dC)((c,d))D)d

II、廣義表((a,b,c,d))的表頭是(),表尾是(

A)aB)()C)(a,b,c,d)D)(b,c,d)

12、設(shè)廣義表1=((a,b.c)),則L的長度和深度分別為()。

A)1和1B)1和3C)1和2D)2和3

13、下面說法不正確的是()o

A)廣義表的表頭總是一個廣義表B)廣義表的表尾總是一個廣義表

C)廣義表難以用順序存儲結(jié)構(gòu)D)廣義表可以是個多層次的結(jié)構(gòu)

14、已知廣義表LS=((a,b,c),(d,e,f)),運用head和tail函數(shù)取出LS中原子e的運算是

()。

A)head(tail(LS))B)tail(head(LS))

C)head(tai1(head(tai1(LS)))D)head(tail(tail(head(LS))))

15、設(shè)一個廣義表中結(jié)點的個數(shù)為n,則求廣義表深度算法的時間復(fù)雜度為()。

2

A)0(1)B)O(n)C)O(n)D)O(log2n)

二、填空題

1、n維數(shù)組中的每個元素都最多有()個直接前趨。

2、對于一個一維數(shù)組A[12],若一個數(shù)據(jù)元素占用字節(jié)數(shù)為S,首地址為1,則A[i](i>=0)

的存儲地址為(),若首地址為d,則A[i]的存儲地址為()。

3、已知二維數(shù)組A[m][n]采用行優(yōu)先順序存儲，每個元素占k個存儲單元，并且第一個元

素的存儲地址LOC(A⑼⑼)，則的地址是()o

4、多維數(shù)組中，數(shù)據(jù)元素的存放地址直接可通過地址計算公式計算出。因此，數(shù)組是一種

()存取結(jié)構(gòu)。

5、矩陣的壓縮存儲就是為多個相同的非零元素分配()個存儲空間，零元素不分配空間。

6、遞歸是算法設(shè)計的重要方法，遞歸由()項和()項構(gòu)成。用遞歸的

方法求廣義表LS的深度DEPTH(LS),寫出基本項和遞歸項。

基本項:

遞歸項:

7、廣義表(2,5,1)),(1,6,3/),1<))的長度是()，深度是()。

8、廣義表((a),((b),c),(((d))))的長度是(),深度是()0

9、設(shè)廣義表S=((a,b),(c,d)),GetHeat⑸和GetTail⑸是取廣義表的表頭和表尾函數(shù)。則

GetHeat(GetTail(S))=(),GetTail(GetHeat(S))=()。

10、設(shè)廣義表S=(a,b,(c,d),(e,(f,g))),GetHeat(S)和GetTail(S)是取廣義表的表頭和表

尾函數(shù)。則GetHeat(GetTail(GetHeat(GetTail(GetTail(S)))))=()

11、二維數(shù)組a[4][5][6](下標(biāo)從0開始計，a有N*5*6個元素)，每個元素的長度是2,

則a[2][3][4]的地址是()。(設(shè)a[0][0][0]的地址是1000,數(shù)據(jù)以行為主方式存儲)

12、設(shè)有二維數(shù)組A[0..9,0..19],其每個元素占兩個字節(jié)，第一個元素的存儲地址為100,

若按列優(yōu)先順序存儲，則元素A[6,6]存儲地址為()。

13、己知三對角矩陣AE1..9,1..9]的每個元素占2個單元，現(xiàn)將其三條對角線上的元素逐

行存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[7,8]的地址為()。

14、廣義表A=(((a,b),(c,d,e))),取出A中的原子e的操作是()。

15、設(shè)廣義表A(((),(a,(b),c))),JU!)head(tail(head(tai1(head(A))))=()。

三、問答題與算法題

1、給出C語言的三維數(shù)組A[m][n][s]地址計算公式。

。120…0、

Clf?Cl22。23???0

2、設(shè)有三對角矩陣A,將其三條對角線上的元素逐行

nXn=0a32%3…0

???????????????

、000

地存儲到向量B[O...3n-3]中,使得B[k]=aij,求:

(1)用i,j表示k的下標(biāo)變換公式。

(2)用k表示i,j的下標(biāo)變換公式。

3、設(shè)二維數(shù)組A5X6的每個元素占4個字節(jié)，已知LocSooAlOOO,A共占多少個字節(jié)？A的

終端結(jié)點A45的起始地位為何？按行和按列優(yōu)先存儲時，A25的起始地址分別為何？

4、己知一個稀疏矩陣如下圖所示:

[-0400000-i

000-3001

8000000

0005000

0-700020

-000600o-

(1)寫出它的三元組順序存儲表示；

⑵給出它的行邏輯鏈接的順序存儲表示;

5、畫出下列廣義表的圖形表示：

(1)A=((a,b),(c,d))

(2)B=(a,(b,(c,d)),(e))

6、畫出廣義表LS=((),(e),(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。

7,畫出廣義表LS=(((b,c),d),(a),((a),((b,c),d)),e,())的具有共享結(jié)構(gòu)的存儲表示。

8、設(shè)廣義表LS=(soldier,(teacher,student),(worker,farmer)),用取表頭函數(shù)GetHead()和

取表尾函數(shù)GetTail()分離出原子student。

9、畫出下列矩陣的卜字鏈表

‘0280、

7009

0300

、2062,

10、設(shè)任意n個整數(shù)存放于數(shù)組A(l:n)中，試編寫程序，將所有正數(shù)排在所有負(fù)數(shù)前面(要

求算法復(fù)雜性為0(n))。

第六章樹和二叉樹

一、選擇題

1、設(shè)高度為h的二叉樹只有度為0和2的結(jié)點，則此類二叉樹的結(jié)點數(shù)至少有(B)

個，至多有(E)個。

A)2h；B)2h-1；C)2h+l；0)2^'；E)2h-1；F)2h+lo

2、高度為h的完全二叉樹至少有(D)個結(jié)點，至多有(B)個結(jié)點。

A)2h；B)2h-1；C)2h+1；D)2h-1?

3、具有n個結(jié)點的滿二叉樹有()個葉結(jié)點。

A)n/2；B)(n-l)/2；C)(n+l)/2；D)n/2+l?

4、一棵具有n個葉結(jié)點的哈夫曼樹，共有()個結(jié)點。

A)2nB)2n-1C)2n+lD)2”“；

5、一棵具有25個葉結(jié)點的完全二叉樹最多