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

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

2、。6若一個圖的頂點集為abcdef邊集為（ab）(ac)(bc)(de)則該圖含有___3____個連通分量。7在進行直接插入排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__有___關(guān)；而在進行直接選擇排序時，其數(shù)據(jù)比較次數(shù)與數(shù)據(jù)的初始排列__無___關(guān)。8若對關(guān)鍵字序列（43，02，80，48，26，57，15，73，21，24，66）進行一趟增量為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時所需進行的關(guān)鍵字比較次數(shù)為__2___。10.在線形表的散列存儲中，處理沖突有開放定址法和鏈地址法兩種方法。11.已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有______12______個葉子的結(jié)點。12.設(shè)二叉樹結(jié)點的先根序列為ABDECFGH，中根序列為DEBAFCHG則二叉樹中葉子結(jié)點是_EFH___。13若

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

5、15，27，68，35，20）進行排序時，序列的變化情況如下：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.采用鄰接表存儲的圖的廣度優(yōu)先遍歷算法類似于二叉樹的D。A先序遍歷；B中序遍歷；C后序遍歷；D按層遍歷。14.若一個圖的邊集為則從頂點1開始對該圖進行深

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