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

模擬試題一模擬試題一

一、選擇題（30分）

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

)。

A)數(shù)據(jù)項

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

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

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

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

)。

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

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

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

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

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

)。

A)O(1)

B)O(n)

C)O(n2)

D)O(nlog2n)

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

)。

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

B)散列方式和索引方式

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

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

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

)。

A)abcd+-

B）abc+*d-

C）abc*+d-

D）一十*abcd

6.棧和隊列的共同特點是(

)。

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

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

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

D）沒有共同點

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

)。

A)GEDHFBCA

B)DGEBHFCA

C)ABCDEFGH

D)ACBFEDHG

8.鏈表不具有的特點是(

)，

A)不必事先估計存儲空間

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

C)插入刪除不需要移動元素

D）所需空間與線性表長度成正比

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

)。

A)32

B)31

C)16

D)15

10.最簡單的交換排序方法是(

)。

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)酱鎯r，其地址(

)。

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

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

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

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

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

)。

A)r-f

B)n-(r-f)

C)(r-f+n)%n

D)(f-r+n)%n

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

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

A)1

B)n

C)nlog2n

D)|_nlog2n_|

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

)。

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個結(jié)點，則共有__________個結(jié)點。

2.有向圖G用鄰接矩陣A{1…n，1...n}存儲，其第i列的所有元素等于頂點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)個結(jié)點的k叉樹中，有__________個空指針。

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

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

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

8.下列算法實現(xiàn)二叉樹排序樹上的查找，請在空格處填上適當(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è)二叉樹的順序存儲結(jié)構(gòu)如下所示。（4分）

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

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

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

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

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

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

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

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

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

3.已知一個單鏈表中每個結(jié)點存放一個整數(shù)，并且其結(jié)點數(shù)不少于2。試編寫算法以判斷該鏈表中從第二項起的每個元素值是否等于其序號的平方減去其前驅(qū)結(jié)點的值，若滿足，返回True，否則返回False。4.在含有n個元素的堆中增加一個元素，且調(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)該存儲結(jié)構(gòu)對應(yīng)的二叉樹為

(2)先序序列為EADCBFHGI。

中序序列為ABCDEFGHI。

后序序列為BCDAGIHFE。

(3)后序線索樹為。

2.序號為12的雙親結(jié)點存在。因為這棵完全二叉樹除根結(jié)點外的其余20個結(jié)點都有1個唯一的雙親結(jié)點。序號為i的雙親結(jié)點是|_i/2_|，所以12的雙親結(jié)點為|_12/2_|=6。

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

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

四、算法設(shè)計

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é)點在給定的二叉樹中的層次的算法：

Void

level(bitree

*t,

bitree

*p,inth,int

th)

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

{if(t==NULl)

h=0;

/*樹為空時返回0*/

else

if(p==t)

h=th;

/*找到結(jié)點p時*/

else

{

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

/*在左子樹中查找*/

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

}

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

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個元素的堆中增加一個元素，且調(diào)整為堆的算法：

voidheapinsert(RectyPe

R[],datatypex)

/*在堆R[1]到R