數(shù)據(jù)結(jié)構(gòu)綜合習(xí)題集含答案

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

2、成的串 C.替換是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)5帶表頭結(jié)點(diǎn)鏈隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則判斷隊(duì)空的條件為（A ）A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL6若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)，最壞的情況下其深度不會(huì)超過(guò)（B）A.n/2        B.n  C.(n+1)/2      D.n+17將兩個(gè)各有n個(gè)元素的有序表合并成一個(gè)有序表

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

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

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

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

7、間或非同義詞之間發(fā)生沖突引起的 D.由散列表“溢出”引起的23在對(duì)查找表的查找過(guò)程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于( B) A.靜態(tài)查找表 B.動(dòng)態(tài)查找表 C.靜態(tài)查找表與動(dòng)態(tài)查找表 D.靜態(tài)查找表或動(dòng)態(tài)查找表24排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是(B )A.選擇排序 B.插入排序 C.冒泡排序 D.快速排序25下列程序段的時(shí)間復(fù)雜度為。（ 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ù)據(jù)的四種基本邏輯結(jié)構(gòu)是指（ D ）A.數(shù)組、鏈表、樹(shù)、圖形結(jié)構(gòu)       B.線性表、鏈表、棧隊(duì)列、數(shù)組廣義表C.線性結(jié)構(gòu)、鏈表、樹(shù)、圖形結(jié)構(gòu)           D.集合、線性結(jié)構(gòu)、樹(shù)、圖形結(jié)構(gòu)27在表長(zhǎng)為n的順序表上做插入運(yùn)算，平均要移動(dòng)的結(jié)點(diǎn)數(shù)為

9、（ C ）。A.n/4 B.n/3 C.n/2 D.n28含有10個(gè)結(jié)點(diǎn)的二叉樹(shù)中，度為0的結(jié)點(diǎn)數(shù)為4，則度為2的結(jié)點(diǎn)數(shù)為（ A ）。 A.3 B.4 C.5 D.629定義二維數(shù)組A18，010，起始地址為L(zhǎng)OC，每個(gè)元素占2L個(gè)存儲(chǔ)單元，在以行序?yàn)橹餍虻拇鎯?chǔ)方式下，某數(shù)據(jù)元素的地址為L(zhǎng)OC+50L，則在以列序?yàn)橹餍虻拇鎯?chǔ)方式下，該元素的存儲(chǔ)地址為（D）。 A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L30下列程序段的時(shí)間復(fù)雜度為_(kāi)。 （ 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設(shè)有一個(gè)棧，按A、B、C、D的順序進(jìn)棧，則可能為出棧序列的是( A )。A.DCBA B. CDAB C. DBAC D. DCAB33對(duì)一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)，它的父結(jié)點(diǎn)的編號(hào)為（A ）。A. 24 B. 25 C.98 D.9934對(duì)一棵二叉排序樹(shù)采用中序遍歷進(jìn)行輸出的數(shù)據(jù)一定是（ D ）。A.遞增或遞減序列 B.遞減序列 C.無(wú)序序列 D.遞增

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

12、存儲(chǔ)結(jié)構(gòu)是指 （B）  A.順序存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、直接存儲(chǔ)結(jié)構(gòu)、倒排存儲(chǔ)結(jié)構(gòu)  B.順序存儲(chǔ)結(jié)構(gòu)、索引存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、散列存儲(chǔ)結(jié)構(gòu)  C.順序存儲(chǔ)結(jié)構(gòu)、非順序存儲(chǔ)結(jié)構(gòu)、指針存儲(chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)  D.順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、樹(shù)型存儲(chǔ)結(jié)構(gòu)、圖型存儲(chǔ)結(jié)構(gòu)39從邏輯關(guān)系來(lái)看，數(shù)據(jù)元素的直接前驅(qū)為0個(gè)或1個(gè)的數(shù)據(jù)結(jié)構(gòu)只能是（ C   ）A.線性結(jié)構(gòu)  B.樹(shù)形結(jié)構(gòu) C.線性結(jié)構(gòu)和樹(shù)型結(jié)構(gòu)  D.線性結(jié)構(gòu)和圖狀結(jié)構(gòu)40在表長(zhǎng)為n的順序表上做刪除運(yùn)算，其平均時(shí)間復(fù)雜度為 ( B )A.O(1) B

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

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

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

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

17、10個(gè)元素的有序表存放在一維數(shù)組A11中，第一個(gè)元素放A1中，最后一個(gè)數(shù)據(jù)存入A10,對(duì)這組數(shù)據(jù)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( A )A. 5，2，3B. 6，4，3C. 6，2，3D. 4，2，356.用鏈表方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)( C ).A. 僅修改頭指針 B. 頭、尾指針都要修改C. 僅修改尾指針 D.頭、尾指針可能都要修改57.下列各項(xiàng)鍵值序列中不是堆的為（ 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ù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？( D )A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹(shù)59二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為( A ).A2k-1 B.2K+1 C.2K-1 D. 2k-160.若有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( D )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，361.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖，該圖至少應(yīng)有( A )條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.862下面關(guān)于線性表的敘述錯(cuò)誤的是（ D ）。A 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間B

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

20、 2，3，6，5，866設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A的前驅(qū)節(jié)點(diǎn)，若刪除單鏈表中結(jié)點(diǎn)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. 設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)

21、，則該強(qiáng)連通圖中至少有（ C ）條邊。A n(n-1)B n+1C nD n(n+1)68設(shè)用鏈表作為棧的存儲(chǔ)結(jié)構(gòu)則出棧操作時(shí)（ B ）。A 必須判別棧是否為滿B 必須判別棧是否為空C 判別棧元素的類型D 對(duì)棧不作任何判別69數(shù)據(jù)的最小單位是（ A ）。A 數(shù)據(jù)項(xiàng)B 數(shù)據(jù)類型C 數(shù)據(jù)元素D 數(shù)據(jù)變量70若入棧順序?yàn)?、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.下列關(guān)鍵碼序列中，屬于堆的是（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在棧結(jié)構(gòu)中，允許插入的一端稱為_(kāi)棧頂_。2從一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素(1in)時(shí)，需向前移動(dòng)_n-i_個(gè)元素。3深度為k的二叉樹(shù)，結(jié)點(diǎn)數(shù)最多有_2k-1_個(gè)。4在圖中，第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為_(kāi)回路或環(huán)_。5對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，采用順序查找法，其平均查找長(zhǎng)度為_(kāi)（n+1）/2_。6快速排序算法的時(shí)間復(fù)雜度為_(kāi)O（nlogn）_。7若圖的鄰接矩陣不是一個(gè)對(duì)稱矩陣，則該圖一定是一個(gè)_有向圖_。8若一個(gè)無(wú)向完全圖具有n個(gè)頂點(diǎn)，則該圖的邊的條數(shù)為_(kāi)n(n-1)/2_

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

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

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

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

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

28、和出棧過(guò)程（用push(a)表示a入棧，pop(a)表示a出棧）。特點(diǎn)自己從書上找。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個(gè)元素，輸入順序?yàn)锳，B，C，D，E，F(xiàn)。請(qǐng)描述棧的操作特點(diǎn)，并判斷能否在棧的輸出端得到序列DCFEBA，若能，給出入棧、出棧操作的過(guò)程，若不能，簡(jiǎn)述其理由。（push（A）表示入棧，pop（A）表示

29、出棧）棧的操作特點(diǎn)自己查找能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.有一字符串的次序?yàn)?3*y+ay！2，試?yán)脳⑤敵龃涡蚋淖優(yōu)?y*-ay！2+，描述棧的操作特點(diǎn)，寫出該輸出序列對(duì)應(yīng)的進(jìn)棧和退棧的操作步驟。(用push(x)表示x進(jìn)棧，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已知一棵二叉樹(shù)的先根遍歷序列為ABCDEGHF，中根遍歷序列為CBEDAGFH，畫出該二叉樹(shù)，并寫出后序遍歷序列。后序遍歷序列：CEDBFHGA5已知無(wú)向圖G的鄰接矩陣如圖所示。請(qǐng)畫出該無(wú)向圖，并寫出v0出發(fā)按深度優(yōu)先遍歷時(shí)的訪問(wèn)序列。6已知散列函數(shù)為H(key)=key%7，散列表長(zhǎng)度為7(散列地址空間為0.6)，待散列序列為：(25，48，32，50，68)。根據(jù)以上條件構(gòu)造一散列表，并用線性探測(cè)法解決有關(guān)地址沖突；若要用該散列表查找元素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：首先計(jì)算：H（68）=68%7=5，68與32比較，68與48比較，68與68比較查找成功，共比較3次。7給定表（39，14，22，8，65，28，88，29，67，13，10），試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹(shù)，描述二叉排序樹(shù)的定義，畫出插入完成后的二叉排序樹(shù)。定義自己從書上找8用冒泡排序算法對(duì)數(shù)據(jù)序列（49，38，65，97，76，134，27，49）進(jìn)行升序排序，寫出整個(gè)冒泡排序的各趟排序過(guò)程。第一趟排序結(jié)果：38,49,65,76,97,27,49,

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

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

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