華北計(jì)算技術(shù)研究所專業(yè)課試題及答案

《華北計(jì)算技術(shù)研究所專業(yè)課試題及答案》由會(huì)員分享，可在線閱讀，更多相關(guān)《華北計(jì)算技術(shù)研究所專業(yè)課試題及答案（9頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 華北計(jì)算技術(shù)研究所 專業(yè)課試題 參考答案 一、 填空題 ( 15 分 ) 1. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素 的集合。一般有下列四種基本 結(jié)構(gòu) : 集合 、 線性結(jié)構(gòu) 、 樹(shù)狀結(jié)構(gòu) 和 圖狀結(jié)構(gòu) ( 或網(wǎng)狀結(jié)構(gòu) ) 。 2. 在順序表中插入或刪除一個(gè)元素 , 需要平均移動(dòng) 表中一半 ( 或 n/2 個(gè)) 元素 , 具體移動(dòng)的元素個(gè)數(shù)與 表長(zhǎng)和該元素在表中的位置 有關(guān)。 3. 0 個(gè)字符的串稱

2、為空串 , 它的長(zhǎng)度為 0 。 4. 矩陣壓縮存儲(chǔ)的基本思想是 : 值相同 的多個(gè)元素只分配一個(gè)存儲(chǔ)空間 , 零元素 不分配空間。 5. 深度為 k 的二叉樹(shù)至多有 2k-1 個(gè)結(jié)點(diǎn) , 至少有 k 個(gè)結(jié)點(diǎn)。 6. 圖的深度優(yōu)先搜索遍歷類似于樹(shù)的 先根 遍歷 ; 圖的廣度優(yōu)先搜索遍歷類似于樹(shù)的 按層次 遍歷。 二、 選擇題 ( 20 分 ) 1. 時(shí)間復(fù)雜性最好 , 即執(zhí)行時(shí)間最短的是 :B ( A) O(n) ( B) O(log 2n) ( C) O(nlog 2n) ( D) O

3、(n 2) 2. 具有  6 個(gè)頂點(diǎn)的無(wú)向圖至少有  D 條邊才能確保是一個(gè)連通圖。 ( A) 15  ( B) 7  ( C) 6  ( D) 5 3. 在所有排序方法中  ,  關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是  : D ( A)  希爾排序  ( B)  起泡排序  ( C)  插入排序  ( D) 

4、選擇排序 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 4. 若用一個(gè)大小為  6 的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列  ,  且當(dāng)前  rear  和 front  的值分別為  0 和  3,  當(dāng) 從隊(duì)列中刪除一個(gè)元素  , 再加入兩個(gè)元素后  , rear  和  front  的值分別為  :  C 。 （ A ）  1 和 5  ( B) 2 

5、 和 4 ( C) 4  和 2 ( D) 5  和  1 5. 設(shè)棧的長(zhǎng)度為 3, 入棧序列為 ( A) A, B, C, D, E, F ( C) C, B, A, F, E, D  A、 B 、 C、 D、 E 、 F, ( B) B, A, D, C, F, E ( D) D, C, B, A, F, E  不可能產(chǎn)生的出棧序列是  :  D 。 三、 判斷題。 ( 10 分) 請(qǐng)判斷下列說(shuō)法的對(duì)錯(cuò)。

6、 1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 錯(cuò) 2. 串的三種存儲(chǔ)表示方法為定長(zhǎng)順序存儲(chǔ)表示、 堆分配存儲(chǔ)表示和塊鏈存儲(chǔ)表示。 對(duì) 3. 一個(gè)稀疏矩陣的轉(zhuǎn)置矩陣依然是稀疏矩陣。 對(duì) 4. 樹(shù)狀結(jié)構(gòu)中 , 度為 0 的結(jié)點(diǎn)稱為樹(shù)根。 錯(cuò) 5. 完全二叉樹(shù)不一定是滿二叉樹(shù) , 但滿二叉樹(shù)一定是完全二叉樹(shù)。 對(duì) 四、 根據(jù)下列要求分別編寫(xiě)算法。 ( 20 分) 1. 設(shè)計(jì)算法 , 判斷一個(gè)算術(shù)表示式的圓括號(hào)是否正確配對(duì)。參考答案 : #include

7、h> #include ”stack.h ” Int PairBracket(char *S) { // 檢查表示式中括號(hào)是否配對(duì) int i; 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 SeqStack T;// 定義一個(gè)棧 InitStack (&T); for(i=0;i

8、 } Return !EmptyStack(&T); // 由?？辗穹祷卣_配對(duì)與否 } 2. 已知一棵完全二叉樹(shù)存于順序表 sa 中, sa.elem[sa.last] 中存放各結(jié)點(diǎn)的數(shù)據(jù)元素。編 寫(xiě)算法由此順序存儲(chǔ)結(jié)構(gòu)建立該二叉樹(shù)的二叉鏈表。 參考答案 : Status CreateBitree_SqList(Bitree &T,SpList sa) {  // 根據(jù)順序存儲(chǔ)結(jié)構(gòu)建立二叉鏈表 Bitree ptr[sa.last+1];//  該數(shù)組存儲(chǔ)與  sa 中各

9、結(jié)點(diǎn)對(duì)應(yīng)的樹(shù)指針 if(!sa.last) { T=NULL; return; } ptr[1]=(BTNode*)malloc(sizeof(BTNode)); ptr[1]->data=sa.elem[1]; T=ptr[1]; for(i=2;i<=sa.last;i++) { if(!sa.elem[i] return ERROR; ptr[i]=(BTNode*)malloc(sizeof(BTNode)); 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，

10、請(qǐng)聯(lián)系改正或者刪除。 ptr[i]->data=sa.elem[i]; j=i/2; if(i-j*2) ptr[j]->rchild=ptr[i]; //I 是 j 的右孩子 else ptr[j]->lchild=ptr[i]; //I 是 j 的左孩子 } return OK; } 五、 回答問(wèn)題。 ( 20 分) 1. 設(shè)有上三角矩陣 (a ij ) nxn, 將其上三角元素逐行存于數(shù)組 B[m] 中( m充分大 ) , 使得 B[k]=a ij 且 k=f 1

11、 (i)+f 2 (j)+c 。試推導(dǎo)出函數(shù) f , f 2 和常數(shù) c( 要求 f 和 f 中不含常數(shù)項(xiàng) ) 。 1 1 2 參考答案 : k ni ( n j ) i (i 1) j ) 1, (i 2 則得 : f1 (i ) (n 1 )i 1 i 2 f 2 (

12、j ) j 2 2 c (n 1) 2. 寫(xiě)出下圖中所示的二叉樹(shù)的先序序列、 中序序列和后序序列。 1 2 3 4 5 6 7 參考答案 :  8 9 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 前序 : 中序 : 后序 : 六、 下圖是一

13、個(gè)有向圖 , 其中每條弧段上的數(shù)字表示該弧段的權(quán)值。利用 Dijkstra 算法求圖中從頂點(diǎn) a 到其它各頂點(diǎn)間的最短路徑 , 寫(xiě)出執(zhí)行算法過(guò)程中各步的狀態(tài)。 ( 15 分) b 4 15 6 e 8 9 a 2 c g 4 10 12 5 f d 3 參考答案 : 終點(diǎn) c d e f g S b Dis

14、t 15 2 12 {a,c} K=1 (a,c) (a,d) (a,b) 15 12 10 6 {a,c,f} K=2 (a,d) (a,c,e) (a,c,f) (a,b) 15 11 10 16 {a,c,f,e} K=3 (a,c,f,d) (a,c,e) (a,c,f,g) (a,b) 15 11 16 {a,c,f,e,d } K=4 (

15、a,c,f,d) (a,c,f,g) (a,b) 15 14 {a,c,f,e,d,g} K=5 (a,c,f,d,g) (a,b) 15 {a,c,f,e,d,g,b} K=6 (a,b) 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 故 : a 到各點(diǎn)最短路徑分別為 : b  c  d  e 

16、 f  g 15  2  11  10  6  14 七、 假設(shè)按下述遞歸方法進(jìn)行順序表的查找 : 若表長(zhǎng) <=10, 則進(jìn)行順序查找 , 否則進(jìn)行折半查找。試畫(huà)出對(duì)表長(zhǎng) n=50 的順序表進(jìn)行上述查找時(shí) , 描述該查找的判定樹(shù) , 并求出 在等概率情況下查找成功的平均查找長(zhǎng)度。 ( 20 分 ) 參考答案 : 25 12 38 6 18 31 44 1 7 13 19

17、 26 32 39 45 2 8 14 20 27 33 40 46 ? ? ? ? ? ? ? ? 5 11 17 23 30 36 43 49 24 37 其等概率查找時(shí)查找成功的平均查找長(zhǎng)度為 : ASLsucc 1 (1 1 2 2 3 4 (4 5 6 7 8) 8 9 3) 5.68 50 八、 將下列 C++程序的類定義和主函數(shù)分離 , 改成多文件結(jié)構(gòu)。主函數(shù)使用類的方式采

18、取包 含類定義頭文件的方法。并寫(xiě)出運(yùn)行結(jié)果。 ( 15 分 ) #include class Cat 資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請(qǐng)聯(lián)系改正或者刪除。 { public: int GetAge( ); void SetAge(int age); void Meow( ); // 喵喵叫 protected: int itsAge; }; int Cat::GetAge( ) { returen itsAge; } void Cat::SetAge(int age) { itsAge=age; } void Cat::Meow( ) { cout<< ”Meow.\n”; } void main( ) { Cat frisky; Frisky.SetAge(5); Frisky.Meow( );