勇者,必以決鬥之勇氣與五張試卷一決雌雄;懦夫,概以鼠目之寸光量人生此戰必輸無疑!
"資料結構"期末考試試題
一、單選題(每小題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個頂點的強連通圖中至少含有( )
條有向邊 條有向邊
條有向邊 一1)條有向邊
3.從一棵二叉搜尋樹中查詢乙個元素時
其時間複雜度大致為( )
4.由權值分別為386
25的葉子結點生成一棵哈夫曼樹
它的帶權路徑長度為( )
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
1830
4356
7882
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
7956
3840
8450
42)則利用堆排序方法建立的初始堆為--
4.有7個帶權結點
其權值分別為378
261014
試以它們為葉子結點生成一棵哈夫曼樹
求出該樹的帶權路徑長度、高度、雙分支結點數
帶權路徑長度:-- 高度:-- 雙分支結點數:--
四、閱讀演算法
回答問題(每小題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.先序:abc
defe //2分
中序:cbd
af8e //2分
後序:cdb
efea //2分
2.最小生成樹的權:31 //6分
3.(84
7956
4240
4650
38) //6分
4.帶權路徑長度:131 //3分
高度:5 //2分
雙分支結點數:6 //1分
四、閱讀演算法
回答問題(每小題8分
共16分)
評分標準:每小題正確得8分
出現一處錯誤扣4分
兩處及以上錯誤不得分
1.(36128
5025
515)
2.5 15 8 6 20 28
五、演算法填空
在畫有橫線的地方填寫合適的內容(每小題6分
共12分)
1.feturn mid //2分
returnbinsch(a
lowmid一1
k) //2分
returnbmsch(a
mid+1
high
k) //2分
2.nodelevel(bt一》right
x) //3分
(c2>=1)returnc2十1 //3分
六、編寫演算法(8分)
評分標準:請參考語句後的注釋
或根據情況酌情給分
elemtype maxvalue(lnodeo* hl
) {
if (hl==null){ //2分
cerr<<"linked llst is empty!"< 資料結構 期末考試試題 一 單選題 每小題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分 共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... 惜光陰百日猶短,看眾志成城拼搏第一 細安排一刻也長,比龍爭虎鬥誰為爭鋒?資料結構 期末考試試題 一 單選題 每小題2分 共12分 1 在乙個單鏈表hl中 若要向表頭插入乙個由指標p指向的結點 則執行 a hl ps p一 next hl b p一 next hl hl p3 c p一 next hl...資料結構C語言版期末考試試題有答案
資料結構C語言版期末考試試題有答案
資料結構C語言版期末考試試題 有答案