《數(shù)據(jù)結(jié)構(gòu)》試題及答案
數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。以下是小編為大家整理推薦關(guān)于數(shù)據(jù)結(jié)構(gòu)試卷題和答案，希望對(duì)大家有所幫助。
數(shù)據(jù)結(jié)構(gòu)試卷題目
一、單選題(每題 2 分，共20分)
1. 棧和隊(duì)列的共同特點(diǎn)是( )。
A.只允許在端點(diǎn)處插入和刪除元素
B.都是先進(jìn)后出
C.都是先進(jìn)先出
D.沒(méi)有共同點(diǎn)
2. 用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( ).
A. 僅修改頭指針 B. 頭、尾指針都要修改
C. 僅修改尾指針 D.頭、尾指針可能都要修改
3. 以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)?( )
A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹(shù)
4. 設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644(10)，A[2][2]存放位置在
676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A[3][3](10)存放在什么位置?腳注(10)表示用10進(jìn)制表示。
A.688 B.678 C.692 D.696
5. 樹(shù)最適合用來(lái)表示( )。
A.有序數(shù)據(jù)元素 B.無(wú)序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無(wú)聯(lián)系的數(shù)據(jù)
6. 二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為( ).
kk-1 A.2-1 B.2K+1 C.2K-1 D. 2
7. 若有18個(gè)元素的有序表存放在一維數(shù)組A[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二
分查找，則查找A〔3〕的比較序列的下標(biāo)依次為( )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
8. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為
A. O(1) B. O(n) C. O(1og2n) D. O(n2)
9. 對(duì)于線性表(7，34，55，25，64，46，20，10)進(jìn)行散列存儲(chǔ)時(shí)，若選用H(K)
=K %9作為散列函數(shù)，則散列地址為1的元素有( )個(gè)，
A.1 B.2 C.3 D.4
10. 設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( )條邊才能確保是一個(gè)連通圖。
A.5 B.6 C.7 D.8
二、填空題(每空1分，共26分)
1. 通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：_________、_________、_________和_________。
2. 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級(jí)表示為_(kāi)_______。
3. 假定一棵樹(shù)的.廣義表表示為A(C，D(E，F(xiàn)，G)，H(I，J))，則樹(shù)中所含的結(jié)點(diǎn)數(shù)
為_(kāi)_________個(gè)，樹(shù)的深度為_(kāi)__________，樹(shù)的度為_(kāi)________。
4. 后綴算式9 2 3 +- 10 2 / -的值為_(kāi)_________。中綴算式(3+4X)-2Y/3對(duì)應(yīng)的后綴算式
為_(kāi)______________________________。
5. 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指
針。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有________個(gè)指針域，其中有________個(gè)指針域是存放了地址，有________________個(gè)指針是空指針。
6. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)
分別有_______個(gè)和________個(gè)。
7. AOV網(wǎng)是一種___________________的圖。
8. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有________條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有
向完全圖中，包含有________條邊。
9. 假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元
素成為一個(gè)子表，則得到的四個(gè)子表分別為_(kāi)___________________________、___________________、_______________________和__________________________。
10. 向一棵B_樹(shù)插入元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的分裂，則新樹(shù)比原樹(shù)的高度
___________。
11. 在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_(kāi)_______，整個(gè)堆排序
過(guò)程的時(shí)間復(fù)雜度為_(kāi)_______。
12. 在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。
三、計(jì)算題(每題 6 分，共24分)
1. 在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A [0].next，試寫(xiě)出該線性表。
data next 2.
3. 已知一個(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};
用克魯斯卡爾算法得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。
4. 畫(huà)出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。
四、閱讀算法(每題7分，共14分)
1. LinkList mynote(LinkList L)
{//L是不帶頭結(jié)點(diǎn)的單鏈表的頭指針
if(L&&L->next){
q=L;L=L->next;p=L;
S1： while(p->next) p=p->next;
S2： p->next=q;q->next=NULL;
}
return L;
}
請(qǐng)回答下列問(wèn)題：
(1)說(shuō)明語(yǔ)句S1的功能;
(2)說(shuō)明語(yǔ)句組S2的功能;
(3)設(shè)鏈表表示的線性表為(a1,a2
, ?,an),寫(xiě)出算法執(zhí)行后的返回值所表示的線性表。
2. void ABC(BTNode * BT)
{
if BT {
ABC (BT->left);
ABC (BT->right);
cout
}
}
該算法的功能是：
五、算法填空(共8分)
二叉搜索樹(shù)的查找遞歸算法:
bool Find(BTreeNode* BST,ElemType& item)
{
if (BST==NULL)
return false; //查找失敗
else {
if (item==BST->data){
item=BST->data;//查找成功
return ___________;}
else if(itemdata)
return Find(______________,item); else return Find(_______________,item); }//if
}
六、編寫(xiě)算法(共8分)
統(tǒng)計(jì)出單鏈表HL中結(jié)點(diǎn)的值等于給定值X的結(jié)點(diǎn)數(shù)。 int CountX(LNode* HL,ElemType x)
數(shù)據(jù)結(jié)構(gòu)試卷參考答案
一、選擇題(每題2分，共20分)
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
二、填空題(每空1分，共26分)
1. 正確性 易讀性 強(qiáng)壯性 高效率
2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / -
5. 2n n-1 n+1
6. e 2e
7. 有向無(wú)回路
8. n(n-1)/2 n(n-1)
9. (12，40) ( ) (74) (23,55，63)
10.增加1
11.O(log2n) O(nlog2n)
12.歸并
三、計(jì)算題(每題6分，共24分)
1. 線性表為：(78，50，40，60，34，90)
?0?1??1??1
?02. 鄰接矩陣：?1110?0101??1011??0101?1110??
鄰接表如圖11所示：
圖11
3. 用克魯斯卡爾算法得到的最小生成樹(shù)為：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 見(jiàn)圖12
26
四、讀算法(每題7分，共14分)
1. (1)查詢鏈表的尾結(jié)點(diǎn)
(2)將第一個(gè)結(jié)點(diǎn)鏈接到鏈表的尾部，作為新的尾結(jié)點(diǎn)
(3)返回的線性表為(a2,a3,?,an,a1)
2. 遞歸地后序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)。
五、法填空(每空2分，共8 分)
true BST->left BST->right
六、編寫(xiě)算法(8分)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i為計(jì)數(shù)器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循環(huán)時(shí)i中的值即為x結(jié)點(diǎn)個(gè)數(shù)
return i;
}//CountX
【《數(shù)據(jù)結(jié)構(gòu)》試題及答案】相關(guān)文章：
1.數(shù)據(jù)結(jié)構(gòu)試題及答案
2.大學(xué)《數(shù)據(jù)結(jié)構(gòu)》試題及答案
3.算法與數(shù)據(jù)結(jié)構(gòu)試題及答案
4.《算法數(shù)據(jù)結(jié)構(gòu)》期末試題及答案
5.大學(xué)《算法數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)試題及答案
6.算法與數(shù)據(jù)結(jié)構(gòu)模擬試題及答案