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