1、福師11春學期數據結構概論在線作業一一、單選題（共 20 道試題，共 40 分。）1. 就平均性能而言，目前最好的內部排序方法是（ ）排序法。 A. 冒泡B. 希爾插入C. 交換D. 快速 2. 從邏輯上可以把數據結構分為（ ）兩大類A. 動態結構、靜態結構B. 順序結構、鏈式結構C. 線性結構、非線性結構D. 初等結構、構造型結構 3. 在完全二叉樹中，若一個結點是葉結點，則它沒（ ）A. 左子結點B. 右子結點C. 左子結點和右子結點D. 左子結點，右子結點和兄弟結點 4. 用二分（對半）查找表的元素的速度比用順序法（ ）A. 必然快B. 必然慢C. 相等D.

2、 不能確定 5. 算法的計算量的大小稱為計算的（ ）A. 效率B. 復雜性C. 現實性D. 難度 6. 以下數據結構中（ ）是非線性數據結構A. 樹B. 字符串C. 隊D. 棧 7. 下面的程序段中，對x的賦值語句的頻度為（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;A. O(2n)B. O(n)C. O(n2)D. O(log2n) 8. 散列函數有一個共同的性質，即函數值應當以（ ）取其值域的每個值。A. 最大概率B. 最小概率C. 平均概率D. 同等概率 9. 最大容量為n的循環隊列，隊尾指針是re

3、ar，隊頭是front，則隊空的條件是（ ）A. (rear+1) MOD n=frontB. rear=frontC. rear+1=frontD. (rear-l) MOD n=front 10. 若要求排序是穩定的，且關鍵字為實數，則在下列排序方法中應選（ ）排序為宜。A. 直接插入B. 直接選擇C. 堆D. 快速 11. 設計一個判別表達式中左，右括號是否配對出現的算法，采用（ ）數據結構最佳。A. 線性表的順序存儲結構B. 隊列C. 線性表的鏈式存儲結構D. 棧 12. 設廣義表L=（a,b,c），則L的長度和深度分別為（ ）A. 1和1B. 1和3C.

4、 1和2D. 2和3 13. 一個棧的輸入序列為123n，若輸出序列的第一個元素是n，輸出第i（1<=i<=n）個元素是（ ）A. 不確定B. n-i+1C. iD. n-i 14. 對于一個頭指針為head的帶頭結點的單鏈表，判定該表為空表的條件是（ ）A. head=NULLB. headnext=NULLC. headnext=headD. head!=NULL 15. 設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）A. 13B. 33C. 18D.

5、40 16. 求解最短路徑的Floyd算法的時間復雜度為（ ）。A. O（n）B. O（n+c）C. O（n*n）D. O（n*n*n） 17. 一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（ ）A. CABDEFGB. ABCDEFGC. DACEFBGD. ADCFEG 18. 要連通具有n個頂點的有向圖，至少需要（ ）條邊。A. n-lB. nC. n+lD. 2n 19. 由3 個結點可以構造出多少種不同的二叉樹（ ）A. 2B. 3C. 4D. 5 20. 從未排序序列中依次取出一個元素與已排序序列中的元素依次進行

6、比較，然后將其放在已排序序列的合適位置，該排序方法稱為（ ）排序法。A. 插入B. 選擇C. 希爾D. 二路歸并  二、判斷題（共 20 道試題，共 40 分。）1. 順序查找法適用于存儲結構為順序或鏈接存儲的線性表（ ）A. 錯誤B. 正確 2. 內部排序要求數據一定要以順序方式存儲（ ）A. 錯誤B. 正確 3. 消除遞歸不一定需要使用棧，此說法（ ）A. 錯誤B. 正確 4. 若一個廣義表的表頭為空表，則此廣義表亦為空表（ ）A. 錯誤B. 正確 5. 兩分法插入排序所需比較次數與待排序記錄的初始排列狀態相關（ ）A. 錯誤B.

7、 正確 6. 順序存儲結構的主要缺點是不利于插入或刪除操作（ ）A. 錯誤B. 正確 7. 線性表采用鏈表存儲時，結點和結點內部的存儲空間可以是不連續的（ ）A. 錯誤B. 正確 8. 順序存儲方式只能用于存儲線性結構（ ）A. 錯誤B. 正確 9. 折半查找法的查找速度一定比順序查找法快（ ）A. 錯誤B. 正確 10. 棧是實現過程和函數等子程序所必需的結構（ ）A. 錯誤B. 正確 11. 廣義表中的元素或者是一個不可分割的原子，或者是一個非空的廣義表（ ）A. 錯誤B. 正確 12. 采用二叉鏈表作存儲結構，樹的前序

8、遍歷和其相應的二叉樹的前序遍歷的結果是一樣的A. 錯誤B. 正確 13. 鏈表中的頭結點僅起到標識的作用（ ）A. 錯誤B. 正確 14. 線性表的特點是每個元素都有一個前驅和一個后繼（ ）A. 錯誤B. 正確 15. 當待排序的元素很多時，為了交換元素的位置，移動元素要占用較多的時間，這是影響時間復雜度的主要因素（ ）A. 錯誤B. 正確 16. 任何一棵二叉樹都可以不用棧實現前序線索樹的前序遍歷（ ）A. 錯誤B. 正確 17. 在查找樹（二叉樹排序樹）中插入一個新結點，總是插入到葉結點下面（ ）A. 錯誤B. 正確 18. 棧與

9、隊列是一種特殊操作的線性表（ ）A. 錯誤B. 正確 19. 用一維數組存儲二叉樹時，總是以前序遍歷順序存儲結點（ ）A. 錯誤B. 正確 20. 二叉樹的遍歷結果不是唯一的（ ）A. 錯誤B. 正確  三、判斷題（共 10 道試題，共 20 分。）V1. 二叉樹是度為2的有序樹（ ）A. 錯誤B. 正確 2. 隊列和棧都是運算受限的線性表，只允許在表的兩端進行運算（ ）。A. 錯誤B. 正確 3. 線性表只能用順序存儲結構實現（ ）A. 錯誤B. 正確 4. 算法的優劣與算法描述語言無關，但與所用計算機有關（ ）A. 錯誤B. 正確 5. 在執行某個排序算法過程中，出現了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩定的（ ）A. 錯誤B. 正確 6. 對無序表用二分法查找比順序查找快（ ）A. 錯誤B. 正確 7. 棧和隊列都是限制存取點的線性結構（ ）A. 錯誤B