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

PAGEPAGE22數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2015年11月綜合練習(xí)一一、單項選擇題1.對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個10行8列的稀疏矩陣A共有73個零元素，其相應(yīng)的三元組表共有()個元素。A．8B．80C．7D．102.對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個10行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個元素，矩陣A共有()個零元素。A．8B．72C．74D．103.字符串()是“abcd321ABCD”的子串。A.“21AB”B.“abcD”C.“aBCD”D.“321a”4.程序段chara[]=“abdcacdef”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}結(jié)果中,n的值是（）A.6B.8C.7D.95.棧和隊列的共同特點是（）。A．都是操作受限的線性結(jié)構(gòu)B．元素都可以隨機(jī)進(jìn)出C．都是先進(jìn)后出D．都是先進(jìn)先出6.10,6,2,1按順序依次進(jìn)棧，該隊列的可能輸出序列是（）。(進(jìn)棧出?？梢越惶孢M(jìn)行）。A．6,10,1,2B．2,10,6,1C．6,1,10,1D．1,6,10,27.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，p指向一個新結(jié)點,要為結(jié)點p所指結(jié)點賦值x,并入隊的運(yùn)算為p->data=x;p->next=NULL;（）。A.f->next=p;f=p;B．r->next=p;r=p;C．r=p;p->next=r;D．p->next=f;f=p;8.對一個棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行(）。A．e=top->next;top->data=e;B．e=top->data;top=top->next;C．top=top->next;e=top->data;D．top=top->next;e=data;9.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。A.邏輯B.存儲C.邏輯與存儲D.物理10.算法的時間復(fù)雜度與()有關(guān)。A.算法本身B.所使用的計算機(jī)C.算法的程序設(shè)計D.數(shù)據(jù)結(jié)構(gòu)11．順序表所具備的特點之一是（）。A．可以隨機(jī)訪問任一結(jié)點B．不需要占用連續(xù)的存儲空間C．插入元素的操作不需要移動元素D．刪除元素的操作不需要移動元素12．在一個單向鏈表中,在p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行s->next=p->next;和（）。A．p=s;B．p->next=s->next;C．p=s->nextD．p->next=s;13.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（）。A．只能有一個數(shù)據(jù)項組成B．至少有二個數(shù)據(jù)項組成C．可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成D．至少有一個數(shù)據(jù)項為指針類型14.一種邏輯結(jié)構(gòu)在存儲時（）。A．只要存儲數(shù)據(jù)元素間的關(guān)系B．只能采用一種存儲結(jié)構(gòu)C．可采用不同的存儲結(jié)構(gòu)D．只要存儲數(shù)據(jù)元素的值15．設(shè)有頭指針為head的非空的單向鏈表,指針p指向其尾結(jié)點,要使該單向鏈表成為單向循環(huán)鏈表,則可利用下述語句（）。A．p=head;B．p=NULL;C．p->next=head;D．head=p;16.單向鏈表所具備的特點是()。A.可以隨機(jī)訪問任一結(jié)點B.占用連續(xù)的存儲空間C.插入刪除不需要移動元素D.可以通過某結(jié)點的指針域訪問其前驅(qū)結(jié)點17.在線性表的順序結(jié)構(gòu)中，以下說法正確的是（）。A．邏輯上相鄰的元素在物理位置上不一定相鄰B．?dāng)?shù)據(jù)元素是不能隨機(jī)訪問的C．邏輯上相鄰的元素在物理位置上也相鄰D．進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高18.數(shù)據(jù)結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是指()。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)19.對鏈表,以下敘述中正確的是（）。A．不能隨機(jī)訪問任一結(jié)點B．結(jié)點占用的存儲空間是連續(xù)的C．插入刪除元素的操作一定要要移動結(jié)點D．可以通過下標(biāo)對鏈表進(jìn)行直接訪問20.下面關(guān)于線性表的敘述中,錯誤的是()。A.線性表采用順序存儲,必須占用一片連續(xù)的存儲空間。B.線性表采用順序存儲,進(jìn)行插入和刪除操作,不需要進(jìn)行數(shù)據(jù)元素間的移動。C.線性表采用鏈?zhǔn)酱鎯Γ槐卣加眠B續(xù)的存儲空間。D.線性表采用鏈?zhǔn)酱鎯?，進(jìn)行插入刪除操作，不需要移動元素21.設(shè)有一個長度為35的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為新表的第5個元素），則移動元素個數(shù)為（）。A．30B．31C.5D．622.設(shè)有一個長度為18的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為新表的第5個元素），則移動元素個數(shù)為（）。A．15B．14C.5D．623．設(shè)有一個長度為40的順序表，要刪除第10個元素(下標(biāo)從1開始)需移動元素的個數(shù)為（）。A．11B．10C．30D．3124．設(shè)有一個長度為25的順序表，要刪除第10個元素(下標(biāo)從1開始)需移動元素的個數(shù)為（）。A．10B．17C．15D．1625．設(shè)有一個25階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是（）。A．25B．24C．26D．2726．設(shè)有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a10,8在一維數(shù)組B中的下標(biāo)是（）。A．62,B．63C．51D．5327．線性表在存儲后,如果相關(guān)操作中有要求:利用已知的指向某結(jié)點的指針或序號,訪問該結(jié)點的前驅(qū)結(jié)點，則采用（）的存儲方式是不可行的。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表28．在一個尾指針為rear的不帶頭結(jié)點的單循環(huán)鏈表中,插入一個s所指的結(jié)點,并作為第一個結(jié)點，可執(zhí)行sànext=rearànext;和（）。A．rearànext=sànext;B．rear=sànext;C．rear=s;D．rearànext=s;29．在一棵二叉樹中，若編號為i的結(jié)點存在左孩子,i結(jié)點的左孩子的順序編號為（）。A．i/2.0B．2*iC．2*i+1D．i+230．在一棵二叉樹中，若編號為15的結(jié)點是其雙親結(jié)點的右孩子，則雙親結(jié)點的順序編號為（）。A．30B．8C．31D．7二、填空題1.廣義表((b,a,c),c,d,f,e,((i,j),k))的長度是________。2.結(jié)構(gòu)中的元素之間存在一對多的關(guān)系是________結(jié)構(gòu)。3.數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的抽象關(guān)系稱為________結(jié)構(gòu)。4.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系是________結(jié)構(gòu)。5.棧的操作特點是后進(jìn)________。6.循環(huán)隊列的最大存儲空間為MaxSize,若隊頭指針front，隊尾指針rear，采用少用一個存儲空間以有效地判斷?？栈驐M，隊空的判定條件為________。7.廣義表((b,a,c),c,d,f,e,((i,j),k))的表頭是________。8.廣義表((b,a,c),c,d,f,e,((i,j),k))的長度是________。9.設(shè)有一個長度為18的順序表,第8號元素到第18號元素依次存放的值為8,9,…,18.某人想要刪除第8號元素，程序中他的做法是用語句for(i=18;i<=9;i--)a[i-1]=a[i];即從第18號元素開始,直到第9號元素,每個元素依次向前(左)移動1個位置.事實上這樣做是錯誤的.其結(jié)果新表中第9號元素的值為________。10．要求在n個數(shù)據(jù)元素中找值最大的元素，其基本操作為元素間的比較。算法的時間復(fù)雜度為_______。11.一棵二叉樹,有1個2度結(jié)點,，2個1度結(jié)點，則該樹共有_______個結(jié)點。12．一棵有8個葉結(jié)點的二叉樹，其1度結(jié)點的個數(shù)為3，則該樹共有_______個結(jié)點。13．設(shè)有一棵深度為5的完全二叉樹，該樹共有21個結(jié)點,第5層上有個結(jié)點。（根所在結(jié)點為第1層）14.對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有________個指針域為空。15．中序遍歷________樹可得到一個有序序列。16.對一組記錄（5，8，9，2，12，7，56，44，39）進(jìn)行直接插入排序(由小到大排序)，當(dāng)把第6個記錄7插入有序表，為尋找插入位置需比較________次。17.序列12,10,13,11,16,14,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是________。（按升序排序）18．設(shè)有一棵深度為6的完全二叉樹，第6層上有3個結(jié)點，該樹共有_______個結(jié)點。（根所在結(jié)點為第1層）19.對16個元素的序列用冒泡排序法進(jìn)行排序，共需要進(jìn)行________趟冒泡。20．一棵有16個葉結(jié)點的哈夫曼樹，則該樹共有_______個結(jié)點。21.一棵有16個葉結(jié)點的哈夫曼樹，則該樹共有_______個非葉結(jié)點。22.20個元素進(jìn)行冒泡法排序，通常第6趟冒泡要進(jìn)行______次元素間的比較。23.在對一組記錄（40，24，82，9，1，78，46，31，69）進(jìn)行直接插入排序(由小到大排序)，當(dāng)把第7個記錄46插入到有序表時，為尋找插入位置需比較________次。24．對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A共有38個零元素，其相應(yīng)的三元組表共有_______個元素。三、綜合題1．設(shè)有序表為(5,8,14,15,33,51,61,73,81,82,93),元素的序號依次為1,2,3,……，11.（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點可用序號表示）（2）說明成功查找到元素33需要經(jīng)過多少次比較？(3)在等概率條件下,給出成功查找的平均查找長度2.設(shè)數(shù)據(jù)集合a={1,5,8,3,10,7,13,9}（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）對該二叉樹進(jìn)行查找，成功查找到7要進(jìn)行多少次元素間的比較？（3）給出對該二叉樹中序遍歷的序列。3．dcdceabfhe圖1(2)設(shè)有向圖如圖2所示下，寫出首先刪除頂點1的1種拓?fù)湫蛄?1234543465圖24．設(shè)有序表為(30,48,58,70,78,79,90),元素的序號依次為1,2,3,……，7.（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點用序號表示）（2）給出有序表中經(jīng)3次比較成功查找到的所有元素(3)說明不成功查找元素59需要經(jīng)過多少次比較？5.(1)設(shè)數(shù)據(jù)集合a={7,4,9,8,6,5,3},依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)對該二叉樹進(jìn)行查找，成功查找到5要進(jìn)行多少次元素間的比較？(3)給出對上述二叉排序樹進(jìn)行中序遍歷的序列6．(1)如圖3所示，若從頂點a出發(fā)，首先經(jīng)過c按廣度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點序列。（2）同圖3所示,若從頂點h出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的2種頂點序列。a阿a阿decfhecdeccdeceec圖3(3)一組記錄的關(guān)鍵字序列為（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆頂元素是最小元素）,給出按篩選法建立的的初始堆。四、程序填空題1．以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格typedefstruct{intkey;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(___(1)_____){mid=(low+high)/2;if(a[mid].key==k)return__(2)______; elseif(___(3)_____)low=mid+1; else__(4)______; }___(5)_____; }2．以下函數(shù)為直接選擇排序算法，對a[1],a[2],…a[n]中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){ inti,j,k; NODEtemp; for(i=1;i<=___(1)___;i++) { k=i; for(j=i+1;___(2)__;j++) if(a[j].key<a[k].key)__(3)____; if(i!=k) { temp=a[i]; ___(4)____; ___(5)____; } }}3.以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(___(1)___);p->data=x;__(2)____;___(3)___;}4.以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___(1)_____;p->data=x;p->next=NULL;___(2)_____;;rear=___(3)_____;}綜合練習(xí)一答案一、單項選擇題1．C2．C3．A4．D5．A6．A7．B8．B9．A10．A11．A12．D13．C14．C15．C16．C17．C18．B19．A20．B21．B22．B23．C24．C25．C26．D27．A28．D29．B30．D二、填空題1.62.樹形3.邏輯4.圖狀5.先出6.rear==front為真7.（b,a,c）8.69.1810.O(n)11.512.1813.614.n+115.二叉排序樹16.,417.10，12，11，13，14，1618.3419.1520.3121.1522.1423.324.4三、綜合應(yīng)用題1．（1）圖4447118521011311396圖451148151561828337393(2)4次(3)(1+2*2+3*4+4*4)/11=33/11=32.(1)圖5(2)4次 (3)中序遍歷1,3,5,7,8,9,10,13131031310318579圖53(1)acdbfeh(2)152364或152634或1562344．（1）圖69494216573圖6487930587890(2)30587890(3)3次589009489009475653e圖7(2)4(3)3,4,,5,6,7,8,96．(1)acefdh(2)hdeacfhdfcae（3）20,53，38，63，75，45，95，809920536338459575圖880四、程序填空題1.(1)low<=high(2)mid(3)a[mid].key<k(4)high=mid-1(5)return-12.(1)n-1(2)j<=n(3)k=j(4)a[i]=a[k](5)a[k]=temp3.(1)sizeof(structnode)(2)pnext=top(3)top=p4.(1)malloc(sizeof(structnode))(2)rear->next=p;(3)rear=p;綜合練習(xí)二一、單項選擇題1.對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個有10行的稀疏矩陣A共有97個零元素，其相應(yīng)的三元組表共有3個元素。該矩陣A有()列。A．8B．9C．7D．102.單向鏈表所具備的特點是()。A.可以隨機(jī)訪問任一結(jié)點B.占用連續(xù)的存儲空間C.插入刪除不需要移動元素D.可以通過某結(jié)點的指針域訪問其前驅(qū)結(jié)點3.子串“acd”在主串“abdcacdefac”中的位置是()。A．3B．5C．7D．14.設(shè)有一個長度為18的順序表，要在第6個元素之前插入一個元素（也就是插入元素作為新表的第6個元素），則移動元素個數(shù)為（）。A．12B．5C5.序列12,16,8,4按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊列，該隊列的不可能輸出序列是（）。(進(jìn)棧、出棧可以交替進(jìn)行）。A．16,12,8,4B．4,8,12,16C．8,4,16,12D．16,12,4,86．棧和隊列的共同特點是（）。A．都是線性結(jié)構(gòu)B．元素都可以隨機(jī)進(jìn)出C．都是先進(jìn)后出D．都是先進(jìn)先出7.在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，對該隊列進(jìn)行出隊操作,并把結(jié)點的值保存在變量e中,其運(yùn)算為（）。A．e=f->data；r=r->next;B．e=f->data；r->next=r;C．e=f->data；f=f->next;D．e=f->data；f->next=f;8．元素1，3，5，7按順序依次入隊列，按該隊列的出隊序列進(jìn)棧，該棧的可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。A．7，5，1，3B．7，3，1，5C．5，1，3，7D．7，5，3，19.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)內(nèi)存中的表示是()。A.給相關(guān)變量分配存儲單元B.數(shù)據(jù)的存儲結(jié)構(gòu)C.數(shù)據(jù)的邏輯結(jié)構(gòu)D.算法的具體體現(xiàn)10．在一個不帶頭結(jié)點的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則對該隊列進(jìn)行出隊操作中并把結(jié)點的值保存在變量e中,其運(yùn)算為e=fdata；和（）。A．r=rnext;B．rnext=r;C．f=fnext;D．fnext=f11.以下說法正確的是()。A.線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)必須占用連續(xù)的存儲空間B.一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu)C．一種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu)D．線性表的順序存儲結(jié)構(gòu)不必占用連續(xù)的存儲空間12．設(shè)有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有45個元素,則該矩陣是（）階的對稱矩陣。A．15B．11C．10D．913．在一個單鏈表中要刪除p所指結(jié)點的后繼結(jié)點，可執(zhí)行q=p->next;和（）。A．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;14.下列是C語言中〝abcd321ABCD〞的子串的選項是（）。A.〝21ABC〞B.〝abcABCD〞C.abcDD.〝321a〞15.在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計算機(jī)有關(guān)的是（）。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)16.字符串a(chǎn)1=〝BEIJING〞,a2=〝BEF〞,a3=〝BEFANG〞,a4=“BEFI〞最小的是（）.A.a1B.a2C.a3D.a417.以下表中可以隨機(jī)訪問的是（）。A．單向鏈表B．雙向鏈表C．單向循環(huán)鏈表D．順序表18．一棵有20個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有（）個指針域為空。A．21B．20C．19D．1819.頭指針為head的不帶頭結(jié)點的單向鏈表為空的判定條件是邏輯表達(dá)式()為真。A.head==NULLB.head->next==NULLC.head->next=NULLD.head->next!=NULL20．設(shè)一棵哈夫曼樹共有18個葉結(jié)點，則該樹有（）個非葉結(jié)點。A．18B．19C．17D．1621.設(shè)有一個長度為32的順序表，要在第5個元素之前插入1個元素（也就是插入元素作為新表的第5個元素），需移動元素個數(shù)為（）。A．25B．28C.5D．622．如圖1所示的一個圖，若從頂點g出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（）。A．gabecdfB．gacfebdC．gaebcfdD．gaedfcb bbdfeCag圖123．設(shè)有一個長度為33的順序表，要刪除第10個元素(下標(biāo)從1開始)需移動元素的個數(shù)為（）。A．11B．10C．23D．1424．線性表以（）方式存儲，能進(jìn)行折半查找。A．關(guān)鍵字有序的B．關(guān)鍵字有序的順序C．鏈接D．順序25．設(shè)有一個28階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第26號元素對應(yīng)于矩陣中的元素是（）。A．a(chǎn)7,5,B．a(chǎn)7,6C．a(chǎn)6,5D．a(chǎn)7,426．有一個長度為8的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A．22/8B．20/8C．23/827.在一個不帶頭結(jié)點的單循環(huán)鏈表中，p、q分別指向表中第一個結(jié)點和尾結(jié)點，現(xiàn)要刪除第一個結(jié)點，且p、q仍然分別指向新表中第一個結(jié)點和尾結(jié)點?？捎玫恼Z句是p=p->next;和（）。A．p=q->next;B．p->next=q;C．q=p;D．q->next=p;28.排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（）。A．折半插入排序B．直接插入排序C．歸并排序D．選擇排序29．在一棵二叉樹中，若編號為16的結(jié)點是其雙親結(jié)點的左孩子，則他的雙親結(jié)點的順序編號為（）。A．7B．8C．32D．3330．排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（）排序。A．堆B．冒泡C．選擇D．快速二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機(jī)中的表示稱為________結(jié)構(gòu)。2.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為________結(jié)構(gòu)。3.四類基本結(jié)構(gòu)分別為_______結(jié)構(gòu)。4.棧的操作特點是______________。5.隊列的操作特點是先進(jìn)________。6.廣義表的(a,(a,b),d,e,((i,j),k))深度是________。7.廣義表((b,a,c),c,d,(e,i,j,k))的表尾是________。8.廣義表((a,b),d,e,((i,j),k))的長度是________。9.設(shè)有一個長度為20的順序表,第8號元素到第20號元素依次存放的值為8,9,…,20。某人想要在第8號元素前插入1個元素7（也就是插入元素作為新表的第8個元素），程序中他的做法是用語句for(i=8;i<=20;i++)a[i+1]=a[i];a[8]=7;即從第8號元素開始,直到第20號元素,每個元素依次向后(右）移動1個位置,然后把7存放在第8號位置。事實上這樣做是錯誤的.其結(jié)果是新表中第20號元素的值為________。10.設(shè)順序隊列的類型為typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行元素的出隊操作，并把元素賦給邊量x,按教科書約定,可用語句x=sq->data[sq->front];和________。11．設(shè)有一棵有38個結(jié)點的完全二叉樹，該樹共有_________層。（根所在結(jié)點為第1層）12.設(shè)順序隊列的類型為typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行新元素x的入隊操作，按教課書約定,可用語句sq->data[sq->rear]=x;和________。13．一棵有18個結(jié)點的二叉樹，其2度結(jié)點數(shù)的個數(shù)為8，則該樹共有_______個1度結(jié)點。14.序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是________。（由小到大排序）15.對一組記錄（1，3，9，2，12，7，5，4，6）進(jìn)行直接插入排序(由小到大排序)，當(dāng)把第6個記錄7插入有序表，為尋找插入位置需比較________次。16.數(shù)據(jù)結(jié)構(gòu)中,________之間的抽象關(guān)系稱為邏輯結(jié)構(gòu)。17.序列5,3,8,4,7,6,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是________。(按升序排序)18.循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，(最多元素為MaxSize,),判斷循環(huán)隊列為空的條件為________為真。19.廣義表(b,a,(c,b),f,e,((i,j),k))的長度是________。20.排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是。21．一棵有18個葉結(jié)點的哈夫曼樹，則該樹共有_______個非葉結(jié)點。22.對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表,矩陣元素a3,4對應(yīng)的三元組為_______。23．對稀疏矩陣進(jìn)行壓縮存儲,可采用三元組表，一個8行7列的稀疏矩陣A共有51個零元素，其相應(yīng)的三元組表共有_______個元素24．在雙向鏈表中，要刪除p所指的結(jié)點，其中所用的一條語句（p->next）->prior=p->prior;的功能是：使P所指結(jié)點的直接后繼的左指針指向________。綜合題1.設(shè)數(shù)據(jù)集合a={6,17,10,13,8,15,12,18,14}（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）給出對該二叉樹中序遍歷的序列（3）對該二叉樹進(jìn)行查找，成功查找到14要進(jìn)行多少次元素間的比較？2.設(shè)數(shù)據(jù)集合a={62,74,30,15,56,48}（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）對該二叉樹進(jìn)行查找，不成功查找有多少種可能？畫出不成功查找樹的示意圖。（3）不成功查找的平均查找長度是多少?（4）為了成功查找到48需要進(jìn)行多少次元素間的比較?（5）給出對該二叉樹后序遍歷的序列。3．設(shè)有序表為(2,5,11,12,30,48,58),元素的序號依次為1,2,3,……，7.（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點用序號表示）（2）說明成功查找到元素11需要經(jīng)過多少次比較？(3)在等概率條件下,給出成功查找的平均查找長度4．設(shè)有序表為（3，9，15，26，38，41，53，74，81，96，97，99），元素的序號依次為1,2,……,12。（1）說出有哪幾個元素需要經(jīng)過3次元素間的比較才能成功查到。（2）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹（樹結(jié)點用序號表示）。（3）設(shè)查找5號元素(38)，需要進(jìn)行多少次元素間的比較才能確定不能查到,依次和哪些元素進(jìn)行了比較？（要求寫出具體元素）。（4）給出后序遍歷該二叉樹的序列。(5)給出中序遍歷該二叉樹的序列。 5.(1)如圖1所示，若從頂點a出發(fā)，首先經(jīng)過頂點c按廣度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點序列。(2)如圖1所示，給出從頂點h出發(fā)，首先經(jīng)過頂點d和e按深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點序列。a阿a阿decfhecdeccdeceecb圖1（3）一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序的方法的方法建立小根堆(堆頂元素是最小元素）,給出按篩選法建立的的初始堆。四、程序填空題1．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進(jìn)行冒泡排序完成程序中的空格部分，其中n是元素個數(shù)，程序按升序排列。voidbsort(NODEa[],int){NODEtemp;inti,j,flag;for(j=1;j<=n-1;(1)){flag=0;for(i=1;(2);i++)if(a[i].key>a[i+1].key){flag=1;(3)a[i]=a[i+1];(4);}if(flag==0)break;}}程序中flag的功能是(5)2.學(xué)生信息存放在結(jié)構(gòu)數(shù)組中，每個數(shù)組元素存放一個學(xué)生的信息，下標(biāo)從0到n-1。數(shù)組元素按學(xué)號num由小到大有序排列，以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字num等于k的記錄，查找成功返回該記錄的下標(biāo)(數(shù)組元素的下標(biāo))。失敗時返回-1，完成程序中的空格。typedefstruct{charsex;intnum;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(___(1)_____){mid=(low+high)/2;if(a[mid].num==k)return__(2)______; elseif(___(3)_____)low=mid+1; else__(4)______; }return-1; }3．以下函數(shù)為鏈棧的出棧操作，出棧結(jié)點的數(shù)據(jù)由x返回structnode{ElemTypedata;structnode*next;};ElemTypePop(){intx;if(top==___(1)_____){printf("棧下溢錯誤！\n");exit(1);}x=___(2)_____;top=___(3)_____;return