(2分)為解決計(jì)算機(jī)和打印機(jī)速度不匹配問題,通常設(shè)置一個打印數(shù)據(jù)緩沖區(qū),主機(jī)將,.?A.棧 B.隊(duì)列 C.樹 D.圖(2分SQ,元素abcdefgS.Q.7個元素出對的順序是bdcfeag,則棧S?A. 1 B:2 C.3 D,4(2分8.數(shù)最多為A. 39 B.52 C.111 D.119.若在二叉樹中節(jié)點(diǎn)u是節(jié)點(diǎn)v.,u與v的可能關(guān)系為甲)父子關(guān). )兄弟關(guān)系 ) u的父節(jié)點(diǎn)與v的父節(jié)點(diǎn)是兄弟關(guān)系A(chǔ).只有甲 B. 甲和乙 C.甲和丙 D甲乙丙,:甲)所有定點(diǎn)度數(shù)之和為偶. 乙)邊數(shù)大于頂點(diǎn)個數(shù)減1丙)至少有一個頂點(diǎn)的度為1.A. 只有甲 B.只有乙 C.甲和乙 甲和丙參考答案:1)B 2)C 3)D 4)B 5)C 6)B 7)A,不符合m階B:A.根節(jié)點(diǎn)最多有m棵子樹 B.所有葉節(jié)點(diǎn)都在同一層.C.各節(jié)點(diǎn)內(nèi)關(guān)鍵字均升序或降序排列 D.葉節(jié)點(diǎn)之間通過指針鏈已知關(guān)鍵字序列5,8,12,19,28,20,15,22(,).3調(diào)整后得到的極小堆是:A.3,5,12,8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19若數(shù)據(jù)元素序列11,12,13,7,8,9,23,4,5是采用下列排序算法之一得到的第二趟排序后的結(jié)果,:A.冒泡排序 B.插入排序 C.選擇排序 二路歸并排序如元素abcdef依次進(jìn)棧,允許進(jìn)棧出棧操作交替進(jìn)行,但不允許連續(xù)三次退棧.:A.dcebfa B.cbdaef C.bcaefd D.afedcb某隊(duì)列允許在其兩端進(jìn)行入隊(duì)操作,但僅允許在一端進(jìn)行出隊(duì)操作.若元素abcde,則不可能的出隊(duì)序列為A.bacde B.dbace C.dbcae D.ecbad參考答案:1)D2)A3)B4)D 5)CCBACBB.,:.;;.(2,12,16,88,5,10).如果前三趟排序結(jié)果如下(2,12,16,5,10,88)則采用的排序算法可能是:A.冒泡排序 B.希爾排序 C.歸并排序 D.基數(shù)排序DA1（ ）數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。2（ ）KMP3（ ）強(qiáng)連通分量是無向圖的極大強(qiáng)連通子圖。4（ ）查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。5（ ）求nk(k<<n)個數(shù)，起泡排序比直接選擇排序要好。6（ ）(AVL7（ ）外排中使用置換選擇排序的目的，是為了增加初始?xì)w并段的長度。8（ ）鏈表的每個結(jié)點(diǎn)都恰好有一個指針。9（ ）30151（ ）若完全二叉樹的某個結(jié)點(diǎn)沒有左子，則此結(jié)點(diǎn)必是葉子結(jié)點(diǎn)。FTFFFTFFTT（ ）。（ ）數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式和內(nèi)容無關(guān)。（ ）若把堆看成是一棵完全二叉樹，則該樹一定是一棵二叉排序樹。（ ）α1，則向散列表中散列元素時(shí)一定會產(chǎn)生沖突。（ ）霍夫曼樹的所有子樹也均是霍夫曼樹。（ ）(AVL（ ）若有向圖不存在回路，即使不用訪問標(biāo)志位同一結(jié)點(diǎn)也不會被訪問兩次。（ ）歸并排序在任何情況下都比所有簡單排序速度快。（ ）外排中使用置換選擇排序的目的，是為了增加初始?xì)w并段的長度。（ ）任何一個關(guān)鍵活動提前完成，則整個工程也會提前完成。TTFFTTFFTF1（ ）優(yōu)于順序存儲結(jié)構(gòu)。2（ ）線性表的邏輯順序與存儲順序總是一致的。3（ ）順序存儲方式只能用于存儲線性結(jié)構(gòu)。4（ ）順序存儲的線性表可以按序號隨機(jī)存取。5.（ ）非空循環(huán)鏈表中每一個元素都有后繼。6.（ ）在對隊(duì)列做出隊(duì)操作時(shí)，不會改變front7.（ ）數(shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)以及數(shù)據(jù)集合上定義的運(yùn)算。8.（ ）遍歷序列最后一個結(jié)點(diǎn)。9.（ ）已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。10.（ ）字符串是數(shù)據(jù)對象特定的線性表。TFFTTFFFFT選擇題:在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分（ ）A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B．緊湊結(jié)構(gòu)和非緊湊結(jié)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu) D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲單元的地址（ 。必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 連續(xù)或不連續(xù)都可以下列數(shù)據(jù)中（ ）不是線性數(shù)據(jù)結(jié)構(gòu)。隊(duì)列 B. 棧 C. 完全二叉樹 D.循環(huán)隊(duì)列除了考慮存儲數(shù)據(jù)結(jié)構(gòu)本身所占用的空間外，實(shí)現(xiàn)算法所用輔助空間的多少稱為（ ）時(shí)間效率 B.空間效率 C.硬件效率 D.軟件效率帶頭結(jié)點(diǎn)的單鏈表h為空的判斷條件是（ ）h==NULL B.h->next==hC.h->next==NULL D.h!=NULL6、以下算法的時(shí)間復(fù)雜度。for(i=1;i<=100;i++)for(j=i;j<=1000;j++)x=x+1;（A）O(1) （B）O(n)（C）O(n^2)（D）O(n^3)7、數(shù)據(jù)元素是數(shù)據(jù)的基本單位，其數(shù)據(jù)項(xiàng)。（A）只能包括一個 （B）不包含（C）可以包含多個 （D）必須包含多個8、線性表的鏈?zhǔn)酱鎯晚樞虼鎯ο啾龋钣欣谶M(jìn)。（A）查找（B）表尾插入或刪除（C）按值插入（D）表頭插入或刪除9、在一個單鏈表中，如果要在p所指向的節(jié)點(diǎn)之后插入一個新的節(jié)點(diǎn)，則需要相繼修改 個節(jié)點(diǎn)的指針域的值。（A）1 （B）2 （C）3 10、棧的插入和刪除操作在 進(jìn)行。（A）棧頂（B）棧底（C）任意位置（D）指定位置11、假定一個不設(shè)隊(duì)列長度變量的順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空條件。（A）f+1==r （B）r+1==f （C）r==f （D）f==12、在一棵樹中，每個節(jié)點(diǎn)最多個前驅(qū)節(jié)點(diǎn)。（A）0 （B）1 （C）2 （D）任意多個13、二叉樹的中序遍歷的順序。（A）根結(jié)點(diǎn)，左子樹，右子樹（B）左子樹，根結(jié)點(diǎn)，右子樹（C）右子樹，根結(jié)點(diǎn)，左子樹（D）左子樹，右子樹，根結(jié)點(diǎn)14、在一棵有35個結(jié)點(diǎn)的完全二叉樹中，該樹深度。（A）5 （B）6 （C）7 （D）815、順序查找適用于存儲結(jié)構(gòu)的線形表（A）順序存儲 式存儲（C）順序存儲或鏈?zhǔn)酱鎯?存儲設(shè)有兩個串p和其中q是p的子串求q在p中首次出現(xiàn)的位置的算法稱（ 。（A）求子串 （B）聯(lián)接 （C）模式匹配 （D）求串長17、具有10個記錄的序列，采用冒泡排序最少的比較次數(shù)。（A）1 （B）100 （C）9 （D）5518、快速排序情況下最不利于發(fā)揮其長處。（A）要排序的數(shù)據(jù)量太大 （B）要排序的數(shù)據(jù)中含有多個相同值（C）要排序的數(shù)據(jù)已經(jīng)基本有序 （D）要排序的數(shù)據(jù)是逆序、一組記錄的排序關(guān)鍵字為，，，，利用快速排序方法，以第一個記錄為基準(zhǔn)得到的第一次劃分的結(jié)果。（A）38，40，46，56，79，84 （B）40，38，46，79，56，84（C）40，38，46，56，79，84 （D）40，38，46，84，56，7920、對n個元素進(jìn)行直接選擇排序，需要進(jìn)趟選擇和交換（A）n （B）n+1 （C）n-1 （D）n/221、折半查找一個具有n個數(shù)據(jù)元素的線性表，其時(shí)間復(fù)雜度。（A）O(n) （B）O() （C）O(logn) （D）O(n3)222、在一棵非空二叉樹的中序遍歷序列中，根結(jié)點(diǎn)的右。（A）只有右子樹上的所有結(jié)點(diǎn) 有右子樹上的部分結(jié)點(diǎn)（C）只有左子樹上的所有結(jié)點(diǎn) 左子樹上的部分結(jié)點(diǎn)23、采用順序查找法檢索長度為n的線性表，則檢索每個元素的平均比較次數(shù)。（A）n （B）n/2 （C）(n+1)/2 24、采用順序查找時(shí)，設(shè)置“監(jiān)測哨”的好處。（A）降低平均查找長度 （B）查找失敗時(shí)，不必每次判斷表是否檢測完，統(tǒng)一算法（C）對于查找成功的情況，可以提高效率 （D）可以使算法對存儲沒有要求25在一棵度為3的樹度為3的結(jié)點(diǎn)個數(shù)為2,度為2的結(jié)點(diǎn)個數(shù)為1,度為1的結(jié)點(diǎn)個數(shù)為0,則度為0的結(jié)點(diǎn)個數(shù)。A．4 B．5 C．6 26、快速排序在平均情況下的時(shí)間復(fù)雜度為 。（A）O(n) （B）O() （C）O(nlogn) （D）O(n3)227、每次從無序表中挑選出一個最大或最小元素，把它交換到有序表的一端，這種排序方法叫。（A）插入排序（B）交換排序 （C）選擇排序 （D）冒泡排序28、快速排序是一種（ 。A.插入排序 B.交換排序 C.選擇排序 歸并排序29、將一棵有100個結(jié)點(diǎn)的完全二叉樹，從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的雙親的編號。（A）24 （B）25 （C）23 30、深度為６（根節(jié)點(diǎn)的層次為１）的二叉樹至多個結(jié)點(diǎn)。（A）64 （B）63 （C）31 （D）321234567891011121314151617181920CDCBCACDBACBBBCCCDCC21222324252627282930CACBCCCBAB六不同元素依次進(jìn)棧，能得種不同的出棧序列。A.42 B.82 C.132 D.192數(shù)據(jù)對象是具有相同特性的集合，它是數(shù)據(jù)的子集。數(shù)據(jù)項(xiàng) B.數(shù)據(jù)元素 C.數(shù)據(jù)對象 D.數(shù)據(jù)結(jié)構(gòu)含有4個元素均不相的結(jié)點(diǎn)的二叉排序樹種。A.4 B.6 C.10 D.有345個元素的有序表，等概率順序查找成功的平均查找長度A.173 B.172 C.86 D.345一棵Huffman樹共有215個結(jié)點(diǎn)，對其進(jìn)行Huffman編碼，共能得不同碼字；A.107 B.108 C.214 D.215一個具有n個頂點(diǎn)的無向圖，最少條邊一定連通。A.n-1 B.n C.n(n-1)/2 D.(n-1)(n-2)/2+1若一個有向圖的鄰接矩陣，則該有向一定存在拓?fù)渑判颉Ｏ∈杈仃?B.對稱矩陣 C.對角矩陣 D.三角矩陣選用時(shí)間最快的穩(wěn)定排序算法。歸并排序 B.堆排序 C.快速排序 D.簡單插入排序18個初始?xì)w并段進(jìn)行5路平衡歸并，需要增個虛擬歸并段。A.1 B.2 C.3 D.4一棵m階的B+樹中，每個結(jié)最多棵子樹。m/2 B.m C.m-1 D.m+1CBDABDDACB一．已知一棵3階的B－樹初態(tài)如下所示，若此后依次向此樹中插入關(guān)鍵字55、61、7，然后再刪除關(guān)鍵字50、101，請畫出每一步執(zhí)行后B－樹的狀態(tài)。45 7045 7025 3052906192739506388101二．請回答以下關(guān)于有向圖的一些問題：某有向無環(huán)圖如下所示，請寫出該圖全部的拓?fù)湫蛄校粚τ谝粋€有向圖，不用拓?fù)渑判颍绾闻袛鄨D中是否存在環(huán)？441736258三．已知一組待排關(guān)鍵字序列{83120，52366，7037，43126，50921，5731，83265，73192，8235，49198}，試根據(jù)基數(shù)排序原理寫出每一趟排序的結(jié)果。四．求模式串P='decddecgdecdegf'的next和nextval數(shù)組各元素的值，填入下表中。J012345 678910111213 14Pnext[j]nextval[j]decddecgdecdegf五．設(shè)已知散列表的地址空間為0-10，散列函數(shù)為H(K)=KMOD11，解決沖突的方法為線性探測再散列法，試將下列關(guān)鍵字集合{22,41,53,33,46,30,13,01,67}依次插入到如下所示的散列表中。并分別求出等概率下查找成功時(shí)和查找失敗時(shí)的平均查找長度.散列地址0散列地址0011223344556677889910關(guān)鍵字六．先根遍歷序列：ABCDEFGHIJKL后根遍歷序列：BDEFCGJKILHA七．已知一圖如下圖所示，以v1為源點(diǎn),以v7為匯點(diǎn)，求出所有事件允許發(fā)生的最早時(shí)間和最晚時(shí)間填入下表中，并求出所有的關(guān)鍵路徑；V2V2a6=5V5a1=3a4=2a11=3a7=2V1a2=6V4a10=5V7a5=3a9=2a12=4a3=3V3a8=3V6事件事件Ve(j)Vl(j)V1V2V3V4V5V6V7八．已知采用某種內(nèi)部排序方法對關(guān)鍵字序列{3，87，12，61，70，97，26，45}進(jìn)行排序，可得到如下幾組中間結(jié)果，請問該方法為何種排序法，并利用該排序方法填寫空白處的內(nèi)容。初態(tài)：3，87，12，61，70，97，26，45（1）97，87，26，61，70，12，3，45（2）45，87，26，61，70，12，3，97（3）3，70，26，61，45，12，87，97（4）12，61，26，3，45，70，87，97（5）（6）（7）（9）（9）3，12，26，45，61，70，87，97九)(m，g，b，e，d，c，a，p，n，h，q，k)，按此順序建立平衡二叉樹，畫出此樹，并求在等概率情況下查找成功的平均查找長度。十)已知有向網(wǎng)絡(luò)的鄰接矩陣為：頂點(diǎn)ABCDEA01530B0108C01510D2008E0畫出此圖；求該圖的強(qiáng)連通分量；從頂點(diǎn)A出發(fā)用DFSBFSDFSBFS用Dijkstra算法求出從源點(diǎn)A到其它各點(diǎn)的最短路徑及它們的長度。十一)已知一組記錄的關(guān)鍵字為{18,2,10,6,78,56,45,50,110,8}.按輸入順序畫出此組記錄的平衡二叉樹，求等概率情況下查找成功的平均查找長度。若查找每個元素的概率不等，此時(shí)的平衡二叉樹是否是最佳查找樹？為什么？十二)多少？十三)求字符串＂aabcdaaa＂的next和nextval數(shù)組值。(10)st(算法如下u=s;while(u!=t){選擇從u出發(fā)的權(quán)值最小的弧邊e=(u,v);u=v}請問上述算法是否正確.若正確請給出證明,若不正確,請給出反例.(10分),k(>=0).(假設(shè)該鏈表至少有k,)甲)描述算法思想乙)描述實(shí)現(xiàn)步驟將n(>0)個整數(shù)存放在數(shù)值R中.試設(shè)計(jì)一個算法在時(shí)間和空間兩個方面盡可能高的算法,將R中元素循環(huán)左移p(0<p<n)個位.即將R中的數(shù)據(jù)(x,x,…,x )變換0 1 n-1為(x,x ,…x ,xx…x ).要求給出算法的基本思;根據(jù)設(shè)計(jì)思,采用C/C++/Javap p+1 n-1 01 p-1語言描述算法;關(guān)鍵處給出注釋;說明算法的時(shí)間和空間復(fù)雜度.參考答案:先將R..試編寫算法，對一棵以孩子—兄弟鏈表表示的樹統(tǒng)計(jì)葉子節(jié)點(diǎn)的個數(shù)。typedef struct nodeetype data;node *child, *sibling;}node, *bitptr;int bitptr root）//root為根節(jié)點(diǎn)，函數(shù)返回值為葉子結(jié)點(diǎn)個數(shù){if(root==NULL)return(0);elseif(t->child==NULL) //return(1+Count(t->nextsibling))；//1（當(dāng)前結(jié)點(diǎn)為葉子）+兄弟子樹上的葉子結(jié)點(diǎn)個數(shù)else}

return(Count(t->firstchild)+Count(t->nextsibling));//左子樹的葉子個數(shù)+兄弟子樹的葉子個數(shù)=0；若左子空，則葉子數(shù)目=1元素值大于n且小于m就地置逆n>，其它部分保持不變。假設(shè)一棵平衡二叉樹的每個結(jié)點(diǎn)都標(biāo)明了平衡因子bf,試設(shè)計(jì)一個算法，利用bf的值求平衡二叉樹的高度。typedef struct node{int bf,struct node*left，*right;}BiTNode，*BSTree；int height(BSTreet)t的高度若待排序列用帶頭結(jié)點(diǎn)的單鏈表存儲，試給出簡單選擇排序算法（15分）typedef struct node{int key;node *next;}node, *pointer;voidselectsort(pointer&h)//h為頭指針已知一棵二叉樹的中序遍歷序列和按層次遍歷的序列鏈表。[a0..an-1]k小元素，要求平均時(shí)間復(fù)雜度為。intk_th(inta[],intn,intk)//返回第k小元素模擬試題一．選擇題：選擇正確的答案填入下面的 中（10分）1．長度為n的順序存儲線性表，當(dāng)在任何位置上插入或刪除一個元素的概率都相等時(shí)插入一個元素所需移動元素的平均個數(shù)為A： ，刪除一個元素所需移動元素的平均個數(shù)為B： 。AB：①(n-1)/2 ②n ③n+1 ④n-1 ⑤n/2 ⑥(n+1)/22．在雙向循環(huán)鏈表p指針指向的結(jié)點(diǎn)之前插入一個q指針指向的結(jié)點(diǎn)，其修改指針的作（注：雙向鏈表結(jié)點(diǎn)的結(jié)構(gòu)為 priordatanext其中prior與next分別為指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的指針）①p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;②p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior;③q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;3．下列排序方法中時(shí)間復(fù)雜度為O(nlogn)，且使用輔助空間最少的是A： ；2間復(fù)雜度不受待排序序列的初始狀態(tài)影響，恒為O(n2)的是B： 。A、B：①堆排序 ②冒泡排序 ③快速排序 ④希爾排序⑤直接插入排序 ⑥簡單選擇排序順序文件在數(shù)據(jù)量很大的情況下適合。①按關(guān)鍵字存取 ②直接存取 ③成批處理 ④隨機(jī)存取二維數(shù)組a[0..8][1..10685共占用A：個存儲單元。若aa[8][5]的起始地址與aB：的起始地址相同。A：①108②114③54④60⑤160B：①a[8][5]②a[3][10]③a[5][8]④a[0][9]假設(shè)某文件經(jīng)過內(nèi)部排序得到27個初始?xì)w并段，若要使多路歸并3趟完成，則應(yīng)歸并的路數(shù)。①2②3③4④57．倒排文件含有若干個倒排表，倒排表的每一個元素①一個主關(guān)鍵字值及其記錄地址②一個次關(guān)鍵字值及具有此次關(guān)鍵字值的記錄個數(shù)③一個次關(guān)鍵字值及所有具有此次關(guān)鍵字值的記錄地址二．回答下列問題（10分）T是一棵二叉樹，共有11個結(jié)點(diǎn)，除葉子結(jié)點(diǎn)外其它結(jié)點(diǎn)的度數(shù)皆為2，試問T的最大可能高度h 和最小可能高度h 是多少？T中共有多少非葉結(jié)點(diǎn)？max min設(shè)目標(biāo)串t='abcd'匹配方法的特點(diǎn)是什么？時(shí)間復(fù)雜度是多少？ -2如果有向圖含有路徑長度為負(fù)的回路（1所示，1試問用Floyd方法求每對頂點(diǎn)之間的最短路徑能否正常 12 3工 作 ？ 為 什 么 ？圖題Ⅱ-143B-樹至少有多少個結(jié)點(diǎn)？為什么？外排序的歸并排序中使用的選擇樹和堆排序中的堆有什么區(qū)別？三．已知一棵二叉樹按層次遍歷序列為BGDHAECIFJ（13）畫出此二叉樹的后序后繼線索樹；畫出此二叉樹對應(yīng)于完全二叉樹的順序存儲結(jié)構(gòu)；4a=54a=58a=23a=55四．某工程的AOE網(wǎng)絡(luò)如圖題Ⅱ-2所示。圖中邊上的權(quán)值為活動a~a

的期限（即完成1a=41a=423a=776a=1a=36a=3912a=245活動所需的天數(shù)（12分）求該工程各事件的最早發(fā)生時(shí)間ve

和允許的最晚發(fā)生時(shí)間vl

及各活動的最早開始時(shí)間e和允許的最晚開始時(shí)間l。完成此項(xiàng)工程至少需要多少時(shí)間？哪些活

a=810動 是 關(guān) 鍵 活 動 ？圖題Ⅱ-2{78,12,45,98,23,109,85,68,89,256,34（15）少？將這組記錄關(guān)鍵字建成一個小根堆；查找成功的平均比較長度是多少？若查找給定關(guān)鍵為45和90的記錄各需比較多少次？六．有一組數(shù)據(jù)元素存于數(shù)組L[1..n]中，閱讀下面的算法，寫出該算法的功能，并分析其時(shí)間復(fù)雜度是多少？（10分）voidmaxmin(inti,intj,ElemType*max,ElemType*min)//此為遞歸算法，調(diào)用初值i=1，j=n{ElemTypemax1,max2,min1,min2;intmid;if(i==j)*max=*min=L[i];else{mid=(i+j)/2;maxmin(i,mid,&max1,&min1);maxmin(mid+1,j,&max2,&min2);if(max1>max2)*max=max1;else*max=max2;if(min1<min2)*min=min1;else*min=min2;}}//maxmin七．試寫一個算法，判斷某二叉樹（以二叉鏈表方式存儲）是否為完全二叉樹（15分八．已知有向圖的鄰接表，試寫出求此有向圖逆鄰接表的算法（15）[模擬試題參考答案]一．選擇題：1．A：⑤B：①2.③3.A：①B：⑥4.③5.A：①B：②6.②7.③二．問答題：非葉結(jié)點(diǎn)的個數(shù)為5；h =6；h =4max min簡單的模式匹配過程如下：i123456789101112sabaabcdabfpg‖a‖b‖a‖cbdcd‖‖a b c d‖‖‖‖abcd（匹配成功，index(s,t)=4）簡單的模式匹配方法，最壞的情況出現(xiàn)在每趟比較都到模式串的最后一個字符時(shí)才失配，此時(shí)的時(shí)間復(fù)雜度是O(m*n)。KMP法的特點(diǎn)是每趟比較目標(biāo)串的下標(biāo)i不回溯，時(shí)間復(fù)雜度為O(m+n)。3．如果有向圖含有路徑長度為負(fù)的回路時(shí)，F(xiàn)loyd方法不能正常工作。雖然Floyd方法允許路徑為負(fù)數(shù)的情況，但不得包含路徑長度為負(fù)的回路，如圖題Ⅱ-1的有向圖，在求頂點(diǎn)①→③的最短路徑過程中，當(dāng)加入中間點(diǎn)②測試時(shí)，因?yàn)榛芈发凇佟诘拈L度為-1,而①→③之間可無數(shù)次經(jīng)過這個回路，每經(jīng)過一次，其路徑長度就減去1，因此使得A[1,3]=-。43B15mB-樹除根之外的每個結(jié)點(diǎn)至少有m/2=2棵子樹，而根至少有兩棵子樹，所以對3階B-樹而言最少的結(jié)點(diǎn)數(shù)應(yīng)與高度相同的滿二叉樹結(jié)點(diǎn)數(shù)相同。選擇樹是由參加比較的nn的序列表示的完全二叉樹，它滿足R且R或RR且RR。i 2i i 2i+1 i 2i i 2i+1三．1所示；所示；ABCBDHCFJA所示。ABCBDHCFJAGEIDEGEIDEFGHIJ1 234 5 678 9101112131415ABABCDE圖題Ⅱ-4四．1．某工程AOE網(wǎng)絡(luò)的各事件最早發(fā)生時(shí)間和允許的最晚發(fā)生時(shí)間如表題Ⅱ-1所示；各個活動的最早開始時(shí)間和允許的最晚開始時(shí)間如表題Ⅱ-2所示。表題Ⅱ-1事件表題Ⅱ-1事件12 3 4 5a a9 10

a a a a a表題Ⅱ-2活動表題Ⅱ-2活動a1a2a3ve0349514e0003444953vl06491114l30794107911614aaa1-3-4-62 5 8五．1．對這組記錄關(guān)鍵字進(jìn)行一趟快速排序后的結(jié)果是： 12[34,12,45,68,23]78[85,109,89,256,98] 23此趟排序中關(guān)鍵字比較10次。 由此組記錄關(guān)鍵字建成的小根堆如圖題所示。68 34表題Ⅱ-3序號 1234表題Ⅱ-3序號 123456key 122334456878858998109256圖題Ⅱ-6636314142等概率情況下查找成功的平均查找長度為：ASL=(1+22+43+44)/11=33/11=3K=453K=904

5圖題Ⅱ-7六．本算法的功能是求數(shù)組L中元素的最大值和最小值。算法的時(shí)間復(fù)雜度分析如下：

1 n=1T(n/2)+T(n/2)+3 為分析方便假設(shè)2（k為正整數(shù)，且每次將序列分為兩個長度相等的子序列，則：T(n)=T(n/2)+T(n/2)+3=2T(n/2)+3=2(2T(n/4)+3)+3=4T(n/4)+2*3+3=4(2T(n/8)+3)+2*3+1*3=8T(n/8)+22*3+21*3+20*3=8T(n/8)+(22+21+20)*3=??=2kT(n/2k)+(2k-1+2k-2+??+21+20)*3=2kT(1)+(2k-1)*3=2k+(2k-1)*3=4*2k-3=4n-3=O(n)因此算法的時(shí)間復(fù)雜度為O(n)。七．算法思想：所示，對于完全二叉樹而言，按層次排列二叉樹的結(jié)點(diǎn)時(shí)，結(jié)點(diǎn)是連續(xù)存在的；而對于非完5（105列結(jié)點(diǎn)時(shí)，會有空結(jié)點(diǎn)間隔實(shí)際存在結(jié)點(diǎn)的情況。

1245 61248 9 101112圖題Ⅱ-8完全二叉樹示例設(shè)一個輔助隊(duì)列q存放二叉樹結(jié)點(diǎn)的指針，另設(shè)標(biāo)志變量tag，表示按層次逐層從左至右掃描結(jié)點(diǎn)過程中是否出現(xiàn)過空結(jié)點(diǎn)，其初值為0，意為尚未有空結(jié)點(diǎn)出現(xiàn)。若根結(jié)點(diǎn)存在，指針入隊(duì)；隊(duì)列不空時(shí)，反復(fù)以下操作：若出隊(duì)指針p為空，置否則p不為空，若此時(shí)tag=1，則判定為非完全二叉樹，結(jié)束；若此時(shí)tag=0，將它的左孩子和右孩子指針入隊(duì)；算法描述：#definemaxsize100#defineFALSE0#defineTRUE1typedefstruct{ElemTypedata;structBitnode*lchild,*rchild;}Bitnode,*Bitree;//定義二叉樹結(jié)點(diǎn)類型和二叉樹類型typedefstruct{BitreeElem[maxsize];intfront,rear;}Sequeue;//定義隊(duì)列類型intcomplete_Bintree(Bitreet)//判斷二叉樹是否為完全二叉樹，t為二叉樹根結(jié)點(diǎn)的指針。/該二叉樹是完全二叉樹，返回“真（即（即0。{Sequeueq;qq.front=-1