數(shù)據結構綜合習題集含答案

1、數(shù)據結構習題集一、選擇題1數(shù)據結構中所定義的數(shù)據元素，是用于表示數(shù)據的 。 （C）A.最小單位  B.最大單位  C.基本單位  D.不可分割的單位2從邏輯上可以把數(shù)據結構分為 （C） A.動態(tài)結構、靜態(tài)結構 B.順序結構、鏈式結構 C.線性結構、非線性結構 D.初等結構、構造型結構3當待排序序列中記錄數(shù)較少或基本有序時，最適合的排序方法為(A )A.直接插入排序法  B.快速排序法 C.堆排序法    D.歸并排序法4關于串的的敘述，不正確的是( B)A.串是字符的有限序列 B.空串是由空格構

2、成的串 C.替換是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲5帶表頭結點鏈隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為（A ）A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL6若構造一棵具有n個結點的二叉排序樹，最壞的情況下其深度不會超過（B）A.n/2        B.n  C.(n+1)/2      D.n+17將兩個各有n個元素的有序表合并成一個有序表

3、，其最少的比較次數(shù)為（A） A.n B.2n-1 C.2n D.n28設順序表有19個元素，第一個元素的地址為200，且每個元素占3個字節(jié)，則第14個元素的存儲地址為(B ) A.236 B.239 C.242 D.2459一個棧的入棧序列是a,b,c,d,e，則棧的輸出序列不可能是(A )A.dceab B.decba C.edcba D.abcde10元素大小為1個單元，容量為n個單元的非空順序棧中，以地址高端為棧底，以top作為棧頂指針，則出棧處理后，top的值應修改為(D ) A.top=top B.top=n-1 C.top=top-1 D.top=top+111設有一個10階的對稱

4、矩陣A，采用壓縮存儲方式以行序為主序存儲，a00為第一個元素，其存儲地址為0，每個元素占有1個存儲地址空間，則a45的地址為（B）A.13 B.35 C.17 D.3612棧和隊列(   C  )A.共同之處在于二者都是先進先出的特殊的線性表 B.共同之處在于二者都是先進后出的特殊的線性表C.共同之處在于二者都只允許在頂端執(zhí)行刪除操作 D.沒有共同之處13含有n個結點的二叉樹用二叉鏈表表示時，空指針域個數(shù)為(C )A.n-1 B.n C.n+1 D.n+214對一棵有100個結點的完全二叉樹按層序編號，則編號為49的結點，它的左孩子的編號為（B） A.9

5、9 B.98 C.97 D.5015在一個圖中，所有頂點的度數(shù)之和與圖的邊數(shù)的比是( C)A.12 B.11 C.21 D.4116在一個具有n個頂點的無向圖中，要連通全部頂點至少需要的邊數(shù)為(A ) A.n-1 B.n C.n+1 D.n/217在一個具有n個頂點的無向圖中，每個頂點度的最大值為（   B  ）A.n  B.n-1 C.n+1  D.2(n-1)18若采用鄰接表存儲結構，則圖的廣度優(yōu)先搜索類似于二叉樹的（D）A.先序遍歷    B.中序遍歷 C.后序遍歷  

6、 D.層次遍歷19對線性表進行二分查找時，要求線性表必須( C)A.以順序方式存儲 B.以鏈式方式存儲 C.以順序方式存儲，且結點按關鍵字有序排列 D.以鏈接方式存儲，且結點按關鍵字有序排列20二分查找算法的時間復雜度是（D）A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)21采用排序算法對n個元素進行排序，其排序趟數(shù)肯定為n-1趟的排序方法是（C） A.插入和快速 B.冒泡和快速 C.選擇和插入 D.選擇和冒泡22. 閉散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是( B)A.由同義詞之間發(fā)生沖突引起的 B.由非同義詞之間發(fā)生沖突引起的C.由同義詞之

7、間或非同義詞之間發(fā)生沖突引起的 D.由散列表“溢出”引起的23在對查找表的查找過程中，若被查找的數(shù)據元素不存在，則把該數(shù)據元素插入到集合中。這種方式主要適合于( B) A.靜態(tài)查找表 B.動態(tài)查找表 C.靜態(tài)查找表與動態(tài)查找表 D.靜態(tài)查找表或動態(tài)查找表24排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是(B )A.選擇排序 B.插入排序 C.冒泡排序 D.快速排序25下列程序段的時間復雜度為。（ C）for（i=0；i<m；i+）for（j=0；j<t；j+）cij=0；for（i=0；i<m；i+）for（j=0；j<t；j+）for（k=0；k<

8、;n；k+）cij=cij+aik*bkj；A.O(m+n×t) B.O(m+n+t) C.O(m×n×t) D.O(m×t+n)26數(shù)據的四種基本邏輯結構是指（ D ）A.數(shù)組、鏈表、樹、圖形結構       B.線性表、鏈表、棧隊列、數(shù)組廣義表C.線性結構、鏈表、樹、圖形結構           D.集合、線性結構、樹、圖形結構27在表長為n的順序表上做插入運算，平均要移動的結點數(shù)為

9、（ C ）。A.n/4 B.n/3 C.n/2 D.n28含有10個結點的二叉樹中，度為0的結點數(shù)為4，則度為2的結點數(shù)為（ A ）。 A.3 B.4 C.5 D.629定義二維數(shù)組A18，010，起始地址為LOC，每個元素占2L個存儲單元，在以行序為主序的存儲方式下，某數(shù)據元素的地址為LOC+50L，則在以列序為主序的存儲方式下，該元素的存儲地址為（D）。 A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L30下列程序段的時間復雜度為_。 （ D ）for(i=1；i<=n；i+)for(j=1；j<=n；j+)for(k=1；k<=n；k+)s

10、=i+j+k；A.O(m2) B.O(m3) C.O(n2) D.O(n3)31排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是( B )。A.選擇排序 B.插入排序 C.冒泡排序 D.快速排序32設有一個棧，按A、B、C、D的順序進棧，則可能為出棧序列的是( A )。A.DCBA B. CDAB C. DBAC D. DCAB33對一棵有100個結點的完全二叉樹按層編號，則編號為49的結點，它的父結點的編號為（A ）。A. 24 B. 25 C.98 D.9934對一棵二叉排序樹采用中序遍歷進行輸出的數(shù)據一定是（ D ）。A.遞增或遞減序列 B.遞減序列 C.無序序列 D.遞增

11、序列35散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是( B )。A.由同義詞之間發(fā)生沖突引起的 B.由非同義詞之間發(fā)生沖突引起的C.由同義詞之間或非同義詞之間發(fā)生沖突引起的 D.由散列表“溢出”引起的36要解決散列引起的沖突問題，常采用的方法有（ D ）。A.數(shù)字分析法、平方取中法  B.數(shù)字分析法、線性探測法C.二次探測法、平方取中法 D.二次探測法、鏈地址法37下列程序段的時間復雜度為_。 （ A ）k=1; for（i=0；i<n；i+）for（j=0；j<n；j+） Aij=k+；A.O（n2） B.O（n） C.O（2n） D.O（1）38數(shù)據的四種基本

12、存儲結構是指 （B）  A.順序存儲結構、索引存儲結構、直接存儲結構、倒排存儲結構  B.順序存儲結構、索引存儲結構、鏈式存儲結構、散列存儲結構  C.順序存儲結構、非順序存儲結構、指針存儲結構、樹型存儲結構  D.順序存儲結構、鏈式存儲結構、樹型存儲結構、圖型存儲結構39從邏輯關系來看，數(shù)據元素的直接前驅為0個或1個的數(shù)據結構只能是（ C   ）A.線性結構  B.樹形結構 C.線性結構和樹型結構  D.線性結構和圖狀結構40在表長為n的順序表上做刪除運算，其平均時間復雜度為 ( B )A.O(1) B

13、.O(n) C.O(nlog2n) D.O(n2)41順序表中有19個元素，第一個元素的地址為200，且每個元素占一個字節(jié)，則第14個元素的存儲地址為（ B ）A.212 B.213 C.214 D.21542當待排序序列中記錄數(shù)較少或基本有序時，最適合的排序方法為(    A  )A.直接插入排序法      B.快速排序法 C.堆排序法       D.歸并排序法43在完全二叉樹中，若一個結點是葉結點，則它沒有(

14、C )A.左孩子結點 B.右孩子結點 C.左孩子結點和右孩子結點 D.左孩子結點，右孩子結點和兄弟結點44設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數(shù)為(C )A.5 B.6 C.7 D.945二維數(shù)組A1120采用按行為主序的存儲方式，每個元素占4個存儲單元，若A00的存儲地址為300，則A1010的地址為（A）  A.700  B.1120 C.1180  D.114046用n個值構造一棵二叉排序樹，它的最大高度為（ B ）A.n/2 B. n C. n+1 D.log2n47含有10個結點的二叉樹中，度為0的結點數(shù)為4，則度為2的結點數(shù)

15、為（A） A.3 B.4 C.5 D.648一個具有n個頂點的無向連通圖，它所包含的連通分量數(shù)為（B） A.0 B.1 C.n D.不確定49對線性表進行二分查找時，要求線性表必須(C )A.以順序方式存儲 B.以鏈式方式存儲 C.以順序方式存儲，且結點按關鍵字有序排列 D.以鏈接方式存儲，且結點按關鍵字有序排列50散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是(B )A.由同義詞之間發(fā)生沖突引起的 B.由非同義詞之間發(fā)生沖突引起的C.由同義詞之間或非同義詞之間發(fā)生沖突引起的 D.由散列表“溢出”引起的51在對查找表的查找過程中，若被查找的數(shù)據元素不存在，則把該數(shù)據元素插入到集合中。這種

16、方式主要適合于(B ) A.靜態(tài)查找表 B.動態(tài)查找表 C.靜態(tài)查找表與動態(tài)查找表 D.靜態(tài)查找表或動態(tài)查找表52要解決散列引起的沖突問題，常采用的方法有(  D   )A.數(shù)字分析法、平方取中法  B.數(shù)字分析法、線性探測法C.二次探測法、平方取中法 D.二次探測法、鏈地址法53設用鏈表作為棧的存儲結構，則進行出棧操作時（ ）。A 必須判別棧是否為滿 B 必須判別棧是否為空C 判別棧元素的類型D 對棧不作任何判別54. 棧和隊列的共同特點是( A )。A.只允許在端點處插入和刪除元素B.都是先進后出 C.都是先進先出 D.沒有共同點55.若有

17、10個元素的有序表存放在一維數(shù)組A11中，第一個元素放A1中，最后一個數(shù)據存入A10,對這組數(shù)據進行二分查找，則查找A3的比較序列的下標依次為( A )A. 5，2，3B. 6，4，3C. 6，2，3D. 4，2，356.用鏈表方式存儲的隊列，在進行插入運算時( C ).A. 僅修改頭指針 B. 頭、尾指針都要修改C. 僅修改尾指針 D.頭、尾指針可能都要修改57.下列各項鍵值序列中不是堆的為（ C ）A.5，23，16，68，94，72，71，73 B.5，16，23，68，94，72，71，73C.5，23，16，73，94，72，71，68 D.5，23，16，68，73，71，72，9

18、458.以下數(shù)據結構中哪一個是非線性結構？( D )A. 隊列 B. 棧 C. 線性表 D. 二叉樹59二叉樹的第k層的結點數(shù)最多為( A ).A2k-1 B.2K+1 C.2K-1 D. 2k-160.若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進行二分查找，則查找A3的比較序列的下標依次為( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，361.設有6個結點的無向圖，該圖至少應有( A )條邊才能確保是一個連通圖。A.5 B.6 C.7 D.862下面關于線性表的敘述錯誤的是（ D ）。A 線性表采用順序存儲必須占用一片連續(xù)的存儲空間B

19、 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C 線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)D 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)63設哈夫曼樹中的葉子結點總數(shù)為m，若用二叉鏈表作為存儲結構，則該哈夫曼樹中總共有（ B ）個空指針域。A 2m-1 B 2m C 2m+1 D 4m64設某完全無向圖中有n個頂點，則該完全無向圖中有（ A ）條邊。A n(n-1)/2 B n(n-1) C n2 D n2-165設一組初始記錄關鍵字序列(5，2，6，3，8)，以第一個記錄關鍵字5為基準進行一趟快速排序的結果為（ C ）。A 2，3，5，8，6 B 3，2，5，8，6C 3，2，5，6，8D

20、 2，3，6，5，866設指針變量p指向單鏈表中結點A的前驅節(jié)點，若刪除單鏈表中結點A，則需要執(zhí)行的操作序列為（C ）。A q=p->next；p->data=q->data；p->next=q->next；free(q)；B q=p->next；q->data=p->data；p->next=q->next；free(q)；C q=p->next；p->next=q->next；free(q)；D q=p->next；p->data=q->data；free(q)；67. 設某強連通圖中有n個頂點

21、，則該強連通圖中至少有（ C ）條邊。A n(n-1)B n+1C nD n(n+1)68設用鏈表作為棧的存儲結構則出棧操作時（ B ）。A 必須判別棧是否為滿B 必須判別棧是否為空C 判別棧元素的類型D 對棧不作任何判別69數(shù)據的最小單位是（ A ）。A 數(shù)據項B 數(shù)據類型C 數(shù)據元素D 數(shù)據變量70若入棧順序為1、2、3、4、5、6，則出棧序列為（ B ）。A 5，3，4，6，1，2B 3，2，5，6，4，1C 3，1，2，5，4，6D 1，5，4，6，2，371.下列關鍵碼序列中，屬于堆的是（A）A（15，30，22，93，52，71） B（15，71，30，22，93，52）

22、C（15，52，22，93，30，71） D（93，30，52，22，15，71）二、填空題1在棧結構中，允許插入的一端稱為_棧頂_。2從一個長度為n的順序表中刪除第i個元素(1in)時，需向前移動_n-i_個元素。3深度為k的二叉樹，結點數(shù)最多有_2k-1_個。4在圖中，第一個頂點和最后一個頂點相同的路徑稱為_回路或環(huán)_。5對于具有n個元素的數(shù)據序列，采用順序查找法，其平均查找長度為_（n+1）/2_。6快速排序算法的時間復雜度為_O（nlogn）_。7若圖的鄰接矩陣不是一個對稱矩陣，則該圖一定是一個_有向圖_。8若一個無向完全圖具有n個頂點，則該圖的邊的條數(shù)為_n(n-1)/2_

23、。9有m個葉子結點的哈夫曼樹，其結點總數(shù)是_2m-1_。10堆排序需_1_個記錄大小的輔助存儲空間。11在隊結構中，允許插入的一端稱為 隊尾 ;在棧結構中，允許插入的一端稱為 。12在數(shù)據結構中，數(shù)據的存儲結構有 存儲、 存儲、 存儲和 存儲四種方式。13若某二叉樹中度為1的結點數(shù)為4，度為2的結點數(shù)為6，則該樹葉子結點數(shù)為 7 。14樹在數(shù)據結構中常采用 、 、 三種存儲結構表示15設一個順序棧S，元素s1，s2，s3，s4，s5，s6依次進棧，如果6個元素的退棧順序為s2，s3，s4，s6，s5，s1，則順序棧的容量至少為 3 。16對一棵深度為10的滿二叉樹按層編號，則編號為51的結點，

24、它的雙親結點編號為 25 。 17一個具有10個頂點的完全無向圖中有 45 條邊。18在無向圖G的鄰接矩陣A中，若Aij等于0，則Aji等于 0 。 19對二叉排序樹進行 遍歷，可得到排好序的遞增結點序列。20設順序表的表長為n，且查找每個元素的概率相等，則采用順序查找法查找表中任一元素，在查找成功時的平均查找長度為 。21實現(xiàn)二分查找的存儲結構僅限于順序存儲結構，且其中元素排列必須是 的。22對順序表執(zhí)行刪除操作，其刪除算法的平均時間復雜性為 O（n） 。23對于具有n個元素的有序序列，若采用冒泡排序，最多需要進行 1 趟起泡。24在圖中，第一個頂點和最后一個頂點相同的路徑稱為 。25在棧結

25、構中，允許插入的一端稱為_，另一端稱為_。26從一個長度為n的順序表中刪除第i個元素(1in)時，需向前移動_n-i_個元素。27一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素為_n-i+1_。28深度為k的二叉樹，結點數(shù)最多有_個。29二路歸并排序算法的時間復雜度為_。30含有n個頂點和n-1條邊的連通圖G采用_鄰接表_存儲結構較省空間。31在圖中，第一個頂點和最后一個頂點相同的路徑稱為_。32對于具有n個元素的數(shù)據序列，采用順序查找法，其平均查找長度為_。33索引順序查找通常分兩個階段進行，首先采用順序查找法或二分法確定所要查找的塊，然后再用_查找法在塊中找到

26、具體的元素值。34對n個元素進行冒泡排序時，最少的比較次數(shù)為_n-1_。 35快速排序法在待排序數(shù)據_基本有序_的情況下最不利于發(fā)揮其長處。36快速排序算法的時間復雜度為_O(nlogn)_。37在一棵二叉排序樹上按_遍歷得到的結點序列是一個有序序列。38若圖的鄰接矩陣不是一個對稱矩陣，則該圖一定是一個_。39若一個無向完全圖具有n個頂點，則該圖的邊的條數(shù)為_。40有m個葉子結點的哈夫曼樹，其結點總數(shù)是_。41對一棵深度為10的滿二叉樹按層編號，則編號為51的結點，它的雙親結點編號為_25_。42具有n個頂點的連通圖至少需有_條邊。43堆排序需_1_個記錄大小的輔助存儲空間。44. 隊列是一種

27、 _ 線性表。45算法的特性有：輸入、_、 _ 、可行性 、輸出。46對任意非空二叉樹，若葉子結點數(shù)為n0，度為1的結點數(shù)為n1，度為2的結點數(shù)為n2，則n0_ 47中序遍歷二叉樹步驟是：若二叉樹非空，1)中序遍歷左子樹，2）_，3)中序遍歷右子樹48. n階上三角矩陣采用一維數(shù)組存放時，可壓縮存儲到_個元素中。49連通圖的最小生成樹中有n個頂點，_條邊，并不能存在_ 。50n個結點的完全二叉樹，結點按從上到下從左到右編號，其中序號為i結點的左孩子序號_2i_三、應用題1有一字符串序列為5*-x-y/x+2，利用棧的運算將其輸出結果變?yōu)?x-*yx+/-2，描述棧的操作特點，試寫出該操作的入棧

28、和出棧過程（用push(a)表示a入棧，pop(a)表示a出棧）。特點自己從書上找。Push(5) pop(5) push(*) push(-) push(x) pop(x) pop(-) pop(x) push(-) push(y) pop(y) push(/) push(x) pop(x) push(+) pop(+) pop(/) pop(-) push(2) pop(2)2在棧的輸入端有6個元素，輸入順序為A，B，C，D，E，F(xiàn)。請描述棧的操作特點，并判斷能否在棧的輸出端得到序列DCFEBA，若能，給出入棧、出棧操作的過程，若不能，簡述其理由。（push（A）表示入棧，pop（A）表示

29、出棧）棧的操作特點自己查找能Push（A）Push（B）Push（C），Push（D），Pop（D），Pop（C）Push（E），Push（F）Pop（F），Pop（E），Pop（B），Pop（A）3.有一字符串的次序為-3*y+ay！2，試利用棧將輸出次序改變?yōu)?y*-ay！2+，描述棧的操作特點，寫出該輸出序列對應的進棧和退棧的操作步驟。(用push(x)表示x進棧，pop(x)表示x退棧)Push(-) push(3) pop(3) push(*) push(y) pop(y) pop(*) pop(-) push(+) push(a) pop(a) push(/) push(y) po

30、p(y) push(!) pop(!) push(2) pop(2) pop(/) pop(+)4已知一棵二叉樹的先根遍歷序列為ABCDEGHF，中根遍歷序列為CBEDAGFH，畫出該二叉樹，并寫出后序遍歷序列。后序遍歷序列：CEDBFHGA5已知無向圖G的鄰接矩陣如圖所示。請畫出該無向圖，并寫出v0出發(fā)按深度優(yōu)先遍歷時的訪問序列。6已知散列函數(shù)為H(key)=key%7，散列表長度為7(散列地址空間為0.6)，待散列序列為：(25，48，32，50，68)。根據以上條件構造一散列表，并用線性探測法解決有關地址沖突；若要用該散列表查找元素68，給出所需的比較次數(shù)。H（25）=25% 7=4 H

31、（50）=50%7=1 H（48）=48%7=6 H（68）=68%7=5 H（32）=32%7=4查找68：首先計算：H（68）=68%7=5，68與32比較，68與48比較，68與68比較查找成功，共比較3次。7給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序將它們依次插入一棵初始時為空的二叉排序樹，描述二叉排序樹的定義，畫出插入完成后的二叉排序樹。定義自己從書上找8用冒泡排序算法對數(shù)據序列（49，38，65，97，76，134，27，49）進行升序排序，寫出整個冒泡排序的各趟排序過程。第一趟排序結果：38,49,65,76,97,27,49,

32、134第二趟排序結果：38,49,65,76,27,49,97,134第三趟排序結果：38,49,65,27,49,76,97,134第四趟排序結果：38,49,27,49,65,76,97,134第五趟排序結果：38,27,49,49,65,76,97,134第六趟排序結果：27,38,49,49,65,76,97,1349某通訊電文由A，B，C，D，E，F(xiàn)六個字符編碼組成，每個字符編碼在電文中出現(xiàn)的次數(shù)分別是6，5，9，10，20，1，請描述哈夫曼樹的特點，并畫出這六個字符編碼所用的哈夫曼樹，寫出每個字符的哈夫曼編碼。哈夫曼樹特點從教材上找。10已知一棵二叉樹的前序序列是ABCDEFG，中

33、序序列是CBDAEGF。請構造出該二叉樹，描述后序遍歷過程，給出該二叉樹的后序序列。 后序遍歷過程：若根不為空，則執(zhí)行如下操作，否則結束1）后序訪問根的左子樹；2）后序訪問根的右子樹；3）訪問根；后序遍歷序列：CDBGFEA11已知無向網的鄰接矩陣A如圖 ， 試畫出該網，描述最小生成樹算法，并畫出該網的最小生成樹。12設散列表容量為7（散列地址空間0.6），給定表（30，36，47，52，34）,散列函數(shù)H（K）=K %6，采用線性探測法解決沖突。要求：（1）構造散列表；（2）求查找數(shù)34需要比較的次數(shù)。 13用冒泡排序算法對數(shù)據序列（49，38，65，97，76，134，27，49）進行升序

34、排序，寫出整個冒泡排序的各趟排序過程。第一趟排序結果：38,49,65,76,97,27,49,134第二趟排序結果：38,49,65,76,27,49,97,134第三趟排序結果：38,49,65,27,49,76,97,134第四趟排序結果：38,49,27,49,65,76,97,134第五趟排序結果：38,27,49,49,65,76,97,134第六趟排序結果：27,38,49,49,65,76,97,13414.已知一棵二叉樹的中根遍歷序列和后根遍歷序列分別為BDAFEHGC和DBFHGECA，試畫出這棵二叉樹，描述前序遍歷過程，并寫出前序遍歷序列。前序遍歷過程：若根不為空，則執(zhí)行如下操作，否則結束1）訪問根結點；2）前序訪問根的左子樹；3）前序訪問根的右子樹；前序遍歷序列：abdcefgh15.設散列表容量為7（散列地址空間0.6），給定表（30，36，47，52，34），散列函數(shù)H（k）=k mod 6，采用線性探測法解決沖突。要求：   （1）構造散列表；  （2）求