




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
數(shù)據(jù)結(jié)構(gòu)試卷
吉首大學試題庫
一、單選題(每題2分,共20分)
1.棧和隊列的共同特點是(A)。
A.只允許在端點處插入和刪除元素
B,都是先進后出
C.都是先進先出
D.沒有共同點
2.用鏈接方式存儲的隊列,在進行插入運算時().
A.僅修改頭指針B.頭、尾指針都要修改
C.僅修改尾指針D.頭、尾指針可能都要修改
3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)?()
A.隊列B.棧C.線性表D.:又樹
4.設(shè)有一?個二維數(shù)組A[叫同,假設(shè)A[0][0]存放位置在644([0),A⑵⑵存放位置在676(助,每個元索
占一個空間,問A[3][3](⑼存放在什么位置?腳注(⑼表示用10進制表示。
A.688B.678C.692D.696
5.樹最適合用來表示()。
A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)
6.二叉樹的第k層的結(jié)點數(shù)最多為().
A.21MB.2K+1C.2K-1D.2k"
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.對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作為散
列函數(shù),則散列地址為1的元素有()個,
A.1B.2C.3D.4
10.設(shè)有6個結(jié)點的無向圖,該圖至少應(yīng)有()條邊才能確保是?個連通圖。
A.5B.6C.7D.8
二、填空題(每空1分,共26分)
1.通常從四個方面評價算法的質(zhì)量:_正確性—、_強壯性、和O
2.個算法的時間復雜度為(r+"210g2"+14")/"2,其數(shù)量級表示為.
3.假定一棵樹的廣義表表示為A(C,D(E,F,G),H(I,J)),則樹中所含的結(jié)點數(shù)為個,樹
的深度為,樹的度為。
4.后綴算式923102/?的值為o中綴算式(3+4X)-2Y/3對應(yīng)的后綴算式為
5.若用鏈表存儲一棵二叉樹時,每個結(jié)點除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個指針。在這種存
儲結(jié)構(gòu)中,n個結(jié)點的二叉樹共有個指針域,其中有個指針域是存放了地址,有
________________個指針是空指針。
6.對于?個具有n個頂點和e條邊的有向圖和無向圖,在其對應(yīng)的鄰接表中,所含邊結(jié)點分別有n_
個和個。
7.AOV網(wǎng)是一種的圖。
8.在一個具有n個頂點的無向完全圖中,包含有條邊,在一個具有n個頂點的有向完全圖中,
包含有條邊。
9.假定一個線性表為(12,23,74,55,63,40),若按Key%4條件進行劃分,使得同一余數(shù)的元素成為一個子
表,則得到的四個子表分別為、、
和O
10.向棵B_樹插入元素的過程中,若最終引起樹根結(jié)點的分裂,則新樹比原樹的高度―o
11.在堆排序的過程中,對任一分支結(jié)點進行篩運算的時間復雜度為整個堆排序過程的時間復雜度
為_O
12.在快速排序、堆排序、歸并排序中,排序是穩(wěn)定的。
三、運算題(每題6分,共24分)
1.在如下數(shù)組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.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時,每加入一個數(shù)據(jù)后堆的變化。
四、閱讀算法(每題7分,共14分)
1.LinkListmynote(LinkListL)
{//L是不帶頭結(jié)點的單鏈表的頭指針
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)查詢鏈表的尾結(jié)點
(2)將第一個結(jié)點鏈接到鏈表的尾部,作為新的尾結(jié)點
(3)返回的線性表為(a2,a3,…,an,al)
(1)說明語句S1的功能;
(2)說明語句組S2的功能;
(3)設(shè)鏈衣表示的線性表為(aha2,…,aj,寫出算法執(zhí)行后的返回值所表示的線性表。
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分)
統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。
intCountX(LNodc*HL,ElcmTypex)
數(shù)據(jù)結(jié)構(gòu)試題(一)(答案)
一、單選題(每題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.畫出向小根堆中加入數(shù)據(jù)4,2,5,8,3時,每加入?個數(shù)據(jù)后堆的變化。
6.
四、閱讀算法(每題7分,共14分)
3.(1)查詢鏈表的尾結(jié)點
(2)將第個結(jié)點鏈接到鏈表的尾部,作為新的尾結(jié)點
(3)返回的線性表為(a2,a3,—,an,al)
4.遞歸地后序遍歷鏈式存儲的二叉樹。
五、算法填空(每空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結(jié)點個數(shù)
returni;
}//CountX
數(shù)據(jù)結(jié)構(gòu)試卷(二)
吉首大學試題庫
一、單選題(每小題2分,共8分)
1、在一個長度為n的順序線性表中順序查找值為x的元素時,查找成功時的平均查找長度(即x與元素
的平均比較次數(shù),假定查找每個元素的概率都相等)為()。
AnBn/2C(n+l)/2D(n-l)/2
2、在一個單鏈表中,若q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點,若在q與p之間插入一個s所指的結(jié)點,則執(zhí)行
()。
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、由權(quán)值分別為11,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹,它的帶權(quán)路徑長度為()
A24B71C48D53
二、填空題(每空1分,共32分)
1、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為、、和四種。
2、一種抽象數(shù)據(jù)類型包括和兩個部分。
3,在下面的數(shù)組a中鏈接存儲著個線性表,表頭指針為a[o].ncxt,則該線性表為
a012345678
data
605642387425
next
4376201
4、在以HL為表頭指針的帶表頭附加結(jié)點的單鏈衣和循環(huán)單鏈表中,判斷鏈表為空的條件分別為
和O
5,用具有n個元素的?維數(shù)組存儲?個循環(huán)隊列,則其隊首指針總是指向隊首元素的,
該循環(huán)隊列的最大長度為。
6、當堆棧采用順序存儲結(jié)構(gòu)時,棧頂元素的值可用-------------表示:當堆棧采用鏈接存儲結(jié)構(gòu)
時,棧頂元素的值可用表示。
7、■■棵高度為5的二叉樹中最少含有個結(jié)點,最多含有個結(jié)點;
一棵高度為5的理想平衡樹中,最少含有個結(jié)點,最多含有個結(jié)點。
8、在圖的鄰接表中,每個結(jié)點被稱為,通常它包含三個域:一是:二
是:三是。
9、在一個索引文件的索引表中,每個索引項包含對應(yīng)記錄的和兩項數(shù)據(jù)。
10、假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J))),則樹中所含的結(jié)點數(shù)為
個,樹的深度為,樹的度為,結(jié)點H的雙親結(jié)點為,孩子結(jié)點為
11、在堆排序的過程中,對任分支結(jié)點進行篩運算的時間復雜度為,整個堆排序過程的時
間復雜度為。
12、在對m階的8_樹插入元素的過程中,每向一個結(jié)點插入一個索引項(葉子結(jié)點中的索引項為關(guān)
鍵字和空指針)后,若該結(jié)點的索引項數(shù)等于個,則必須把它分裂為個結(jié)點。
三、運算題(每小題6分,共24分)
1、已知一組記錄的排序碼為(46,79,56,38,40,80,95,24),寫出對其進行快速排序的每一
次劃分結(jié)果。
2、一個線性表為B=(12,23,45,57,20,03,78,31,15,36),設(shè)散列表為HT[0..12],散列函
數(shù)為H(key)=key%13并用線性探杏法解決沖突,請畫出散列表,并計算等概率情況卜.查找成
功的平均查找長度。
3、已知一棵二叉樹的前序遍歷的結(jié)果序列是ABECKFGHIJ,中序遍歷的結(jié)果是EBCDAFHIGJ,試
寫出這棵:叉樹的后序遍歷結(jié)果。
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。出發(fā)按深度優(yōu)先搜索遍歷得到的頂點序列和
按廣度優(yōu)先搜索遍歷等到的頂點序列。
假定每個頂點鄰接表中的結(jié)點是按頂點序號從大到小的次序鏈接的。
圖深度優(yōu)先序列廣度優(yōu)先序列
鄰接矩陣表示時
鄰接表表示時
四、閱讀算法,回答問題(每小題8分,共16分)
1、假定從鍵盤上輸入一批整數(shù),依次為:7863453()9134-1,請寫出輸出結(jié)果。
#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;
}
該算法的輸出結(jié)果為:
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);
}
)
該算法的功能是:________________________________
五、算法填空,在畫有橫線的地方填寫合適的內(nèi)容(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分)
編寫算法,將一個結(jié)點類型為Lnode的單鏈表按逆序鏈接,即若原單鏈表中存儲元素的次序為
aP……an.Pa.則逆序鏈接后變?yōu)椋琣.an.P……a”
Voidcontrary(Lnode*&HL)
數(shù)據(jù)結(jié)構(gòu)試題(二)(答案)
?、單選題(每小題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:邊結(jié)點、鄰接點域、權(quán)域、鏈域;
9:索引值域、開始位置域;
10:10、3、3、B、I和J;
11:0(Iog2n)>O(nlog2n);
12:m、m-1
三、運算題(每小題6分,共24分)
1、
劃分次序劃分結(jié)果
第一次[382440]46[56809579]
第二次24[3840]46[56809579]
第三次24384046[56809579]
第四次2438404656[809579]
第五次243840465679[8095]
第六次2438404656798095
0123456789101112
78150357452031233612
查找成功的平均查找長度:ASLSUCC=M/10=1.4
3、此二叉樹的后序遍歷結(jié)果是: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、該算法的輸入結(jié)果是:349130456378
2、2、該算法的功能是:交換二叉樹的左右子樹的遞歸算法。
五、算法填空,在畫有橫線的地方填寫合適的內(nèi)容(10分)
1、1是:(low+high)/2;
2是:Binsch(A,low,mid-1,K);
3是:Binsch(A,mid+1,high,K);
4是:-1;
六、編寫算法(10分)
根據(jù)編程情況,酌情給分。
(
Lnodc*P=HL;
HL=NULL;
While(p!=null)
(
Lnode*q=p;
P=pfnext;
q-*next=HL;
HL=q;
)
數(shù)據(jù)結(jié)構(gòu)試卷(三)
吉首大學試題庫
第一部分選擇題(30分)
一、單項選擇題(本大題共15小題,每小題2分,共30分)在每小題列出的四個選項中只有一個選項
是符合題目要求的,請將正確選項前的字母填在題后的括號內(nèi)。
1.算法指的是()
A.計算機程序B.解決問題的計算方法
C.排序算法D.解決問題的有限運算序列
2.線性表采用鏈式存儲時,結(jié)點的存儲地址()
A.必須是不連續(xù)的
B.連續(xù)與否均可
C.必須是連續(xù)的
D.和頭結(jié)點的存儲地址相連續(xù)
3.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為()
A.O(1)B.0(n)C.0(m)D.O(m+n)
4.由兩個棧共享?個向量空間的好處是:()
A.減少存取時間,降低下溢發(fā)生的機率
B.節(jié)省存儲空間,降低上溢發(fā)生的機率
C.減少存取時間,降低上溢發(fā)生的機率
D.節(jié)省存儲空間,降低下溢發(fā)生的機率
5.設(shè)數(shù)組data[m]作為循環(huán)隊列SQ的存儲空間,fhmt為隊頭指針,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.可以是子表或原子
0-8060-806
9.假祗?。横荏О参?且表表示稀疏矩陣,牌下髀匏06
A.5B.-800400)
對由1■麻露做網(wǎng)是a)D.000000
0530040)
00000300
10.在一棵度為3的樹中,度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個數(shù)為()
A.4B.5C.6D.7
11.在含n個頂點和e條邊的無向圖的鄰接矩陣中,零元素的個數(shù)為()
A.eB.2eC.n2-eD.n2-2e
12.假設(shè)一個有n個頂點和e條弧的有向圖用鄰接表表示,則刪除與某個頂點環(huán)相關(guān)的所有弧的時間復雜度
是()
A.O(n)B.0(e)C.O(n-i-e)D.O(n*e)
13.用某種排序方法對關(guān)鍵字序列(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)查找表進行高效率查找的組織結(jié)構(gòu)是()
A.有序表B.分塊有序表C.?:叉排序樹D.線性鏈表
15.不定長文件是指()
A.文件的長度不固定B.記錄的長度不固定
C.字段的長度不固定D.關(guān)鍵字項的長度不固定
第二部分非選擇題(共70分)
二、填空題(本大題共10小題,每小題2分,若有兩個空格,每個空格1分,共20分)不寫解答過程,
將正確的答案寫在每小題的空格內(nèi)。錯填或不填均無分。
16.數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù),它與數(shù)據(jù)的.無關(guān),是獨立于計算機的。
17.在-個帶頭結(jié)點的單循環(huán)鏈表中,p指向尾結(jié)點的直接前驅(qū),則指向頭結(jié)點的指針head可用p表示為
head=
18.棧頂?shù)奈恢檬请S著.操作而變化的。
19.在串S="structure”中,以t為首字符的子串有..個。
20.假設(shè)?個9階的上三角矩陣A按列優(yōu)先順序壓縮存儲在?維數(shù)組B中,其中B[0]存儲矩陣中第1個元
素aij,則B[31]中存放的元素是.
21.已知一棵完全二叉樹中共有768結(jié)點,則該樹中共有.個葉子結(jié)點。
22.己知一個圖的廣度優(yōu)先生成樹如右圖所示,則與此相
應(yīng)的廣度優(yōu)先遍歷序列為.
?
0?
23.在單鏈表上難以實現(xiàn)的排序方法有和。
24.在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時所需進行的關(guān)鍵字比較次數(shù)
為o
25.多重表文件和倒排文件都歸屬于文件。
三、解答題(本大題共4小題,每小題5分,共20分)
26.畫出下列廣義表的共享結(jié)構(gòu)圖形衣示
P=(((z),(x,y)),((x,y),x),(z))
27.請畫出與下列二叉樹對應(yīng)的森林。
28.已知一個無向圖的頂點集為{a,b,c,d,e},其鄰接矩陣如下所示
(I)畫出該圖的圖形;
(2)根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,寫出相應(yīng)的遍歷序列。
29.已知一個散列表如卜圖所示:
352()334S59
0123456789101112
其散列函數(shù)為h(key尸key%13,處理沖突的方法為雙重散列法,探查序列為:
hj=(h(key)+i*h1(kcy))%mi=0,m—1
其中
h1(key)=key%11+1
回答下列問題:
(1)對表中關(guān)鍵字35,20,33和48進行杳找時,所需進行的比較次數(shù)各為多少?
(2)該散列表在等概率查找時查找成功的平均查找長度為多少?
、題■,前黨分,共分)
四、算法閱讀題(本大題共4d620
應(yīng)串款后噴返回值為:
30.下列算法的功能是比較兩彳
1當S]>S2
comstr(S|,S2)=
請在空白處填入適當?shù)膬?nèi)容。
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是不帶頭結(jié)點的單鏈表的頭指針
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)設(shè)鏈表表示的線性表為(aha2,…,aQ,寫出算法執(zhí)行后的返回值所表示的線性表。
32.假設(shè)兩個隊列共享一個循環(huán)向量空間(參見右下圖),
其類型Queue2定義如卜.:
typedefstruct{
DateTypedata[MaxSize];
intfront[2],rear[2]:
}Queue2;
對于i=0或1,front[i]和rear[i]分別為第i個隊列的頭指針和尾指針。請對以下算法填空,實現(xiàn)第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.已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表,閱讀下面算法。
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)畫出執(zhí)行上述算法后所建立的結(jié)構(gòu);
(2)說明該算法的功能。
五、算法設(shè)計題(本題共10分)
34.閱讀下列函數(shù)arrangc()
intarrange(inta[],intl,inth,intx)
{//l和h分別為數(shù)據(jù)區(qū)的下界和上界
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)寫出該函數(shù)的功能;
(2)寫一個調(diào)用上述函數(shù)實現(xiàn)下列功能的算法:對一整型數(shù)組b[n]中的元素進行重新排列,將所有負數(shù)
均調(diào)整到數(shù)組的低下標端,將所有正數(shù)均調(diào)整到數(shù)組的高下標端,若有零值,則置于兩者之間,并
返回數(shù)組中零元素的個數(shù)。
數(shù)據(jù)結(jié)構(gòu)試題(三)參考答案
單項選擇題(本大題共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.存儲(或存儲結(jié)構(gòu))17.p—>next—>next
18.進棧和退棧19.12
20.為了21.384
22.abefedg
23.快速排序、堆排序、希爾排序
24.225.多關(guān)鍵字
三、解答題(本大題共4小題,每小題5分,共20分)
26.於m1
圖1圖2
*99zxyxy
27.A
深度優(yōu)先遍歷序列為:abdce
廣度優(yōu)先遍歷序列為:abcdc
29.(1)對關(guān)鍵字35、20、33和48進行查找的比較次數(shù)為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)查詢鏈表的尾結(jié)點
(2)將第一個結(jié)點鏈接到鏈表的尾部,作為新的尾結(jié)點
(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)中序遍歷二叉樹,按遍歷序列中葉子結(jié)點數(shù)據(jù)域的值構(gòu)建一個以Leafhead為頭指針的逆序單鏈
表(或按:叉樹中葉子結(jié)點數(shù)據(jù)自右至左鏈接成一個鏈表)。
五、算法設(shè)計題(本題共10分)
34.(1)該函數(shù)的功能是:調(diào)整整數(shù)數(shù)組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;
數(shù)據(jù)結(jié)構(gòu)試卷(四)
吉首大學試題庫
一、選擇題(20分)
1.組成數(shù)據(jù)的基本單位是(
(A)數(shù)據(jù)項(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量
2.設(shè)數(shù)據(jù)結(jié)構(gòu)A=(D,R),其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,<3,4>,<4,1>},則數(shù)
據(jù)結(jié)構(gòu)A是()。
(A)線性結(jié)構(gòu)(B)樹型結(jié)構(gòu)(C)圖型結(jié)構(gòu)(D)集合
3.數(shù)組的邏輯結(jié)構(gòu)不同于下列()的邏輯結(jié)構(gòu)。
(A)線性表(B)棧(C)隊列(D)樹
4.二叉樹中第i(iR)層上的結(jié)點數(shù)最多有()個。
(A)2i(B)2j(C)2iu(D)2i-l
5.設(shè)指針變量p指向單鏈表結(jié)點A,則刪除結(jié)點A的后繼結(jié)點B需要的操作為().
(A)p->next=p->next->next(B)p=p->next
(C)p=p->next->next(D)p->next=p
6.設(shè)棧S和隊列Q的初始狀態(tài)為空,元素El、E2、E3、E4、E5和E6依次通過棧S,一個元素出棧后即
進入隊列Q,若6個元素出列的順序為E2、E4、E3、E6、E5和E1,則棧S的容量至少應(yīng)該是()?
(A)6(B)4(C)3(D)2
7.將10階對稱矩陣壓縮存儲到?維數(shù)組A中,則數(shù)組A的長度最少為().
(A)100(B)40(C)55(D)80
8.設(shè)結(jié)點A有3個兄弟結(jié)點且結(jié)點B為結(jié)點A的雙
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 深入理解機電工程考試試題及答案解析
- 無線網(wǎng)絡(luò)的安全性問題探討試題及答案
- 湖北省孝感市八校2025屆高三下學期三模聯(lián)考數(shù)學試題
- 公共政策的透明性與公信力研究試題及答案
- 網(wǎng)絡(luò)工程師面臨的挑戰(zhàn)與機遇試題及答案
- 企業(yè)文化對收入分配制度的影響
- 公共政策轉(zhuǎn)型中的技術(shù)影響試題及答案
- 備受矚目2025年項目管理試題及答案
- 高速網(wǎng)絡(luò)技術(shù)與趨勢試題及答案
- 權(quán)力分立下的西方政治試題及答案
- 《安規(guī)變電部分》培訓課件
- 原發(fā)性肺癌診療規(guī)范
- 麻醉藥品和精神藥品管理培訓試題
- 中醫(yī)技能考核評分表
- 增材制造技術(shù)課件
- 電動力學-同濟大學中國大學mooc課后章節(jié)答案期末考試題庫2023年
- 五輸穴的臨床運用
- 基于增強現(xiàn)實(AR)體驗式學習模式在小學英語情景教學中的應(yīng)用
- 幼兒園游戲PPT中職學前教育專業(yè)完整全套教學課件
- 市場調(diào)查與分析考試試題
- 1噸串聯(lián)中頻爐原理技術(shù)與分析
評論
0/150
提交評論