新題庫-數(shù)據(jù)結(jié)構(gòu)題庫及答案

第一章緒論

一、選擇題

1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的，以及它們

之間的B和運(yùn)算等的學(xué)科。（易）

①A、數(shù)據(jù)元素B、計(jì)算方法C、邏輯存儲D、數(shù)據(jù)映象

②A、結(jié)構(gòu)B、關(guān)系C、運(yùn)算D、算法

2、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（K,R）,其中K是D的有限集,R是K上的B

有限集。（易）

①A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯結(jié)構(gòu)

②A、操作B、映象C、存儲D、關(guān)系

3、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成—C―o（易）

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)

4、算法分析的目的是C,算法分析的兩個主要方面是A。（中）

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

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

②A、空間復(fù)雜度和時(shí)間復(fù)雜度B、正確性和簡單性

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

5、計(jì)算機(jī)算法指的是C,它必須具備輸入、輸出和B等5個特性。

（易）

①A、計(jì)算方法B、排序方法

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

②A、可執(zhí)行性、可移植性和可擴(kuò)充性

B、可行性、確定性和有窮性

C、確定性、有窮性和穩(wěn)定性

D、易讀性、穩(wěn)定性和安全性

答案：1、A,B2、D,B3、C4、C,A5、C,B

二、名詞解釋：(易)

1、數(shù)據(jù)2、數(shù)據(jù)元素3、數(shù)據(jù)對象

4、數(shù)據(jù)結(jié)構(gòu)5、數(shù)據(jù)類型6、算法

答案：1、數(shù)據(jù)——是對客觀事物的符號表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算

機(jī)中被計(jì)算機(jī)程序處理的符號的總稱。

2、數(shù)據(jù)元素——數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常做為一個整體進(jìn)行考慮和處理。

3、數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合。

4、數(shù)據(jù)結(jié)構(gòu)：相互具有一種或多種關(guān)系的數(shù)據(jù)元素的集合。

5、數(shù)據(jù)類型：是具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)的集合及在這個數(shù)據(jù)上的一組運(yùn)算，是和

數(shù)據(jù)結(jié)構(gòu)密切相關(guān)的概念。

6、算法：對特定問題求解步驟的一種描述，是有限指令的集合。

三、填空題

1、下面程序段的時(shí)間復(fù)雜度是0(m*n)o(易)

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

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

2、下面程序段的時(shí)間復(fù)雜度是—0(冊)—。(中)

i=s=0

while(s<n)

(

i++;/*i=i+1*/

s+=i;/*s=s+i*/

3、下面程序段的時(shí)間復(fù)雜度是_0（/）。（易）

s=0;

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

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

s+=b[i][J];

sum=s;

4、下面程序段的時(shí)間復(fù)雜度是—Odog./）。（難）

i=1；

wiIe（i<=n）

i=i*3;

5、數(shù)據(jù)元素可以由若干—數(shù)據(jù)項(xiàng)—組成，―數(shù)據(jù)元素—是數(shù)據(jù)的基本單位，

—數(shù)據(jù)項(xiàng)—是數(shù)據(jù)的最小單位。（易）

6、數(shù)據(jù)結(jié)構(gòu)分為兩部分，即—邏輯—結(jié)構(gòu)和一物理—結(jié)構(gòu)。（易）

7、數(shù)據(jù)的存儲方式分為—順序—存儲和—鏈?zhǔn)健鎯Α＃ㄒ祝?/p>

8、順序存儲是一種—隨機(jī)存取—的存儲方式，是用一組_連續(xù)—的存儲空間存

儲數(shù)據(jù)，而鏈?zhǔn)酱鎯κ怯靡唤M一任意—的存儲空間存儲數(shù)據(jù)。（易）

四、簡答題：

1、什么是算法，其基本性質(zhì)是什么？（易）

答案：1、算法是對特定問題求解步驟的一種描述，是有限指令的集合。其基本性質(zhì)如

下：

1）有窮性：算法對任意合法的輸入均能在有限時(shí)間、有限步驟后完成。

2）確定性：算法的每一步驟的含義都是唯一、確定的，對于相同的輸入均能得到相同

的輸出。

3）可行性：算法的每一個步驟和指令都應(yīng)在已實(shí)現(xiàn)的算法的基礎(chǔ)上完成。

4）輸入：任一個算法必須有0個或多個輸入。

5）輸出：任一個算法必須有1個或多個輸出。

2、算法的要求是什么？（中）

2、算法的要求是：

1）正確性：算法能正確描述待求解問題的需求，沒有邏輯錯誤，據(jù)此算法書寫的程序,

對于任何合法的輸入，都有得到正確的、說明需求的結(jié)果。

2）可讀性：算法應(yīng)簡潔、明晰，易于閱讀和理解，便于算法的移植和交流，有利于增

加算法的生命力。

3）健壯性：當(dāng)輸入的數(shù)據(jù)非法時(shí)，算法要能作出適當(dāng)?shù)奶幚?，不會產(chǎn)生難以預(yù)料的結(jié)

果。

4）高效率性：一般來說，對同一問題的多種算法，首先選擇執(zhí)行時(shí)間相對較短、存儲

空間相對較少的算法，然后考慮易于實(shí)現(xiàn)的算法。

3、結(jié)構(gòu)共分幾類？其各自的性質(zhì)是什么？（易）

3、結(jié)構(gòu)共分為四類，分別為：

1）集合：所有元素除共在同一集合外，沒有其他關(guān)系。

2）線性結(jié)構(gòu)：元素間是一對一的關(guān)系。

3）樹型結(jié)構(gòu)：元素間是一對多的關(guān)系。

4）圖型結(jié)構(gòu)：元素間是多對多的關(guān)系。

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

1、試寫一算法，求隨機(jī)輸入的三個整數(shù)的最大值。（中）

2、隨機(jī)從鍵盤上輸入三個整數(shù)求其平均值輸出。（易）

答案：1、intmax（intx,inty,intz）

{intt;

t=x>y?x:y;

t=t>z?t:z;

returnt;

}

2、main（）

{inta,b,c;

fIoatsum=0,ave;

scanf（“%d%d%d"，&a,&b,&c）;

sum=a+b+c;

ave=sum/3;

printf（"%.2f\n”,ave）;

}

第二章線性結(jié)構(gòu)

一、判斷題

1、線性表的邏輯順序與存儲順序總是一致的。（X）

2、順序存儲的線性表可以按序號隨機(jī)存取。（J）

3、順序表的插入和刪除一個數(shù)據(jù)元素，每次操作平均只有近一半的元素需要移動。

（J）

4、線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特

性，因此是屬于同一數(shù)據(jù)對象。（J）

5、在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊

鄰。（X）

6、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的元素在物理位置上不一定相鄰。（J）

7、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)。（義）

8、在線性表的順序存儲結(jié)構(gòu)中，插入和刪除時(shí)，移動元素的個數(shù)與該元素的位置

有關(guān)。（J）

9、線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是用一組任意的存儲單元來存儲線性表中數(shù)據(jù)元素的。

(J)

10、在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此，單鏈表

是隨機(jī)存取的存儲結(jié)構(gòu)。（X）

11、線性表中，每一個元素均存在前驅(qū)。（X）

12、線性表中，每一個元素均存在后繼。（X）

13、線性表中，存在唯一一個被稱為第一元素的元素。（J）

14、線性表中，存在唯一一個被稱為最后一個元素的元素。（J）

15、線性結(jié)構(gòu)是一種一對一的結(jié)構(gòu)。（J）

二、選擇題：

1、線性表是（A）。（易）

A、一個有限序列，可以為空；B、一個有限序列，不能為空；

C、一個無限序列，可以為空；D、一個無序序列，不能為空。

2、對順序存儲的線性表，設(shè)其長度為n,在任何位置上插入或刪除操作都是等概

率的。插入一個元素時(shí)平均要移動表中的（A）個元素。（易）

A、n/2B、（n+1）/2C>（n-1）/2D、n

3、線性表采用鏈?zhǔn)酱鎯r(shí)，其地址（D）。（易）

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

C、一定是不連續(xù)的；D、連續(xù)與否均可以。

4、用鏈表表示線性表的優(yōu)點(diǎn)是（C）。（易）

A、便于隨機(jī)存取

B、花費(fèi)的存儲空間較順序存儲少

C、便于插入和刪除

D、數(shù)據(jù)元素的物理順序與邏輯順序相同

5、某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個

元素，則采用（D）存儲方式最節(jié)省運(yùn)算時(shí)間。（易）

A、單鏈表

B、雙鏈表

C、單循環(huán)鏈表

D、帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

6、循環(huán)鏈表的主要優(yōu)點(diǎn)是（D）。（易）

A、不再需要頭指針了

B、已知某個結(jié)點(diǎn)的位置后，能夠容易找到他的直接前趨

C、在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開

D、從表中的任意結(jié)點(diǎn)出發(fā)都能掃描到整個鏈表

7、下面關(guān)于線性表的敘述錯誤的是（B）。（易）

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

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

C、線性表采用鏈?zhǔn)酱鎯?，不必占用一片地址連續(xù)的單元；

D、線性表采用鏈?zhǔn)酱鎯Γ阌谶M(jìn)行插入和刪除操作；

8、單鏈表中，增加一個頭結(jié)點(diǎn)的目的是為了（C）。（易）

A、使單鏈表至少有一個結(jié)點(diǎn)B、標(biāo)識表結(jié)點(diǎn)中首結(jié)點(diǎn)的位置

C、方便運(yùn)算的實(shí)現(xiàn)D、說明單鏈表是線性表的鏈?zhǔn)酱鎯?/p>

9、若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一

個元素，則采用（D）存儲方式最節(jié)省運(yùn)算時(shí)間。（易）

A、單鏈表B、僅有頭指針的單循環(huán)鏈表

C、雙鏈表D、僅有尾指針的單循環(huán)鏈表

10、若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則

采用（B）存儲方式最節(jié)省運(yùn)算時(shí)間。（易）

A、單鏈表B、順序表

C、雙鏈表D、單循環(huán)鏈表

11、一個向量（一種順序表）第一個元素的存儲地址是100,每個元素的長度為2,

則第5個元素的地址是—B—。（易）

A、110B、108C、100D、120

12、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是A。（易）

A、head二二NULL;B、head->next=二NULL;

C^head->next=二head;D>head!二NULL;

13、帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是—B—。（易）

A、head二二NULL;B、head->next=二NULL;

C、head->next二二head;D、head!=NULL;

14、在一個單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，

則執(zhí)行—B_o（易）

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;

15、在一個單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之

間插入s結(jié)點(diǎn)，則執(zhí)行C。（易）

A、s->nextz:p->next;p->next=s;B、p->next=s->next;s->next二p;

C、q->next=s;s->next=p;D、p->next=s;s->next二q;

16、從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況

下，需平均比較—口_個結(jié)點(diǎn)。（易）

A、n;B、n/2;C、（n-1）/2;D、（n+1）/2;

17、給定有n個結(jié)點(diǎn)的向量，建立一個有序單鏈表的時(shí)間復(fù)雜度_____C_。（易）

（）（）（2）（）

A^01;B、0n;C、0n;D、0nlog2n;

18、順序存儲結(jié)構(gòu)是一種_A_的存儲結(jié)構(gòu)。（易）

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

19、在以下的敘述中，正確的是_C一。（易）

A、線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈表存儲結(jié)構(gòu)

B、線性表的順序存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

C、線性表的鏈表存儲結(jié)構(gòu)適用于頻繁插入/刪除數(shù)據(jù)元素的情況

D、線性表的鏈表存儲結(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu)

20、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足—C_o（易）

A、p->next==NULLB、p二二NULL

C、p->next==headD>p==head

21、在一個單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行_A—。（易）

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；

三、填空題

1在一個長度為n的向量中的第i個元素ClWiWn）之前插入一個元素時(shí)，需向后

移動—n~i+1個元素。（易）

2、在一個長度為n的向量中刪除第i個元素（1WiWn）時(shí)，需向前移動個

元素。（易）

3、在一個單鏈表中p所指結(jié)點(diǎn)之前插入一個由指針s所指結(jié)點(diǎn)，可執(zhí)行以下操作:

（易）

s->next=_（1）;

p->next=s;

t二p->data;

p->data=（2）;

s->data=（3）;

4、在線性表L=（a1,a2,……,an）中，L稱為線性表的,n稱為線性表的

______。（易）

5、在線性表中有（ai,aj）,稱ai為aj的,稱aj為ai的。（易）

6、在順序表中，若第一個元素所在的地址為Loc（a1）,每個元素在內(nèi)存中占有L

個存儲單元，則元素ai在內(nèi)存中的地址Loc（ai）;。（易）

7、順序表是一種存取的存儲結(jié)構(gòu)，其元素的邏輯位置與物理位置一一對應(yīng)。

（易）

8、系統(tǒng)在內(nèi)存中為順序表提供一組的存儲空間，為單鏈表提供一組的

存儲空間。（易）

9、在單鏈表中，一個結(jié)點(diǎn)包含兩部分內(nèi)容，分別為和o（易）

10、在單鏈表中，若指針p已指向最后一個結(jié)點(diǎn)，則p應(yīng)滿足的條件是o

（易）

11、在單鏈表中，若結(jié)點(diǎn)p是結(jié)點(diǎn)q的前驅(qū)，應(yīng)滿足的條件是。（易）

12、在單鏈表中，申請一個結(jié)點(diǎn)空間的命令是，釋放一個空間的命令是

________。（易）

13、在雙向鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個為,指向；另一

個為，指向o（易）

14、在一個單鏈表中p所指結(jié)點(diǎn)之后插入一個s所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行s->next=_

_p.next—和p->next=_s的操作。（易）

15、在雙向鏈表中，若結(jié)點(diǎn)p是結(jié)點(diǎn)q的前驅(qū)，現(xiàn)要刪除結(jié)點(diǎn)q,需要完成的操作

是p.next二q.next；q.next,prior=q.prior；（易）

16、在雙向鏈表中，若在結(jié)點(diǎn)p之前插入一個新結(jié)點(diǎn)s,需要完成的操作有一

s.prior二p.prior；_s.next=p；_p.prior.next二s；_p.prior二s

______;（易）

答案：1、2^n-i3、（1）p->next（2）s->data（3）t

4、名字長度5、直接前驅(qū)元素直接后繼元素

6、LOG（ai）=Loc（a1）+（i-1）*L7、隨機(jī)8、連續(xù)任意9、指針域數(shù)據(jù)域

10、p.next-nuII11、p.next=q12、maIIoc0free0

13、前驅(qū)指針域prior后繼指針域next四、算法設(shè)計(jì)題：

1、在一順序表L的第i個元素前，插入一新元素X。（中）

2、現(xiàn)有一順序表L,其值非遞增有序排列，現(xiàn)插入一新元素x,要求插入后，L

仍保持非遞增有序排列，試寫其算法。（中）

3、在帶頭結(jié)點(diǎn)的單鏈表H中的p結(jié)點(diǎn)前插入一個新元素X。（中）

4、已知單鏈表LA、LA中的元素按值非遞減有序排列，現(xiàn)將LA、LB歸并成一個新

表LC,并要求LC中的元素亦非遞減有序排列。（中）

五、編程題：

1、百錢百雞問題。（中）

2、獵人與狗的問題：一隊(duì)獵人一隊(duì)狗，兩隊(duì)并成一隊(duì)走，數(shù)頭一共三百六，數(shù)腳

一共八百九，問多少獵人多少狗。（中）

四、五題答案：

四、算法題：

1>intInsert_Sq（SqListL,inti,eIemtp

x）2、intInsert(SqListL,eIemtpx)

{if(i<1||i>L.len+1)return0;{if(L.Ien-maxsize)return-1;

if(L.Ien~maxsize)return_1;

for(j=L.len;j>=i;j-)for(p二&L.eIem[L.len-1];*p<=x;p-)

L.elem[j+1]=L.eIem[j];*(p+1)=*p；

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

L.Ien++;return1;

return1;})

3intInsert_L(LNode*H,LNodes.data二x;q二H;

*p,eIemtpx)while(q.next!=p)q=q.next;

{s=(LNode*)s.next二p;

maIIoc(sizeof(LNode));q.next=s;

return1;{if(pa.data<=pb.data)

}{pc.next=pa;pc=pa;pa=pa.next;}

eIse

{pc.next=pb;pc=pb;pb=pb.next;}

}

4、voidMerge_L(LNodeLa,LNodepc.next=pa?pa:pb;

Lb,LNodeLc)free(Lb);

{pa=La.next;pb=Lb.next;Lc=pc=La;)

while(pa&&pb)

五、編程題：

1、main()}

{intx,y,z;2、main()

for(x=1;x<20;x++){intx,y;

for(y=1;y<33;y++)for(x=1;x<360;x++)

{z=100-x-y;{y=360-x;

if(100=5*x+3*y+z/3.0)if(2*x+4*y=890)

printf(“％d,%d\n”,x,y);

printf("%d,%d,%d\n”,x,y,z);}

}}

第三章棧和隊(duì)列

一、判斷題：

1、棧和隊(duì)列都是限制存取點(diǎn)的線性結(jié)構(gòu)（易）

2、棧和隊(duì)列是兩種重要的線性結(jié)構(gòu)。（易）

3、帶頭結(jié)點(diǎn)的單鏈表形式的隊(duì)列，頭指針F指向隊(duì)列的頭結(jié)點(diǎn)，尾指針R指向隊(duì)

列的最后一個結(jié)點(diǎn)（易）

4、在對不帶頭結(jié)點(diǎn)的鏈隊(duì)列作出隊(duì)操作時(shí)，不會改變頭指針的值。（易）

答案：1—4VVXX

二、選擇題：

1、一個棧的入棧序列a,b,c,d,e,則棧的不可能的輸出序列是_C_。A、

edcbaB、decbaC、dceabD>abode

2、若已知一個棧的入棧序列是1,2,3,…，n,其輸出序列為p1,p2,p3,…,

pn,若p1=n,則pi為_C_o

A、iB、n=iC、n-i+1D、不確定

3、棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是_A_。

A、順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)C^鏈表存儲結(jié)構(gòu)和數(shù)組

B、散列方式和索引方式D、線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)

4、判定一個順序棧ST（最多元素為mO）為空的條件是B_oA、top!=0B、

top==0C、top!=m0D、top==m0-1

5、判定一個順序棧ST（最多元素為mO）為棧滿的條件是_D_。A、top!=0B、

top=二0C、top!=m0D>top=二mO7

6、隊(duì)列操作的原則是（A）A、先進(jìn)先出B、后進(jìn)先出C、只能進(jìn)行插

入D、只能進(jìn)行刪除

7、向一個棧頂指針為HS的鏈棧中插入一個s所指結(jié)點(diǎn)時(shí)，則執(zhí)行―2。（不

帶空的頭結(jié)點(diǎn)）（易）

A、HS一>next=s;C、s一>next=HS;HS二s;

B、s一>next二HS—>next;HS一D、s—>next二HS;HS二HS一>

>next二s;next;

8、從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)的值，則

執(zhí)行B。（不帶空的頭結(jié)點(diǎn)）（中）

A、x=HS;HS=HS—>next;B、x=HS—>data;

c、HS=HS—>next;x=HS——>data;D、x=HS——>data;HS=HS—>next;

9、一個隊(duì)列的數(shù)據(jù)入列序列是1,2,3,4,則隊(duì)列的出隊(duì)時(shí)輸出序列是_C_。

（易）

A、4,3,2,1B、1,2,3,4

C、1,4,3,2D、3,2,4,1

10、判定一個循環(huán)隊(duì)列QU（最多元素為m）為空的條件是_C_。（中）

A、rear-front==mB、rear-front_1==m

C、fronts-rearD、front二二rear+1

11、判定一個循環(huán)隊(duì)列QU（最多元素為m,m==Maxsize-1）為滿隊(duì)列的條件是

A_o（易）

A、（（rear-front）+Maxsize）%Maxsize==m

B、rear-front-1==mC、front二二rearD、front二二rear+1

12、循環(huán)隊(duì)列用數(shù)組A[0,m-l]存放其元素值，已知其頭尾指針分別是front和

rear,則當(dāng)前隊(duì)列中的元素個數(shù)是_A_。（中）

A、（rear-front+m）%mB、rear-front+1

C、rear-front-1D、rear-front

13、棧和隊(duì)列的共同點(diǎn)是_C_。A、都是先進(jìn)后出B、都是先進(jìn)先出C、只

允許在端點(diǎn)處插入和刪除元素D、沒有共同點(diǎn)

14、棧操作的原則是（B）（易）

A、先進(jìn)先出B、后進(jìn)先出C、只能進(jìn)行插入D、只能進(jìn)行刪除

15、在順序棧中，判斷棧s為空的條件是（D）（中）

A、t.base=NULLB、st.top=st.stacksize

C、st.top-st.base>=st.stacksizeD、s*t."top—st.base

16、在順序棧中，判斷棧s滿的條件是（C）（易）

A、st.base=NULLB、st.top=st.stacksize

C、st.top-st.base>=st.stacksizeD、st.top==st.base

答案：1-5CCABD6-10ACBCC11-15AACBD16C

三、填空題：

1、棧和隊(duì)列都是—結(jié)構(gòu)，對于棧只能在一插入和刪除元素；對于隊(duì)列只能在

―插入元素和—刪除元素。（易）

2、向一個長度為n的順序表的第i個元素（1WiWn+1）之前插入一個元素時(shí)，

需向后移動個兀素。（易）

3、向一個長度為n的順序表中刪除第i個元素（1WiWn）時(shí)，需向前移動

個元素。（易）

4、向棧中壓入元素的操作是—o（易）

5、對棧進(jìn)行退棧時(shí)的操作是—o（易）

6、在一個循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的—。（易）

7、從循環(huán)隊(duì)列中刪除一個元素時(shí)，其操作是—。（易）

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

9、一個棧的輸入序列是12345,則棧的輸出序列43512是。（易）

10、一個棧的輸入序列是12345,則棧的輸出序列12345是。（易）

11、隊(duì)列的基本性質(zhì)是；棧的基本性質(zhì)是o（易）

12、在一個鏈棧中，若棧頂指針等于NULL則為,在一個鏈隊(duì)中，

若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為或該隊(duì)列

_______________。（易）

13、向一個棧頂指針為top的鏈棧中插入一個新結(jié)點(diǎn)*P,應(yīng)執(zhí)行和操作。

（易）

14、棧的順序存儲結(jié)構(gòu)即順序棧，是利用來依次存放自棧底

至棧頂?shù)臄?shù)據(jù)元素；當(dāng)棧為非空時(shí)，棧頂指針tOp始終指向0

15、從數(shù)據(jù)結(jié)構(gòu)的角度看，棧和隊(duì)列是兩類線性表。（易）

答案：1.線性、棧頂、隊(duì)尾、隊(duì)首2.n-i+13.n-i

4.先移動棧頂指針，后存入元素5.先取出元素，后移動棧頂指針

6.前一個位置7.先移動隊(duì)首元素，后取出元素

8.n-19.不可能的10.可能的11、FIFOLIFO

12、?？湛贞?duì)只有一個元素13>p->next=toptop=p

14、一組地址連續(xù)的存儲單元棧頂元素的下一位置15、受限的線性表

四、算法題：1、輸入一個任意的非負(fù)十進(jìn)制整數(shù),輸出與其等值的八進(jìn)值數(shù)。（中）

答案：voidconversion()

{InitStack(s);

scanf("%d,&N);

while(N)

{push(s,N%d);N=n/8;}

whiIe(!empty(s))

{pop(s,e);printf("%d\n",e);}

}

五、編程題：

1、從鍵盤上輸入一個大寫字母，要求改用小寫字母輸出。(中)

2、輸入一個圓的半徑，求其周長及面積并輸出。

答案：

1、main()

{charc;

scanf(“％c”，&c);2>#definetPI3.14

c=c+32;main()

printf("%c\n",c);{fIoatr,s,c;

)scanf(,&r);

s=PI*r*r;printf（as=%.2f,c=%.2f\nw,s,c）;

c=2*PI*r;}

第四章串和廣義表

一、判斷題：

1、空串是由空白字符組成的串（易）

2、串的定長順序結(jié)構(gòu)是用一組地址連續(xù)的存儲單元存儲串值的字符序列，按照預(yù)

定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)。（易）

3、串的堆分配存儲表示是用一組地址連續(xù)的存儲單元存儲串值的字符序列，但它

們的存儲空間是在程序執(zhí)行過程中動態(tài)分配得到的。（易）

4、如果一個串中的所有字符均在另一串中出現(xiàn)，那么則說明前者是后者的子串。

（易）

5、串是由有限個字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中

字符構(gòu)成的有限序列。（易）

6、廣義表的表頭一定是列表。（易）

7、廣義表的表尾一定是列表。（易）

8、空串的長度為零。（易）

9、廣義表的元素即可以是原子，也可以是子表。（易）

10、廣義表中的子表與串中的子串的含義一樣。（易）

11、廣義表A=（）,為空表，其長度為0。（易）

12、由于廣義表的元素可以是列表，所以可以將廣義表轉(zhuǎn)化為一個樹型結(jié)構(gòu)

答案：1-5XVVXX6-10XVVVX11-12JJ

二、選擇題：

1、以下敘述中正確的是o（易）

A、串是一種特殊的線性表B、串的長度必須大于零

C、串中無素只能是字母D、空串就是空白串

2、空串與空格串是相同的，這種說法—o（易）

A、正確B、不正確

3、串是一中特殊的線性表，其特殊性體現(xiàn)在一。（易）

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

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

4、設(shè)有兩個串p和q,求q在P中首次出現(xiàn)的位置的運(yùn)算稱作—。（易）

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

5、設(shè)串s1='ABCDEFG',s2='PQRST',函數(shù)con（x,y）返回x和y串的連接串，

subs（s,i,））返回串s的從序號i的字符開始的J個字符組成的子串，len（s）返回串s

的長度，則con（subs（s1,2,len（s2））,subs（s1,len（s2）,2））的結(jié)果串是。（中）

A、BCDEFB、BCDEFGC、BCPQRSTD、BCDEFEF

6、設(shè)串的長度為n,則它的子串個數(shù)為o（易）

A、nB、n（n+1）C、n（n+1）/2D>n（n+1）/2+1

7、下列那些為空串（）（易）

A、S=""B、S=C、S=“6"D、S=“0”

8、S1="ABCD”，S2=“CD”貝ljS2在S3中的位置是）（易）

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

9、串是一種特殊的線性表，其特殊性體現(xiàn)在（）0（易）

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

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

10、串是（）o（易）

A、少于一個字母的序列B、任意個字母的序列

C、不少于一個字符的序列D、有限個字符的序列

11、串的長度是（）o（易）

A、串中不同字母的個數(shù)B、串中不同字符的個數(shù)

C、串中所含的字符的個數(shù)D、串中所含字符的個數(shù)，且大于0

12、若某串的長度小于一個常數(shù)，則采用()存儲方式最為節(jié)省空間。(易)

A、鏈?zhǔn)紹、堆結(jié)構(gòu)C、順序表

答案：1-5ABBBD6-10CBCBD11-12CC

三、填空題：

1、串的兩種最基本的存儲方式是—。(易)

2、兩個串相等的充分必要條件是—。(易)

3、空串是—,其長度等于—o(易)

4、空格串是—,其長度等于—o(易)

5、設(shè)s='AM—A—TEACHER',其長度是。(易)

6、串s='abcdef',s1='cde',s1在s中的位置為。(易)

7、廣義表A=(a,(b,cd))；其表頭為,表尾為o(中)

8、廣義表A=(a,A)；其表頭為,表尾為o(易)

9、串是每個結(jié)點(diǎn)僅由一個字符組成的()。(易)

答案：1.順序存儲方式和鏈接存儲方式

2.兩個串的長度相等且對應(yīng)位置的字符相同

3.零個字符的串、零

4.由一個或多個空格字符組成的串、其包含的空格個數(shù)

5.14

6、37、a((b,c,d))8、a(A)9、線性表

四、簡答題：

1、請寫出下列廣義表的表長、表頭、表尾。(易)

(1)A=()(2)B=(e)(3)C=(a,b,(c,d,e))(4)D=(a,D)

答案：(1)表長為0,表頭為()，表尾為()

(2)表長為1,表頭為e,表尾為()

(3)表長為3,表頭為a,表尾為(b,(c,d,e))

(4)表長為2,表頭為a,表尾為(D)

五、編程題：

1.編寫一個程序，要求有鍵盤輸入三個數(shù)，計(jì)算以這三個數(shù)為邊長的三角形的面

積(假定輸入的邊長是有效的)。(中)

2.有一函數(shù)，其函數(shù)關(guān)系如下，試編程求對應(yīng)于每一自變量的函數(shù)值。(中)

1(x<0)

Y

yk0(x=0)

-1(x>0)

答案:1>#incIude"math,h”

main()

{fIoata,b,c,p,s;

scanf(，&a,&b,&c);

p=(a+b+c)/2;

s=sqrt(p*(p-a)*(p-b)*(p-c));

printf("%.2f\n,s);

}

2、main0

{intx,y;

scanf("%d",&x);

if(x<0)y=1;

if(x=0)y=0;

if(x>0)y=-1;

prinft(“％d\n”,y);

}

第五章數(shù)組

一、名詞解釋：

1、壓縮存儲（易）

2、特殊矩陣（易）

3、稀疏矩陣（易）

答案：1、壓縮存儲：為多個值相同的元分配一個存儲空間，對零元不分配存儲空間。

2、特殊矩陣：值相同的元素或者是零元素分布的有規(guī)律則稱為特殊矩陣。

3^稀疏矩陣：在一個m*n的矩陣中，有t個非0元，其稀疏因子為t/（m*n）,如果稀

疏因子小于0.05就稱為稀疏矩陣。

二、選擇題：

1、設(shè)數(shù)組a[7][6]的基地址為1024,每個元素占2個存儲單元，若以行序?yàn)橹餍蝽?/p>

序存儲，則元素a口⑷的存儲地址是（中）

A、1058B、1056C、1098D、答案A,B,C都不對

2、二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從。到7,列下標(biāo)J

從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]

的起始地址為—o（中）

A、SA+141B、SA+180C、SA+222D、SA+225

3、二維數(shù)組A中，每個元素的長度為3個字節(jié)，行下標(biāo)i從0到7,列下標(biāo)j從

0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是—o

仲）

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

4、二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從。到7,列下標(biāo)J

從0到9,從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]

的起始地址為—O(中)

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

答案：1-4BBCC

三、填空題：

1、已知二維數(shù)組采用行序?yàn)橹鞣绞酱鎯?，每個元素占k個存儲單元，并

且第一個元素的存儲地址是LOC(A[O][O]),則的地址是。(中)

2、二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯Γ總€元素占一個存儲單元并且

A[0][0]的存儲地址是200,則A[6][12]的地址是—。(中)

3、二維數(shù)組A[10…20][5…10]采用行序?yàn)橹鞣绞酱鎯?，每個元素占4個存儲單

元,并且A[10][5]的存儲地址是1000,則A[18][9]的地址是____。(中)

4、現(xiàn)有一個n階的對稱矩陣a[n][n],現(xiàn)將其壓縮存儲在一個一維數(shù)組s[m]中，

則m=,若以行序?yàn)橹餍蜻M(jìn)行存儲，則元素a[i][J](i>=j)在s中的下標(biāo)

"o(中)

5、在一個m*n的矩陣中，若a[0][0]是第一個元素，則a[i][j]是第個元

素。素)

答案：1、LOG(A[OJ[O])+(n*i+j)*k2.、3263、1208

4、n(n+1)/2i(i-1)/2+j-15、i*n+j

四、編程題：

1、編寫一程序，求1+2+3+4+...+100的值(中)

2、菱形的輸出(前5行)(中)

答案：1、main()

{inti,sum=0;

for(i=1;i<=100;i++)sum+二i;

printf("sum二%d\n”,sum);

}

2、main()

{inti,j;

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

{for(j=1;j<=3-i;j++)printf(u“)；

for(j=1;j<=2*i-1;j++)printf(;

printf(<<\nM);

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

{for(j=1;j<=i;j++)printf(““)；

for(j=1;j<=5-2*i;j++)printf("*");

printf(u\nn);

)

}

第六章樹

一、選擇題:

1、由于二叉樹中每個結(jié)點(diǎn)的度最大為2,所以二叉樹是一種特殊的樹，這種說法

o(易)

A、正確B、錯誤

2、假定在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15,單分支結(jié)點(diǎn)數(shù)為30個，則葉子結(jié)

點(diǎn)數(shù)為個。(易)

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

3、按照二叉樹的定義,具有3個結(jié)點(diǎn)的不同形狀的二叉樹有種。（易）

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

4、按照二叉樹的定義,具有3個不同數(shù)據(jù)結(jié)點(diǎn)的不同的二叉樹有種。（易）

A、5B、6C、30D、32

5、深度為5的二叉樹至多有個結(jié)點(diǎn)。（易）

A、16B、32C、31D、10

6、設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的

結(jié)點(diǎn)數(shù)至少為o（易）

A、2hB、2h-1C、2h+1D、h+1

7、對一個滿二叉樹，m個樹葉，n個結(jié)點(diǎn)，深度為h,則o（易）

A、n=h+mB、h+m=2nC、m=h-1D、n=2h-1

8、任何一棵二叉樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序―。

（易）

A、不發(fā)生改變B、發(fā)生改變C、不能確定D、以上都不對

9、如果某二叉樹的前根次序遍歷結(jié)果為stuwv,中序遍歷為uwtvs,那么該二叉

樹的后序?yàn)椤猳（易）

A、uwvtsB、vwutsC、wuvtsD、wutsv

10、二叉樹的前序遍歷序列中，任意一個結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說

法—o（易）

A、正確B、錯誤

11、某二叉樹的前序遍歷結(jié)點(diǎn)訪問順序是abdgcefh,中序遍歷的結(jié)點(diǎn)訪問順序是

dgbaechf,則其后序遍歷的結(jié)點(diǎn)訪問順序是o（易）

A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca

12、在一非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右邊—。（易）

A、只有右子樹上的所有結(jié)點(diǎn)B、只有右子樹上的部分結(jié)點(diǎn)

C、只有左子樹上的部分結(jié)點(diǎn)D、只有左子樹上的所有結(jié)點(diǎn)

13、如圖6、1所示二叉樹的中序遍歷序列是。（易）

A、abcdgefB、dfebagcC、dbaefcgD、defbagc

圖6、1

14、一棵二叉樹如圖6、2所示，其中序遍歷的序列為（易）

A^abdgcefhB、dgbaechfC、gdbehfcaD、abcdefgh

15、設(shè)a,b為一棵二叉樹上的兩個結(jié)點(diǎn)，在中序遍歷時(shí),a在b前的條件是o

（易）

A^a在b的右方B、a在b的左方C、a是b的祖先D、a是b的子孫

16、已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序

遍歷序列是—o（易）

A、acbedB、decabC、deabcD、cedba

17、實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉

樹采用—存儲結(jié)構(gòu)。（易）

A、二叉鏈表B、廣義表存儲結(jié)構(gòu)C、三叉鏈表D、順序存儲結(jié)構(gòu)

18、如圖6、3所示的4棵二叉樹，不是完全二叉樹。（易）

(A)(B)(C)(D)

圖6.3

19、如圖6、4所示的4棵二叉樹，是平衡二叉樹。（易）

(A)(B)(C)(D)

圖6.4

20、在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是—o（易）

A、t.left=NULLB、t.Itag=1

C、t.Itag=1且=NULLD、以上都不對

21、二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)