《華北計算技術(shù)研究所專業(yè)課試題及答案》由會員分享，可在線閱讀，更多相關(guān)《華北計算技術(shù)研究所專業(yè)課試題及答案（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、資料內(nèi)容僅供您學習參考，如有不當或者侵權(quán)，請聯(lián)系改正或者刪除。
華北計算技術(shù)研究所 專業(yè)課試題
參考答案
一、 填空題 ( 15 分 )
1. 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素 的集合。一般有下列四種基本
結(jié)構(gòu) : 集合 、 線性結(jié)構(gòu) 、 樹狀結(jié)構(gòu) 和 圖狀結(jié)構(gòu) ( 或網(wǎng)狀結(jié)構(gòu) ) 。
2. 在順序表中插入或刪除一個元素 , 需要平均移動 表中一半 ( 或 n/2 個) 元素 , 具體移動的元素個數(shù)與 表長和該元素在表中的位置 有關(guān)。
3. 0 個字符的串稱
2、為空串 , 它的長度為 0 。
4. 矩陣壓縮存儲的基本思想是 : 值相同 的多個元素只分配一個存儲空間 , 零元素
不分配空間。
5. 深度為 k 的二叉樹至多有 2k-1 個結(jié)點 , 至少有 k 個結(jié)點。
6. 圖的深度優(yōu)先搜索遍歷類似于樹的 先根 遍歷 ; 圖的廣度優(yōu)先搜索遍歷類似于樹的 按層次 遍歷。
二、 選擇題 ( 20 分 )
1. 時間復雜性最好 , 即執(zhí)行時間最短的是 :B
( A) O(n) ( B) O(log 2n) ( C) O(nlog 2n) ( D) O
3、(n 2)
2. 具有
6 個頂點的無向圖至少有
D 條邊才能確保是一個連通圖。
( A) 15
( B) 7
( C) 6
( D) 5
3. 在所有排序方法中
,
關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是
: D
( A)
希爾排序
( B)
起泡排序
( C)
插入排序
( D)
4、選擇排序
資料內(nèi)容僅供您學習參考，如有不當或者侵權(quán)，請聯(lián)系改正或者刪除。
4. 若用一個大小為
6 的數(shù)組來實現(xiàn)循環(huán)隊列
,
且當前
rear
和 front
的值分別為
0 和
3,
當
從隊列中刪除一個元素
, 再加入兩個元素后
, rear
和
front
的值分別為
:
C 。
（ A ）
1 和 5
( B) 2
5、
和 4 ( C) 4
和 2 ( D) 5
和
1
5. 設(shè)棧的長度為 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 分)
請判斷下列說法的對錯。
6、
1. 數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 錯
2. 串的三種存儲表示方法為定長順序存儲表示、 堆分配存儲表示和塊鏈存儲表示。 對
3. 一個稀疏矩陣的轉(zhuǎn)置矩陣依然是稀疏矩陣。 對
4. 樹狀結(jié)構(gòu)中 , 度為 0 的結(jié)點稱為樹根。 錯
5. 完全二叉樹不一定是滿二叉樹 , 但滿二叉樹一定是完全二叉樹。 對
四、 根據(jù)下列要求分別編寫算法。 ( 20 分)
1. 設(shè)計算法 , 判斷一個算術(shù)表示式的圓括號是否正確配對。參考答案 :
#include
7、h> #include ”stack.h ”
Int PairBracket(char *S)
{
// 檢查表示式中括號是否配對
int i;
資料內(nèi)容僅供您學習參考，如有不當或者侵權(quán)，請聯(lián)系改正或者刪除。
SeqStack T;// 定義一個棧
InitStack (&T);
for(i=0;i
8、
}
Return !EmptyStack(&T); // 由?？辗穹祷卣_配對與否
}
2. 已知一棵完全二叉樹存于順序表 sa 中, sa.elem[sa.last] 中存放各結(jié)點的數(shù)據(jù)元素。編
寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。
參考答案 :
Status CreateBitree_SqList(Bitree &T,SpList sa)
{
// 根據(jù)順序存儲結(jié)構(gòu)建立二叉鏈表
Bitree ptr[sa.last+1];//
該數(shù)組存儲與
sa 中各
9、結(jié)點對應(yīng)的樹指針
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)容僅供您學習參考，如有不當或者侵權(quán)，
10、請聯(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;
}
五、 回答問題。 ( 20 分)
1. 設(shè)有上三角矩陣 (a ij ) nxn, 將其上三角元素逐行存于數(shù)組 B[m] 中( m充分大 ) , 使得 B[k]=a ij
且 k=f
1
11、
(i)+f
2
(j)+c 。試推導出函數(shù) f , f
2
和常數(shù) c(
要求 f
和 f
中不含常數(shù)項 ) 。
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. 寫出下圖中所示的二叉樹的先序序列、 中序序列和后序序列。
1
2 3
4 5 6
7
參考答案 :
8 9
資料內(nèi)容僅供您學習參考，如有不當或者侵權(quán)，請聯(lián)系改正或者刪除。
前序 :
中序 :
后序 :
六、 下圖是一
13、個有向圖 , 其中每條弧段上的數(shù)字表示該弧段的權(quán)值。利用 Dijkstra 算法求圖中從頂點 a 到其它各頂點間的最短路徑 , 寫出執(zhí)行算法過程中各步的狀態(tài)。 ( 15 分)
b
4
15
6
e
8
9
a
2
c
g
4
10
12
5
f
d
3
參考答案 :
終點
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)容僅供您學習參考，如有不當或者侵權(quán)，請聯(lián)系改正或者刪除。
故 :
a 到各點最短路徑分別為 :
b
c
d
e
16、
f
g
15
2
11
10
6
14
七、 假設(shè)按下述遞歸方法進行順序表的查找 : 若表長 <=10, 則進行順序查找 , 否則進行折半查找。試畫出對表長 n=50 的順序表進行上述查找時 , 描述該查找的判定樹 , 并求出
在等概率情況下查找成功的平均查找長度。 ( 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
其等概率查找時查找成功的平均查找長度為
:
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、取包
含類定義頭文件的方法。并寫出運行結(jié)果。 ( 15 分 )
#include
class Cat
資料內(nèi)容僅供您學習參考，如有不當或者侵權(quán)，請聯(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( );
華北計算技術(shù)研究所專業(yè)課試題及答案
