【文章內(nèi)容簡介】 三 13 38 [47] 52 64 85 最后結(jié)果 13 38 47 52 64 85`0093 08B2 所謂歸并是指將若干個__________ 的子文件合并成一個有序的文件.~0093 已排序`0094 08B2 給定一組關(guān)鍵字91,28,72,63,15,101,79,46,81將其用二路歸并排序的各趟結(jié)果.~0094 初始關(guān)鍵字 [91] [28] [72] [63] [15] [101] [79] [46] [81] 第一趟 [28,91] [63,72] [15,101] [46,79] [81] 第二趟 [28,63,72,91] [15,46,79,101] [81] 第三趟 [15,28,46,72,79,91,101] [81] 第四趟 [15,28,46,63,72,81,91,101]`0095 08B2 n個關(guān)鍵字序列k1,k2,......,kn稱為堆,當(dāng)且僅當(dāng)該序列滿足特性______和______(1=i=[n/2])~0095 k=k2i k=k2i+1`0096 08B2 ________的基本方法是:每一趟從待排序的記錄中選出關(guān)鍵字最小的記錄,順序放在以排好序的文件的最后直到全部記錄排序完畢.~0096 選擇排序`0097 08B2 堆排序是一樹形選擇排序,特點是在排序過程中,將r[1]到r[n]看成一棵________順序存儲結(jié)構(gòu).~0097 完全二叉樹`0098 08B2 起泡排序最好情況下,時間復(fù)雜度為______,其壞時間復(fù)雜度為_______ ,平均時間復(fù)雜度為_______ .~0098 0(n),0(n2),0(n2)`0099 08B2 評價排序算法好壞的標(biāo)準(zhǔn)主要兩條:第一條是算法執(zhí)行時所需的_____ ,第二條是執(zhí)行算法所需要的附加________~0099 時間, 附加空間`0100 08B2 交換排序的基本思想是:兩兩比較待排序記錄的_______ ,發(fā)現(xiàn)兩個記錄的次序相反時即進行交換,直到?jīng)]有_______ 的記錄為止,其中________和_________都屬于交換排序.~0100 關(guān)鍵字,反序,起泡排序,快速排序.`0101 03B2 順序棧S,棧頂指針為top,則棧置空操作是____________.~0101 stop=1`0102 03B2 設(shè)有一棧,結(jié)點結(jié)構(gòu)為data next *s結(jié)點入棧操作是________和__________.~0102 snext=hnext h=s`0103 09B1 在對有二十個數(shù)據(jù)有序表作二分查找時有___________個結(jié)點的查找長度是4.~0103 4`0104 09C1 用折半查找法的查找速度比用順序查找法的查找速度_________. A 必然慢 B必然快 C速度相等 D 快慢不定 ~0104 D`0105 03D2 假定有三個元素abc進棧,進棧次序為abc,則可能出棧序列為abc,acb,bac, bca,cba ( )~0105 正確`0106 09F2 從循環(huán)單鏈表中查找出最大值.~0106 int searchmax(linklist l) {int max。 int *p。 p=l。max=pdata。 p=pnext。while (pnext nil) { if (maxpdata) max=pdata。 p=pnext。} return max。 }`0107 09F2 從循環(huán)單鏈表中查找出最小值 .~0107 int searchmin(linklist l){int min。int *p。p=l。min=pdata。p=pnext。while (pnext nil) {if (minpdata) min=pdata。p=pnext。}return min。}`0108 03B2 棧是一種特殊的_________,又稱為_________.~0108 線性表 后進先出表`0109 03C1 設(shè)輸入序列為1,2,3,4,5借助一個棧不可能得到的輸出序列是( )A 、 1,2,3,4,5 B 、5,4,3,2,1 C 、 4,3,1,2,5 D、 1,3,2,5,4~0109 C`0110 09C1 適合折半查找的表的存貯方式及元素排列要求為( ) A、 鏈?zhǔn)酱尜A 元素?zé)o序 B 、 鏈?zhǔn)酱尜A 元素有序 C 、 順序存貯 元素?zé)o序 D 、 順序存貯 元素有序~0110 D`0111 03D1 順序隊列和循環(huán)隊列的隊滿及隊空判斷條件是一樣的( )~0111 錯誤`0112 03D1 棧和隊列都是線性表.( )~0112 正確`0113 03D1 排序和查找是兩種基本的數(shù)據(jù)結(jié)構(gòu).( )~0113 錯誤`0114 09D1 隊列只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu).( )~0114 錯誤`0115 03B1 隊列是一種特殊的________,允許插入的一端稱為_______,允許刪除的一端稱為______,所以隊列又稱為____________.~0115 線性表 隊尾 隊頭 先進先出表`0116 03B1 棧的兩個重要應(yīng)用是___________和_________.~0116 在編譯系統(tǒng)運行計算機語言程序的過程中,利用棧進行語法檢查,實現(xiàn)遞歸調(diào)用.`0117 03A2 棧和隊列都是運算受到限制的特殊的線性表,棧和隊列有何不同?~0117 棧是僅允許在一端進行插入和刪除的線性表,又稱為后進先出表, 隊列是允許在一端插入,在另一端刪除的線性表,允許插入的一端的稱為隊尾,允許刪除的一端稱為隊頭,又稱為先進先出表.`0118 09F2 寫出在有序表A上進行遞歸形式的折半查找的算法,其中給定值 K為待查的關(guān)鍵字,若查找成功則返回該元素的下標(biāo),否則返回零值.~0118 int binasearch(Sqlist s。keytype k。int low。int high。){int mid。while(low=high) { mid=(low+high)/2。if(k==[mid].key) return mid。if(k[mid].key) return(binasearch(s,k,mid1,high))。 else return(binasearch(s,k,low,mid+1)。}if(lowhigh) return 1。}`0119 03C1 用數(shù)組A存放循環(huán)隊列的元素值,若其頭指針為front,尾指針為rear,則循環(huán)隊列中當(dāng)前元素個數(shù)為( ).A、 (rearfront+m) mod m B 、 (rearfront+1) mod mC 、(rearfront1+m) mod m D 、 (rearfront) mod m~0119 A`0120 03A2 設(shè)循環(huán)隊列Q頭指針為front,尾指針為rear,隊列的最大容量為M,寫出循環(huán)隊列隊滿和隊空的判定條件.~0120 隊滿條件: (+1)mod m= 隊空條件: =`0121 09F2 對一個鏈?zhǔn)酱尜A結(jié)構(gòu)的線性表進行順序查找算法.~0121 struct node { int data。 struct node *next。 }。 typedef sealink(node *head,x){node *p。p=headnext。while (p!=NULL amp。amp。 pdata!=x) p=pnext。 rerurn(p)。}`0122 03F2 給出循環(huán)隊列的入隊和出隊算法.~0122 int ENQUEUE(sequeue *sq。datatype x){ if(sqfront==(sqrear+1)%maxsize) { printf(queue is full)。 return NULL。 } else { sqrear=(sqrear+1)%maxsize。 sqdata[sqrear]=x。 return(TRUE)。 }} datatype DEQUEUE(sequeue *sq){ if(EMPTY(sq)) { printf(queue is empty)。 } else { sqfront=(sqfront+1)%maxsize。 return(sqdata[sqfront]。 }}`0123 09C1 順序查找法適用于存儲結(jié)構(gòu)為( )的線性表. A、 散列存儲 B 、壓縮存儲 C、順序或鏈?zhǔn)酱鎯? D、索引存儲~0123 C`0124 03B2 由于查找運算的主要操作是關(guān)鍵字的比較,所以,通常把查找過程中對關(guān)鍵字需要執(zhí)行的_________作為衡量一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn).~0124 平均比較次數(shù)(或平均查找長度)`0125 03F2 設(shè)計算法判斷一個算術(shù)表達(dá)式的圓括號是否正確配對,(提示:對表達(dá)式進行掃描,凡遇39。(39。就進棧,遇39。)39。就退掉棧頂?shù)?9。)39。,表達(dá)式被掃描完畢,棧就為空.)~0125 boolean pair(b){ stack s。 =0。 i=1。 ch=b[i]。while (ch!=@) { if ((ch=39。(39。) || (ch=39。)39。)) switch { 39。(39。:push(s,ch)。break。 39。)39。:if empty(s) {pair=false。return。} else pop(s) }i=i+1。ch=b[i]。}if empty(s) pair=true。else pair=false。}`0126 09F2 編寫順序查找算法,并求在等概率情況下的平均查找長度ASL.~0126 typedef struct{deytype key。datatype other。}table。table r[n+1]。int SEQSEARCH(R,K)table R[]。keytype K。{int i。R[n].key=K。i=0。while(R[i].key!=K) i++。if(i==n) return(1)。else return i。}在等概率情況下的平均查找長度是ASL=(n+1)/2`0127 03B2 程序段的輸出結(jié)果是_________（隊列中的元素類型QElem Type為char）。void main( ){Queue Q。 Init Queue (Q)。Char x=’e’。 y=’c’。EnQueue (Q,’h’)。 EnQueue (Q,’r’)。 EnQueue (Q, y)。DeQueue (Q,x)。 EnQueue (Q,x)。 DeQueue (Q,x)。 EnQueue (Q,’a’)。 while(!QueueEmpty(Q)){ DeQueue (Q,y)。printf(y)。 }。Printf(x)。}~0127 stack`0128 09E2 在地址空間為016的散列區(qū)中,對以下關(guān)鍵字序列構(gòu)造兩個哈希表:(Jan, Feb, Mar, Apr, May, June, July, A