【正文】 少。 B、 9， 7， 8， 4，1， 7， 15， 20 C、 20， 15， 8， 9， 7， 1， 4， 7 D、 9， 4， 7， 8， 7， 1， 15， 20 21． 一組記錄的關(guān)鍵碼為（ 46， 79， 56， 38， 40， 84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為。 A. 冒泡 B、 希爾插入 C、 交換 D、 快速 25． 設(shè)棧 S 和隊(duì)列 Q 的初始狀態(tài)為空，元素 e1， e2， e3， e4,e5 和 e6 依次通過棧 S，一個(gè)元素出棧后即進(jìn)隊(duì)列 Q，若 6 個(gè)元素出隊(duì)的序列是 e2， e4， e3,e6,e5,e1 則棧 S 的容量至少應(yīng)該是 A． 6 B、 4 C、 3 D、 2 26． 棧和隊(duì)都是 A、順序存儲的線性結(jié)構(gòu) B、 鏈?zhǔn)酱鎯Φ姆蔷€性結(jié)構(gòu) C、 限制存取 點(diǎn)的線性結(jié)構(gòu) D、 限制存取點(diǎn)的非線性結(jié)構(gòu) 27． 棧和隊(duì)列的共同點(diǎn)是 A、 都是先進(jìn)先出 B、 都是先進(jìn)后出 C、 只允許在端點(diǎn)處插入和刪除元素 D、 沒有共同點(diǎn) 28． 假定一個(gè)順序循環(huán)隊(duì)列存儲于數(shù)組 A[n]中，其隊(duì)首和隊(duì)尾指針分別用 front 和 rear 表示，則判斷隊(duì)滿的條件是 A、 (rcar1)％ n==front B、 (rear+1)％ n=front C、 rear ==(front1)％ n D、 rear ==(front+1)％ n 29． 棧在（ ）中應(yīng)用。表左的 s 指向起始表元。p ne x t q q pri or p p ne x t pri or q q ne x t q? ? ? ? ? ? ? ? ? B 、。p nex t q q nex t pr i or q q pr i or p q nex t p nex t? ? ? ? ? ? ? ? ? ? C 、。q ne x t p q ne x t p ne x t p ne x t pri or q p ne x t q? ? ? ? ? ? ? ? ? ? D 、。q ne x t p ne x t q pri or p p ne x t q p ne x t q? ? ? ? ? ? ? ? ? 38． 若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ ）存儲方式最節(jié)省時(shí)間。 A、 N l B、 N C、 N+1 D、 N+2 42． 數(shù) 組 SZ[3…50 ， O… 10 ]含有元素?cái)?shù)目為 A、 88 B、 99 C、 80 D、 90 43． 已知串 S=‘a(chǎn)aab’， 其 next 數(shù)組值為 A、 0123 B、 1123 C、 1231 D、 1211 44． 已知 Head(Tail([Head(S), Head(Tail(Tail(S)))]=[a],廣義表 S 滿足上式，則 S 為 _______.(其中，方括號表示廣義表，圓括號表示函數(shù)。 A、 可以順序存儲 B、數(shù)據(jù)元素是一個(gè)字符 C、可以鏈接存儲 D、 數(shù)據(jù)元素可以是多個(gè)字符 47． 下列說法正確的是。（ i≤ h） A、 2i1 B、 2i1 C、 2h1 D、 2h1 表元編號 貨號 數(shù)量 表元間聯(lián)系 1 618 40 5 2 205 2 1 3 103 15 4 4 501 20 0 5 781 17 6 6 910 24 3 表元編號 貨號 數(shù)量 表元間聯(lián)系 1 2 1 618 40 5 2 2 205 2 1 0 3 103 15 4 6 4 501 20 0 3 5 781 17 6 1 6 910 24 3 5 石家莊學(xué)院 20222022 學(xué)年第 二 學(xué)期《 數(shù)據(jù)結(jié)構(gòu) 》 期末考試 試卷 試卷 第 5 頁 （共 7 頁） 考核人數(shù)______ 考核班次_______________ 任課教員_________ 出題教員簽名________ 任課教研室主任簽名_______日期_______ 隊(duì)別__________ 教學(xué)班次___________ 學(xué)號___________ 姓名____________ ??????????密????????????封????????????線??????????????? 51． 順序棧是空棧的條件是。 A、 (1)(2) B、 (1) C、 (2) D、(1)、 (2)都錯 56． 利用二叉鏈表存儲樹，則根結(jié)點(diǎn)的右指針是 A、指向最左孩子 B、指向最右孩子 C、空 D、非空 57． 下面關(guān)于 B 和 B+樹的敘述中，不正確的是 A、 B 樹和 B+樹都是平衡的多叉樹。 58． 既希望較快的查找又便于線性表動態(tài)變化的查找方法是 A、順序查找 B、 折半查找 C、 索引順序查找 D、 哈希法查找 59． 設(shè)單鏈表中結(jié)點(diǎn)結(jié)構(gòu)為 (data,link).已知指針 q 所指結(jié)點(diǎn)是指針 p 所指結(jié)點(diǎn)的直接前驅(qū)，若在 *q 與 *p 之間插入結(jié)點(diǎn) *s，則應(yīng)執(zhí)行下列哪一個(gè)操作 A、 slink=plink。 slink=p。 2． 試給出二叉樹的自下而上、自右而左的層次遍歷算法。 2． 克魯斯卡爾算法的時(shí)間復(fù)雜度為 _____，它 對 ______圖較為適臺。 {假設(shè) r[k+1..m]中各元素滿足堆的性質(zhì)，本算法調(diào)整 r[k]使整個(gè)序列 r[k..m]中各元素滿足堆的性質(zhì)。 finished:=false。 i:=j。{sift} 5． 直接插入排序用監(jiān)視哨的作用是 _______。 9． 一個(gè)無頭結(jié)點(diǎn)的線性鏈表 (不循環(huán) )有兩個(gè)域。 {在鏈?zhǔn)诪?head 的表中按遞增序插入 x} new(r)。 head:=r] ELSE [p:=head。 r＾ .next:= (8)____。 PROC creat(head)。 read(num) ] ENDP。 15． 在雙向鏈表結(jié)構(gòu)中，若要求在 p 指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為 s 所指的結(jié)點(diǎn)，則需執(zhí)行下列語句： s^ .next:=p； s^ .prior:= ________； p^ .prior:=s； ________:=s； 16