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

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