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

一、單項選擇題（每題2分，共20分）1.線性表采用鏈式存儲時，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以答案：D2.棧和隊列的共同點是（）A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點答案：C3.一個棧的入棧序列是a,b,c,d,e，則棧的不可能的輸出序列是（）A.edcbaB.decbaC.dceabD.abcde答案：C4.樹最適合用來表示（）A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)答案：C5.具有10個葉子結(jié)點的二叉樹中有（）個度為2的結(jié)點。A.8B.9C.10D.11答案：B6.對n個記錄的文件進行快速排序，所需要的輔助存儲空間大致為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)答案：C7.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A.1B.2C.3D.4答案：B8.順序查找法適合于存儲結(jié)構(gòu)為（）的線性表。A.散列存儲B.順序存儲或鏈式存儲C.壓縮存儲D.索引存儲答案：B9.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（）A.(n-1)/2B.n/2C.(n+1)/2D.n答案：C10.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)。A.存儲B.物理C.邏輯D.物理和存儲答案：C二、多項選擇題（每題2分，共20分）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊列C.樹D.圖答案：AB2.關(guān)于棧的描述，正確的有（）A.先進后出B.后進先出C.可以在棧頂插入元素D.可以在棧底刪除元素答案：ABC3.以下哪些是隊列的基本操作（）A.入隊B.出隊C.取隊頭元素D.取隊尾元素答案：ABC4.二叉樹的遍歷方式有（）A.前序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ABCD5.圖的存儲結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表答案：ABCD6.排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.選擇排序C.插入排序D.歸并排序答案：ACD7.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.數(shù)字分析法C.平方取中法D.折疊法答案：ABCD8.以下關(guān)于線性表的描述正確的有（）A.順序存儲的線性表可以隨機訪問B.鏈式存儲的線性表插入和刪除操作效率高C.線性表中元素可以是不同類型D.線性表是一種線性結(jié)構(gòu)答案：ABD9.樹的遍歷方式包括（）A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷答案：ACD10.以下哪些算法的時間復雜度為O(n^2)（）A.冒泡排序B.選擇排序C.插入排序D.快速排序答案：ABC三、判斷題（每題2分，共20分）1.線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)。（）答案：×2.棧和隊列都是特殊的線性表。（）答案：√3.完全二叉樹一定是滿二叉樹。（）答案：×4.圖的深度優(yōu)先搜索遍歷類似于樹的前序遍歷。（）答案：√5.快速排序是一種穩(wěn)定的排序算法。（）答案：×6.哈希表是一種基于查找的存儲結(jié)構(gòu)。（）答案：√7.順序查找適合于有序表和無序表。（）答案：√8.二叉排序樹的中序遍歷序列是一個有序序列。（）答案：√9.堆排序是一種選擇排序。（）答案：√10.數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)無關(guān)。（）答案：√四、簡答題（每題5分，共20分）1.簡述棧和隊列的主要區(qū)別。答案：棧是先進后出，元素只能在棧頂進行插入和刪除操作；隊列是先進先出，元素在隊尾入隊，在隊頭出隊。二者操作規(guī)則不同。2.簡述二叉樹的性質(zhì)。答案：性質(zhì)有：在二叉樹的第i層上至多有2^(i-1)個結(jié)點；深度為k的二叉樹至多有2^k-1個結(jié)點；對任何一棵二叉樹，度為0的結(jié)點比度為2的結(jié)點多1個。3.簡述哈希表查找的基本思想。答案：哈希表查找先通過哈希函數(shù)將關(guān)鍵字映射到哈希表的地址，若該地址為空則查找失敗，若不為空且關(guān)鍵字匹配則查找成功，若不匹配則按解決沖突的方法繼續(xù)查找。4.簡述插入排序的基本步驟。答案：將待排序數(shù)據(jù)分為已排序和未排序兩部分。初始時已排序部分只有第一個元素。然后從未排序部分依次取出元素，插入到已排序部分的合適位置，直到所有元素都插入完成。五、討論題（每題5分，共20分）1.討論線性表順序存儲和鏈式存儲在不同應(yīng)用場景下的優(yōu)缺點。答案：順序存儲優(yōu)點是可隨機訪問，存儲密度高；缺點是插入刪除操作效率低，需要連續(xù)存儲空間。鏈式存儲優(yōu)點是插入刪除操作方便，無需連續(xù)空間；缺點是不能隨機訪問，存儲密度低。應(yīng)用中頻繁隨機訪問選順序存儲，頻繁插入刪除選鏈式存儲。2.討論圖的不同遍歷方式（深度優(yōu)先和廣度優(yōu)先）的適用場景。答案：深度優(yōu)先遍歷適合探索一條路徑到底的場景，如尋找連通分量、判斷圖是否有環(huán)等；廣度優(yōu)先遍歷適合尋找最短路徑、層次關(guān)系等場景，因為它是按層次依次訪問頂點。3.討論排序算法在實際應(yīng)用中的選擇策略。答案：數(shù)據(jù)量小且基本有序時，可選用插入排序；數(shù)據(jù)量小但無序，選擇排序簡單；數(shù)據(jù)量大會優(yōu)先考慮快速排序、歸并排序等高效算法；對穩(wěn)定性有要求則