【正文】 2=4 (2+8)/2=5 (2+9)/2=5 (2+10)/2=6 (2+14)/2=8 鏈地址法 0 AprAug 1 2 Dec 3 4 5 JanJuneJuly 6 FebMarMay 7 OctNov 8 9 Sep 10 11 12 13`0129 09E2 什么是二叉排序樹,按如下關(guān)鍵字的插入次序生成一棵二叉排序樹,試畫出此二叉排序樹 25,48,36,16,45,20,18,72~0129 二叉排序樹或者是一棵空樹,或者是具有如下性質(zhì)的二叉樹: (1)若它的左子樹不空,則左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值 。 }。 while(!QueueEmpty(Q)){ DeQueue (Q,y)。 DeQueue (Q,x)。DeQueue (Q,x)。 EnQueue (Q,’r’)。 y=’c’。 Init Queue (Q)。}在等概率情況下的平均查找長(zhǎng)度是ASL=(n+1)/2`0127 03B2 程序段的輸出結(jié)果是_________（隊(duì)列中的元素類型QElem Type為char）。if(i==n) return(1)。i=0。{int i。int SEQSEARCH(R,K)table R[]。}table。}`0126 09F2 編寫順序查找算法,并求在等概率情況下的平均查找長(zhǎng)度ASL.~0126 typedef struct{deytype key。}if empty(s) pair=true。} else pop(s) }i=i+1。:if empty(s) {pair=false。 39。:push(s,ch)。)) switch { 39。) || (ch=39。while (ch!=) { if ((ch=39。 i=1。,表達(dá)式被掃描完畢,棧就為空.)~0125 boolean pair(b){ stack s。就退掉棧頂?shù)?9。就進(jìn)棧,遇39。 }}`0123 09C1 順序查找法適用于存儲(chǔ)結(jié)構(gòu)為( )的線性表. A、 散列存儲(chǔ) B 、壓縮存儲(chǔ) C、順序或鏈?zhǔn)酱鎯?chǔ) D、索引存儲(chǔ)~0123 C`0124 03B2 由于查找運(yùn)算的主要操作是關(guān)鍵字的比較,所以,通常把查找過程中對(duì)關(guān)鍵字需要執(zhí)行的_________作為衡量一個(gè)查找算法效率優(yōu)劣的標(biāo)準(zhǔn).~0124 平均比較次數(shù)(或平均查找長(zhǎng)度)`0125 03F2 設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否正確配對(duì),(提示:對(duì)表達(dá)式進(jìn)行掃描,凡遇39。 } else { sqfront=(sqfront+1)%maxsize。 return(TRUE)。 } else { sqrear=(sqrear+1)%maxsize。datatype x){ if(sqfront==(sqrear+1)%maxsize) { printf(queue is full)。 rerurn(p)。amp。p=headnext。 }。}`0119 03C1 用數(shù)組A存放循環(huán)隊(duì)列的元素值,若其頭指針為front,尾指針為rear,則循環(huán)隊(duì)列中當(dāng)前元素個(gè)數(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)隊(duì)列Q頭指針為front,尾指針為rear,隊(duì)列的最大容量為M,寫出循環(huán)隊(duì)列隊(duì)滿和隊(duì)空的判定條件.~0120 隊(duì)滿條件: (+1)mod m= 隊(duì)空條件: =`0121 09F2 對(duì)一個(gè)鏈?zhǔn)酱尜A結(jié)構(gòu)的線性表進(jìn)行順序查找算法.~0121 struct node { int data。 else return(binasearch(s,k,low,mid+1)。if(k==[mid].key) return mid。){int mid。int low。}`0108 03B2 棧是一種特殊的_________,又稱為_________.~0108 線性表 后進(jìn)先出表`0109 03C1 設(shè)輸入序列為1,2,3,4,5借助一個(gè)棧不可能得到的輸出序列是( )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 順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿及隊(duì)空判斷條件是一樣的( )~0111 錯(cuò)誤`0112 03D1 棧和隊(duì)列都是線性表.( )~0112 正確`0113 03D1 排序和查找是兩種基本的數(shù)據(jù)結(jié)構(gòu).( )~0113 錯(cuò)誤`0114 09D1 隊(duì)列只能采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).( )~0114 錯(cuò)誤`0115 03B1 隊(duì)列是一種特殊的________,允許插入的一端稱為_______,允許刪除的一端稱為______,所以隊(duì)列又稱為____________.~0115 線性表 隊(duì)尾 隊(duì)頭 先進(jìn)先出表`0116 03B1 棧的兩個(gè)重要應(yīng)用是___________和_________.~0116 在編譯系統(tǒng)運(yùn)行計(jì)算機(jī)語(yǔ)言程序的過程中,利用棧進(jìn)行語(yǔ)法檢查,實(shí)現(xiàn)遞歸調(diào)用.`0117 03A2 棧和隊(duì)列都是運(yùn)算受到限制的特殊的線性表,棧和隊(duì)列有何不同?~0117 棧是僅允許在一端進(jìn)行插入和刪除的線性表,又稱為后進(jìn)先出表, 隊(duì)列是允許在一端插入,在另一端刪除的線性表,允許插入的一端的稱為隊(duì)尾,允許刪除的一端稱為隊(duì)頭,又稱為先進(jìn)先出表.`0118 09F2 寫出在有序表A上進(jìn)行遞歸形式的折半查找的算法,其中給定值 K為待查的關(guān)鍵字,若查找成功則返回該元素的下標(biāo),否則返回零值.~0118 int binasearch(Sqlist s。p=pnext。p=pnext。p=l。 }`0107 09F2 從循環(huán)單鏈表中查找出最小值 .~0107 int searchmin(linklist l){int min。 p=pnext。 p=pnext。 p=l。[31] 37,43,[61,79,47]`0063 10B1 文件按記錄的結(jié)構(gòu)可分為兩類______和______,按記錄中關(guān)鍵字的多少可分為______和________~0063 定長(zhǎng)記錄文件 不定長(zhǎng)記錄文件 單關(guān)鍵字文件 多關(guān)鍵字文件`0064 10B2 外部分類包括______和________~0064 磁帶文件的歸并分類 磁盤文件的歸并分類`0065 08B2 設(shè)一組關(guān)鍵字為{23,3,39,9,7,5,16,8},進(jìn)行線性插入分類,試寫出第一遍分類后關(guān)鍵字的排列次序________~0065 [23] 3 39 9 7 5 16 8 第一遍 [3 23] 39 9 7 5 16 8 第二遍 [3 23 39] 9 7 5 16 8 第三遍 [3 9 23 39 7] 5 16 8 第四遍 [3 7 9 23 39] 5 16 8 第五遍 [3 5 7 9 23 39] 16 8 第六遍 [3 5 7 9 16 23 39] 8 第七遍 [3 5 7 8 9 16 23 39]`0066 08B2 內(nèi)部分類包括(任寫六種)___________________________________~0066 冒泡分類 簡(jiǎn)單選擇分類 線性插入分類 折半插入分類 希爾分類 快速分類 堆分類 歸并分類 基數(shù)分類`0067 10B1 磁帶主要由______,______,______組成.~0067 磁帶介質(zhì) 讀寫磁頭 磁帶驅(qū)動(dòng)器`0068 08B1 分類的目的是____________________________~0068 便于查詢和處理數(shù)據(jù)`0069 08B2 你所學(xué)過的排序的方法中,哪些是穩(wěn)定的____________~0069 直接插入 二分(折半)插入 冒泡 歸并排序 枚舉`0070 08C2  下列排序算法中,排序花費(fèi)的時(shí)間不受數(shù)據(jù)開始排列特性影響的算法是( ) A、直接插入排序 B、冒泡排序 C、直接選擇排序 D、快速排序~0070 c`0071 08C2 下列排序算法中,最好情況下時(shí)間復(fù)雜度為0(n)的算法是( ) A、選擇排序 B、歸并排序 C、快速排序 D、冒泡排序~0071 d`0072 08E3 利用堆排序的方法給已知數(shù)據(jù)A中的數(shù)據(jù)排序,寫出在構(gòu)成初始堆和利用堆排序的過程中每次篩運(yùn)算后數(shù)據(jù)的排列情況(要求構(gòu)造大根堆) 1 2 3 4 5 6 7 8  ┌─┬─┬─┬─┬─┬─┬─┬─┐ A│45│28│49│16│37│82│56│75│ └─┴─┴─┴─┴─┴─┴─┴─┘~0072 1:45 28 49 75 37 82 56 16 2:45 28 82 75 37 49 56 16 3:45 75 82 28 37 49 56 16 4:82 75 45 28 37 49 56 16 5:75 37 45 28 16 49 56 82 6:56 37 45 28 16 49 75 82 7:49 37 45 28 16 56 75 82 8:45 37 16 28 49 56 75 82 9:37 28 16 45 49 56 75 82 10:28 16 37 45 49 56 75 82 11:16 28 37 45 49 56 75 82 `0073 10B1 根據(jù)排序文件所處的位置不同,可將排序分為______和______兩大類.~0073 內(nèi)部 外部`0074 08D1 堆排序是不穩(wěn)定排序 ( )~0074 正確`0075 10D1 文件中存取數(shù)據(jù)的基本單位是數(shù)據(jù)項(xiàng) ( )~0075 錯(cuò)誤`0076 08E2 設(shè)文件有10個(gè)記錄其關(guān)鍵字值分別為:37,23,7,79,29,43,73,19,31,61,試給出用冒泡排序法,按非遞減的次序進(jìn)行排序過程中的每一趟結(jié)果序列.~0076 37 23 7 79 29 43 73 19 31 61 第一趟 23 7 37 29 43 73 19 31 61 | 79 第二趟 7 23 29 37 43 19 31 61 | 73 三 7 23 29 37 19 31 43 |61