[語言類考試復(fù)習(xí)資料大全]中級軟件設(shè)計師下午試題分類模擬15

1、書山有路勤為徑，學(xué)海無涯苦作舟。祝愿天下莘莘學(xué)子：學(xué)業(yè)有成，金榜題名！語言類考試復(fù)習(xí)資料大全中級軟件設(shè)計師下午試題分類模擬15中級軟件設(shè)計師下午試題分類模擬15試題一閱讀下列說明、圖和C代碼，填入橫線處的字句。問題:1. 說明1 B樹是一種多又平衡查找樹。一棵m階的B樹，或為空樹，或為滿足下列特性的m叉樹。 (1)樹中每個節(jié)點至多有m棵子樹。 (2)若根節(jié)點不是葉子節(jié)點，則它至少有兩棵子樹。 (3)除根之外的所有非葉子節(jié)點至少有m/2棵子樹。 (4)所有的非葉子節(jié)點中包含下列數(shù)據(jù)信息：(n，A0，K1，A1，K2，A2，Kn，An)。其中，Ki(i=1，2，n)為關(guān)鍵字，且KiKi+1(i=1

2、，2，n-1)，Ai(i=0，1，n)為指向樹根節(jié)點的指針，且指針Ai-1所指子樹中所有節(jié)點的關(guān)鍵字均小于ki，Ai+1所指子樹中所有節(jié)點的關(guān)鍵字均大于ki；n為節(jié)點中關(guān)鍵字的數(shù)目。 (5)所有的葉子節(jié)點都出現(xiàn)在同一層次上，并且不帶信息(可以看作是外部節(jié)點或查找失敗的節(jié)點，實際上這些節(jié)點不存在，指向這些節(jié)點的指針為空)。 例如，一棵4階B樹如圖1所示(節(jié)點中關(guān)鍵字的數(shù)目省略)。 B樹的階M、bool類型、關(guān)鍵字類型及B樹節(jié)點的定義如下： #define M 4 /*B樹的階*/ typedef enum FALSE=0, TRUE=1 bool; typedef int ElemKeyType

3、; typedef Struct BTreeNode int numkeys; /*節(jié)點中關(guān)鍵字的數(shù)目*/ struct BTreeNode *parent; /*指向父節(jié)點的指針，樹根的父節(jié)點指針為空*/ struct BTreeNode *AM; /*指向子樹節(jié)點的指針數(shù)組*/ ElemgeyType KM; /*存儲關(guān)鍵字的數(shù)組，K0閑置不用*/ BTreeNode; 函數(shù)SearchBtree(BTreeNode* root, ElemKeyType akey, BTreeNode *ptr)的功能是：在給定的一棵M階B樹中查找關(guān)鍵字akey所在節(jié)點，若找到則返回TRUE，否則返回FA

4、LSE。其中，root是指向該M階B樹根節(jié)點的指針，參數(shù)ptr返回akey所在節(jié)點的指針，若akey不在該B樹中，則ptr返回查找失敗時空指針所在節(jié)點的指針。例如，在圖1所示的4階B樹中查找關(guān)鍵字25時，ptr返回指向節(jié)點e的指針。 注：在節(jié)點中查找關(guān)鍵字akey時采用二分法。 函數(shù)SearchBtree的代碼如下： bool SearchBtree (BTreeNode* root, ElemKeyType akey, BTreeNode *ptr) int lw, hi, mid; BTreeNode *P=root; *ptr=NULL; while(p) lw=1; hi=_; whi

5、le (lw=hi) mid=(lw+hi)/2; if (p Kmid = akey) *ptr=P; return TRUE; else if _ hi = mid - 1; else lw=mid+1; *ptr=p; p=_; return FALSE; 答案:pnumkeys或其等價形式 pKmidakey或其等價形式 pAhi或pAlw-1或其等價形式 問題:2. 說明2 在M階B樹中插入一個關(guān)鍵字時，首先在最接近外部節(jié)點的某個非葉子節(jié)點中增加一個關(guān)鍵字，若該節(jié)點中關(guān)鍵字的個數(shù)不超過M-1，則完成插入；否則，要進行節(jié)點的“分裂”處理。所謂“分裂”，就是把節(jié)點中處于中間位置上的關(guān)鍵字

6、取出來并插入其父節(jié)點中，然后以該關(guān)鍵字為分界線，把原節(jié)點分成兩個節(jié)點?！胺至选边^程可能會一直持續(xù)到樹根，若樹根節(jié)點也需要分裂，則整棵樹的高度增1。 例如，在圖1所示的B樹中插入關(guān)鍵字25時，需將其插入節(jié)點e中。由于e中已經(jīng)有3個關(guān)鍵字，因此將關(guān)鍵字24插入節(jié)點e的父節(jié)點b中，并以24為分界線將節(jié)點e分裂為e1和e2兩個節(jié)點，結(jié)果如圖2所示。 函數(shù)Isgrowing(BTreeNode* root, ElemKeyType akey)的功能是：判斷在給定的M階B樹中插入關(guān)鍵字akey后，該B樹的高度是否增加，若增加則返回TRUE，否則返回FALSE。其中，root是指向該M階B樹根節(jié)點的指針。

7、在函數(shù)Isgrowing中，首先調(diào)用函數(shù)SearchBtree查找關(guān)鍵字akey是否在給定的M階B樹中，若在則返回FALSE(表明無需插入關(guān)鍵字akey，樹的高度不會增加)；否則，通過判斷節(jié)點中關(guān)鍵字的數(shù)目考查插入關(guān)鍵字akey后該B樹的高度是否增加。 函數(shù)lsgrowing的代碼如下： bool Isgrowing(BTreeNode* root, ElemKeyType akey) BTreeNode *t, *f; if (!SearchBtree (_) t=f; while (_) t = t parent; if (!t) return TRUE; return FALSE; 答案

8、:root，akey， struct BucketNode *Link; BUCKET; BUCKET Bucket P; /*基桶空間定義*/ 函數(shù)InsertToHashTable代碼如下： int InsertToHashTable(int NewElemKey) /*將元素NewElemKey插入散列桶中，若插入成功則返回0，否則返回-1*/ /*設(shè)插入第一個元素前基桶的所有KeyData、Link域已分別初始化為NULLKEY、NULL*/ int Index; /*基桶編號*/ int i, k; BUCKET *s, *front, *t; _; for (i = 0; i IT

9、EMS; i+) /*在基桶查找空閑單元，若找到則將元素存入*/ if (BucketIndex. KeyDatai = NULLKEY) BucketIndex. KeyData i = NewElemKey; break; if (_) return 0; /*若基桶已滿，則在溢出桶中查找空閑單元，若找不到則申請新的溢出桶*/ _； t = Bucket Index. Link; if (t != NULL) /*有溢出桶*/ while (t !=NULL) for (k=0; kITEMS; k+) if (tKeyData k = NULLKEY) /*在溢出桶鏈表中找到空閑單元*/

10、 tKeyData k = NewElemKey; break; /*if*/ front=t; if (_)t = t; Link; else break; /*while*/ /*if*/ if (_) /*申請新溢出桶并將元素存入*/ s = (BUCKET *) malloc (sizeof (BUCKET); if (!s) return -1; sLink = NULL; for (k=0; kITEMS; k+) sKeyData k = NULLKEY; SKeyData0=NewElemKey; _; /*if*/ return 0; /*InsertToHashTable*

11、/ 答案:Index=NewElemKey%P或Index=Hash(NewElemKey) iITEMS front= struct DocExplorer func update; /*DocExplorer結(jié)構(gòu)采用的更新函數(shù)*/ /*其他的結(jié)構(gòu)字段省略*/ ; Struct OfficeDoc _ myObsOBS_MAXNUM; /*存儲所有與OfficeDoc相關(guān)聯(lián)的DocExplorer結(jié)構(gòu)指針*/ int index; /*與OfficeDoc結(jié)構(gòu)變量相關(guān)聯(lián)的DocExplorer結(jié)構(gòu)變量的個數(shù)*/ ; Void attach (struct OfficeDoc *doc, st

12、ruct DocExplorer *ob) /*關(guān)聯(lián)Obersver結(jié)構(gòu)ob與OfficeDoc結(jié)構(gòu)doc*/ int loop = 0; if (docindex =OBS_MAXNUM | ob = NULL) return; for (loop=0; loopdocindex; loop+) if (docmyObs loop = ob) return; docmyObs docindex = ob; docindex+; void detach (struct OfficeDoc *doc, struct DocExplorer *b) /*解除doc結(jié)構(gòu)與ob結(jié)構(gòu)間的關(guān)系*/ int

13、 loop; if (ob = NULL) return; for (loop = 0; loop doc index; loop+) if (docmyObs loop = ob) if (loop =docindex-2) docmyObs loop = docmyObs _; docmyObsdocindex-1 = NULL; docindex-一j break; void update1 (struct OfficeDoc *doc, struct DocExplorer *ob) /*更新ob結(jié)構(gòu)的值，更新代碼省略*/ void update2 (struct OfficeDoc

14、*doc, struct DocExplorer *ob) /*更新ob結(jié)構(gòu)的值，更新代碼省略*/ void notifyObs (struct OfficeDoc *doc) /*當doc結(jié)構(gòu)的值發(fā)生變化時，通知與之關(guān)聯(lián)的所有DocExplorer結(jié)構(gòu)變量*/ int loop; for (loop = 0; loop docindex; loop+) (docmyObs loop)update(_); void main() struct OfficeDoc doc; /*定義一個OfficeDoc變量*/ struct DocExplorer explorer1, explorer2;

15、/*定義兩個DocExplorer變量*/ /*初始化與OfficeDoc變量相關(guān)的DocExplorer變量個數(shù)為0*/ doc. index=0; explorer1. update = update1; /*設(shè)置explorer1 變量的更新函數(shù)*/ explorer2. update = update2; /*設(shè)置explorer2 變量的更新函數(shù)*/ attach ( /*關(guān)聯(lián)explorer1與doc對象*/ attach ( /*關(guān)聯(lián)explorer2與doc對象*/ /*其他代碼省略*/ _; /*通知與OfficeDoc相關(guān)的所有DocExploer變量*/ return;

16、答案:*func struct DocExplorer* docindex-1 doc，docmyObsloop notifyObs( int flgN; sum (int i, int total, int sigma, int rear, int d, int t) int j; /* 考慮元素di被包含在新的部分元素序列中的可能性 */ if (sigma + di =total) /*如果di與當前序列的和不超過total*/ flgi=1；/* di被考慮在部分元素序列中 */ if (_=total) /* 輸出解 */ for (j=0; flgj = 0; j+) printf

17、 (%4d = %d, total，dj); for (j+; j =i; j+) if (flgj) printf (+%d, dj); printf(); else if(i n-1 rear+sigma =total) /* 并且繼續(xù)考慮后面的元素有可能找到解答時 */ sum (i+1, total, _, rear-di, d, n); _; /* 考慮元素di不被包含在新的部分元素序列中的可能性*/ if (i n-1 rear-di+tigma =total) sum(i+1, total, _, rear-di, d, n); main() int i, j, n, total, s, d; printf (輸入 total! /n); sc