1、西安交通大學17年9月課程考試數(shù)據(jù)結構作業(yè)考核試題 1-5: B A D A D一、單選題（共 30 道試題，共 60 分。）1. （）二叉排序樹可以得到一個從小到大的有序序列。A. 先序遍歷B. 中序遍歷C. 后序遍歷D. 層次遍歷正確答案：B2. 下列程序段的時間復雜度為（）。i=0，s=0；while(sn)s=s+i；i+；A. O(n)B. O(n)C. O(n)D. O(n)正確答案：A3. 設數(shù)組datam作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指針，則執(zhí)行出隊操作后其頭指針front值為（）A. front=front+1B. front=(front+

2、1)%(m-1)C. front=(front-1)%mD. front=(front+1)%m正確答案：D4. 程序段s=i=0；doi=i+1；s=s+i；while(inext=0C. head-next=headD. head!=0正確答案：A8. 棧和隊列的共同特點是（）。A. 只允許在端點處插入和刪除元素B. 都是先進后出C. 都是先進先出D. 沒有共同點正確答案：A9. 對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為A. O（1）B. O（n）C. O（1og2n）D. O（n2)正確答案：C10. 設有一個10階的下三角矩陣A（包括對角線），按照從上到下、從左到右的順

3、序存儲到連續(xù)的55個存儲單元中，每個數(shù)組元素占1個字節(jié)的存儲空間，則A54地址與A00的地址之差為（）。A. 10B. 19C. 28D. 55正確答案：B11. 設某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（）A. BADCB. BCDAC. CDABD. CBDA正確答案：A12. 設在一棵度數(shù)為3的樹中，度數(shù)為3的結點數(shù)有2個，度數(shù)為2的結點數(shù)有1個，度數(shù)為1的結點數(shù)有2個，那么度數(shù)為0的結點數(shù)有（）個。A. 4B. 5C. 6D. 7正確答案：C13. 設指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為（）。A. top=to

4、p+1;B. top=top-1;C. top-next=top;D. top=top-next;正確答案：D14. 二叉排序樹中左子樹上所有結點的值均（）根結點的值。A. C. =D. !=正確答案：A15. 若目標串的長度為n，模式串的長度為n/3，則執(zhí)行模式匹配算法時，在最壞情況下的時間復雜度是（）A. O（1）B. O（n）C. O（n2)D. O（n3）正確答案：C16. 設順序線性表中有n個數(shù)據(jù)元素，則刪除表中第i個元素需要移動（）個元素。A. n-iB. n+l-iC. n-1-iD. i正確答案：A17. 設一棵三叉樹中有2個度數(shù)為1的結點，2個度數(shù)為2的結點，2個度數(shù)為3的結

5、點，則該三叉鏈權中有（）個度數(shù)為0的結點。A. 5B. 6C. 7D. 8正確答案：C18. 設一組初始記錄關鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關鍵字90需要比較的關鍵字個數(shù)為（）。A. 1B. 2C. 3D. 4正確答案：B19. 在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的（）A. 前一個位置B. 后一個位置C. 隊頭元素位置D. 隊尾元素的前一位置正確答案：A20. 用鏈接方式存儲的隊列，在進行插入運算時（）.A. 僅修改頭指針B. 頭、尾指針都要修改C. 僅修改尾指針D. 頭、尾指針可能都要修改正確答案：D21.

6、以下數(shù)據(jù)結構中哪一個是非線性結構？（）A. 隊列B. 棧C. 線性表D. 二叉樹正確答案：D22. 設無向圖G中的邊的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為（）。A. aedfcbB. acfebdC. aebcfdD. aedfbc正確答案：A23. 一趟排序結束后不一定能夠選出一個元素放在其最終位置上的是（）。A. 堆排序B. 冒泡排序C. 快速排序D. 希爾排序正確答案：D24. 設指針q指向單鏈表中結點A，指針p指向單鏈表中結點A的后繼結點B，指針s指向被插入的結點X，則在結點A

7、和結點B插入結點X的操作序列為（）。A. s-next=p-next；p-next=-s；B. q-next=s；s-next=p；C. p-next=s-next；s-next=p；D. p-next=s；s-next=q；正確答案：B25. 設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數(shù)分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數(shù)為（）。A. N1-1B. N2-1C. N2+N3D. N1+N3正確答案：A26. 若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進行二分查找，則查找A3的比較序列的下標依次為（）A

8、. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，3正確答案：D27. 二叉樹的第k層的結點數(shù)最多為（）.A. 2-1B. 2K+1C. 2K-1D. 2正確答案：D28. 設有6個結點的無向圖，該圖至少應有（）條邊才能確保是一個連通圖。A. 5B. 6C. 7D. 8正確答案：A29. 設有5000個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10個記錄關鍵字，則用下列（）方法可以達到此目的。A. 快速排序B. 堆排序C. 歸并排序D. 插入排序正確答案：B30. 設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。A. 6

9、B. 11C. 5D. 6.5正確答案：D 西安交通大學17年9月課程考試數(shù)據(jù)結構作業(yè)考核試題 二、判斷題（共 20 道試題，共 40 分。）1. 順序表查找指的是在順序存儲結構上進行查找。A. 錯誤B. 正確正確答案：A2. 完全二叉樹中的葉子結點只可能在最后兩層中出現(xiàn)。A. 錯誤B. 正確正確答案：B3. 不論線性表采用順序存儲結構還是鏈式存儲結構，刪除值為X的結點的時間復雜度均為O（n）。A. 錯誤B. 正確正確答案：B4. 設一棵樹T可以轉化成二叉樹BT，則二叉樹BT中一定沒有右子樹。A. 錯誤B. 正確正確答案：B5. 當向二叉排序樹中插入一個結點，則該結點一定成為葉子結點。A. 錯

10、誤B. 正確正確答案：B6. 有向圖的鄰接表和逆鄰接表中表結點的個數(shù)不一定相等。A. 錯誤B. 正確正確答案：A7. 中序遍歷一棵二叉排序樹可以得到一個有序的序列。A. 錯誤B. 正確正確答案：B8. 具有n個結點的完全二叉樹的高度為log2n+1。A. 錯誤B. 正確正確答案：A9. 由樹轉化成二叉樹，該二叉樹的右子樹一定為空。A. 錯誤B. 正確正確答案：B10. 線性表中的所有元素都有一個前驅元素和后繼元素。A. 錯誤B. 正確正確答案：A11. 堆是完全二叉樹，完全二叉樹不一定是堆。A. 錯誤B. 正確正確答案：B12. 對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。A. 錯誤B. 正確正確答案：B13. 如果兩個關鍵字的值不等但哈希函數(shù)值相等，則稱這兩個關鍵字為同義詞。A. 錯誤B. 正確正確答案：B14. 線性表中的所有元素都有一個前驅元素和后繼元素。A. 錯誤B. 正確正確答案：A15. 帶權無向圖的最小生成樹是唯一的。A. 錯誤B. 正確正確答案：A16. 快速排序是排序算法中平均性能最好的一種排序。A. 錯誤B. 正確正確答案：B17.