科學(xué)院數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)1999歷年考研真題2010-筆記加

一、選擇題(2021.2.3.若度為m的樹中,其葉結(jié)點(diǎn)個(gè)數(shù)為n,則非葉結(jié)點(diǎn)的個(gè)數(shù) 最優(yōu)二叉樹(樹)、最優(yōu)查找樹均為平均查找路徑長(zhǎng)度∑wh最小的樹,其中對(duì)最優(yōu)二叉樹,n表示 ,對(duì)最優(yōu)查找樹,n表示 ;構(gòu)造這兩種樹均 1.結(jié)點(diǎn)數(shù)2.葉結(jié)點(diǎn)數(shù)3.非葉結(jié)點(diǎn)數(shù)4.度為二的結(jié)點(diǎn)數(shù)5.n各關(guān)鍵字的有序表6.需要對(duì)n個(gè)關(guān)鍵字進(jìn)行動(dòng)態(tài)7.需要n個(gè)關(guān)鍵字的查找概率表8.不許要任何前提 ;對(duì)于前序遍歷與后序遍歷結(jié)果相 1.2.3.4.根接點(diǎn)無右孩子的二叉樹5.所有結(jié)點(diǎn)只有左子樹的二叉樹6所有結(jié)點(diǎn)只有右子樹的二叉樹m路B+樹是一 ,其結(jié)點(diǎn)中關(guān)鍵字最多 個(gè),最少 個(gè)1.m2.m3.m路trie4.m5.m-16.m7m+18.[m/2]-二、填空題(10分,每空一分 四種 ,他 深度為k(設(shè)根的層數(shù)為1)的完全二叉樹至少有個(gè)結(jié)點(diǎn),至多有 個(gè)結(jié)點(diǎn),k和結(jié)點(diǎn)數(shù)n之間的關(guān)系是 三、問答題(10分,5分的入度為0，其他頂點(diǎn)入度為一的有向圖卻不一定是一棵有向樹。請(qǐng)舉例說明之。若有nK(n+1)明你如何在log2(n)的時(shí)間內(nèi)將其重新調(diào)整為一個(gè)堆？四、閱讀下述程序,程序的輸出。(10分voidg(int**);intline[100],i;int*p=line;}}g(int**p){(**p)++;}五、編程題。(共50分,要求寫出設(shè)計(jì)思想和程序注解head,key域,試設(shè)計(jì)算法將此鏈表的記錄按照key遞增的次序進(jìn)行就地排序.(10分)],b中最長(zhǎng)平臺(tái)的長(zhǎng)度.(20分自由樹(即無環(huán)連通圖T=(V,E)的直徑是樹中所有點(diǎn)對(duì)間最短路徑長(zhǎng)度的最大值,即T的MAXd(u,v)d(u,v)uv的最短路徑長(zhǎng)度(路徑長(zhǎng)度為路所含的邊數(shù)).T的直徑,并分析算法的時(shí)間復(fù)雜度(時(shí)間復(fù)雜度越小得分越高)(20分)九、(14分)設(shè)正在處理器上執(zhí)行的一個(gè)進(jìn)程的頁表如下.頁表的虛頁號(hào)和物理塊號(hào)是十進(jìn)制數(shù),起始頁號(hào)(塊號(hào))均為0.所有的地址均是器字節(jié)地址,頁的大小為1024字節(jié).B.下列虛地址對(duì)應(yīng)與什么物理地址:(1)54