「資料結構」期末考試試題
一、單選題(每小題2分，共12分)
1．在乙個單鏈表hl中，若要向表頭插入乙個由指標p指向的結點，則執行( )。
a． hl＝ps p一》next＝hl
b． p一》next＝hl；hl＝p3
c． p一》next＝hl；p＝hl；
d． p一》next＝hl一》next;hl一》next＝p；
2．n個頂點的強連通圖中至少含有( )。
a.n—l條有向邊 b.n條有向邊
c.n(n—1)／2條有向邊 d.n(n一1)條有向邊
3.從一棵二叉搜尋樹中查詢乙個元素時，其時間複雜度大致為( )。
a.o(1) b.o(n)
c.o(1ogzn) d.o(n2)
4．由權值分別為3，8，6，2，5的葉子結點生成一棵哈夫曼樹，它的帶權路徑長度為( )。
a．24 b．48
c． 72 d． 53
5．當乙個作為實際傳遞的物件占用的儲存空間較大並可能需要修改時，應最好把它說明為( )引數，以節省引數值的傳輸時間和儲存引數的空間。
a.整形 b.引用型
c.指標型 d.常值引用型·
6．向乙個長度為n的順序表中插人乙個新元素的平均時間複雜度為( )。
a．o(n) b．o(1)
c．o(n2) d．o(10g2n)
二、填空題(每空1分，共28分)
1．資料的儲存結構被分為——、——、——和——四種。
2．在廣義表的儲存結構中，單元素結點與表元素結點有乙個域對應不同，各自分別為——域和——域。
3．——中綴表示式 3十x*(2.4／5—6)所對應的字尾表示式為————。
4．在一棵高度為h的3叉樹中，最多含有——結點。
5．假定一棵二叉樹的結點數為18，則它的最小深度為——，最大深度為——·
6．在一棵二叉搜尋樹中，每個分支結點的左子樹上所有結點的值一定——該結點的值，右子樹上所有結點的值一定——該結點的值。
7．當向乙個小根堆插入乙個具有最小值的元素時，該元素需要逐層——調整，直到被調整到——位置為止。
8．表示圖的三種儲存結構為——、——和———。
9．對用鄰接矩陣表示的具有n個頂點和e條邊的圖進行任一種遍歷時，其時間複雜度為——，對用鄰接表表示的圖進行任一種遍歷時，其時間複雜度為——。
10．從有序表(12，18，30，43，56，78，82，95)中依次二分查詢43和56元素時，其查詢長度分別為——和——·
11．假定對長度n＝144的線性表進行索引順序查詢，並假定每個子表的長度均為，則進行索引順序查詢的平均查詢長度為——，時間複雜度為——·
12．一棵b—樹中的所有葉子結點均處在——上。
13．每次從無序表中順序取出乙個元素，把這插入到有序表中的適當位置，此種排序方法叫做——排序；每次從無序表中挑選出乙個最小或最大元素，把它交換到有序表的一端，此種排序方法叫做——排序。
14．快速排序在乎均情況下的時間複雜度為——，最壞情況下的時間複雜度為——。
三、運算題(每小題6分，共24分)
1．假定一棵二叉樹廣義表表示為a(b(c，d)，c(((，8)))，分別寫出對它進行先序、中序、後序和後序遍歷的結果。
先序：中序；後序：
2．已知乙個帶權圖的頂點集v和邊集g分別為：
v＝；e=，則求出該圖的最小生成樹的權。
最小生成樹的權；
3．假定一組記錄的排序碼為(46，79，56，38，40，84，50，42)，則利用堆排序方法建立的初始堆為——。
4．有7個帶權結點，其權值分別為3，7，8，2，6，10，14，試以它們為葉子結點生成一棵哈夫曼樹，求出該樹的帶權路徑長度、高度、雙分支結點數。
帶權路徑長度：—— 高度：—— 雙分支結點數：——。
四、閱讀演算法，回答問題(每小題8分，共16分)
1．voldac(list&l)
;for(inti＝0; i<5; i++)
if (a[i]％2＝＝0)insertfront(l，a[i])；
elselnsertrear(l，a[i])；
}該演算法被呼叫執行後，得到的線性表l為：
2．void ag(queue&q)
；for(int i＝0;i<5; i++)qinsert(q，a[i])；
qinsert(q，qdelete(q))；
qinsert(q，20)；
qinsert(q，qdelete(q)十16)；
while(!queueempty(q))cout< }
該演算法被呼叫後得到的輸出結果為：
五、演算法填空，在畫有橫線的地方填寫合適的內容(每小題6分，共12分)
1．從一維陣列a[n)中二分查詢關鍵字為k的元素的遞迴演算法，若查詢成功則返回對應元素的下標，否則返回一1。
intbinsch(elemtypea，intlow，int high，keytypek)
else return—l；
}2．已知二叉樹中的結點型別bintreenode定義為：
structbintreenode；
其中data為結點值域，left和right分別為指向左、右子女結點的指標域。下面函式的功能是返回二叉樹bt中值為x的結點所在的層號，請在劃有橫線的地方填寫合適內容。
int nodelevel(bintreenode * bt，elemtype x)
}六、編寫演算法(8分)
按所給函式宣告編寫乙個演算法，從表頭指標為hl的單鏈表中查詢出具有最大值的結點，該最大值由函式返回，若單鏈表為空則中止執行。
eiemtype maxvalue(lnode*hl);
「資料結構」期末考試試題答案
一、單選題(每小題2分，共12分)
評分標準；選對者得2分，否則不得分。
1．b 2．b 3．c 4．d 5．b 6．a
二、填空題(每空1分，共28分)
1．順序結構鏈結結構索引結構雜湊結構(次序無先後)
2．值(或data) 子表指標(或sublist)
3．3 x 2．4 5／6一*十
4．(3h一1)／2
5． 5 18
6．小於大於(或大於等於)
7．向上堆頂
8．鄰接矩陣鄰接表邊集陣列(次序無先後)
9．o(n2) o(e)
10． 1 3
11．13 o()
12．同一層
13．插人選擇
14．o(nlog2n) o(n2)
三、運算題(每小題6分，共24分)
1．先序：a，b，c，d，e，f，e ／／2分
中序：c，b，d，a，f，8，e ／／2分
後序：c，d，b，e，f，e，a ／／2分
2．最小生成樹的權：31 ／／6分
3．(84，79，56，42，40，46，50，38) ／／6分
4．帶權路徑長度：131 ／／3分
高度：5 ／／2分
雙分支結點數：6 ／／1分
四、閱讀演算法，回答問題(每小題8分，共16分)
評分標準：每小題正確得8分，出現一處錯誤扣4分，兩處及以上錯誤不得分。
1．(36，12，8，50，25，5，15)
2．5 15 8 6 20 28
五、演算法填空，在畫有橫線的地方填寫合適的內容(每小題6分，共12分)
1．feturn mid ／／2分
returnbinsch(a，low，mid一1，k) ／／2分
returnbmsch(a，mid+1，high，k) ／／2分
2．nodelevel(bt一》right，x) ／／3分
(c2>=1)returnc2十1 ／／3分
六、編寫演算法(8分)
評分標準：請參考語句後的注釋，或根據情況酌情給分。
資料結構C語言版期末考試試題有答案
只要站起來的次數比倒下去的次數多，那就是成功。資料結構 期末考試試題 一 單選題 每小題2分 共12分 1 在乙個單鏈表hl中 若要向表頭插入乙個由指標p指向的結點 則執行 a hl ps p一 next hl b p一 next hl hl p3 c p一 next hl p hl d p一 ne...
資料結構C語言版期末考試試題 有答案
勇者，必以決鬥之勇氣與五張試卷一決雌雄 懦夫，概以鼠目之寸光量人生此戰必輸無疑！資料結構 期末考試試題 一 單選題 每小題2分 共12分 1 在乙個單鏈表hl中 若要向表頭插入乙個由指標p指向的結點 則執行 a hl ps p一 next hl b p一 next hl hl p3 c p一 nex...
資料結構C語言版期末考試試題 有答案
惜光陰百日猶短，看眾志成城拼搏第一 細安排一刻也長，比龍爭虎鬥誰為爭鋒？資料結構 期末考試試題 一 單選題 每小題2分 共12分 1 在乙個單鏈表hl中 若要向表頭插入乙個由指標p指向的結點 則執行 a hl ps p一 next hl b p一 next hl hl p3 c p一 next hl...