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

單項選擇題（每題2分，共10題）1.線性表采用鏈?zhǔn)酱鎯r，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以2.棧和隊列的共同特點是（）A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素D.沒有共同點3.若某棧的輸入序列為1，2，3，…，n，輸出序列的第一個元素為n，則第i個輸出元素為（）A.n-i+1B.n-iC.iD.哪個元素?zé)o所謂4.一個隊列的入隊序列是1，2，3，4，則隊列的輸出序列是（）A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，15.樹最適合用來表示（）A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)6.具有10個葉結(jié)點的二叉樹中有（）個度為2的結(jié)點。A.8B.9C.10D.117.對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間大致為（）A.O（1）B.O（n）C.O（logn）D.O（n^2）8.哈希表的平均查找長度（）A.與處理沖突方法有關(guān)而與表的長度無關(guān)B.與處理沖突方法無關(guān)而與表的長度有關(guān)C.與處理沖突方法有關(guān)且與表的長度有關(guān)D.與處理沖突方法無關(guān)且與表的長度無關(guān)9.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為（）A.（n-1）/2B.n/2C.（n+1）/2D.n10.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（）倍。A.1B.2C.3D.4答案：1.D2.C3.A4.B5.C6.B7.C8.C9.C10.B多項選擇題（每題2分，共10題）1.以下屬于線性數(shù)據(jù)結(jié)構(gòu)的有（）A.棧B.隊列C.鏈表D.樹2.關(guān)于棧的描述，正確的是（）A.先進(jìn)后出B.后進(jìn)先出C.可以在棧頂插入元素D.可以在棧底刪除元素3.隊列的基本操作有（）A.入隊B.出隊C.取隊頭元素D.取隊尾元素4.以下關(guān)于二叉樹的說法正確的是（）A.二叉樹的每個結(jié)點最多有兩個子結(jié)點B.二叉樹可以為空C.二叉樹的度可以為1D.滿二叉樹是完全二叉樹5.圖的存儲結(jié)構(gòu)有（）A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表6.排序算法中，穩(wěn)定的排序算法有（）A.冒泡排序B.插入排序C.歸并排序D.快速排序7.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.除留余數(shù)法C.平方取中法D.折疊法8.查找算法中，平均查找長度與數(shù)據(jù)元素個數(shù)n有關(guān)的有（）A.順序查找B.折半查找C.哈希查找D.二叉排序樹查找9.以下關(guān)于樹和森林的說法正確的是（）A.一棵樹可以看作是一個特殊的森林B.森林可以轉(zhuǎn)換為二叉樹C.樹的后根遍歷序列與其轉(zhuǎn)換的二叉樹的中序遍歷序列相同D.森林的先序遍歷序列與其轉(zhuǎn)換的二叉樹的先序遍歷序列相同10.以下哪些操作可以在鏈表中實現(xiàn)（）A.插入元素B.刪除元素C.查找元素D.按序號訪問元素答案：1.ABC2.ABC3.ABC4.ABCD5.ABCD6.ABC7.ABCD8.ABD9.ABCD10.ABC判斷題（每題2分，共10題）1.線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更節(jié)省存儲空間。（）2.棧和隊列都是限制在一端進(jìn)行操作的線性表。（）3.二叉樹中每個結(jié)點的度不能超過2，所以二叉樹是一種特殊的樹。（）4.完全二叉樹一定是滿二叉樹。（）5.圖的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷都需要借助隊列來實現(xiàn)。（）6.快速排序在任何情況下的時間復(fù)雜度都是O(nlogn)。（）7.哈希表的查找效率主要取決于哈希函數(shù)和處理沖突的方法。（）8.在有序表中進(jìn)行折半查找，其平均查找長度為O(logn)。（）9.樹的先根遍歷序列和后根遍歷序列可以唯一確定一棵樹。（）10.鏈表不適合隨機(jī)訪問，但插入和刪除操作效率較高。（）答案：1.×2.×3.×4.×5.×6.×7.√8.√9.√10.√簡答題（每題5分，共4題）1.簡述棧和隊列的區(qū)別。答案：棧是先進(jìn)后出，操作在棧頂進(jìn)行；隊列是先進(jìn)先出，入隊在隊尾，出隊在隊頭。二者操作規(guī)則和數(shù)據(jù)進(jìn)出順序不同。2.簡述二叉樹的前序、中序、后序遍歷的遞歸算法思想。答案：前序遍歷：先訪問根結(jié)點，再遞歸遍歷左子樹和右子樹；中序遍歷：先遞歸遍歷左子樹，再訪問根結(jié)點，最后遞歸遍歷右子樹；后序遍歷：先遞歸遍歷左、右子樹，最后訪問根結(jié)點。3.簡述選擇排序的基本思想。答案：在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。然后，再從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。4.簡述哈希表的基本原理。答案：哈希表通過哈希函數(shù)將關(guān)鍵字映射到一個有限的地址空間中。當(dāng)要存儲或查找數(shù)據(jù)時，先通過哈希函數(shù)計算關(guān)鍵字對應(yīng)的地址，若該地址有沖突，則采用特定方法處理沖突來確定最終存儲或查找位置。討論題（每題5分，共4題）1.在實際應(yīng)用中，如何選擇合適的數(shù)據(jù)結(jié)構(gòu)？答案：需考慮數(shù)據(jù)操作特點，如頻繁插入刪除選鏈表；頻繁隨機(jī)訪問選順序表。還要看數(shù)據(jù)元素關(guān)系，層次關(guān)系用樹，網(wǎng)狀關(guān)系用圖。此外，存儲規(guī)模、效率要求等也是影響因素。2.分析快速排序在不同數(shù)據(jù)分布下的性能表現(xiàn)。答案：數(shù)據(jù)隨機(jī)分布時，快速排序平均性能最優(yōu)，時間復(fù)雜度O(nlogn)。若數(shù)據(jù)基本有序或逆序，性能最差，時間復(fù)雜度會退化到O(n^2)，因為劃分極度不均衡。3.討論哈希沖突的處理方法及其優(yōu)缺點。答案：開放定址法簡單直接，但易出現(xiàn)堆積現(xiàn)象；鏈地址法解決沖突靈