北師大教育技術(shù)數(shù)據(jù)結(jié)構(gòu)考研歷年真題總結(jié)

..1998年請譯出以下專業(yè)術(shù)語：1、balancedmerging2、criticalpaths3、directedgraph4、fieldidentifier5、hashingfunction6、linearlinkedlists7、postordertraversal8、recursiveprocedure9、spanningtree10、top-downapproach簡答：1、遞歸算法有何特點？定義遞歸子程序時應(yīng)注意什么？2、設(shè)計一個好的算法,應(yīng)具有哪幾個基本特性？3、32階的B+樹,作為有100萬個數(shù)據(jù)項的索引時,樹高為多少？若改用256階的B+樹,最小樹高為多少？4、簡述抽象數(shù)據(jù)類型隊列的定義。5、面向?qū)ο蟮某绦蛟O(shè)計,有何優(yōu)點？填空：1、在Pascal程序中,標(biāo)識符要先_______后________,各標(biāo)識符的作用域始于_________,止于______________。2、在Pascal程序塊中說明的指針變量如p:↑real;中的p是_____態(tài)的變量,它在該程序塊被激活時占有特定存區(qū)；而p↑是_______型的______態(tài)變量,在__________時才________相應(yīng)的存區(qū)。3、使用關(guān)鍵路徑方法安排施工計劃,圖中各頂點代表___________,各個邊代表_________,邊長表示_________,這類圖又稱作__________網(wǎng)。4、哈夫曼編碼是在已知諸事件出現(xiàn)幾率相差_______時,用來________描述事件序列的代碼數(shù)的方法,請?zhí)畋聿⑶笃骄枋鲆粋€事件要用的比特數(shù)________。事件出現(xiàn)幾率編碼A0.8B0.1C0.06D0.045、若下方為某有向圖的鄰接矩陣：A0567∞B∞04∞3C8∞05∞D(zhuǎn)∞∞502E9∞∞40則有A至E的最短路徑為_______,其長度為________；而E至A的最短路徑為________,長度為________。讀程序,寫輸出：programtest41;Proceduretry<x:integer>;Vary:0...4Beginy:=xmods;x:=xdivs;Ifx<>0thentry<x>;write<y>End;Begintry<3179>end.輸出為：________2、若計算機(jī)做加法時,把比運算器最低位之后的數(shù)據(jù)舍掉；Programtest42;CONSTM=255;ONE=1;HALF=0.5;TYPER=0....5;VARI:R;F:=HALF;BEGINI:=1;F:=HALF;WHILE①、②DOBEGINI:=I+1;①ONE<>ONE+F時輸出為：_________F:=F*HALFEND;WRITELN<‘I:’,I:3>②F<>0時輸出為：_________END.<此題無需填具體值>五、編寫程序或子程序：1、請編寫程序讀取文件DATA.TXT中的數(shù)據(jù),存入數(shù)組。該文件是由字處理程序準(zhǔn)備好的,上面是多次對同一樣本測得的值,數(shù)值數(shù)目小魚200個。再求這些值的均值和標(biāo)準(zhǔn)差〔,并剔除與均值距離超過3倍標(biāo)準(zhǔn)差的可疑數(shù)據(jù)復(fù)算均值,直到?jīng)]有可剔除數(shù)據(jù)為止。2、使用二叉鏈接樹時,請編寫Pascal函數(shù),以使在調(diào)用時,指定某個樹的根指針時,可求出該樹內(nèi)結(jié)點的總數(shù)。top為棧頂指針,各元素皆為記錄型,其中key字段類型為INFO;next字段類型為LINK。請改正進(jìn)棧與退棧過程中的錯誤。..1999請譯為中文：1、Breadth-firstsearch2、Discreteeventsimulation3、Enumeratedmethod4、Functionaldesignator5、Huffmancoding6、Linerlinkedlists7、Radixsorting8、Recursiveroutine9、Spanningtree10、Undirectedgraph填空：1、使用關(guān)鍵路徑方法安排施工計劃時,通常圖中各個頂點代表______________,邊代表________________,邊長表示____________。這類圖又稱作_________________網(wǎng)。2、B樹是一種__________樹,但在其所有葉子結(jié)點內(nèi)都沒有____________；B﹢樹是___________樹,在其諸葉子結(jié)點中有____________,沒有___________。3、Pascal源程序在____________時能發(fā)現(xiàn)語法錯,修改后應(yīng)____________；如果通過編譯后再運行時出錯則為錯,這時應(yīng)在編輯窗口中__________并__________與運行。4、哈夫曼編碼的目的是_______________________。為此在已知各事件出現(xiàn)幾率時,要用___________的碼組表示幾率最大的事件,且任一個碼組都不能稱為其它碼組的________。5、已經(jīng)定義好了某數(shù)組類型,其下標(biāo)類型為index=0..n{n為常量標(biāo)識符},a為該數(shù)組類型的變量,在a[1]到a[n]中有類型為item的排序之值。簡答題：1、試舉例說明用程序設(shè)計語言描述堆棧結(jié)構(gòu)時,要涉及哪些問題？2、在程序設(shè)計語言中實現(xiàn)遞歸的條件是什么？編寫遞歸子程序,應(yīng)注意什么？3、動態(tài)查找樹,有哪幾項基本操作？4、舉例說明有向圖的最短路徑算法常用于哪幾種情形？改錯：2、在數(shù)組已排好序的前提下,TEST42函數(shù)用來查找其內(nèi)值為key的元素：若未找到,函數(shù)值為0,否則函數(shù)值為該元素的下標(biāo)值。按要求編寫程序或子程序：請編寫函數(shù)子程序以計數(shù)指定了指針的某個二叉樹內(nèi)結(jié)點的總數(shù)。已知：若n為自然數(shù),先后調(diào)用RANDOM<n>將產(chǎn)生在0到n-1之間取值的偽隨機(jī)序列。請編寫程序給小學(xué)生做四則運算的練習(xí),且要求如下：〔1每組25道題,每題列出題號、模式及等號,請小學(xué)生輸入答案；〔2若答案正確,該題得4分,加到總分中去,再給出下一題的題目；若第一次的答案不正確,則應(yīng)指出來,隨后重顯示原題,請學(xué)生答第二次,這次若能答對,仍記2分,并立即顯示下題；在第二次仍算錯后,先指出答案錯了,再顯示正確的式子；〔3加、減、乘、除運算的順序亦由一種隨機(jī)數(shù)來控制,使各種不同運算無規(guī)則地交錯進(jìn)行；〔4每組中加、減、乘、除和平方〔以兩相同數(shù)相乘表示各占5題；〔5每組題做完要顯示學(xué)生做該組題的成績；〔6在此組題目中要求被減數(shù)大于減數(shù),要求除法恰好除盡；〔7運算數(shù)的位數(shù)應(yīng)當(dāng)不使運算超出2字節(jié)整數(shù)的范圍。..2001請譯為中文：1、adjacencymatrix2、binarysearch3、completegraph4、enumeratedscalar5、heapsorting6、linearlinkedlist7、minimalspanningtree8、optimalmergetree9、patternmatching10、postfixnotation11、preordertraversal12、refinementapproach13、shortestpathfirst14、threadedfile簡答題：1、試說明描述數(shù)據(jù)結(jié)構(gòu)時,必須涉及哪些方面？2、好的應(yīng)用程序應(yīng)當(dāng)具有哪些共同特點？3、編寫與使用遞歸子程序應(yīng)注意什么？4、階為32的B樹,構(gòu)成有10萬個數(shù)據(jù)項的索引時,最大搜索長度是多少？若改用階為128的B樹,這一長度變?yōu)槎嗌伲?、說明對字符串的基本操作是什么？6、給出子圖的形式定義？并回答連通圖的極小連通圖是什么？填空：1、在面向?qū)ο蟮某绦蛟O(shè)計中,對象是包含_______和_________的邏輯實體,實體內(nèi)專有的這兩部分被封裝在一起,較好地解決了________、__________及模塊化這3個軟件的基本問題。2、PASCAL程序中直接說明的指針型變量p是________態(tài)變量,在執(zhí)行________<p>過程語句后,p↑成為新的________態(tài)變量,被稱作__________的變量。3、采用哈夫曼編碼的目的是__________,為此出現(xiàn)頻度最大的事件要用__________的碼組來表示,且任一碼組都不應(yīng)成為其他碼組的___________；若第k個事件出現(xiàn)的幾率為PR,并滿足以下等式ΣPK=1,且Pn>Pn+1,<0<k<5>,則平均碼長為__________。4、使用關(guān)鍵路徑方法安排施工計劃時,圖中各頂點代表________,各個弧代表________,弧長表示___________。這類帶權(quán)的有向無環(huán)圖又稱作_________網(wǎng)。5、試以15、6、23、4、19為原始序列,請?zhí)畛鲇弥苯硬迦敕ò瓷蚺判驎r,每趟處理后的情況：_______________________;_______________________;_______________________;_______________________。結(jié)合你對計算機(jī)運算器的理解完成本題填空,使程序運行時的輸出正確無誤。改錯：請按要求編程序：1、根據(jù)公式：編寫求e值到盡可能精確,并將結(jié)果輸出的程序。2、某系統(tǒng)選撥優(yōu)秀畢業(yè)生,要求對近200名畢業(yè)班學(xué)生的成績進(jìn)行統(tǒng)計排序。設(shè)已將課程分成公共基礎(chǔ)課和專業(yè)課兩類,每個學(xué)生分類計算的兩個平均分也已經(jīng)存入了名為‘LIST.TXT’的文件,該文件是用寫字板編輯成的,文件內(nèi)每行存入一個學(xué)生的信息,最左方是學(xué)號,隨后先是公共基礎(chǔ)課平均分,后是專業(yè)課平均分,最右方是學(xué)生姓名,各項之間有一個或多個空格。學(xué)號是8位的數(shù)碼字符串；兩個平均分皆為帶兩位小數(shù)的實數(shù)；學(xué)生姓名為最多10位的字符串。請編寫程序,按公共基礎(chǔ)課占4成,專業(yè)課占6成計算出綜合成績,并給出最終排好序的選撥名單。排隊的規(guī)則是先分兩檔,進(jìn)入第1檔的條件是兩類課程平均分都不低于90分,然后在每檔內(nèi)按照綜合成績的高低排序。排好序的結(jié)構(gòu)嬴蕩記入一個名為‘SORTED.TXT’文本文件,且將錢20名的情況送往屏幕。文件及屏幕上數(shù)據(jù)的格式是：名次姓名學(xué)號檔次綜合成績公共課成績專業(yè)課成績..2003請翻譯成中文：1、allocationstrategy2、boundarytagmethod3、mergeinsertionsort4、patternmatching5、threadedbinarytrees6、adjacencymultilists7、asymptotictimecomplexity8、indexedsequentialsearch9、implementinglinkedlistsusingarray10、quadraticprobing11、circularlinkedlist12、discreteeventsimulation簡答題：1、從概念上講,樹、森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu),將樹、森林轉(zhuǎn)化為二叉樹的基本目的是什么,并指出樹和二叉樹的主要區(qū)別。2、面向?qū)ο蟮某绦蛟O(shè)計方法有何特點,并說明繼承的含義。3、一棵二叉樹的中序遍歷序列為：ECBHFDJIGA,后序遍歷序列為ECHFJIGDBA,請構(gòu)造出這棵二叉樹,并寫出它的先序遍歷序列。4、線性表的順序存儲結(jié)構(gòu)具有三個弱點：第一,在作插入或刪除操作時,需要移動大量元素；第二,由于難以估計,必須預(yù)先分配較大的空間,往往使存儲空間不能得到充分利用；第三,表的容量難以擴(kuò)充。試問,線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是否一定能夠克服上述三個弱點？請簡述之。5、簡要敘述Hash表技術(shù)中沖突的概念,并給出三種解決沖突的辦法。6、何謂算法,其基本特征是什么？填空：1、稀疏矩陣一般的壓縮存儲方法有兩種,即____________和____________。2、遞歸函數(shù)f<n>=f<n-1>+n<n>1>的遞歸出口是________,遞歸體是_______。將遞歸算法轉(zhuǎn)換成對應(yīng)的非遞歸算法時,通常需要使用___________。3、廣義表〔a,b,<c,d>,e,<<i,j>,k>的長度是________,深度是_______；廣義表運算式HEAD<TAIL<<x,y,z>,<a,b,c>>>的結(jié)果為____________。4、以數(shù)據(jù)集〔4,5,6,7,10,12,18為結(jié)點權(quán)值所構(gòu)造的哈夫曼樹為_______,其帶權(quán)路徑長度為_____________。5、已知序列{18,19,62,45,9,37,78,69,88},采用快速排序法對該序列作升序排列時每一趟的結(jié)果為:初始：____________________________第一趟：____________________________第二趟：____________________________第三趟：____________________________第四趟：____________________________第五趟：____________________________第六趟：____________________________第七趟：____________________________第八趟：____________________________6、對于長度為n的線性表,順序查找法的平均查找長度為______,其時間復(fù)雜度為_______;二分查找法的平均查找長度為_______,其時間復(fù)雜度為_____;若采用分塊查找〔假定總塊數(shù)和每塊長度均接近,其時間復(fù)雜度為_____。7、在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中,排序是不穩(wěn)定的有________、_________、__________、__________,平均比較次數(shù)最少的排序是_________,需要內(nèi)存容量最多的排序是_________。8、下面算法是實現(xiàn)對以鄰接表存儲的圖進(jìn)行深度優(yōu)先遍歷遞歸算法,請空白處填上適當(dāng)?shù)膬?nèi)容。Typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];VoidDFSTraverse<ALGraph*G>{inti;for<i=0;i<G->n;i++>visited[i]=_____________;for<i=0;i<G->n;i++>if<!Visited[i]>_________________;}voidDFS<ALGraph*G,inti>{EdgeNode*p;printf<"visitvertex:%c",G->adglist[i],vertex>;visited[i]=TRUE;p=G->adglist[i].firstedge;While<____________>{if<!Visited[p->adjvex]>DFS<G,p->adjvex>;P=___________;}}改錯：以下給出在鏈棧中實現(xiàn)插入操作的算法Push,其類型和算法說明如下〔2處錯誤：typedefstructstacknode{DataTypedata;structstacknode*next;}StackNode;typedefStacknODE*ListStack;VoidPush<LinkStackls,DataTypex>{//將元素x插入鏈棧頭部p=<StackNode*>malloc<sizeof<StackNode>>;p->number=x;p->next=ls;ls=p->data;}以環(huán)形順序隊列的存儲方式實現(xiàn)隊列的基本算法如下〔3處錯誤：#include<iostream.h>#defineMaxLen20typedefcharelemtype;typedefstruct{elemtypedata[MaxLen];intfront,rear;}queue;//front為隊頭指針,rear為隊尾指針。voidinit<queue*sq>//初始化隊列{sq->front=0;sq->rear=0;}intinqueue<queue*sq,elemtypex>//入隊列{if<<sq->rear+1>%MaxLen==sq->front>//隊列上溢出return0;else{sq->rear=<sq->rear+1>%MaxLen;sq->data<sq->rear+1>=x;return1;}}intoutqueue<queue*sq,elemtype*x>//出隊列{if<<sq->front>==sq->rear>//隊列下溢出return0;else{sq->front=<sq->front+1>%MaxLen;*x=sq->data[sq->front+1];return1;}}intempty<queue*sq>//判斷隊列是否為空隊{if<<sq->rear>==sq->front>return1;elsereturn0;}intgethead<queue*sq,elemtype*x>//取隊頭{if<<sq->rear>==sq->front>return0;//隊列下溢出else{*x=sq->data[sq->front>%MaxLen];return1;}}請按要求編寫程序：已知函數(shù)M<x>定義如下：編寫一個非遞歸函數(shù)計算給定x的M<x>值；編寫一個遞歸函數(shù)計算給定x的M<x>值。設(shè)計一種算法用于判定一棵給定的二叉樹是否為完全二叉樹。設(shè)有文件"PERSONEL.TXT"存放職工的數(shù)據(jù),該文件是用寫字板編輯成的,其內(nèi)容包括：職工號、姓名、性別、年齡、職稱、基本工資、津貼、獎金、扣款、實發(fā)工資等〔假設(shè)沒有重復(fù)的職工號。編寫實現(xiàn)如下功能的函數(shù)：在PERSONEL.TXT文件末尾追加職工記錄,其中基本工資、津貼、獎金、扣款由用戶輸入,而實發(fā)工資由計算機(jī)自動計算,即實發(fā)工資=基本工資+津貼+獎金-扣款；根據(jù)用戶輸入的職工號和對應(yīng)的數(shù)據(jù)修改該職工的數(shù)據(jù)；根據(jù)用戶輸入的職工號刪除該職工的數(shù)據(jù)；根據(jù)用戶輸入的工資數(shù),顯示實發(fā)工資數(shù)額大于該工資數(shù)的職工的所有信息,并送往屏幕,其顯示格式為：職工號姓名性別年齡職稱基本工資津貼獎金扣款實發(fā)工資..2004請翻譯成中文:1、randomnumbermethod2、sparsematrix3、replacementselectionsort4、Huffmancodes5、minimalspanningtree6、threadedlinkedlists7、IndexedSequentialAccessMethod8、DynamicSearchTable9、polymorphicdatetype10、garbagecollection11、foldingattheboundaries12、orthogonallist簡答題：1、簡述數(shù)據(jù)結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。2、何謂隊列的上溢現(xiàn)象和假溢現(xiàn)象？解決它們有哪些方法？3、回答下列問題：〔1什么叫Huffman樹？〔2什么叫B樹？〔3什么是圖的生成樹？〔4什么是最小-最大堆？4、簡述無向圖和有向圖有哪幾種存儲結(jié)構(gòu),并說明各種結(jié)構(gòu)在圖中的不同操作〔圖的遍歷,有向圖的拓?fù)渑判虻戎杏惺裁礃拥膬?yōu)越性?5、評價一個算法一般從哪些方面進(jìn)行？和算法執(zhí)行時間相關(guān)的因素有哪些？6、指出對象和類的區(qū)別,使用矩形類說明對象和類的區(qū)別。判斷題,錯誤的請說明理由。1、棧的輸入序列為123...n,輸出序列為a1a2...an,若ai=n<1≤i<n-1>,則ai>ai+1>an?！?、無向圖的鄰接矩陣一定是對稱矩陣,且有向圖的鄰接矩陣一定是非對稱矩陣?！?、哈希表的查找效率主要取決于哈希建表時所選取的哈希函數(shù)和處理沖突的方法?！?、一個稀疏矩陣Am*n采用三元組形式表示。若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換,并把m和n的值互換,則就完成了Am*n的轉(zhuǎn)置運算?！蔡羁眨?、表長為n的順序表中,若在第i個數(shù)據(jù)元素〔1≤i≤n+1之前插入一個數(shù)據(jù)元素,需要向后移動________個數(shù)據(jù)元素；刪除第i個元素需要向前移動______個數(shù)據(jù)元素；在等概率的情況下,插入一個數(shù)據(jù)元素平均需要移動_____個數(shù)據(jù)元素,刪除一個數(shù)據(jù)元素平均需要移動_______個數(shù)據(jù)元素。2、用某種排序方法對線性表{24,88,21,48,15,27,69,35,20},進(jìn)行排序時,元素序列的變化情況如下：〔124,88,21,48,15,27,69,35,20〔315,20,21,24,35,27,48,69,88〔415,20,21,24,27,35,48,69,88則所采用的排序方法是_________?？焖倥判駼、選擇排序C、希爾排序D、歸并排序3、在AOE網(wǎng)中,結(jié)點表示_________,邊表示_________,從源點到匯點路徑上各活動的時間總和最長的路徑稱為____________。4、在堆排序、快速排序和歸并排序中,若從節(jié)省存儲空間考慮,則應(yīng)首先選取_________方法,其次選取__________方法,最后選取_________方法；若只從排序結(jié)果的穩(wěn)定性考慮,則應(yīng)選擇_________方法；若只從平均情況下排序的速度來考慮,則應(yīng)選取__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮,則應(yīng)選取__________方法。5、已知廣義表〔〔a,b,c,<d,e,f>,從A中取出原子e的運算時______。<1>tail<head<A>><2>head<tail<A>><3>head<tail<tail<head<A>>>><4>head<head<tail<tail<A>>>>改錯：1、假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列,并且只設(shè)一個指針指向隊尾元素結(jié)點〔不設(shè)頭指針,類型定義和出對與入隊算法如下?！?處錯誤：2、以順序棧的存儲方式實現(xiàn)棧的基本運算,其算法如下〔4處錯誤：應(yīng)用題：1、已知一個長度為12的表{Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec},〔1試按表中元素的順序依次插入一棵初始為空的二叉排序樹〔字符之間以字典順序比較大小,請畫出對應(yīng)的二叉排序樹,并求出在等概率情況下對此有序表進(jìn)行折半檢索時檢索成功的平均檢索長度。若對表中元素先進(jìn)行排序構(gòu)成有序表,試求在等概率情況下對此有序表進(jìn)行折半檢索時檢索成功的平均檢索長度。按表中元素順序構(gòu)造一棵平衡二叉排序樹,試求在等概率的情況下檢索成功的平均檢索長度。已知一棵二叉樹的中序遍歷序列和按層次遍歷的序列,試編寫算法生成此二叉樹的二叉鏈表。3、已知遞歸函數(shù)F<m><其中DIV為整除>：寫出求F〔m遞歸算法；寫出求F〔m的非遞歸算法。..2005請翻譯成中文：1、VirtualStorageAccessMethod2、directedacyclinegraph3、balancedbinarytree4、havevariablesizerecords5、recursivefunction6、weightedpathlength7、LeastSignificationDigitfirst8、Fibonaccisearch9、immediatesuccessor10、fixed-aggregatedatatype11、randomprobing12、diminishingincrementsort簡答題：1、簡述數(shù)據(jù)的四種存儲方式及各自特點。2、線性表的基本運算包括哪些？簡述線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)的幾種形式。3、名詞術(shù)語解釋：〔1平均查找長度〔AVL〔2抽象數(shù)據(jù)類型〔3廣義表〔4強連通圖與強連通分量4、什么叫AOE網(wǎng)中的源點、匯點和關(guān)鍵路徑,一個正常的AOE網(wǎng)中只有一個源點、匯點和一條關(guān)鍵路徑嗎？5、描述頭指針、頭結(jié)點和首元結(jié)點三個概念的區(qū)別。6、試比較順序文件、索引順序文件和散列文件的存儲代價、檢索、插入及刪除記錄時的優(yōu)點和缺點。判斷題,錯誤的請說明理由。1、子串定位函數(shù)的時間復(fù)雜度在最壞情況下為O<n×m>,因此子串定位函數(shù)沒有實際使用的價值?！?、一般來說,若深度為k的n個結(jié)點的二叉樹只有最小路徑長度,那么從根結(jié)點到第k-1層具有最多的結(jié)點數(shù)為2k-1-1,余下的n-2k-1+1個結(jié)點在第k層的任一位置上?！?、用鄰接矩陣存儲一個圖時,所占用的存儲空間大小只與圖中結(jié)點的個數(shù)有關(guān),而與圖的邊數(shù)無關(guān)?！?、對于滿足折半查找和分塊查找條件的文件而言,無論它存放在任何介質(zhì)上,均能進(jìn)行順序查找,折半查找和分塊查找?！蔡羁眨?、一維數(shù)組的邏輯結(jié)構(gòu)是_________,存儲結(jié)構(gòu)是________；對二維或多維數(shù)組,分為按________和__________兩種不同的存儲方式。2、具有n個結(jié)點的完全二叉樹若層次從上到下、從左到右對其編號〔根結(jié)點為1,則編號最大的分支結(jié)點序號是________。編號最小的分支結(jié)點序號是_______,編號最大的葉子結(jié)點序號是______,編號最小的葉子結(jié)點是_______。3、遍歷圖的過程實質(zhì)上是______。設(shè)圖G有n個頂點和e條邊,則對用鄰接矩陣表示的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時的時間復(fù)雜度為________,而對用鄰接表表示的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時的時間復(fù)雜度為_______；圖的深度或廣度優(yōu)先搜索遍歷時的空間復(fù)雜度均為_________。4、構(gòu)造哈?！睭ash函數(shù)的方法有_________、__________、__________等。5、參照下面的樹,回答各個問題：〔1如果插入結(jié)點33,它的父結(jié)點是________；〔2如果插入結(jié)點64,它的父結(jié)點是________；〔3如果刪除結(jié)點30后,根據(jù)算法將選取_______結(jié)點來替換；〔4如果刪除結(jié)點90后,根據(jù)算法將選取_______結(jié)點來替換；〔5如果刪除了根結(jié)點50,則應(yīng)該用_______結(jié)點來替換。改錯：1、以下算法使用少一個元素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿條件,借以描述出隊、入隊的基本操作〔2處錯誤：2、以下算法通過單鏈表實現(xiàn)了接收用戶輸入的一個字符串,統(tǒng)計其中出現(xiàn)過的所有字符,并按其出現(xiàn)的頻率從高到低的順序排列輸出?！?處錯誤應(yīng)用題：給出一組關(guān)鍵字30,19,26,48,59,11,53,10,分別寫出按下列各種排序方法進(jìn)行排序時的變化過程：〔1歸并排序,每歸并一次書寫一個次序?！?快速排序,每劃分一次書寫一個次序?！?堆排序,先建成一個堆,然后每從堆頂取下一個元素后,將堆調(diào)整一次。已知Ackermann函數(shù)的定義如下：〔1寫出Ack<2,1>的計算過程；〔2寫出計算Ack<m,n>的非遞歸算法。3、已知深度為n的二叉樹采用順序存儲結(jié)構(gòu)存放數(shù)組B[1...2n-1]中,請編寫一個非遞歸算法產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。設(shè)二叉鏈表節(jié)點的結(jié)構(gòu)為：指向左右孩子的指針lchild,rchild及數(shù)據(jù)域data,根節(jié)點的指針為t。..2006簡答題：列舉數(shù)據(jù)邏輯結(jié)構(gòu)上定義的基本運算,簡述度量算法效率的方法及各自特點。根據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間存在的關(guān)系,比較樹形結(jié)構(gòu)與線性結(jié)構(gòu)的異同。名詞術(shù)語解釋：〔1循環(huán)隊列〔2十字鏈表〔3線索二叉樹〔4索引順序文件說明在圖的遍歷中,設(shè)置訪問標(biāo)志數(shù)組的作用。并說明采用圖的深度優(yōu)先搜索模式能否完成拓?fù)渑判虻幕舅悸贰：喪龉１淼脑O(shè)計過程以及哈希函數(shù)的構(gòu)造原則,并列舉常用的構(gòu)造哈希函數(shù)的方法。什么是串的存儲密度？如果串采用塊鏈結(jié)構(gòu)存儲,試分析：〔1一個節(jié)點只存儲一個字符與一個節(jié)點存儲4個字符兩種情況下串的存儲密度〔字鏈指針占用4個字節(jié),一個字符占用1個字節(jié)；〔2上述兩種情況下,哪種存儲結(jié)構(gòu)的空間利用率高。判斷題,錯誤的說明理由。圖G的一棵最小生成樹的代價未必小于G的其他任何一棵生成樹的代價?！捕S數(shù)組A的每個元素是由6個字符組成的串,其行下標(biāo)i=0、1、...、8,列下標(biāo)j=1、2、...、10,若A按行先存儲,元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素A[5,10]的起始地址相同〔設(shè)每個字符占一個字節(jié)?！灿绵徑泳仃嘇表示圖,判定任意兩個結(jié)點Vi和Vj之間是否有長度為m的路徑相連,則只要檢查Am的第i行和第j列的元素是否為0即可。〔已知待排序的n個元素可以分為n/k組,每個組包含k個元素,且任一組內(nèi)的各元素均分別大于前一組內(nèi)的所有元素和小于后一組內(nèi)的所有元素,若采用基于比較的排序,其時間下界應(yīng)為O<nlogk>?！?gt;填空：下列程序的功能是按照右側(cè)的格式輸出6行楊輝三角形。請?zhí)羁諏⒊绦蜓a充完整。具有條邊的無向圖稱為________,簡稱為_________,其中n表示無向圖中頂點的個數(shù),是具有n個頂點無向圖所擁有邊的__________。在AOV網(wǎng)中不可以出現(xiàn)有向環(huán)或回路,這意味著某項活動是________,這樣的工程無法進(jìn)行,對于計算機(jī)中的程序流程圖來說就是__________,也相當(dāng)于操作系統(tǒng)中的__________。比較以下4種排序方法,填寫下表：函數(shù)expand<chars[],chart[]>在將字符串s復(fù)制到字符串t時,將其中的換行符和制表符轉(zhuǎn)換為可見的轉(zhuǎn)義字符,即用"\n"表示換行符,用"\t"表示制表符,填空將程序補充完整。五、應(yīng)用題：1、已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)已存放于數(shù)組BT[1:2h-1]中,請寫算法,產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu),設(shè)二叉鏈表中鏈結(jié)點的構(gòu)造為：lchilddatarchild根結(jié)點所在鏈結(jié)點的指針有BT給出。依據(jù)圖1所示無向圖,分別使用Prim和Kruskal算法,完成如下要求：寫出構(gòu)造該圖的最小生成樹的過程；寫出相應(yīng)的構(gòu)造最小生成樹算法。設(shè)有n個活動需要演講會場,而在同一時間內(nèi)會場只能分配給其中一個活動。如果用E表示活動集合,E={1,2,...,n},每個活動i使用會場有一個起止時間〔si,fi,其中si<fi。如果兩個活動i和j的時間段不相交,則稱活動i與活動j是相容的,前后活動的時間邊界重合不算相交。給定規(guī)模為10的問題實例E如下：{<1,3>,<0,5>,<7,10>,<6,7>,<3,6>,<8,9>,<1,2>,<11,12>,<8,11>,<10,13>}給出以上問題實例的解及求解過程。設(shè)計一個求解"活動方案"的算法,使得在方案中安排的所有活動都是相容的且活動數(shù)目最多。..2007填空：1、設(shè)將整數(shù)1,2,3,4依次進(jìn)棧,可能的出棧序列有〔種；下面四個輸出序列中〔不可能是它的輸出序列。A、1,3,2,4B、2,3,4,1C、3,4,2,1D、4,3,1,2具有m個葉結(jié)點的霍夫曼樹,其分支節(jié)點總數(shù)為〔；對電文"dodoesdoordoors"進(jìn)行霍夫曼編碼,其霍夫曼樹的節(jié)點個數(shù)為〔,該電文的總編碼長度為〔。有n個頂點的有向連通圖最多有〔條邊,最少有〔條邊；其存儲方式可以為〔、〔或〔。設(shè)哈希表中已存在多個記錄〔如下所示。哈希函數(shù)為H<K>=KMOD11,用二次探測再散列處理沖突。請問關(guān)鍵字為94的記錄的存儲地址是〔。0123456789104516396276B-樹只有一個查找的入口指針,指向其〔；B+樹有兩個查找的入口指針,其中一個指向〔,另一個指向〔。下面是中序遍歷的非遞歸算法,請在算法的空缺處填入適當(dāng)內(nèi)容,使之能夠正常工作。算法中設(shè)置了一個順序存儲結(jié)構(gòu)的堆棧STACK[M]來保存遍歷過程中結(jié)點的存儲位置,棧頂指針為top,初始時top=0；同時,算法中還設(shè)置了一個活動指針變量p,用來指向當(dāng)前要訪問的那個結(jié)點,初始時指向二叉樹的根結(jié)點。判斷下面?zhèn)€陳述是否正確,并說明理由。使用三元組表表示稀疏矩陣可以節(jié)省存儲空間。度為2的樹是二叉樹。當(dāng)在函數(shù)定義中作為形參時,chars[]和char*s是等價的。二叉樹葉結(jié)點的數(shù)目只與度為2的結(jié)點的數(shù)目有關(guān)。對于有序鏈表可以采用折半查找。在執(zhí)行某種排序算法的過程中,出現(xiàn)了數(shù)據(jù)元素朝著與其在最終排序結(jié)果中的位置相反方向移動的情況,因此斷定該排序算法是不穩(wěn)定的。簡答題：已知有實現(xiàn)同一功能的兩個算法,其時間復(fù)雜度分別為O<2n>和O〔n10,假設(shè)現(xiàn)實計算機(jī)可連續(xù)運行的時間為107秒〔約100天,又每秒可執(zhí)行基本操作為105次。試問在此條件下,這兩個算法可解決的問題的規(guī)?！布磏的范圍各為多少？哪個算法更合適？試說明理由。已知廣義表L=〔<a,b>,<c,<d,<e>>>,f試?yán)脧V義表取表頭head<L>和取表尾tail〔L的基本運算,將原子c從廣義表L中分解出來,請寫出運算表達(dá)式。請給出下列表達(dá)式的運算結(jié)果：head<tail<head<tail<L>>>>tail<tail<head<L>>>能夠生成下圖所示的二叉排序樹的關(guān)鍵字初始序列有幾種？寫出所有這些序列組合。已知一帶權(quán)連通圖采用鄰接矩陣存儲方法,并且鄰接矩陣采用三元組表來表示,其中第一個三元組〔5,5,16分別表示鄰接矩陣的行數(shù)、列數(shù)與非零元素的個數(shù),從第二個三元組開始,依次按行序為主序的次序分別給出16個非零元素,它們依次為〔1,2,7、〔1,3,6、〔1,4,9、〔2,1,7、〔2,3,8、〔2,4,4、〔2,5,4、〔3,1,6、〔3,2,8、〔3,4,6、〔4,1,9、〔4,2,4、〔4,3,6、〔4,5,2、〔5,2,4、〔5,4,2。請分別畫出該帶權(quán)連通圖的兩棵最小生成樹。將數(shù)組13,5,10,7,27,9,4,15,33,20調(diào)整成極小堆,畫出這個極小堆的邏輯圖和內(nèi)存映像。設(shè)某有序的連續(xù)順序文件的記錄按關(guān)鍵字值從小到大排列,請用文字?jǐn)⑹鲈谠撐募胁捎谜郯氩檎曳椒ù_定一個記錄存在與否的過程。改錯：假設(shè)帶頭結(jié)點的單鏈表中只設(shè)一個指針指向頭節(jié)點,下面算法將實現(xiàn)以下功能：在單鏈表中查找值為value的節(jié)點并刪除。已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表,下面算法將實現(xiàn)以下功能：將二叉樹T中分支節(jié)點按照后序遍歷序列逆序保存在單鏈表L中。應(yīng)用題：已知一個非空的線性鏈表的首結(jié)點地址由list指出,請編寫程序,將鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面去。已知某二叉樹有n個結(jié)點,各結(jié)點存放的值是互不相同的字符,其先序遍歷和中序遍歷的序列分別存放在數(shù)組pre和in中。編寫一個函數(shù)建立該樹的二叉鏈表。假設(shè)已知二叉樹的謙虛便利序列為ABCEFHIDG,中序遍歷序列為ECHFIBDGA,請畫出該二叉樹,并給出它的后序遍歷序列。有一只小袋鼠路過一條河,看到河中一塊石頭上有一個布娃娃,于是它想跳過去把布娃娃撿起來玩?？墒悄菈K石頭離它的距離超出了它所能跳的最遠(yuǎn)距離,因此小松鼠決定把河中其他一些石頭當(dāng)作中繼站,這樣它就可以每次跳比較短的距離〔但需要跳多次,最后到達(dá)布娃娃所在的那塊石頭上。在這樣一串石頭間連續(xù)跳躍,顯然小袋鼠一次能夠跳躍的距離必須至少等于這串石頭間間隔最遠(yuǎn)的距離,這一距離稱為該串石頭間的跳躍距離例如,如果在袋鼠跳躍路徑上各石頭之間的間距分別為2,1,3,3,5和2,則這里的跳躍距離為5。輸入：第一個輸入數(shù)據(jù)是一個整數(shù)n〔2≤n≤200。接下來的n組數(shù)據(jù)是n組二維坐標(biāo)。其中第一組為小袋鼠所在位置的坐標(biāo),第二組為布娃娃所在石頭的坐標(biāo),其余n-2組為可以當(dāng)作中繼站的其他石頭的坐標(biāo)。輸出：袋鼠到達(dá)布娃娃所要跳的最小跳躍距離。按照上述的輸入、輸出要求編寫解決該問題的算法。用下面的輸入實例給出算法的運行過程及結(jié)果。輸入實例：5,〔2,4,〔4,5,〔3,5,〔1,2,〔4,1..2008簡答題：數(shù)據(jù)類型和抽象數(shù)據(jù)類型的含義。算法的特性與算法的時間復(fù)雜度?？焖倥判蚍椒ㄗ詈煤妥顗牡那闆r是什么？簡要分析說明。棧、隊列的共同點與不同點,說明其屬于線形表的原因。方法選擇：一棵二叉排序樹中各結(jié)點不相同,欲得到一個由大到小的結(jié)點值遞減序列,你認(rèn)為采用什么方法能得到要求的結(jié)果？設(shè)有1000個無序元素,僅要求找出前10個最小元素,在下列排序方法中〔歸并排序,基數(shù)排序,快速排序,堆排序,插入排序,哪種方法最好,為什么？三、已知一個循環(huán)單鏈表la,av是可利用棧的頭指針,請用3個賦值語句,完成將整個循環(huán)鏈表釋放的功能?！布磳⒈碚麄€歸還到可用的?？臻g給出求N階hanoi塔的函數(shù)定義如下：寫出執(zhí)行hanoi<3,a,b,c>時遞歸函數(shù)的實在參變量變化,以及move的搬運過程。已知關(guān)鍵字序列為：〔75,33,52,41,12,88,66,27,哈希表長為10,哈希函數(shù)為：H〔k=kMOD7,解決沖突用線性探測再散列法,要求構(gòu)造哈希表,求出等概率下查找成功查找長度。已知一棵二叉樹,中序序列DBCAFGE,后序序列DCBGFEA,構(gòu)造該二叉樹。給定權(quán)值{8,12,4,5,26,16,9},構(gòu)造一個哈夫曼樹,并計算其帶權(quán)路徑長度。編寫程序：建立線形表,〔a1,a2,a3,...,an的單鏈表存儲,并實現(xiàn)其就地逆置為〔an,an-1,...,a2,a1。編寫程序：在中序線索樹中,要找出X結(jié)點的前驅(qū)結(jié)點,請寫出相關(guān)函數(shù)定義。編寫算法：已知有N個結(jié)點的無向圖,采用鄰接表結(jié)構(gòu)存儲,要求對每個連通子圖中一個生成樹中的各條邊逐層刪除。編寫算法：寫出建立二叉樹,二叉鏈表存儲結(jié)構(gòu)的算法。已知二叉樹采用二叉鏈表方式存放