數(shù)據(jù)結(jié)構(gòu)本期末綜合練習(xí)6月

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)1.在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計算機(jī)有關(guān)的是（B）。A．?dāng)?shù)據(jù)元數(shù)間的抽象關(guān)系B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)C．算法的時間復(fù)雜度D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2.一種邏輯結(jié)構(gòu)在存儲時（C）。A．只要存儲數(shù)據(jù)元素間的關(guān)系B．只能采用一種存儲結(jié)構(gòu)C．可采用不同的存儲結(jié)構(gòu)D．只要存儲數(shù)據(jù)元素的值3.對順序表,以下敘述中正確的是(A)。A．用一組地址連續(xù)的存儲單元依次存放線性表的數(shù)據(jù)元素B．各個數(shù)據(jù)元素的首地址是連續(xù)的C．?dāng)?shù)據(jù)元素不能隨機(jī)訪問D．插入操作不需要移動元素4.對鏈表,以下敘述中正確的是（A）。A．不能隨機(jī)訪問任一結(jié)點(diǎn)B．結(jié)點(diǎn)占用的存儲空間是連續(xù)的C．插入刪除元素的操作一定要要移動結(jié)點(diǎn)D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問5．設(shè)有一個長度為25的順序表，要刪除第10個元素(下標(biāo)從1開始),需移動元素的個數(shù)為（C）。A．9B．10C．15D．6．線性表在存儲后,如果相關(guān)操作是:要求已知第i個結(jié)點(diǎn)的位置訪問該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用（A）存儲方式是不可行的。A．單鏈表B．雙鏈表C．單循環(huán)鏈表D．順序表7.設(shè)單向鏈表中,指針p指向結(jié)點(diǎn)A，若要刪除A的直接后繼，則所需修改指針的操作為(A)。A.p->next=p->next->next;B.p=p->next;C.p=p->next->next; D.p->next=p;8．棧和隊列的共同特點(diǎn)是（C）。A都是先進(jìn)后出B元素都可以隨機(jī)進(jìn)出C只容許在端點(diǎn)處插入和刪除元素D都是先進(jìn)先出9．元素1，3，5，7按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊列，該隊列的可能輸出序列是（A）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．7，5，3，1B．7，3，1,5C．7，5，1，3D．5,1，3，710．元素2，4，6，8按順序依次進(jìn)棧，按該棧的的可能輸出序列依次入隊列，該隊列的可能輸出序列是（D）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．8，6，2，4B．8，4，2，6C．6，2，4，8D．8，6，4，211．對一個棧頂指針為top的鏈棧進(jìn)行進(jìn)棧操作，設(shè)P為待進(jìn)棧的結(jié)點(diǎn)，則執(zhí)行（C）。A．p=top->next;top=topnext;B．p->next=top;C．p->next=top;top=p;D．top=p;12．在一個不帶頭結(jié)點(diǎn)的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則從該對列中刪除一個結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x中的運(yùn)算為（C）。A．x=rdata；r=rnext;B．r=rnext;x=rdataC．x=fdata；f=fnext;D．f=fnext;x=fdata13．設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第33號元素對應(yīng)于矩陣中的元素是（D）。(矩陣中的第1個元素是a1,1）A．a(chǎn)7,6B．a(chǎn)10,8C．a(chǎn)9,2D14．設(shè)有一個20階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第38號元素對應(yīng)于矩陣中的元素是（C）。(矩陣中的第1個元素是a1,1）A．a(chǎn)10,8B．a(chǎn)7,6C．a(chǎn)9,2D．a(chǎn)15．設(shè)有一個17階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a10,6在一維數(shù)組B中的下標(biāo)是（C）。(矩陣中的第1個元素是a1,1）A．45,B．18C16．在C語言中，分別存儲“S”和‘s’，各需要占用（D）字節(jié)。A．一個和兩個B．兩個C．一個D．兩個和一個17．串函數(shù)StrCmp（“ABCd”，“ABCD”）的值為（C）。A．0B．-118．一棵有n個結(jié)點(diǎn)，采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（C）個指針域被有效使用（即指針域?yàn)榉强眨?。A．n+1B．nC．n-1D．n-219．一棵采用鏈?zhǔn)酱鎯Φ亩鏄渲杏衝個指針域?yàn)榭?該二叉樹共有（C）個結(jié)點(diǎn)。A．n+1B．nC．n-1D．n-220．在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在雙親結(jié)點(diǎn)，則雙親結(jié)點(diǎn)的順序編號為（B）。A．i/2.0B．i/2向下取整C．2i+1D．i+221．設(shè)一棵哈夫曼樹共有n個非葉結(jié)點(diǎn)，則該樹有（D）個結(jié)點(diǎn)。A．2nB．2n+2C．2n-1D．2n+122．設(shè)一棵哈夫曼樹共有2n+1個結(jié)點(diǎn)，則該樹有（A）個非葉結(jié)點(diǎn)。A．nB．n+1C．n-123．一棵結(jié)點(diǎn)數(shù)31<n<40的完全二叉樹，最后一層有4個結(jié)點(diǎn)，則該樹有（A）個葉結(jié)點(diǎn)A．18B．17C．3624．一棵完全二叉樹共有4層，且第4層上有2個結(jié)點(diǎn)，該樹共有（B）個非葉子結(jié)點(diǎn)(根為第一層)。A．5B．4C．325．已知如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（A）。A．a(chǎn)bedfcB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfbcbbdfeca圖126．如圖2所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（C）。A．a(chǎn)bedfcB．a(chǎn)cfebdC．a(chǎn)ebcdfD．a(chǎn)ebcfdbbdfeca圖227．一組記錄的關(guān)鍵字序列為（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（B）。A．20,30,40，38，46，79，56，84,90,100B．40，20,30,38，46，56，79，84,90,110C．30,20,40，38，46，84，56，79,90,100D．20,3038，40，46，56，79，84,90,10028．一組記錄的關(guān)鍵字序列為（56，30,89，66，48，50，94,87,100），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（B）。A．30，50,48，56，66，89，94,100,87B．50，30,48，56，66，89，94,87,100C．48，30,50，56，66，89，94,87,100D．50，30,48，66，56，89，94,87,10029．一組記錄的關(guān)鍵字序列為（75，63，95，80，53，45，38，20），利用堆排序（堆頂元素是最大元素）的方法建立的初始堆為（A）。A．95，80，75，63，53，45，38，20B．95，63，75，80，53，45，38，20c.95,80,45,63,53,75,38,20D．95,80,75,20,53,45,38,6330．線性表以（C）方式存儲，能進(jìn)行折半查找。A．關(guān)鍵字有序的鏈接B．順序C．關(guān)鍵字有序的順序D．?dāng)?shù)組二、填空題1．?dāng)?shù)據(jù)元素之間的抽象關(guān)系稱為___邏輯___結(jié)構(gòu)。2.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示稱為__物理__結(jié)構(gòu)。3．要求在n個數(shù)據(jù)元素中找值最大的元素，其基本操作為__元素間的比較__。算法的時間復(fù)雜度為_O(n)__。4.求兩個n階矩陣的乘積，算法的基本操作為__乘法__，時間復(fù)雜度為__O(n3)__。5．設(shè)有一個長度為25的順序表,第8號元素到第25號元素依次存放的值為8,9,10,11,…,25，某人想要刪除第8個元素，他的做法是從第25號元素開始,直到第9號元素依次向前移動1個位置,其結(jié)果新表中第9號元素的值為（25）。6．設(shè)有一個長度為25的順序表,第8號元素到第25號元素依次存放的值為8,9,10,11,…25,某人想要在第8個元素前插入1個元素7（也就是插入元素作為新表的第8個元素），他的做法是從第8號元素開始,直到第25號元素依次向后移動1個位置,然后把7存放在8號位置，其結(jié)果是新表中第25號元素的值為（8）。7．在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)(設(shè)q所指的結(jié)點(diǎn)已賦值)，可以先用語句q->next=p->next;（p->next）->prior=q；然后再用語句q->prior=p;和語句_p->next=q；_。8．在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)(設(shè)q所指的結(jié)點(diǎn)已賦值)，其中所用的一條語句（p->next）->prior=q；的功能是使P所指結(jié)點(diǎn)的_直接前驅(qū)的左指針_指向q。9．在一個單向鏈表中，要刪除p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。則可以用操作__p->next=p->next->next;_。（用一條語句）10．設(shè)有一個帶頭結(jié)點(diǎn)的，頭指針為head的單向鏈表，p指向表中某一個結(jié)點(diǎn)，且有p->next==NULL,現(xiàn)要刪除頭結(jié)點(diǎn)，并使該單向鏈表構(gòu)造成單向循環(huán)鏈表，通過操作head=head->next;__p->next=head;_。11．向一個棧頂指針為top的鏈棧中插入一個p所指結(jié)點(diǎn)時，可執(zhí)行_p->next=top;top=p；_操作。(填兩條語句,結(jié)點(diǎn)的指針域?yàn)閚ext)12．從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用d保存被刪結(jié)點(diǎn)的值，可執(zhí)行__d=top->data;top=top->next;_。(結(jié)點(diǎn)的指針域?yàn)閚ext,數(shù)據(jù)域?yàn)閐ata)13．在一個帶頭結(jié)點(diǎn)的鏈隊中，設(shè)front和rear分別為隊頭和隊尾指針，則刪除一個結(jié)點(diǎn)的操作為p=front->next;__front->next__=p->next;(結(jié)點(diǎn)的指針域?yàn)閚ext,p為輔助用指針)14.循環(huán)鏈隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為MaxSize,采用少用一個元素的模式),判斷循環(huán)鏈隊列為滿的條件為__front==(rear+1)%MaxSize__。15．設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，最后一個元素的下標(biāo)為27，則n=__7__。(矩陣中的第1個元素是a1,1）16．對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個元素,則矩陣A共有___34__個零元素。17.一棵3度的樹，其中3度結(jié)1個，2度結(jié)2個，1度結(jié)2個，則該樹共有_5__個葉結(jié)點(diǎn)。18.一棵有8個權(quán)重值構(gòu)造的哈夫曼數(shù)，共有15個結(jié)點(diǎn)。19．一棵有7個葉結(jié)點(diǎn)的二叉樹，其1度結(jié)點(diǎn)數(shù)的個數(shù)為2，則該樹共有____15___個結(jié)點(diǎn)20．一棵有18個結(jié)點(diǎn)的二叉樹，其2度結(jié)點(diǎn)數(shù)的個數(shù)為8，則該樹共有____1___個1度結(jié)點(diǎn)21．如圖3所示的二叉樹，其中序遍歷序列為____512389746_____。3c3c7gd65e4dc2b18hd9圖322．如圖4所示的二叉樹，其先序遍歷序列為____215347896_____。3c7g3c7gd65e4dc2b18hd9圖423．二叉排序樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹非空，則左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值；若它的右子樹非空，則右子的所有結(jié)點(diǎn)的值都大于（若允許結(jié)點(diǎn)有相同的值，則大于等于）它的根結(jié)點(diǎn)的值。這種說法是__不正確__的。(回答正確或不正確)24．在查找表中，通過記錄的某關(guān)鍵字能唯一地確定一個記錄，該關(guān)鍵字稱為__主關(guān)鍵字__。三、綜合題1．(1)以3，4，5，8，9，10作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(3)一棵哈夫曼樹有2n-1個結(jié)點(diǎn)，它是共有多少個權(quán)重值構(gòu)造而成的？簡述理由？(1)1091098791293543933171552218圖7(2)300004000150011001810911（3）n個，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個,而權(quán)值個數(shù)=葉結(jié)點(diǎn)數(shù)2．（1）對給定權(quán)值3，1，4，4，5，6，構(gòu)造深度為5的哈夫曼樹。(設(shè)根為第1層)(2)求樹的帶權(quán)路徑長度。（3）鏈接存儲上述哈夫曼樹，結(jié)點(diǎn)中共有多少個指針域?yàn)榭?說明理由.(1)6565435423418145197896434531213圖8（2)WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3)共11個結(jié)點(diǎn),22個指針域,除根結(jié)點(diǎn)外,每個結(jié)點(diǎn)對應(yīng)一個指針域.,共10個指針域非空,故有22-10=12個空指針域,3．（1）簡述拓?fù)渑判虻牟襟E。（2）說明有向圖的拓?fù)湫蛄胁灰欢ㄊ俏ㄒ坏脑?。?）如何利用拓?fù)渑判蛩惴ㄅ卸▓D是否存在回路。（4）設(shè)有向圖G如下，寫出首先刪除頂點(diǎn)1的3種拓?fù)湫蛄小?1234543465圖5(1)循環(huán)執(zhí)行以下兩步選擇一個度為0的頂點(diǎn)并輸出從網(wǎng)中刪除此結(jié)點(diǎn)及所有出邊（2）因?yàn)檫x擇一個度為0的頂點(diǎn)時不一定是唯一的（3）由頂點(diǎn)活動網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程中，輸出結(jié)點(diǎn)后，余下的結(jié)點(diǎn)均有前驅(qū)(4)1523641526341562344.(1)如下的一棵樹,給出先序遍歷序列(2)把1,2,3,4,5,6,7,8,9填人,使它成為一棵二叉排序樹提示：設(shè)圖中的樹是二叉排序樹，找出中序遍歷序列與1，2，…9的對應(yīng)關(guān)系(3)請在該樹中再插入一個結(jié)點(diǎn)3.5作為葉結(jié)點(diǎn)，并使它仍然是一棵二叉排序樹。A1A2A1A2A43A7A5A9A8A3A6(1)A1A2A(2)(3)747421563893.55．設(shè)有序表為（21，22，23，24，25，26，27，28，29，30，31,32），元素的下標(biāo)從0開始。（1）說出有哪幾個元素需要經(jīng)過4次元素間的比較才能成功查到。（2）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹（樹結(jié)點(diǎn)用數(shù)值表示）（3）設(shè)查找元素為5，需要進(jìn)行多少次元素間的比較才能確定不能查到。（4）求在等概率條件下，成功查找的平均比較次數(shù)？2431427172431427173222818251522112312101000000302026162322132919(2)圖10(3)3(4)ASL=(1+2*2+3*4+5*4)/12=37/126．設(shè)查找表為(5,6,7,8,9,10,11,12,13,14)（1）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(2)給出二叉排序樹的定義,針對上述折半查找所對應(yīng)的判定樹的構(gòu)造過程,說明判定樹是否是二叉排序樹(設(shè)樹中沒有相同結(jié)點(diǎn))？(3)為了查找元素5.5，經(jīng)過多少次元素間的比較才能確定不能查到？97971014118512136(2)二叉排序樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹非空，則左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值；若它的右子樹非空，則右子樹的所有結(jié)點(diǎn)的值都大于（若允許結(jié)點(diǎn)有相同的值，則大于等于）它的根結(jié)點(diǎn)的值;左,右子樹也是一棵二叉排序樹，按定義判定樹是二叉排序樹。(3)3次四、程序填空題1．以下程序是快速排序的算法設(shè)待序的記錄序列存放在a[start],…a[end]中，按記錄的關(guān)鍵字進(jìn)行快速排序，先進(jìn)行一次劃分，再分別進(jìn)行遞歸調(diào)用voidquicksort(NODEa[],intstart,intend){inti，j;NODEmid;if(start>=end)return;i=start;j=end;mid=a[i];while(i<j){while(i<j&&a[j].key>mid.key)j--;if(i<j){a[i]=a[j];__i++__;}while(i<j&&a[i].key<=mid.key)__i++__;if(i<j){__a[j]=a[i];____j--;__}}a[i]=mid;quicksort(a,stat,i-1);quicksort__(a,i+1,end);__}2．以下函數(shù)為直接選擇排序算法，對a[1],a[2],…a[n]中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){inti,j,k; NODEtemp; for(i=1;i<=___n-1____;i++) {k=i; for(j=i+1;j<=___n____;j++) if(a[j].key<a[k].key)__k=j____; if(i!=k) {temp=a[i]; ___a[i]=a[k]__; ____a[k]=temp___;} }}3．以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___(1)malloc(sizeof(structnode)_____;p->data=x;p->next=NULL;___(2)rear->next=p_____;rear=___(3)p_____;}4.設(shè)有一個頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表,且p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中某結(jié)點(diǎn)a（設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同）,寫出相關(guān)語句(1).使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結(jié)點(diǎn)q=p;x=p->data;while（q->next!=NULL）q=q->next;__(1)q->next=head;___q=p;p=p->next;while(p->data!=x){q=p;__(2)p=p->next;___}__(3)q->next=p->next;___期末綜合練習(xí)二一、單項(xiàng)選擇題1.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指(B)。A．?dāng)?shù)據(jù)元素之間的關(guān)系B．?dāng)?shù)據(jù)的存儲結(jié)構(gòu)C．?dāng)?shù)據(jù)元素的類型D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)2.結(jié)構(gòu)中的元素之間存在一對多的關(guān)系是（C）。A．集合B．線性結(jié)構(gòu)C．樹形結(jié)構(gòu)D．圖狀結(jié)構(gòu)3.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系是（D）。A．集合B．線性結(jié)構(gòu)C．樹形結(jié)構(gòu)D．圖狀結(jié)構(gòu)4.對不帶頭結(jié)點(diǎn)的單向鏈表,判斷是否為空的條件是（A）（設(shè)頭指針為head）。A．head==NULLB．head->next==NULLC．head->next==headD．head=NULL5.設(shè)有一個長度為20的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為新表的第5個元素），則移動元素個數(shù)為（B）。A．15B．16C.5D．6.在一個不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要刪除第一個結(jié)點(diǎn)，可用的語句是（D）。A．p=q->next;p=p->next;B．p->next=q;p=p->next;C．p->next=q->next;q=p;D．p=p->next;q->next=p;7．在一個尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個s所指的結(jié)點(diǎn),并作為第一個結(jié)點(diǎn)，可執(zhí)行（D）。A．rearnext=s;snext=rearnextB．rearnext=snext;C．rear=snextD．snext=rearnext;rearnext=s;8．一個棧的進(jìn)棧序列是1，2，3，4，5，則棧的不可能輸出序列是（B）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．12345B．43512C．45321D．543219．元素a，b，c,d按順序依次進(jìn)棧，則該棧的可能輸出序列是（C）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．c,a,b，dB．d，b，c,aC．a(chǎn),c，b，dD．d，c，a,b10．一個隊列的入隊序列是2，4，6，8，按該隊列的輸出序列使各元素依次入棧，該棧的可能輸出序列是（A）。A．8，6，4，2B．6，2，4，8C．8，4，2，6D．8，2，4，611．從一個棧頂指針為top的鏈棧中取棧頂元素，用變量x保存該元素的值，則執(zhí)行（B）。A．x=top->data;top=topnext;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;12．在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，已生成一個結(jié)點(diǎn)p,要為結(jié)點(diǎn)p賦值x,并入隊的運(yùn)算為（B）。A.p->data=x;p->next=NULL;f->next=p;f=p;B．p->data=x;p->next=NULL;r->next=p;r=p;C．p->data=x;p->next=r;r=s;D．p->data=x;p->next=f;f=s;13．設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有55個元素,則該矩陣是（C）階的對稱矩陣。(矩陣中的第1個元素是a1,1）A．5B．20C．10D．1514．設(shè)有一個25階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素．a(chǎn)7,6在一維數(shù)組B中的下標(biāo)是（D）。(矩陣中的第1個元素是a1,1）A．34B．14C．26D．2715．設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第53號元素對應(yīng)于矩陣中的元素是（B）。(矩陣中的第1個元素是a1,1）A．a(chǎn)8,5,B．a(chǎn)10,8C．a(chǎn)8,1,D．a(chǎn)7,616.以下程序段的結(jié)果是c的值為（B）。chara[8]=“1236789”while(*p++)c++;A．8,B．7C．10D．1217.以下程序段的結(jié)果是c的值為（A）。char*a[5]={“12378”,“1237”,“1236789”,“1237”,inti,c=0;for(i=0;i<5:i++)if(StrCmp(a[i],“1237”A．2,B．5C．0D．123718．一棵有23個結(jié)點(diǎn)，采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（A）個指針域?yàn)榭铡．24B．25C．2319．一棵采用鏈?zhǔn)酱鎯Φ亩鏄渲校灿衝個指針域被有效使用（即指針域?yàn)榉强眨Ｔ摱鏄溆校ˋ）個結(jié)點(diǎn)。A．n+1B．nC．n-1D．n-220在一棵二叉樹中，若編號為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則雙親結(jié)點(diǎn)的順序編號為（A）。A．i/2B．2i-1C．2i+1D．21在一棵二叉樹中，若編號為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號為（D）。A．i/2.0B．i/2+1C．2i+122．設(shè)一棵哈夫曼樹共有2n+1個葉結(jié)點(diǎn)，則該樹有（C）個葉結(jié)點(diǎn)。A．n-1B．nC．n+1D．2n23．設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄洌~結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，該樹結(jié)點(diǎn)中共有2n個指針域?yàn)榭?。則該樹有（D）個葉結(jié)點(diǎn)。A．2nB．2n+1C24．已知如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（D）。A．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edbfcbbdfeca圖125．已知如圖2所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（C）。A．a(chǎn)cedfbB．a(chǎn)ecfdbC．a(chǎn)ecdfbD．a(chǎn)cebfdbbdfeca圖226．已知如圖3所示的一個圖，若從頂點(diǎn)B出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（C）。A.BADEHCFGB.BADEHCGFC.BADECHFGD.BADEHCFGFFGV7ABCHV8DV4E圖327．一組記錄的關(guān)鍵字序列為（42，37，62，40，32，92），利用快速排序算法，以第一個關(guān)鍵字為分割元素，算法經(jīng)過一次劃分后結(jié)果為（A）。A．32，37，40，42，62，92B．37，32,40，42，62，92C．32，40，37，42，62，92D．32，37，42，40，62，9228．一組記錄的關(guān)鍵字序列為（46，38，56，40，79，84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（B）。A．40，38，46，79，56，84B．40，38，46，56，79，84C．40，38，46，84，56，79D．38，40，46，56，79，8429．一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（A）。A．39，46，41,57,80，47B．39，47，46，80，41，57C．41，39，46，47，57，80D．39，80，46，47，41，5730．在有序表{21，23，28，33，43，45，46，73，77，78，89，99，106}中，用折半查找值43時，經(jīng)（B）次比較后查找成功。A．6B．3C．8二、填空題1．?dāng)?shù)據(jù)元素可以有一個或____多個數(shù)據(jù)項(xiàng)____組成。2.本書中介紹的樹形結(jié)構(gòu)和____圖狀結(jié)構(gòu)___屬非線性結(jié)構(gòu)。3.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為線性結(jié)構(gòu)。而數(shù)據(jù)元素存在__多對多_的關(guān)系稱為圖狀結(jié)構(gòu)。4．設(shè)有一個長度為18的順序表，要在第4個元素之前插入2個元素（也就是插入元素作為新表的第5個和第4個元素），則最少要移動元素的個數(shù)為（15）。5．設(shè)有一個長度為25的順序表，要刪除前3個元素,則最少要移動元素的個數(shù)為（22）。6．在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，可以先用語句（p->prior）->next=p->next；然再用語句____（p->next）->prior=p->prior；____。7．在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句（p->prior）->next=p->next；的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向____P所指結(jié)點(diǎn)的直接后繼____。8．在一個單向鏈表中p所指結(jié)點(diǎn)之后插入一個s所指向的結(jié)點(diǎn)時，應(yīng)執(zhí)行s->next=p->next;和___p->next=s;____的操作.9．設(shè)有一個頭指針為head的單向鏈表，p指向鏈表中的某結(jié)點(diǎn)，若要使該鏈表成為單向循環(huán)鏈表，可用語句while(p->next!=NULL)p=p->next;和____p->next=head;____。10．一個棧和一個隊列的輸入序列都為abcdefg，它們可能有相同的輸出序列嗎？_abcdefg_。（若沒有則回答沒有，若有則寫出序列,進(jìn)棧出?？梢越惶孢M(jìn)行）。11．向一個棧頂指針為top的鏈棧中插入一個p所指結(jié)點(diǎn)時，某人用語句top=p；p->next=top;這樣做的結(jié)果使p所指向的結(jié)點(diǎn)的指針域指向了___p本身__。12.從一個棧頂指針為top的鏈棧中取棧頂元素，用d保存棧頂元素的值，可執(zhí)行___d=top->data;__。(結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata)13．在一個鏈隊中，設(shè)front和rear分別為隊頭和隊尾指針，則s所指結(jié)點(diǎn)(數(shù)據(jù)域已賦值)的入隊操作為s->next=NULL;.__rear->next=s;__和rear=s;14.循環(huán)鏈隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為MaxSize,),判斷循環(huán)鏈隊列為空的條件是__front==rear__為真。15．設(shè)有n階對稱矩陣A，用一維數(shù)組s壓縮存儲A的下三角元素，s的下標(biāo)從零開始，元素s[26]相應(yīng)于A中的元素為____a7,6___。(矩陣中的第1個元素是a1,1）16.對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，設(shè)a是稀疏矩陣A相應(yīng)的三元組表類型（結(jié)構(gòu)體類型）變量，a中的一個成員項(xiàng)是三元組類型的結(jié)構(gòu)體數(shù)組data，按書中定義，若a.data[0].i=2;a.data[0].j=3;a.data[0].v=16;它提供的A數(shù)組的相關(guān)信息有___A的第一個非零元素的下標(biāo)為2，3，元素為16____。17．對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，設(shè)a是稀疏矩陣A相應(yīng)的三元組表類型（結(jié)構(gòu)體類型）變量，a中的一個成員項(xiàng)是三元組類型的結(jié)構(gòu)體數(shù)組data，按書中定義，若data的下標(biāo)從零開始，最后一個元素下標(biāo)為10，又a.data[10].i=8;a.data[10].j=5;a.data[10].v=36;它提供的A矩陣的相關(guān)信息有___A共有11個非零元素，a8,5為36____。18．設(shè)有一棵深度為5的完全二叉樹，該樹共有20個結(jié)點(diǎn),第五層上有5個葉結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）19．設(shè)有一棵有78個結(jié)點(diǎn)的完全二叉樹，該樹共有_____7____層。（根所在結(jié)點(diǎn)為第1層）20．中序遍歷___二叉排序___樹可得到一個有序序列。21．對于一棵具有_____n___個結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有n+1個指針域空.22．如圖4所示的二叉樹，其后序遍歷序列為_____519876432____。3c7gd6f3c7gd6f5e4dc2b1a8hd923．如圖5所示的二叉樹，其中序遍歷序列為____5387946_____。4g3f4g3f9a7b58e6c圖524.給定一組權(quán)重值，構(gòu)造哈夫曼樹，哈夫曼樹的高度一定是唯一的，這種說法是__不正確__的。(回答正確或不正確)三、綜合題1．（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹。（2）若上述二叉樹的各個結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系。ababced（1）圖8（2）d<b<e<a<c（3）abdec2.(1)說明什么是頂點(diǎn)活動網(wǎng)(AOV網(wǎng))和拓?fù)湫蛄校?）設(shè)有向圖G如下，寫出3種拓?fù)湫蛄校?）在圖G中增加一條邊，使圖G僅有一條拓?fù)湫蛄衋bcabcd(1)用頂點(diǎn)表示活動，邊表示活動間先后關(guān)系的有向圖稱為頂點(diǎn)活動網(wǎng)在頂點(diǎn)活動網(wǎng)中，若不存在回路,則所有活動可排列成一個線性序列,使每個活動的所有前驅(qū)活動都排在該活動的前面,稱此序列為拓?fù)湫蛄?2)abdcadbcdabc(3)在b和d間添加有向邊3．（1）利用篩選過程把序列{42，82，67，102，16，32，57，52}建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）。164216423252576782102428242826752573216102初始樹堆圖9（2）102，52，42，82，16，67，32，574．如下是一棵二叉排序樹，A1,A2,…A9代表1，2，3,…9中各個不同數(shù)字，（1）給出對該樹中序遍歷的結(jié)果（2）A3,A5,A7的值各為多少？（3）請在該樹中再插入一個結(jié)點(diǎn)9.5作為葉結(jié)點(diǎn)，并使它仍然是一棵二叉排序樹A1AA1A2A4A7A5A9A8A3A6(1)A7A123456789(2)851（3）7427421563899.55．設(shè)查找表為(11,12,13,14,15,16,17,18,19,20,21),元素的下標(biāo)從0開始。（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點(diǎn)用數(shù)值表示）（2）說明成功查找到元素15，19各需要經(jīng)過多少次比較？（3）說明查找不到元素10，15.5各需要經(jīng)過多少次比較？（4）給出中序遍歷判定樹的序列。（1）1414172118151220290111331916圖11(2)4次2次（3）3次4次（4）11，12，13，14，15，16，17，18，19，20，216．(1)設(shè)有查找表{17，26，14，16，15，30，18，19，28}，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹.(2)對上述二叉樹給出后序遍歷的結(jié)果(3).對上述二叉樹給出中后序遍歷的結(jié)果(4))在上述二叉樹中查找元素15共要進(jìn)行多少次元素的比較?14141618191530172628(2)15,16,14,19,18,28,30,26,17(3)14,15,16,17,18,19,26,28,30(4)4四、程序填空題1.以下程序是折半插入排序的算法設(shè)待排序的記錄序列存放在a[1],…a[n]中，以a[0]作為輔助工作單元，以下程序是要把a(bǔ)[i]插入到已經(jīng)有序的序列a[1],…a[i-1]中。voidbinsort(NODEa[],intn){intx,i,j,s,k,m;for（i=2；i<=__(1)n___;i++）{a[0]=a[i];x=a[i].key;s=1;j=i-1;while(s<=j){m=__(2)(s+j)/2;___if(x<a[m].key)__(3)j=m-1;___else__(4)s=m+1;___}for(k=i-1;k>=j+1;k--)__(5)a[k+1]___=a[k];a[j+1]=a[0];}}2．以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格typedefstructBnode{intkey;structBnode*left;structBnode*right;}Bnode;Bnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/{Bnode*p;if(bt==___(1)NULL_____)return(bt);p=bt;while(p->key!=__(2)k______) {if(k<p->key) ___(3)p=p->left_____;else___(4)p=p->right_____; if(p==NULL)break;}return(___(5)p_____);}3．以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(___(1)sizeof(structnode)_____);p->data=x;___(2)p->next=top_____;_____(3)top=p___;}4.設(shè)有一個頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中結(jié)點(diǎn)a,（設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同）,寫出相關(guān)語句(1).使該單向鏈表成為單向循環(huán)鏈表(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p;x=p->data;while（__(1)q->next!=NULL___）q=q->next;q->next=head;q=p;p=p->next;while(p->data!=x){q=p;__(2)p=p->next;___}s->next=p;__(3)q->next=s;___期末綜合練習(xí)三一、單項(xiàng)選擇題1．在C語言中，順序存儲長度為3的字符串，需要占用（A）個字節(jié)。A．4B．3C2．深度為5的完全二叉樹共有20個結(jié)點(diǎn)，則第5層上有（C）個結(jié)點(diǎn)(根所在結(jié)點(diǎn)為第一層)。A．3B．8C．5D3．串函數(shù)StrCat（a,b）的功能是進(jìn)行串（D）。A．比較B．復(fù)制C．賦值D．連接4．已知一個圖的邊數(shù)為m，則該圖的所有頂點(diǎn)的度數(shù)之和為（A）。A．2mB．mC．2m+1D．m/25．一棵有n個結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（A）個指針域?yàn)榭?。A．n+1B．nC．n-1D．n-26．?dāng)?shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的（D）結(jié)構(gòu)。A．物理B．存儲C．邏輯與物理D．邏輯7．設(shè)一棵哈夫曼樹共有n個非葉結(jié)點(diǎn)，則該樹有（B）個葉結(jié)點(diǎn)。A．nB．n+1C8．鏈表所具備的特點(diǎn)是（C）。A．可以隨機(jī)訪問任一結(jié)點(diǎn)B．占用連續(xù)的存儲空間C．插入刪除不需要移動元素結(jié)點(diǎn)D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問9．從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用變量x保存被刪結(jié)點(diǎn)的值，則執(zhí)行（A）。A．x=top->data;top=topnext;B．x=top->data;C．top=top->next;x=top->data;D．top=top->next;x=data;10．線性表只要以（C）方式存儲就能進(jìn)行折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D．二叉樹11．一棵完全二叉樹共有5層，且第5層上有六個結(jié)點(diǎn)，該樹共有（C）個結(jié)點(diǎn)。A．30B．20C12．散列查找的原理是（A）。A．在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B．按待查記錄的關(guān)鍵字有序的順序方式存儲C．按關(guān)鍵字值的比較進(jìn)行查找D．基于二分查找的方法13．在一個無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（D）倍。A．3B．2.5C14．對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（C）次元素間的交換，則表明序列已經(jīng)排好序。A．1B．2C．0D15．已知如圖1所示的一個圖，若從頂點(diǎn)V1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（A）。V6V7V1V2V3V8V4V5A．V1V2V4V8V5V3V6V7B．V1V2V4V5V8V3V6V7C．V1V2V4V8V3V5V6V7D．V1VV6V7V1V2V3V8V4V5圖116．排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序?yàn)橹梗撆判蛩惴ㄊ?A)。A．直接插入排序B．快速排序C．冒泡排序D．選擇排序17．已知如圖2所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（B）。A．a(chǎn)bcedfB．a(chǎn)bcefdC．a(chǎn)ebcfdD．a(chǎn)cfdebbdfebdfeca18．在對一組元素（64，48，106，33，25，82，70，55，93）進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進(jìn)行（B）次元素間的比較（指由小到大排序）。A．6B．2C．3D19．對二叉排序樹進(jìn)行（C）遍歷，可以使遍歷所得到的序列是有序序列。A．按層次B．后序C．中序D．前序20．采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（B）次元素間的比較。A．n+2B．nC．n-1D．n/221．在有序表{2，4，7，14，34，43，47，64，75，80，90，97，120}中，用折半查找法查找值80時，經(jīng)（A）次比較后查找成功。A．4B．2C22．如圖3若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（B）。abecdfgabecdfgB．a(chǎn)becdgfC．a(chǎn)cfedgbD．a(chǎn)becfdg圖323．有一個長度為9的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（B）。A．25/10B．25/9C24．元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（D）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．8，6，4，2B．2，4，6，8C．4，2，8，6D．8，6，2，425．排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（C）。A．冒泡B．直接插入C．折半插入D．選擇排序26．排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（C）排序。A．歸并B．插入C．選擇D．快速27．一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（B）。A．40，38，46，79，56，84B．40，38，46，56，79，84C．40，38，46，84，56，79D．38，40，46，56，79，8428．一棵哈夫曼樹總共有23個結(jié)點(diǎn)，該樹共有（D）個葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）A．10B．13C．1129．排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（D）排序。A．歸并B．插入C．快速D．選擇30．隊列的插入操作在（B）進(jìn)行。A．隊頭B．隊尾C．隊頭或隊尾D．在任意指定位置二、填空題1．在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點(diǎn)中設(shè)置三個域，它們是_值域_、左指針、右指針。2．一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個葉結(jié)點(diǎn)，則該樹總共有____11____個結(jié)點(diǎn)。3．一棵二叉樹中順序編號為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號分別為_____2i_、___2i+1_____。4．設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10，該完全二叉樹一共有____21____個結(jié)點(diǎn)。5．串的兩種最基本的存儲方式是__順序存儲_和__鏈?zhǔn)酱鎯。6．按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有先序、__中序_、__后序__兩種。7．一棵有2n-1個結(jié)點(diǎn)的二叉樹，其每一個非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有__n_個葉結(jié)點(diǎn)。8．?dāng)?shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為__樹形___結(jié)構(gòu)。9．對于一棵具有n個結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有__n+1_個指針域?yàn)榭铡?0．把數(shù)據(jù)存儲到計算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為___物理___結(jié)構(gòu)。11．__中序__遍歷二叉排序樹可得到一個有序序列。12．結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為___線性__結(jié)構(gòu)。13．如圖4所示的二叉樹，其后序遍歷序列為gdbeihfca。eefgibachdeefgibachd圖414．如圖5所示的二叉樹，其后序遍歷序列為gdbeihfca。圖515．如圖6所示的二叉樹，其先序遍歷序列為___abdefcg__。ggfabdec圖616．n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行_____n-1___趟冒泡。17．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是__正確____的。18．二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是___不正確____的。(回答正確或不正確)19．二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是__不正確___的。(回答正確或不正確)20．圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_正確__的。21．對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按___主關(guān)鍵字___排序結(jié)果是唯一的。22．根據(jù)搜索方法的不同，圖的遍歷有_深度優(yōu)先搜索遍歷_、廣度優(yōu)先搜索遍歷_兩種方法。23．按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字相等的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。24．按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字相等的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題1．設(shè)查找表為(16,15,20,53,64,7),(1)用冒泡法對該表進(jìn)行排序（要求升序排列），寫出每一趟的排序過程，通常對n個元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫出對其進(jìn)行折半查找所對應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(1)原序列1615205364715162053764n-1-j/p>