5．選擇題

（1）在數(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)

答案：C

（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（?? ）。

A．存儲結(jié)構(gòu)?????????????? B．存儲實現(xiàn)

C．邏輯結(jié)構(gòu)?? ????????????D．運算實現(xiàn)

答案：C

（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（?? ）。

?? A．?dāng)?shù)據(jù)具有同一特點

B．不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)數(shù)據(jù)項的類型要一致

C．每個數(shù)據(jù)元素都一樣

D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等

答案：B

（4）以下說法正確的是（?? ）。

A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位

B．?dāng)?shù)據(jù)項是數(shù)據(jù)的基本單位

C．?dāng)?shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合

D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

答案：D

解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。

（5）算法的時間復(fù)雜度取決于（??? ）。

A．問題的規(guī)模 ??????? B．待處理數(shù)據(jù)的初態(tài)

C．計算機(jī)的配置?? ??????? D．A和B

答案：D

解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及平均時間復(fù)雜度的評價。

（6）以下數(shù)據(jù)結(jié)構(gòu)中，（? ）是非線性數(shù)據(jù)結(jié)構(gòu)

A．樹??????? B．字符串?????? C．隊列?????????? D．棧

答案：A

6．試分析下面各程序段的時間復(fù)雜度。

（1）x=90; y=100;?

while(y>0)

if(x>100)

?{x=x-10;y--;}

else x++;

答案：O(1)

解釋：程序的執(zhí)行次數(shù)為常數(shù)階。

（2）for (i=0; i<n; i++)

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

a[i][j]=0;

答案：O(m*n)

解釋：語句a[i][j]=0;的執(zhí)行次數(shù)為m*n。

（3）s=0;

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

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

? ???????s+=B[i][j];

sum=s;

答案：O(n2)

解釋：語句s+=B[i][j];的執(zhí)行次數(shù)為n2。

（4）i=1;

? ???while(i<=n)

??????? i=i*3;

答案：O(log3n)

解釋：語句i=i*3;的執(zhí)行次數(shù)為??log3n?。

（5）x=0;

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

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

x++;

答案：O(n2)

解釋：語句x++;的執(zhí)行次數(shù)為n-1+n-2+……＋1= n(n-1)/2。

（6）x=n; //n>1

y=0;

while(x≥(y+1)* (y+1))

????y++;

答案：O()

解釋：語句y++;的執(zhí)行次數(shù)為???。

二

1．選擇題

（1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（??? ）。

A．110??????????? B．108? ???????C．100????????? D．120

答案：B

解釋：順序表中的數(shù)據(jù)連續(xù)存儲，所以第5個元素的地址為：100+2*4=108。

（2）在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(1)的操作是（?? ）。

A．訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）

B．在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）

C．刪除第i個結(jié)點（1≤i≤n）

D．將n個結(jié)點從小到大排序

答案：A

解釋：在順序表中插入一個結(jié)點的時間復(fù)雜度都是O(n2)，排序的時間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問第i個結(jié)點和求第i個結(jié)點的直接前驅(qū)都可以直接通過數(shù)組的下標(biāo)直接定位，時間復(fù)雜度是O(1)。

（3） 向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動? 的元素個數(shù)為（?? ）。

A．8 ?????B．63.5 ???????C．63????? D．7

答案：B

解釋：平均要移動的元素個數(shù)為：n/2。

（4）鏈接存儲的存儲結(jié)構(gòu)所占存儲空間（?? ）。

A．分兩部分，一部分存放結(jié)點值，另一部分存放表示結(jié)點間關(guān)系的指針

B．只有一部分，存放結(jié)點值

C．只有一部分，存儲表示結(jié)點間關(guān)系的指針

D．分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)

答案：A

（5）線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址（?? ）。

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

C．一定是不連續(xù)的??? ??D．連續(xù)或不連續(xù)都可以

答案：D

（6）線性表Ｌ在（?? ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實現(xiàn)。

A．需經(jīng)常修改Ｌ中的結(jié)點值????? Ｂ．需不斷對Ｌ進(jìn)行刪除插入

C．Ｌ中含有大量的結(jié)點????????? Ｄ．Ｌ中結(jié)點結(jié)構(gòu)復(fù)雜

答案：B

解釋：鏈表最大的優(yōu)點在于插入和刪除時不需要移動數(shù)據(jù)，直接修改指針即可。

（7）單鏈表的存儲密度（?? ）。

A．大于1????? ??B．等于1????? C．小于1??? D．不能確定

答案：C

解釋：存儲密度是指一個結(jié)點數(shù)據(jù)本身所占的存儲空間和整個結(jié)點所占的存儲空間之比，假設(shè)單鏈表一個結(jié)點本身所占的空間為D，指針域所占的空間為N，則存儲密度為：D/(D+N)，一定小于1。

（8）將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是（?? ）。

A．n ???????????B．2n-1 ???????C．2n ???????D．n-1

答案：A

解釋：當(dāng)?shù)谝粋€有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較n次。

（9）在一個長度為n的順序表中，在第i個元素（1≤i≤n+1）之前插入一個新元素時須向后移動（?? ）個元素。

A．n-i ??????????B．n-i+1? ?????C．n-i-1 ?????D．I

答案：B

(10) 線性表L=(a1，a2,……an)，下列說法正確的是（?? ）。

A．每個元素都有一個直接前驅(qū)和一個直接后繼

B．線性表中至少有一個元素

C．表中諸元素的排列必須是由小到大或由大到小

D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅(qū)和直接后繼。

答案：D

(11) 創(chuàng)建一個包括n個結(jié)點的有序單鏈表的時間復(fù)雜度是（??? ）。

A．O(1) ?????????B．O(n)?? ?????????C．O(n2) ?????????D．O(nlog2n)

答案：C

解釋：單鏈表創(chuàng)建的時間復(fù)雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結(jié)點時需要和已有的結(jié)點進(jìn)行比較，確定合適的插入位置，所以時間復(fù)雜度是O(n2)。

(12) 以下說法錯誤的是（?? ）。????????????????????????????????????????????

A．求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實現(xiàn)的效率低

B．順序存儲的線性表可以隨機(jī)存取

C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活

D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)????????????????

答案：D

解釋：鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序存儲結(jié)構(gòu)各有優(yōu)缺點，有不同的適用場合。

(13) 在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(yīng)為（?? ）。

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

B．(*p).next=s; (*s).next=(*p).next;

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

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

答案：D

?(14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（?? ）。

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

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

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

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

答案：A

(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是（?? ）。

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

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

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

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

答案：C

2．算法設(shè)計題

（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。

[題目分析]

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個表到達(dá)表尾結(jié)點，為空時，將非空表的剩余元素直接鏈接在Lc表的最后。

[算法描述]

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)

{//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

??pa=La->next;? pb=Lb->next;???

?? //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

?? Lc=pc=La;? //用La的頭結(jié)點作為Lc的頭結(jié)點

?? while(pa && pb)

{if(pa->data<pb->data){pc->next=pa;pc=pa;pa=pa->next;}

??? ?//取較小者La中的元素，將pa鏈接在pc的后面，pa指針后移

???? else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}

????? //取較小者Lb中的元素，將pb鏈接在pc的后面，pb指針后移

???? else //相等時取La中的元素，刪除Lb中的元素

{pc->next=pa;pc=pa;pa=pa->next;

????? q=pb->next;delete pb ;pb =q;

}

?? ??}

?pc->next=pa?pa:pb;??? //插入剩余段

?? ??delete Lb;??????????? //釋放Lb的頭結(jié)點

}?

（2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復(fù)的數(shù)據(jù)。

[題目分析]

合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的表頭結(jié)點之后，如果兩個表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當(dāng)一個表到達(dá)表尾結(jié)點，為空時，將非空表的剩余元素依次摘取，鏈接在Lc表的表頭結(jié)點之后。

[算法描述]

void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, )

{//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向

? pa=La->next;? pb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

? Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點

? Lc->next=NULL;

? while(pa||pb )

{//只要存在一個非空表，用q指向待摘取的元素

??? if(!pa)? {q=pb;? pb=pb->next;}

//La表為空，用q指向pb，pb指針后移

??? else if(!pb)? {q=pa;? pa=pa->next;}

//Lb表為空，用q指向pa，pa指針后移

??? else if(pa->data<=pb->data)? {q=pa;? pa=pa->next;}

//取較小者（包括相等）La中的元素，用q指向pa，pa指針后移

??? else {q=pb;? pb=pb->next;}

//取較小者Lb中的元素，用q指向pb，pb指針后移

???? q->next = Lc->next;? Lc->next = q;??

//將q指向的結(jié)點插在Lc 表的表頭結(jié)點之后

? ??}

? ??delete Lb;???????????? //釋放Lb的頭結(jié)點

}??

?

（3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出A與B的交集，并存放于A鏈表中。

[題目分析]

只有同時出現(xiàn)在兩集合中的元素才出現(xiàn)在結(jié)果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時，如果兩個表中相等的元素時，摘取La表中的元素，刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個到達(dá)表尾結(jié)點，為空時，依次刪除另一個非空表中的所有元素。

[算法描述]

void Mix(LinkList& La, LinkList& Lb, LinkList& Lc)

{? pa=La->next;pb=Lb->next;

pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點

while(pa&&pb)

{ if(pa->data==pb->data)∥交集并入結(jié)果表中。

?? { pc->next=pa;pc=pa;pa=pa->next;

???? u=pb;pb=pb->next; delete u;}

??else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;}

else {u=pb; pb=pb->next; delete u;}

}

while(pa) {u=pa; pa=pa->next; delete u;}∥ 釋放結(jié)點空間

while(pb) {u=pb; pb=pb->next; delete u;}∥釋放結(jié)點空間

pc->next=null;∥置鏈表尾標(biāo)記。

delete Lb;? //釋放Lb的頭結(jié)點

?? }

（4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設(shè)計算法求出兩個集合A和B 的差集（即僅由在A中出現(xiàn)而不在B中出現(xiàn)的元素所構(gòu)成的集合），并以同樣的形式存儲，同時返回該集合的元素個數(shù)。

[題目分析]

求兩個集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應(yīng)結(jié)點,所以要保存待刪除結(jié)點的前驅(qū)，使用指針pre指向前驅(qū)結(jié)點。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進(jìn)行比較，當(dāng)兩個鏈表La和Lb均為到達(dá)表尾結(jié)點時，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當(dāng)鏈表La和Lb有一個為空時，依次刪除另一個非空表中的所有元素。

[算法描述]

void Difference（LinkList& La, LinkList& Lb,int *n）

{∥差集的結(jié)果存儲于單鏈表La中，*n是結(jié)果集合中元素個數(shù)，調(diào)用時為0

pa=La->next; pb=Lb->next;?????

∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點

? pre=La;????????? ∥pre為La中pa所指結(jié)點的前驅(qū)結(jié)點的指針

??while（pa&&pb）

{if（pa->data<q->data）{pre=pa;pa=pa->next;*n++;}

∥ A鏈表中當(dāng)前結(jié)點指針后移

else if（pa->data>q->data）q=q->next;???? ∥B鏈表中當(dāng)前結(jié)點指針后移

?? ?else {pre->next=pa->next;????? ∥處理A，B中元素值相同的結(jié)點，應(yīng)刪除

????????? u=pa; pa=pa->next; delete u;}?? ∥刪除結(jié)點

}

}

（5）設(shè)計算法將一個帶頭結(jié)點的單鏈表A分解為兩個具有相同結(jié)構(gòu)的鏈表B、C，其中B表的結(jié)點為A表中值小于零的結(jié)點，而C表的結(jié)點為A表中值大于零的結(jié)點（鏈表A中的元素為非零整數(shù)，要求B、C表利用A表的結(jié)點）。

[題目分析]

B表的頭結(jié)點使用原來A表的頭結(jié)點，為C表新申請一個頭結(jié)點。從A表的第一個結(jié)點開始，依次取其每個結(jié)點p，判斷結(jié)點p的值是否小于0，利用前插法，將小于0的結(jié)點插入B表,大于等于0的結(jié)點插入C表。

[算法描述]

void DisCompose(LinkedList A)

{ ??B=A;

B->next= NULL;??? ∥B表初始化

?? ??C=new LNode;∥為C申請結(jié)點空間

???? C->next=NULL;???? ∥C初始化為空表

???? p=A->next;?????? ?∥p為工作指針

???? while(p!= NULL)

??? ?{ r=p->next;??? ??∥暫存p的后繼

?????? if(p->data<0)

????? ??{p->next=B->next; B->next=p; }∥將小于0的結(jié)點鏈入B表,前插法

?????? else {p->next=C->next; C->next=p; }∥將大于等于0的結(jié)點鏈入C表,前插法

?????? p=r;∥p指向新的待處理結(jié)點。

???? }

}

第3章? 棧和隊列

1．選擇題

（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（? ）種情況。

A．5，4，3，2，1?? B．2，1，5，4，3?? ?C．4，3，1，2，5 ???D．2，3，5，4，1

答案：C

解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項所示的情況。

（2）若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（? ）。

A．i?????????????? B．n-i????????????? ?C．n-i+1??????????? D．不確定

答案：C

解釋：棧是后進(jìn)先出的線性表，一個棧的入棧序列是1，2，3，…，n，而輸出序列的第一個元素為n，說明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。

（3）數(shù)組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當(dāng)前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(shù)小于ｎ，計算隊列中元素個數(shù)的公式為（? ）。

A．r-f???????????? B．(n+f-r)%n?????? C．n+r-f?????????? D．（n+r-f)%n

答案：D

解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。

（4）鏈?zhǔn)綏＝Y(jié)點為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作（? ）。

A．x=top->data;top=top->link；? ? ???? ??B．top=top->link;x=top->link；???

C．x=top;top=top->link；??????????? ????? D．x=top->link；

答案：A

解釋：x=top->data將結(jié)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。

（5）設(shè)有一個遞歸算法如下

??? ??? int fact(int n) {? //n大于等于0

??? ???????? if(n<=0) return 1;

??? ???????? else return n*fact(n-1);??? ??? }

則計算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（? ）。?

A．?n+1??? ????????? B．?n-1????????????? C． n??????????????? ??D． n+2

答案：A

解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。

（6）棧在?（? ）中有所應(yīng)用。

A．遞歸調(diào)用? ?????B．函數(shù)調(diào)用 ?????C．表達(dá)式求值??? ????D．前三個選項都有

答案：D

解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。

（7）為解決計算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（? ）。

A．隊列 ??????????B．棧??????????? C． 線性表?????????? D．有序表

答案：A

解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊列正是一種先進(jìn)先出的線性表。

（8）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個元素出棧后即進(jìn)入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（?。?。

A．2???????????? ?B．3? ????????????C．4??????????????? D． 6

答案：B

解釋：元素出隊的序列是e2、e4、e3、e6、e5和e1，可知元素入隊的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧，易知棧S中最多同時存在3個元素，故棧S的容量至少為3。

（9）若一個棧以向量V[1..n]存儲，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是(??? )。

A．top++; V[top]=x; ??????????????? B．V[top]=x; top++;

C．top--; V[top]=x; ??????????????? D．V[top]=x; top--;

答案：C

解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因為元素存儲在向量空間V[1..n]中，所以進(jìn)棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。

（10）設(shè)計一個判別表達(dá)式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結(jié)構(gòu)最佳。

A．線性表的順序存儲結(jié)構(gòu)??? ??????????B．隊列????

C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)?? ???????????D. 棧

答案：D

解釋：利用棧的后進(jìn)先出原則。

（11）用鏈接方式存儲的隊列，在進(jìn)行刪除運算時（?。?。

A. 僅修改頭指針?????????????????? ???B. 僅修改尾指針

C. 頭、尾指針都要修改? ??????????????D. 頭、尾指針可能都要修改

答案：D

解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。

（12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（　）。

A. rear=rear+1???????????? ??????????B. rear=(rear+1)%(m-1)

? C. rear=(rear+1)%m??????????? ???????D. rear=(rear+1)%(m+1)

答案：D

解釋：數(shù)組A[0..m]中共含有m+1個元素，故在求模運算時應(yīng)除以m+1。

（13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（　）。

? A. (rear+1)%n==front???????????????? ?B. rear==front ?????????????????????????????????????????????????????????

C．rear+1==front? ????????????????????D. (rear-l)%n==front

答案：B

解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n==front，隊空條件是rear==front。

（14）棧和隊列的共同點是（　）。

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

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

答案：C

解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素。

（15）一個遞歸算法必須包括（?。?/p>

A. 遞歸部分????? ?????????????????????B. 終止條件和遞歸部分

C. 迭代部分??? ???????????????????????D. 終止條件和迭代部分

答案：B

?

?

（5）假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。

①下面所示的序列中哪些是合法的？

?? A. IOIIOIOO???? B. IOOIOIIO????? C. IIIOIOIO???? D. IIIOOIOO

②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數(shù)組中）。

答案：

①A和D是合法序列，B和C 是非法序列。

第4章? 串、數(shù)組和廣義表

1．選擇題

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

? A．可以順序存儲?????????????? B．?dāng)?shù)據(jù)元素是一個字符?????

C．可以鏈?zhǔn)酱鎯?????????????? D．?dāng)?shù)據(jù)元素可以是多個字符若

答案：B

（2）串下面關(guān)于串的的敘述中，（? ）是不正確的？

A．串是字符的有限序列?????? ???B．空串是由空格構(gòu)成的串

C．模式匹配是串的一種重要運算? D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯?/p>

答案：B

解釋：空格常常是串的字符集合中的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零。

（3）串“ababaaababaa”的next數(shù)組為（? ）。

A．012345678999?? B．012121111212 ??C．011234223456??? D．0123012322345

答案：C

（4）串“ababaabab”的nextval為（? ）。

A．010104101??? ??B．010102101????? C．010100011?????? D．010101011

答案：A

（5）串的長度是指（? ）。

A．串中所含不同字母的個數(shù)???? ??B．串中所含字符的個數(shù)

C．串中所含不同字符的個數(shù)???? ??D．串中所含非空格字符的個數(shù)

答案：B

解釋：串中字符的數(shù)目稱為串的長度。

（6）假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC[5,5]=（? ）。

A．808????????? ??B．818 ????????????C．1010???????????? D．1020

答案：B

解釋：以行序為主，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。

（7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為（? ）。

A．BA+141? ??????B．BA+180? ???????C．BA+222???????? D．BA+225

答案：B

解釋：以列序為主，則LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。

（8）設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（? ）。

A．13????????? ???B．32 ?????????????C．33?????????????? D．40

答案：C

（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i<j）的位置k的關(guān)系為（? ）。

A．i*(i-1)/2+j?? ???B．j*(j-1)/2+i ?????C．i*(i+1)/2+j? ????D．j*(j+1)/2+i

答案：B

（10）二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素（??? ）的起始地址相同。設(shè)每個字符占一個字節(jié)。

A．A[8,5]?? ??????B．A[3,10]?? ??????C. A[5,8]???????? ?D．A[0,9]

答案：B

解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲，易計算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。

（11）設(shè)二維數(shù)組A[1.. m，1.. n]（即m行n列）按行存儲在數(shù)組B[1.. m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（? ）。

A．(i-1)*n+j? ?????B．(i-1)*n+j-1??? ??C．i*(j-1)???? ????D．j*m+i-1

答案：A

解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個選項中僅有A選項能確定的值為1，故選A。

（12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（? ）。

A．55???????? ???B．45 ????????????C．36???????? ???D．16

答案：B

解釋：共有5*3*3=45個元素。

（13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（? ）。

A．(g)??????????? B．(d)???????????? C．c????????? ??D．d

答案：D

解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Head(Tail(Head(Tail(Tail(A)))))=d。

（14）廣義表((a,b,c,d))的表頭是（? ），表尾是（? ）。

A．a(chǎn)????????? ????B．( )???????????? C．(a,b,c,d)? ????D．(b,c,d)

答案：C、B

解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表( )。

（15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（? ）。

A．1和1????? ????B．1和3?????? ???C．1和2 ?????????D．2和3

答案：C

解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1，深度為2。

?