國家開放大學數(shù)據(jù)結(jié)構(gòu)（本）

PAGE練習一單選題1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的（）。DA.存儲結(jié)構(gòu)B.物理和存儲結(jié)構(gòu)C.物理結(jié)構(gòu)D.邏輯結(jié)構(gòu)2．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（）。DA.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)3．設有一個長度為n的順序表，要刪除第i個元素,則需移動元素的個數(shù)為（）。CA.iB.n-i-1C.n-iD.n-i+14．設頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點,則通過以下操作（)可使其成為單向循環(huán)鏈表。DA.head=p;B.p=head;C.p->next=NULL;D.p->next=head;5．一個棧的進棧序列是10，20，30，40，50，則棧的不可能輸出序列是（）（進棧出?？梢越惶孢M行）。BA．10,20,30,40,50B．40,30,50,10,20C．40,50,30,20,10D．50,40,30,20,106．在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行（）。DA．x=top;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．x=top->data;top=top->next;7．判斷一個順序隊列sq（最多元素為m）為空的條件是（）。CA．sq->rear-sq->front==mB．sq->rear-sq->front-1==mC．sq->front==sq->rearD．sq->front==sq->rear+18．串函數(shù)Strcat（a,b）的功能是進行串（）。DA．比較B．復制C．賦值D．連接9．稀疏矩陣采用壓縮存儲的目的主要是（）。DA．表達變得簡單B．對矩陣元素的存取變得簡單C．去掉矩陣中的多余元素D．減少不必要的存儲空間的開銷10.深度為5的二叉樹至多有（）個結(jié)點。CA.16B.32C.31D.1011.如圖所示二叉樹的中序遍歷序列是（）。BA.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh12.一個具有n個頂點的無向完全圖包含（）條邊。CA．n（n-1）B．n（n+1）C．n（n-1）/2D．n（n+1）/213.圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。AA．先序B．中序C．后序D．層次14.在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時，經(jīng)（）次比較后查找成功。BA．3B．4C．6D．815.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。DA.插入排序B.交換排序C.選擇排序D.歸并排序16.下面程序段的時間復雜度是（）。Dfor(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}A.O(1)B.O(log2n)C.O(n)D.O(n3)17．在一個單鏈表中p指向結(jié)點a,q指向結(jié)點a的直接后繼結(jié)點b，要刪除結(jié)點b，可執(zhí)行（）。AA．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;18．設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（）。CA.n-iB.n-i-1C.n-i+1D.i19．一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（）。BA．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，120．在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應執(zhí)行（）。CA．top->next=p;B．p->next=top->next;top->next=p;C．p->next=top;top=p;D．p->next=top->next;top=top->next;21．判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（）。CA．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%mD．Q->front!=(Q->rear+1)%m22．設有兩個串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（）。CA．求子串B．連接C．模式匹配D．求串長23．一個非空廣義表的表頭（）。DA．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子24.樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（）。DA.1B.0C.2D.-125.在一棵二叉樹上，第5層的結(jié)點數(shù)最多為（）。CA．8B．15C．16D．3226.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。CA．1/2B．1C．2D．427.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（）。DA．nB．eC．2nD．2e28.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。AA．37/12B．39/12C．41/12D．35/1229.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（）。AA.插入排序B.交換排序C.選擇排序D.歸并排序30．數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。DA.數(shù)據(jù)處理的方法B.相關算法C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關系的表示31．在一個單鏈表中p所指結(jié)點之后插入一個s所指的結(jié)點時，可執(zhí)行（）。DA．p->next=s;s->next=p->next;B．p->next=s->next;C．p=s->next;D．s->next=p->next;p->next=s;32．在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用語句（）。CA．p=q->next;B．p->next=q;C．p->next=q->next;D．q->next=NULL;33．表達式a*(b+c)-d的后綴表達式是（）。BA．a(chǎn)bcd*+-B．a(chǎn)bc+*d-C．a(chǎn)bc*++d-D．-+*abcd34．判斷順序棧s滿（元素個數(shù)最多n個）的條件是（）。CA．s->top==0B．s->top!=0C．s->top==n-1D．s->top!=n-135．串的長度是指（）。BA．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù)C．串中所含不同字符的個數(shù)D．串中所含非空格字符的個數(shù)36．廣義表(a,(d,a,b),h,(e,((i,j),k)))深度是()。DA．6B．10C．8D．437.在一棵二叉樹中，若編號為8的結(jié)點存在右孩子，則右孩子的順序編號為（）。DA．18B．16C．15D．1738.對于一個線性表，若要求既能進行較快地插入和刪除，又要求存儲結(jié)構(gòu)能夠反映數(shù)據(jù)元素之間的邏輯關系，則應該（）。BA．以順序存儲方式B．以鏈接存儲方式C．以索引存儲方式D．以散列存儲方式39.從未排序序列中挑選元素，并將其放入已排序序列的一端，此方法稱為（）。CA.插入排序B.交換排序C.選擇排序D.歸并排序40.每個存儲結(jié)點只存儲一個數(shù)據(jù)元素，各結(jié)點存儲在連續(xù)的存儲空間，該存儲方式是（）存儲方式。AA．順序B．鏈接C．索引D．散列41．元素4，6，8，10按順序依次進棧，按該棧的可能輸出序列依次入隊列，該隊列的可能輸出序列是（）（進棧出?？梢越惶孢M行）。DA．10，8，4，6B．10，6，4，8C．8，4，6，10D．10，8，6，442．如果以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時（）。CA．必須判斷棧是否滿B．判斷棧元素類型C．必須判斷棧是否空D．對棧不作任何判斷43．串與普通的線性表相比較，它的特殊性體現(xiàn)在（）。CA．順序的存儲結(jié)構(gòu)B．鏈接的存儲結(jié)構(gòu)C．數(shù)據(jù)元素是一個字符D．數(shù)據(jù)元素可以任意44．設有一個廣義表A(a)，其表尾為（）。CA．a(chǎn)B．(())C．（）D．(a)45.權(quán)值為{1，2，6，8}的四個結(jié)點構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（）。DA．18B．28C．19D．2946.一個具有n個頂點的有向完全圖包含（）條邊。AA．n（n-1）B．n（n+1）47．n（n-1）/2D．n（n+1）/247.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（）。CA．nB．n/2C．(n+1)/2D．(n-1)/248.當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。BA.插入排序B.交換排序C.選擇排序D.歸并排序49．下列說法中，不正確的是（）。DA．數(shù)據(jù)元素是數(shù)據(jù)的基本單位B．數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位C．數(shù)據(jù)可有若干個數(shù)據(jù)元素構(gòu)成D．數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成50.每個存儲結(jié)點不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是（）存儲方式。BA．順序B．鏈接C．索引D．散列51．向順序棧中壓入新元素時，應當（）。AA．先移動棧頂指針，再存入元素B．先存入元素，再移動棧頂指針C．先后次序無關緊要D．同時進行52．一般情況下，將遞歸算法轉(zhuǎn)換成等價的非遞歸算法應該設置（）。AA．棧B．隊列C．堆?；蜿犃蠨．數(shù)組53．空串與空格串（）。BA．相同B．不相同C．可能相同D．無法確定54．廣義表(f,h,(a,b,d,c),d,e,((i,j),k))的長度是()。AA．6B．10C．8D．455.二叉樹第k層上最多有（）個結(jié)點。BA．2kB．2k-1C．2k-1D．2k-156.對于具有n個頂點的圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。BA．nB．n2C．n-1D．(n-1)257.采用折半查找方法查找長度為n的線性表時，其算法的時間復雜度為（）。DA．O(n2)B．O(nlog2n)C．O(n)D．O(log2n)

數(shù)據(jù)結(jié)構(gòu)（本）試題一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）1.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關的是數(shù)據(jù)的（D）。A.存儲結(jié)構(gòu)B.物理和存儲結(jié)構(gòu)C.物理結(jié)構(gòu)D.邏輯結(jié)構(gòu)2．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（D）。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)3．設有一個長度為n的順序表，要刪除第i個元素,則需移動元素的個數(shù)為（C）。A.i B.n-i-1C.n-i D.n-i+14．設頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點,則通過以下操作（D)可使其成為單向循環(huán)鏈表。A.head=p;B.p=head;C.p->next=NULL;D.p->next=head;5．一個棧的進棧序列是10，20，30，40，50，則棧的不可能輸出序列是（B）（進棧出棧可以交替進行）。A．10,20,30,40,50B．40,30,50,10,20C．40,50,30,20,10D．50,40,30,20,106．在一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用x保存被刪結(jié)點的值，則執(zhí)行（D）。A．x=top;top=top->next;B．x=top->data;C．top=top->next;x=top->data;D．x=top->data;top=top->next;7．判斷一個順序隊列sq（最多元素為m）為空的條件是（C）。A．sq->rear-sq->front==mB．sq->rear-sq->front-1==mC．sq->front==sq->rearD．sq->front==sq->rear+18．串函數(shù)Strcat（a,b）的功能是進行串（D）。A．比較B．復制C．賦值D．連接9．稀疏矩陣采用壓縮存儲的目的主要是（D）。A．表達變得簡單B．對矩陣元素的存取變得簡單C．去掉矩陣中的多余元素D．減少不必要的存儲空間的開銷10.深度為5的二叉樹至多有（C）個結(jié)點。A.16B.32C.31D.1011.如圖所示二叉樹的中序遍歷序列是（B）。A.abdgcefhB.dgbaechfC.gdbehfcaD.abcdefgh12.一個具有n個頂點的無向完全圖包含（C）條邊。A．n（n-1）B．n（n+1）C．n（n-1）/2D．n（n+1）/213.圖的深度優(yōu)先遍歷算法類似于二叉樹的（A）遍歷。A．先序B．中序C．后序D．層次14.在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86時，經(jīng)（B）次比較后查找成功。A．3B．4C．6D．815.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（D）。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ枴啊獭被虼虿嫣枴啊痢?。每小題2分，共30分）1.數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。(√)2．數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關系稱為樹狀結(jié)構(gòu)。(×)3．設有一個不帶頭結(jié)點的單向循環(huán)鏈表，結(jié)點的指針域為next，指針p指向尾結(jié)點，現(xiàn)要使p指向第一個結(jié)點，可用語句p=p->next;。(√)4．要在一個單向鏈表中p所指向的結(jié)點之后插入一個s所指向的新結(jié)點，若鏈表中結(jié)點的指針域為next，可執(zhí)行p->next=s;s->next=p->next；的操作。(×)5.鏈式棧與順序棧相比，一個明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情況。(√)6.在一個順序存儲的循環(huán)隊列中,隊頭指針指向隊頭元素的后一個位置。(×)7.一個遞歸算法不必包括遞歸終止條件。(×)8．空串的長度是1。(×)9.一個廣義表((a),((b),c),(((d))))的長度為3，深度為4。(√)10．如果結(jié)點A有3個兄弟，而且B是A的雙親，則B的度是4。(√)11.哈夫曼樹只存在著雙支結(jié)點，不存在單支結(jié)點。(√)12.無向圖的鄰接矩陣一定是對稱的。（√）13.AOV網(wǎng)拓撲排序的結(jié)果是惟一的。（×）14.折半查找的前提條件是，查找表中記錄相應的關鍵字值必須有序或者部分有序。(×)15.對16個元素的序列用冒泡排法進行排序，通常需要進行15趟冒泡。(√)三、綜合應用及程序設計題（每小題5分，共25分）1．設有一個不帶頭結(jié)點的單向鏈表，頭指針為head，p、prep是指向結(jié)點類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結(jié)點的信息重復輸入，以下程序段是在該單向鏈表中查找這相鄰兩個結(jié)點，把該結(jié)點的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。（A）prep=head;p=prep->next;while(p->data!=prep->data){prep=p;____①____;}printf(“%d”,p->data);prep->next=____②____;A.①p=p->next②p->nextB.①prep->data②p->nextC.①p->next②p=p->nextD.①p->next②p->data2．設SeqStack為順序棧，寫出下列程序段執(zhí)行后的結(jié)果。SeqStackS;InitStack(S);Push(S,3);Push(S,4);Push(S,5);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)Push(S,a[i]);while(!StackEmpty(S))Printf(“%d“,Pop(S));執(zhí)行后的輸出結(jié)果為：__________A________。1512851333581213151513128531512133853．以下程序段執(zhí)行后，c的值為（A）。char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}inti,c=0for(i=0;i<5;i++)if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.12374．以1，2，3，6，7，8作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹是如下哪個圖？（B）379273792717103612866727151233128771236612631982793938271512123675．以下直接插入排序算法對存放在a[0],a[1],···,a[n-1]中，長度為n的記錄序列按關鍵字key由小到大排序，完成程序中空格部分。(C)voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<n;i++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[j].key){a[j+1]=a[j];_______;}a[j+1]=temp;}}A.j++B.i++C.j--D.i--

數(shù)據(jù)結(jié)構(gòu)（本）試題一、單項選擇題（把合適的選項編號填寫在括號內(nèi)。每小題3分，共45分）1．在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（D）。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D.線性結(jié)構(gòu)和非線性結(jié)構(gòu)2.下面程序段的時間復雜度是（D）。for(i=1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)c[i][j]=c[i][j]+a[i][k]*b[k][j];}O(1)B.O(log2n)C.O(n)D.O(n3)3．在一個單鏈表中p指向結(jié)點a,q指向結(jié)點a的直接后繼結(jié)點b，要刪除結(jié)點b，可執(zhí)行（A）。A．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;4．設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（C）。A.n-iB.n-i-1C.n-i+1D.i5．一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（B）。A．4，3，2，1B．1，2，3，4C．1，4，3，2D．3，2，4，16．在一個棧頂指針為top的鏈棧中，將一個p指針所指的結(jié)點入棧，應執(zhí)行（C）。A．top->next=p;B．p->next=top->next;top->next=p;C．p->next=top;top=p;D．p->next=top->next;top=top->next;7．判斷一個循環(huán)隊列Q（最多元素為m）為滿的條件是（C）。A．Q->front==Q->rearB．Q->front!=Q->rearC．Q->front==(Q->rear+1)%mD．Q->front!=(Q->rear+1)%m8．設有兩個串p和q，其中q是p的子串，q在p中首次出現(xiàn)的位置的算法稱為（C）。A．求子串B．連接C．模式匹配D．求串長9．一個非空廣義表的表頭（D）。A．不可能是原子B．只能是子表C．只能是原子D．可以是子表或原子10.樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（D）。A.1B.0C.2D.-111.在一棵二叉樹上，第5層的結(jié)點數(shù)最多為（C）。A．8B．15C．16D．3212.在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（C）倍。A．1/2B．1C．2D．413.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則所有頂點鄰接表中的結(jié)點總數(shù)為（D）。A．nB．eC．2nD．2e14.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(shù)為（A）。A．37/12B．39/12C．41/12D．35/1215.從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（A）。A.插入排序 B.交換排序C.選擇排序 D.歸并排序二、判斷題（根據(jù)敘述正確與否在其后面的括號內(nèi)打?qū)μ枴啊獭被虼虿嫣枴啊痢?。每小題2分，共30分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關系，是用戶根據(jù)應用需要建立的。（√）2．數(shù)據(jù)結(jié)構(gòu)中,元素之間存在多對多的關系稱為圖狀結(jié)構(gòu)。(√)3．設有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->next=head。(√)4．設有一個單向循環(huán)鏈表，結(jié)點的指針域為next，頭指針為head，指針p指向表中某結(jié)點，若邏輯表達式p->next==head;的結(jié)果為真，則p所指結(jié)點為尾結(jié)點。(√)5.棧和隊列都是特殊的線性表,但它們對存取位置的限制不同。(√)6.棧是限定在表的兩端進行插入和刪除操作的線性表，又稱為先進先出表。(×)7.遞歸定義的數(shù)據(jù)結(jié)構(gòu)通常用遞歸算法來實現(xiàn)對它的操作。(√)8．一個空格的串的長度是0。(×)9.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行號、列號和元素值三項信息。(√)10．深度為k的完全二叉樹至少有2k-1個結(jié)點。（×）11.完全二叉樹中沒有度為1的結(jié)點。（×）12.圖的生成樹是惟一的。（×）13.對連通圖進行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（√）14.在順序查找、折半查找、哈希表查找3種方法中，平均查找長度與結(jié)點個數(shù)n無關的查找方法是折半查找。(×)15.n個元素進行冒泡法排序，通常需要進行n-1趟冒泡。(√)三、綜合應用及程序設計題（每小題5分，共25分）1．在下面空格處填寫一條語句，以使下面的鏈式隊列全部元素出隊的算法完整。(C)intwrite(LinkQueue*q){QueueNode*p;if(q->front==q->rear)/*隊空*/{printf(“隊空！無元素可取”);exit(0);}while(q->front->next!=NULL){p=q->front->next;q->front->next=p->next;/*出隊*/printf(“%4d”,p->data);free(p);/*釋放已出隊結(jié)點*/}_____________/*隊空時，頭尾指針指向頭結(jié)點*/}q->front=q->rear;q=q->next;q->rear=q->front;D.p=p->next;2．以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。(C)voidPreorder(structBTreeNode*BT){if(BT!=NULL){_________________;Preorder(BT-->left);Preorder(BT-->right);}}A.printf(“%c”,BT->left)B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)3．9684968457969654789784569784569684754．設關鍵字序列為：（36，69，46，28，30，74）（1）將此序列用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結(jié)果為（D）。（本小題3分）A.30，28，46，36，69，74

B.28，30，36，46，69，74C.28，30，46，36，69，74

D.

30，28，36，46，69，74（2）用冒泡法對上述序列排序，經(jīng)過兩趟冒泡的結(jié)果序列為（A）。（本小題2分）

A.36，28，30，46，69，74

B.36，46，28，20，69，74

C.38，36，30，46，69，74

D.28，36，30，46，69，745．設數(shù)據(jù)序列為：{53,30,37,12,45,24,96}（1）從空二叉樹開始逐個插入該數(shù)據(jù)序列來形成二叉排序樹，若希望高度最小，應該選擇的序列是（B）。（本小題3分）A．45,24,53,12,37,96,30B．37,24,12,30,53,45,96C．12,24,30,37,45,53,96D．30,24,12,37,45,96,53（2）用鏈接地址法將該數(shù)據(jù)序列構(gòu)造哈希表，哈希函數(shù)為H(key)=keymod13，則散列地址為1的鏈中有（B）個記錄。（本小題2分）A.0 B.1 C.2 D.3

練習三綜合應用及程序設計題1．設有一個不帶頭結(jié)點的單向鏈表，頭指針為head，p、prep是指向結(jié)點類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結(jié)點的信息重復輸入，以下程序段是在該單向鏈表中查找這相鄰兩個結(jié)點，把該結(jié)點的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。prep=head;p=prep->next;while(p->data!=prep->data){prep=p;____①____;}printf(“%d”,p->data);prep->next=____②____;A.①p=p->next②p->nextB.①prep->data②p->nextC.①p->next②p=p->nextD.①p->next②p->dataA2.在下面空格處填寫一條語句，以使下面的進棧算法完整。voidPush(structSeqStack*s,ElemTypex){if(s->top==MaxSize-1){printf(“棧滿溢出錯誤！\n”);exit(1);}________s->data[s->top]=x;}s->top=s->data;B.s->data++;C.s->top++;D.s->data=s->top;C3．設有一個頭指針為head的不帶頭結(jié)點單向鏈表中（結(jié)點類型為NODE），p為指向該鏈表中某個結(jié)點的指針。以下程序段為插入一個指針為s的結(jié)點，使它成為p結(jié)點的直接前驅(qū)，請選擇其中空格的選項。NODE*q;q=head;while(q->next!=p)____①____;s->next=p;____②____;①A.p=p->next B.q=q->nextC.s=s->nextD.head=head->nextB②A.p->next=qB.p->next=sC.q->next=sD.q->next=pC4.設線性表以不帶頭結(jié)點的單向鏈表存儲，鏈表頭指針為head。以下程序的功能是輸出鏈表中各結(jié)點中的數(shù)據(jù)域data，完成程序中空格部分。#defineNULL0voidmain(){NODE*head,*p;p=head;/*p為工作指針*/do{printf(“%d\n”,p->data);____①____;}while(____②____);}①A.head=p->next B.p=head->nextC.p=p->nextD.head=head->nextC②A.p==NULLB.p!=NULLC.p!=headD.p==headB5.寫出下列程序執(zhí)行后的結(jié)果SeqQueueQ;InitQueue(Q);inta[4]={5,8,12,15};for(inti=0;i<4;i++)InQueue(Q,a[i]);InQueue(Q,OutQueue(Q));InQueue(Q,30);InQueue(Q,OutQueue(Q)+10);while(!QueueEmpty(Q))printf(“%d”,OutQueue(Q));執(zhí)行后的輸出結(jié)果為：__________________。58121530121553018812153018121551830B6．設SeqStack為順序棧，寫出下列程序段執(zhí)行后的結(jié)果。SeqStackS;InitStack(S);Push(S,3);Push(S,4);Push(S,5);intx=Pop(S)+2*Pop(S);Push(S,x);inti,a[4]={5,8,12,15};for(i=0;i<4;i++)Push(S,a[i]);while(!StackEmpty(S))Printf(“%d“,Pop(S));執(zhí)行后的輸出結(jié)果為：__________________。151285133358121315151312853151213385A7．以下程序段執(zhí)行后，c的值為（）。char*a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}inti,c=0for(i=0;i<5;i++)if(strcmp(a[i],”1237”)==0)c++;A.2B.5C.0D.1237A8．以下程序是先序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點）。voidPreorder(structBTreeNode*BT){if(BT!=NULL){_________________;Preorder(BT-->left);Preorder(BT-->right);}}A.printf(“%c”,BT->left)B.printf(“%c”,BT->right)C.printf(“%c”,BT->data)D.printf(“%d”,BT->data)C9.設某二叉樹先序遍歷為abdec，中序遍歷為dbeac（1）該二叉樹的圖形是（）。BdeabdeabcabcdeababdceabcdeC.D.（2）寫出該二叉樹后序遍歷的結(jié)果（）。BA.edbcaB.debcaC.ebdcaD.bceda10．已知某帶權(quán)圖的鄰接矩陣如下所示：從頂點1出發(fā)的廣度優(yōu)先搜索序列為（）。AA.1，2，3，4，5，6B.1，4，3，2，6，5C.1，3，2，4，6，5D.1，2，4，3，5，611．以1，2，3，6，7，8作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹是如下哪個圖？（）B3792737927171036128667271512331287712366126319827939382715121236712．以下直接插入排序算法對存放在a[0],a[1],···,a[n-1]中，長度為n的記錄序列按關鍵字key由小到大排序，完成程序中空格部分。voiddisort(NODEa[],intn){inti,j;NODEtemp;for(i=1;i<n;i++){temp=a[i];j=i-1;while(j>=0&&temp.key<a[j].key){a[j+1]=a[j];_______;}a[j+1]=temp;}}A.j++