西安交通大學(xué)17年9月課程考試《數(shù)據(jù)結(jié)構(gòu)》作業(yè)考核試題

1、西安交通大學(xué)17年9月課程考試數(shù)據(jù)結(jié)構(gòu)作業(yè)考核試題 1-5: B A D A D一、單選題（共 30 道試題，共 60 分。）1. （）二叉排序樹可以得到一個(gè)從小到大的有序序列。A. 先序遍歷B. 中序遍歷C. 后序遍歷D. 層次遍歷正確答案：B2. 下列程序段的時(shí)間復(fù)雜度為（）。i=0，s=0；while(sn)s=s+i；i+；A. O(n)B. O(n)C. O(n)D. O(n)正確答案：A3. 設(shè)數(shù)組datam作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行出隊(duì)操作后其頭指針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. 棧和隊(duì)列的共同特點(diǎn)是（）。A. 只允許在端點(diǎn)處插入和刪除元素B. 都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒有共同點(diǎn)正確答案：A9. 對(duì)n個(gè)記錄的文件進(jìn)行快速排序，所需要的輔助存儲(chǔ)空間大致為A. O（1）B. O（n）C. O（1og2n）D. O（n2)正確答案：C10. 設(shè)有一個(gè)10階的下三角矩陣A（包括對(duì)角線），按照從上到下、從左到右的順

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

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

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

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

7、和結(jié)點(diǎn)B插入結(jié)點(diǎn)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. 設(shè)F是由T1、T2和T3三棵樹組成的森林，與F對(duì)應(yīng)的二叉樹為B，T1、T2和T3的結(jié)點(diǎn)數(shù)分別為N1、N2和N3，則二叉樹B的根結(jié)點(diǎn)的左子樹的結(jié)點(diǎn)數(shù)為（）。A. N1-1B. N2-1C. N2+N3D. N1+N3正確答案：A26. 若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為（）A

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

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

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