【正文】 A. 必須一致 B. 可以不一致 C. 不能一致 D. 不必不一致 (8) 順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用 ___________。 A. 不變的 C. 任意的 D. 0 (6) 4個(gè)元素進(jìn) S棧的順序是 A、 B、 C、 D，進(jìn)行兩次 Pop(S,x)操作后，棧頂元素的值是 __________。 A. A B. B C. C D. D (4) 棧的特點(diǎn)是 __________。 A. 端點(diǎn) B. 棧底 C. 棧頂 D. 中間 (2) 在棧頂一端可進(jìn)行的全部操作是 ___________。 (30) 鏈隊(duì) lq是空隊(duì)時(shí)， lqfrontnext為 _______________。 (28) 在鏈隊(duì)列 lq中，鏈隊(duì)的尾元素是鏈表的 _____________元素。 (26) 鏈隊(duì) lq是空隊(duì)的條件是 _____________。 (24) 鏈隊(duì) lq中，指向隊(duì)頭元素的指針是 ______。 (22) 循環(huán)隊(duì)列 sq存儲(chǔ)在數(shù)組 [0..max]中， max，則存放隊(duì)列尾元素的數(shù)組元素是 ____________。 (20) 循環(huán)隊(duì)列 sq空的條件是 ____________。 習(xí) 題 __ 填空題 (18) 已知循環(huán)隊(duì)列 sq，在進(jìn)行出隊(duì)操作之前要先判斷 __________。 (16) 隊(duì)列出隊(duì)的一端是 ____________。Push(s,b)后， GetTop(S)的值是 ____。 (13) 棧 s經(jīng)過(guò)運(yùn)算 InitStack(s)。 (11) 鏈棧 ls的棧頂元素是鏈表的 ______元素。 (9) 對(duì)鏈棧 ls，指向棧頂元素的指針是 ______。 (7) 順序棧 s存儲(chǔ)在數(shù)組 Ssdata[0..max]中， s棧滿時(shí)， Sstop==______。 (5) 順序棧 s存儲(chǔ)在數(shù)組 Ssdata[0..max]中，ｓ進(jìn)行出棧操作后，要執(zhí)行的語(yǔ)句是Sstop____。 (3) 順序棧 s存儲(chǔ)在數(shù)組 Ssdata[0..max]中， s棧滿的條件是 ____________。 } 習(xí) 題 ? 1 填空題 ? 2 選擇題 ? 3 簡(jiǎn)答題 ? 4 算法題 習(xí) 題 __填空題 ? 1. 填空題 (1) 已知順序棧 s，在對(duì) s進(jìn)行進(jìn)棧操作之前要先判斷 _______。 i++。 i=0。 } 實(shí)習(xí) 4 ? 求鏈隊(duì) Lq中包括棧元素個(gè)數(shù)的算法 。 i++。 i=0。 } 實(shí)習(xí) 3 ? 求鏈棧 Ls中包括棧元素個(gè)數(shù)的算法 。 ch=getchar( )。) { if(EmptyStack(s))error(不配對(duì))。 if(ch== 39。[39。39。 ch=getchar( )。 } } 實(shí)習(xí) 2 ? 編寫判斷 “ [‖與 “ ]‖是否配對(duì)的函數(shù) 。 } while(!EmptyStack (s)) { pop(s,x)。 while(n) { push(s,n%8)。 (算法 ) conversion( ) { InitStack(s)。 ? 初始化運(yùn)算 ? 進(jìn)隊(duì)列運(yùn)算 ? 出隊(duì)列運(yùn)算 ,將隊(duì)列頭元素刪除 ， 并返回其值 。 /*返回 x中 存放的原隊(duì)列頭元素的值 */ } } 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) ?2. 順序存儲(chǔ)結(jié)構(gòu) 用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的隊(duì)列稱為順序隊(duì)列 。 /*刪去隊(duì)列的頭元素 */ free(p)。 /*使 P指 向隊(duì)列的頭元素 */ x=pdata。 /*將尾指針指向新的尾元素 */ } 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) ? 1. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 出隊(duì)算法 (算法 ) datatype OutQueue(stuct linkqueue Q) { if(front==rear) error(Empty Queue)。 /*將尾結(jié)點(diǎn)的指針域置空指針 */ next=p。 /*為新元素準(zhǔn)備結(jié)點(diǎn)的空間 */ pdata=x。 提示： 使用上述鏈表存儲(chǔ)隊(duì)列時(shí) ， 必須注意正確使用 front和 rear兩個(gè)指針 ， 才能方便地實(shí)現(xiàn)隊(duì)列的各種運(yùn)算 。 一個(gè)指向頭結(jié)點(diǎn) ， 稱為 front，另一個(gè)指向尾結(jié)點(diǎn) ， 稱為 rear。 一般用單鏈表表示一個(gè)鏈隊(duì)列 。 隊(duì)列的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) ?隊(duì)列和棧一樣 ， 也可采用 順序存儲(chǔ) 和 鏈?zhǔn)酱鎯?chǔ) 兩種存儲(chǔ)結(jié)構(gòu) 。 ? 讀隊(duì)頭 GetHead(Q)： 其作用是當(dāng)隊(duì)列非空時(shí)，返回隊(duì)列頭元素的值，但不刪除隊(duì)列頭元素。 隊(duì)列的基本運(yùn)算 ? 隊(duì)列的基本運(yùn)算有以下幾種： ? 初始化 InitQueue(Q)： 其作用是建立一個(gè)空隊(duì)列 Q，準(zhǔn)備存放數(shù)據(jù)。 ? 先進(jìn)入隊(duì)列中的元素稱為隊(duì)列的 頭元素 (隊(duì)列的頭 )，最后進(jìn)入隊(duì)列中的元素稱為隊(duì)列的 尾元素 (隊(duì)列的尾 )。 能進(jìn)行插入的一端稱為隊(duì)列的尾 ， 能進(jìn)行刪除的一端稱為隊(duì)列的頭 。 /*釋放被刪除的結(jié)點(diǎn) */ return(x)。 /*將棧頂結(jié)點(diǎn)的數(shù)據(jù)域的值賦給 x*/ snext=pnext。 /*空棧 ， 返回空 */ else { p=snext。 /*將新結(jié)點(diǎn)插入鏈表 ， 作為首元素 */ snext=p。 /*申請(qǐng)一個(gè)新結(jié)點(diǎn) */ pdata=x。 }node,*pointer。 其中結(jié)點(diǎn)結(jié)構(gòu)定義為： typedef struct node { elemtype data。 因?yàn)闂５闹饕\(yùn)算都在棧頂進(jìn)行 ， 為訪問(wèn)單鏈表的表頭方便 ， 指定單鏈表的表頭作為棧頂 。 其各結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)完全相同 。 /*棧頂位置減 1*/ return(array[+1])。 /*將元素 x放入新棧頂 */ } } 棧的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) ? 刪除算法 (算法 ) datatypes pop(struct stack s) /* s退棧 ， 即刪去棧頂元素 */ { if(==1) error(Emptystack)。 } 棧的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn) ? 插入算法 (算法 ) void push(struct Stack s,datatype x) /*將數(shù)據(jù)元素 x進(jìn)棧 */ { if( == maxlen1) error(棧滿 ) /*棧已滿 ， 不能再插入新元素 */ else { =+1。 ?1. 順序存儲(chǔ)結(jié)構(gòu) 用一個(gè)向量 (一維數(shù)組 )作為棧的順序存儲(chǔ)結(jié)構(gòu) ， C語(yǔ)言表示形式如下： struct stack { datatypes array[maxlen]。 判?？?Empty Stack(S)： 若 S為空棧則該函數(shù)值為 1， 否則為 0。 出棧 Pop(S)： 其作用是當(dāng)棧不空時(shí)返回棧頂元素為該函數(shù)的值 ，然后刪去棧頂元素 。 棧的定義 ? 棧的基本運(yùn)算如下： 初始化 IniStack(S)： 其作用是建立一個(gè)空棧 ， 準(zhǔn)備存放數(shù)據(jù) 。 假設(shè)棧 S=(a1， a2， … ， an)， 則稱 a1為 棧底元素 ， an為 棧頂元素 。 棧的表尾端稱為 棧頂 (top)， 表頭端稱為 棧底 (bottom)。 ? 教學(xué)目標(biāo)： 通過(guò)本章的學(xué)習(xí) ， 使讀者能夠掌握棧和隊(duì)列的概念 、 有關(guān)術(shù)語(yǔ) 、 存儲(chǔ)方式 、 相關(guān)運(yùn)算和算法 ， 并能靈活應(yīng)用 。 J o s e p h u s (L,m ,n) Q amp。 ( 1 5) 任意給出正整數(shù) m 和 n ，將 m 個(gè)數(shù) 1 ， 2 ， 3 ，…， m ，順時(shí)針排列成環(huán)型，從 1 開(kāi)始順時(shí)針開(kāi)始計(jì)數(shù)，將數(shù)到的第 n 個(gè)數(shù)輸出，再繼續(xù)從1 數(shù)到 n ，并將第 n 個(gè)數(shù)輸出，依次將這 m 個(gè)數(shù)全部輸出。 De lete 1 6 (s ) ( 1 3) 已知單鏈表 L 是按值從小到大有序，將 X 插入到 L 鏈表中，并保持 L鏈表有序，寫出算法。 Mp a s s 1 4 (A ,B, C) ( 1 1) 已知 A 、 B 、 C 是三個(gè)按值從小到大有序的單鏈表，對(duì) A 表進(jìn)行如下操作：刪除那些即在 B 表又在 C 表中的元素。 Mp a s s 1 3 (A ,B, C) (1 0 ) 設(shè)單鏈表 A =(a1,a2,a3,… ,an) 和 B=( b1,b2,b3,… ,bm) 都是有序表 ( 按值從小到大排列 ) ，用類 C 語(yǔ)言編寫將 A 與 B 合并為鏈表 C 的算法， C 表也要求從小到大。 m o v e1 2 (L ) 習(xí) 題 __算法題 (9 ) 設(shè)單鏈表 A =(a1,a2,a3,… ,an) 和 B=( b1,b2,b3,… ,bm) ，用類 C 語(yǔ)言編寫將 A 與 B合并為單鏈表 C 的算法。 D el et e 10 (L ) (7 ) 用類 C 語(yǔ)言寫出將順序表逆置的算法，即利用原來(lái)的順序表將線性表 L = (a1,a2, a3,… ,an) 逆置為 L =( an,… ,a3,a2,a1) 。 L i n k (L 1 , L 2 ) ( 5 ) 寫出刪除單鏈表 L 中值大于 m ax 或小于 m i n 的元素的算法。 In s ert O r d erL i s t (amp。 試設(shè)計(jì)一個(gè)算法 void concat(node p, q)，將它們合并成一個(gè)以 p為頭指針的單鏈表 Z，使其仍然有序。 習(xí) 題 __算法題 (2) 設(shè)有兩個(gè)按升序排列的單鏈表 X和 Y，其頭指針?lè)謩e為 p、 q，結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下： typedef struct node1 { intdata。 }node。 (5) 哪些鏈表從尾指針出發(fā)可以訪問(wèn)到鏈表中的任意結(jié)點(diǎn)？ 習(xí) 題 __算法題 (1) 設(shè)某帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)說(shuō)明如下： typedef struct node1 { int data。 BB(pb,pa)。 pnext=s。 void BB(s,q) /* s、 q是指向結(jié)點(diǎn)類型的指針 */ { p=s。 } return OK。 pnext=q。 p=q。 Lnextnext) { q=Lnext。 Status a(L) { if(Lnext amp。 A. s t1 r1 = s t1 ； s r1 t 1 = s r1 ； B. s tl rl = s r1 ； s r1 t l = s tl ； C. s r 1 = s t1 r1 ； s t 1 = s r1 t1 ； D. s t 1 = s t1 rl ； s r1 =s r1 t1 ； ( 18 ) 假設(shè) l ef t 和 r i g h t 為雙向鏈表中指向直接前趨結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)的指針字段，現(xiàn)要把一個(gè)指針 s 所指的新結(jié)點(diǎn)作為非空雙鏈表中 q 所指結(jié)點(diǎn) ( 中間結(jié)點(diǎn) ) 的直接后繼結(jié)點(diǎn)插入到該雙向鏈表中，則下列算法段能正確完成上述要求的是 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. s n ex t = p n e x t ； p n e x t =s ； B. p n e x t = s ； s n e x t =p n e x t ； C. s n ex t = p n e x t ； p n e x t =s ；交換 p d at a 和 s d a t a ； D. p =s ； s n ex t = p ； 習(xí) 題 __單項(xiàng)選擇題 ( 16 ) 在一個(gè)具有 n 個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)，并使插入結(jié)點(diǎn)后的單鏈表仍然有序，則該操作的時(shí)間復(fù)雜性量級(jí)為 _ _ _ _ _ _ _ _ _ _ _ _ 。 A. n i +1 B.