數(shù)據(jù)結構試題及答案

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