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

單項(xiàng)選擇題（每題2分，共10題）1.線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（）A.必須是連續(xù)的B.部分地址必須是連續(xù)的C.一定是不連續(xù)的D.連續(xù)與否均可以2.棧的特點(diǎn)是（）A.先進(jìn)先出B.先進(jìn)后出C.隨機(jī)進(jìn)出D.只進(jìn)不出3.一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是（）A.4，3，2，1B.1，2，3，4C.1，4，3，2D.3，2，4，14.具有n個(gè)頂點(diǎn)的無向完全圖有（）條邊A.n(n-1)/2B.n(n-1)C.n(n+1)/2D.n(n+1)5.對(duì)一組數(shù)據(jù)(84,47,25,15,21)排序，數(shù)據(jù)的排列次序在排序的過程中的變化為：(1)8447251521(2)1547258421(3)1521258447(4)1521254784，則采用的排序方法是（）A.選擇排序B.冒泡排序C.插入排序D.快速排序6.順序查找適合于存儲(chǔ)結(jié)構(gòu)為（）的線性表A.順序存儲(chǔ)B.鏈?zhǔn)酱鎯?chǔ)C.順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)D.索引存儲(chǔ)7.樹最適合用來表示（）A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)8.哈希表的平均查找長(zhǎng)度（）A.與處理沖突方法有關(guān)而與表的長(zhǎng)度無關(guān)B.與處理沖突方法無關(guān)而與表的長(zhǎng)度有關(guān)C.與處理沖突方法有關(guān)且與表的長(zhǎng)度有關(guān)D.與處理沖突方法無關(guān)且與表的長(zhǎng)度無關(guān)9.在一個(gè)單鏈表中，若要?jiǎng)h除p結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行（）A.p->next=p->next->next;B.p=p->next;p->next=p->next->next;C.free(p->next);D.p=p->next->next;10.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（）結(jié)構(gòu)A.存儲(chǔ)B.物理C.邏輯D.物理和存儲(chǔ)多項(xiàng)選擇題（每題2分，共10題）1.以下屬于線性結(jié)構(gòu)的有（）A.棧B.隊(duì)列C.樹D.圖2.關(guān)于順序存儲(chǔ)結(jié)構(gòu)，正確的是（）A.存儲(chǔ)密度大B.邏輯上相鄰的元素物理上也相鄰C.插入、刪除操作效率高D.可以隨機(jī)存取3.下列排序算法中，平均時(shí)間復(fù)雜度為O(n^2)的有（）A.冒泡排序B.選擇排序C.插入排序D.快速排序4.以下關(guān)于棧的說法正確的是（）A.棧頂元素最先被刪除B.棧底元素最后被刪除C.可以在棧頂插入元素D.可以在棧底刪除元素5.圖的遍歷方式有（）A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.先序遍歷D.后序遍歷6.樹的存儲(chǔ)結(jié)構(gòu)有（）A.雙親表示法B.孩子表示法C.孩子兄弟表示法D.順序存儲(chǔ)法7.哈希函數(shù)的構(gòu)造方法有（）A.直接定址法B.數(shù)字分析法C.平方取中法D.折疊法8.以下哪些是隊(duì)列的基本操作（）A.入隊(duì)B.出隊(duì)C.取隊(duì)頭元素D.取隊(duì)尾元素9.以下關(guān)于鏈表的說法正確的是（）A.單鏈表每個(gè)結(jié)點(diǎn)只有一個(gè)指針域B.雙鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域C.循環(huán)鏈表最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)D.鏈表不適合隨機(jī)訪問10.下列屬于查找算法的有（）A.順序查找B.折半查找C.哈希查找D.冒泡查找判斷題（每題2分，共10題）1.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）2.棧和隊(duì)列都是特殊的線性表。（）3.二叉樹中每個(gè)結(jié)點(diǎn)的度都為2。（）4.圖的鄰接矩陣表示法只適用于有向圖。（）5.快速排序是一種穩(wěn)定的排序算法。（）6.順序查找的時(shí)間復(fù)雜度為O(n)。（）7.樹的后序遍歷和二叉樹的后序遍歷含義相同。（）8.哈希表中沖突是不可避免的。（）9.雙鏈表從任何一個(gè)結(jié)點(diǎn)出發(fā)都能訪問到所有結(jié)點(diǎn)。（）10.選擇排序在最好情況下的時(shí)間復(fù)雜度為O(n)。（）簡(jiǎn)答題（每題5分，共4題）1.簡(jiǎn)述棧和隊(duì)列的區(qū)別。-棧是先進(jìn)后出，元素的插入和刪除都在棧頂進(jìn)行。-隊(duì)列是先進(jìn)先出，元素在隊(duì)尾入隊(duì)，在隊(duì)頭出隊(duì)。2.簡(jiǎn)述二叉樹的前序遍歷過程。-先訪問根結(jié)點(diǎn)。-再遞歸前序遍歷左子樹。-最后遞歸前序遍歷右子樹。3.簡(jiǎn)述哈希表的基本思想。-根據(jù)關(guān)鍵碼值，通過一個(gè)哈希函數(shù)計(jì)算出一個(gè)哈希地址。-把數(shù)據(jù)存儲(chǔ)到該地址對(duì)應(yīng)的位置。-當(dāng)發(fā)生沖突時(shí)，采用一定方法解決。4.簡(jiǎn)述折半查找的適用條件。-適用于順序存儲(chǔ)的有序表。-每次將查找區(qū)間縮小一半，直到找到目標(biāo)元素或確定不存在。討論題（每題5分，共4題）1.討論不同排序算法在實(shí)際應(yīng)用中的選擇依據(jù)。-數(shù)據(jù)量小且接近有序時(shí)，可選用插入排序。-數(shù)據(jù)量較大時(shí)，快速排序平均性能好。-對(duì)穩(wěn)定性有要求，可考慮歸并排序等。-還要考慮空間復(fù)雜度、時(shí)間復(fù)雜度等因素。2.分析線性表順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)在不同場(chǎng)景下的優(yōu)缺點(diǎn)。-順序存儲(chǔ)：優(yōu)點(diǎn)是存儲(chǔ)密度大、可隨機(jī)存?。蝗秉c(diǎn)是插入刪除效率低、大小固定。適用于數(shù)據(jù)變動(dòng)少、頻繁隨機(jī)訪問的場(chǎng)景。-鏈?zhǔn)酱鎯?chǔ)：優(yōu)點(diǎn)是插入刪除效率高、大小動(dòng)態(tài)變化；缺點(diǎn)是存儲(chǔ)密度小、不能隨機(jī)訪問。適用于數(shù)據(jù)頻繁變動(dòng)的場(chǎng)景。3.談?wù)剤D的兩種遍歷方式（深度優(yōu)先和廣度優(yōu)先）的應(yīng)用場(chǎng)景。-深度優(yōu)先遍歷適合探索連通分量、尋找路徑等。如在迷宮探索中找一條到終點(diǎn)的路徑。-廣度優(yōu)先遍歷常用于求最短路徑、分層結(jié)構(gòu)等。如在社交網(wǎng)絡(luò)中找最短社交距離。4.如何提高哈希表的查找效率？-選擇好的哈希函數(shù)，使數(shù)據(jù)均勻分布。-采用合適的沖突解決方法，如鏈地址法、開放定址法。-控制哈希表的負(fù)載因子，適時(shí)進(jìn)行擴(kuò)容。答案單項(xiàng)選擇題1.D2.B3.B4.A5.A6.C7.C8.C9.A10.C多項(xiàng)選擇題1.