數(shù)據(jù)結(jié)構(gòu)試題和答案

1、數(shù)據(jù)結(jié)構(gòu)試題和答案A卷一、填空題（共8小題，每空1分，共計(jì)20分）1棧和隊(duì)列都是_線性_結(jié)構(gòu)；對(duì)于棧只能在_棧頂_插入和刪除元素；對(duì)于隊(duì)列只能在_隊(duì)尾_插入元素和在_隊(duì)頭_刪除元素。2一個(gè)廣義表中的元素分為單元素和表元素兩類。3對(duì)于一個(gè)長度為n的順序存儲(chǔ)的線形表，在表頭插入元素的時(shí)間復(fù)雜度為__O(n)_______，在表尾插入元素的時(shí)間復(fù)雜度為____O(1)_______。5在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于n1

2、。6若一個(gè)圖的頂點(diǎn)集為abcdef邊集為（ab）(ac)(bc)(de)則該圖含有___3____個(gè)連通分量。7在進(jìn)行直接插入排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__有___關(guān)；而在進(jìn)行直接選擇排序時(shí)，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__無___關(guān)。8若對(duì)關(guān)鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進(jìn)行一趟增量為3的希爾排序，則得到的結(jié)果為（15，02，21，24，26，57，43，66，80，48，7

3、3）。9.在有序表（12，24，36，48，60，72，84）中折半查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為__2___。10.在線形表的散列存儲(chǔ)中，處理沖突有開放定址法和鏈地址法兩種方法。11.已知一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹中有______12______個(gè)葉子的結(jié)點(diǎn)。12.設(shè)二叉樹結(jié)點(diǎn)的先根序列為ABDECFGH，中根序列為DEBAFCHG則二叉樹中葉子結(jié)點(diǎn)是_EFH___。13若

4、由3，6，8，12，10作為葉子結(jié)點(diǎn)的值生成一棵哈夫曼樹，則該樹的高度為4帶權(quán)路徑長度為87。二、選擇題（共15小題，每題1分，共計(jì)15分）1算法指的是（D）10線性鏈表不具有的特點(diǎn)是（A）。A隨機(jī)訪問B不必事先估計(jì)所需存儲(chǔ)空間大小C插入與刪除時(shí)不必移動(dòng)元素D所需空間與線性表長度成正比11.含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中零元素的個(gè)數(shù)為(D)AeB2eCn2－eDn2－2e12.用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，

5、15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84則所采用的排序方法是（D）A選擇排序B希爾排序C歸并排序D快速排序13.采用鄰接表存儲(chǔ)的圖的廣度優(yōu)先遍歷算法類似于二叉樹的D。A先序遍歷；B中序遍歷；C后序遍歷；D按層遍歷。14.若一個(gè)圖的邊集為則從頂點(diǎn)1開始對(duì)該圖進(jìn)行深

6、度優(yōu)先搜索，得到的頂點(diǎn)序列可能為C。A1，2，5，4，3；B1，2，3，4，5；C1，2，5，3，4；D1，4，3，2，5。15.假定對(duì)元素序列（7，3，5，9，1，12）進(jìn)行堆排序，并且采用小根堆，則由初始數(shù)據(jù)構(gòu)成的初始堆為B。A1，3，5，7，9，12；B1，3，5，9，7，12；C1，5，3，7，9，12；D1，5，3，9，12，7。三、判斷題（對(duì)的打√，錯(cuò)的打共15小題，每題1分，共計(jì)15分）1、在線性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都有一個(gè)直