數(shù)據(jù)結(jié)構(gòu)試題-試卷一-含答案

模擬試題一模擬試題一

一、選擇題（30分）

1.組成數(shù)據(jù)的基本單位是(

)。

A)數(shù)據(jù)項(xiàng)

B）數(shù)據(jù)類型

C）數(shù)據(jù)元素

D）數(shù)據(jù)變量

2.線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址(

)。

A)必須是連續(xù)的

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

C)一定是不連續(xù)的

D）連續(xù)或不連續(xù)都可以

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

)。

A)O(1)

B)O(n)

C)O(n2)

D)O(nlog2n)

4.棧結(jié)構(gòu)通常采用的兩種結(jié)構(gòu)是(

)。

A)順序存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu)

B)散列方式和索引方式

C)鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組

D)線性鏈表結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)

5.表達(dá)式a*(b+c)-d的后綴表達(dá)式是(

)。

A)abcd+-

B）abc+*d-

C）abc*+d-

D）一十*abcd

6.棧和隊(duì)列的共同特點(diǎn)是(

)。

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

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

C)只允許在端點(diǎn)處插入和刪除元素

D）沒有共同點(diǎn)

7.已知一棵二叉樹前序遍歷和中序遍歷分別為ABDEGCFH和DBGEACHF，則該二叉樹的后序遍歷為(

)。

A)GEDHFBCA

B)DGEBHFCA

C)ABCDEFGH

D)ACBFEDHG

8.鏈表不具有的特點(diǎn)是(

)，

A)不必事先估計(jì)存儲(chǔ)空間

B）可隨機(jī)訪問任一元素

C)插入刪除不需要移動(dòng)元素

D）所需空間與線性表長(zhǎng)度成正比

9.在深度為5的滿二叉樹中，葉子結(jié)點(diǎn)的個(gè)數(shù)為(

)。

A)32

B)31

C)16

D)15

10.最簡(jiǎn)單的交換排序方法是(

)。

A)快速排序

B）選擇排序

C）堆排序

D）冒泡排序

11.數(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)

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

)。

A)必須是連續(xù)的

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

C)-定是不連續(xù)的

D）連續(xù)與否均可以

13.設(shè)循環(huán)隊(duì)列Q[l...n-l]的首尾指針為f和r，當(dāng)插入元素時(shí)尾指針r加1，首指針F總是指在隊(duì)列中第一個(gè)元素的前一個(gè)位置，則隊(duì)列中元素計(jì)數(shù)為(

)。

A)r-f

B)n-(r-f)

C)(r-f+n)%n

D)(f-r+n)%n

14.完成堆排序的全過程需要(

)個(gè)記錄大小的輔助空間。

A)1

B)n

C)nlog2n

D)|_nlog2n_|

15.若給定的關(guān)鍵字集合為{20，15，14，18，21，36，40，10}，一趟快速排序結(jié)束時(shí)，鍵值的排列為(

)。

A)10,15,14,18,20,36,40,21

B)10,15,14,18,20,40,36,21

C)10,15,14,20,18,40,36,21

D)15,10,14,18,20,36,40,21

二、填空題（22分）

1.一棵完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則共有__________個(gè)結(jié)點(diǎn)。

2.有向圖G用鄰接矩陣A{1…n，1...n}存儲(chǔ)，其第i列的所有元素等于頂點(diǎn)i的__________。

3.設(shè)有一空棧，棧頂指針為IOOOH（十六進(jìn)制），現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過Push,Push，Pop，Push，Pop，Push，Push操作后，輸出序列為__________。

4.在具有n(n≥1)個(gè)結(jié)點(diǎn)的k叉樹中，有__________個(gè)空指針。

5.模式中“ababbabbab”的前綴函數(shù)為__________。

6.設(shè)圖G的頂點(diǎn)數(shù)為n，邊數(shù)為e，第i個(gè)頂點(diǎn)的度數(shù)為D(vi)，則e=__________即邊數(shù)與各項(xiàng)點(diǎn)的度數(shù)之間的關(guān)系）。

7.按__________遍歷二叉樹，可以得到按值遞增的關(guān)鍵值序列，在下圖所示的二叉樹中，檢索關(guān)鍵值85的過程中，需與85進(jìn)行比較的關(guān)鍵碼序列為__________。

8.下列算法實(shí)現(xiàn)二叉樹排序樹上的查找，請(qǐng)?jiān)诳崭裉幪钌线m當(dāng)?shù)恼Z句，完成上述功能。

bitreptr*bstsearch(bitreptr

*t,

keytypek)

{

if(t==NULL)

returnNULL;

else

while(t!=NULL)

{

if(t->key==k__________;

if(t->key>k)__________;

else__________;

}

}

三、應(yīng)用題(16分)1.設(shè)二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下所示。（4分）

(1)根據(jù)其存儲(chǔ)結(jié)構(gòu)，畫出二叉樹。

(2)寫出按前序、中序、后序遍歷該二叉樹所得的結(jié)點(diǎn)序列。

(3)畫出二叉樹的后序線索化樹。

2.-棵完全二叉樹共有21個(gè)結(jié)點(diǎn)，現(xiàn)順序存放在一個(gè)矢量中，矢量的下標(biāo)正好為結(jié)點(diǎn)的序號(hào)，試問序號(hào)為12的雙親結(jié)點(diǎn)存在嗎？是什么？（4分）

3.線性表有順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)，簡(jiǎn)述各自的優(yōu)缺點(diǎn)。（4分）

4.何謂隊(duì)列的“假溢”現(xiàn)象？如何解決？（4分）

四、算法設(shè)計(jì)（32分）

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

2.試設(shè)計(jì)一個(gè)算法，求出指定結(jié)點(diǎn)在給定的二叉樹中的層次。

3.已知一個(gè)單鏈表中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，并且其結(jié)點(diǎn)數(shù)不少于2。試編寫算法以判斷該鏈表中從第二項(xiàng)起的每個(gè)元素值是否等于其序號(hào)的平方減去其前驅(qū)結(jié)點(diǎn)的值，若滿足，返回True，否則返回False。4.在含有n個(gè)元素的堆中增加一個(gè)元素，且調(diào)整為堆。模擬試題一答案

模擬試題一參考答案

一、選擇題

1.C

2.D

3.B

4.A

5.B

6.C

7.B

8.B

9.C

10.D

11.C

12.D

13.D

14.A

15.A

二、填空題

1.20。

2.入度即ID(i)。

3.2，3，5，4，

1.

4.n(k-l)+l。

5.Next[j]=(0

1

1

23

1

2312)。

6.

7.中序，55

9057

7585a

8.Return(t),Return(bstsearch(t->lchild,k)),Return(bstsearch(t->rchild,k))。

三、應(yīng)用題

1.(1)該存儲(chǔ)結(jié)構(gòu)對(duì)應(yīng)的二叉樹為

(2)先序序列為EADCBFHGI。

中序序列為ABCDEFGHI。

后序序列為BCDAGIHFE。

(3)后序線索樹為。

2.序號(hào)為12的雙親結(jié)點(diǎn)存在。因?yàn)檫@棵完全二叉樹除根結(jié)點(diǎn)外的其余20個(gè)結(jié)點(diǎn)都有1個(gè)唯一的雙親結(jié)點(diǎn)。序號(hào)為i的雙親結(jié)點(diǎn)是|_i/2_|，所以12的雙親結(jié)點(diǎn)為|_12/2_|=6。

3.在順序表結(jié)構(gòu)中，邏輯相鄰的元素其存儲(chǔ)位置也相鄰。只要確定了線性表的起始存儲(chǔ)位置，就可以隨機(jī)存取任意數(shù)據(jù)元素。所以順序表的優(yōu)點(diǎn)是方便查找，缺點(diǎn)是做插入和刪除操作時(shí)需移動(dòng)大量元素。鏈表結(jié)構(gòu)不要求邏輯相鄰元素的存儲(chǔ)位置相鄰，即可存放內(nèi)存中任何位置，元素間邏輯關(guān)系依指針相連。查找時(shí)必須從表頭指針開始依序查找。但插入和刪除操作時(shí)無需移動(dòng)元素，只修改元素的指針即可。所以鏈表的優(yōu)點(diǎn)是方便插入和刪除操作，缺點(diǎn)是不能隨機(jī)查找任一元素。

4.隨著數(shù)據(jù)元素的不斷插入和刪除，隊(duì)列的隊(duì)首指針已指向允許插入的最大位置，此時(shí)或許還有很多可插入的空間，但卻不能插入數(shù)據(jù)元素了，這種現(xiàn)象稱為隊(duì)列的“假溢”。解決的方法是采用循環(huán)鏈表（隊(duì)列）。

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

1.刪除表中所有值大于min且小于max的元素的算法如下：

Typedef

struct

node{

intdata;

structnode+next

}

linklist;

delete(linklist

*head,int

max,int

min)

/*刪除有序單鏈表中所有值大于min且小于max的元素*/

{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;

2.求出指定結(jié)點(diǎn)在給定的二叉樹中的層次的算法：

Void

level(bitree

*t,

bitree

*p,inth,int

th)

/*t為指向二叉樹的指針，p指向待找的結(jié)點(diǎn)，h為p結(jié)點(diǎn)的層次數(shù)，th為當(dāng)前的層次數(shù)*/

{if(t==NULl)

h=0;

/*樹為空時(shí)返回0*/

else

if(p==t)

h=th;

/*找到結(jié)點(diǎn)p時(shí)*/

else

{

level(p,t->lchild,h，th+l);

/*在左子樹中查找*/

if（h==-1）level(p,t->rchild,h，th+l);/*在右子樹中查找*/

}

}3.判斷鏈表中從第二項(xiàng)起的每個(gè)元素值是否等于其序號(hào)的平方減去其前驅(qū)結(jié)點(diǎn)的值的算法如下：

intJudge(linklist

*head)

{intflag,i

linklist

*P,*q;

q=head->next;

flag=False;

i=2;

while(p!-NUIL)(

if(p->data==i*i-q->data)

flag=True;

else

returnFalse;

q=p;

p=p->next;

i++;

)

returnflag;

}4.在含有n個(gè)元素的堆中增加一個(gè)元素，且調(diào)整為堆的算法：

voidheapinsert(RectyPe

R[],datatypex)

/*在堆R[1]到R