數(shù)據(jù)結構期末考試題1

一、單選題(每題2分，共20分)

1.1.對一個算法的評價，不包括如下(B)方面的內容。

A.健壯性和可讀性B.并行性C.正確性D.時空復雜度

2.2.在帶有頭結點的單鏈表HL中，要向表頭插入?個由指針p指向的結點，則執(zhí)

行()。

A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;

C.p->next=HL;p=HL;D.HL=p;p->next=HL;

3.3.對線性表，在下列哪種情況下應當采用鏈表表示？()

A.經(jīng)常需要隨機地存取元素B.經(jīng)常需要進行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲空間D.表中元素的個數(shù)不變

4.4.一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是(C)

A.231B.321

C.312D.123

5.5.AOV網(wǎng)是一種()。

A.有向圖B.無向圖C.無向無環(huán)圖D.有向無環(huán)圖

6.6.采用開放定址法處理散列表的沖突時，其平均查找長度()。

A.低于鏈接法處理沖突B.高于鏈接法處理沖突

C.與鏈接法處理沖突相同D.高于二分查找

7.7.若需要利用形參直接訪問實參時，應將形參變量說明為()參數(shù)。

A.值B.函數(shù)C.指針D.引用

8.8.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個單鏈表中的結點都具有相同的

()。

A.行號B.列號C.元素值D.非零元素個數(shù)

9.9.快速排序在最壞情況下的時間復雜度為()o

2

A.O(log2n)B.O(nlog2n)C.0(n)D.0(n)

10.10.從二叉搜索樹中查找一個元素時，其時間復雜度大致為()。

2

A.O(n)B.O(l)C.O(log2n)D.O(n)

二、二、運算題(每題6分，共24分)

1.1.數(shù)據(jù)結構是指數(shù)據(jù)及其相互之間的。當結點之間存在M對N(M：

N)的聯(lián)系時，稱這種結構為。

2.2.隊列的插入操作是在隊列的—尾進行，刪除操作是在隊列的一首

______進行。

3.3.當用長度為N的數(shù)組順序存儲一個棧時，假定用top=N表示?？?，則表示棧滿

的條件是一top==0_(要超出才為滿)o

4.4.對于一個長度為n的單鏈存儲的線性表，在表頭插入元素的時間復雜度為

,在表尾插入元素的時間復雜度為。

5.5.設W為一個二維數(shù)組，其每個數(shù)據(jù)元素占用4個字節(jié)，行下標i從。到7,列

下標j從0到3,則二維數(shù)組W的數(shù)據(jù)元素共占用個字節(jié)。W中第6行的

元素和第4列的元素共占用..個字節(jié)。若按行順序存放二維數(shù)組W,其起始

地址為100,則二維數(shù)組元素W[6,3]的起始地址為

6.6.廣義表A=(a,(a,b),((a,b),c)),則它的深度為,它的長度為

7.7.二叉樹是指度為2的樹。一棵結點數(shù)為N的二叉樹，其

所有結點的度的總和是。

8.8.對一棵二叉搜索樹進行中序遍歷時，得到的結點序列是一個。對

?棵由算術表達式組成的二叉語法樹進行后序遍歷得到的結點序列是該算術表達式的

9.9.對于一棵具有n個結點的二叉樹，用二叉鏈表存儲時，其指針總數(shù)為

個，其中個用于指向孩子，個指針

是空閑的。

10.10.若對一棵完全二叉樹從0開始進行結點的編號，并按此編號把它順序存儲到一維

數(shù)組A中，即編號為0的結點存儲到A[0]中。其余類推，則A[i]元素的左孩子元素為

，右孩子元素為,雙親元素為。

11.11.在線性表的散列存儲中，處理沖突的常用方法有和

______________________________兩種。

12.12.當待排序的記錄數(shù)較大，排序碼較隨機且對穩(wěn)定性不作要求時，宜采用

排序；當待排序的記錄數(shù)較大，存儲空間允許且要求排序是穩(wěn)定時，

宜采用排序。

三、三、運算題(每題6分，共24分)

1.1.已知一個6x5稀疏矩陣如下所示，

00001

00000

0-1000

0000-2

50000

00700

試：

(1)(1)寫出它的三元組線性表；

(2)(2)給出三元組線性表的順序存儲表示。

2.2.設有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸

入各個數(shù)據(jù)而生成的二叉搜索樹。

3.3.對于圖6所示的有向圖若存儲它采用鄰接表，并且每個頂點鄰接表中的邊結點都

是按照終點序號從小到大的次序鏈接的，試寫出：

(1)從頂點①出發(fā)進行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹；

(2)從頂點②出發(fā)進行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹；

4.4.已知一個圖的頂點集V和邊集E

分別為：

V={1,2,3,4,5,6,7};

E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6

>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};

若存儲它采用鄰接表，并且每個頂點鄰

接表中的邊結點都是按照終點序號從小到

大的次序鏈接的，按主教材中介紹的拓樸排

序算法進行排序，試給出得到的拓樸排序的

序列。

四、四、閱讀算法(每題7分，共14分)

1.1.intPrime(intn)

(

inti=l;

intx=(int)sqrt(n);

while(++i<=x)

if(n%i=0)break;

if(i>x)return1;

elsereturn0;

)

(1)(1)指出該算法的功能；

(2)(2)該算法的時間復雜度是多少？

2.2.寫出下述算法的功能:

voidAJ(adjlistGL,inti,intn)

(

QueueQ;

InitQueue(Q);

cout?i?,

visited[i]=true;

QInsert(Q,i);

while(!QueucEmpty(Q)){

intk=QDclete(Q);

edgenode*p=GL[k];

while(p!=NULL)

|

intj=p->adjvex;

if(!visited[j])

(

cout<<j?l

visited[j]=true;

QInsert(Q,j);

}

p=p->next;

五、五、算法填空(共8分)

如下為二分查找的非遞歸算法，試將其填寫完整。

IntBinsch(ElemTypeA[],intn,KeyTypeK)

{

intlow=0;

inthigh=n-l;

while(low<=high)

{

intmid=；

if(K==A[mid].key)returnmid;〃查找成功，返回元素的下標

elseif(K<[mid].key)

____________________________________；//在左子表上繼續(xù)查找

else;//在右子表上繼續(xù)查

找

}

return-1;//查找失敗，返回-1

}

六、六、編寫算法(共8分)

HL是單鏈表的頭指針，試寫出刪除頭結點的算法。

ElemTypeDeleFront(LNode*&HL)

參考答案

單選題(每題2分，共20分)

l.B2.A3.B4.C5.D6.B7.D8.A9.D10.C

二、二、填空題（每空1分，共26分）

1.1.聯(lián)系圖I（或圖結構）

2.2.尾首

3.3.top==0

4.4.0(1)O(n)

5.5.12844108

6.6.33

7.7.有序n-1

6558.8.有序序列后綴表達式（或逆波蘭式）

1519.9,.2nn-1n+1

10.10.2i+l2i+2（i-l）/2

32-1

11.11.開放定址法鏈接法

45-212.12.快速歸并

515三、三、運算題(每題6分，共24分)

6371.1.（1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)

圖7(2)

(b)

圖8

2.2.如圖8所示。

3.3.DFS：①②③④⑤

BFS：②③④⑤①

4.4.拓樸排序為：4365721

四、四、閱讀算法（每題7分，共14分）

1.1.（1）判斷n是否是素數(shù)（或質數(shù)）

（2）O（）

2.2.功能為：從初始點w出發(fā)廣度優(yōu)先搜索山鄰接表GL所表示的圖。

五、五、算法填空（8分）

(low+high)/2high=mid-llow=mid+l

六、六、編寫算法(8分)

ElemTypeDeleFront(LNode*&HL)

{

if(HL==NULL){

cerr?n空表"?endl;

exit(l);

}

LNode*p=HL;

HL=HL->next;

ElemTypetemp=p->data;

deletep;

returntemp;

一、一、單選題（每題2分，共20分）

1.1.棧和隊列的共同特點是（）。

A.只允許在端點處插入和刪除元素

B.都是先進后出

C.都是先進先出

D.沒有共同點

2.2.用鏈接方式存儲的隊列，在進行插入運算時（）.

A.僅修改頭指針B.頭、尾指針都要修改

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

3.3.以下數(shù)據(jù)結構中哪一個是非線性結構？（）

A.隊列B.棧C.線性表D.二叉樹

4.4.設有一個二維數(shù)組A[問[〃],假設A[0][0]存放位置在644（io）,A⑵[2]存放位置

在676（⑼，每個元素占一個空間，問4[3][3]（⑼存放在什么位置？腳注（⑼表示用10

進制表示。

A.688B.678C.692D.696

5.5.樹最適合用來表示（）。

A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素

C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)

6.6.二叉樹的第k層的結點數(shù)最多為（）.

A.21MB.2K+1C.2K-1D.2k"'

7.7.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[l]中，現(xiàn)進

行二分查找，則查找A[3]的比較序列的下標依次為（）

A.1,2,3B.9,5,2,3

C.9,5,3D.9,4,2,3

8.8.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為

A.O（1）B.O（n）C.O（log2n）D.O（n2）

9.9.對于線性表（7,34,55,25,64,46,20,10）進行散列存儲時，若選用H

（K）=K%9作為散列函數(shù)，則散列地址為1的元素有（）個，

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

10.10.設有6個結點的無向圖，該圖至少應有（）條邊才能確保是一個連通圖。

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

二、二、填空題（每空1分，共26分）

1.1.通常從四個方面評價算法的質量：、、和

2.2.一個算法的時間復雜度為（〃3+“210g2〃+14〃）/”2,其數(shù)量級表示為。

3.3.假定一棵樹的廣義表表示為A（C,D（E,F,G）,H（I,J））,則樹中所含的

結點數(shù)為個，樹的深度為,樹的度為?

4.4.后綴算式923+-102/-的值為。中綴算式（3+4X）-2Y/3對應的后

綴算式為?

5.5.若用鏈表存儲一棵二叉樹時，每個結點除數(shù)據(jù)域外，還有指向左孩子和右孩子的

兩個指針。在這種存儲結構中，n個結點的二叉樹共有個指針域，其中有

個指針域是存放了地址，有個指針是空指針。

6.6.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含

邊結點分別有個和個。

7.7.AOV網(wǎng)是一種的圖。

8.8.在一個具有n個頂點的無向完全圖中，包含有條邊，在一個具有n個頂

點的有向完全圖中，包含有條邊。

9.9.假定一個線性表為（12,23,74,55,63,40）,若按Key%4條件進行劃分，使得同一余

數(shù)的元素成為一個子表，則得到的四個子表分別為、

、和。

10.10.向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高

度

11.11.在堆排序的過程中,對任一分支結點進行篩運算的時間復雜度為,整個

堆排序過程的時間復雜度為。

12.12.在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。

三、三、運算題(每題6分，共24分)

1.1.在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A[0].next,試寫出該線性

表。

A01234567

2.2.請畫出圖10的鄰接矩陣和鄰接表。

3.3.已知個圖的頂點集V和邊集E分別為:

V={1,2,3,4,5,6,71;

E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,

(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};

用克魯斯卡爾算法得到最小生成樹，試寫出在最小生

成樹中依次得到的各條邊。

4.4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時,每加入

一個數(shù)據(jù)后堆的變化。

閱讀算法(每題7分，共14分)

1.1.LinkListmynote(LinkListL)

{//L是不帶頭結點的單鏈表的頭指針

if(L&&L->next){

q=L；L=L—>next；p=L；

SI：while(p->next)p=p—>next；

S2：p—>next=q；q->next=NULL；

returnL；

請回答下列問題：

(1)說明語句SI的功能；

(2)說明語句組S2的功能;

(3)設鏈表表示的線性表為(aba2,…,aQ，寫出算法執(zhí)行后的返回值所表示的線性

2.2.voidABC(BTNode*BT)

{

ifBT{

ABC(BT->left);

ABC(BT->right);

cout?BT->data?,

該算法的功能是：

五、五、算法填空(共8分)

二叉搜索樹的查找——遞歸算法：

boolFind(BTreeNode*BST,ElemType&item)

if(BST=NULL)

returnfhlse;〃查找失敗

else(

if(item==BST->data){

item=BST->data;//^r找成功

return___________;}

elseif(item<BST->data)

returnFind(______________3tem);

elsereturnFind(_______________,item);

}//if

六、六、編寫算法(共8分)

統(tǒng)計出單鏈表HL中結點的值等于給定值X的結點數(shù)。

intCountX(LNode*HL,ElemTypcx)

參考答案

一、單選題(每題2分，共20分)

LA2.D3.D4.C5.C6.D7.D8.C9.D10.A

——、二、填空題(每空I分，共26分)

1.1.正確性易讀性強壯性高效率

2.2.O(n)

3.3.933

4.4.-134X*+2Y*3/?

5.5.2nn-1n+1

6.6.e2e

7.7.有向無回路

8.8.n(n-l)/2n(n-l)

9.9.(12,40)()(74)(23,55,63)

10.10.增加1

11.11.O(log2n)O(nlog2n)

12.12.歸并

三、運算題(每題6分，共24分)

1.1.線性表為：(78,50,40,60,34,90)

01110'

10101

11011

10101

2.2.鄰接矩陣：L01110J

鄰接表如圖11所示：

圖11

3.3.用克魯斯卡爾算法得到的最小生成樹為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20

四、四、閱讀算法（每題7分，共14分）

1.1.（1）查詢鏈表的尾結點

（2）將第一個結點鏈接到鏈表的尾部，作為新的尾結點

（3）返回的線性表為⑸處,…,an,ai）

2.2.遞歸地后序遍歷鏈式存儲的二叉樹。

五、五、算法填空（每空2分，共8分）

trueBST->leftBST->right

六、六、編寫算法（8分）

intCountX（LNode*HL,ElemTypex）

{inti=0;LNode*p=HL;//i為計數(shù)器

while（p!=NULL）

{if（P->data=x）i++;

p=p->next;

}//while,出循環(huán)時i中的值即為x結點個數(shù)

returni;

}//CountX

一、一、單選題（每小題2分，共8分）

1、1、在一個長度為n的順序線性表中順序查找值為x的元素時，查找成功時的平均查找

長度（即x與元素的平均比較次數(shù)，假定查找每個元素的概率都相等）為（B）。

AnBn/2C（n+l）/2D（n-l）/2

2、2、在一個單鏈表中，若q所指結點是p所指結點的前驅結點，若在q與p之間插入一個s

所指的結點，則執(zhí)行（A）。

As_*link=pflink;p-*link=s;Bp-*iink=s;s-*link=q;

Cp—link=s-link;s-*link=p;Dq-"link=s;s-link=p;

3、3、棧的插入和刪除操作在（）進行。

A棧頂B棧底C任意位置D指定位置

4、4、由權值分別為11,8,6,2,5的葉子結點生成一棵哈夫曼樹，它的帶權路徑

長度為（）

A24B71C48D53

二、二、填空題（每空1分，共32分）

1、1、數(shù)據(jù)的邏輯結構被分為、、和四種。

2、2、?種抽象數(shù)據(jù)類型包括和兩個部分。

3、3、在下面的數(shù)組a中鏈接存儲著一個線性表，表頭指針為a[o].next,則該線性表為

a012345678

605642387425

4376201

4、4、在

以HL為表頭指針的帶表頭附加結點的單鏈表和循環(huán)單鏈表中，判斷鏈表為空的條

件分別為和o

5、5、用具有n個元素的一維數(shù)組存儲一個循環(huán)隊列，則其隊首指針總是指向隊首元

素的，該循環(huán)隊列的最大長度為.

6、6、當堆棧采用順序存儲結構時，棧頂元素的值可用--------------表示；當堆棧

采用鏈接存儲結構時，棧頂元素的值可用表示。

7、7、一棵高度為5的二叉樹中最少含有個結點，最多含有個結點；

一棵高度為5的理想平衡樹中，最少含有個結點，最多含有個

結點。

8、:)在圖的鄰接表中，每個結點被稱為，通常它包含三個域：一是

：1是：:是。

9、9、在一個索引文件的索引表中,每個索引項包含對應記錄的和

___________兩項數(shù)據(jù)。

10、10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))),

則樹中所含的結點數(shù)為個，樹的深度為，樹的度為,結

點H的雙親結占為孩子結點為。

11/11、-在堆排序而過程%;對任一分支結點進行篩運算的時間復雜度為

，整個堆排序過程的時間復雜度為。

12、12、在對m階的B_樹插入元素的過程中，每向一個結點插入一個索引

項(葉子結點中的索引項為關磁字和空指針)后，若該結點的索引項數(shù)等于

個，則必須把它分裂為個結點。

三、運算題(每小題6分，共24分)

1、1、已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫出對其進行

快速排序的每一次劃分結果。

2、2、一個線性表為B=(12,23,45,57,20,03,78,31,15,36),設散列表為

HT[0..12],散列函數(shù)為H(key)=key%13并用線性探查法解決沖突，請畫出散列

表，并計算等概率情況下查找成功的平均查找長度。

3、3、已知一棵二叉樹的前序遍歷的結果序列是ABECKFGHIJ,中序遍歷的結果是

EBCDAFHIGJ,試寫出這棵二叉樹的后序遍歷結果。

4、4、已知一個圖的頂點集V各邊集G如下：

V={0,1,2,3,4,5,6,7,8,9)；

E={(0,1),(0,4),(1,2),(1,7),(2,8),(3,4),(3,8),(5,6),(5,8),(5,

9),(6,7),(7,8),(8,9)}

當它用鄰接矩陣表示和鄰接表表示時，分別寫出從頂點V。出發(fā)按深度優(yōu)先搜索遍歷得

到的頂點序列和按廣度優(yōu)先搜索遍歷等到的頂點序列。

假定每個頂點鄰接表中的結點是按頂點序號從大到小的次序鏈接的。

圖深度優(yōu)先序列廣度優(yōu)先序列

鄰接矩陣表示時

鄰接表表示時

四、四、閱讀算法，回答問題(每小題8分，共16分)

1、假定從鍵盤上輸入一批整數(shù)，依次為：786345309134-1,請寫出輸出結

果。

#include<iostream.h>

#include<stdlib.h>

consstintstackmaxsize=30;

typedefintelemtype;

structstack{

elemtypestack[stackmaxsize];

inttop;

}；

#include"stack.h"

Voidmain()

{

stacka;

initstack(a);

intx;

cin?x;

while(x!=-1){

push(a,x);

cin?x;

}

while(!stackempty(a))

cout?pop(a)?””;

cout?endl;

}

該算法的輸出結果為：

2、閱讀以下二叉樹操作算法，指出該算法的功能。

Template<calsstype>voidBinTree<Type>：：

unknown(BinTreeNode<Type>*t){

BinTreeNode<Type>*p=t,*temp;

if(p!=NULL){

temp=p-*leftchild;

p->leftchild=pfrightchild;

p-*-rightchild=temp;

unknown(p->leftchild);

undnown(p-*rightchild);

)

)

該算法的功能是：_________________________________

五、五、算法填空，在畫有橫線的地方填寫合適的內容(10分)

對順序存儲的有序表進行二分查找的遞歸算法。

intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK)

{-

if(low<=high)

|

intmid=1

if(K==A[mid].key)

returnmid;

elseif(K<A[mid].key)

return2

else

return3

}

else

return4

編寫算法（10分）

編寫算法，將一個結點類型為Lnode的單鏈表按逆序鏈接，即若原單鏈表中存儲元素

的次序為a”……an.,,an,則逆序鏈接后變?yōu)?a”，a^,……a]。

Voidcontrary（Lnode*&HL）

數(shù)據(jù)結構試題（答案）

一、單選題（每小題2分，共8分）

題號1234

答案CDAB

二、填空題（每空1分，共32分）

1：集合、線性、樹、圖；

2：數(shù)據(jù)描述、操作聲名；

3：（38,56,25,60,42,74）；

4：HL-next=NULL；HL=HL-next；

5：前一個位置；n-1；

6：S.stack[S.top];HS-^data;

7：531

8：邊結點、鄰接點域、權域、鏈域；

9：索引值域、開始位置域；

10：10、3、3、B、I和J；

11：O（log2n）＞O（nlog2n）;

12：m、m-1

三、運算題（每小題6分，共24分）

劃分次序劃分結果

第一次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

0123456789101112

78150357452031233612

查找成功的平均查找長度：ASLSUCC=14/10=1.4

3、此二叉樹的后序遍歷結果是：EDCBIHJGFA

4、

圖深度優(yōu)先序列廣度優(yōu)先序列

鄰接矩陣表示時0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9

鄰接表表示時0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5

四、閱讀算法，回答問題（每小題8分，共16分）

1、1、該算法的輸入結果是：349130456378

2、2、該算法的功能是：交換二叉樹的左右子樹的遞歸算法。

五、算法填空，在畫有橫線的地方填寫合適的內容(10分)

1、1是：(low+high)/2;

2是：Binsch(A,low,mid-1,K);

3是：Binsch(A,mid+1,high,K);

4是：-1；

六、編寫算法(10分)

根據(jù)編程情況，酌情給分。

(

Lnode*P=HL;

HL=NULL;

While(p!=null)

{

Lnode*q=p;

P=pfnext;

q—next=HL;

HL=q;

第一部分選擇題（30分）

一、一、項選擇題（本大題共15小題，每小題2分，共30分）在每小題列出的四個選項

中只有一個選項是符合題目要求的，請將正確選項前的字母填在題后的括號內。

1.算法指的是（）

A.計算機程序B.解決問題的計算方法

C.排序算法D.解決問題的有限運算序列

2.線性表采用鏈式存儲時，結點的存儲地址（）

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

B.連續(xù)與否均可

C.必須是連續(xù)的

D.和頭結點的存儲地址相連續(xù)

3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）

A.O（1）B.O（n）C.O（m）D.O（m+n）

4.由兩個棧共享一個向量空間的好處是：（）

A.減少存取時間，降低下溢發(fā)生的機率

B.節(jié)省存儲空間，降低上溢發(fā)生的機率

C.減少存取時間，降低上溢發(fā)生的機率

D.節(jié)省存儲空間，降低下溢發(fā)生的機率

5.設數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)

行出隊操作后其頭指針front值為()

A.front=front+lB.front=(front+l)%(m-l)

C.front=(front-1)%mD.front=(front+1)%m

6.如下陳述中正確的是()

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

C.串中元素只能是字母D.空串就是空白串

7.若目標串的長度為n,模式串的長度為[n/3],則執(zhí)行模式匹配算法時，在最壞情況下的

時間復雜度是()

A.0(3)B.0(n)C.0(n2)D.0(n3)

8.一個非空廣義表的表頭()

A.不可能是子表B.只能是子表

C.只能是原子D.可以是子表或原子

9.假咚以隼行表可三不碼表表示稀疏矩陣,則和下列行表

1。|2|3|3|5

對應的稀疏矩陣是()

-0-806-'0-806

70007000

A.0000B.-5040

-50400000

00000300

-0-806

0-806

00000000

C.0200D.7000

-5040-5040

00000300

10.在一棵度為3的樹中，度為3的結點個數(shù)為2,度為2的結點個數(shù)為1,則度為0的結點個

數(shù)為()

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

11.在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為()

A.eB.2eC.n2—eD.n2—2e

12.假設一個有n個頂點和e條弧的有向圖用鄰接表表示，則刪除與某個頂點片相關的所有

弧的時間復雜度是()

A.0(n)B.0(e)C.0(n+e)D.0(n*e)

13.用某種排序方法對關鍵字序列(25,84,21,47,15,27,68,35,20)進行排序時，

序列的變化情況如下：

20,15,21,25,47,27,68,35,84

15,20,21,25,35,27,47,68,84

15,20,21,25,27,35,47,68,84

則所采用的排序方法是（）

A.選擇排序B.希爾排序C.歸并排序D.快速排序

14.適于對動態(tài)查找表進行高效率查找的組織結構是（）

A.有序表B.分塊有序表C.三叉排序樹D.線性鏈表

15.不定長文件是指（）

A.文件的長度不固定B.記錄的長度不固定

C.字段的長度不固定D.關鍵字項的長度不固定

第二部分非選擇題（共70分）

二、填空題（本大題共10小題，每小題2分，若有兩個空格，每個空格1分，共20分）不

寫解答過程，將正確的答案寫在每小題的空格內。錯填或不填均無分。

16.數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，它與數(shù)據(jù)的無關，是獨立于計算

機的。

17.在一個帶頭結點的單循環(huán)鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head

可用p表示為head=。

18.棧頂?shù)奈恢檬请S著操作而變化的。

19.在串S="structure”中，以t為首字符的子串有個。

20.假設一個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在一維數(shù)組B中，其中B[0]存儲

矩陣中第1個元素小小則B[31]中存放的元素是o

21.已知一棵完全二叉樹中共有768結點，則該樹中共有個葉子結點。

22.已知一個圖的廣度優(yōu)先生成樹如右圖所示，則與此相

應的廣度優(yōu)先遍歷序列為。

23.在單鏈表上難以實現(xiàn)的排序方法有和。

24.在有序表（12,24,36,48,60,72,84）中二分查找關鍵字72時所需進行的關鍵字

比較次數(shù)為。

25.多重表文件和倒排文件都歸屬于文件。

三、解答題（本大題共4小題，每小題5分，共20分）

26.畫出下列廣義表的共享結構圖形表示

P=?（z）,（x,y））,（（x,y）,x）,（z））

27.請畫出與下列二叉樹對應的森