《2019年電大本科數(shù)據結構期末考試題庫及答案》由會員分享，可在線閱讀，更多相關《2019年電大本科數(shù)據結構期末考試題庫及答案（21頁珍藏版）》請在裝配圖網上搜索。

1、數(shù)據結構（本）期末題庫及答案一、單項選擇題1數(shù)據的物理結構（ D ）。 A與數(shù)據的邏輯結構無關 B僅僅包括數(shù)據元素的表示C只包括數(shù)據元素間關系的表示 D包括數(shù)據元素的表示和關系的表示2數(shù)據元素是數(shù)據的基本單位，它（ C ）。A只能有一個數(shù)據項組成 B至少有二個數(shù)據項組成C可以是一個數(shù)據項也可以由若干個數(shù)據項組成D至少有一個數(shù)據項為指針類型3從n個數(shù)中選取最大元素，（ C ）。 A基本操作是數(shù)據元素間的交換 B算法的時間復雜度是O(n2)C算法的時間復雜度是O(n) D需要進行(n+1)次數(shù)據元素間的比較4線性表的順序結構中，（ C ）。A邏輯上相鄰的元素在物理位置上不一定相鄰B數(shù)據元素是不能隨

2、機訪問的C邏輯上相鄰的元素在物理位置上也相鄰D進行數(shù)據元素的插入、刪除效率較高5以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表6帶頭結點的單向鏈表為空的判斷條件是（ B ）（設頭指針為head）。Ahead = =NULL Bhead-next= =NULL Chead-next= =head Dhead!=NULL7 .設順序存儲的線性表長度為n，對于刪除操作，設刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ A ）。A(n+1)/2 Bn C2n Dn-i8線性結構中數(shù)據元素的位置之間存在（ A ）的關系。 A一對一 B一對多 C多對多 D

3、每一個元素都有一個直接前驅和一個直接后繼9設top是一個鏈棧的棧頂指針，棧中每個結點由一個數(shù)據域data和指針域next組成，設用x接收棧頂元素，則出棧操作為（ A ）。Ax=top-data;top=top-next; Btop=top-next;x=top-data; Cx=top- next;top=top- data; Dtop-next =top; x=top-data;10設順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法，當i=（ C ）時，移動元素的次數(shù)為3A3 Bn/2 Cn-3 D411以下說法正確的是（ C ）。A隊列是后進先出 B棧的特點是后進后出C棧的刪除和插

4、入操作都只能在棧頂進行D隊列的刪除和插入操作都只能在隊頭進行12 .以下說法不正確的是（ C ）。A棧的特點是后進先出 B隊列的特點是先進先出C棧的刪除操作在棧底進行，插入操作在棧頂進行D隊列的插入操作在隊尾進行，刪除操作在隊頭進行13串函數(shù)StrCmp(“abA”,”aba”)的值為（ D ）。A1 B0 C“abAaba” D-114一個棧的進棧序列是a，b，c，d，則棧的不可能的出棧序列是（ A ）。Aadbc BbcadCcbad Ddcba15設有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始）

5、，則矩陣A中第4行的元素在數(shù)組b中的下標i一定有（ A ）。A7i10 B11i15 C9i14 D6i916已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ A ）。A2m Bm C2m+1 Dm/217設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數(shù)據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結點類型的指針，可執(zhí)行如下操作：p=front-next;x=p-data; 然后執(zhí)行（ B ）。Afront=p-next; Bfront-next=p-next;Cfront=p; Dfront-next =

6、p;18以下說法不正確的是（ D ）。 A連通圖G一定存在生成樹B連通圖G的生成樹中一定包含G的所有頂點C連通圖G的生成樹中不一定包含G的所有邊D連通圖G的生成樹可以是不連通的19散列查找的原理是（ A ）。A在待查記錄的關鍵字值與該記錄的存儲位置之間建立確定的對應關系B按待查記錄的關鍵字有序的順序方式存儲C按關鍵字值的比較進行查找D基于二分查找的方法20空串的長度為（ A ）。A0 B1 C2 D321排序過程中，每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經排好序的子序列的適當位置，直到全部排好序為止，該排序算法是( D )。 A選擇排序 B快速排序C冒泡排序 D直接插入排

7、序 22采用順序查找法對長度為n的線性表進行查找（不采用表尾設監(jiān)視哨的方法），最壞的情況下要進行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/223設有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標從1開始），則矩陣元素a5,3對應一維數(shù)組b的數(shù)組元素是（ C ）。Ab18 Bb8 Cb13 Db1024如圖1若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ D ）。abecdhgf AacebdfghBaebcghdfCaedfbcghDabecdfgh 圖125已知如圖2所示的

8、一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ D ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca 圖226一棵哈夫曼樹總共有23個結點，該樹共有（ D ）個葉結點（終端結點）。A10 B13 C11 D12二、填空題1通常數(shù)據的邏輯結構包括集合、線性、_樹形_、_ 圖狀 四種類型。2通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_圖狀 _結構。3設有一個單向鏈表，結點的指針域為next，頭指針為head，p指向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_ p-next=head;_ _。4設有一個單向循環(huán)鏈表，頭指針為

9、head，鏈表中結點的指針域為next，p指向尾結點的直接前驅結點，若要刪除尾結點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作_ _ p-next=head 。 5循環(huán)隊列的隊頭指針為f，隊尾指針為r，當_ r=f _時表明隊列已空。6在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next，則插入一個s所指結點的操作為_ r-next=s _；r=s；7設有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結點要入棧，則可執(zhí)行操作_ s-next=hs 和hs=s；8循環(huán)隊列的隊頭指針為f，隊尾指針為r，當_ r= =f _時表明隊列為空。 9在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的

10、指針域為next，則插入一個s所指結點的操作為_ r-next=s _；r=s；10“A”在存儲時占_2_個字節(jié)。11串的兩種最基本的存儲方式分別是_順序存儲_和 _鏈式存儲 _。12一棵二叉樹沒有單分支結點，有6個葉結點，則該樹總共有_11_個結點。13一棵二叉樹中順序編號為i的結點，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序 、_中序_、 _后序_三種。15兩個串相等的充分必要條件是 串長度相等且對應位置的字符相等 。16把數(shù)據存儲到計算機中,并具體體現(xiàn)數(shù)據之間的邏輯結構稱為_物理（存儲）_結構。17一棵二叉

11、樹葉結點（終端結點）數(shù)為5，單分支結點數(shù)為2，該樹共有_11_個結點。18如圖3所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖319根據搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷 方法。20二叉樹為二叉排序的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_錯誤_的。(回答正確或不正確) 21一個有序表3，4，10，14，34，43，46，64，75，78，90，96，130用折半查找法查找值為90的結點，經_4_次比較后查找成功。三、綜合題 1（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbe

12、ac，試畫出該二叉樹abced （2）若上述二叉樹的各個結點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關系。答：dbeac （3）給出該樹的前序遍歷序列答：abdec2（1）一組記錄的關鍵字序列為45，40，65，43，35，95，寫出利用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結果（要求給出一趟劃分中每次掃描和交換的 結果）答： 45 40 65 43 35 95 35 40 65 43 35 95 35 40 65 43 65 95 35 40 43 43 65 95 35 40 43 45 65 95 （2）對序列

13、45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。 答 40 45 65 43 35 95 40 43 45 65 35 95 35 40 43 45 65 9540287231005463（1）設有一個整數(shù)序列40，28，6，72，100，3，54依次取出序列中的數(shù)，構造一棵二叉排序樹 （2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：ASL=（1x1+2x2+3x3+4）/7=18/74 (1) 設有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據，構造一棵二叉排序樹.2461673185145（2）說明如

14、何通過序列的二叉排序樹得到相應序列的排序結果。答：中序遍歷16423252576782102 5（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出相應的完全二叉樹（不要求中間過程）初始樹 堆42826752573216102（2）寫出對上述堆對應的完全二叉樹進行中序遍歷得到的序列答：102，52，42，82，16，67，32，57四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關鍵字等于k的記錄，查找成功返回該記錄的下標，失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Sea

15、rch(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_low=high _) mid=(low+high)/2; if(amid.key=k) return _ mid _; else if(_amid.keydata=x; _ p-next=top _; _ top=p _; 3以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結點的數(shù)據域的值，front、rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *front，*re

16、ar; void InQueue(ElemType x) struct node *p; p= (struct node*) _ malloc(sizeof (struct node)_; p-data=x; p-next=NULL; _ rear-next=p _; rear= _ p _; 期末綜合練習二 一、單項選擇題1（ B ）是性質相同的數(shù)據元素的集合，是數(shù)據的子集。A數(shù)據元素 B數(shù)據對象 C數(shù)據結構 D數(shù)據項2同一種邏輯結構（ B ）。 A只能有唯一的存儲結構 B可以有不同的存儲結構 C只能表示某一種數(shù)據元素之間的關系 D以上三種說法均不正確3設鏈表中的結點是NODE類型的結構體變

17、量，且有NODE *p；為了申請一個新結點，并由p指向該結點，可用以下語句（ A ）。Ap=(NODE *)malloc(sizeof(NODE);Bp=(*NODE)malloc(sizeof(NODE);Cp=(NODE )malloc(sizeof(p);Dp=(NODE *)malloc(sizeof(p);4鏈表所具備的特點是（ C ）。A可以隨機訪問任一結點 B占用連續(xù)的存儲空間C插入刪除元素的操作不需要移動元素結點 D可以通過下標對鏈表進行直接訪問5設順序存儲的線性長度為n，要在第i個元素之前插入一個新元素，按課本的算法當i= （ D ）時，移動元素次數(shù)為2An/2 Bn C1

18、Dn-1 6數(shù)據的物理結構（ D ）。 A與數(shù)據的邏輯結構無關 B僅僅包括數(shù)據元素的表示C只包括數(shù)據元素間關系的表示 D包括數(shù)據元素的表示和關系的表示7一個棧的進棧序列是1，2，3，4，則棧的不可能的出棧序列是（ B ）（進出棧操作可以交替進行）A3，2，4，1 B1，4，2，3C4，3，2，1 D3，2，1，48線性結構中數(shù)據元素的位置之間存在（ A ）的關系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅和一個直接后繼 9設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數(shù)據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設p指向要入隊的新結點(

19、該結點已被賦值)，則入隊操作為（ A ）。Arear-next=p;rear=p; Brear-next=p; p = rear; Cp = rear-next;rear=p; Drear=p;rear-next=p;10以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表11以下說法不正確的是（ C ）。 A順序棧中，棧滿時再進行進棧操作稱為“上溢”B順序棧中，?？諘r再作出棧棧操作稱為“下溢”C順序隊列中，當尾指針已經超越隊列存儲空間的上界，則一定是隊列已滿D順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空12算法的時間復雜度與（ C ）

20、有關。 A所使用的計算機 B與計算機的操作系統(tǒng) C與算法本身 D與數(shù)據結構13設有一個20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11，數(shù)組b的下標從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標是（ D ）。A30 B28 C40 D3314設有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為（ B ）。 An-i+1 Bn-i Cn-i-1 Di15深度為5的完全二叉樹第5層上有4個結點，該樹一共有（ D ）個結點。A28 B30 C31 D1916在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結

21、點的直接后繼，現(xiàn)要刪除q所指結點，可用的語句是（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL17已知一個圖的所有頂點的度數(shù)之和為m，則m一定不可能是（ D ）。A4 B8 C12 D918從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(zhí)行（ A ）。 Ax=top-data; top=top-next; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;19以下說法正確的是（ D ）。 A連通圖G的生成樹中可以包含回路B連通圖G的生成

22、樹可以是不連通的C連通圖G的生成樹一定是唯一的D連通圖G的生成樹一定是連通而不包含回路的20在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（ C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;21 對n個元素進行冒泡排序，通常要進行n-1趟冒泡，在第j趟冒泡中共要進行（ C ）次元素間的比較。 Aj Bj-1 Cn-j Dn-j-122一個棧的進棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ A ）（進棧出?？梢越惶孢M行）。Adceab Bedcba Cdecba Dabcde 23在排序過程中，可以有效地減少一趟排序過

23、程中元素間的比較次數(shù)的算法是（ D ）。 A冒泡 B選擇 C直接插入 D折半插入 24有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A26/10 B29/10 C29/9 D31/1025如圖1若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ B ）。abecdf AaebcfdBabedcfCacebdfDacfbde 圖1 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇

24、排序27一棵哈夫曼樹有n個葉子結點（終端結點），該樹總共有（ B ）個結點。A2n-2 B2n-1 C2n D2n+228設有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標從1開始），則矩陣中元素A8,5在一維數(shù)組B中的下標是（ A ）。A33 B32 C85 D4129數(shù)據的（ A ）結構與所使用的計算機無關。 A邏輯 B物理 C存儲 D邏輯與存儲30在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D2 二、填空題1通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結構抽象成_樹形_結構。2棧和隊列的操作特點分別是_先

25、進后出_和 _先進先出_。3要在一個單向鏈表中p所指向的結點之后插入一個s所指向的新結點，若鏈表中結點的指針域為next，可執(zhí)行_ s-next= p-next；_和p-next=s;的操作。4結構中的數(shù)據元素存在多對多的關系稱為_圖狀 （網狀）_結構。5設有一個非空的鏈棧，棧頂指針為hs，要進行出棧操作，用x保存出棧結點的值，棧結點的指針域為next，則可執(zhí)行x=hs-data; _ hs=hs-next;_ _。6根據數(shù)據元素間關系的不同特性，通常可分為集合、線性、樹形 、 圖狀 四類基本結構。7在一個不帶頭結點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的數(shù)據域為data，指針域為n

26、ext，若要進行出隊操作，并用變量x存放出隊元素的數(shù)據值，則相關操作為x=f-data; _ f=f-next;_ _。8要求在n個數(shù)據元素中找其中值最大的元素，設基本操作為元素間的比較。則比較的次數(shù)和算法的時間復雜度分別為_和 _ n-1,O(n)_ 。9循環(huán)隊列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，則當隊尾指針rear= _ 4 _時，隊列為空，當rear= _ 2 _時，隊列有6個元素。10稀疏矩陣存儲時，采用一個由_行號_ 、_列號 _ 、_非零元_3部分信息組成的三元組唯一確定矩陣中的一個非零元素。11在二叉樹的鏈式

27、存儲結構中，通常每個結點中設置三個域，它們是值域 左指針 、 右指針 。12一棵二叉樹順序編號為6的結點（樹中各結點的編號與等深度的完全二叉中對應位置上結點的編號相同），若它存在右孩子，則右孩子的編號為_13_。13向一個棧頂指針為h的鏈棧中插入一個s所指結點時，可執(zhí)行s-next=h;和_ h=s _。14在一個鏈隊中，設f和r分別為隊頭和隊尾指針，則插入s所指結點的操作為_ r-next=s _和r=s; (結點的指針域為next)15如圖2所示的二叉樹，其前序遍歷序列為_ abdefcg _。gfabdec 圖2 16設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有_12_個結

28、點。（根所在結點為第1層）17在隊列的順序存儲結構中，當插入一個新的隊列元素時，尾指針的值增1，當刪除一個元素隊列時， 頭 指針的值增1。18對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的_行下標_、_列下標_和_非零元素值_三項信息。19循環(huán)隊列的引入，目的是為了克服 假上溢 。20在對一組記錄(55,39,97,22,16,73,65,47,88)進行直接插入排序時，當把第7個記錄65插入到有序表時，為尋找插入位置需比較_3_次。三、綜合題1（1）設head1和p1分別是不帶頭結點的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結點的單向鏈表B的頭指針和尾指針

29、，若要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關鍵的賦值語句（不用完整程序，結點的鏈域為next）。 答：p1-next= head2；p2-next= head1； （2）單向鏈表的鏈域為next，設指針p指向單向鏈表中的某個結點，指針s指向一個要插入鏈表的新結點，現(xiàn)要把s所指結點插入p所指結點之后，某學生采用以下語句： p-next=s; s-next=p-next; 這樣做正確嗎？若正確則回答正確，若不正確則說明應如何改寫答：不對，s-next= p-next；p-next=s；2 (1)以2，3，4，7，8，9作為葉結點的權，構造一棵哈夫曼樹(

30、要求每個結點的左子樹根結點的權小于等于右子樹根結點的權)，給出相應權重值葉結點的哈夫曼編碼。33 (1)1518799854322：11103: 11114：1107：008：019：10 (2) 一棵哈夫曼樹有n個葉結點，它一共有多少個結點？簡述理由？答: 2n-1個，因為非葉結點數(shù)比葉結點數(shù)少一個。3（1）畫出對長度為10的有序表進行折半查找的判定樹（以序號1，2，10表示樹結點） 52849631071（2）對上述序列進行折半查找，求等概率條件下，成功查找的平均查找長度答：ASL=（1x1+2x2+3x4+4x3）/10=29/104一組記錄的關鍵字序列為（46，79，56，38，40，

31、84）（1）利用快速排序的方法，給出以第一個記錄為基準得到的一次劃分結果（給出逐次交換元素的過程，要求以升序排列）初始序列 46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，84（2）對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。37776247522711 97113727475262779756793840844684793840465665679384046793840848456465（1）利用篩選法，把序列37，77

32、，62，97，11，27，52，47建成堆（小根堆），畫出相應的完全二叉樹初始樹 堆 （2）寫出對上述堆所對應的二叉樹進行前序遍歷得到的序列答：11，37，47，97，77，27，62，526設查找表為(50,60,75,85,96,98,105,110,120,130) (1) 說出進行折半查找成功查找到元素120需要進行多少次元素間的比較？ 3次(2) 為了折半查找元素95，經過多少次元素間的比較才能確定不能查到？4次96759813010585501100512060（3）畫出對上述有序表進行折半查找所對應的判定樹(要求以數(shù)據元素作為樹結點)四、程序填空題1以下函數(shù)為直接選擇排序算法，對

33、a1,a2,an中的記錄進行直接選擇排序，完成程序中的空格typedef struct int key;NODE; void selsort(NODE a,int n)int i,j,k;NODE temp;for(i=1;i= _ n-1_;i+) k=i; for(j=i+1;j= _ n _;j+) if(aj.keyak.key) _ k=j _; if(i!=k) temp=ai;_ ai=ak_;_ ak=temp _;2以下是用尾插法建立帶頭結點且有n個結點的單向鏈表的程序，結點中的數(shù)據域從前向后依次為1,2,3,n，完成程序中空格部分。NODE *create(n)NODE *

34、head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= p ; q=p ;pnext=NULL; /*建立頭結點*/for(i=1; ileft) ; printf(“%c”,BT-data) ; Inorder(BT-right) ; 期末綜合練習三一、單項選擇題1深度為5的完全二叉樹共有20個結點，則第5層上有（ C ）個結點(根所在結點為第一層)。A3 B8 C5 D62在C語言中，順序存儲長度為3的字符串，需要占用（ A ）個字節(jié)。 A4 B3 C6 D123已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ A ）。A2m

35、Bm C2m+1 Dm/24串函數(shù)StrCat（a,b）的功能是進行串（ D ）。 A比較 B復制 C賦值 D連接5數(shù)據結構中，與所使用的計算機無關的是數(shù)據的（ D ）結構。 A物理 B存儲 C邏輯與物理 D邏輯6一棵有n個結點采用鏈式存儲的二叉樹中，共有（ A ）個指針域為空。 An+1 Bn Cn-1 Dn-27鏈表所具備的特點是（ C ）。A可以隨機訪問任一結點 B占用連續(xù)的存儲空間C插入刪除不需要移動元素結點 D可以通過下標對鏈表進行直接訪問8設一棵哈夫曼樹共有n個非葉結點，則該樹有（ B ）個葉結點。 An Bn+1 Cn-1 D2n9線性表只要以（ C ）方式存儲就能進行折半查找。

36、A鏈接 B順序 C關鍵字有序的順序 D二叉樹10從一個棧頂指針為top的鏈棧中刪除一個結點時，用變量x保存被刪結點的值，則執(zhí)行（ A ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;11散列查找的原理是（ A ）。A在待查記錄的關鍵字值與該記錄的存儲位置之間建立確定的對應關系B按待查記錄的關鍵字有序的順序方式存儲C按關鍵字值的比較進行查找D基于二分查找的方法12一棵完全二叉樹共有5層，且第5層上有六個結點，該樹共有（ C ）個結點。 A30 B20 C21 D2

37、313對n個元素進行冒泡排序若某趟冒泡中只進行了（ C ）次元素間的交換，則表明序列已經排好序。 A1 B2 C0 Dn-114在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D215排序過程中，每一趟從無序子表中將一個待排序的記錄按其關鍵字的大小放置到已經排好序的子序列的適當位置，直到全部排好序為止，該排序算法是( A )。 A直接插入排序 B快速排序C冒泡排序 D選擇排序 16已知如圖1所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ A ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7

38、CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5 圖117在對一組元素（64，48，106，33，25，82，70，55，93）進行直接插入排序時，當進行到要把第7個元素70插入到已經排好序的子表時，為找到插入位置，需進行（ C ）次元素間的比較（指由小到大排序）。A6 B2 C3 D418已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為（ B ）。 Aabcedf Babcefd Caebcfd Dacfdebbdfeca 圖219采用順序查找法對長度為n的線性表進行查找（不采用表尾設監(jiān)視哨的方

39、法），最壞的情況下要進行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/220對二叉排序樹進行（ C ）遍歷，可以使遍歷所得到的序列是有序序列。 A按層次 B后序 C中序 D前序21如圖3，若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為（ B ）。 Aacebdgf BabecdgfCacfedgbDabecfdg abecdfg 圖322在有序表2，4，7，14，34，43，47，64，75，80，90，97，120中，用折半查找法查找值80時，經（ B ）次比較后查找成功。A4 B2 C3 D523元素2，4，6，8按順序依次進棧，則該棧的不可能輸出序列是（ D

40、 ）（進棧出?？梢越惶孢M行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，424有一個長度為9的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A25/10 B25/9 C20/9 D17/925排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ C ）排序。 A歸并 B插入 C選擇 D快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序

41、27一棵哈夫曼樹總共有23個結點，該樹共有（ D ）個葉結點（終端結點）A10 B13 C11 D1228一組記錄的關鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（ B ）。 A40，38，46，79，56，84 B40，38，46，56，79，84C40，38，46，84，56，79 D38，40，46，56，79，8429隊列的插入操作在（ B ）進行。 A隊頭 B隊尾 C隊頭或隊尾 D在任意指定位置 二、填空題（每小題2分，共24分）1一棵二叉樹沒有單分支結點，有6個葉結點，則該樹總共有_11_個結點。2在二叉樹的鏈式存儲

42、結構中，通常每個結點中設置三個域，它們是_值域_、 左指針 、右指針。3設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù)，該葉節(jié)點的雙親結點的編號為10，該完全二叉樹一共有_21_個結點。4一棵二叉樹中順序編號為i的結點，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。5按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序_ 、_中序 _、 _后序_三種。6串的兩種最基本的存儲方式是_順序存儲_和 _鏈式存儲_。7數(shù)據結構中的數(shù)據元素存在一對多的關系稱為_樹形_結構。8一棵有2n-1個結點的二叉樹，其每一個非葉結點的度數(shù)都為2，則該樹共有_N_個葉結點。9把數(shù)據存儲到

43、計算機中,并具體體現(xiàn)數(shù)據之間的邏輯結構稱為_物理（存儲）_結構。10對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有_ n+1_個指針域為空。11結構中的數(shù)據元素存在一對一的關系稱為_線性_結構。12_中序_遍歷二叉排序樹可得到一個有序序列。13如圖4所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖4 14n個元素進行冒泡法排序，通常需要進行_ n-1_趟冒泡。15如圖5所示的二叉樹，其先序遍歷序列為_ abdefcg _。gfabdec 圖5 16二叉樹為二叉排序的充分必要條件是其任一結點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_不正確_的。(回答正確或不正確) 17圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_的。(回答正確或不正確) 18根據搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷_ 兩種方法19對記錄序列排序是指按記錄的某個關鍵字排序，記錄序列按_主關鍵字_排序結果是唯一的。20按某關鍵字對記錄序列排序，若關鍵字 相等 的記錄在排序前和排序后仍保持它們的前后關系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。16423252576782102三、綜合題1（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出該堆