國開形成性考核02272《數(shù)據(jù)結構》形考任務(1-4)試題及答案

1、國開形成性考核數(shù)據(jù)結構形考任務（1-4）試題及答案（課程ID： 02272,整套相同，如遇順序不同，Ctrl F查 找，祝同學們?nèi)〉脙?yōu)異成績?。┬慰既蝿眨?）一、單項選擇題（每題3分，共60分）題目：1、把數(shù)據(jù)存儲到計算機中，并具體表達數(shù)據(jù)元素間的 邏輯結構稱為（B）。A：給相關變量分配存儲單元B：物理結構C：邏輯結構D：算法的具體實現(xiàn)題目：2、以下說法中，不正確的選項是（B） oA：數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位B：數(shù)據(jù)項可由假設干個數(shù)據(jù)元素構成C：數(shù)據(jù)可有假設干個數(shù)據(jù)元素構成D：數(shù)據(jù)元素是數(shù)據(jù)的基本單位題目：33、要在一個帶頭結點的單向循環(huán)鏈表中刪除頭結 點，得到一個新的不帶頭結點

2、的單向循環(huán)鏈表，假設結點的指針域 為next,頭指針為head,尾指針為p,那么可執(zhí)行head二head- next; p-next=head； 。 (V)題目：34、設有一個單向循環(huán)鏈表，頭指針為head,鏈表中 結點的指針域為next, p指向尾結點的直接前驅結點，假設要刪除 尾結點，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作P-next=head； 。 (V)三、程序填空題(每題6分，共12分。請點擊正確選項, 然后拖拽至相應的方框上)題目：35、設線性表以不帶頭結點的單向鏈表存儲，鏈表頭 指針為head,以下程序的功能是輸出鏈表中各結點中的數(shù)據(jù)域 data,完成程序中空格局部。define

3、NULL 0void main NODE *head , *p ;p=head;/*p為工作指針*/doprintf( dn ， p-data ;p=p- nextwhile p!=NULL ;題目：36、設有一個頭指針為head的不帶頭結點單向鏈表， P、q是指向鏈表中結點類型的指針變量，P指向鏈表中結點a, (設鏈表中沒有結點的數(shù)據(jù)域與結點a的數(shù)據(jù)域相同)，寫出相關 語句(1)使該單向鏈表成為單向循環(huán)鏈表(2)插入結點s,使它成為a結點的直接前驅q=p; x=p-data;while q- next!=NULL) q=q-next;q-next=head;q=p; p=p-next;whi

4、le(p-data!=x) q=P； p=p- nexts-next=p;q-next=s形考任務（2）一、單項選擇題（每題2分，共50分）題目：1、假設讓元素1, 2, 3依次進棧，那么出棧順序不可能為 （D） o TOC o 1-5 h z ：1,3,2：2,1,3：3,2,1：3,1,2題目：2、一個隊列的入隊序列是1, 2, 3, 4O那么隊列的輸出 序列是（B）。： 1, 4, 3, 2： 1, 2, 3, 4： 3, 2, 4, 1： 4, 3, 2, 1題目：3、向順序棧中壓入新元素時，應當(B) oA：先后次序無關緊要B：先移動棧頂指針，再存入元素C：先存入元素，再移動棧頂指針

5、D：同時進行題目：4、在一個棧頂指針為top的鏈棧中，將一個p指針所 指的結點入棧，應執(zhí)行(B)。： top-next=p;： p-next=top;top=p;： p-next=top-next;top-next=p;： p-next=top-next;top=top-next;題目：5、在一個棧頂指針為top的鏈棧中刪除一個結點時， 用x保存被刪結點的值，那么執(zhí)行(A) o： x=top-data;top=top-next;： top=top-next;x=top-data;： x=top-data;： x=top;top=top-next;題目：6、判斷一個順序隊列（最多元素為m）為空的

6、條件是 （A） o： front=rear： front二二rear 1： rear=m-l： rear=m題目：7、判斷一個循環(huán)隊列為滿的條件是（C）。： front二二rear 1： rear=MaxSize： （rear l）%MaxSize=front： rear%MaxSize= =front題目：8、判斷棧滿（元素個數(shù)最多n個）的條件是（A） o： top=n-l： top=-l： top=0： top!=0題目：9、設有一個20階的對稱矩陣A （第一個元素為 al, 1）,采用壓縮存儲的方式，將其下三角局部以行序為主序存 儲到一維數(shù)組B中（數(shù)組下標從1開始），那么矩陣元素a6,

7、2在 一維數(shù)組B中的下標是（A）。： 17： 28： 23： 21題目：10、在解決計算機主機與打印機之間速度不匹配問題 時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入 緩沖區(qū)中，而打印機那么從緩沖區(qū)中取出數(shù)據(jù)打印，該緩沖區(qū)應該 是一個（A）結構。A：隊列B：數(shù)組C：線性表D：堆棧題目：11、一個遞歸算法必須包括（B）。A：遞歸局部B：終止條件和遞歸局部C：迭代局部D：終止條件和迭代局部題目：12、在一個鏈隊中，假設f和r分別為隊頭和隊尾指 針，那么刪除一個結點的運算為（B）。： r=f-next;： f=f-next;： f=r-next;： r=r-next;題目：13、在一個鏈

8、隊中，假設f和r分別為隊頭和隊尾指 針，那么插入s所指結點的運算為（D）。： s-next=r;r=s;： s-next=f;f=s;： f-next=s;f=s;： r-next=s;r=s;題目：14、數(shù)組a經(jīng)初始化char a=English” ;a7中 存放的是(C)。A：變量hB ： hC：字符串的結束符D：字符h題目：15、設主串為ABcCDABcdEFaBc，以下模式串能與 主串成功匹配的是(B) o： BCd： Bed： Abe： ABC題目：16、字符串 al=AEIJING, a2二AEI, a3二AEFANG, a4二AEFI中最大的是(A)。： al： a2： a3：

9、a4題目：17、兩個字符串相等的條件是(A) oA：兩串的長度相等，并且對應位置上的字符相同B：兩串的長度相等，并且兩串包含的字符相同C：兩串的長度相等D：兩串包含的字符相同題目：18、一維數(shù)組A采用順序存儲結構，每個元素占用6 個字節(jié)，第6個元素的存儲地址為100,那么該數(shù)組的首地址是(C) O： 64： 28： 70： 90題目：19、一個非空廣義表的表頭(C)。A：只能是子表B：只能是原子C：可以是子表或原子D：不可能是原子題目：20、對稀疏矩陣進行壓縮存儲，可采用三元組表，一個 10行8列的稀疏矩陣A,其相應的三元組表共有6個元素，矩陣 A共有(A)個零元素。： 74： 72： 10：

10、 8題目：21、對稀疏矩陣進行壓縮存儲，可采用三元組表，一個 10行8列的稀疏矩陣A共有73個零元素，A的右下角元素為6, 其相應的三元組表中的第7個元素是(B)。： (10, 8, 7)： (10, 8, 6)： (7, 10, 8)： (7, 8, 10)題目：3、一個存儲結點存儲一個(D)。A：數(shù)據(jù)類型B：數(shù)據(jù)項C：數(shù)據(jù)結構D：數(shù)據(jù)元素題目：4、數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的 (B) oA：存儲結構B：邏輯結構C：物理和存儲結構D：物理結構題目：5、在線性表的順序結構中，以下說法正確的選項是(D) oA：進行數(shù)據(jù)元素的插入、刪除效率較高B：邏輯上相鄰的元素在物理位置上也相鄰

11、C：數(shù)據(jù)元素是不能隨機訪問的題目：22、對一個棧頂指針為top的鏈棧進行入棧操作，通 過指針變量P生成入棧結點，并給該結點賦值a,那么執(zhí)行： p=(struct node *)malloc(sizeof (struct node);p-data=a;和(C) o： p-next=top;p=top;： top-next=p;p=top;： p-next=top;top=p;： top=top-next;p=top;題目：23、頭指針為head的帶頭結點的單向鏈表為空的判定 條件是(B)為真。： head-next!=NULL： head-next-NULL： head二二NULL： head-

12、next!=NULL題目：24、設有一個對稱矩陣A,采用壓縮存儲的方式，將其 下三角局部以行序為主序存儲到一維數(shù)組B中(數(shù)組下標從1開 始)，B數(shù)組共有55個元素，那么該矩陣是(C)階的對稱矩陣。： 5： 15： 10： 20題目:25、數(shù)組a經(jīng)初始化char a二English ；al中 存放的是(B)。A :EB：字符n【C】：nD：字符E二、判斷題(每題2分，16題，共32分)題目：26、設有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指 向的結點要入棧，那么可執(zhí)行操作。hs=s； s- next=hs; (X)。題目：27、設有一個非空的鏈棧，棧頂指針為hs,要進行出 棧操作，用x保存出棧結

13、點的值，棧結點的指針域為next,那么可 執(zhí)行 hs=hs-next ; x=hs-data; (X)。題目：28、有一個鏈棧，棧頂指針為h,現(xiàn)有一個p所指向的 結點要入棧，那么可執(zhí)行操作p-next二h;和h=p； (V) 0題目：29、設有一個非空的鏈棧，棧頂指針為hs,要進行出 棧操作，用x保存出棧結點的值，棧結點的指針域為next,數(shù)據(jù) 域為 data,那么可執(zhí)行 hs= hs-next; x= hs-data; (X)。題目：30、在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊 結點的指針域為next,那么插入所指結點的操作為r-next=s； r=s； (V) o題目：31、在一個鏈

14、隊中，f和r分別為隊頭和隊尾指針，隊 結點的指針域為next, s指向一個要入 隊的結點，那么入隊操作為 r=s； r-next=s； (X)。題目：32、在一個不帶頭結點的非空鏈隊中，f和r分別為隊 頭和隊尾指針，隊結點的數(shù)據(jù)域為data,指針域為next,假設要進 行出隊操作，并用變量x存放出隊元素的數(shù)據(jù)值，那么相關操作為 x=f-data; f=f-next; (V)。題目：33、對稀疏矩陣進行壓縮存儲，可采用三元組表，一個 6行7列的稀疏矩陣A相應的三元組表共有8個元素,那么矩陣A共 有34個零元素。(V)。題目：34、循環(huán)隊列的最大存儲空間為MaxSize,隊頭指針為 f,隊尾指針為

15、r,當(r 1) %MaxSize=f時說明隊列已滿。(X) O題目：35、循環(huán)隊列的隊頭指針為f,隊尾指針為r,當產(chǎn) 二f時說明隊列已滿。(X)。題目：36、空串的長度是0；空格串的長度是空格字符的個 數(shù)。（V）。題目：37、對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素 對應的三元組包括該元素的行下標、列下標、和非零元素值三項 信息。（V） O題目：38、循環(huán)隊列的引入，目的是為了克服假上溢。（V） O題目：39、設有n階對稱矩陣A,用一維數(shù)組s壓縮存儲A的下三角元 素，s的下標從零開始，元素s26相應于A中的元素為a 7,50 （X） o題目：40、循環(huán)隊列的最大存儲空間為MaxSize=6

16、,采用少用 一個元素空間以有效的判斷?？栈驐M，假設隊頭指針front=4,當 隊尾指針rear二3時隊滿。（V）。題目：41、循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用 一個元素空間以有效的判斷棧空或棧滿，假設隊頭指針front=4,隊 尾指針rear=3時，隊列中共有5個元素。（V）。三、程序選擇填空題（每題9分，共18分。請點擊正確選 項，然后拖拽至相應的方框上）題目：42、以下函數(shù)為鏈棧的進棧操作，x是要進棧的結點的 數(shù)據(jù)域，top為棧頂指針struct node ElemType data;struct node *next;struct node *top ;void P

17、ush(ElemType x)|struct node *p;p= (struct node*)mallocA ： sizeof (struct node);p-data=x;p- next=top ;top=p ;題目：43、以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結點 的數(shù)據(jù)域的值，front、rear分別鏈隊列的隊頭、隊尾指針struct node ElemType data;structnode*next;);structnode*front, *rear;void InQueue (ElemType x) struct node *p;p= (struct node*) malloc

18、 (sizeof (struct node)p-data=x;p-next=NULL;rear-next=p ;rear=p ;形考任務（3）一、單項選擇題（每題2分，共38分）題目：1、假定一棵二叉樹中，雙分支結點數(shù)為15,單分支結 點數(shù)為30,那么葉子結點數(shù)為（B）。： 47： 16： 17： 15題目：2、二叉樹第k層上最多有（B）個結點。： 2k： 2kH： 2k-1： 2k-l題目：3、將含有150個結點的完全二叉樹從根這一層開始， 每一層從左到右依次對結點進行編號，根結點的編號為1,那么編號 為69的結點的雙親結點的編號為（D）。LA ： 33： 36： 35： 34題目：4、如果

19、將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的 二叉樹的帶權路徑長度最小，那么該樹稱為（A）?！続】：哈夫曼樹B：平衡二叉樹C：二叉樹D：完全二叉樹題目：5、在一棵度具有5層的滿二叉樹中結點總數(shù)為（A） o： 31： 16： 33： 32題目：6、一棵完全二叉樹共有6層，且第6層上有6個結 點，該樹共有（C）個結點。： 31： 38： 37： 72題目：7、利用3、6、8、12這四個值作為葉子結點的權，生 成一棵哈夫曼樹，該樹中所有葉子結點中的最長帶權路徑長度為(B) o： 30： 18： 12： 16題目：8、在一棵樹中，(A)沒有前驅結點。A：樹根結點B：空結點C:葉結點 D：分支結點題目：9、

20、設一棵采用鏈式存儲的二叉樹，除葉結點外每個結 點度數(shù)都為2,該樹結點中共有20個指針域為空，那么該樹有（C） 個葉結點。： 21： 9： 10： 22題目：10、在一個圖G中，所有頂點的度數(shù)之和等于所有邊 數(shù)之和的（A）倍。： 2： 1/2： 4： 1題目：11、鄰接表是圖的一種（D） oA：順序存儲結構LB：索引存儲結構D：邏輯上相鄰的元素在物理位置上不一定相鄰題目：6、對鏈表，以下表達中正確的選項是(D) oA：可以通過下標對鏈表進行直接訪問B：插入刪除元素的操作一定要要移動結點C：結點占用的存儲空間是連續(xù)的D：不能隨機訪問任一結點題目：7、以下的表達中，不屬于算法特性的是(B) oA：可

21、行性B：可讀性C：有窮性D：輸入性題目：8、算法的時間復雜度與(B)有關。A：所使用的計算機B：算法本身 C：數(shù)據(jù)結構C：散列存儲結構D：鏈式存儲結構題目：12、圖的深度優(yōu)先遍歷算法類似于二叉樹的（C）遍 歷。A：后序B：層次C：先序D：中序題目：13、以下圖所示的一個圖，假設從頂點VI出發(fā)，按深 度優(yōu)先搜索法進行遍歷，那么可能得到的一種頂點序列為（B）。： V1V2V4V5V8V3V6V7： V1V2V4V8V5V3V6V7： V1V2V4V8V3V5V6V7： V1V3V6V7V2V4V5V8題目：14、如以下圖所示的一個圖，假設從頂點a出發(fā)，按 廣度優(yōu)先搜索法進行遍歷，那么可能得到的一種

22、頂點序列為（B）。： abecdf： aecbdf： aedfcb： aebcfd題目：15、圖狀結構中數(shù)據(jù)元素的位置之間存在（D）的關 系。A：每一個元素都有一個且只有一個直接前驅和一個直接 后繼B： 一對一C： 一對多D：多對多題目：16、在一棵二叉樹中，假設編號為i的結點存在右孩 子，那么右孩子的順序編號為（A）。： 2i 1： 2i-lLC ： 2iD ： 2i 2題目：17、一棵具有16個結點的完全二叉樹，共有（B） 層。（設根結點在第一層）： 4： 5： 6： 7題目：18、對二叉排序樹進行（C）遍歷，可以使遍歷所得到 的序列是有序序列。A：按層次B：后序C：中序D：前序題目：19

23、、一個圖的邊數(shù)為m,那么該圖的所有頂點的度數(shù) 之和為（D） o： m： 2m 1： m/2： 2m二、判斷題（每題1分，共10分）題目：20、一棵二叉樹的葉結點（終端結點）數(shù)為5,單分支 結點數(shù)為2,該樹共有11個結點。（V）題目：21、一棵有14個結點的完全二叉樹，那么它的最高層上 有7個結點。（V）題目：22、一棵二叉樹有6個葉結點，那么該樹總共有11個結 點。（X）題目：23、根據(jù)搜索方法的不同，圖的遍歷有.先序；中 序；后序三種方法。（X）題目：24、對于一棵具有n個結點的二叉樹，其相應的鏈式 存儲結構中共有n-1個指針域空。（X）題目：25、設一棵完全二叉樹，其最高層上最右邊的葉結點

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

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

26、點)。void Inorder (struct BTreeNode *BT)(if (BT!=NULL)Inorder(BT-left);printf( %c ，BT-data);Inorder (BT- right);)利用上述程序對右圖進行中序遍歷，結果是d, b, e, a, f, c四、綜合應用題(每題8分，5題，共40分)題目：32、（1）以3, 4, 5, 8, 9,作為葉結點的權，構造 一棵哈夫曼樹。該樹的帶權路徑長度為（B）。A, 64： 65： 62： 66（2）權重為3的葉結點的哈夫曼編碼為（C）。： 010： 0101： 000： 0111題目：33、（1）以2, 3,

27、4, 7, 8, 9作為葉結點的權，構 造一棵哈夫曼樹，該樹的帶權路徑長度為（B）。： 66： 80： 62： 87 (2)權重值為4的葉結點的哈夫曼編碼為(C)。： 0001： 1110： 001： 110題目：34、(1)某二叉樹的后序遍歷序列是debca,中 序遍歷序列是dbeac,該二叉樹的根結點是(D)。： e： c： b： a(2)先序遍歷序列是(C)。： e, b, c, d, a： c, a, b, d, e： a, b, d, e, cD：A ： c, b, d, e,題目：35、(1)某二叉樹的先序遍歷序列是aecdb,中 序遍歷序列是eadcb,該二叉樹的根結點是(D)。

28、： e： c： b： a(2)后序遍歷序列為(A)。： e, d, b, c, a： c, a, b, , d, e： a, b, d, e, c： a, c, b, d, e,題目：36、(1)以給定權重值5, 6, 17, 18, 25, 30,為葉 結點，建立一棵哈夫曼樹，該樹的中序遍歷序列為(B)。A：5, 11, 28, 6, 17, 58, 30, 101,18, 43, 25B：5, 11, 6, 28, 17, 58, 30, 101, 18, 43, 25C：5,11, 6, 28, 101, 58, 30, 17, 18, 43, 25D：5,IL 6, 28, 17, 5

29、8, 30, 10L 18, 25, 43（2）權重值為6的葉結點的哈夫曼為（D）。A：5, 11, 28, 6, 17, 58, 30, 101,18, 43, 25B：5, 11, 6, 28, 17, 58, 30, 101, 18, 43, 25C：5,11, 6, 28, 101, 58, 30, 17, 18, 43, 25D：5,IL 6, 28, 17, 58, 30, 10L 18, 25, 43： 1001： 011： 001： 0001形考任務（4）一、單項選擇題（每題2分，共40分） 題目：1、對線性表進行二分查找時，要求線性表必須（D） oA：以順序存儲方式B：以鏈接

30、存儲方式C：以鏈接存儲方式，口數(shù)據(jù)元素有序D：計算機的操作系統(tǒng)題目：9、設有一個長度為n的順序表，要在第i個元素之前 （也就是插入元素作為新表的第i個元素），插入一個元素，那么 移動元素個數(shù)為（C）。： i： n-i： n-i 1： n-i-1題目：10、設有一個長度為n的順序表，要刪除第i個元素 移動元素的個數(shù)為（D）。： n-i-l： i： n-i 1： n-i題目：11、在一個單鏈表中，p、q分別指向表中兩個相鄰的 結點，且q所指結點是P所指結點的直接后繼，現(xiàn)要刪除q所指 結點，可用語句（D）。A ： q-next=NULLD：以順序存儲方式，且數(shù)據(jù)元素有序題目：2、采用順序查找方法查找

31、長度為n的線性表時，每個 元素的平均查找長度為(B)。： n： (n 1)/2： n/2： (n-l)/2題目：3、有一個長度為10的有序表，按折半查找對該表進 行查找，在等概率情況下查找成功的平均比擬次數(shù)為(B)。： 29/9： 29/10： 26/10： 31/10題目：4、一個有序表為(11, 22, 33, 44, 55, 66, 77, 88, 99),那么順序查找元素55需要比擬 (A)次。： 5： 4： 3： 6題目：5、有數(shù)據(jù)53, 30, 37, 12,45,24,96,從空二叉樹開始 逐個插入數(shù)據(jù)來形成二叉排序樹，假設希望高度最小，應該選擇的 序列是（B）。： 45, 24

32、, 53, 12, 37, 96, 30： 37, 24, 12, 30, 53, 45,96： 30, 24, 12, 37, 45, 96, 53： 12, 24, 30, 37, 45, 53, 96題目：6、對于順序存儲的有序表（5, 12, 20, 26, 37, 42, 46, 50, 64）,假設采用折半查找，那么查找元素26 的比擬次數(shù)是（B）。： 3： 4： 5： 6題目：7、在所有的排序方法中，關鍵字比擬的次數(shù)與記錄初 始排列秩序無關的是（B）。A：冒泡排序B：直接選擇排序C：直接插入排序D：希爾排序題目：8、從未排序序列中依次取出元素與已經(jīng)排好序的序列 中的元素作比擬。將

33、其放入已排序序列的正確的位置上，此方法 稱為（B）。A：選擇排序B：插入排序C：歸并排序D：交換排序題目：9、依次將每兩個相鄰的有序表合并成一個有序表的排 序方法稱為（B）。A：選擇排序 B：歸并排序C：插入排序D：交換排序題目：10、當兩個元素出現(xiàn)逆序的時候就交換位置，這種排 序方法稱為(C)。A：選擇排序B：插入排序C：交換排序【D】：歸并排序題目：11、每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間， 其中左區(qū)間中記錄的關鍵字均小于等于基準記錄的關鍵字，右區(qū) 間中記錄的關鍵字均大于等于基準記錄的關鍵字，這種排序稱為(B) oA：插入排序【B】：快速排序【口 ：歸并排序D：堆排序題目：12、一組

34、記錄的關鍵字序列為（46,20,30,79, 56,38, 40, 84,90,110）,利用快速排序，以第一個關鍵字為分割元 素，經(jīng)過一次劃分后結果為（B）。A20,30,40, 38, 46,79, 56, 84,90, 100A20,30,40, 38, 46,79, 56, 84,90, 100B ： 40, 20,30,38, 46, 56, 79, 84,90, 110CCC20,30 38, 40, 46,56, 79, 84,90,100C20,30 38, 40, 46,56, 79, 84,90,100D ： 30,20,40, 38, 46, 84, 56, 79,90,

35、 100題目：13、在有序表10, 14, 34, 43, 47, 64, 75, 80, 90 中，用折半查找法查找值80時，經(jīng)（A）次比擬后查找成功。： 3： 2： 5： 4題目：14、對序列（49, 38, 65, 97, 76, 13, 47, 50）采 用直接插入排序法進行排序，要把第七個元素47插入到已排序 中，為尋找插入的合適位置需要進行（A）次元素間的比擬。： 5： 3： 4： 6題目：15、排序方法中，從未排序序列中挑選元素，并將其 依次放入已排序序列（初始為空）的一端的方法，稱為（D）排 序?！続】：快速B:歸并C：插入D：選擇題目：16、一組記錄的關鍵字序列為（26, 5

36、9, 36, 18, 20, 25）,利用堆排序的方法建立的初始小根堆為（B）。 TOC o 1-5 h z ：26,18,59,20,36,25：18,20,25,59,26,36：26,59,36,18,20,25 D ： 18, 20, 36, 59, 26, 25題目：17、一組記錄的關鍵字序列為(25, 48, 16, 35, 79, 82, 23, 40, 36, 72),其中，含有5個長度為2的有序 表，按歸并排序的方法對該序列進行一趟歸并后的結果為(D)。A：16,25,48,35,79,82,23,36,40,72B：16,25,35,48,79,82,23,36,40,72

37、C：16,25,35,48,79,23,36,40,82,72D：16,25,35,48,23,40,A：16,25,48,35,79,82,23,36,40,72B：16,25,35,48,79,82,23,36,40,72C：16,25,35,48,79,23,36,40,82,72D：16,25,35,48,23,40,79,82,36,72題目：18、10個數(shù)據(jù)元素為(54, 28, 16, 34, 73, 62, 95, 60, 26, 43),對該數(shù)列從小到大排序，經(jīng)過一趟冒泡 排序后的序列為(D)。A：16, 28, 34,54,73,62, 60, 26, 43, 95B：28

38、,16,34,54,62,60,73,26,43,95C：16,28,34,54,62,60,73,26,43,95D：28,16,34,54,62,73,A：16, 28, 34,54,73,62, 60, 26, 43, 95B：28,16,34,54,62,60,73,26,43,95C：16,28,34,54,62,60,73,26,43,95D：28,16,34,54,62,73,60,26,43,95題目：19、一組記錄的關鍵字序列為(46, 79, 56, 38, 40, 84),利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一 次劃分后結果為(B)。： 40, 38, 46, 7

39、9, 56, 84B ： 40, 38, 46, 56, 79, 84C：C：C：40,38,46,84,56,79D：38,40,46,56,79,84C：40,38,46,84,56,79D：38,40,46,56,79,84題目：20、一組記錄的關鍵字序列為(80, 57,41,39, 46, 47)，(80, 57,41,39, 46, 47)，(80, 57,41,39, 46, 47)，利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為(B)A：41,39,46,47,57,80B：39,46,41,57,80,47C：39,80,46,47,41,57D：39,47,(80,

40、57,41,39, 46, 47)，利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為(B)A：41,39,46,47,57,80B：39,46,41,57,80,47C：39,80,46,47,41,57D：39,47,46,80,41,57二、程序填空題（每題10分，2題，共20分。請點擊正確選 項，然后拖拽至相應的方框上）題目：21、以下函數(shù)是二叉排序樹的查找算法，假設二叉樹為 空，那么返回根結點的指針，否那么，返回值是指向樹結點的結構指 針P （查找成功P指向查到的樹結點，不成功P指向為NULL）完 成程序中的空格typedef struct Bnodeintkey;struct B

41、node *left;intkey;struct Bnode bright; Bnode;Bnode *BSearch(Bnode *bt, int k)/* bt用于接收二叉排序樹的根結點的指針，k用以接收要查 找的關鍵字*/ Bnode *p;if (bt=二NULL )return (bt);P=bt;while(p-key!=k ) if (kkey)p=p-left ;elsep=p-right ;if (p=NULL) break;return(p ;題目：22、以下程序是折半插入排序的算法設待排序的記錄序列存放在an中，以a0作為輔 助工作單元，程序是要把ai插入到已經(jīng)有序的序列

42、 al,中。void binsort (NODE a , int n) int x, i, j, s, k, m;for (i=2； i=n ;i )a0=ai;x= ai. key;s=l;while (s=j) m=(s j)/2 if ( xnext=q： p=q-next： p-next=q-next題目：12、在一個單鏈表中p所指結點之后插入一個s所指 的結點時，可執(zhí)行(D) o： p-next=s-next;： p-next= s; s-next= p-next： p=s-next： s-next=p-next; p-next=s;題目：13、非空的單向循環(huán)鏈表的尾結點滿足(D)(

43、設頭指 針為head,指針p指向尾結點)。： p-next=NULL： p=二NULL： p= head： p-next=head題目：14、鏈表不具有的特點是（C）。j=m- 1elses=m 1)for ( k=i-l;k=j 1;k-)ak 1 =ak;aj l=a0;)三、綜合題(每題8分，共40分)題目：23、(1)設查找表為(1,10,11,14,23,27,29,55,68),畫出對上述查找表進行折半查 找所對應的判定樹，為了成功查找到元素14,需要依次與元素(C)進行比擬。A ： 23, 10, 1, 14 B ： 23, 29, 27, 14： 23, 10, 11, 14：

44、 23, 29,55, 14(2)在等概率條件下，成功查找的平均比擬次數(shù)為(B)。： 24/9： 25 /9： 3： 2. 5題目：24、(1) 一組記錄的關鍵字序列為(47, 80, 57, 39, 41, 46),利用堆排序的方法建立的初始堆為(B)(堆頂元 素是最小元素，采用樹的形式建堆)。： 39, 41, 57, 80, 47, 46： 39,41,46, 80, 47, 57： 39, 47, 46, 80,41,57： 39,41,57, 80, 46, 47(2)輸出堆頂元素后,調整后的堆為(A)。A ： 41,47, 46, 80,57： 41,57, 46, 80,47：

45、41,57, 80, 47, 46： 41, 80, 46, 47, 57題目：25、(1)對關鍵字序列(56, 51, 71, 54, 46, 106),利用 快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結果為O： 46, 51, 56, 54, 71, 106： 56,51,54, 46,71, 106： 46, 51, 54, 56, 71, 106： 56,51,46, 54,71, 106(2) 一組記錄的關鍵字序列為(60,47, 80, 57, 39, 41, 46,30),利用歸并排序的方法，經(jīng)過2)歸并的結果序列為o TOC o 1-5 h z ： (30, 57, 6

46、0, 80,47,39,41,46)：(47, 60, 57, 80, 30,39,41,46)： (41, 57, 60, 80, 30,39,47,46)D ：(47, 57, 60, 80, 30,39,41,46)題目：26、(1)對關鍵字序列(36, 69, 46, 28, 30, 74)采用快 速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后的結果序 列為(D) o： 30, 28, 46, 36, 69, 74： 28, 30, 36, 46, 69, 74： 28, 30, 46, 36, 69, 74： 30, 28, 36, 46, 69, 74(2)用冒泡法對上述序列排序,經(jīng)兩趟冒泡的結果序列為 (A) o TOC o 1-5 h z ：36,28,30,46,69,74：36,46,28,20,69,74：38,36,30,46,69,74：