電大《數(shù)據(jù)結(jié)構(gòu)(本)》復(fù)習(xí)題與答案

...wd......wd......wd...數(shù)據(jù)構(gòu)造(本)復(fù)習(xí)題一、單項選擇題(每題2分，共30分)1．深度為5的完全二叉樹共有20個結(jié)點，則第5層上有()個結(jié)點(根所在結(jié)點為第一層)。A．3B．8C．5D．62．一個圖的邊數(shù)為ii，則該圖的所有頂點的度數(shù)之和為()。A．2mB．mC．2m+1D．3．?dāng)?shù)據(jù)構(gòu)造中，與所使用的計算機無關(guān)的是數(shù)據(jù)的()構(gòu)造。A．物理B．存儲C．邏輯與物理D．邏輯4．鏈表所具備的特點是()。A．可以隨機訪問任一結(jié)點 B．占用連續(xù)的存儲空間C．插人刪除不需要移動元素結(jié)點D．可以通過下標(biāo)對鏈表進展直接訪問5．線性表只要以()方式存儲就能進展折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D．二又樹6．散列查找的原理是()。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建設(shè)確定的對應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲C．按關(guān)鍵字值的比擬進展查找D．基于二分查找的方法7．對n個元素進展冒泡排序假設(shè)某趟冒泡中只進展了()次元素間的交換，則說明序列已經(jīng)排好序。A．1B．2C．0D．n-18．排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序為止，該排序算法是()。A．直接插入排序B．快速排序C．冒泡排序D．選擇排序9．在對一組元素(64,48,106,33,25,82,70,55,93)進展直接插入排序時，當(dāng)進展到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插人位置，需進展()次元素n的比擬(指由小到大排序)。A．6B．2C．3D．410．采用順序查找法對長度為n的線性表進展查找(不采用表尾設(shè)監(jiān)視哨的方法)，最壞的情況下要進展()次元素間的比擬。A．n+2B．nC．n-1D．n/211如圖，假設(shè)從頂點a出發(fā)按廣度優(yōu)先搜索法進展遍歷，則可能得到的頂點序列為()。A．a(chǎn)cebdgfB．a(chǎn)becdgfC．a(chǎn)cfedgbD．a(chǎn)becfdg12．元素2,4,6,8按順序依次進棧，則該棧的不可能輸出序列是()(進棧出?？梢越惶孢M展)。A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，413．排序方法中，從未排序序列中挑選元素，并將其依次放人已排序序列(初始為空)的一端的方法，稱為()排序。A．歸并B．插人C．選擇D．快速I4．一棵哈夫曼樹總共有23個結(jié)點，該樹共有()個葉結(jié)點(終端結(jié)點)。A．10B．13C．11D．1215．隊列的插人操作在()進展。A．隊頭B．隊尾C．隊頭或隊尾D．在任意指定位置二、填空題(每題2分。共24分)16．一棵二又樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有___________個結(jié)點。17．設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10，該完全二又樹一共有___________個結(jié)點。18．按照二又樹的遞歸定義，對二叉樹遍歷的常用算法有先序、___________、___________三種。19．構(gòu)造中的數(shù)據(jù)元素存在一對多的關(guān)系稱為___________構(gòu)造。20．把數(shù)據(jù)存儲到計算機中，并具體表達數(shù)據(jù)之間的邏輯構(gòu)造稱為___________構(gòu)造。21．構(gòu)造中的數(shù)據(jù)元素存在一對一的關(guān)系稱為___________構(gòu)造。22．如圖2所示的二又樹，其后序遍歷序列為______________________。23．n個元素進展冒泡法排序，通常需要進展____________趟排序。24．二叉樹為二又排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是____________的。(答復(fù)正確或不正確)25．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是____________的。(答復(fù)正確或不正確)26．根據(jù)搜索方法的不同，圖的遍歷有______________________、______________________兩種方法。27．按某關(guān)鍵字對記錄序列排序，假設(shè)關(guān)鍵字___________的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題(每題10分，共30分)28．(1)利用篩選過程把序列{42,82,67,102,16,32,57,52}建成堆(小根堆)，畫出該堆(不要求中間過程)。(2)寫出對上述堆對應(yīng)的完全二又樹進展中序遍歷得到的序列。29．設(shè)查找表為(16,15,20,53,64,7)，(1)用冒泡法對該表進展排序(要求升序排列)，要求寫出每一趟的排序過程。(2)在排序后的有序表的根基上，畫出對其進展折半查找所對應(yīng)的判定樹。(要求以數(shù)據(jù)元素作為樹結(jié)點)。(3)求在等概率條件下，對上述有序表成功查找的平均查找長度。30．(1)設(shè)有一個整數(shù)序列(50,38,16,82,110,13,64}，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹。(2)．利用上述二叉排序樹，為了查找110，經(jīng)多少次元素間的比擬能成功查到，為了查找15，經(jīng)多少次元素間的比擬可知道查找失敗?四、程序填空題(每空2分，共16分)31．以下函數(shù)為鏈隊列的入隊操作，X為要人隊的結(jié)點的數(shù)據(jù)域的值，front,rear分別是鏈隊列的隊頭、隊尾指針32．以下函數(shù)在head為頭指針的具有頭結(jié)點的單向鏈表中刪除第1個結(jié)點，參考答案一、單項選擇題(每題2分，共30分}CADCCACACBBDCDB二、填空題(每題2分，共24分)16．1117．2118．中序 后序19．樹形20．物理(存儲)21．線性22．gdbeihfca23．N-124．不正確25．正確26．深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷27．相等三、綜合應(yīng)用題(每題10分，共30分)28．(1)(2)．102，52，42，82，16，6?，32，5729．．(1)原序列16 15 20 53 64 71516205376415162075364151672053641571620536471516205364(2)(3)平均查找長度=(1*1+2*2+3*3)/6=14/630．(1)(2)三次，四次四、程序填空題(每空2分，共16分)31．(1)malloc(sizeof(structnode))(2)rear->next=p(3)p32．(1)j<i-1(2)q=q->next(3)q->next(4)q->next(5)p一、單項選擇題〔每題2分，共30分〕1．?dāng)?shù)據(jù)的物理構(gòu)造()。A．與數(shù)據(jù)的邏輯構(gòu)造無關(guān)B．僅僅包括數(shù)據(jù)元素的表示C．只包括數(shù)據(jù)元素間關(guān)系的表示D．包括數(shù)據(jù)元素的表示和關(guān)系的表示2．從n個數(shù)中選取最大元素()。A．根本操作是數(shù)據(jù)元素間的交換B．算法的時間復(fù)雜度是O(n2)C．算法的時間復(fù)雜度是O(n)D．需要進展(n+1)次數(shù)據(jù)元素間的比擬3．線性表的順序構(gòu)造中，()。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D．進展數(shù)據(jù)元素的插入、刪除效率較高4．帶頭結(jié)點的單向鏈表為空的判斷條件是()(設(shè)頭指針為head)。A．head==NULLB．head->next==NULLC．head->next==headD．head!=NULL5．線性構(gòu)造中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A．一對一 B．一對多C．多對多D．每一個元素都有-個直接前驅(qū)和一個直接后繼6．設(shè)順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法，當(dāng)i=()，移動元素的次數(shù)為3。A．3B．n/2C．n-3D．47．以下說法不正確的選項是()。A．棧的特點是后進先出B．隊列的特點是先進先出C棧的刪除操作在棧底進展，插入操作在棧頂進展B隊列的插入操作在隊尾進展，刪除操作在隊頭進展8．一個棧的進棧序列是a，h，c，d，則棧的不可能的出棧序列是()。A．a(chǎn)dbcB．beadC．cbadD．dcba9．設(shè)top是一個鏈榜的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收棧頂元素，則出棧操作為()。A．x=top->data;top=top->next;B．top=top->next;x=top->data;C．x=top->next;top=top->data;D．top->next=top;x=top->data;10．設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作:p=front->next;x=p->data;然后執(zhí)行()。A．front=p->next;B．front->next=p->next;C．front=p;D．front->next=p;11．以下說法正確的選項是()。A．隊列是后進先出B．棧的特點是后進后出C．?dāng)n的刪除和插入操作都只能在棧頂進展D．隊列的刪除和插入操作都只能在隊頭進展12．在C語言中，存儲字符串"ABCD"需要占用()字節(jié)。A．4B．2C．5D．313．串函數(shù)StrCmp("abA"，"aba")的值為()。A．1B．0C．"abAaba"D．-114．設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角局部以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為al,l，數(shù)組b的下標(biāo)從1開場)，則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是()。A．b[18]B．b[8]C．b[13]D．b[lO]15．如圖1所示的一個圖，假設(shè)從頂點a出發(fā)，按深度優(yōu)先搜索法進展遍歷，則可能得到的一種頂點序列為()。A．a(chǎn)becdfB．a(chǎn)cfebdc．a(chǎn)ebcfdD．a(chǎn)edfcb二、填空題{每小黯2分，共24分}16．通常數(shù)據(jù)的邏輯構(gòu)造包括集合、線性、________________、________________四種類型。17．通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成_________________構(gòu)造。18．設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_________________。19．循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)_________________時說明隊列已空。20．設(shè)有一個鏈錢，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作_________________和hs=s。21．在-個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為_________________；r=s。22．串的兩種最根本的存儲方式分別是_________________和_________________。23．一棵二叉樹中順序編號為i的結(jié)點，假設(shè)它存在左、右孩子，則左、右孩子編號分別為_________________、_________________。24．兩個串相等的充分必要條件是___________________________________________________。25．一棵二叉樹葉結(jié)點〈終端結(jié)點〉數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有____________個結(jié)點。26．根據(jù)搜索方法的不同，圖的遍歷有__________________________________、__________________________________兩種方法。27．一個有序表{3，4，10，14，34，43，46，64，75，78，90，96，130}用折半查找法查找值為90的結(jié)點，經(jīng)_________________次比擬后查找成功。三、綜合題〔每題10分，共30分〕28．(1)某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹。(2)假設(shè)上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系。(3)給出該樹的前序遍歷序列。29．(1)一組記錄的關(guān)鍵字序列為{45，40，65，43，35，95}，寫出利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果(要求給出一趟劃分中每次掃描和交換的結(jié)果〉。(2)對序列{45，40，65，43，35，95}利用直接插入排序，寫出逐次插入過程(從第一個元素一直到第六個元素〉。30．(1)設(shè)有查找表{5，14，2，6，18，7，4，16，3}，依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。四、程序填空題〔每空2分，共16分〕31．以下函數(shù)在a[O]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格。32．以下函數(shù)為鏈棧的進棧操作，x是要進棧的結(jié)點的數(shù)據(jù)域，top為錢頂指針參考答案一、單項選擇題〔每題2芳，共30分〕DCCBACCAABCCDCD二、填空題〔每題2分，共24分}16．樹形、圖狀17．圖狀18．p->next=head;19．r=f20．在>next=hs;21．r->next=的22．順序存儲、鏈?zhǔn)酱鎯?3．2i、2i+124．串長度相等且對應(yīng)位置的字符相等26．深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷27．4三、結(jié)合應(yīng)用題〔每題10分，共30分〕28．(1)(2)d<b<e<a<c(3)abdec四、程序填空題〔每空2分，共16分〕一、單項選擇題(每題2分，共30分)1.()是性質(zhì)一樣的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A.數(shù)據(jù)元素 B.數(shù)據(jù)對象C.數(shù)據(jù)構(gòu)造 D.數(shù)據(jù)項2.設(shè)鏈表中的結(jié)點是NODE類型的構(gòu)造體變量，且有NODE頭P;為了申請一個新結(jié)點，并由p指向該結(jié)點，可用以下語句()。A.p=(NODE*)malloC{sizeof(NODE); B.p=(*ODE)malloC(sizeof(NODE));C.p=(NODE)malloC(sizeof(p)) D.p=(NODE*)malloC(sizeof(p));3.設(shè)順序存儲的線性表長度為n，要在第i個元素之前插入一個新元素，按課本的算法當(dāng)i=()時，移動元素次數(shù)為2。A.n/2B.nC.1D.n-l4.一個棧的進棧序列是1，2，3，4，則棧的不可能的出棧序列是()(進出棧操作可以交替進展)。A.3,2,4,1B.1,4,2,3C.4,3,2,1D.3,2,1,45.設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點〔該結(jié)點已被賦值),則入隊操作為()。A.rear->next=p;rear=p; B.rear->next=p;p=rear;C.p=rear->next;rear=p;D.rear=p;rear->next=p;6.以下說法不正確的選項是()。A.順序校中，錢滿時再進展進校操作稱為"上溢"B.順序校中，找空時再作出校校操作稱為"下溢"C.順序隊列中，當(dāng)尾指針已經(jīng)超越隊列存儲空間的上界，則一定是隊列已滿D.順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空7.設(shè)有一個20階的對稱矩陣A，采用壓縮存儲方式，將其下三角局部以行序為主序存儲到一維數(shù)組中(矩陣A的第一個元素為a11，數(shù)組b的下標(biāo)從1開場)，則矩陣元素a8,5在一維數(shù)組b中的下標(biāo)是()。A.30B.28C.40D.338.深度為5的完全二叉樹第5層上有4個結(jié)點，該樹一共有()個結(jié)點。A.28B.30C.31D.199.一個圖的所有頂點的度數(shù)之和為m，則m一定不可能是()。A.4B.8C.12D.910.以下說法正確的選項是()。A.連通圖G的生成樹中可以包含回路 B.連通圖G的生成樹可以是不連通的C.連通圖G的生成樹一定是唯一的 D.連通圖G的生成樹一定是連通而不包含回路的11.對n個元素進展冒泡排序，通常要進展n-l趟冒泡，在第j趟冒泡中共要進展()次元素間的比擬。A.jB.j-lC.n-jD.n-j-l12.在排序過程中，可以有效地減少一趟排序過程中元素間的比擬次數(shù)的算法是()。A.冒泡 B.選擇C.直接插入 D.折半插入13.如圖假設(shè)從頂點a出發(fā)按深度優(yōu)先搜索法進展遍歷，則可能得到的頂點序列為()。A.aebCfdB.abedCfC.aCebdfD.aCfbde14.一棵哈夫曼樹有n個葉子結(jié)點(終端結(jié)點)，該樹總共有()個結(jié)點。A.2n-2B.2n-lC.2n D.2n十215.數(shù)據(jù)的()構(gòu)造與所使用的計算機無關(guān)。A.邏輯 B.物理C.存儲 D.邏輯與存儲二、填空題(每題2分，共24分)1.通?？梢园岩槐竞胁煌鹿?jié)的書的目錄構(gòu)造抽象成____________構(gòu)造。2.要在一個單向鏈表中p所指向的結(jié)點之后插入一個S所指向的新結(jié)點，假設(shè)鏈表中結(jié)點的指針域為next，可執(zhí)行____________和p->next==s的操作。3.設(shè)有一個非空的鏈棧，棧頂指針為hs，要進展出棧操作，用x保存出棧結(jié)點的值，找結(jié)點的指針域為next，則可執(zhí)行x=hs一>data;________________________。4.在一個不帶頭結(jié)點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的數(shù)據(jù)域為data，指針域為next，假設(shè)要進展出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，則相關(guān)操作為x=f->data;________________________。5.循環(huán)隊列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷?？栈驐M，假設(shè)隊頭指針front=4，則當(dāng)隊尾指針rear=____________時，隊列為空，當(dāng)rear=____________時，隊列有6個元素。6.稀疏矩陣存儲時，采用一個由____________、____________、非零元3局部信息組成的三元組唯一確定矩陣中的一個非零元素。7.一棵二叉樹順序編號為6的結(jié)點(樹中各結(jié)點的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點的編號一樣)，假設(shè)它存在右孩子，則右孩子的編號為____________。8.數(shù)據(jù)構(gòu)造中的數(shù)據(jù)元素存在多對多的關(guān)系稱為____________構(gòu)造o9.數(shù)據(jù)構(gòu)造中的數(shù)據(jù)元素存在一對多的關(guān)系稱為____________構(gòu)造。10.如以下列圖所示的二叉樹，其前序遍歷序列為____________11.在隊列的順序存儲構(gòu)造中，當(dāng)插入一個新的隊列元素時，____________指針的值增1，當(dāng)刪除一個元素隊列時，____________指針的值增1。12.循環(huán)隊列的引入，目的是為了抑制____________________________________。三、綜合題(每題10分，共30分)1.(1)設(shè)head1和P1分別是不帶頭結(jié)點的單向鏈表A的頭指針和尾指針，head2和P2分別是不帶頭結(jié)點的單向鏈表B的頭指針和尾指針，假設(shè)要把B鏈表接到A鏈表之后，得到一個以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個關(guān)鍵的賦值語句(不用完整程序，結(jié)點的鏈域為next)(2)單向鏈表的鏈域為next，設(shè)指針p指向單向鏈表中的某個結(jié)點，指針S指向一個要插入鏈表的新結(jié)點，現(xiàn)要把s所指結(jié)點插入p所指結(jié)點之后，某學(xué)生采用以下語句:p->next==s;s->next==p->next;這樣做正確嗎?假設(shè)正確則答復(fù)正確，假設(shè)不正確則說明應(yīng)如何改寫。2.(1)畫出對長度為10的有序表進展折半查找的判定樹(以序號1，2，……10表示樹結(jié)點)。(2)對上述序列進展折半查找，求等概率條件下，成功查找的平均查找長度。3.(1)利用篩選法，把序列{37，77，62，97，11，27，52，47}建成堆(小根堆)。畫出相應(yīng)的完全二叉樹。(2)寫出對上述堆所對應(yīng)的二叉樹進展前序遍歷得到的序列。四、程序填空題(每空2分，共16分)1.以下函數(shù)為直接選擇排序算法，對a[口，a[幻，…a[n]中的記錄進展直接選擇排序，完成程序中的空格。2.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格局部(樹構(gòu)造中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點。參考答案一、單項選擇題(每題2分，共30分)BADBACDDDDCDBBA二、填空題(每題2分，共24分)1.樹形2.s->next===p->next;3.hs===hs一>next;4.f===f一>next;5.426.行號列號7.138.圖狀9.樹形10.abdefCg11.尾頭12.假上溢三、綜合應(yīng)用題(每題10分，共30分)四、程序填空題(每空2分，共16分)1.(l)n-l(2)n(3)k==j(4)a[i]==a[k](5)a[k]==temp2.(1)Inorder(BT->left)(2)printf("%C"，BT->data)(3)Inorder(B1-"->right)一、單項選擇題〔每題2分，共30分〕1.數(shù)據(jù)元素是數(shù)據(jù)的3根本單位，它( )。A.只能有一個數(shù)據(jù)項組成 B.至少有二個數(shù)據(jù)項組成C.可以是一個數(shù)據(jù)項也可以由假設(shè)干個數(shù)據(jù)項組成 D.至少有一個數(shù)據(jù)項為指針類型2.絨性表的順序構(gòu)造中，( )。A邏輯上相鄰的元素在物理位置上不一定相鄰 B.數(shù)據(jù)元素是不能隨機訪問的C.邏輯上相鄰的元素在物理位置上也相鄰 D.進展數(shù)據(jù)元素的插入、刪除效率較高3.以下表中可以隨機訪問的是( )。A.單向鏈表 B.雙向鏈表C.單向循環(huán)鏈表 D.順序表4.設(shè)順序存儲的錢性表長度為n，對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為()。A.(n+1)/2B.nC.2nD.n-i5.設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，設(shè)用x接收樓頂元素，則出棧操作為( )。A.x=top->data；top=top->next； B.top=top->next；x=top->data；C.x=top->next；top=top->data； D.top->next=top；x=top->data；6.以于說法正確的選項是()。A.隊列是后進先出 B.棧的特點是后進后出C．棧的刪除和插入操作都只能在棧頂進展 D．隊列的刪除和捶入操作都只能在隊頭進展7.串函數(shù)StrCmp("b"，"cd")的值為()。A.1 B.0C."bcd"D.-18.設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角局部以行序為主存儲如一維數(shù)組b中〈矩陣A的第一個元素為al,l，數(shù)組b的下標(biāo)從1開場)，則矩陣A中第4行的元素在數(shù)組b中的下標(biāo)i一定有( )。9.一個圖的邊數(shù)為m.則該圖的所有頂點的度數(shù)之和為()。A.2mB.mC.2m+1 D.m/210.以下說法不正確的選項是()。A.連通圖G一定存在生成樹B.連通圈G的生成樹中一定包含G的所有頂點C.連通圖G的生成制中不一定包含G的所有邊D.連通圖G的生成樹可以是不連同的11.散列查找的原理是()。A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建設(shè)確定的對應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲C.按關(guān)鍵字值的比擬進展查找D.基于二分查找的方法12.排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序為止，該排序算法是()。A．直接插入排序B.快速排序fC.冒泡排序D.選擇排序13.采用順序查找法對長度為n的線性表進展查找〈不采用表尾設(shè)監(jiān)視哨的方法)，最壞的情況下要進展()次元素間的比擬。A.n+2B.nC.n-l D.n/214.如圖假設(shè)從頂點a出發(fā)按廣度優(yōu)先搜索法進展遍歷，則可能得到的頂點序列為()。A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh15.一棵哈夫曼樹總共有23個結(jié)點，該樹共有()個葉結(jié)點(終端結(jié)點〉。A.10B.13C．11D.121363i二、填空題{每小黯2分，共24分}1.通常數(shù)據(jù)的邏輯構(gòu)造包括____________、___________、___________、____________四種類型。2.設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_______________________________________。3.設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點的指針域為next，p指向尾結(jié)點的直接前驅(qū)結(jié)點，假設(shè)要刪除尾結(jié)點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作____________________________。4.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為______________；r=s。5.循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)_________