數(shù)據(jù)結(jié)構(gòu)期末考試試卷3套

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)期末考試試卷3套數(shù)據(jù)結(jié)構(gòu)

一、判斷題（共10分，每題1分）（×）1、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。

（×）2、串是由有限個字符構(gòu)成的連續(xù)序列，串長度為串中字符的個數(shù)，子串是主串中符構(gòu)成的有限序列。

（×）3、子串定位函數(shù)的時間繁雜度在最壞狀況下為O（n*m），因此子串定位函數(shù)沒有實際使用的價值。

（×）4、在線性鏈表中刪除中間的結(jié)點時，只需將被刪結(jié)點釋放。

（×）5、鄰接表只能用于有向圖的存儲，鄰接矩陣對于有向圖和無向圖的存儲都適用。（√）6、遞歸定義的數(shù)據(jù)結(jié)構(gòu)尋常用遞歸算法來實現(xiàn)對它的操作。

（√）7、在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進(jìn)行前序遍歷和按層遍歷，則具有一致的結(jié)果。

（√）8、已知指針P指向鍵表L的某結(jié)點，執(zhí)行語句P=P->next不會刪除該鏈表中的結(jié)點。

（√）9、對一個連通圖進(jìn)行一次深度優(yōu)先探尋可以遍訪圖中的所有頂點。（√）10、進(jìn)行折半探尋的表必需是順序存儲的有序表。二、填空題（共20分，每空1分）

1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系有限集合。

2、算法的五個重要特性是有窮性、確定性、可行性、輸入、輸出。

3、在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以任意多個。

4、在樹形結(jié)構(gòu)中，樹根結(jié)點沒有前驅(qū)結(jié)點，其余每個結(jié)點有且只有1個直接

前驅(qū)結(jié)點，葉子結(jié)點沒有后續(xù)結(jié)點，其余每個結(jié)點的直接后續(xù)結(jié)點可以任意多個。

5、在具有n個單元的循環(huán)隊列中，隊滿時共有n-1個元素。6、向棧中壓入元素的操作是先移動棧頂指針，后存入元素。

7、不包含任何字符（長度為0）的串稱為空串；

由一個或多個空格（僅由空格符）組成的串稱為空白串。8、假使含n個頂點的圖形成一個環(huán)，則它有n棵生成樹。

9、有向圖中的結(jié)點前驅(qū)后繼關(guān)系的特征是一個結(jié)點可能有若干個前驅(qū)，也可能有若干個后繼。

10、折半查找的存儲結(jié)構(gòu)僅限于_順序存儲結(jié)構(gòu)__，且是有序的。三、選擇題（共30分，每題2分）

1.一個向量（即一批地址連續(xù)的存儲單元）第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是____。A.110B.108C.100D.120

2.線性表的順序存儲結(jié)構(gòu)是一種___的存儲結(jié)構(gòu)，而鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種___的存儲結(jié)構(gòu)。A．隨機存取B．索引存取C．順序存取D．散列存取

3.線性表的規(guī)律順序與存儲順序總是一致的，這種說法___。A.正確B.不正確

4．設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作____。A.連接C.求子串

B.模式匹配D.求串長

5．設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號i的字符開始的j個字符組成的子串，len(s)返回串s的長度，則con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的結(jié)果串是____。A.BCDEFC.BCPQRST

B.BCDEFG

D.BCDEFEF

6.二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，數(shù)組元素A[7][4]的起始地址為____。

A.SA+141B.SA+144C.SA+222D.SA+225

7.二維數(shù)組A中，每個元素A的長度為3個字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A[4][7]的起始地址為____。A.SA+141B.SA+180C.SA+222D.SA+225

8.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特別的樹，這種說法____。A.正確B.錯誤

9.假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為個。

A．15B．16C．17D．47

10.依照二叉樹的定義，具有3個結(jié)點的不同形狀的二叉樹有____種。A.3B.4C.5D.6

11.依照二叉樹的定義，具有3個不同數(shù)據(jù)結(jié)點的不同的二叉樹有____種。A.5B.6C.30D.32

12.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的____倍。A.1/2B.1C.2D.413．任何一個無向連通圖的最小生成樹。A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

14．在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的____倍。A.1/2B.1C.2D.4

15.解決散列法中出現(xiàn)的沖突問題常采用的方法是。

A.數(shù)字分析法、除余法、平方取中法B.數(shù)字分析法、除余法、線性探測法C.數(shù)字分析法、線性探測法、多重散列法D.線性探測法、多重散列法、鏈地址法四、簡答題（共24分，每題6分）

1、根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有5種不同的形態(tài)，請將它們分別畫出。答：如圖6.10所示

cbaaccabaccbabcb圖6.10樹形5種

2、試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點。在什么狀況下用順序表比鏈表好？答：①順序存儲時，相鄰數(shù)據(jù)元素的存放地址也相鄰（規(guī)律與物理統(tǒng)一）；要求內(nèi)存中可用存儲單元的地址必需是連續(xù)的。

優(yōu)點：存儲密度