數(shù)據(jù)結(jié)構(gòu)自考試題及答案

單項(xiàng)選擇題（每題2分，共10題）1.棧的邏輯結(jié)構(gòu)特點(diǎn)是？A.先進(jìn)先出B.后進(jìn)先出C.隨機(jī)訪問D.順序存儲2.適合實(shí)現(xiàn)“先進(jìn)先出”的結(jié)構(gòu)是？A.棧B.隊(duì)列C.二叉樹D.圖3.二叉樹中葉子節(jié)點(diǎn)數(shù)n0與度為2的節(jié)點(diǎn)數(shù)n2的關(guān)系是？A.n0=n2B.n0=n2+1C.n0=n2-1D.無固定關(guān)系4.冒泡排序的平均時間復(fù)雜度是？A.O(n)B.O(nlogn)C.O(n2)D.O(logn)5.以下排序中不穩(wěn)定的是？A.冒泡排序B.插入排序C.快速排序D.歸并排序6.n個頂點(diǎn)的圖鄰接矩陣大小是？A.n×nB.n×(n-1)C.(n-1)×(n-1)D.不確定7.哈希表查找的平均時間復(fù)雜度是？A.O(1)B.O(logn)C.O(n)D.O(n2)8.二叉樹中序遍歷順序是？A.根→左→右B.左→根→右C.左→右→根D.根→右→左9.鏈表插入（找到位置后）的時間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(n2)10.堆排序的空間復(fù)雜度是？A.O(1)B.O(n)C.O(logn)D.O(nlogn)單選答案：1.B2.B3.B4.C5.C6.A7.A8.B9.A10.A多項(xiàng)選擇題（每題2分，共10題）1.線性表的存儲結(jié)構(gòu)包括？A.順序表B.單鏈表C.雙鏈表D.哈希表2.棧的常見應(yīng)用有？A.表達(dá)式求值B.遞歸調(diào)用C.括號匹配D.層次遍歷3.二叉樹的遍歷方式有？A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷4.時間復(fù)雜度為O(nlogn)的排序是？A.快速排序B.歸并排序C.堆排序D.冒泡排序5.圖的遍歷方法有？A.DFSB.BFSC.前序遍歷D.后序遍歷6.動態(tài)查找算法包括？A.順序查找B.二叉查找樹查找C.哈希查找D.折半查找7.樹的基本術(shù)語有？A.根節(jié)點(diǎn)B.葉子節(jié)點(diǎn)C.子樹D.路徑8.哈希表沖突解決方法有？A.開放地址法B.鏈地址法C.再哈希法D.公共溢出區(qū)9.隊(duì)列的常見應(yīng)用有？A.打印隊(duì)列B.BFSC.遞歸調(diào)用D.表達(dá)式求值10.非線性結(jié)構(gòu)包括？A.樹B.圖C.棧D.隊(duì)列多選答案：1.ABC2.ABC3.ABCD4.ABC5.AB6.BC7.ABCD8.ABCD9.AB10.AB判斷題（每題2分，共10題）1.棧是先進(jìn)先出的線性結(jié)構(gòu)。A.正確B.錯誤2.二叉樹葉子節(jié)點(diǎn)數(shù)=度為2的節(jié)點(diǎn)數(shù)+1。A.正確B.錯誤3.冒泡排序是穩(wěn)定排序。A.正確B.錯誤4.隊(duì)列只能用順序存儲實(shí)現(xiàn)。A.正確B.錯誤5.圖的鄰接矩陣一定對稱。A.正確B.錯誤6.二叉查找樹中序遍歷是有序序列。A.正確B.錯誤7.堆排序是不穩(wěn)定排序。A.正確B.錯誤8.鏈表插入無需移動元素。A.正確B.錯誤9.哈希表查找平均時間O(1)。A.正確B.錯誤10.樹的高度是根到最深葉子的路徑長度。A.正確B.錯誤判斷答案：1.B2.A3.A4.B5.B6.A7.A8.A9.A10.A簡答題（總4題，每題5分）1.簡述棧和隊(duì)列的區(qū)別。答案：棧是后進(jìn)先出，僅在棧頂操作；隊(duì)列是先進(jìn)先出，隊(duì)頭刪、隊(duì)尾插。應(yīng)用：棧用于遞歸、括號匹配；隊(duì)列用于層次遍歷、打印隊(duì)列。2.二叉樹的三種基本遍歷是什么？答案：前序（根→左→右）、中序（左→根→右）、后序（左→右→根）。按順序訪問所有節(jié)點(diǎn)一次，是二叉樹操作的基礎(chǔ)。3.冒泡排序的基本思想？答案：重復(fù)遍歷序列，比較相鄰元素，逆序則交換，直到無逆序。每趟將最大元素“冒泡”到末尾，共需n-1趟（n為元素數(shù)）。4.哈希表沖突解決方法有哪些？答案：①開放地址法（線性/二次探測）；②鏈地址法（節(jié)點(diǎn)存鏈表）；③再哈希法（換哈希函數(shù)）；④公共溢出區(qū)（單獨(dú)存沖突元素）。討論題（總4題，每題5分）1.比較順序表和鏈表的優(yōu)缺點(diǎn)。答案：順序表：隨機(jī)訪問快（O(1)），但插入/刪除需移動元素（O(n)），空間連續(xù)易浪費(fèi)；鏈表：插入/刪除無需移動（O(1)），空間動態(tài)分配，隨機(jī)訪問慢（O(n)）。2.快速排序和歸并排序的異同？答案：同：均為O(nlogn)，分治思想；異：快排原地排序（O(1)空間）、不穩(wěn)定；歸并需額外空間（O(n)）、穩(wěn)定；快排依賴pivot，歸并依賴合并。3.BST和AVL樹的區(qū)別？答案：BST：左≤根≤右，無平衡要求，最壞退化為鏈表（O(n)查找）；AVL：是BST，左右子樹高度差≤1，節(jié)點(diǎn)設(shè)平衡因子，操作均