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

經(jīng)典word整理文檔，僅參考，雙擊此處可刪除頁眉頁腳。本資料屬于網(wǎng)絡(luò)整理，如有侵權(quán)，請聯(lián)系刪除，謝謝！1.描述一個求解問題的抽象數(shù)據(jù)類型由？兩部分組成。[填空題]*_________________________________答案：數(shù)據(jù)邏輯結(jié)構(gòu)和抽象運(yùn)算)2.算法具有？5個重要特征[填空題]*_________________________________答案：有窮性、確定性、可行性、輸入和輸出)3.一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的？稱為存儲結(jié)構(gòu)[填空題]*_________________________________答案：映像)4.通常從四個方面評價算法的質(zhì)量？[填空題]*_________________________________答案：正確性、易讀性、強(qiáng)壯性、高效率正確易讀,強(qiáng)壯高效))5.算法的時間復(fù)雜度取決于？[填空題]*_________________________________答案：問題的規(guī)模和待處理數(shù)據(jù)的初態(tài))6.在分析算法的時間復(fù)雜度時，通常認(rèn)為算法的執(zhí)行時間是？的函數(shù)[填空題]*_________________________________答案：問題規(guī)模)7.數(shù)據(jù)結(jié)構(gòu)是一門研究程序設(shè)計中數(shù)據(jù)的元素以及他們之間的？等的學(xué)科[填空題]*_________________________________答案：關(guān)系和運(yùn)算)8.算法分析的主要任務(wù)之一是？[填空題]*_________________________________答案：算法的執(zhí)行時間和問題規(guī)模之間的關(guān)系)9.算法分析的目的是？[填空題]*_________________________________答案：分析算法的效率以求改進(jìn))15.單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是？[填空題]*_________________________________答案：n、2n-1)_________________________________答案：(n+1)/2)動元素的次數(shù)是？25.鏈隊，在進(jìn)行插入或刪除運(yùn)算時？[]*_________________________________答案：頭、尾指針可能都要修改)26.共享棧，當(dāng)？時才產(chǎn)生上溢[填空題]*_________________________________答案：兩個棧的棧頂在?？臻g的某一位置相遇)27.若某堆棧的輸入序列是1，2，3，…，n，輸出序列的第一個元素為n，則第i個輸出元素為？[]*_________________________________答案：n-i+1)28.如果用單鏈表表示鏈?zhǔn)綏＃瑒t棧頂一般設(shè)在鏈表的？[填空題]*_________________________________答案：鏈頭)29.鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是？[填空題]*_________________________________答案：不會出現(xiàn)空間浪費(fèi)問題)30.適合用作鏈隊的鏈表是：_________最不適合用作鏈隊的鏈表是：_________最不適合用作鏈棧的鏈表是：_________[]*空1答案：帶隊首指針和隊尾指針的非循環(huán)單鏈表空2答案：只帶隊首指針的非循環(huán)雙鏈表空3答案：只有表頭指針沒有表尾指針的循環(huán)單鏈表31.共享棧的好處是？填空題]*_________________________________答案：節(jié)省存儲空間,降低上溢出發(fā)生的幾率)32.串的長度是指？[]*_________________________________答案：串中所含字符的個數(shù))33.含n個不同字符的串的子串個數(shù)為？[]*_________________________________答案：n(n+1)/2+1)34.在串匹配中一般將主串稱為：_________將子串稱為：_________[填空題]*空1答案：目標(biāo)串35.兩個字符串相等的充要條件是[填空題]*36.串是一種特殊的線性表，其特殊性體現(xiàn)在[填空題]*_________________________________答案：模式匹配)空2答案：j=0空1答案：i不變44.一維數(shù)組ai的存儲地址公式：[填空題]*45.特殊矩陣包括[]*46.上三角矩陣公式[]*_________________________________答案：請設(shè)置答案)49.對角矩陣公式[]*空1答案：節(jié)省存儲空間空2答案：隨機(jī)存取特性空1答案：三元組和十字鏈表空2答案：順序存儲結(jié)構(gòu)空3答案：鏈?zhǔn)酱鎯Y(jié)構(gòu)52.廣義表中的數(shù)據(jù)元素是有相對次序的[]*對正確答案)錯53.廣義表可以共享[]*對正確答案)錯54.將一個n階下（上）三角矩陣采用壓縮存儲，共存儲[填空題]*_________________________________答案：n(n+1)/2+1)55.矩陣a[m][n]和矩陣b[n][p]相乘，其時間復(fù)雜度為[填空題]*_________________________________答案：O(mnp))56.對稀疏矩陣采用壓縮存儲的缺點(diǎn)之一是無法根據(jù)行、列號直接計算矩陣元素的存儲地址[判斷題]*對正確答案)錯57.稀疏矩陣用十字鏈表表示優(yōu)點(diǎn)在于便于實(shí)現(xiàn)增加或減少矩陣中非零元素的操作[判斷題]*對正確答案)錯58.對于含有n個結(jié)點(diǎn)的樹（或者二叉樹），無論度為多少，其分支數(shù)或所有結(jié)點(diǎn)度之和均為[填空題]*_________________________________答案：n-1)59.樹的存儲結(jié)構(gòu)主要有[填空題]*空1答案：1空2答案：請設(shè)置答案空3答案：請設(shè)置答案結(jié)點(diǎn)[填空題]*空1答案：n+1/2空2答案：n-1/263.70.先序和中序相同的條件是二叉樹中[]*對正確答案)錯_________________________________答案：后序遍歷)76.對正確答案)對正確答案)對正確答案)錯80.順序存儲結(jié)構(gòu)下的數(shù)據(jù)元素為層次遍歷結(jié)果[判斷題]*對正確答案)錯81.完全有向圖的鄰接矩陣是對稱的[判斷題]*對正確答案)錯82.深度優(yōu)先遍歷可以找到所有路徑，而廣度優(yōu)先遍歷可以找到最短路徑[判斷題]*對正確答案)錯83.如果一個有向圖的拓?fù)湫蛄惺俏ㄒ坏?，則圖中必定[填空題]*_________________________________答案：僅有一個頂點(diǎn)的入度為0,一個頂點(diǎn)的出度為0)84.一個AOE網(wǎng)中至少有一條關(guān)鍵路徑，且是從源點(diǎn)到匯點(diǎn)的路徑中最長的一條[判斷題]*對正確答案)錯85.一個AOE網(wǎng)的關(guān)鍵路徑不一定是唯一的，但其關(guān)鍵路徑長度一定是唯一的[判斷題]*對正確答案)錯86.n個結(jié)點(diǎn)完全無向圖的邊數(shù)為：_________，n個結(jié)點(diǎn)完全有向圖的邊數(shù)為_________[填空題]*空1答案：n(n-1)/2空2答案：n(n-1)87.對于鄰接矩陣而言：無向圖的邊數(shù)矩陣中1元素個數(shù)的和/2，有向圖的邊數(shù)=矩陣中1元素個數(shù)的和[判斷題]*對正確答案)錯88.對于鄰接表而言：無向圖的邊數(shù)邊結(jié)點(diǎn)個數(shù)的和/2，有向圖的邊數(shù)邊結(jié)點(diǎn)個數(shù)的和[判斷題]*對正確答案)錯89.設(shè)圖G是一個含有n個頂點(diǎn)的連通圖，其中任意一條簡單路徑的長度不會超過[填空題]*_________________________________答案：n-1)90.設(shè)某無向圖中有n個頂點(diǎn)e條邊，則建立該圖鄰接矩陣的時間復(fù)雜度為：_________，建立該圖鄰接表的時間復(fù)雜度為：_________[填空題]*空1答案：O(n2)空2答案：O(n+e)91.設(shè)無向圖G中有n個頂點(diǎn)，則該無向圖中每個頂點(diǎn)的度數(shù)最多是[填空題]*_________________________________答案：n-1)對正確答案)對正確答案)錯101.任何一個含兩個或以上頂點(diǎn)的帶權(quán)無向圖有？最小生成樹[]*_________________________________答案：一顆或多顆)102.一個連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的[填空題]*_________________________________答案：極小連通子圖)103.在用Prim和Kruskal算法構(gòu)造最小生成樹時，前者更適合于稠密圖，后者更適合于稀疏圖[判斷題]*對正確答案)錯104.Dijkstra算法的時間復(fù)雜度為[填空題]*_________________________________答案：O(n2))105.Dijkstra算法是按？的順序方法求出圖中從某頂點(diǎn)到其余頂點(diǎn)的最短路徑[填空題]*_________________________________答案：長度遞增)106.Dijkstra算法從源點(diǎn)到其余各頂點(diǎn)的最短路徑的路徑長度按遞增次序依次產(chǎn)生，該算法在邊上的權(quán)出現(xiàn)負(fù)值情況時不能正確產(chǎn)生最短路徑。[]*對正確答案)錯107.在有n個頂點(diǎn)的有向圖中，每個頂點(diǎn)的度最大可達(dá)[填空題]*_________________________________答案：2(n-1))108.一個含有n個頂點(diǎn)的有向圖僅有唯一的拓?fù)湫蛄校瑒t該圖的邊數(shù)為[填空題]*_________________________________答案：n-1)109.一個有n個頂點(diǎn)、e條邊的連通圖采用鄰接表表示，從某個頂點(diǎn)v出發(fā)進(jìn)行，則最大的遞歸深度是[填空題]*_________________________________答案：n)110.一個有n個頂點(diǎn)、e條邊的連通圖采用鄰接表表示，從某個頂點(diǎn)v出發(fā)進(jìn)行，則隊列中最多的頂點(diǎn)個數(shù)是[填空題]*_________________________________答案：n-1)111.DFS時間復(fù)雜度為[填空題]*_________________________________答案：O(n2))112.拓?fù)渑判虻臅r間復(fù)雜度是[填空題]*_________________________________答案：O(n+e))113.如果圖G存在拓?fù)渑判蛐蛄校瑒tG必為[填空題]*_________________________________答案：有向無環(huán)圖)114.若含有n個頂點(diǎn)的無向圖恰好形成一個環(huán)，則它有n棵生成樹判斷題]*對正確答案)錯115.用鄰接矩陣表示有n個頂點(diǎn)和e條邊的無向圖，矩陣中零元素的個數(shù)為：_________,采用壓縮方式存儲矩陣中零元素的個數(shù)為。：_________填空題]*空1答案：n*n-2e空2答案：n(n+1)/2-e116.對箱排序的改進(jìn)和推廣的算法是[填空題]*_________________________________答案：基數(shù)排序)對正確答案)對正確答案)空2答案：O(log2n)120.對正確答案)錯123.二叉排序樹的中序序列是一個遞增有序序列[判斷題]*對正確答案)錯124.給定結(jié)點(diǎn)個數(shù)的平衡二叉樹的高度不一定是唯一的[判斷題]*對正確答案)錯125.設(shè)計哈希表主要是設(shè)計哈希函數(shù)和哈希沖突解決方法[判斷題]*對正確答案)錯126.同義詞是指兩個不同關(guān)鍵字的元素，其哈希函數(shù)值相同，這種沖突稱為同義詞沖突[判斷題]*對正確答案)錯127.非同義詞沖突是指哈希函數(shù)值不相同的兩個元素爭奪同一個后繼哈希地址，導(dǎo)致出現(xiàn)堆積或聚集現(xiàn)象[判斷題]*對正確答案)錯128.在采用線性探測法處理沖突的哈希表中，所有同義詞在表中不一定相鄰[判斷題]*對正確答案)錯129.評價哈希函數(shù)好壞的標(biāo)準(zhǔn)是[填空題]*_________________________________答案：哈希函數(shù)的取值是否均勻)130.在哈希存儲中，裝填因子的值越大，則存取元素時發(fā)生沖突的可能性就越大。值越小，存取元素時發(fā)生沖突的可能性就越小[判斷題]*對正確答案)錯131.為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是[]*_________________________________答案：構(gòu)造一個好的HASH函數(shù)和確定解決沖突的方法)132.假設(shè)m個關(guān)鍵字互為同義詞，若用線性探測法把這m個關(guān)鍵字存入散列表中，至少要進(jìn)行的探查次數(shù)是[填空題]*_________________________________答案：m(m+1)/2)133.設(shè)二叉排序樹中有n個結(jié)點(diǎn)，則在二叉排序樹上查找或插入結(jié)點(diǎn)的平均時間復(fù)雜度為[填空題]*_________________________________答案：O(log2n))134.在最壞情況下，利用插入操作構(gòu)造一顆二叉排序樹花費(fèi)的代價為[填空題]*_________________________________答案：O())135.當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)無序，但塊間必須有序，每塊內(nèi)最大或最小的數(shù)據(jù)組成索