數(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è)字符構(gòu)成的連續(xù)序列，串長度為串中字符的個(gè)數(shù)，子串是主串中符構(gòu)成的有限序列。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

B.模式匹配D.求串長

5．設(shè)串s1=’ABCDEFG’，s2=’PQRST’，函數(shù)con(x,y)返回x和y串的連接串，subs(s,i,j)返回串s的從序號(hào)i的字符開始的j個(gè)字符組成的子串，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中，每個(gè)元素A的長度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為____。

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

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

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

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

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

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

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

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

B.有一棵或多棵

C.一定有多棵

D.可能不存在

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

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

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

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

cbaaccabaccbabcb圖6.10樹形5種

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

優(yōu)點(diǎn)：存儲(chǔ)密度