2023年數(shù)據(jù)結(jié)構(gòu)模擬真題

數(shù)據(jù)構(gòu)造課程設(shè)計——教學(xué)編制問題米修，米修，I。數(shù)據(jù)構(gòu)造期末復(fù)習(xí)題〔清華C語言版〕作業(yè)，專業(yè)2010-02-2014:57:09閱讀351評論9 訂閱一．是非題〔共分，每題分〕1. 數(shù)據(jù)構(gòu)造可用三元式表示SPDS是DP是對D的根本操作集。(f)簡潔地說,數(shù)據(jù)構(gòu)造是帶有構(gòu)造的數(shù)據(jù)元素的集合。(t)推斷帶頭結(jié)點的非空循環(huán)單鏈表〔L〕中指針p所指結(jié)點是最終一個元素結(jié)點的條件是：p->next==L。(t)線性表的鏈?zhǔn)酱鎯?gòu)造具有可直接存取表中任一元素的優(yōu)點。(f)線性表的挨次存儲構(gòu)造優(yōu)于鏈?zhǔn)酱鎯?gòu)造。(f)6. 在單鏈表P指針?biāo)附Y(jié)點之后插入S結(jié)點的操作是：P->next=S;S->next=P->next;。(f)7 對于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?yōu)于挨次存儲。(t)挨次存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。(f)棧和隊列是操作上受限制的線性表。(t)隊列是與線性表完全不同的一種數(shù)據(jù)構(gòu)造。(f)隊列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進(jìn)展。(f)棧和隊列也是線性表。假設(shè)需要，可對它們中的任一元素進(jìn)展操作。(f)棧是限定僅在表頭進(jìn)展插入和表尾進(jìn)展刪除運算的線性表。(f)二叉樹中每個結(jié)點有兩個子結(jié)點，而對一般的樹，則無此限制，所以，二叉樹是樹的特別情形。(f)二叉樹是一棵結(jié)點的度最大為二的樹。(f)赫夫曼樹中結(jié)點個數(shù)肯定是奇數(shù)。(t)(t)假設(shè)B是一棵樹，B′BB′的后序遍歷。(f)通常，二叉樹的第i2i-1個結(jié)點。(f)(t)二叉樹的先序遍歷序列中，任意一個結(jié)點均處在其孩子結(jié)點的前面。(t)由樹結(jié)點的先根序列和后根序列可以唯一地確定一棵樹。(t)鄰接多重表可以用以表示無向圖，也可用以表示有向圖。(f)可從任意有向圖中得到關(guān)于全部頂點的拓?fù)浯涡颉?f)有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)關(guān)鍵路徑是AOE網(wǎng)中源點到匯點的最短路徑。(f)連通圖G的生成樹是一個包含G的全部n個頂點和n-1條邊的子圖。(f)一個無向圖的連通重量是其極大的連通子圖。(t)十字鏈表可以表示無向圖，也可用以表示有向圖。(f)鄰接表可以表示有向圖，也可以表示無向圖〔t〕二叉排序樹的平均查找長度為O(logｎ)。(t)二叉排序樹的最大查找長度與〔LOG2N〕同階。(f)選用好的HASH函數(shù)可避開沖突。(f)折半查找不適用于有序鏈表的查找。(t)35.對于目前所知的排序方法，快速排序具有最好的平均性能。(t)對于任何待排序序列來說，快速排序均快于冒泡排序。(f)在最壞狀況下，堆排序的時間性能是O(nlogn),比快速排序好(t)快速排序具有最好的平均時間性能，它在任何時候的時間簡單度都是〔nlog。(f)字符串是數(shù)據(jù)對象特定的線性表。(t)空串與空格串是一樣的。(f)對于一棵m階的B-樹.樹中每個結(jié)點至多有m個關(guān)鍵字.除根之外的全部非終端結(jié)點至少有┌m/2┐個關(guān)鍵字。(f)當(dāng)二叉排序樹是一棵平衡二叉樹時，其平均查找長度為O(log2n)。(t)廣義表的表頭和表尾都是廣義表。(f)44二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表。(t)選擇題。從規(guī)律上可以把數(shù)據(jù)構(gòu)造分成(c )。A.動態(tài)構(gòu)造和靜態(tài)構(gòu)造 B.挨次組織和鏈接組織C.線性構(gòu)造和非線性構(gòu)造 D.根本類型和組合類型線性表L在( b )狀況下適于使用鏈表構(gòu)造實現(xiàn)。A.不需修改L的構(gòu)造 B.需不斷對L進(jìn)展刪除、插入C.需常常修改L中結(jié)點值 D.L中含有大量結(jié)點帶頭結(jié)點的單鏈表L為空的推斷條件是b 。帶頭結(jié)點的循環(huán)鏈表L為空的推斷條件是 。A.L==null B.L->next==nullC.L->next==L D.L!=null假設(shè)挨次表中各結(jié)點的查找概率不等，則可用如下策略提高挨次查找的效率：假設(shè)找到指定的結(jié)點，將該結(jié)點與其后繼〔假設(shè)存在〕結(jié)點交換位置，使得常常被查找的結(jié)點漸漸移至表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。挨次表的存儲構(gòu)造為：typedefstruct{ElemType*elem;//數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨int length;//表長度}SSTable;intsearch_seq(SSTableST,KeyTypekey){//在挨次表ST中挨次查找關(guān)鍵字等于key的數(shù)據(jù)元素。//假設(shè)找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem[0].key=key;i=ST.length;while(ST.elem[i].key!=key) f if( a ){ST.elem[i]←→ST.elem[i+1]；e ；}returni;}A.i>0 B.i>=0 C.i<ST.length D.i<=ST.lengthE.i++ F.i-- G.A和C同時滿足 H.B和D同時滿足假設(shè)入棧挨次為A、B、C、D、E，則以下(d )出棧序列是不行能的。A．A、B、C、D、E B．B、C、D、A、EC．C、D、B、E、A D．D、E、C、A、B遞歸程序可借助于( c )轉(zhuǎn)化為非遞歸程序。a.線性表 b.隊列c:棧 d.數(shù)組在以下數(shù)據(jù)構(gòu)造中( c )具有先進(jìn)先出〔FIFO〕特性，( b)具有先進(jìn)后出(FILO〕特性。a．線性表 b．棧 c．隊列 d．廣義表假設(shè)對編號為1，2，3的列車車廂依次通過扳道棧進(jìn)展調(diào)度，不能得到( e)的序列。a:1,2,3 b:1,3,2 c:2,1,3 d:2,3,1 e:3,1,2 f:3,2,1在計算遞歸函數(shù)時，如不用遞歸過程，應(yīng)借助于(b) 這種數(shù)據(jù)構(gòu)造。A.線性表 B.棧 C.隊列 D.雙向隊列假設(shè)帶頭結(jié)點的鏈表只設(shè)尾結(jié)點指針。以下選擇中〔c〕最適用于隊列。單鏈表B〕雙向鏈表C循環(huán)單鏈表D〕雙向循環(huán)鏈表棧和隊列的一個共同點是(c )。A.都是先進(jìn)先出 B.都是先進(jìn)后出C.只允許在端點處插入和刪除元素 D.沒有共同點循環(huán)隊列用數(shù)組A[0..m-1]存放其元素值，設(shè)頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)是( c )。A.rear-front-1 B.Rear-front+1C.(rear-front+m)%m D.Rear-front如下關(guān)于串的陳述中，正確的選項是(a, c )。A.串是數(shù)據(jù)元素類型特別的線性表 B.串中的元素是字母C.串中假設(shè)干個元素構(gòu)成的子序列稱為子串 D.空串即為空格串對字符串s=’data-structure’執(zhí)行操作replace(s,substring(s,6,8),’bas’)的結(jié)果是( b )。a: ‘database’ b:‘data-base’ c: ‘bas’ d:‘data-basucture’設(shè)有二維數(shù)組A5x7,4個字節(jié)存儲，存儲器按字節(jié)編址.A的起始地址為100。則按行存儲時，元素A06的第一個字節(jié)的地址是〔d 〕按列存儲時，元素A06的第一個字節(jié)的地址是〔a 〕a:220 b: 200 c:140 d: 124對廣義表A=〔a,(b)〕,(c,),d〕執(zhí)行操作gettail(gethead(gettail(A)))〔b〕。a〔〕 b:〔〕 c:d d:(d)假設(shè)用于通訊的電文僅由6個字符組成，字母在電文中消滅的頻率分別為7,19,22,6,32,14。假設(shè)為這6個字母設(shè)計哈夫曼編碼〔設(shè)生成的二叉樹的規(guī)章是按給出的次序從左至右的結(jié)合，生成的二叉樹總是插入在最右，則頻率為7的字符編碼是〔g ，頻率為32的字符編碼是〔c 。a:00 b:01 c:10 d:11e:011 f:110 g:1110 h:1111對二叉排序樹〔c 〕可得到有序序列。a:按層遍歷 b:前序遍歷 c:中序遍歷 d:后序遍歷設(shè)一棵二叉樹BT的存儲構(gòu)造如下:1 2 3 4 5 6 7 8lchild 2 3 0 0 6 0 0 0dataABCDEFG Hrchild05408700其中l(wèi)child，rchild分別為結(jié)點的左、右孩子指針域，data為結(jié)點的數(shù)據(jù)域。則該二叉樹的高度為( d )；第3層有( a )個結(jié)點〔根結(jié)點為第1層。A．2 B.3 C.4 D.5在有n個結(jié)點的二叉樹的二叉鏈表表示中，空指針數(shù)〔b 。a.不定 b.n+1 c.n d.n-1假設(shè)某二叉樹有20個葉子結(jié)點，有20個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是( c )。A．40 B.55 C.59 D.61某二叉樹的先序遍歷次序為abcdefg中序遍歷次序為badcgfe，則該二叉樹的后序遍歷次序為〔c 。層次遍歷次序為〔a 。a: abcdefg b:cdebgfa c: bdgfeca d:edcgfba.圖示的三棵二叉樹中( c)為最優(yōu)二叉樹。A) B) C)c a2 7a b c d d b7 5 2 4 4 5abcd7524某二叉樹的后序遍歷和中序遍歷次序分別為DBFGECA和BDACFEG。則其先序遍歷次序為〔b ，層次遍歷次序為〔a 。a: abcdefg b:abdcefg c:abcdfeg d:abcdegf某樹的先根遍歷次序為abcdefg后根遍歷次序為cdebgfa。假設(shè)將該樹轉(zhuǎn)換為二叉樹,其后序遍歷次序為〔d。a: abcdefg b:cdebgfa c: cdegbfa d:edcgfbaxy是二叉樹中的任意兩個結(jié)點，假設(shè)在先根序列中xy之前，而在后根序列中xy之后，則x和y的關(guān)系是( c )。A.x是y的左兄弟 B.x是y的右兄弟C.x是y的祖先 D.x是y的子孫用三叉鏈表作二叉樹的存儲構(gòu)造，當(dāng)二叉樹中有n個結(jié)點時，有( d )個空指針。A.n-1 B.n C.n+1 D.n+2對一棵完全二叉樹進(jìn)展層序編號。則編號為n的結(jié)點假設(shè)存在右孩子,其位序是( d)。編號為n的結(jié)點假設(shè)存在雙親,其位置是(a )。a:n/2 b:2n c:2n-1 d:2n+1 e:n f:2(n+1)設(shè)森林F中有三棵樹，第一、其次和第三棵樹的結(jié)點個數(shù)分別為m1、m2和m3，則與森林F對應(yīng)的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是(d)。A.m1 B.m1+m2 C.m3 D.m2+m3以下二叉樹中，(a )可用于實現(xiàn)符號不等長高效編碼。a:最優(yōu)二叉樹 b:次優(yōu)查找樹 c:二叉平衡樹d:二叉排序樹鄰接表存儲構(gòu)造以下圖的深度優(yōu)先遍歷算法類似于二叉樹的( a )遍歷。A.先根 B.中根 C.后根 D.層次設(shè)無向圖G=(V,E)和G’=(V’,E’)，假設(shè)G’是G的生成樹，則下面不正確的說法是( b )。A.G’是G的子圖 B.G’是G的連通重量C.G’是G的無環(huán)子圖 D.G’是G的微小連通子圖且V’=V任何一個連通圖的最小生成樹(b)。A．只有一棵 B.有一棵或多棵 C.肯定有多棵 D.可能不存在某無向圖的鄰接表如下所示；(e)是其原圖。(c)是按該鄰接表遍歷所得深度優(yōu)先生成樹。(d)是按該鄰接表遍歷所得廣度優(yōu)先生成樹。0 a3211 b302 c4303 d52104 e525 f43A.a b B.a b C. a bc d c d c de f e f e fD.a b E.a b F.a bc d c d c de f e f e f深度優(yōu)先遍歷圖使用了數(shù)據(jù)構(gòu)造b ，而廣度優(yōu)先遍歷圖使用了數(shù)據(jù)構(gòu)造〔cA〕數(shù)組 B〕棧 C〕隊列 D〕線性表某有向圖的鄰接表存儲構(gòu)造如下圖。0 E 2 1 ∧1 D034∧2 C43 B120∧4 A2∧依據(jù)存儲構(gòu)造依教材中的算法其深度優(yōu)先遍歷次序為〔d 。廣度優(yōu)先遍歷此序為〔c 。各強連通重量的頂點集為〔h 。a: abcde. b: edcba. c: ecdab. d: ecadb.e: abc及ed f:bc及aed g: ab及ced h: ac及bed以下查找方法中〔a〕適用于查找單鏈表。挨次查找B〕折半查找 C〕分塊查找D〕hash查找以下算法中〔c 〕適用于求圖的最小代價生成樹〔b 〕能對圖作廣度優(yōu)先遍歷。A〕DFS算法 B〕BFS算法 C〕Prim算法 D〕Dijkstra算法關(guān)鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點〔c〕的路徑。a:弧的數(shù)目最多 b:弧的數(shù)目最少c:權(quán)值之和最大d:權(quán)值之和最小哈希表的查找效率取決于〔d 。a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是在Hash函數(shù)H(k)=kMODm中，一般來說，m應(yīng)取( c)。A.奇數(shù) B.偶數(shù) C.素數(shù) D.充分大的數(shù)在挨次表查找中，為避開查找過程中每一步都檢測整個表是否查找完畢，可承受a 方法。A.設(shè)置監(jiān)視哨B.鏈表存貯C.二分查找 D.快速查找靜態(tài)查找表和動態(tài)查找表的區(qū)分在于( b )。前者是挨次存儲，而后者是鏈?zhǔn)酱鎯η罢咧荒苓M(jìn)展查找操作，而后者可進(jìn)展查找、插入和刪除操作前者只能挨次查找，而后者只能折半查找前者可被排序，而后者不能被排序在一個含有n個元素的有序表上進(jìn)展折半查找找到一個元素最多要進(jìn)展( b )次元素比較。A．?log2(n)? B.?log2(n)?+1 C.?log2(n+1)? D.?log2(n+1)?+120,45,30,89,70,38,62，192-3樹中(初始狀態(tài)為空)，該B-樹為〔b 。再刪除38，該B-樹為〔f ?！?0 62〕 〔45 〕1920〔3845〕〔70，89〕 〔30 〕 〔70〕192〕 38〔62〕〔89〕a: b:〔45 70 〕 〔45 〕〔20〕〔62〕〔89〕 〔20〕 〔70〕19〔30〕 〔19〕(30,38〔62〕〔89〕c: d:〔30 70 〕 〔45 〕〔19，20〕〔4562〕〔89〕 〔20〕 〔70〕19〕 〔30〔62〕〔89〕e: f:依據(jù)插入次序〔80，90，100，110，85，70，75，60，72〕建立二叉排序樹。圖〔a 〕是最終變化的結(jié)果。假設(shè)仍以該插入次序建立平衡二叉樹。圖〔c 〕是最終變化的結(jié)果。80 8070 90 75 9060 75 85 100 60 70 85 1007211072110a:b:9090751008010070801107570 8511060728560 72c: d:假設(shè)有序表中關(guān)鍵字序列為：14，20，25，32，34，45，57，69，77，83，92。對其進(jìn)展折半查找，則在等概率狀況下，查找成功時的平均查找長度是(c)。查找32時需進(jìn)展(c)次比較。A.1 B.2 C.3 D.4哈希表地址空間為A[9]，哈希函數(shù)為H(k)=kmod7，承受線性探測再散列處理沖突。假設(shè)依次將數(shù)據(jù)序列：76,45,88,21,94,77,1717存儲的下標(biāo)為(h)；在等概率狀況下查找成功的平均查找長度為(c)。A.0 B.1 C.2 D.3E.4 F.5 G.6 H.7假設(shè)從二叉樹的根結(jié)點到其它任一結(jié)點的路徑上所經(jīng)過的結(jié)點序列按其關(guān)鍵字遞增有序二叉樹是(c)。A.二叉排序樹 B.赫夫曼樹 C.堆 D.平衡二叉樹當(dāng)待排序序列的關(guān)鍵字次序為倒序時，假設(shè)需為之進(jìn)展正序排序，以下方案中(d)為佳。A.起泡排序 B.快速排序C.直接插入排序 D.簡潔選擇排序一組待排序的記錄關(guān)鍵字初始排列如下：56,26,86,35,75,19,77,58,48,42以下選擇中〔d 〕是快速排序一趟排序的結(jié)果〔c 〕是希爾排序〔初始步長為3〕一趟排序的結(jié)果〔a 〕是初始堆〔大堆頂。A〕86,75,77,58,42,19,56,35,48,26.B〕26,56,35,75,19,77,58,48,42,86.C〕35,26,19,42,58,48,56,75,86,77.D〕42,26,48,35,19,56,77,58,75,86.以下排序算法中，(d)算法可能會消滅：初始數(shù)據(jù)有序時，花費的時間反而最多。A.堆排序 B.起泡排序 C.歸并排序 D.快速排序在以下排序方法中〔c 〕方法平均時間簡單度為0(nlogn，最壞狀況下時間簡單度為0(n2〔d 〕方法全部狀況下時間簡單度均為0(nlogn。a.插入排序b.希爾排序c.快速排序d.堆排序?qū)τ谝豢酶叨葹镵的二叉排序樹，結(jié)點數(shù)最少可有 個，最多可有 個。用 遍歷對二叉排序樹進(jìn)展訪問可得到有序序列。Hash函數(shù)為H〔K〕=Kmod130--14，用二次探測再散列處理沖突，關(guān)鍵字〔23，34，56，24，75，12，49,52，36，92〕的分布如圖，則平均成功的查找長度為〔 、平均失敗的查找長度為〔 。一棵ｍ階的Ｂ-樹，第一層至少有一個結(jié)點；其次層至少有2個結(jié)點，除根之外的全部非終端結(jié)點至少有〔〕棵子樹，樹中每個結(jié)點至多有〔 〕棵子樹。哈希表的查找效率取決于〔 〕( )和〔 。高度為4(包含不帶關(guān)鍵字的葉子結(jié)點層)的7 階B 樹最少有 個關(guān)鍵字，最多有 個關(guān)鍵字；假設(shè)其中的某結(jié)點正好有2個兒子，那么，該結(jié)點必定是 結(jié)點。對于一棵二叉排序樹，通過按( )次序遍