數(shù)據(jù)結(jié)構(gòu)期末考試試題與答案

大學(xué)理學(xué)院數(shù)學(xué)系信息與計(jì)算科學(xué)專業(yè)《數(shù)據(jù)結(jié)構(gòu)》期末考試試題及答案(2003-2004學(xué)年第2學(xué)期)單項(xiàng)選擇題1．對(duì)于一個(gè)算法，當(dāng)輸入非法數(shù)據(jù)時(shí)，也要能作出相應(yīng)的處理，這種要求稱為（）。(A)、正確性(B).可行性(C).健壯性(D).輸入性2．設(shè)S為C語言的語句,計(jì)算機(jī)執(zhí)行下面算法時(shí)，算法的時(shí)間復(fù)雜度為（）。for(i=n-1；i>=0；i--)for(j=0；j<i；j++)S；(A)、n2(B).O(nlgn)(C).O(n)(D).O(n2)3．折半查找法適用于（）。（A）、有序順序表（B）、有序單鏈表（C）、有序順序表和有序單鏈表都可以（D）、無限制4．順序存儲(chǔ)結(jié)構(gòu)的優(yōu)勢(shì)是（）。（A）、利于插入操作（B）、利于刪除操作（C）、利于順序訪問（D）、利于隨機(jī)訪問5．深度為k的完全二叉樹，其葉子結(jié)點(diǎn)必在第（）層上。（A）、k-1（B）、k（C）、k-1和k（D）、1至k6．具有60個(gè)結(jié)點(diǎn)的二叉樹，其葉子結(jié)點(diǎn)有12個(gè)，則度過1的結(jié)點(diǎn)數(shù)為（）（A）、11（B）、13（C）、48（D）、377．圖的Depth-FirstSearch(DFS)遍歷思想實(shí)際上是二叉樹（）遍歷方法的推廣。（A）、先序（B）、中序（C）、后序（D）、層序8．在下列鏈隊(duì)列Q中，元素a出隊(duì)的操作序列為（）bbcd∧afrontrearQ（A）、p=Q.front->next;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;9．Huffman樹的帶權(quán)路徑長(zhǎng)度WPL等于（）（A）、除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)權(quán)值之和（B）、所有結(jié)點(diǎn)權(quán)值之和（C）、各葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（D）、根結(jié)點(diǎn)的值10．線索二叉鏈表是利用（）域存儲(chǔ)后繼結(jié)點(diǎn)的地址。（A）、lchild（B）、data（C）、rchild（D）、root二、填空題邏輯結(jié)構(gòu)決定了算法的，而存儲(chǔ)結(jié)構(gòu)決定了算法的。棧和隊(duì)列都是一種的線性表，棧的插入和刪除只能在進(jìn)行。線性表（a1,a2,…,an）的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)每個(gè)單元的長(zhǎng)度為L(zhǎng)，元素ai的存儲(chǔ)地址LOC(ai)為已知一雙向鏈表如下(指針域名為next和prior)：yyxeep現(xiàn)將p所指的結(jié)點(diǎn)插入到x和y結(jié)點(diǎn)之間，其操作步驟為：；；；；5．n個(gè)結(jié)點(diǎn)無向完全圖的的邊數(shù)為，n個(gè)結(jié)點(diǎn)的生成樹的邊數(shù)為。6．已知一有向無環(huán)圖如下：BABACDFEG任意寫出二種拓?fù)渑判蛐蛄校?、?．已知二叉樹的中序遍歷序列為BCA，后序遍歷序列為CBA，則該二叉樹的先序遍歷序列為，層序遍歷序列為。三、應(yīng)用題設(shè)散列函數(shù)H(k)=k%13,設(shè)關(guān)鍵字系列為{22,12,24,6,45,7,8,13,21},要求用線性探測(cè)法處理沖突。(6分)(1)構(gòu)造HASH表。(2)分別求查找成功和不成功時(shí)的平均查找長(zhǎng)度。給定表（19,14,22,15,20,21,56,10）.（8分）按元素在表中的次序，建立一棵二叉排序樹對(duì)(1)中所建立的二叉排序樹進(jìn)行中序遍歷，寫出遍歷序列。畫出對(duì)(2)中的遍歷序列進(jìn)行折半查找過程的判定樹。已知二個(gè)稀疏矩陣A和B的壓縮存儲(chǔ)三元組表如下：ABijVijV13-525224633725241342-152-9529558寫出A-B壓縮存儲(chǔ)的三元組表。（5分）已知一維數(shù)組中的數(shù)據(jù)為（18,12,25,53,18）,試寫出插入排序（升序）過程。并指出具有n個(gè)元素的插入排序的時(shí)間復(fù)雜度是多少？(5分)已知一網(wǎng)絡(luò)的鄰接矩陣如下，求從頂點(diǎn)A開始的最小生成樹。(8分，要有過程)ABCDEF（1）求從頂點(diǎn)A開始的最小生成樹。（2）分別畫出以A為起點(diǎn)的DFS生成樹和BFS生成樹。6．已知數(shù)據(jù)六個(gè)字母及在通信中出現(xiàn)頻率如下表：ABCDEF0.150.150.10.10.20.3把這些字母和頻率作為葉子結(jié)點(diǎn)及權(quán)值，完成如下工作(7分，要有過程)。畫出對(duì)應(yīng)的Huffman樹。計(jì)算帶權(quán)路徑長(zhǎng)度WPL。求A、B、C、D、E、F的Huffman編碼。已知有如下的有向網(wǎng)：25325364106122AEBEBDCDC求頂點(diǎn)A到其它各頂點(diǎn)的最短路徑（采用Dijkstra算法，要有過程）。（6分）設(shè)計(jì)題（30分，每題10分,用C語言寫出算法，做在答題紙上）已知線性表（a1,a2,…,an）以順序存儲(chǔ)結(jié)構(gòu)為存儲(chǔ)結(jié)構(gòu)，其類型定義如下：#defineLIST_INIT_SIZE100//順序表初始分配容量typedefstruct{Elemtype*elem;//順序存儲(chǔ)空間基址intlength;//當(dāng)前長(zhǎng)度（存儲(chǔ)元素個(gè)數(shù)）}SqList;設(shè)計(jì)一個(gè)算法，刪除其元素值為x的結(jié)點(diǎn)（假若x是唯一的）。并求出其算法的平均時(shí)間復(fù)雜度。其算法函數(shù)頭部如下：StatusListDelete(Sqlist&L,Elemtypex){……}anan…a2a1其中結(jié)點(diǎn)定義如下：toptypedefstruct{Elemtype*base;//棧底指針Elemtype*top;//棧頂指針}Stack;設(shè)計(jì)算法，將棧頂元素出棧并存入e中．base3．設(shè)二叉鏈樹的類型定義如下：typedefintElemtype;typedefstructnode{Elemtypedata;structnode*lchild,*rchild;}BinNode,*BinTree;試寫出求該二叉樹葉子結(jié)點(diǎn)數(shù)的算法:StatusCountLeaves(BinTree&root,int&n){//nisthenumberofleaves……}答案：選擇題（每題1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C填空題設(shè)計(jì)、實(shí)現(xiàn)特殊、棧頂LOC（a1）+(i-1)*Lp->next=q->next;q->next->prior=p;q->next=p;p->prior=q;n(n-1)/2、n-1ADCBFEG、ABCDEFFGABC、ABC應(yīng)用題1（1）Hash表（4分）地址0123456789101112關(guān)鍵安132164572282412探測(cè)次數(shù)171231311（2）查找成功的平均查找長(zhǎng)度：（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找長(zhǎng)度：（1分）（2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、構(gòu)造（3分）191914221015205621(2)、1014151920212256（2分）（3）、（3分）3、(5分，每行0.5)ijv13-524633741342-152185584、初始關(guān)鍵字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分AB1C325D4EF（2）4分6、(1)3分EFEFABCD（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10（3分）12、A-B：（A、B）1分A-C：（A、D、C）2分A-D：（A、D）1分A-E：（A、D、E）2分三，設(shè)計(jì)題（20分）1、(10分)StatusListDelete(Sqlist&L,ElemTypex){inti,j;for(i=0;i<L->length;i++)if(L->elem[i]==x)break;if(i=L->length)returnERROR;for(j=i;j<L->lengthi-1;j++)L->elem[j]=L->elem[j+1];L->length--;}（8分）平均時(shí)間復(fù)雜度：（2分）設(shè)元素個(gè)數(shù)記為n，則平均時(shí)間復(fù)雜度為：2（10分）voidpop(Stack&S,Elemtype&e){if(S.top==S.base)returnERROR;S.top--;e=*s.top;}2、（10分）voidCountLeaves(BinTreeT,int&n){if(T){if((!(T->lchild)&&!(T->rchild))n++;CountLeaves(T->lchild,n);CountLeaves(T->rchild,n);}}習(xí)題1

一、單項(xiàng)選擇題

1.數(shù)據(jù)結(jié)構(gòu)是指（）。

A.數(shù)據(jù)元素的組織形式B.數(shù)據(jù)類型

C.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)定義

2.數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器表示時(shí)，物理地址與邏輯地址不相同的，稱之為（）。

A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)

C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D.順序存儲(chǔ)結(jié)構(gòu)

3.樹形結(jié)構(gòu)是數(shù)據(jù)元素之間存在一種（）。

A.一對(duì)一關(guān)系B.多對(duì)多關(guān)系

C.多對(duì)一關(guān)系D.一對(duì)多關(guān)系

4.設(shè)語句x++的時(shí)間是單位時(shí)間，則以下語句的時(shí)間復(fù)雜度為（）。

for(i=1;i<=n;i++)

for(j=i;j<=n;j++)

x++;

A.O(1)B.O()C.O(n)D.O()

5.算法分析的目的是（1），算法分析的兩個(gè)主要方面是（2）。

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

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

（2）A.空間復(fù)雜度和時(shí)間復(fù)雜度B.正確性和簡(jiǎn)明性

C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性

6.計(jì)算機(jī)算法指的是（1），它具備輸入，輸出和（2）等五個(gè)特性。

（1）A.計(jì)算方法B.排序方法

C.解決問題的有限運(yùn)算序列D.調(diào)度方法

（2）A.可行性，可移植性和可擴(kuò)充性B.可行性，確定性和有窮性

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

7.數(shù)據(jù)在計(jì)算機(jī)有鏈?zhǔn)胶晚樞騼煞N存儲(chǔ)方式，在存儲(chǔ)空間使用的靈活性上，鏈?zhǔn)酱鎯?chǔ)比順序存儲(chǔ)要（）。

A.低B.高C.相同D.不好說

8.數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程出現(xiàn)是在（）年。

A.1946B.1953C.1964D.1968

9.數(shù)據(jù)結(jié)構(gòu)只是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，這種觀點(diǎn)（）。

A.正確B.錯(cuò)誤

C.前半句對(duì)，后半句錯(cuò)D.前半句錯(cuò)，后半句對(duì)

10.計(jì)算機(jī)部數(shù)據(jù)處理的基本單位是（）。

A.數(shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)項(xiàng)D.數(shù)據(jù)庫(kù)

二、填空題

1.數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，分別是____________?__和_________________。

2.數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是________________、__________________、__________________和__________________。

3.線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的，非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是__________________的。

4.一個(gè)算法的效率可分為__________________效率和__________________效率。

5.在樹型結(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)可以__________________。

6.在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以__________________。

7.線性結(jié)構(gòu)中元素之間存在__________________關(guān)系；樹型結(jié)構(gòu)中元素之間存在__________________關(guān)系；圖型結(jié)構(gòu)中元素之間存在__________________關(guān)系。

8.下面程序段的時(shí)間復(fù)雜度是__________________。

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=0;

9.下面程序段的時(shí)間復(fù)雜度是__________________。

i=s=0;

while(s<n)

{i++;

s+=i;

}

10.下面程序段的時(shí)間復(fù)雜度是__________________。

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

s+=B[i][j];

sum=s;

11.下面程序段的時(shí)間復(fù)雜度是__________________。

i=1;

while(i<=n)

i=i*3;

12.衡量算確性的標(biāo)準(zhǔn)通常是____________________________________。

13.算法時(shí)間復(fù)雜度的分析通常有兩種方法，即___________和___________的方法，通常我們對(duì)算法求時(shí)間復(fù)雜度時(shí)，采用后一種方法。

三、求下列程序段的時(shí)間復(fù)雜度。

1.x=0;

for(i=1;i<n;i++)

for(j=i+1;j<=n;j++)

x++;

2.x=0;

for(i=1;i<n;i++)

for(j=1;j<=n-i;j++)

x++;

3.inti,j,k;

for(i=0;i<n;i++)

for(j=0;j<=n;j++)

{c[i][j]=0;

for(k=0;k<n;k++)

c[i][j]=a[i][k]*b[k][j]

}

4.i=n-1;

while((i>=0)&&A[i]!=k))

j--;

return(i);

5.fact(n)

{if(n<=1)

return(1);

else

return(n*fact(n-1));

}

習(xí)題1參考答案

一、單項(xiàng)選擇題

1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B

二、填空題

1.線性結(jié)構(gòu)，非線性結(jié)構(gòu)

2.集合，線性，樹，圖

3.一對(duì)一，一對(duì)多或多對(duì)多

4.時(shí)間，空間

5.前趨，一，后繼，多

6.有多個(gè)

7.一對(duì)一，一對(duì)多，多對(duì)多

8.O()

9.O()

10.O()

11.O(logn)

12.程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。

13.事后統(tǒng)計(jì)，事前估計(jì)

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

1.O()2.O()3.O(n)4.O(n)5.O(n)

習(xí)題2

一、單項(xiàng)選擇題

1.線性表是________。

A．一個(gè)有限序列，可以為空B．一個(gè)有限序列，不可以為空

C．一個(gè)無限序列，可以為空D．一個(gè)無限序列，不可以為空

2.在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(0<=i<=n)時(shí)，需向前移動(dòng)個(gè)元素。

A．n-iB．n-i+lC．n-i-1D．i

3.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址________。

A．必須是連續(xù)的B．一定是不連續(xù)的

C．部分地址必須是連續(xù)的D．連續(xù)與否均可以

4.從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較________個(gè)元素結(jié)點(diǎn)。

A．n/2B．nC．（n+1）/2D．（n-1）/2

5.在雙向循環(huán)鏈表中，在p所指的結(jié)點(diǎn)之后插入s指針?biāo)傅慕Y(jié)點(diǎn)，其操作是____。

A．p->next=s;s->prior=p;

p->next->prior=s;s->next=p->next;

B．s->prior=p;s->next=p->next;

p->next=s;p->next->prior=s;

C．p->next=s;p->next->prior=s;

s->prior=p;s->next=p->next;

D．s->prior=p;s->next=p->next;

p->next->prior=s;p->next=s;

6.設(shè)單鏈表中指針p指向結(jié)點(diǎn)m，若要?jiǎng)h除m之后的結(jié)點(diǎn)（若存在），則需修改指針的操作為________。

A．p->next=p->next->next;B．p=p->next;

C．p=p->next->next;D．p->next=p;

7.在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0<i<n+l)之前插入一個(gè)新元素時(shí)，需向后移動(dòng)______個(gè)元素。

A．n-iB．n-i+lC．n-i-1D．i

8.在一個(gè)單鏈表中，已知q結(jié)點(diǎn)是p結(jié)點(diǎn)的前趨結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則須執(zhí)行

A．s->next=p->next;p->next=s

B．q->next=s;s->next=p

C．p->next=s->next;s->next=p

D．p->next=s;s->next=q

9.以下關(guān)于線性表的說法不正確的是______。

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

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

C．線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。

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

10.線性表的順序存儲(chǔ)結(jié)構(gòu)是一種_______的存儲(chǔ)結(jié)構(gòu)。

A．隨機(jī)存取B．順序存取C．索引存取D．散列存取

11.在順序表中，只要知道_______，就可在相同時(shí)間求出任一結(jié)點(diǎn)的存儲(chǔ)地址。

A．基地址B．結(jié)點(diǎn)大小

C．向量大小D．基地址和結(jié)點(diǎn)大小

12.在等概率情況下，順序表的插入操作要移動(dòng)______結(jié)點(diǎn)。

A．全部B．一半

C．三分之一D．四分之一

13.在______運(yùn)算中，使用順序表比鏈表好。

A．插入B．刪除

C．根據(jù)序號(hào)查找D．根據(jù)元素值查找

14.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并保持該表有序的時(shí)間復(fù)雜度是_______。

A．O(1)B．O(n)

C．O(n2)D．O(log2n)

15.設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳,B,C,D,E,下列是不可能的出棧序列__________。

A．A,B,C,D,EB．B,C,D,E,A

C．E,A,B,C,DD．E,D,C,B,A

16.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為______。

A．top不變B．top=0C．top--D．top++

17.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行______。

A．hs->next=s;

B．s->next=hs;hs=s;

C．s->next=hs->next;hs->next=s;

D．s->next=hs;hs=hs->next;

18.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)滿的條件為________。

A．rear％n==frontB．（front+l）％n==rear

C．rear％n-1==frontD．(rear+l)％n==front

19.在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為________。

A．rear％n==frontB．front+l=rear

C．rear==frontD．(rear+l)％n=front

20.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的操作為________。

A．front=front->nextB．rear=rear->next

C．rear=front->nextD．front=rear->next

二、填空題

1.線性表是一種典型的_________結(jié)構(gòu)。

2.在一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素之前插入一個(gè)元素，需要后移____個(gè)元素。

3.順序表中邏輯上相鄰的元素的物理位置________。

4.要從一個(gè)順序表刪除一個(gè)元素時(shí)，被刪除元素之后的所有元素均需_______一個(gè)位置，移動(dòng)過程是從_______向_______依次移動(dòng)每一個(gè)元素。

5.在線性表的順序存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的；在線性表的存儲(chǔ)中，元素之間的邏輯關(guān)系是通過_______決定的。

6.在雙向鏈表中，每個(gè)結(jié)點(diǎn)含有兩個(gè)指針域，一個(gè)指向_______結(jié)點(diǎn)，另一個(gè)指向_______結(jié)點(diǎn)。

7.當(dāng)對(duì)一個(gè)線性表經(jīng)常進(jìn)行存取操作，而很少進(jìn)行插入和刪除操作時(shí)，則采用_______存儲(chǔ)結(jié)構(gòu)為宜。相反，當(dāng)經(jīng)常進(jìn)行的是插入和刪除操作時(shí)，則采用_______存儲(chǔ)結(jié)構(gòu)為宜。

8.順序表中邏輯上相鄰的元素，物理位置_______相鄰，單鏈表中邏輯上相鄰的元素，物理位置_______相鄰。

9.線性表、棧和隊(duì)列都是_______結(jié)構(gòu)，可以在線性表的______位置插入和刪除元素；對(duì)于棧只能在_______位置插入和刪除元素；對(duì)于隊(duì)列只能在_______位置插入元素和在_______位置刪除元素。

10.根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表可分為_________和_______；而根據(jù)指針的聯(lián)接方式，鏈表又可分為________和_________。

11.在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是________。

12.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為______，在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為_______。

13.對(duì)于一個(gè)棧作進(jìn)棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，作退棧運(yùn)算時(shí)，應(yīng)先判別棧是否為_______，當(dāng)棧中元素為m時(shí)，作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢，則說明棧的可用最大容量為_______。為了增加存空間的利用率和減少發(fā)生上溢的可能性，由兩個(gè)棧共享一片連續(xù)的存空間時(shí)，應(yīng)將兩棧的_______分別設(shè)在這片存空間的兩端，這樣只有當(dāng)_______時(shí)才產(chǎn)生上溢。

14.設(shè)有一空棧，現(xiàn)有輸入序列1，2，3，4，5，經(jīng)過push,push,pop,push,pop,push,push后，輸出序列是_________。

15.無論對(duì)于順序存儲(chǔ)還是鏈?zhǔn)酱鎯?chǔ)的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜度均相同為__________。

三、簡(jiǎn)答題

1.描述以下三個(gè)概念的區(qū)別：頭指針，頭結(jié)點(diǎn)，表頭結(jié)點(diǎn)。

2.線性表的兩種存儲(chǔ)結(jié)構(gòu)各有哪些優(yōu)缺點(diǎn)？

3.對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，如果有n個(gè)線性表同時(shí)并存，而且在處理過程中各表的長(zhǎng)度會(huì)動(dòng)態(tài)發(fā)生變化，線性表的總數(shù)也會(huì)自動(dòng)改變，在此情況下，應(yīng)選用哪一種存儲(chǔ)結(jié)構(gòu)？為什么？

4.對(duì)于線性表的兩種存儲(chǔ)結(jié)構(gòu)，若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素，應(yīng)選用何種存儲(chǔ)結(jié)構(gòu)？試說明理由。

5.在單循環(huán)鏈表中設(shè)置尾指針比設(shè)置頭指針好嗎？為什么?

6.假定有四個(gè)元素A,B,C,D依次進(jìn)棧，進(jìn)棧過程中允許出棧，試寫出所有可能的出棧序列。

7.什么是隊(duì)列的上溢現(xiàn)象？一般有幾種解決方法，試簡(jiǎn)述之。

8.下述算法的功能是什么?

LinkList*Demo(LinkList*L)

{//L是無頭結(jié)點(diǎn)的單鏈表

LinkList*q,*p;

if(L&&L->next)

{q=L;L=L->next;p=L;

while(p->next)

p=p->next;

p->next=q;q->next=NULL;

}

return(L);

}

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

1.設(shè)計(jì)在無頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)的算法。

2.在單鏈表上實(shí)現(xiàn)線性表的求表長(zhǎng)ListLength(L)運(yùn)算。

3.設(shè)計(jì)將帶表頭的鏈表逆置算法。

4.假設(shè)有一個(gè)帶表頭結(jié)點(diǎn)的鏈表，表頭指針為head，每個(gè)結(jié)點(diǎn)含三個(gè)域：data,next和prior。其中data為整型數(shù)域，next和prior均為指針域?，F(xiàn)在所有結(jié)點(diǎn)已經(jīng)由next域連接起來，試編一個(gè)算法，利用prior域（此域初值為NULL）把所有結(jié)點(diǎn)按照其值從小到大的順序起來。

5.已知線性表的元素按遞增順序排列，并以帶頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)結(jié)構(gòu)。試編寫一個(gè)刪除表中所有值大于min且小于max的元素（若表中存在這樣的元素）的算法。

6.已知線性表的元素是無序的，且以帶頭結(jié)點(diǎn)的單鏈表作為存儲(chǔ)結(jié)構(gòu)。設(shè)計(jì)一個(gè)刪除表中所有值小于max但大于min的元素的算法。

7.假定用一個(gè)單循環(huán)鏈表來表示隊(duì)列（也稱為循環(huán)隊(duì)列），該隊(duì)列只設(shè)一個(gè)隊(duì)尾指針，不設(shè)隊(duì)首指針，試編寫下列各種運(yùn)算的算法：

（1）向循環(huán)鏈隊(duì)列插入一個(gè)元素值為x的結(jié)點(diǎn)；

（2）從循環(huán)鏈隊(duì)列中刪除一個(gè)結(jié)點(diǎn)。

8.設(shè)順序表L是一個(gè)遞減有序表，試寫一算法，將x插入其后仍保持L的有序性。

習(xí)題2參考答案

一、單項(xiàng)選擇題

1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A

二、填空題

1．線性

2．n-i+1

3．相鄰

4．前移，前，后

5．物理存儲(chǔ)位置，鏈域的指針值

6．前趨，后繼

7．順序，

8．一定，不一定

9．線性，任何，棧頂，隊(duì)尾，隊(duì)頭

10．單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表

11．使空表和非空表統(tǒng)一；算法處理一致

12．O(1)，O(n)

13．棧滿，棧空，m，棧底，兩個(gè)棧的棧頂在棧空間的某一位置相遇

14．2、3

15．O(1)

三、簡(jiǎn)答題

1．頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。

2．線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在存儲(chǔ)結(jié)構(gòu)中存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。

3．應(yīng)選用存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。

4．應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。

5．設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來表示單循環(huán)鏈表可以使得查找鏈表的開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear->next->next和rear,查找時(shí)間都是O(1)。若用頭指針來表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。

6．共有14種可能的出棧序列，即為：

ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA

7．在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大小）為maxnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。

一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：

（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。

（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決：

第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。

第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。

第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。

8．該算法的功能是：將開始結(jié)點(diǎn)摘下到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來的第二個(gè)結(jié)點(diǎn)成為新的開始結(jié)點(diǎn)，返回新鏈表的頭指針。

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

1．算法思想為：

（1）應(yīng)判斷刪除位置的合法性，當(dāng)i<0或i>n-1時(shí)，不允許進(jìn)行刪除操作；

（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：

（3）當(dāng)０<i<n時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：

delete(LinkList*q,inti)

{//在無頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn)

LinkList*p,*s;

intj;

if(i<0)

printf("Can'tdelete");

elseif(i==0)

{s=q;

q=q->next;

free(s);

}

else

{j=0;s=q;

while((j<i)&&(s!=NULL))

{p=s;

s=s->next;

j++;

}

if(s==NULL)

printf("Cant'tdelete");

else

{p->next=s->next;

free(s);

}

}

}

2．由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：

intListLength(LinkList*L)

{//求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng)

intlen=0;

ListList*p;

p=L;

while(p->next!=NULL)

{p=p->next;

len++;

}

return(len);

}

3．設(shè)單循環(huán)鏈表的頭指針為head，類型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q->next=s;操作即可，算法描述如下：

voidinvert(LinkList*head)

{//逆置head指針?biāo)赶虻膯窝h(huán)鏈表

linklist*p,*q,*s;

q=head;

p=head->next;

while(p!=head)//當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置

{s=q;

q=p;

p=p->next;

q->next=s;

}

p->next=q;

}

4．定義類型LinkList如下：

typedefstructnode

{intdata;

structnode*next,*prior;

}LinkList;

此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：

insert(LinkList*head)

{LinkList*p,*s,*q;

p=head->next;//p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn)

while(p!=NULL)

{s=head;//s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn)

q=head->prior;//q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn)

while((q!=NULL)&&(p->data>q->data))//查找插入結(jié)點(diǎn)p的合適的插入位置

{s=q;

q=q->prior;

}

s->prior=p;

p->prior=q;//結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間

p=p->next;

}

}

5．算法描述如下：

delete(LinkList*head,intmax,intmin)

{linklist*p,*q;

if(head!=NULL)

{q=head;

p=head->next;

while((p!=NULL)&&(p->data<=min))

{q=p;

p=p->next;

}

while((p!=NULL)&&(p->data<max))

p=p->next;

q->next=p;

}

}

6．算法描述如下：

delete(LinkList*head,intmax,intmin)

{LinkList*p,*q;

q=head;

p=head->next;

while(p!=NULL)

if((p->data<=min)||(p->data>=max))

{q=p;

p=p->next;

}

else

{q->next=p->next;

free(p);

p=q->next;

}

}

7．本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：

（1）插入（即入隊(duì)）算法：

insert(LinkList*rear,elemtypex)

{//設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素

LinkList*p;

p=(LinkList*)malloc(sizeof(LinkList));

if(rear==NULL)//如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn)

{rear=p;

rear->next=p;//成循環(huán)鏈表

}

else//否則在隊(duì)尾插入p結(jié)點(diǎn)

{p->next=rear->next;

rear->next=p;

rear=p;

}

}

（2）刪除（即出隊(duì)）算法：

delete(LinkList*rear)

{//設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear

if(rear==NULL)//空隊(duì)

printf("underflow\n");

if(rear->next==rear)//隊(duì)中只有一個(gè)結(jié)點(diǎn)

rear=NULL;

else

rear->next=rear->next->next;//rear->next指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)

}

8．只要從終端結(jié)點(diǎn)開始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：

intInsertDecreaseList(SqList*L,elemtypex)

{inti;

if((*L).len>=maxlen)

{printf(“overflow");

return(0);

}

for(i=(*L).len;i>0&&(*L).elem[i-1]<x;i--)

(*L).elem[i]=(*L).elem[i-1];//比較并移動(dòng)元素

(*L).elem[i]=x;

(*L).len++;

return(1);

}

習(xí)題3

一、單項(xiàng)選擇題

1.空串與空格字符組成的串的區(qū)別在于（）。

A.沒有區(qū)別B.兩串的長(zhǎng)度不相等

C.兩串的長(zhǎng)度相等D.兩串包含的字符不相同

2.一個(gè)子串在包含它的主串中的位置是指（）。

A.子串的最后那個(gè)字符在主串中的位置

B.子串的最后那個(gè)字符在主串中首次出現(xiàn)的位置

C.子串的第一個(gè)字符在主串中的位置

D.子串的第一個(gè)字符在主串中首次出現(xiàn)的位置

3.下面的說法中，只有（）是正確的。

A.字符串的長(zhǎng)度是指串中包含的字母的個(gè)數(shù)

B.字符串的長(zhǎng)度是指串中包含的不同字符的個(gè)數(shù)

C.若T包含在S中，則T一定是S的一個(gè)子串

D.一個(gè)字符串不能說是其自身的一個(gè)子串

4.兩個(gè)字符串相等的條件是（）。

A.兩串的長(zhǎng)度相等

B.兩串包含的字符相同

C.兩串的長(zhǎng)度相等，并且兩串包含的字符相同

D.兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同

5.若SUBSTR（S，i，k）表示求S中從第i個(gè)字符開始的連續(xù)k個(gè)字符組成的子串的操作，則對(duì)于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。

A.“ijing”B.“jing＆”

C.“ingNa”D.“ing＆N”

6.若INDEX（S，T）表示求T在S中的位置的操作，則對(duì)于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。

A.2B.3C.4D.5

7.若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對(duì)于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。

A.“Nanjing＆Shanghai”B.“Nanjing＆Nanjing”

C.“ShanghaiNanjing”D.“Shanghai＆Nanjing”

8.在長(zhǎng)度為n的字符串S的第i個(gè)位置插入另外一個(gè)字符串，i的合法值應(yīng)該是（）。

A.i＞0B.i≤n

C.1≤i≤nD.1≤i≤n+1

9.字符串采用結(jié)點(diǎn)大小為1的鏈表作為其存儲(chǔ)結(jié)構(gòu)，是指（）。

A.鏈表的長(zhǎng)度為1

B.鏈表中只存放1個(gè)字符

C.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中不僅只存放了一個(gè)字符

D.鏈表的每個(gè)鏈結(jié)點(diǎn)的數(shù)據(jù)域中只存放了一個(gè)字符

二、填空題

1.計(jì)算機(jī)軟件系統(tǒng)中，有兩種處理字符串長(zhǎng)度的方法：一種是___________，第二種是___________________。

2.兩個(gè)字符串相等的充要條件是_____________________和___________________。

3.設(shè)字符串S1=“ABCDEF”，S2=“PQRS”，則運(yùn)算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。

4.串是指___________________。

5.空串是指___________________，空格串是指___________________。

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

1.設(shè)有一個(gè)長(zhǎng)度為s的字符串，其字符順序存放在一個(gè)一維數(shù)組的第1至第s個(gè)單元中（每個(gè)單元存放一個(gè)字符）?，F(xiàn)要求從此串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串，m<s，t<(s-m)，并將刪除后的結(jié)果復(fù)制在該數(shù)組的第s單元以后的單元中，試設(shè)計(jì)此刪除算法。

2.設(shè)s和t是表示成單鏈表的兩個(gè)串，試編寫一個(gè)找出s中第1個(gè)不在t中出現(xiàn)的字符（假定每個(gè)結(jié)點(diǎn)只存放1個(gè)字符）的算法。

習(xí)題3參考答案

一、單項(xiàng)選擇題

1．B2．D3．C4．D5．B6．C7．D8．C9．D

二、填空題

1.固定長(zhǎng)度，設(shè)置長(zhǎng)度指針

2.兩個(gè)串的長(zhǎng)度相等，對(duì)應(yīng)位置的字符相等

3.“BCDEDE”

4.含n個(gè)字符的有限序列（n≥0）

5.不含任何字符的串，僅含空格字符的字符串

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

1．算法描述為：

intdelete(r,s,t,m)//從串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串

charr[];

ints,t,m;

{inti,j;

for(i=1;i<=m;i++)

r[s+i]=r[i];

for(j=m+t-i;j<=s;j++)

r[s-t+j]=r[j];

return(1);

}//delete

2．算法思想為：

（1）鏈表s中取出一個(gè)字符；將該字符與單鏈表t中的字符依次比較；

（2）當(dāng)t中有與從s中取出的這個(gè)字符相等的字符，則從t中取下一個(gè)字符重復(fù)以上比較；

（3）當(dāng)t中沒有與從s中取出的這個(gè)字符相等的字符，則算法結(jié)束。

設(shè)單鏈表類型為L(zhǎng)inkList；注意，此時(shí)類型LinkList中的data成分為字符類型。

LinkStringfind(s,t)

LinkString*s,*t;

{LinkString*ps,*pt;

ps=s;

while(ps!=NULL)

{pt=t;

while((pt!=NULL)&&(ps->data!=pt->data))

pt=pt->next;

if(pt==NULL)

ps=NULL;

else

{ps=ps->next;

s=ps;

}

}

returns;

}//find

習(xí)題4

一、單項(xiàng)選擇題

1.設(shè)二維數(shù)組A[0…m-1][0…n-1]按行優(yōu)先順序存儲(chǔ)在存中，第一個(gè)元素的地址為p，每個(gè)元素占k個(gè)字節(jié)，則元素aij的地址為（）。

A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*k

C.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k

2.已知二維數(shù)組A10×10中，元素a20的地址為560，每個(gè)元素占4個(gè)字節(jié)，則元素a10的地址為（）。

A.520B.522C.524D.518

3.若數(shù)組A[0…m][0…n]按列優(yōu)先順序存儲(chǔ)，則aij地址為（）。

A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]

C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]

4.若下三角矩陣An×n，按列順序壓縮存儲(chǔ)在數(shù)組Sa[0…(n+1)n/2]中，則非零元素aij的地址為（）。（設(shè)每個(gè)元素占d個(gè)字節(jié)）

A.[(j-1)*n-+i-1]*d

B.[(j-1)*n-+i]*d

C．[(j-1)*n-+i+1]*d

D．[(j-1)*n-+i-2]*d

5.設(shè)有廣義表D=(a,b,D)，其長(zhǎng)度為（），深度為（）。

A.無窮大B.3C.2D.5

6.廣義表A=（a），則表尾為（）。

A.aB.(())C.空表D.(a)

7.廣義表A=((x,(a,B)),(x,(a,B),y))，則運(yùn)算head(head(tail(A)))的結(jié)果為（）。

A.xB.(a,B)C.(x,(a,B))D.A

8.下列廣義表用圖來表示時(shí)，分支結(jié)點(diǎn)最多的是（）。

A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))

C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)

9.通常對(duì)數(shù)組進(jìn)行的兩種基本操作是（）。

A.建立與刪除B.索引和修改

C.查找和修改D.查找與索引

10.假定在數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器，存放該數(shù)組至少需要的單元數(shù)為（）。

A.80B.100C.240D.270

11.數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從1到8，列下標(biāo)j從1到10，從首地址SA開始連續(xù)存放在存儲(chǔ)器，該數(shù)組按行存放時(shí)，元素A[8][5]的起始地址為（）。

A.SA+141B.SA+144C.SA+222D.SA+225

12.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。

A.二維數(shù)組和三維數(shù)組B.三元組和散列

C.三元組和十字鏈表D.散列和十字鏈表

13.若采用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)（）。

A.正確B.不正確

14.一個(gè)廣義表的表頭總是一個(gè)（）。

A.廣義表B.元素C.空表D.元素或廣義表

15.一個(gè)廣義表的表尾總是一個(gè)（）。

A.廣義表B.元素C.空表D.元素或廣義表

16.數(shù)組就是矩陣，矩陣就是數(shù)組，這種說法（）。

A.正確B.錯(cuò)誤

C.前句對(duì)，后句錯(cuò)D.后句對(duì)

二、填空題

1.一維數(shù)組的邏輯結(jié)構(gòu)是______________，存儲(chǔ)結(jié)構(gòu)是______________；對(duì)于二維或多維數(shù)組，分為______________和______________兩種不同的存儲(chǔ)方式。

2.對(duì)于一個(gè)二維數(shù)組A[m][n]，若按行序?yàn)橹餍虼鎯?chǔ)，則任一元素A[i][j]相對(duì)于A[0][0]的地址為______________。

3.一個(gè)廣義表為(a,(a,b),d,e,((i,j),k))，則該廣義表的長(zhǎng)度為_____，深度為_____。

4.一個(gè)稀疏矩陣為，則對(duì)應(yīng)的三元組線性表為_____________。

5.一個(gè)n×n的對(duì)稱矩陣，如果以行為主序或以列為主序存入存，則其容量為______________。

6.已知廣義表A=((a,b,c),(d,e,f))，則運(yùn)算head(tail(tail(A)))=____________。

7.設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式以行序?yàn)橹餍虼鎯?chǔ)，a為第一個(gè)元素，其存儲(chǔ)地址為0，每個(gè)元素占有1個(gè)存儲(chǔ)地址空間，則a的地址為______________。

8.已知廣義表Ls=(a,(b,c,d),e)，運(yùn)用head和tail函數(shù)取出Ls中的原子b的運(yùn)算是______________。

9.三維數(shù)組R[c1…d1,c2…d2,c3…d3]共含有______________個(gè)元素。（其中：c1≤d1,c2≤d2,c3≤d3）

10.數(shù)組A[1…10，-2…6，2…8]以行優(yōu)先的順序存儲(chǔ)，設(shè)第一個(gè)元素的首地址是100，每個(gè)元素占3個(gè)存儲(chǔ)長(zhǎng)度的存儲(chǔ)空間，則元素A[5，0，7]的存儲(chǔ)地址為______________。

三、判斷題

1.數(shù)組可看作基本線性表的一種推廣，因此與線性表一樣，可以對(duì)它進(jìn)行插入、刪除等操作。（）

2.多維數(shù)組可以看作數(shù)據(jù)元素也是基本線性表的基本線性表。（）

3.以行為主序或以列為主序?qū)τ诙嗑S數(shù)組的存儲(chǔ)沒有影響。（）

4.對(duì)于不同的特殊矩陣應(yīng)該采用不同的存儲(chǔ)方式。（）

5.采用壓縮存儲(chǔ)之后，下三角矩陣的存儲(chǔ)空間可以節(jié)約一半。（）

6.在一般情況下，采用壓縮存儲(chǔ)之后，對(duì)稱矩陣是所有特殊矩陣中存儲(chǔ)空間節(jié)約最多的。（）

7.矩陣不僅是表示多維數(shù)組，而且是表示圖的重要工具。（）

8.距陣中的數(shù)據(jù)元素可以是不同的數(shù)據(jù)類型。（）

9.矩陣中的行列數(shù)往往是不相等的。（）

10.廣義表的表頭可以是廣義表，也可以是單個(gè)元素。（）

11.廣義表的表尾一定是一個(gè)廣義表。（）

12.廣義表的元素可以是子表，也可以是單元素。（）

13.廣義表不能遞歸定義。（）

14.廣義表實(shí)際上是基本線性表的推廣。（）

15.廣義表的組成元素可以是不同形式的元素。（）

習(xí)題4參考答案

一、單項(xiàng)選擇題

1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B

二、填空題

1.線性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序

2.i×n+j個(gè)元素位置

3.5，3

4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））

5.n×(n+1)/2

6.e

7.41

8.head(head(tail(Ls)))

9.（d-c+1）×（d-c+1）×（d-c+1）

10.913

三、判斷題

1.×2.√3.√4.√5.×6.×7.√8.×9.×10.√11.√12.√13.×14.√15.√

習(xí)題5

一、單項(xiàng)選擇題

1.在一棵度為3的樹中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)為（）個(gè)。

A.4B.5C.6D.7

2.假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。

A.15B.16C.17D.47

3.假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（）。

A.3B.4C.5D.6

4.在一棵二叉樹上第4層的結(jié)點(diǎn)數(shù)最多為（）。

A.2B.4C.6D.8

5.用順序存儲(chǔ)的方法將完全二叉樹中的所有結(jié)點(diǎn)逐層存放在數(shù)組中R[1..n]，結(jié)點(diǎn)R[i]若有左孩子，其左孩子的編號(hào)為結(jié)點(diǎn)（）。

A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]

6.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。

A.24B.48C.72D.53

7.線索二叉樹是一種（）結(jié)構(gòu)。

A.邏輯B.邏輯和存儲(chǔ)C.物理D.線性

8.線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（）。

A.p->lc=NULLB.p->ltag=1

C.p->ltag=1且p->lc=NULLD.以上都不對(duì)

9.設(shè)n,m為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷序列中n在m前的條件是（）。

A.n在m右方B.n在m左方

C.n是m的祖先D.n是m的子

10.如果F是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的前序就是F中結(jié)點(diǎn)的（）。

A.中序B.前序C.后序D.層次序

11.欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（）存儲(chǔ)結(jié)構(gòu)。

A.三叉鏈表B.廣義表C.二叉鏈表D.順序

12.下面敘述正確的是（）。

A.二叉樹是特殊的樹

B.二叉樹等價(jià)于度為2的樹

C.完全二叉樹必為滿二叉樹

D.二叉樹的左右子樹有次序之分

13.任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。

A.不發(fā)生改變B.發(fā)生改變

C.不能確定D.以上都不對(duì)

14.已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為（）。

A.1B.2C.3D.4

15.根據(jù)先序序列ABDC和中序序列DBAC確定對(duì)應(yīng)的二叉樹，該二叉樹（）。

A.是完全二叉樹B.不是完全二叉樹

C.是滿二叉樹D.不是滿二叉樹

二、判斷題

1.二叉樹中每個(gè)結(jié)點(diǎn)的度不能超過2，所以二叉樹是一種特殊的樹。（）

2.二叉樹的前序遍歷中，任意結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)之前。（）

3.線索二叉樹是一種邏輯結(jié)構(gòu)。（）

4.哈夫曼樹的總結(jié)點(diǎn)個(gè)數(shù)（多于1時(shí)）不能為偶數(shù)。（）

5.由二叉樹的先序序列和后序序列可以唯一確定一顆二叉樹。（）

6.樹的后序遍歷與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同。（）

7.根據(jù)任意一種遍歷序列即可唯一確定對(duì)應(yīng)的二叉樹。（）

8.滿二叉樹也是完全二叉樹。（）

9.哈夫曼樹一定是完全二叉樹。（）

10.樹的子樹是無序的。（）

三、填空題

1.假定一棵樹的廣義表表示為A（B（E），C（F（H，I，J），G），D），則該樹的度為_____，樹的深度為_____，終端結(jié)點(diǎn)的個(gè)數(shù)為______，單分支結(jié)點(diǎn)的個(gè)數(shù)為______，雙分支結(jié)點(diǎn)的個(gè)數(shù)為______，三分支結(jié)點(diǎn)的個(gè)數(shù)為_______，C結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_______，其孩子結(jié)點(diǎn)為_______和_______結(jié)點(diǎn)。

2.設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有_______個(gè)。

3.對(duì)于一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵________二叉樹時(shí)具有最小高度，即為_______，當(dāng)它為一棵單支樹具有_______高度，即為_______。

4.由帶權(quán)為3，9，6，2，5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng)度為___。

5.在一棵二叉排序樹上按_______遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。

6.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行存儲(chǔ)時(shí)，其二叉鏈表中的指針域的總數(shù)為_______個(gè)，其中_______個(gè)用于孩子結(jié)點(diǎn)，_______個(gè)空閑著。

7.在一棵二叉樹中，度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=______。

8.一棵深度為k的滿二叉樹的結(jié)點(diǎn)總數(shù)為_______，一棵深度為k的完全二叉樹的結(jié)點(diǎn)總數(shù)的最小值為_____，最大值為______。

9.由三個(gè)結(jié)點(diǎn)構(gòu)成的二叉樹，共有____種不同的形態(tài)。

10.設(shè)高度為h的二叉樹中只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為____。

11.一棵含有n個(gè)結(jié)點(diǎn)的k叉樹，______形態(tài)達(dá)到最大深度，____形態(tài)達(dá)到最小深度。

12.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i(1≤i≤n)，則它的左孩子結(jié)點(diǎn)的編號(hào)為________，右孩子結(jié)點(diǎn)的編號(hào)為________，雙親結(jié)點(diǎn)的編號(hào)為________。

13.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲(chǔ)時(shí)，鏈表中指針域的總數(shù)為_________個(gè)，其中___________個(gè)用于孩子結(jié)點(diǎn)，_____________個(gè)空閑著。

14.哈夫曼樹是指________________________________________________的二叉樹。

15.空樹是指________________________，最小的樹是指_______________________。

16.二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有______________和_______________兩種。

17.三叉鏈表比二叉鏈表多一個(gè)指向______________的指針域。

18.線索是指___________________________________________。

19.線索鏈表中的rtag域值為_____時(shí)，表示該結(jié)點(diǎn)無右孩子，此時(shí)______域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。

20.本節(jié)中我們學(xué)習(xí)的樹的存儲(chǔ)結(jié)構(gòu)有_____________、___________和___________。

四、應(yīng)用題

1.已知一棵樹邊的集合為{<i，m>，<i，n>，<e，i>，<b，e>，<b，d>，<a，b>，<g，j>，<g，k>，<c，g>，<c，f>，<h，l>，<c，h>，<a，c>}，請(qǐng)畫出這棵樹，并回答下列問題：

（1）哪個(gè)是根結(jié)點(diǎn)？

（2）哪些是葉子結(jié)點(diǎn)？

（3）哪個(gè)是結(jié)點(diǎn)g的雙親？

（4）哪些是結(jié)點(diǎn)g的祖先？

（5）哪些是結(jié)點(diǎn)g的孩子？

（6）哪些是結(jié)點(diǎn)e的孩子？

（7）哪些是結(jié)點(diǎn)e的兄弟？哪些是結(jié)點(diǎn)f的兄弟？

（8）結(jié)點(diǎn)b和n的層次號(hào)分別是什么？

（9）樹的深度是多少？

（10）以結(jié)點(diǎn)c為根的子樹深度是多少？

2.一棵度為2的樹與一棵二叉樹有何區(qū)別。

3.試分別畫出具有3個(gè)結(jié)點(diǎn)的樹和二叉樹的所有不同形態(tài)？

4.已知用一維數(shù)組存放的一棵完全二叉樹：ABCDEFGHIJKL，寫出該二叉樹的先序、中序和后序遍歷序列。

5.一棵深度為H的滿k叉樹有如下性質(zhì)：第H層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹，如果按層次自上至下，從左到右順序從1開始對(duì)全部結(jié)點(diǎn)編號(hào)，回答下列問題：

（1）各層的結(jié)點(diǎn)數(shù)目是多少？

（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是多少？

（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是多少？

（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？

6.找出所有滿足下列條件的二叉樹：

（1）它們?cè)谙刃虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；

（2）它們?cè)诤笮虮闅v和中序遍歷時(shí)，得到的遍歷序列相同；

（3）它們?cè)谙刃虮闅v和后序遍歷時(shí)，得到的遍歷序列相同；

7.假設(shè)一棵二叉樹的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。

8.假設(shè)一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請(qǐng)寫出該二叉樹的后序遍歷序列。

9.給出如圖5-14所示的森林的先根、后根遍歷結(jié)點(diǎn)序列，然后畫出該森林對(duì)應(yīng)的二叉樹。

10．給定一組權(quán)值（5，9，11，2，7，16），試設(shè)計(jì)相應(yīng)的哈夫曼樹。五、算法設(shè)計(jì)題

1.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹以一維數(shù)組作為存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)對(duì)該完全二叉樹進(jìn)行先序遍歷的算法。

2.給定一棵用二叉鏈表表示的二叉樹，其中的指針t指向根結(jié)點(diǎn)，試寫出從根開始，按層次遍歷二叉樹的算法，同層的結(jié)點(diǎn)按從左至右的次序訪問。

3.寫出在中序線索二叉樹中結(jié)點(diǎn)P的右子樹中插入一個(gè)結(jié)點(diǎn)s的算法。

4.給定一棵二叉樹，用二叉鏈表表示，其根指針為t，試寫出求該二叉樹中結(jié)點(diǎn)n的雙親結(jié)點(diǎn)的算法。若沒有結(jié)點(diǎn)n或者該結(jié)點(diǎn)沒有雙親結(jié)點(diǎn)，分別輸出相應(yīng)的信息；若結(jié)點(diǎn)n有雙親，輸出其雙親的值。

習(xí)題5參考答案

一、單項(xiàng)選擇題

1.C2.B3.C4.D5.B6.D7.C8.B9.B10.B11.A12.D13.A14.B15.A

二、判斷