數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)-王春鳳

數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)練習(xí)一一、單項(xiàng)選擇題1．棧和隊(duì)列的共同特點(diǎn)是（）。A.元素都可以隨機(jī)進(jìn)出B.都是先進(jìn)先出C.都是先進(jìn)后出D.都是操作受限的線性結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素間的關(guān)系的表示C.相關(guān)算法D.數(shù)據(jù)元素的類型3．對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過指針變量p生成入棧結(jié)點(diǎn)，則執(zhí)行：p=(structnode*)malloc(sizeof(structnode);p->data=a;和（）。A.top->next=p;p=top;B.p->nex=top;top=p;C.top=top->next;p=top;D.p->next=top;p=top;4．樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B．一對(duì)一C．多對(duì)多D．一對(duì)多5．設(shè)頭指針為head的非空的單向鏈表,指針p指向尾結(jié)點(diǎn),則通過以下操作()可使其成為單向循環(huán)鏈表。A．p->next=NULL;B．head=p;C．p->next=head;D．p=head;6．設(shè)有一個(gè)長度為26的順序表，要插入一個(gè)元素,并使它成為新表的第6個(gè)元素,需移動(dòng)元素的個(gè)數(shù)為（）。A．21B．22C．20D．197．一種邏輯結(jié)構(gòu)（）。A．只能有唯一的存儲(chǔ)結(jié)構(gòu)B．可以有不同的存儲(chǔ)結(jié)構(gòu)C．與存儲(chǔ)該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān)D．是指某一種數(shù)據(jù)元素的性質(zhì)8．頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p所指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表,可執(zhí)行head=head->nex;和（）。A．p=head->nextB．head->next=pC．head->next=p->nextD．p->next=head;9．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（）。A．存儲(chǔ)結(jié)構(gòu)B．邏輯結(jié)構(gòu)C．?dāng)?shù)據(jù)元素的存儲(chǔ)D.給數(shù)據(jù)元素分配存儲(chǔ)空間10．元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．117，115，113，111B．111，113，115，117C．117，115，111，113D．113，111，117，11511．圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A．一對(duì)一B．一對(duì)多C．多對(duì)多D．每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼12．以下說法正確的是（）。A．棧的特點(diǎn)是先進(jìn)先出B．棧的特點(diǎn)是先進(jìn)后出C．隊(duì)列的特點(diǎn)是先進(jìn)后出D.棧和隊(duì)列的特點(diǎn)都是后進(jìn)后出13．一個(gè)單鏈表中,在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行:s->next=p->next;和（）。A．s=p->next;B．p->next=s->next;C．p=s->next;D．p->next=s;14.設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（）。A．21B．28C．17D．2315．元素12，14，16，18順序依次進(jìn)棧，則該棧的不可能輸出序列是（）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．18，16，14，12B．12，14，16，18D．14，12，18，16D．18，16，12，1416．設(shè)有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四個(gè)串中最大的是()。A．p3B．p2C．p1D．p417．設(shè)有一個(gè)30階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（）。A．41B．32C18.數(shù)組a經(jīng)初始化chara[]=“English”;a[7]中存放的是（）。A.字符串的結(jié)束符B.字符hC.〝h〞D.變量h19．設(shè)有一個(gè)長度為32的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。A．15B．22C．14D．2420.設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（）。A.BcdB.BCdC.ABCD.Abc21.在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A．2iB．2i-1C22．在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為（）。A．2i+1B．2i-1C．2i23．一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹，共有（）層。(設(shè)根結(jié)點(diǎn)在第一層)A．7B．6C．4D．524．如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)becdfB．a(chǎn)ebcfdC．a(chǎn)ecbdfD．a(chǎn)edfcbbdbdfeca圖125．如圖2所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)becdfgB．a(chǎn)cfebgdC．a(chǎn)ebcfgdD．a(chǎn)edfcgbbbdfecag圖226．線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。A．鏈接B．順序C．關(guān)鍵字有序的順序D．二叉樹27.字符串“DABcdabcd321ABC”的子串是()。A.“cd32”B.“ABcD”C.“aBcd”D.“321a”28．一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹，最后一層有（）個(gè)結(jié)點(diǎn)。A．7B．5C．6D．829．如圖3所示，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)bcdfgeB．a(chǎn)bcdfegC．a(chǎn)cbfedgD．a(chǎn)bcfgdeggfabdec圖330.下圖4的拓?fù)湫蛄惺?)。A．52346B．23645C．56234D.23564 2234543465圖4二、填空題1.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有10行的稀疏矩陣A共有97個(gè)零元素，其相應(yīng)的三元組表共有3個(gè)元素。該矩陣A有列。2．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為________結(jié)構(gòu)。3．在單向鏈表中，q指向p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，要?jiǎng)h除q所指結(jié)點(diǎn)，可以用操作______=q->next;。4.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行______次元素間的比較。5.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)和_______三項(xiàng)信息。6．中序遍歷________樹可得到一個(gè)有序序列。7.隊(duì)列的操作特點(diǎn)是后進(jìn)________。8.待排序的序列為8,3,4,1,2,5,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為()。9．n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行________趟冒泡。10廣義表((a,b),d,e,((i,j),k))的長度是________。11．中序遍歷二叉排序樹可得到一個(gè)________的序列。12.廣義表的(c，a,(a,b),d,e,((i,j),k))深度是________。13.廣義表(c,a,(a,b),d,e,((i,j),k))的長度是________。14.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有10行10列的稀疏矩陣A共有95個(gè)零元素，其相應(yīng)的三元組表共有個(gè)元素。15.廣義表的(c,a,(a,b),d,e,((i,j),k))深度是________。16．在對(duì)一組記錄(50,49,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_________次。17.循環(huán)隊(duì)列在規(guī)定少用一個(gè)存儲(chǔ)空間的情況下，隊(duì)空的判定條件為________。18.一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹,該樹中總共有_____個(gè)結(jié)點(diǎn)。19.c語言中,字符串“E”存儲(chǔ)時(shí)占個(gè)字節(jié)。20.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有_______個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）。21．一棵二叉樹中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有_______個(gè)葉結(jié)點(diǎn)。22．設(shè)有一個(gè)長度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為_______。23．在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較_________次。24.有以下程序段chara[]=“English”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}結(jié)果中，n的值是_______。三、綜合題1．設(shè)查找表為(1,10,11,14,23,27,29,55,68),元素的下標(biāo)依次為1,2,3,……，9。（1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹（樹中結(jié)點(diǎn)用下標(biāo)表示）。（2）說明成功查找到元素14,需要依次經(jīng)過與哪些元素的比較？共幾次比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？.2．有一個(gè)長度為11的有序表(1,2,11,15,24,28,30,56,69,70,80),元素的下標(biāo)依次為1,2,3,……,11，按折半查找對(duì)該表進(jìn)行查找。(1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹。（2）說出成功查找到元素56,,需要依次經(jīng)過與哪些元素的比較？（3）說出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)？3．(1)以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(3)n個(gè)葉結(jié)點(diǎn)的哈夫曼樹，總共有多少個(gè)結(jié)點(diǎn)？4.(1)一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56），利用堆排序（堆頂元素是最小元素）的方法建立初始堆（要求以完全二叉樹描述）。(2)對(duì)關(guān)鍵字序列(56,51,71,54,46,106)利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。(3)一組記錄的關(guān)鍵字序列為（60,47，80，57，39，41，46,30），利用歸并排序的方法,分別給出(1,1)歸并、(2,2)歸并、(4,4)歸并的結(jié)果序列。四、程序填空題1．以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。avoidInorder(structBTreeNode*BT)a{cbif(BT!=NULL){cb（1）;ed（2）;edInorder(BT->right);}f}f利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是（3）;圖圖52.設(shè)線性表為（16，20，26，24），以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,___(1)_____);___(2)_____;}while(___(3)_____);}3．以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進(jìn)行排序，完成程序中的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。voidbsort(NODEa[],intn){NODEtemp;inti,j,flag;for(j=1;（1）;j++);{flag=0;for(i=1;（2）;i++)if(a[i].key>a[i+1].key){flag=1;temp=a[i];（3）;（4）;}if(flag==0)break;}}設(shè)有序列6，4，5，8，2，1，給出由該程序經(jīng)過兩趟冒泡后的結(jié)果序列（5）4.以下函數(shù)為直接選擇排序算法，對(duì)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;j<=(2)_____;j++) if(a[j].key<a[k].key)(3)______; if(i!=k) { temp=a[i]; (4)_____; (5)____; } }}練習(xí)一答案一、單項(xiàng)選擇題1．C2．B3．B4．D5．C6．A7．B8．D9．A10．C11．C12．B13．D14．C15．D16．B17．D18．A19．D20．A21.C22．C23.D24．C25.D26．C27.A28．A29.A30．C二、填空題1．102．圖狀3．p->next;4．n-j5．?dāng)?shù)組元素6．二叉排序樹7．后出8．1，2，4，8，3，5，99．n-110．411．有序12．313．614．515．316．317.front==rear18．919.220.1221.n+122．3223.324．7三、綜合題1．63639481275圖6(2)按序號(hào)5,2,3,4。按元素23，10，11，144次(3)ASL=(1+2*2+3*4+4*2)/9=25/92．30158030158056662427011169286圖7(2)28,69,30,56(3)4次3.8181221222517529187349圖8(2)3:0004:0015:018:109:11(3)2n-14．(1)50505156579067圖9(2)46,51,54,56,71,106(3)(47,60)(57,80)(39,41)(30,46)(47,57,60,80)(30,39,41,46)(30,39,41,46,47,57,60,80)四、程序填空題1.（1）Inorder(BT->left)（2）printf(“%c”,BT->data)（3）dbfeac2．（1）p->data（2）p=p->next（3）p!=NULL3．（1）j<=n-1（2）i<=n-j（3）a[i]=a[i+1]（4）a[i+1]=temp（5）4,5,2,1,6,84．（1）n-1（2）n（3）k=j（4）a[i]=a[k](5)a[k]=temp練習(xí)二一、單項(xiàng)選擇題1．下面關(guān)于線性表的敘述錯(cuò)誤的是（）。A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C.線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)2．設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表,指針p指向其尾結(jié)點(diǎn),要?jiǎng)h除第一個(gè)結(jié)點(diǎn),則可利用下述語句head=head->next;和（）。A．p=head;B．p=NULL;C．head=p;D．p->next=head;3.以下數(shù)據(jù)結(jié)構(gòu)中是非線性結(jié)構(gòu)的是()。A.隊(duì)列B.棧C.二叉樹D.線性表4.以下說法正確的是()。A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間B.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)C．一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)D．線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間5．設(shè)有一個(gè)長度為18的順序表，要?jiǎng)h除第7個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。A．13B．12C．11D．106．把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)()稱為物理結(jié)構(gòu)。A．?dāng)?shù)據(jù)的處理方法B．?dāng)?shù)據(jù)的性質(zhì)C．?dāng)?shù)據(jù)的運(yùn)算D.數(shù)據(jù)元素間的邏輯關(guān)系7.兩個(gè)字符串相等的充要條件是（）。 A.兩個(gè)字符串的長度相等 B.同時(shí)具備(A)和(C)兩個(gè)條件C.兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等D.以上答案都不對(duì)8．順序表所具備的特點(diǎn)之一是（）。A．可以隨機(jī)訪問任一結(jié)點(diǎn)B．不需要占用連續(xù)的存儲(chǔ)空間C．插入元素的操作不需要移動(dòng)元素D．刪除元素的操作不需要移動(dòng)元素9.設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，在已知尾指針的條件下,選用下列（）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A.單向鏈表 B.單向循環(huán)鏈表C.雙向鏈表 D.雙向循環(huán)鏈表10．圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A．一對(duì)一B．一對(duì)多C．多對(duì)多D．每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼11．元素13，15，19，20順序依次進(jìn)棧，則該棧的不可能輸出序列是（）。進(jìn)棧出?？梢越惶孢M(jìn)行）。A．20，19，15，13B．13，15，19，20C．19，13，15，20D．15，13，20，1912．元素20，14，16，18按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A．18，16，14，20B．20，14，16，18C．18，16，20，14D．14，20，18，1613．設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，則在表中刪除結(jié)點(diǎn)B的操作為（）。A.p->next；=q； B.q->next=p->next；C.p->next=q->next；； D.q->next=p；14．設(shè)有一個(gè)12階的對(duì)稱矩陣A(左上角第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a5,4在一維數(shù)組B中的下標(biāo)是（）。A．12B．14C．13D．1115.棧和隊(duì)列的共同特點(diǎn)之一是()。A.都是先進(jìn)后出B..都是先進(jìn)先出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)16．設(shè)有一個(gè)長度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。A．25B．14C．15D．2317.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)()。A.需修改頭指針B.頭、尾指針都需要修改C.需修改尾指針D.頭、尾指針都不需要修改18．在一棵二叉樹中，若編號(hào)為5的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（）。A．12B．9C．11D．1019.字符串a(chǎn)1=“AEIJING“，a2=〝AEI“，a3=〝AEFANG〞a4=”AEFI“中最大的是（）。A.a1B.a2C.a3D.a420．一棵具有5層的完全二叉樹，最后一層有4個(gè)結(jié)點(diǎn)，則該樹總共有（）個(gè)結(jié)點(diǎn)。A．14B．15C．19D．1821．設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a6,2在一維數(shù)組B中的下標(biāo)是（）。A．23B．17C．21D．1822.如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)bcdfgeB．a(chǎn)bcedfgC．a(chǎn)cbfedgD．a(chǎn)bcfgdeggfabdec圖123.以下說法正確的是()。A.若二叉樹中左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。則該樹為二叉排序樹。B.二叉樹中任意一個(gè)非葉結(jié)點(diǎn)的值都大于其左子樹上所有結(jié)點(diǎn)的值,小于其右子樹上所有結(jié)點(diǎn)的值,則該樹為二叉排序樹。C.二叉樹中任意一個(gè)結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。則該樹為二叉排序樹。D.前序遍歷二叉排序樹可得到一個(gè)有序序列。24.字符串〝abcd321ABCD〞的子串是（）。A.〝21ABC〞B.〝abcABCD〞C.abcDD.〝321a〞25.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為()。A.2K-1B.2K+1C.2k-1D.2k-126.數(shù)組a經(jīng)初始化chara[]=“English”;a[1]中存放的是（）。A.字符EB.字符nC.〝n〞D.〝E〞27.如圖2所示，若從頂點(diǎn)6出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．6,9,3,2,8,7,4B．6,9,2,3,7,8,4C．6,2,7,9,8,4,3D．6,2,8,7,9,3,433289674圖228．如圖3所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)becdfB．a(chǎn)cfebdC．a(chǎn)ebcfdD．a(chǎn)edfcbbbdfeca圖329.如圖4所示，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A．a(chǎn)bcfegdB．a(chǎn)cbfedgC．a(chǎn)bcdfgeD．a(chǎn)bcfgdeggfabdec圖430.下圖5的拓?fù)湫蛄惺?)。A．52346B.23456C．56423D．523642234543465圖5二、填空題1.設(shè)：chara[]=“AEIJING“;該字符串在計(jì)算機(jī)中存儲(chǔ)時(shí)占________個(gè)字節(jié)。2.棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是:先進(jìn)_______。3．結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為________結(jié)構(gòu)。4．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的三項(xiàng)信息是_______。5.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有8行的稀疏矩陣A共有92個(gè)零元素，其相應(yīng)的三元組表共有4個(gè)元素。該矩陣A有________列。6．在對(duì)10個(gè)記錄的序列(9，35,19,77,2,10,53,45,27,68)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄10插入到有序表時(shí)，為尋找插入位置，元素間需比較_________次。（按升序排序）7.循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，最大存儲(chǔ)空間元素為MaxSize,采用少用一個(gè)存儲(chǔ)空間的模式，則判斷循環(huán)鏈隊(duì)列為空的條件是______為真。8.字符串a(chǎn)1=〝beijing〞,a2=〝bef〞,a3=〝beifang〞,a4=“befi〞最小的是________。9.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行______次元素間的比較。10．10個(gè)元素進(jìn)行冒泡法排序，,其中第5趟冒泡共需要進(jìn)行________次元素間的比較。11．設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有_______個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）12．________遍歷一棵二叉排序樹可得到一個(gè)有序序列。13．中序遍歷一棵________樹可得到一個(gè)有序序列。14.廣義表(c,(a,b,c),(d,e,f),((i,j),k))的長度是_______。15.待排序的序列為9,4,5,1,2,6,10,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為________。16.廣義表的(c,(b,a,b),f,e,((i,j),k))深度是________。17.廣義表((a,b),d,e,((i,j),k))的長度是________。18.序列4,2,5,3,8,6,采用冒泡排序算法(升序),經(jīng)一趟冒泡后,結(jié)果序列是________。19.廣義表的(c，a,(a,b),d,e,((i,j),k))深度是________。20.待排序的序列為8,3,4,1,2,5,9,采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為________。21.線性表用________方式存儲(chǔ)需要占用連續(xù)的存儲(chǔ)空間。22.線性表用________方式存儲(chǔ)可以隨機(jī)訪問。23.線性表用關(guān)鍵字________的順序方式存儲(chǔ)，可以用二分法排序。24.順序表,,6，5，1,2,4,3,8，7經(jīng)過一趟(1,1)歸并后的結(jié)果序列為________。三、綜合題1．（1）設(shè)有數(shù)據(jù)集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。(2)在上述二叉排序樹上進(jìn)行查找，給出成功查找到元素92的查找路徑,其中共經(jīng)過了多少次元素間的的比較。(3)有一個(gè)長度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，給出在等概率情況下查找成功的平均比較次數(shù)為。2．設(shè)查找表為序號(hào)1234567891011序列8162223415969818990121（1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹。（2）說明成功查找到元素90需要經(jīng)過多少次比較？（3）說明不成功查找元素82，依次與哪些元素進(jìn)行了比較，需要經(jīng)過多少次比較？3.(1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹，(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(3)一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），利用堆排序的方法建立的初始堆（堆頂元素是最小元素,以樹的形式給出）。4.(1)一組記錄的關(guān)鍵字序列為（36，69，46，28，30，35），給出利用堆排序（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述）。(2)對(duì)關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。(3)設(shè)有數(shù)據(jù)集合{30,73,101,4,8,9,2,81}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。程序填空題1.設(shè)線性表為（1,3,7,5），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。structnode{intdata;structnode*next;};typedefstructnodeNODE;#defineNULL0voidmain(){NODEa,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4;/*d是尾結(jié)點(diǎn)*/head=（1）;a.next=&b;b.next=&c;c.next=&d;（2）;/*以上結(jié)束建表過程*/p=head;/*p為工作指針，準(zhǔn)備輸出鏈表*/do{printf(“%d\n”,（3）);（4）;}while(p!=NULL);}畫出按該程序建立的單向鏈表的示意圖，說明程序運(yùn)行結(jié)束后p的指向。（5）2．設(shè)查找表為序號(hào)1234567891011序列8162223415969818990121（1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹。（2）說明成功查找到元素90需要經(jīng)過多少次比較？（3）說明不成功查找元素82，依次與