数据结构题及c语言版答案9.14,十套数据结构试题+答案+难题解析(精校版)
十套數據結構試題+答案+難題解析(精校版)
更新時間：2017/2/9 10:47:00??瀏覽量：643??手機版
數據結構試卷(一)
一、單選題(每題 2 分，共20分)
1. 棧和隊列的共同特點是( A )。
A.只允許在端點處插入和刪除元素
B.都是先進后出
C.都是先進先出
D.沒有共同點
2. 用鏈接方式存儲的隊列，在進行插入運算時( D ).
A. 僅修改頭指針 B. 頭、尾指針都要修改
C. 僅修改尾指針 D.頭、尾指針可能都要修改
3. 以下數據結構中哪一個是非線性結構？( D )
A. 隊列 B. 棧 C. 線性表 D. 二叉樹
4. 設有一個二維數組A[m][n]，假設A[0][0]存放位置在644(10)，A[2][2]存放位置在
676(10)，每個元素占一個空間，問A[3][3](10)存放在什么位置？腳注(10)表示用10進制表示。C
A．688B．678 C．692 D．696
5. 樹最適合用來表示( C )。
A.有序數據元素 B.無序數據元素
C.元素之間具有分支層次關系的數據 D.元素之間無聯系的數據
6. 二叉樹的第k層的結點數最多為( D ).
kk-1A．2-1 B.2K+1 C.2K-1D. 2
7. 若有18個元素的有序表存放在一維數組A[19]中，第一個元素放A[1]中，現進行二
分查找，則查找A［3］的比較序列的下標依次為( D )
A. 1，2，3 B. 9，5，2，3
C. 9，5，3 D. 9，4，2，3
8. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為C
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作為散列函數，則散列地址為1的元素有( D )個，
A．1 B．2 C．3 D．4
10. 設有6個結點的無向圖，該圖至少應有( A )條邊才能確保是一個連通圖。
A.5 B.6 C.7 D.8
二、填空題(每空1分，共26分)
1. 通常從四個方面評價算法的質量：__正確性__、_易讀性_、_強壯性_和__高效率___。
1. 一個算法的時間復雜度為(n3+n2log2n+14n)/n2，其數量級表示為____ O(n)____。
2. 假定一棵樹的廣義表表示為A(C，D(E，F，G)，H(I，J))，則樹中所含的結點數
為______9____個，樹的深度為_____3______，樹的度為_____3____。
3. 后綴算式9 2 3 +- 10 2 / -的值為_____-1_____。中綴算式(3+4X)-2Y/3對應的后綴算
式為_________3 4 X * + 2 Y * 3 / -_______。
4. 若用鏈表存儲一棵二叉樹時，每個結點除數據域外，還有指向左孩子和右孩子的兩個指
針。在這種存儲結構中，n個結點的二叉樹共有_____2n ___個指針域，其中有____ n-1____個指針域是存放了地址，有_________ n+1_______個指針是空指針。
5. 對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結點
分別有____ e ___個和____2e ____個。
6. AOV網是一種________有向無回路___________的圖。
7. 在一個具有n個頂點的無向完全圖中，包含有__ n(n-1)/2______條邊，在一個具有n
個頂點的有向完全圖中，包含有____ n(n-1)____條邊。
8. 假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數的元
素成為一個子表，則得到的四個子表分別為_____(12，40)_____、_____( )____、__(74)____和______(23,55，63)____。
9. 向一棵B_樹插入元素的過程中，若最終引起樹根結點的分裂，則新樹比原樹的高度
______增加1_____。
10. 在堆排序的過程中，對任一分支結點進行篩運算的時間復雜度為____ O(log2n)____，
整個堆排序過程的時間復雜度為____ O(nlog2n)____。
11. 在快速排序、堆排序、歸并排序中，_____歸并____排序是穩定的。
三、計算題(每題 6 分，共24分)
1. 在如下數組A中鏈接存儲了一個線性表，表頭指針為A [0].next，試寫出該線性表。
data next 1. 線性表為：(782. 請畫出下圖的鄰接矩陣和鄰接表。
?0?1??1??1
?02. 鄰接矩陣：?1110?0101??1011??0101?1110?
?
鄰接表如圖11所示：
圖11
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};
用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。
3. 用克魯斯卡爾算法得到的最小生成樹為：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 畫出向小根堆中加入數據4, 2, 5, 8, 3時，每加入一個數據后堆的變化。
4. 見圖12
圖12
四、閱讀算法(每題7分，共14分)
1.
LinkList mynote(LinkList L)
{//L是不帶頭結點的單鏈表的頭指針
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的功能；(1)查詢鏈表的尾結點
(2)說明語句組S2的功能；(2)將第一個結點鏈接到鏈表的尾部，作為新的尾結點
(3)設鏈表表示的線性表為(a1,a2, ?,an),寫出算法執行后的返回值所表示的線性表。(3)返回的線性表為(a2,a3,?,an,a1)
2. void ABC(BTNode * BT)
{ if BT
{ ABC (BT->left);
ABC (BT->right);
cout<data<
}
}
該算法的功能是：遞歸地后序遍歷鏈式存儲的二叉樹。
五、算法填空(共8分)
二叉搜索樹的查找——遞歸算法:
bool Find(BTreeNode* BST,ElemType& item)
{ if (BST==NULL)
return false; //查找失敗
else
{ if (item==BST->data)
{ item=BST->data;//查找成功
return _____ true ______;}
else if(itemdata)
return Find(_______BST->left _______,item);
else return Find(________BST->right _______,item);
}//if
}
六、編寫算法(共8分)
統計出單鏈表HL中結點的值等于給定值X的結點數。 int CountX(LNode* HL,ElemType x)
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i為計數器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循環時i中的值即為x結點個數 return i;
}//CountX
總結
以上是生活随笔為你收集整理的数据结构题及c语言版答案9.14,十套数据结构试题+答案+难题解析(精校版)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： c 语言 声明 定义,C/C++语言声明
- 下一篇： 求楼字开头的成语接龙！