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