• 一、選擇題

1、棧和隊列的共同特點是(????? )。
A.只允許在端點處插入和刪除元素?
B.都是先進后出?
C.都是先進先出?
D.沒有共同點

參考答案是：A

2、用鏈接方式存儲的隊列，在進行插入運算時(?? ).
A. 僅修改頭指針? 　?????????
B. 頭、尾指針都要修改?
C. 僅修改尾指針???????????????
D.頭、尾指針可能都要修改

參考答案是：D

3、以下數(shù)據(jù)結(jié)構(gòu)中哪一個是非線性結(jié)構(gòu)？( ??)
A. 隊列?? 　　??
B. 棧????????
C. 線性表? 　　??
D. 二叉樹

參考答案是：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

參考答案是：C

5、樹最適合用來表示(????? )。
A.有序數(shù)據(jù)元素?
B.無序數(shù)據(jù)元素
C.元素之間具有分支層次關(guān)系的數(shù)據(jù)????
D.元素之間無聯(lián)系的數(shù)據(jù)

參考答案是：C

6、二叉樹的第k層的結(jié)點數(shù)最多為(? ).

A. 2k-1???????
B.2K+1??????
C.2K-1? 　　　
D. 2k-1

參考答案是：D

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

參考答案是：D

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

A. O（1）?? 　　
B. O（n）　　???
C. O（1og2n）???????
D. O（n2）

參考答案是：C

9、對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）= K %9作為散列函數(shù)，則散列地址為1的元素有（?? ）個。
A．1?????????
B．2???????????
C．3???????????
D．4

參考答案是：D

10、設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有(????? )條邊才能確保是一個連通圖。
A.5???????
B.6?????????
C.7??????
D.8

參考答案是：A

二、填空題

1、通常從四個方面評價算法的質(zhì)量：_________、_________、_________和_________。

參考答案是：正確性 易讀性 強壯性 高效率

2、一個算法的時間復(fù)雜度為(n3+n2log2n+14n)/n2，其數(shù)量級表示為________。

參考答案是：O(n)

3、假定一棵樹的廣義表表示為A（C，D（E，F，G），H（I，J）），則樹中所含的結(jié)點數(shù)為_______個，樹的深度為_______，樹的度為_________。

參考答案是：9 3 3

4、后綴算式9 2 3 + - 10 2 / -的值為__________。中綴算式（3+4X）-2Y/3對應(yīng)的后綴算式為_________________。

參考答案是：-1 ? 3 4 X * + 2 Y * 3 / -

5、若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共
有 ________個指針域， 其中有________個指針域是存放了地址，有________________個指針是空指針。

參考答案是：2n n-1 n+1

6、對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應(yīng)的鄰接表中，所含邊結(jié)點分別有_______個和________個。

參考答案是：e 2e

7、AOV網(wǎng)是一種_____________的圖。

參考答案是：有向無回路

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

參考答案是：n(n-1)/2 n(n-1)

9、假定一個線性表為(12,23,74,55,63,40)，若按Key % 4條件進行劃分，使得同一余數(shù)的元素成為一個子表，則得到的四個子表分別為
__________________、 ___________________、_______________________和__________________________。

參考答案是：（12，40） （ ） （74） （23,55，63）

10、向一棵B_樹插入元素的過程中，若最終引起樹根結(jié)點的分裂，則新樹比原樹的高度___________。

參考答案是：增加1

11、在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復(fù)雜度為________，整個堆排序過程的時間復(fù)雜度為________。

參考答案是：O(log2n) O(nlog2n)

12、在快速排序、堆排序、歸并排序中，_________排序是穩(wěn)定的。

參考答案是：歸并

三、計算題

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

參考答案是：線性表為：（78，50，40，60，34，90）

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}; 用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

參考答案是：用克魯斯卡爾算法得到的最小生成樹為：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4、畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。

參考答案是：

四、閱讀算法

請回答下列問題：?

（1）說明語句S1的功能；?
（2）說明語句組S2的功能；?
（3）設(shè)鏈表表示的線性表為（a1,a2, …,an）,寫出算法執(zhí)行后的返回值所表示的線性表。

參考答案是：（1）查詢鏈表的尾結(jié)點
（2）將第一個結(jié)點鏈接到鏈表的尾部，作為新的尾結(jié)點
（3）返回的線性表為（a2,a3,…,an,a1）

2、void ABC(BTNode * BT)
{
??? ? if? BT?
???? {
???????? ABC (BT->left);
???????? ABC (BT->right);
???????? cout<<BT->data<<' ';
?? ? }
}
該算法的功能是什么？

參考答案是：遞歸地后序遍歷鏈式存儲的二叉樹。

五、算法填空

• 二叉搜索樹的查找——遞歸算法:
  ???? bool Find(BTreeNode* BST,ElemType& item)
  ???? {?
  ?????????? if (BST==NULL)
  ??????????????? return false; //查找失敗?
  ?????????? else?
  ?????????? {
  ????????????????? if (item==BST->data)
  ???????? ???????? {
  ????????????????????? item=BST->data;//查找成功?
  ????????????????????? return? ___________;
  ????????????????? }
  ?????????? else if(item<BST->data)
  ????????????????????? return? Find(______________,item);
  ?????????? else??
  ????????????????????? return Find(_______________,item);
  ?????????? }
  ???? }

參考答案是：true ? BST->left ? BST->right

六、編寫算法

• 統(tǒng)計出單鏈表HL中結(jié)點的值等于給定值X的結(jié)點數(shù)。?
  ???? int CountX(LNode* HL,ElemType x)

參考答案是：

來源：我是碼農(nóng)，轉(zhuǎn)載請保留出處和鏈接！

本文鏈接：http://www.54manong.com/?id=45

'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646208", container: s }); })(); '); (window.slotbydup = window.slotbydup || []).push({ id: "u3646147", container: s }); })();

總結(jié)

以上是生活随笔為你收集整理的数据结构试卷及答案（一）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。