數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)

第二部分模擬試卷

模擬試卷

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

1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）

A.有向圖B.隊(duì)列C.線索二叉樹D.B樹

2.在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn),

則執(zhí)行如下（）語句序列。

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

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

3.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？()

A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素

C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值

4.字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串,至多可以組成

（）個(gè)不同的字符串？

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

5.由權(quán)值分別為3,8,6,2的葉子生成一棵哈夫曼樹,它的帶權(quán)路徑長度為（)°

A.11B.35C.19D.53

以下6-8題基于圖lo

6.該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（)°

A.E、G、F、A、C、D、B

B.E、A、G、C、F、B、D

C.E、ANC、B、D、G、F

D.E、G、A、C、D、F、B

7.該二叉樹結(jié)點(diǎn)的中序遍歷的序列為（)°

A.A、B>C、D^E、G、F

B.E、A、G、C、F、B、D

C.E、A、C、B、D、G^F

E.B、D、C、A、F、G、E

8.該二叉樹的按層遍歷的序列為（）o

A.E、G、F、ANC、D、BB.E、A、C、B、D、G、F

C.E、A、G、C、F、DD.E、G、A、C、D、F、B

9.下面關(guān)于圖的存儲(chǔ)的敘述中正確的是（)°

A.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)

B.用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān)

C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有關(guān)

D.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無關(guān)

10.設(shè)有關(guān)鍵碼序列（q，g,m,z,a,n,p,x,h）,下面哪一個(gè)序列是從上述序列出發(fā)建堆

的結(jié)果?（)

A.a,g,h,m,n,p,q,x,zB.a,g,m,h,q,n,p,x,z

C.g，m,q,a,n,p,x,h,zD.h,g,m,p,a,n,q,x,z

1

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

1.數(shù)據(jù)的物理結(jié)構(gòu)被分為順序，鏈表，索引，散列，四種。

1.對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為,

在表尾插入元素的時(shí)間復(fù)雜度為。

2.向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是;

刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是(假設(shè)棧不空而

且無需回收被刪除結(jié)點(diǎn))。

3.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，一個(gè)結(jié)點(diǎn)的編號(hào)為i(lWiWn),若它有左孩子則左孩

子結(jié)點(diǎn)的編號(hào)為，若它有右孩子，則右孩子結(jié)點(diǎn)的編號(hào)為,若它有雙

親，則雙親結(jié)點(diǎn)的編號(hào)為。

4.當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層調(diào)整，直到被調(diào)整

到位置為止。

5.以二分查找方法從長度為10的有序表中查找一個(gè)元素時(shí)，平均查找長度為。

6.表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為、和?

7.對(duì)于線性表(70,34,55,23,65,41,20)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%7

作為散列函數(shù)，則散列地址為0的元素有個(gè)，散列地址為6的有個(gè)。

8.在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為,整個(gè)排序過程的時(shí)間復(fù)雜度為

,空間復(fù)雜度為。

9.在一棵m階B一樹上，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為個(gè),最多為

個(gè)，其子樹數(shù)目最少為，最多為。

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

1.寫出下列中綴表達(dá)式的后綴形式：①,

(1)3X/(Y-2)+l

(2)2+X*(Y+3)

2.試對(duì)圖2中的二叉樹畫出其：、⑥

(1)順序存儲(chǔ)表示的示意圖：

(2)二叉鏈表存儲(chǔ)表示的示意圖。?X?遨

3.判斷以下序列是否是小根堆？如果不是，將它調(diào)曠

整為小根堆。圖2

(1){12,70,33,65,24,56,48,92,86,33}

(2){05,23,20,28,40,38,29,61,35,76,47,100}

4.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：

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

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

按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各

條邊。

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

1.voidAE(Stack&S){

InitStack(S);

Push(S,3);

Push(S,4);

intx=Pop(S)+2*Pop(S);

Push(S,x);

2

inti,a[5]={l,5,8,12,15);

for(i=0;i<5;i++)Push(S,2*a[i]);

while(!StackEmpty(S))cout<<Pop(S)?，';

)

該算法被調(diào)用后得到的輸出結(jié)果為：

2.voidABC(BTNode*BT,int&cl,int&c2)

{if(BT!=NULL){

ABC(BT->left,cl,c2);

cl++;

if(BT->left==NULL&&BT->right==NULL)c2++;

ABC(BT->right,cl,c2);

}//if

)

該函數(shù)執(zhí)行的功能是什么？

五、算法填空(共8分)

向單鏈表的末尾添加一個(gè)元素的算法。

VoidInsertRear(LNode*&HL,constElemType&item)

(

LNode*newptr;

newptr=newLNode;

If()

(

cerr?/zMemoryallocationfailare!z*<<endl;

exit(1);

)

_________________________二item;

newptr->next=NULL;

if(HL==NULL)

HL二;

else(

LNode*P=HL;

While(P->next!=NULL)

p->next=newptr;

）

）

六、編寫算法（共8分）

編寫從類型為List的線性表L中將第i個(gè)元素刪除的算法，（假定不需要對(duì)i的值進(jìn)行

有效性檢查，也不用判別L是否為空表。）

voidDelete（List&L,inti）

模擬試卷一參考答案

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

l.B2.D3.A4.B5.B6.C7.A8.C9.B10.B

3

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

2,順序鏈表索引散列

3.0(n)0(1)

4p->next=HS;HS=pHS=HS->next

52i2i+l|_i/2」(或i/2)

6向上根

72.9

8鄰接矩陣鄰接表邊集數(shù)組

914

10.0(n)0(nlog2n)0(n)

八1八|8|A|

Il.「m/21Tm-1「m/21m

三、運(yùn)算題(每題6分，共24分)FPHAI

1.(1)3X*Y2-/I+圖3

(2)2XY3+*+

2.(1)

012345678910111213141516

(2)見圖3所示：

3.(1)不是小根堆。調(diào)整為：{12,65,33,70,24,56,48,92,86,33}

(2)是小根堆。

4.普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹為：

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

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

1.30241610210

2.該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹的結(jié)點(diǎn)總數(shù)和葉子總數(shù)

五、算法填空(共8分，每一空2分)

newptr==NULLnewptr->=datanewptrp=p->next

六、編寫算法(8分)

voidDelete(List&L,inti)

(

for(intj=i-l;j<L.size-1;j++)

L.list[j]=Llist[j+l];//第i個(gè)元素的下標(biāo)為iT

L.size―;

)

模擬試卷二

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

1.在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)

點(diǎn)，則執(zhí)行().

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

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

2.若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,則該隊(duì)列最多可存儲(chǔ)()個(gè)元素.

A.nB.n-l

C.n+1D.不確定

4

3.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？()

A.存儲(chǔ)密度大B.插入和刪除運(yùn)算方便

C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快

4.設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在6004網(wǎng)[3]存放位置在

678，每個(gè)元素占一個(gè)空間，問A[2][3]存放在什么位置％,(腳注表示用10進(jìn)

(10)(10)(10)

制表示,m>3)

A.658B.648C.633D.653

5.下列關(guān)于二叉樹遍歷的敘述中，正確的是()。

A.若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷

最后一個(gè)結(jié)點(diǎn)

B.若一個(gè)點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最

后一個(gè)結(jié)點(diǎn)

C.若一個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最

后一個(gè)結(jié)點(diǎn)

D.若一個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后

一個(gè)結(jié)點(diǎn)

6.k層二叉樹的結(jié)點(diǎn)總數(shù)最多為().

A.2k-1B.2K+1C.2K-1D.

7.對(duì)線性表進(jìn)行二分法查找，其前提條件是().

A.線性表以鏈接方式存儲(chǔ),并且按關(guān)鍵碼值排好序

B.線性表以順序方式存儲(chǔ),并且按關(guān)鍵碼值的檢索頻率排好序

C.線性表以順序方式存儲(chǔ),并且按關(guān)鍵碼值排好序

D.線性表以璉接方式存儲(chǔ),并且按關(guān)鍵碼值的檢索頻率排好序

8.對(duì)n個(gè)記錄進(jìn)行堆排序,所需要的輔助存儲(chǔ)空間為

A.0(logn)B.0(n)C.0(1)D.0(n2)

9.對(duì)于線性表(7,34,77,25,64,49,20,14)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)

=K用作為散列函數(shù)，則散列地址為0的元素有()個(gè)，

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

10.下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是().

A.數(shù)組是不同類型值的集合

B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉

C.樹是一種線性結(jié)構(gòu)

D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法

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

1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、、和四種。

2.一個(gè)算法的時(shí)間復(fù)雜度為(3〃3+2000“l(fā)og2”+90)/”2,其數(shù)量級(jí)表示為o

3.對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為，在

表尾插入元素的時(shí)間復(fù)雜度為。

4.假定一棵樹的廣義表表示為A(D(E,G),H(LJ)，則樹中所含的結(jié)點(diǎn)數(shù)為

個(gè)，樹的深度為,樹的度為。

5.后綴算式79230+-42/*的值為。中綴算式(3+X*Y)-2Y/3對(duì)

應(yīng)的后綴算式為，

6.在一棵高度為5的理想平衡樹中，最少含有個(gè)結(jié)點(diǎn)，最多含有個(gè)結(jié)點(diǎn)。

7.在樹中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的。一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱

5

為該結(jié)點(diǎn)的o

8.在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的

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

9.假定一個(gè)線性表為(12,17,74,5,63,49,82,36),若按Key%4條件進(jìn)行劃分，使得同一余數(shù)

的元素成為一個(gè)子表，則得到的四個(gè)子表分別為、

、和。

10.對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度

比原樹的高度。

11.在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為,整個(gè)堆排序

過程的時(shí)間復(fù)雜度為。

12.在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表

示待散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于。

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

1.在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針存放在A[O].next,試寫出該線性表。

A01234567

data605078903440

next4052713

2.已知一棵二叉樹的前序遍歷的結(jié)果是ABKCDFGHIJ,中序遍歷的結(jié)果是KBCDAFHIGJ,試

畫出這棵二叉樹。

3.己知一個(gè)圖的頂點(diǎn)集V為：V={1,2,3,4,5,6,7};

其共有10條邊。該圖用如下邊集數(shù)組存儲(chǔ)：

起

占

八1225522613

統(tǒng)

占

26454767775

權(quán)

1122233457

試用克魯斯卡爾算法依次求出該圖的最小生成樹中所得到的各條邊及權(quán)值。

4.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3,6,10,1時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。

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

1.在下面的每個(gè)程序段中，假定線性表La的類型為List,元素類型ElemType為int,

并假定每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表La。

(1)InitList(La);

Inta[]={100,26,57,34,79};

For(i=0;i<5;i++)

Insert(La,a[i]);

TraverseList(La);

(2)DeleteFront(La);

InsertRear(La,DeleteFront(La))：

TraverseList(La);

(3)ClearList(La);

For(i=0;i<5;i++)

InsertFront(La,a[i]);

TraverseList(La);

2.現(xiàn)面算法的功能是什么？

voidABC(BTNode*BT)

ifBT{

6

cout?BT->data?'r;

ABC(BT->left);

ABC(BT->right);

五、算法填空(共8分)

二分查找的遞歸算法。

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

(

if_

intmid=(low+high)/2;

if()returnmid;〃查找成功，返回元素的下標(biāo)

elseif(K<A[mid].key)

returnBinsch(A,low,mid-1,K);〃在左子表上繼續(xù)查找

elsereturn//在右子表上繼續(xù)查找

)

else；〃查找失敗，返回T

}

六、編寫算法(共8分)

HL為單鏈表的表頭指針，試寫出在該單鏈表中查找具有給定的元素item的算法。

boolFind(LNode*HL,ElemType&item)

模擬試卷二參考答案

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

l.B2.B3.A4.C5.D6.A7.C8.C9.D10,D

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

1.集合結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)

2.0(n)

3.0(1)0(1)

4.722

5.943XY*+2Y*3/-

6.1631

7.孩子(或子)結(jié)點(diǎn)雙親(或父)結(jié)點(diǎn)

8.45n(n-l)

9.(12,36)(17,5,49)(74,82)(63)

10.減少1(或減少)

11.0(logn)0(nlogn)

22

12.n/m

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

1.線牌為：(90,40,78,50,34,60)

2.當(dāng)前序序列為ABKCDFGHIJ,中序序列為KBCDAFHIGJ時(shí)，逐步形成二叉樹的過程

(1,6)1,(2,4)1,(2,5)2,(5,7)2,(2,6)3,(3,5)7

4.見圖5。

圖5

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

1.(l)La=(26,34,57,79,100)

(2)La=(57,79,100,34)

(3)La=(79,34,57,26,100)

2.前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。

五、算法填空(每空2分，共8分)

(low<=high)K==A[mid].keyBinsch(A,mid+1,hight,K)return-1

六、編寫算法(8分)

boolFindfLNode*HL,ElemType&item)

LNode*p=HL;

whilep

if(P-

>data==item){return

true;

elsep=p->next;

returnfalse;

模擬試卷三

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

1.對(duì)一個(gè)算法的評(píng)價(jià)，不包括如下（）方面的內(nèi)容。

A.健壯性和可讀性B.并行性C.正確性D.時(shí)空復(fù)雜度

2.在帶有頭結(jié)點(diǎn)的單鏈表HL中，要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行（）。

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

8

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

3.對(duì)線性表，在下列哪種情況下應(yīng)當(dāng)采用鏈表表示？（）

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

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

4.一個(gè)棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是（）

A.231B.321

C.312D.123

5.AOV網(wǎng)是一種（）?

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

6.采用開放定址法處理散列表的沖突時(shí)，其平均查找長度（）o

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

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

7.若需要利用形參直接訪問實(shí)參時(shí)，應(yīng)將形參變量說明為（）參數(shù)。

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

8.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的（）.

A.行號(hào)B.列號(hào)C.元素值D.非零元素個(gè)數(shù)

9.快速排序在最壞情況下的時(shí)間復(fù)雜度為（

A.O（logn）B.O（nlogn）C.0（n）D.0（n2）

22

10.從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）o

A.O（n）B.0（1）C.0（logn）D.0（nz）

二、運(yùn)算題（每題6分，共24分）

1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的o當(dāng)結(jié)點(diǎn)之間存在M對(duì)N（M：N）

的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為。

2.隊(duì)列的插入操作是在隊(duì)列的進(jìn)行，刪除操作是在隊(duì)列的進(jìn)行。

3.當(dāng)用長度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top==N表示?？?，則表示棧滿的條件

是。

4.對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_______,

在表尾插入元素的時(shí)間復(fù)雜度為。

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

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

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

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

6.廣義表人=似,似,功,（包,功,可）,則它的深度為,它的長度為o

7.二叉樹是指度為2的樹。一棵結(jié)點(diǎn)數(shù)為N的二叉樹，其所有結(jié)

點(diǎn)的度的總和是?

8.對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè)。對(duì)一棵由

算術(shù)表達(dá)式組成的二叉語法樹進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的

9.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，用二叉鏈表存儲(chǔ)時(shí)，其指針總數(shù)為個(gè)，

其中個(gè)用于指向孩子，個(gè)指針是空閑的。

10.若對(duì)一棵完全二叉樹從0開始進(jìn)行結(jié)點(diǎn)的編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A

中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到A[0]中。其余類推，則A[i]元素的左孩子元素為

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

11.在線性表的散列存儲(chǔ)中，處理沖突的常用方法有和

9

________________________________兩種。

12.當(dāng)待排序的記錄數(shù)較大，排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí),宜采用

排序；當(dāng)待排序的記錄數(shù)較大，存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí)，宜采用

__________________________排序。

三、運(yùn)算題(每題6分，共24分)00001

1.己知一個(gè)6x5稀疏矩陣如右所示，試：00000

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

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

2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從50000

空樹起，逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二叉搜索樹。

Uu/u

3.對(duì)于圖6所示的有向圖若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)鄰

接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從小到大的次序鏈接的，試寫出:

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

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

4.已知一個(gè)圖的頂點(diǎn)集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>};

若存儲(chǔ)它采用鄰接表，并且每個(gè)頂點(diǎn)

鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(hào)從

小到大的次序鏈接的，按主教材中介紹的

拓樸排序算法進(jìn)行排序，試給出得到的拓

樸排序的序列。

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

1.intPrime(intn)

{

inti=1;

intx=(int)sqrt(n);

while(++i<=x)

if(n%i==O)break;

if(i>x)return1;

elsereturn0;

)

⑴指出該算法的功能；

⑵該算法的時(shí)間復(fù)雜度是多少？

2.寫出下述算法的功能：

voidAJ(adjlistGL,inti,intn)

QueueQ;

InitQueue(Q);

cout?i<<，’;

visited[i]=true;

QInsert(Q,i);

10

while(!QueueEmpty(Q))

{intk=QDelete(Q);

edgenode*p=GL[k];

while(p!=NULL)

(

intj=p->adjvex;

if(!visited[j])

(

cout?j?,;

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;〃查找成功，返回元素的下標(biāo)

elseif(K<[mid].key)

________________________________________；〃在左子表上繼續(xù)查找

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

}

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

}

六、編寫算法(共8分)

HL是單鏈表的頭指針，試寫出刪除頭結(jié)點(diǎn)的算法。

ElemTypeDeleFront(LNode*&HL)

模擬試卷三參考答案

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

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

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

1.聯(lián)系圖(或圖結(jié)構(gòu))

2.尾首

3.top==0

4.O(1)O(n)

11

5.12844108

6.33

7.有序n-1

655

8.有序序列后綴表達(dá)式(或逆波蘭式)

151

9.2nn-1n+132-1

10.2i+l2i+2(i-l)/245-2

11.開放定址法鏈接法515

637

12.快速歸并

H7

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

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

(2)三元組線性表的順序存儲(chǔ)表示如圖7示。

2.如圖8所示。

3.DFS：①②③④⑤

BFS：②③④⑤①

4.拓樸排序?yàn)椋?365721

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

1.(1)判斷n是否是素?cái)?shù)(或質(zhì)數(shù))

(2)O(6)

2.功能為：從初始點(diǎn)看出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖。

五、算法填空(8分)

(low+high)/2high=mid-1low=mid+1

六、編寫算法(8分)

ElemTypeDeleFront(LNode*&HL)

{

if(HL==NULL){

cerr<<“空表"<<endl;

exit(l);

}

LNode*p=HL;

HL=HL->next;

ElemTypetemp=p->data;

deletep;

returntemp;

}

12

模擬試卷四

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

1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）

A.有向圖B.棧C.二叉樹D.B樹

2.若某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，則采

用（）存儲(chǔ)方式最節(jié)省時(shí)間。

A.單鏈表B.雙鏈表

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

3.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（）

A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素

C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值

4.字符A、B、C、D依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以

組成（）個(gè)不同的字符串？

A.15B.14C.16D.21

5.由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（）。

A.11B.37C.19D.53

以下6-8題基于下面的敘述：若某二叉樹結(jié)點(diǎn)的中序遍歷的序列為A、B、C、D、E、

F、G,后序遍歷的序列為B、D、C、A、F、G、E。

6.則該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）.

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、D

C.E、A、C、B、D、G、FD.E、G、A、C、D、F、B

7.該二叉樹有（）個(gè)葉子。

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

8.該二叉樹的按層遍歷的序列為（）

A.E、G、F、A、C、D、BB.E、A、C、B、D、G、F

C.E、A、G、C、F、B、DD.E、G、A、C、D、F、B

9.下面的二叉樹中，（）不是完全二叉樹。

A.B.C.D.

10.設(shè)有關(guān)鍵碼序列（q,g，m,z,a）,下面哪一個(gè)序列是從上述序列出發(fā)建的小根堆的結(jié)

果?()

A.a,g,m,q，zB.a,g,m,z,q

C.g,m,q.a,D.g，m,a,q,z

二、填空題（每空1分,共26分)

1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的.o當(dāng)結(jié)點(diǎn)之間存在1對(duì)N（1：N）

的聯(lián)系時(shí)，稱這種結(jié)構(gòu)為

2.一個(gè)廣義表中的元素分為,元素和.元素兩類。

3.對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為.

在表尾插入元素的時(shí)間復(fù)雜度為o

13

4.向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是;

刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是(假設(shè)棧不空而且

無需回收被刪除結(jié)點(diǎn))。

5.棧又稱為表，隊(duì)列又稱為表。

6.在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按為主序、

為輔序的次序排列。

7.若一棵二叉樹中只有葉子結(jié)點(diǎn)和左、右子樹皆非空的結(jié)點(diǎn)，設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為K則左、

右子樹皆非空的結(jié)點(diǎn)個(gè)數(shù)是。

8.以折半(或二分)查找方法從長度為8的有序表中查找一個(gè)元素時(shí)，平均查找長度為

9.表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為、和。

10.對(duì)于線性表(78,4,56,30,65)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)=K%5作為散列

函數(shù)，則散列地址為0的元素有個(gè)，散列地址為4的有個(gè)。

11.在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為，整個(gè)排序過程的時(shí)間復(fù)雜度為

,空間復(fù)雜度為。

12.在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹中，帶權(quán)路徑長度最小的二叉樹稱為

?WPL稱為o

13.在索引表中，若一個(gè)索引項(xiàng)對(duì)應(yīng)主表的一個(gè)記錄，則此索引為索引，若對(duì)

應(yīng)主表的若干條記錄，則稱此索引為索引。

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

1.寫出下列中綴表達(dá)式的后綴形式：

(1)3X/(Y-2H)+1

(2)2+X*(Y+3)

2.假定一棵二叉樹廣義表表示為a(b(c),d(e,f)),分別寫出對(duì)它進(jìn)行先序、中序、后序、按

層遍歷的結(jié)果。

先序：

中序：

后序：

按層：

3.已知一個(gè)無向圖的頂點(diǎn)集為{a,b,c,d,e},其鄰接矩陣如下所示

a[01001

b10010

c00011

d01101

eL10110J

(1)畫出該圖的圖形；

(2)根據(jù)鄰接矩陣從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序

列。

4.己知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：

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

E={(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,

14

(4,6)4,(5,7)20);

按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

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

1.voidAE(Stack&S){

InitStack(S);

Push(S,3);

Push(S,4);

intx=Pop(S)+2*Pop(S);

Push(S,x);

inti,a[5]={2,5,8,22,