1、國家開放大學數據結構（本）形考作業1-4參考答案形考作業1一、單項選擇題（每小題3分，共60分）1.把數據存儲到計算機中，并具體體現數據元素間的邏輯結構稱為（ ）。A. 算法的具體實現B. 物理結構C. 邏輯結構D. 給相關變量分配存儲單元2.下列說法中，不正確的是（ ）。A. 數據項是數據中不可分割的最小可標識單位B. 數據元素是數據的基本單位C. 數據項可由若干個數據元素構成D. 數據可有若干個數據元素構成3.一個存儲結點存儲一個（ ）。A. 數據結構B. 數據元素C. 數據類型D. 數據項4.數據結構中，與所使用的計算機無關的是數據的（ ）。A. 物理和存儲結構B. 物理結構C. 邏輯結

2、構D. 存儲結構5.在線性表的順序結構中，以下說法正確的是（ ）。A. 邏輯上相鄰的元素在物理位置上不一定相鄰B. 邏輯上相鄰的元素在物理位置上也相鄰C. 進行數據元素的插入、刪除效率較高D. 數據元素是不能隨機訪問的6.對鏈表, 以下敘述中正確的是（ ）。A. 結點占用的存儲空間是連續的B. 插入刪除元素的操作一定要要移動結點C. 可以通過下標對鏈表進行直接訪問D. 不能隨機訪問任一結點7.下列的敘述中，不屬于算法特性的是（ ）。A. 可讀性B. 輸入性C. 可行性D. 有窮性8.算法的時間復雜度與（ ）有關。A. 算法本身B. 計算機的操作系統C. 數據結構D. 所使用的計算機9.設有一個

3、長度為n的順序表，要在第i個元素之前（也就是插入元素作為新表的第i個元素），插入一個元素，則移動元素個數為（ ）。A. n-i+1B. n-i-1C. n-iD. i10.設有一個長度為n的順序表，要刪除第i個元素移動元素的個數為（ ）。A. iB. n-iC. n-i-1D. n-i+111.在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現要刪除q所指結點，可用語句（ ）。A. p->next=q->nextB. p=q->nextC. p->next=qD. q->next=NULL12.在一個單鏈表中p所指結點之后插入

4、一個s所指的結點時，可執行（ ）。A. p->next=s->next;B. p->next= s; s->next= p->nextC. p=s->nextD. s->next=p->next; p->next=s;13.非空的單向循環鏈表的尾結點滿足（ ）（設頭指針為head，指針p指向尾結點）。A. p->next=headB. p=NULLC. p->next=NULLD. p= head14.鏈表不具有的特點是（ ）。A. 邏輯上相鄰的元素在物理位置上不一定相鄰B. 插入刪除不需要移動元素C. 不必事先估計存儲空間D.

5、 可隨機訪問任一元素15.帶頭結點的鏈表為空的判斷條件是（ ）（設頭指針為head）。A. head =NULLB. head!=NULLC. head->next=NULLD. head->next=head16.在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（ ）。A. 20B. 25C. 21D. 1917.有關線性表的正確說法是（ ）。A. 線性表至少要求一個元素B. 表中的元素必須按由小到大或由大到下排序C. 每個元素都有一個直接前驅和一個直接后繼D. 除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前

6、驅和一個直接后繼18.向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（ ）個元素。A. 8B. 63C. 7D. 63.519.一個順序表第一個元素的存儲地址是90，每個元素的長度為2，則第6個元素的地址是（ ）。A. 102B. 100C. 106D. 9820. 在一個不帶頭結點的單循環鏈表中，p、q分別指向表中第一個結點和尾結點，現要刪除第一個結點，且p、q仍然分別指向新表中第一個結點和尾結點。可用的語句是p=p->next;和（ ）。A. p->next=qB. p=q->nextC. q=pD. q->next=p二、判斷題（

7、每小題2分，14題，共28分）21.數據元素可以有一個或多個數據項組成。（）22.數據元素之間的抽象關系稱為物理結構。（×）23.數據的邏輯結構在計算機中的表示稱為邏輯結構。（×）24.數據的邏輯結構是與存儲該結構的計算機相關的。（×）25.數據結構中,元素之間存在多對多的關系稱為樹狀結構。（×）26.通常可以把一本含有不同章節的書的目錄結構抽象成線性結構。（×）27.通常可以把某城市中各公交站點間的線路圖抽象成樹型結構。（×）28.設有一個不帶頭結點的單向循環鏈表，結點的指針域為next，指針p指向尾結點，現要使p指向第一個結點，可

8、用語句p=p->next;。（）29.設有一個單向鏈表，結點的指針域為next，頭指針為head，p指向尾結點，為了使該單向鏈表改為單向循環鏈表，可用語句p->next=head。（）30.設有一個單向循環鏈表，結點的指針域為next，頭指針為head，指針p指向表中某結點，若邏輯表達式p->next=head;的結果為真，則p所指結點為尾結點。（）31.要在一個單向鏈表中p所指向的結點之后插入一個s所指向的新結點，若鏈表中結點的指針域為next，可執行 p->next=s; s->next= p->next；的操作。（×）32.要在一個單向鏈表中

9、刪除p所指向的結點，已知q指向p所指結點的直接前驅結點，若鏈表中結點的指針域為next，則可執行q->next= p->next；（）33.要在一個帶頭結點的單向循環鏈表中刪除頭結點，得到一個新的不帶頭結點的單向循環鏈表，若結點的指針域為next，頭指針為head，尾指針為p，則可執行head=head-> next; p->next=head；。（）34.設有一個單向循環鏈表，頭指針為head，鏈表中結點的指針域為next，p指向尾結點的直接前驅結點，若要刪除尾結點，得到一個新的單向循環鏈表，可執行操作p->next=head；。（）三、程序填空題（每小題6分，

10、共12分。請點擊正確選項，然后拖拽至相應的方框上）35.設線性表以不帶頭結點的單向鏈表存儲，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結點中的數據域data,完成程序中空格部分。 #define NULL 0 void main( ) NODE *head ,*p ; p=head; /*p為工作指針*/ do printf(“%dn”,（p>data）; （p=p>next）; while（p!=NULL）; p>datap=p>nextp!=NULL36.設有一個頭指針為head的不帶頭結點單向鏈表，p、q是指向鏈表中結點類型的指針變量，p指向鏈表中結點a,

11、 （設鏈表中沒有結點的數據域與結點a的數據域相同）,寫出相關語句 (1)使該單向鏈表成為單向循環鏈表 (2)插入結點s,使它成為a結點的直接前驅q=p; x=p->data;while （q>next!=NULL）q=q->next;q->next=head;q=p; p=p->next;while(p->data!=x) q=p;（p=p>next）s->next=p;（q>next=s） p=p>nextq>next=sq>next!=NULL形考作業2一、單項選擇題（每小題2分，共50分）1.若讓元素1，2，3依次進

12、棧，則出棧順序不可能為（ ）。A. 1，3，2B. 3，1，2C. 3，2，1D. 2，1，32.一個隊列的入隊序列是1，2，3，4。則隊列的輸出序列是（ ）。A. 3，2，4，1B. 1，2，3，4C. 1，4，3，2D. 4，3，2，13.向順序棧中壓入新元素時，應當（ ）。A. 先后次序無關緊要B. 同時進行C. 先存入元素，再移動棧頂指針D. 先移動棧頂指針，再存入元素4.在一個棧頂指針為top的鏈棧中，將一個p指針所指的結點入棧，應執行（ ）。A. p->next=top->next;top=top->next;B. top->next=p;C. p->

13、next=top->next;top->next=p;D. p->next=top;top=p;5.在一個棧頂指針為top的鏈棧中刪除一個結點時，用 x保存被刪結點的值，則執行（ ）。A. x=top;top=top->next;B. x=top->data;top=top->next;C. x=top->data;D. top=top->next;x=top->data;6.判斷一個順序隊列（最多元素為m）為空的條件是（ ）。A. front=rearB. rear=m-1C. rear=mD. front=rear+17.判斷一個循環隊

14、列為滿的條件是（ ）。A. (rear+1)%MaxSize=frontB. front=rear+1C. rear%MaxSize= =frontD. rear=MaxSize8.判斷棧滿（元素個數最多n個）的條件是（ ）。A. top=-1B. top=0C. top=n-1D. top!=09.設有一個20階的對稱矩陣A（第一個元素為a1,1），采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始）， 則矩陣元素a6,2在一維數組B中的下標是（ ）。A. 23B. 21C. 28D. 1710.在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據

15、緩沖區，主機將要輸出的數據依次寫入緩沖區中，而打印機則從緩沖區中取出數據打印，該緩沖區應該是一個（ ）結構。A. 堆棧B. 線性表C. 數組D. 隊列11.一個遞歸算法必須包括（ ）。A. 遞歸部分B. 終止條件和迭代部分C. 迭代部分D. 終止條件和遞歸部分12.在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點的運算為（ ）。A. f=f->next;B. r=r->next;C. f=r->next;D. r=f->next;13.在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算為（ ）。A. f->next=s;f=s;B.

16、s->next=r;r=s;C. s->next=f;f=s;D. r->next=s;r=s;14.數組a經初始化char a =“English”;a7中存放的是（ ）。A. 變量hB. 字符hC. "h"D. 字符串的結束符15.設主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。A. AbcB. BcdC. BCdD. ABC16.字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ ）。

17、A. a4B. a1C. a3D. a217.兩個字符串相等的條件是（ ）。A. 兩串包含的字符相同B. 兩串的長度相等，并且對應位置上的字符相同C. 兩串的長度相等，并且兩串包含的字符相同D. 兩串的長度相等18.一維數組A采用順序存儲結構，每個元素占用6個字節，第6個元素的存儲地址為100，則該數組的首地址是（ ）。A. 70B. 28C. 90D. 6419.一個非空廣義表的表頭（ ）。A. 只能是原子B. 可以是子表或原子C. 只能是子表D. 不可能是原子20.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A，其相應的三元組表共有6個元素，矩陣A共有（ ）個零元素。

18、A. 72B. 10C. 74D. 821.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6，其相應的三元組表中的第7個元素是（ ）。A. （10，8，7）B. （7，10，8）C. （7，8，10）D. （10，8，6）22.對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入棧結點，并給該 結點賦值a，則執行: p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ ）。A. p->next=top;top=p;B. p->next=top;p=to

19、p;C. top=top->next;p=top;D. top->next=p;p=top;23.頭指針為head的帶頭結點的單向鏈表為空的判定條件是（ ）為真。A. head=NULLB. head->next!=NULLC. head->next!=NULLD. head->next=NULL24.設有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），B數組共有55個元素,則該矩陣是（ ）階的對稱矩陣。A. 20B. 5C. 15D. 1025.數組a經初始化char a =“English”;a1中存放的是

20、（ ）。A. 字符EB. "E"C. "n"D. 字符n二、判斷題（每小題2分，16題，共32分）26.設有一個鏈棧，棧頂指針為hs，現有一個s所指向的結點要入棧，則可執行操作。hs=s；s-> next=hs; （×）27.設有一個非空的鏈棧，棧頂指針為hs，要進行出棧操作，用x保存出棧結點的值，棧結點的指針域為next，則可執行hs=hs->next ;x=hs->data;（）28.有一個鏈棧，棧頂指針為h，現有一個p所指向的結點要入棧，則可執行操作p->next=h;和h=p；（）29.設有一個非空的鏈棧，棧頂指

21、針為hs，要進行出棧操作，用x保存出棧結點的值，棧結點的指針域為next，數據域為data，則可執行hs= hs->next; x= hs->data; （×）30. 在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next，則插入所指結點的操作為r->next=s；r=s；（）31.在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的指針域為next，s指向一個要入 隊的結點，則入隊操作為r=s；r->next=s；（×）32.在一個不帶頭結點的非空鏈隊中，f和r分別為隊頭和隊尾指針，隊結點的數據域為data，指針域為next，若要進行出隊

22、操作，并用變量x存放出隊元素的數據值，則相關操作為x=f->data; f=f->next; （）33.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個6行7列的稀疏矩陣A相應的三元組表共有8個元素,則矩陣A共有34個零元素。（）34.循環隊列的最大存儲空間為MaxSize，隊頭指針為f，隊尾指針為r，當（r+1）%MaxSize=f 時表明隊列已滿。（）35.循環隊列的隊頭指針為f，隊尾指針為r，當r= =f時表明隊列已滿。（×）36.空串的長度是0；空格串的長度是空格字符的個數。（）37.對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包括該元素的行下標、列下標、和

23、非零元素值三項信息。（）38.循環隊列的引入，目的是為了克服假上溢。（）39.設有n階對稱矩陣A，用一維數組s壓縮存儲A的下三角元素，s的下標從零開始，元素 s26相應于A中的元素為a 7,5。（×）40.循環隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷棧空或棧滿，若隊頭指針front=4，當隊尾指針rear=3時隊滿。（）41.循環隊列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效的判斷棧空或棧滿，若隊頭指針front=4，隊尾指針rear=3時，隊列中共有5個元素。（）三、程序選擇填空題（每小題9分，共18分。請點擊正確選項，然后拖拽至

24、相應的方框上）42.以下函數為鏈棧的進棧操作，x是要進棧的結點的數據域，top為棧頂指針struct node ElemType data;struct node *next;struct node *top ;void Push(ElemType x) struct node *p; p=(struct node*)malloc（A.sizeof(struct node)）; p->data=x; （p>next=top）; （top=p）; A.sizeof(struct node)top=pp>next=top43.以下函數為鏈隊列的入隊操作，x為要入隊的結點的數據域的

25、值，front、rear分別鏈隊列的隊頭、隊尾指針struct node ElemType data;struct node *next;struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) malloc（(sizeof(struct node)）; p->data=x; p->next=NULL; （rear>next=p）; rear（p）; rear>next=pp(sizeof(struct node)形考作業3一、單項選擇題（每小題2分，共38分

26、）1.假定一棵二叉樹中，雙分支結點數為15，單分支結點數為30，則葉子結點數為（ ）。A. 17B. 47C. 16D. 152.二叉樹第k層上最多有（ ）個結點。A. 2kB. 2k-1C. 2k-1D. 2k-13.將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1，則編號為69的結點的雙親結點的編號為（ ）。A. 33B. 35C. 34D. 364.如果將給定的一組數據作為葉子數值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（ ）。A. 平衡二叉樹B. 二叉樹C. 完全二叉樹D. 哈夫曼樹5.在一棵度具有5層的滿二叉樹中結點總數為（ ）

27、。A. 16B. 31C. 33D. 326.一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（ ）個結點。A. 72B. 38C. 31D. 377.利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為（ ）。A. 12B. 18C. 16D. 308.在一棵樹中，（ ）沒有前驅結點。A. 分支結點B. 葉結點C. 樹根結點D. 空結點9.設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數都為2，該樹結點中共有20個指針域為空,則該樹有（ ）個葉結點。 A. 10B. 9C. 21D. 2210.在一個圖G中，所有頂點的度數之和等于所

28、有邊數之和的（ ）倍。A. 1/2B. 2C. 4D. 111.鄰接表是圖的一種（ ）。A. 索引存儲結構B. 順序存儲結構C. 散列存儲結構D. 鏈式存儲結構12.圖的深度優先遍歷算法類似于二叉樹的（ ）遍歷。A. 后序B. 層次C. 先序D. 中序13.已知下圖所示的一個圖，若從頂點V1出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V4V8V3V5V6V7B. V1V3V6V7V2V4V5V8C. V1V2V4V5V8V3V6V7 D. V1V2V4V8V5V3V6V714.已知如下圖所示的一個圖，若從頂點a出發，按廣度優先搜索法進行遍歷，則可能得到的一種

29、頂點序列為（ ）。 A. aebcfdB. aecbdfC. aedfcbD. abecdf15.圖狀結構中數據元素的位置之間存在（ ）的關系。A. 一對多B. 每一個元素都有一個且只有一個直接前驅和一個直接后繼C. 一對一D. 多對多16.在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為（ ）。A. 2i-1B. 2i+1C. 2iD. 2i+217.一棵具有16個結點的完全二叉樹，共有（ ）層。(設根結點在第一層)A. 4B. 5C. 6D. 718.對二叉排序樹進行（ ）遍歷，可以使遍歷所得到的序列是有序序列。A. 中序B. 按層次C. 后序D. 前序19.已知一個圖的邊

30、數為m，則該圖的所有頂點的度數之和為（ ）。A. m/2B. 2m+1C. 2mD. m二、判斷題 （每小題1分，共10分）20.一棵二叉樹的葉結點（終端結點）數為5，單分支結點數為2，該樹共有11個結點。（）21.一棵有14個結點的完全二叉樹，則它的最高層上有7個結點。（）22.一棵二叉樹有6個葉結點，則該樹總共有11個結點。（×）23.根據搜索方法的不同，圖的遍歷有先序；中序；后序三種方法。（×）24.對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有n-1個指針域空。（×）25.設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數，該葉結點的雙親結點

31、的編號為10，該完全二叉樹一共有21個結點。（）26.設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數，該葉結點的雙親結點的編號為9，該完全二叉樹一共有19個結點。（×）27.按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優先遍歷和深度優先遍兩種方法。（×）28.一棵有8個權重值構造的哈夫曼數，共有17個結點。（×）29.一棵有7個葉結點的二叉樹，其1度結點數的個數為2，則該樹共有15個結點。（）三、程序填空題（每空6分，共12分。請點擊正確選項，然后拖拽至相應的方框上）30.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指

32、針域分別為left和right，數據域data為字符型，BT指向根結點）。完成程序中空格部分。 void Inorder (struct BTreeNode *BT)if( BT!=NULL)Inorder(BT->left);（Inorder(BT> right)）（printf(“%c”,BT>data)）利用上述程序對左圖進行后序遍歷，結果是（d,e,b,f,c,a）;Inorder(BT> right)d,e,b,f,c,aprintf(“%c”,BT>data)31.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結構中左、右指針域分別為

33、left和right，數據域data為字符型，BT指向根結點）。 void Inorder (struct BTreeNode *BT)if(BT!=NULL)Inorder(BT->left);（printf(“%c”,BT>data)）;（Inorder(BT>right)）;利用上述程序對右圖進行中序遍歷，結果是（d,b,e,a,f,c）;d,b,e,a,f,cprintf(“%c”,BT>data)Inorder(BT>right)四、綜合應用題（每小題8分，5題，共40分）32.（1）以3，4，5，8，9，作為葉結點的權，構造一棵哈夫曼樹。該樹的帶權路徑

34、長度為（）。A,64 B.65 C. 62 D. 66（2）權重為3的葉結點的哈夫曼編碼為（）。 A.010 B.0101 C.000 D.011133.（1）以2，3，4，7，8，9作為葉結點的權，構造一棵哈夫曼樹，該樹的帶權路徑長度為（）。A,66 B. 80 C. 62 D. 87（2）權重值為4的葉結點的哈夫曼編碼為（）。A.0001 B. 1110 C.001 D. 11034.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，該二叉樹的根結點是（）。A. e B. c C. b D. a（2）先序遍歷序列是（）。A. e,b,c,d,a B. c,a,b,d,

35、e C. a,b,d,e,c D. a.c,b,d,e,35.（1）已知某二叉樹的先序遍歷序列是aecdb，中序遍歷序列是eadcb，該二叉樹的根結點是（）; A. e B. c C. b D. a（2）后序遍歷序列為（）。A. e,d,b,c,a B. c,a,b,d,e C. a,b,d,e,c D. a.c,b,d,e,36.（1）以給定權重值5，6，17，18，25，30，為葉結點，建立一棵哈夫曼樹,該樹的中序遍歷序列為（）。A. 5，11，28，6，17，58，30，101，18，43，25B. 5，11，6，28，17，58，30，101，18，43，25 C. 5，11，6，28

36、，101，58，30，17，18，43，25 D. 5，11，6，28，17，58，30，101，18，25，43 （2）權重值為6的葉結點的哈夫曼為回答. A. 1001 B. 011 C.001 D.0001形考作業4一、單項選擇題（每小題2分，共40分）1.對線性表進行二分查找時，要求線性表必須（ ）。A. 以鏈接存儲方式B. 以順序存儲方式C. 以順序存儲方式，且數據元素有序D. 以鏈接存儲方式，且數據元素有序2.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。A. nB. (n-1)/2C. n/2D. (n+1)/23.有一個長度為10的有序表，按折半查找對

37、該表進行查找，在等概率情況下查找成功的平均比較次數為（ ）。A. 29/10B. 31/10C. 29/9D. 26/104.已知一個有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（ ）次。A. 5B. 6C. 4D. 35.有數據53,30,37,12,45,24,96，從空二叉樹開始逐個插入數據來形成二叉排序樹，若希望高度最小，應該選擇的序列是（ ）。A. 37,24,12,30,53,45,96B. 12,24,30,37,45,53,96C. 45,24,53,12,37,96,30D. 30,24,12,37,45,96,536.對于順序存儲

38、的有序表5,12,20,26,37,42,46,50,64，若采用折半查找，則查找元素26的比較次數是（ ）。A. 4B. 3C. 5D. 67.在所有的排序方法中，關鍵字比較的次數與記錄初始排列秩序無關的是（ ）。A. 直接插入排序B. 冒泡排序C. 希爾排序D. 直接選擇排序8.從未排序序列中依次取出元素與已經排好序的序列中的元素作比較。將其放入已排序序列的正確的位置上，此方法稱為（ ）。A. 插入排序B. 選擇排序C. 交換排序D. 歸并排序9.依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（ ）。A. 選擇排序B. 歸并排序C. 插入排序D. 交換排序10.當兩個元素出現逆序的

39、時候就交換位置，這種排序方法稱為（ ）。A. 交換排序B. 歸并排序C. 選擇排序D. 插入排序11.每次把待排序的區間劃分為左、右兩個子區間，其中左區間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區間中記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為（ ）。A. 快速排序B. 歸并排序C. 插入排序D. 堆排序12.一組記錄的關鍵字序列為（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（ ）。A. 30,20,40，38，46，84，56，79,90,100B. 20,30,40，38，46，79，56，84,

40、90,100C. 40，20,30,38，46，56，79，84,90,110D. 20,30 38，40，46，56，79，84,90,10013.在有序表10,14，34，43，47，64，75，80，90中，用折半查找法查找值80時，經（ ）次比較后查找成功。A. 3B. 2C. 4D. 514.對序列（49，38，65，97，76，13，47，50）采用直接插入排序法進行排序，要把第七個元素47插入到已排序中，為尋找插入的合適位置需要進行（ ）次元素間的比較。A. 5B. 6C. 4D. 315.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為

41、（ ）排序。A. 選擇B. 插入C. 歸并D. 快速16.一組記錄的關鍵字序列為（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆為（ ）。A. 18，20，25，59，26，36B. 18，20，36，59，26，25C. 26，59，36，18，20，25D. 26，18，59，20，36，2517.一組記錄的關鍵字序列為（25，48，16，35，79，82，23，40，36，72），其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟歸并后的結果為（ ）。A. 16，25，48，35，79，82，23，36，40，72B. 16，25，35，48，79，

42、23，36，40，82，72C. 16，25，35，48，23，40，79，82，36，72D. 16，25，35，48，79，82，23，36，40，7218.已知10個數據元素為（54，28，16，34，73，62，95，60，26，43），對該數列從小到大排序，經過一趟冒泡排序后的序列為（ ）。A. 28，16，34，54，62，73，60，26，43，95B. 16，28，34，54，73，62，60，26，43，95C. 16，28，34，54，62，60，73，26，43，95D. 28，16，34，54，62，60，73，26，43，9519.一組記錄的關鍵字序列為（46，79，

43、56，38，40，84），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（ ）。A. 40，38，46，79，56，84B. 40，38，46，84，56，79C. 38，40，46，56，79，84D. 40，38，46，56，79，8420.一組記錄的關鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（ ）。A. 39，46，41，57，80，47B. 39，47，46，80，41，57C. 41，39，46，47，57，80D. 39，80，46，47，41，57二、程序填空題（每題10分，2題，共20分。請點擊正確選項

44、，然后拖拽至相應的方框上）21.以下函數是二叉排序樹的查找算法，若二叉樹為空，則返回根結點的指針，否則，返回值是指向樹結點的結構指針p（查找成功p指向查到的樹結點，不成功p指向為NULL）完成程序中的空格typedef struct Bnode int key;struct Bnode *left;struct Bnode *right; Bnode; Bnode *BSearch(Bnode *bt, int k) /* bt用于接收二叉排序樹的根結點的指針，k用以接收要查找的關鍵字*/ Bnode *p; if(bt= （NULL） ) return (bt); p=bt; while(p->key!=（k） ) if(k<p->key) （p=p>left） ; else （p=p>>right） ; if(p=NULL) break; return(（p） ; p=p>leftNULLp=p>>rightpk22.以下程序是折半插入排序的算法設待排序的記錄序列存放在a1,an中，以a0作為輔助工作單元，程序是要把ai 插入到已經有序的序列a1,ai-1中。 void binsort (NODE a