數(shù)據(jù)結(jié)構(gòu)（本）期末題庫及答案一、單項選擇題1數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示2數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。A只能有一個數(shù)據(jù)項組成 B至少有二個數(shù)據(jù)項組成C可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D至少有一個數(shù)據(jù)項為指針類型3從n個數(shù)中選取最大元素，（ C ）。 A基本操作是數(shù)據(jù)元素間的交換 B算法的時間復(fù)雜度是O(n2)C算法的時間復(fù)雜度是O(n) D需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較4線性表的順序結(jié)構(gòu)中，（ C ）。A邏輯上相鄰的元素在物理位置上不一定相鄰B數(shù)據(jù)元素是不能隨機訪問的C邏輯上相鄰的元素在物理位置上也相鄰D進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高5以下表中可以隨機訪問的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表6帶頭結(jié)點的單向鏈表為空的判斷條件是（ B ）（設(shè)頭指針為head）。Ahead = =NULL Bhead-next= =NULL Chead-next= =head Dhead!=NULL7 .設(shè)順序存儲的線性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ A ）。A(n+1)/2 Bn C2n Dn-i8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼9設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用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設(shè)順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法，當(dāng)i=（ C ）時，移動元素的次數(shù)為3A3 Bn/2 Cn-3 D411以下說法正確的是（ C ）。A隊列是后進(jìn)先出 B棧的特點是后進(jìn)后出C棧的刪除和插入操作都只能在棧頂進(jìn)行D隊列的刪除和插入操作都只能在隊頭進(jìn)行12 .以下說法不正確的是（ C ）。A棧的特點是后進(jìn)先出 B隊列的特點是先進(jìn)先出C棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行D隊列的插入操作在隊尾進(jìn)行，刪除操作在隊頭進(jìn)行13串函數(shù)StrCmp(“abA”,”aba”)的值為（ D ）。A1 B0 C“abAaba” D-114一個棧的進(jìn)棧序列是a，b，c，d，則棧的不可能的出棧序列是（ A ）。Aadbc BbcadCcbad Ddcba15設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中（矩陣A的第一個元素為a1,1，數(shù)組b的下標(biāo)從1開始），則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有（ A ）。A7i10 B11i15 C9i14 D6i916已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ A ）。A2m Bm C2m+1 Dm/217設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作：p=front-next;x=p-data; 然后執(zhí)行（ B ）。Afront=p-next; Bfront-next=p-next;Cfront=p; Dfront-next =p;18以下說法不正確的是（ D ）。 A連通圖G一定存在生成樹B連通圖G的生成樹中一定包含G的所有頂點C連通圖G的生成樹中不一定包含G的所有邊D連通圖G的生成樹可以是不連通的19散列查找的原理是（ A ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法20空串的長度為（ A ）。A0 B1 C2 D321排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序為止，該排序算法是( D )。 A選擇排序 B快速排序C冒泡排序 D直接插入排序 22采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/223設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣A的第一個元素為a1,1，數(shù)組b的下標(biāo)從1開始），則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是（ C ）。Ab18 Bb8 Cb13 Db1024如圖1若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為（ D ）。abecdhgf AacebdfghBaebcghdfCaedfbcghDabecdfgh 圖125已知如圖2所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ D ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca 圖226一棵哈夫曼樹總共有23個結(jié)點，該樹共有（ D ）個葉結(jié)點（終端結(jié)點）。A10 B13 C11 D12二、填空題1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性、_樹形_、_ 圖狀 四種類型。2通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_圖狀 _結(jié)構(gòu)。3設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_ p-next=head;_ _。4設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點的指針域為next，p指向尾結(jié)點的直接前驅(qū)結(jié)點，若要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作_ _ p-next=head 。 5循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)_ r=f _時表明隊列已空。6在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為_ r-next=s _；r=s；7設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作_ s-next=hs 和hs=s；8循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)_ r= =f _時表明隊列為空。 9在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為_ r-next=s _；r=s；10“A”在存儲時占_2_個字節(jié)。11串的兩種最基本的存儲方式分別是_順序存儲_和 _鏈?zhǔn)酱鎯?_。12一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有_11_個結(jié)點。13一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序 、_中序_、 _后序_三種。15兩個串相等的充分必要條件是 串長度相等且對應(yīng)位置的字符相等 。16把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。17一棵二叉樹葉結(jié)點（終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有_11_個結(jié)點。18如圖3所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖319根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷 方法。20二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_錯誤_的。(回答正確或不正確) 21一個有序表3，4，10，14，34，43，46，64，75，78，90，96，130用折半查找法查找值為90的結(jié)點，經(jīng)_4_次比較后查找成功。三、綜合題 1（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹abced （2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系。答：dbeac （3）給出該樹的前序遍歷序列答：abdec2（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95，寫出利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的 結(jié)果）答： 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）對序列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è)有一個整數(shù)序列40，28，6，72，100，3，54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （2）對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：ASL=（1x1+2x2+3x3+4）/7=18/74 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.2461673185145（2）說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。答：中序遍歷16423252576782102 5（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）初始樹 堆42826752573216102（2）寫出對上述堆對應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列答：102，52，42，82，16，67，32，57四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(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為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *front，*rear; 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 _; 期末綜合練習(xí)二 一、單項選擇題1（ B ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A數(shù)據(jù)元素 B數(shù)據(jù)對象 C數(shù)據(jù)結(jié)構(gòu) D數(shù)據(jù)項2同一種邏輯結(jié)構(gòu)（ B ）。 A只能有唯一的存儲結(jié)構(gòu) B可以有不同的存儲結(jié)構(gòu) C只能表示某一種數(shù)據(jù)元素之間的關(guān)系 D以上三種說法均不正確3設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量，且有NODE *p；為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下語句（ A ）。Ap=(NODE *)malloc(sizeof(NODE);Bp=(*NODE)malloc(sizeof(NODE);Cp=(NODE )malloc(sizeof(p);Dp=(NODE *)malloc(sizeof(p);4鏈表所具備的特點是（ C ）。A可以隨機訪問任一結(jié)點 B占用連續(xù)的存儲空間C插入刪除元素的操作不需要移動元素結(jié)點 D可以通過下標(biāo)對鏈表進(jìn)行直接訪問5設(shè)順序存儲的線性長度為n，要在第i個元素之前插入一個新元素，按課本的算法當(dāng)i= （ D ）時，移動元素次數(shù)為2An/2 Bn C1 Dn-1 6數(shù)據(jù)的物理結(jié)構(gòu)（ D ）。 A與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) B僅僅包括數(shù)據(jù)元素的表示C只包括數(shù)據(jù)元素間關(guān)系的表示 D包括數(shù)據(jù)元素的表示和關(guān)系的表示7一個棧的進(jìn)棧序列是1，2，3，4，則棧的不可能的出棧序列是（ B ）（進(jìn)出棧操作可以交替進(jìn)行）A3，2，4，1 B1，4，2，3C4，3，2，1 D3，2，1，48線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ A ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼 9設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點(該結(jié)點已被賦值)，則入隊操作為（ 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順序棧中，棧滿時再進(jìn)行進(jìn)棧操作稱為“上溢”B順序棧中，?？諘r再作出棧棧操作稱為“下溢”C順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿D順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空12算法的時間復(fù)雜度與（ C ）有關(guān)。 A所使用的計算機 B與計算機的操作系統(tǒng) C與算法本身 D與數(shù)據(jù)結(jié)構(gòu)13設(shè)有一個20階的對稱矩陣A，采用壓縮存儲方式，將其下三角部分以行序為主序存儲到一維數(shù)組中（矩陣A的第一個元素為a11，數(shù)組b的下標(biāo)從1開始），則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是（ D ）。A30 B28 C40 D3314設(shè)有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為（ B ）。 An-i+1 Bn-i Cn-i-1 Di15深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有（ D ）個結(jié)點。A28 B30 C31 D1916在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是（ C ）。 Ap=q-next Bp-next=q Cp-next=qnext Dq-next=NULL17已知一個圖的所有頂點的度數(shù)之和為m，則m一定不可能是（ D ）。A4 B8 C12 D918從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(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的生成樹可以是不連通的C連通圖G的生成樹一定是唯一的D連通圖G的生成樹一定是連通而不包含回路的20在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為（ C ）。 Ar=f-next; Br=r-next; Cf=f-next; Df=r-next;21 對n個元素進(jìn)行冒泡排序，通常要進(jìn)行n-1趟冒泡，在第j趟冒泡中共要進(jìn)行（ C ）次元素間的比較。 Aj Bj-1 Cn-j Dn-j-122一個棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ A ）（進(jìn)棧出棧可以交替進(jìn)行）。Adceab Bedcba Cdecba Dabcde 23在排序過程中，可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（ D ）。 A冒泡 B選擇 C直接插入 D折半插入 24有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A26/10 B29/10 C29/9 D31/1025如圖1若從頂點a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為（ B ）。abecdf AaebcfdBabedcfCacebdfDacfbde 圖1 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序27一棵哈夫曼樹有n個葉子結(jié)點（終端結(jié)點），該樹總共有（ B ）個結(jié)點。A2n-2 B2n-1 C2n D2n+228設(shè)有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A8,5在一維數(shù)組B中的下標(biāo)是（ A ）。A33 B32 C85 D4129數(shù)據(jù)的（ A ）結(jié)構(gòu)與所使用的計算機無關(guān)。 A邏輯 B物理 C存儲 D邏輯與存儲30在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D2 二、填空題1通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成_樹形_結(jié)構(gòu)。2棧和隊列的操作特點分別是_先進(jìn)后出_和 _先進(jìn)先出_。3要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行_ s-next= p-next；_和p-next=s;的操作。4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_圖狀 （網(wǎng)狀）_結(jié)構(gòu)。5設(shè)有一個非空的鏈棧，棧頂指針為hs，要進(jìn)行出棧操作，用x保存出棧結(jié)點的值，棧結(jié)點的指針域為next，則可執(zhí)行x=hs-data; _ hs=hs-next;_ _。6根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常可分為集合、線性、樹形 、 圖狀 四類基本結(jié)構(gòu)。7在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為data，指針域為next，若要進(jìn)行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x=f-data; _ f=f-next;_ _。8要求在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為_和 _ n-1,O(n)_ 。9循環(huán)隊列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，若隊頭指針front=4，則當(dāng)隊尾指針rear= _ 4 _時，隊列為空，當(dāng)rear= _ 2 _時，隊列有6個元素。10稀疏矩陣存儲時，采用一個由_行號_ 、_列號 _ 、_非零元_3部分信息組成的三元組唯一確定矩陣中的一個非零元素。11在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個域，它們是值域 左指針 、 右指針 。12一棵二叉樹順序編號為6的結(jié)點（樹中各結(jié)點的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點的編號相同），若它存在右孩子，則右孩子的編號為_13_。13向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行s-next=h;和_ h=s _。14在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為_ r-next=s _和r=s; (結(jié)點的指針域為next)15如圖2所示的二叉樹，其前序遍歷序列為_ abdefcg _。gfabdec 圖2 16設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有_12_個結(jié)點。（根所在結(jié)點為第1層）17在隊列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊列元素時，尾指針的值增1，當(dāng)刪除一個元素隊列時， 頭 指針的值增1。18對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的_行下標(biāo)_、_列下標(biāo)_和_非零元素值_三項信息。19循環(huán)隊列的引入，目的是為了克服 假上溢 。20在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較_3_次。三、綜合題1（1）設(shè)head1和p1分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，head2和p2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句（不用完整程序，結(jié)點的鏈域為next）。 答：p1-next= head2；p2-next= head1； （2）單向鏈表的鏈域為next，設(shè)指針p指向單向鏈表中的某個結(jié)點，指針s指向一個要插入鏈表的新結(jié)點，現(xiàn)要把s所指結(jié)點插入p所指結(jié)點之后，某學(xué)生采用以下語句： p-next=s; s-next=p-next; 這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫答：不對，s-next= p-next；p-next=s；2 (1)以2，3，4，7，8，9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹( 要求每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。33 (1)1518799854322：11103: 11114：1107：008：019：10 (2) 一棵哈夫曼樹有n個葉結(jié)點，它一共有多少個結(jié)點？簡述理由？答: 2n-1個，因為非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。3（1）畫出對長度為10的有序表進(jìn)行折半查找的判定樹（以序號1，2，10表示樹結(jié)點） 52849631071（2）對上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長度答：ASL=（1x1+2x2+3x4+4x3）/10=29/104一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84）（1）利用快速排序的方法，給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過程，要求以升序排列）初始序列 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，62，97，11，27，52，47建成堆（小根堆），畫出相應(yīng)的完全二叉樹初始樹 堆 （2）寫出對上述堆所對應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列答：11，37，47，97，77，27，62，526設(shè)查找表為(50,60,75,85,96,98,105,110,120,130) (1) 說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？ 3次(2) 為了折半查找元素95，經(jīng)過多少次元素間的比較才能確定不能查到？4次96759813010585501100512060（3）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點)四、程序填空題1以下函數(shù)為直接選擇排序算法，對a1,a2,an中的記錄進(jìn)行直接選擇排序，完成程序中的空格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以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。NODE *create(n)NODE *head , *p, *q; int i; p=(NODE*)malloc(sizeof(NODE);head= p ; q=p ;pnext=NULL; /*建立頭結(jié)點*/for(i=1; ileft) ; printf(“%c”,BT-data) ; Inorder(BT-right) ; 期末綜合練習(xí)三一、單項選擇題1深度為5的完全二叉樹共有20個結(jié)點，則第5層上有（ C ）個結(jié)點(根所在結(jié)點為第一層)。A3 B8 C5 D62在C語言中，順序存儲長度為3的字符串，需要占用（ A ）個字節(jié)。 A4 B3 C6 D123已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ A ）。A2m Bm C2m+1 Dm/24串函數(shù)StrCat（a,b）的功能是進(jìn)行串（ D ）。 A比較 B復(fù)制 C賦值 D連接5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ D ）結(jié)構(gòu)。 A物理 B存儲 C邏輯與物理 D邏輯6一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?A ）個指針域為空。 An+1 Bn Cn-1 Dn-27鏈表所具備的特點是（ C ）。A可以隨機訪問任一結(jié)點 B占用連續(xù)的存儲空間C插入刪除不需要移動元素結(jié)點 D可以通過下標(biāo)對鏈表進(jìn)行直接訪問8設(shè)一棵哈夫曼樹共有n個非葉結(jié)點，則該樹有（ B ）個葉結(jié)點。 An Bn+1 Cn-1 D2n9線性表只要以（ C ）方式存儲就能進(jìn)行折半查找。A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹10從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行（ A ）。 Ax=top-data; top=topnext; Bx=top-data; Ctop=top-next; x=top-data; Dtop=top-next; x=data;11散列查找的原理是（ A ）。A在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B按待查記錄的關(guān)鍵字有序的順序方式存儲C按關(guān)鍵字值的比較進(jìn)行查找D基于二分查找的方法12一棵完全二叉樹共有5層，且第5層上有六個結(jié)點，該樹共有（ C ）個結(jié)點。 A30 B20 C21 D2313對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（ C ）次元素間的交換，則表明序列已經(jīng)排好序。 A1 B2 C0 Dn-114在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ D ）倍。 A3 B2.5 C1.5 D215排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序為止，該排序算法是( A )。 A直接插入排序 B快速排序C冒泡排序 D選擇排序 16已知如圖1所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ A ）。 AV1V2V4V8V5V3V6V7 BV1V2V4V5V8V3V6V7CV1V2V4V8V3V5V6V7 DV1V3V6V7V2V4V5V8V6V7V1V2V3V8V4V5 圖117在對一組元素（64，48，106，33，25，82，70，55，93）進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進(jìn)行（ C ）次元素間的比較（指由小到大排序）。A6 B2 C3 D418已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ B ）。 Aabcedf Babcefd Caebcfd Dacfdebbdfeca 圖219采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ B ）次元素間的比較。 An+2 Bn Cn-1 Dn/220對二叉排序樹進(jìn)行（ C ）遍歷，可以使遍歷所得到的序列是有序序列。 A按層次 B后序 C中序 D前序21如圖3，若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為（ B ）。 Aacebdgf BabecdgfCacfedgbDabecfdg abecdfg 圖322在有序表2，4，7，14，34，43，47，64，75，80，90，97，120中，用折半查找法查找值80時，經(jīng)（ B ）次比較后查找成功。A4 B2 C3 D523元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ D ）（進(jìn)棧出棧可以交替進(jìn)行）。 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，424有一個長度為9的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ B ）。A25/10 B25/9 C20/9 D17/925排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ C ）排序。 A歸并 B插入 C選擇 D快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ C ）。 A冒泡 B直接插入 C折半插入 D選擇排序27一棵哈夫曼樹總共有23個結(jié)點，該樹共有（ D ）個葉結(jié)點（終端結(jié)點）A10 B13 C11 D1228一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ 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 ）進(jìn)行。 A隊頭 B隊尾 C隊頭或隊尾 D在任意指定位置 二、填空題（每小題2分，共24分）1一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有_11_個結(jié)點。2在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個域，它們是_值域_、 左指針 、右指針。3設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有_21_個結(jié)點。4一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為_2i _、_2i+1_。5按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_先序_ 、_中序 _、 _后序_三種。6串的兩種最基本的存儲方式是_順序存儲_和 _鏈?zhǔn)酱鎯。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_樹形_結(jié)構(gòu)。8一棵有2n-1個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_N_個葉結(jié)點。9把數(shù)據(jù)存儲到計算機中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_物理（存儲）_結(jié)構(gòu)。10對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有_ n+1_個指針域為空。11結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_線性_結(jié)構(gòu)。12_中序_遍歷二叉排序樹可得到一個有序序列。13如圖4所示的二叉樹，其后序遍歷序列為 gdbeihfca 。efgibachd 圖4 14n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行_ n-1_趟冒泡。15如圖5所示的二叉樹，其先序遍歷序列為_ abdefcg _。gfabdec 圖5 16二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_不正確_的。(回答正確或不正確) 17圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確_的。(回答正確或不正確) 18根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、 _廣度優(yōu)先搜索遍歷_ 兩種方法19對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按_主關(guān)鍵字_排序結(jié)果是唯一的。20按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字 相等 的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。16423252576782102三、綜合題1（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出該堆