《數(shù)據(jù)結(jié)構(gòu)》期中測試-2014計算機應(yīng)用技術(shù)用

1-12每題3分

1. 以下算法的時間復(fù)雜度為( )

for( i=n-1;i>=1; - -i)

for( j=1;j<=i;j++)

if(a[j]>a[j+1]) a[j]與a[j+1]對換；

A. O(n)B. O(n*log2n)C. O(log2n)D. O(n2)

2.下面關(guān)于線性表的敘述中，錯誤的是哪一個？( )

A.線性表采用順序存儲，可根據(jù)元素的序號隨機訪問元素

B.線性表采用順序存儲，插入操作在表尾進行時復(fù)雜度最高

C.線性表采用鏈?zhǔn)酱鎯?#xff0c;插入操作在表頭進行時復(fù)雜度最低

D.線性表采用鏈?zhǔn)酱鎯?#xff0c;刪除操作在表頭進行時復(fù)雜度最低

3. 設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用( )最節(jié)省時間。

A. 單鏈表 B.單循環(huán)鏈表 C. 帶尾指針的單循環(huán)鏈表

D.帶頭結(jié)點的雙循環(huán)鏈表

4. 設(shè)指針變量p指向雙向循環(huán)鏈表中的某結(jié)點，能刪除p所指結(jié)點的操作為( )。A. p->next = p->prior->next; p->prior= p->next->prior; free(p);B. p->prior->next=p->next; p->next->prior=p->prior; free(p); C. free(p); p=p->next; D. 以上都不正確

5. 一個棧的輸入序列為123…n，若輸出序列的第一個元素是n，輸出第i(1<=i<=n)個元素是( )。

A. 不確定 B. n-i+1 C. i D. n-i

6. 進行銀行窗口服務(wù)業(yè)務(wù)模擬時，應(yīng)該采用的數(shù)據(jù)結(jié)構(gòu)為( )

A.棧 B.隊列 C.樹 D.圖

7. 對于最大容量為n的循環(huán)隊列Q，隊尾指針是Q.rear，隊頭是Q.front，則隊滿的條件是 ( )

A. (Q.rear+1) % n=Q.front B. Q.rear=Q.front

C．Q.rear+1=Q.front D. (Q.rear-1) % n=Q.front

8. 一棵完全二叉樹上有1023個結(jié)點，其中葉子結(jié)點的個數(shù)是( )

A． 512 B． 511 C．513 D．前述答案均不正確

9. 關(guān)于樹與其對應(yīng)的二叉樹說法正確的是( )

A. 兩者葉子數(shù)相同

B. 兩者深度相同

C. 兩者結(jié)點數(shù)相同

D. 兩者度為2的結(jié)點數(shù)相同

10. 算術(shù)表達式a+b*(c+d/e)轉(zhuǎn)為后綴表達式后為( )

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++

11. 關(guān)于Huffamn樹，如下說法錯誤的是( )

A. 多于1個葉子結(jié)點的Huffman樹中不存在度為1的結(jié)點

B. Huffman樹中，任意調(diào)整結(jié)點左右孩子的順序，不影響帶權(quán)路徑長度

C. Huffamn樹的帶權(quán)路徑長度最大

D. Huffman樹中，權(quán)值越大的葉子結(jié)點離根結(jié)點越近

12. n個結(jié)點的線索二叉樹上含有的線索數(shù)為( )

A. 2n B. n－l C. n＋l D. n

13-18每題2分

13.鏈?zhǔn)酱鎯Φ膬?yōu)點是插入、刪除元素時不會引起后續(xù)元素的移動，缺點是只能順序訪問各元素。( DUI )

A.正確 B.錯誤

14. 單鏈表中引入頭結(jié)點會使結(jié)點插入操作的時間復(fù)雜度降為常數(shù)階。( CUO )

A.正確 B.錯誤

15.雙循環(huán)鏈表中，任一個結(jié)點的前驅(qū)與后繼指針都不為空。( DUI )

A.正確 B.錯誤

16. 循環(huán)隊列執(zhí)行出隊操作時會引起大量元素的移動。( CUO )

A.正確 B.錯誤

17. 樹的后根序遍歷序列等同于它所對應(yīng)二叉樹的中序遍歷序列。( DUI )

A.正確 B.錯誤

18.二叉樹可以用二叉鏈表存儲，樹無法用二叉鏈表存儲。( CUO )

A.正確 B.錯誤

以下每小問分值，在題后標(biāo)出

19.已知樹的先根序列FKDAIE和后根序列DIAEKF

(1)試畫出該樹；-----------------------6分

(2)試畫出該樹對應(yīng)的二叉樹；-

總結(jié)

以上是生活随笔為你收集整理的《数据结构》是计算机应用,《数据结构》期中测试-2014计算机应用技术用.doc的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。