數據結構試卷

吉首大學試題庫

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

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

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

B,都是先進后出

C.都是先進先出

D.沒有共同點

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

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

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

3.以下數據結構中哪一個是非線性結構？（）

A.隊列B.棧C.線性表D.:又樹

4.設有一?個二維數組A[叫同，假設A[0][0]存放位置在644（[0）,A⑵⑵存放位置在676（助，每個元索

占一個空間，問A[3][3]（⑼存放在什么位置？腳注（⑼表示用10進制表示。

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

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

A.有序數據元素B.無序數據元素

C.元素之間具有分支層次關系的數據D.元素之間無聯系的數據

6.二叉樹的第k層的結點數最多為（）.

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

7.若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[l]中，現進行二分查找，則查

找A[3]的比較序列的下標依次為（）

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

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

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

A.0（1）B.O（n）C.O（Jog2n）D.O（n2）

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

列函數，則散列地址為1的元素有（）個，

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

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

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

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

1.通常從四個方面評價算法的質量：_正確性—、_強壯性、和O

2.個算法的時間復雜度為（r+"210g2"+14"）/"2,其數量級表示為.

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

的深度為，樹的度為。

4.后綴算式923102/?的值為o中綴算式(3+4X)-2Y/3對應的后綴算式為

5.若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指針。在這種存

儲結構中，n個結點的二叉樹共有個指針域，其中有個指針域是存放了地址，有

________________個指針是空指針。

6.對于?個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點分別有n_

個和個。

7.AOV網是一種的圖。

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

包含有條邊。

9.假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進行劃分，使得同一余數的元素成為一個子

表，則得到的四個子表分別為、、

和O

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

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

為_O

12.在快速排序、堆排序、歸并排序中，排序是穩定的。

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

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

A01234567

data605078903440

next3572041

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

3.已知一個圖的頂點集V和邊集E分別為：

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

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

圖10

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,2,5,8,3時，每加入一個數據后堆的變化。

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

1.LinkListmynote(LinkListL)

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

if(L&&L->next){

q=L；L=L->next；p=L：

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

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

returnL；

請回答下列問題：

1.(1)查詢鏈表的尾結點

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

(3)返回的線性表為(a2,a3,…,an,al)

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

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

(3)設鏈衣表示的線性表為(aha2,…,aj,寫出算法執行后的返回值所表示的線性表。

2.voidABC(BTNode*BT)

{

ifBT{

ABC(BT->1eft);

ABC(BT->right);

cout?BT->data?r

)

)

2.該算法的功能是：

五、算法填空(共8分)

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

boolFind(BTrccNodc*BST,ElcmType&item)

{

if(BST==NULL)

returnfalse;〃查找失敗

else{

if(item=BST->data){

item=BST->data;〃查找成功

return;}

elseif(itcm<BST->data)

returnFind(,item);

elsereturnFind(,itcm);

}//if

)

六、編寫算法(共8分)

統計出單鏈表HL中結點的值等于給定值X的結點數。

intCountX(LNodc*HL,ElcmTypex)

數據結構試題(一)(答案)

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

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

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

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

2.O(n)

3.933

4.-134X*+2Y*3/-

5.2nn-1n+1

6.e2e

7.有向無回路

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

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

10.增加1

11.O(log2n)O(nlog2n)

12.歸并

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

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

01110

10101

11011

10101

2.鄰接矩陣：101110

鄰接表如圖II所示：

圖11

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

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

4.見圖12

5.4.畫出向小根堆中加入數據4,2,5,8,3時,每加入?個數據后堆的變化。

6.

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

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

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

（3）返回的線性表為（a2,a3,—,an,al）

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

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

trueBST->leftBST->right

六、編寫算法(8分)

intCountX(LNode*HL,ElemTypex)

{inti=0;LNode*p=HL;//i為計數器

while(p!=NULL)

{if(P->data==x)i++;

p=p->next;

}//while,出循環時i中的值即為x結點個數

returni;

}//CountX

數據結構試卷（二）

吉首大學試題庫

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

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

的平均比較次數，假定查找每個元素的概率都相等）為（）。

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

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

（）。

As-*link=p->link;p->link=s;Bp->link=s;s->link=q;

Cp-*link=s-*link;s_*link=p;Dq-*link=s;s—link=p：

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

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

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

A24B71C48D53

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

1、數據的邏輯結構被分為、、和四種。

2、一種抽象數據類型包括和兩個部分。

3,在下面的數組a中鏈接存儲著個線性表，表頭指針為a[o].ncxt,則該線性表為

a012345678

data

605642387425

next

4376201

4、在以HL為表頭指針的帶表頭附加結點的單鏈衣和循環單鏈表中，判斷鏈表為空的條件分別為

和O

5,用具有n個元素的?維數組存儲?個循環隊列，則其隊首指針總是指向隊首元素的,

該循環隊列的最大長度為。

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

時，棧頂元素的值可用表示。

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

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

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

是:三是。

9、在一個索引文件的索引表中，每個索引項包含對應記錄的和兩項數據。

10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))),則樹中所含的結點數為

個，樹的深度為，樹的度為,結點H的雙親結點為，孩子結點為

11、在堆排序的過程中，對任分支結點進行篩運算的時間復雜度為，整個堆排序過程的時

間復雜度為。

12、在對m階的8_樹插入元素的過程中，每向一個結點插入一個索引項(葉子結點中的索引項為關

鍵字和空指針)后，若該結點的索引項數等于個，則必須把它分裂為個結點。

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

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

次劃分結果。

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

數為H(key)=key%13并用線性探杏法解決沖突，請畫出散列表，并計算等概率情況卜.查找成

功的平均查找長度。

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

寫出這棵：叉樹的后序遍歷結果。

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

V={0,1,2.3,4,5,6,7,8,9}：

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

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

當它用鄰接矩陣表示和鄰接衣表示時.，分別寫出從頂點V。出發按深度優先搜索遍歷得到的頂點序列和

按廣度優先搜索遍歷等到的頂點序列。

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

圖深度優先序列廣度優先序列

鄰接矩陣表示時

鄰接表表示時

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

1、假定從鍵盤上輸入一批整數，依次為：7863453()9134-1,請寫出輸出結果。

#include<iostream.h>

#include<stdlib.h>

consstintstackmaxsize=30;

typedefintelemtype;

structstack{

elemtypestack[stackinaxsize];

inttop;

)；

#include"stack.h"

Voidmain()

(

stacka;

initstack(a);

intx;

cin?x;

while(x!=-l){

push(a,x);

cin?x;

)

while(Istackempty(a))

cout?pop(a)vv"”;

cout?endl;

}

該算法的輸出結果為：

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

Template<calsstype>voidBinTree<Type>：：

unknown(BinTreeNode<Type>*t){

BinTreeNodc<Typc>*p=t,*tcmp;

if(p!=NULL){

temp=p-*leftchild;

p-*leftchild=p->rightchild;

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的單鏈表按逆序鏈接，即若原單鏈表中存儲元素的次序為

aP……an.Pa.則逆序鏈接后變為，a.an.P……a”

Voidcontrary(Lnode*&HL)

數據結構試題(二)(答案)

?、單選題(每小題2分，共8分)

題號1234

答案CDAB

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

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

2：數據描述、操作聲名；

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：0(Iog2n)>O(nlog2n);

12：m、m-1

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

1、

劃分次序劃分結果

第一次[382440]46[56809579]

第二次24[3840]46[56809579]

第三次24384046[56809579]

第四次2438404656[809579]

第五次243840465679[8095]

第六次2438404656798095

0123456789101112

78150357452031233612

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

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

4、

圖深度優先序列廣度優先序列

鄰接矩陣表示時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分)

根據編程情況，酌情給分。

(

Lnodc*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.必須是不連續的

B.連續與否均可

C.必須是連續的

D.和頭結點的存儲地址相連續

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

A.O(1)B.0(n)C.0(m)D.O(m+n)

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

A.減少存取時間,降低下溢發生的機率

B.節省存儲空間,降低上溢發生的機率

C.減少存取時間,降低上溢發生的機率

D.節省存儲空間,降低下溢發生的機率

5.設數組data[m]作為循環隊列SQ的存儲空間，fhmt為隊頭指針，rear為隊尾指針，則執行出隊操作后其

頭指針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],則執行模式匹配算法時，在最壞情況下的時間復雜度是（）

A.0（3）B.0（n）C.0（n2）D.0（n3）

8.一個非空廣義表的表頭（）

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

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

0-8060-806

9.假祗?。横荏О参?且表表示稀疏矩陣,牌下髀匏06

A.5B.-800400）

對由1■麻露做網是a)D.000000

0530040）

00000300

10.在一棵度為3的樹中，度為3的結點個數為2,度為2的結點個數為1,則度為0的結點個數為（）

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

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

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

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

是（）

A.O(n)B.0(e)C.O(n-i-e)D.O(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.適于對動態查找表進行高效率查找的組織結構是（)

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

15.不定長文件是指（）

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

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

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

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

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

16.數據的邏輯結構是從邏輯關系上描述數據，它與數據的.無關，是獨立于計算機的。

17.在-個帶頭結點的單循環鏈表中，p指向尾結點的直接前驅，則指向頭結點的指針head可用p表示為

head=

18.棧頂的位置是隨著.操作而變化的。

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

20.假設?個9階的上三角矩陣A按列優先順序壓縮存儲在?維數組B中，其中B[0]存儲矩陣中第1個元

素aij,則B[31]中存放的元素是.

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

22.己知一個圖的廣度優先生成樹如右圖所示，則與此相

應的廣度優先遍歷序列為.

?

0?

23.在單鏈表上難以實現的排序方法有和。

24.在有序表(12,24,36,48,60,72,84)中二分查找關鍵字72時所需進行的關鍵字比較次數

為o

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

三、解答題(本大題共4小題，每小題5分，共20分)

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

P=(((z),(x,y)),((x,y),x),(z))

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

28.已知一個無向圖的頂點集為{a,b,c,d,e}，其鄰接矩陣如下所示

(I)畫出該圖的圖形；

(2)根據鄰接矩陣從頂點a出發進行深度優先遍歷和廣度優先遍歷，寫出相應的遍歷序列。

29.已知一個散列表如卜圖所示：

352()334S59

0123456789101112

其散列函數為h(key尸key%13,處理沖突的方法為雙重散列法，探查序列為：

hj=(h(key)+i*h1(kcy))%mi=0,m—1

其中

h1(key)=key%11+1

回答下列問題：

(1)對表中關鍵字35,20,33和48進行杳找時，所需進行的比較次數各為多少？

(2)該散列表在等概率查找時查找成功的平均查找長度為多少？

、題■,前黨分，共分)

四、算法閱讀題(本大題共4d620

應串款后噴返回值為：

30.下列算法的功能是比較兩彳

1當S]>S2

comstr(S|,S2)=

請在空白處填入適當的內容。

intcomstr(LinkStringsi,LinkStrings2)

{//si和s2為兩個鏈串的頭指針

while(sl&&s2){

if(sl—>date<s2—>date)return—1；

ififsl—>date>s2—>date)retuml；

iR?)retuni1；

⑤；

)

?

②

③

④

⑤

31.閱讀下面的算法

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）設鏈表表示的線性表為（aha2,…,aQ，寫出算法執行后的返回值所表示的線性表。

32.假設兩個隊列共享一個循環向量空間（參見右下圖）,

其類型Queue2定義如卜.:

typedefstruct{

DateTypedata[MaxSize]；

intfront[2],rear[2]：

}Queue2；

對于i=0或1,front[i]和rear[i]分別為第i個隊列的頭指針和尾指針。請對以下算法填空，實現第i個

隊列的入隊操作。

intEnQueue(Queue2*Q,inti,DateTypex)

{//若第i個隊列不滿，則元素x入隊列，并返回1；否則返回0

if(i<O||i>l)return0：

i[Q—>rear[i]=Q—>front[?1retumO；

Q—>data[?]=x；

Q—>rcar[i]=[@]；

return1；

}

②

③

33.已知二叉樹的存儲結構為二叉鏈表，閱讀下面算法。

typedefstructnode{

DatcTypcdata；

Structnode*next；

(ListNodc；

typedefListNode*LinkList；

LinkListLcafhcad=NULL；

VoidInorder(BinTreeT)

{

LinkLists；

If(T))

Inorder(T—>lchild)；

If((!T->lchild)&&(!T->rchild)){

s=(ListNode*)malloc(sizeof(ListNode))；

s->data=T—>data；

s->next=Leafhead：

Lcafhcad=s；

}

Inorder(T—>rchild)；

)

)

對于如下所示的二叉樹

(1)畫出執行上述算法后所建立的結構;

(2)說明該算法的功能。

五、算法設計題(本題共10分)

34.閱讀下列函數arrangc()

intarrange(inta[],intl,inth,intx)

{//l和h分別為數據區的下界和上界

intij,t；

i=l;j=h；

while(i<j){

whilc(i<j&&a[j]>=x)j—；

while(i<j&&a[j]>=x)i++；

if(i<j)

{t=aU];aU]=a[i]；a[i]=t;}

}

if(a[i]<x)returni；

elsereturni_1；

)

(1)寫出該函數的功能；

(2)寫一個調用上述函數實現下列功能的算法：對一整型數組b[n]中的元素進行重新排列，將所有負數

均調整到數組的低下標端，將所有正數均調整到數組的高下標端，若有零值，則置于兩者之間，并

返回數組中零元素的個數。

數據結構試題(三)參考答案

單項選擇題(本大題共15小題，每小題2分，共30分)

1.D2.B3.C4.B5.D

6.A7.C8,D9,A10.C

11.D12.C13.D14.C15.B

二、填空題(本大題共10小題，每小題2分,.共20分）

16.存儲(或存儲結構)17.p—>next—>next

18.進棧和退棧19.12

20.為了21.384

22.abefedg

23.快速排序、堆排序、希爾排序

24.225.多關鍵字

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

26.於m1

圖1圖2

*99zxyxy

27.A

深度優先遍歷序列為：abdce

廣度優先遍歷序列為：abcdc

29.(1)對關鍵字35、20、33和48進行查找的比較次數為3、2、1、1；

…3+2+1+1+29

(2)平均查找長度55

四、算法閱讀題(本大題共4小題，每小題5分，共20分)

30.①S1=S1—>next

②s2=s2—>next

③s2(或s2!=NULL或s2&&!sl)

④si(或si!=NULL或sl&&!s2)

?return0

31.(1)查詢鏈表的尾結點

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

(3)返回的線性表為(a2,a3,-,an,a1)

32.①(i+l)%2(或1-i)

②Q—>rear[i]

③(Q—>rear[i]+)%Maxsize

33.(1)Leafhead-----?F——?H--?G-->DA

(2)中序遍歷二叉樹，按遍歷序列中葉子結點數據域的值構建一個以Leafhead為頭指針的逆序單鏈

表(或按：叉樹中葉子結點數據自右至左鏈接成一個鏈表)。

五、算法設計題(本題共10分)

34.(1)該函數的功能是：調整整數數組a口中的元素并返回分界值i,使所有<x的元素均落在a[L.i]

上，使所有的元素均落在a[i+l..h]上。

(2)intf(intb[],intn)或intf(intb[],intn)

intp,q；intp,q；

p=arrangc(b,O,n—1,0)；p=arrangc(b,0,n—1,1)；

q=arrange(b,p+1,n-1,1)；q=arrange(b,0,p,0)；

returnq-p；returnp-q；

數據結構試卷(四)

吉首大學試題庫

一、選擇題(20分)

1.組成數據的基本單位是(

(A)數據項(B)數據類型(C)數據元素(D)數據變量

2.設數據結構A=(D,R),其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,<3,4>,<4,1>},則數

據結構A是()。

(A)線性結構(B)樹型結構(C)圖型結構(D)集合

3.數組的邏輯結構不同于下列()的邏輯結構。

(A)線性表(B)棧(C)隊列(D)樹

4.二叉樹中第i(iR)層上的結點數最多有()個。

(A)2i(B)2j(C)2iu(D)2i-l

5.設指針變量p指向單鏈表結點A,則刪除結點A的后繼結點B需要的操作為().

(A)p->next=p->next->next(B)p=p->next

(C)p=p->next->next(D)p->next=p

6.設棧S和隊列Q的初始狀態為空，元素El、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即

進入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應該是()?

(A)6(B)4(C)3(D)2

7.將10階對稱矩陣壓縮存儲到?維數組A中，則數組A的長度最少為().

(A)100(B)40(C)55(D)80

8.設結點A有3個兄弟結點且結點B為結點A的雙