




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
一、計算(每題參考分值5分)
1、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。
0015co22QOco
coco118QO00
co3cococo28
22coco8QOco
00coQOcoCO00
15cococococo
1311
123
正確答案:
2、以{24Z68,2Z55,23,U,10,19,20,79,84},構(gòu)造hash表并求平均查找
長度。hash表長度為17,hash(key)=key%17o
用線性探測法解決沖突。
正確答案:
02578910111213141516
68119205523271110791484
ASL=(l*10+3*2)/12=16/12
3、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷
序列是:生司%寫出后序遍歷序列。
正確答案:
后序遍歷序列:cdbgfea
4、設(shè)通信用8個字符abcdefgh,各字符使用的相對頻率分別
為25,36,2,5,8,10,14,50,構(gòu)造哈夫曼樹,設(shè)計哈夫曼編碼,求該樹的帶樹路
徑長度WPLO
正確答案:
OTOW
IOOI:9
IOOOI:P
OOOOI:)
io:q
oo:e
g:1011
h:ll
WPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5
=385
5、對{49,38,65,97,76,13,27,49)進行直接插入排序,寫出每一趟排序
過程
正確答案:
第1趟i=2(3849)659776132749
第2趟(384965)9776132749
第3趟(38496597)76132749
第4趟(3849657697)132749
第5趟i=6(133849657697)2749
第6趟i=7(13273849657697)49
第7趟(1327384949657697
6、用kruskal方法求下圖的最小生成樹
正確答案:
?
?
o
7、對對{278,109,63,930,589r184,505,269,8r83)用基數(shù)排序方法進行排
序,寫出每一趟排序過程
正確答案:
第一趟排序后(個位有序):
930,063,083,184,505,278,008,109,589,269
第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):
505,008,109,930,063,269,278,083,184,589
第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):
008,063,083,109,184,269,278,505,589,930
8、以{45,53,12,37,24,100,3,61,90,78}
構(gòu)造二叉排序樹。
正確答案:
二、論述(每題參考分值5分)
9、設(shè)計算法求二叉樹的高度
正確答案:
intdepth(BTreeT)
{intl,r;
if(T==NULL)
return0;
else{
1=depth(T->lchild);
r=depth(T->rchild);
return(l>r)?(l+l):(r+l)
)
)
10、已知線性表中的元素按值遞增排列,并以單鏈表作存儲結(jié)構(gòu)。寫一高效算
法,刪除表中所有值大于min且小于max的元翦若表中存在這樣的元素X
正確答案:
voiddel_l(node*h,intmin,intmax){
//h:帶頭結(jié)點的單鏈表的頭指針
q=h;p=h->next;〃初值
while(p!=NULL&&p->data<=min)
{q=p;p=p->next;}
//p指向其值〉min的結(jié)點,q是p的前趨
while(p!=NULL&&p->data<max)
{u=p;p=p->next;deleteu;}
//刪除所有的其值〉min并且vmax的結(jié)點p(u)
q->next=p;
}//del,l
三、單選(每題參考分值2.5分)
11、深度為k的完全二叉樹中最少有()個結(jié)點。
A.
2匕1-1
2匕1
c.
21+1
D.
2k-l
答案:【B】
12、設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后,輸出序列中的第一個元素是n,則輸出
序列中的第i個輸出元素是()。
A.
n-i
B.
n-1-i
C.
n+l-i
D.
不能確定
答案:【O
13、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)=key%p,貝Up最好選擇(
A.
小于等于m的最大奇數(shù)
B.
小于等于m的最大素數(shù)
C.
小于等于m的最大偶數(shù)
D.
小于等于m的最大合數(shù)
答案:【B】
14、某二叉樹的后序遍歷序列為DABEC、中序遍歷序列為DEBAC,則前序遍歷為
A.
ACBED
B.
DECAB
C.
DEABC
D.
CEDBA
答案:【D】
15、下列排序算法中時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響,恒為0(己)的是
A.
堆排序
B.
冒泡排序
C.
直接叫排序
D.
快速排序
答案:【C
16、利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。
A.
O(n)
B.
O(nlog2n)
C.
0(n2)
D.
O(log2n)
答案:【C】
17、圖G的某一最小生成樹的代價一定小于其他生成樹的代價
A.
一定是
B.
肯定不是
C.
不一定是
D.
都不對
答案:【O
18、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進行順序編號,則編號為
i結(jié)點的左孩子結(jié)點的編號為()。
A.
2i+l
B.
2i
C.
i/2
D.
2i-l
答案:【B】
19、兩個字符串相等的充要條件是()。
A.
兩個字符串的長度相等
B.
兩個字符串中對應(yīng)位置上的字符相等
C.
同時具備(A)和(B)兩個條件
D.
以上答案都不對
答案:
20、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏5臈m?,則刪除棧頂元素的操作序列為()c
A.
top=top+l;
B.
top=top-l;
C.
top->next=top;
D.
top=top->next;
答案:【D】
21、設(shè)某無向圖有n個頂點,則該無向圖的鄰接表中有()個表頭結(jié)點。
A.
2n
B.
n
C.
n/2
D.
n(n-l)
答案:【B】
22、JII頁序查找不論在J順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為(
A.
O(n)
B.
0(帝)
C.
0(nV2)
D.
O(log2n)
答案:【A】
23、設(shè)III頁序線性表中有n個數(shù)據(jù)元素,則刪除表中第i個元素需要移動()個元素。
A.
n-i
B.
n+l-i
C.
n-l-i
D.
i
答案:【A】
24、算法必須具備輸入、輸出和
A.
計算方法
B.
排序方法
C.
解決問題的有限運算步驟
D.
程序設(shè)計方法
答案:【C
25、()是線性表。
A.
(123,...)
B.
{abode}
C.
(135,7)
D.
{'A';C}
答案:【。
26、下列各種排序算法中平均時間復(fù)雜度為0(M)是()。
A.
快速排序
B.
堆排序
C.
歸并排序
D.
冒泡排序
答案:【D】
27、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。
A.
0(n)
B.
O(log2n)
C.
O(nlog2n)
D.
0(M)
答案:【B】
28、設(shè)某哈夫昌樹中有199個結(jié)點,則該哈夫晝樹中有()個葉子結(jié)點C
A.
99
B.
100
C.
101
D.
102
答案:【B】
29、設(shè)二叉排序樹上有n個結(jié)點廁在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()。
A.
O(n)
B.
O(M)
C.
O(nlog2n)
D.
O(log2n)
答案:【D】
30、設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點
A的后面插入結(jié)點X的操作序列為()。
A.
p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.
s->left=p;s->right=p->right;p->right=s;p->right->left=s;
C.
p->right=s;p->right->left=s;s->left=p;s->right=p->right;
D.
s->left=p;s->right=p->right;p->right->left=s;p->right=s;
答案:【A】
31、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點i的入度為()。
A.
第i行非0元素的個數(shù)之和
B.
第i列非0元素的個數(shù)之和
C.
第i彳亍0元素的個數(shù)之和
D.
第i列0元素的個數(shù)之和
答案:【B】
32、設(shè)輸入序列為L2.3、4、5、6,則通i寸棧的作用后可以得到的輸出序列為(]
A.
5,3,4,6,1,2
B.
3,256,4,1
C.
3,1,254,6
D.
1,5,4,6,2,3
答案:【B】
33、設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點,則其判空條件是()。
A.
head==O
B.
head->next==O
C.
head->next==head
D.
head!=O
答案:【A】
34、設(shè)順序表的長度為n,則JI質(zhì)序杳找的平均比較次數(shù)為()。
A.
n
B.
n/2
C.
(n+l)/2
D.
(n-l)/2
答案:【C】
35、設(shè)某強連通圖中有n個頂點,則該強連通圖中至少有()條邊。
A.
n(n-l)
B.
n+1
C.
n
D.
n(n+l)
答案:【C】
36、設(shè)某散列表的長度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇(
A.
99
B.
97
C.
91
D.
93
答案:【B】
37、若線性表最常用的操作是存取第i個元素的值,則采用______存儲方式節(jié)省時間。
A.
單鏈表
B.
雙鏈表
C.
單循環(huán)鏈表
D.
順序表
答案:【D】
38、設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點,2個度數(shù)為2的結(jié)點,2個度數(shù)為3的結(jié)
點,則該三叉樹中有()個度數(shù)為0的結(jié)點。
A.
5
B.
6
C.
7
D.
8
答案:
39、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值,則用線性探測法把這n個關(guān)鍵字映射到
HASH表中需要做()次線性探測。
A.
n2
B.
n(n+l)
C.
n(n+l)/2
D.
n(n-l)/2
答案:【D】
40、對n個記錄的文件進行快速排序,所需要的輔助存儲空間大致為()
A.
0(1)
B.
O(n)
c.
O(log2n)
D.
O(n2)
答案:【O
41、設(shè)某無向圖中有n個頂點e條邊,則建立該圖鄰接表的時間復(fù)雜度為()。
A.
O(n+e)
B.
0(M)
C.
O(ne)
D.
0(n3)
答案:【A】
42、設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為Ni..........度數(shù)為
m的結(jié)點數(shù)為Nm,則No=()。
A.
N1+N2+.....+Nm
B.
I+N2+2N3+3N4+……+(m-l)Nm
C.
N2+2N3+3N4+......+(m-l)Nm
D.
2N+3N2++(m+l)Nm
答案:【B】
43、二叉樹的第k層的結(jié)點數(shù)最多為()。
A.
2k-l
B.
2K+1
C.
2K-1
D.
2k-l
答案:【D】
44、設(shè)指針q指向單躡中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s
指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。
A.
s->next=p->next;p->next=-s
B.
q->next=s;s->next=p
C.
p->next=s->next;s->next=p
D.
p->next=s;s->next=q
答案:【B】
45、設(shè)輸入序列是1、2、3.............n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則
輸出序列中第i個輸出元素是()。
A.
n-i
B.
n-1-i
C.
n+1-i
D.
不能確定
答案:【。
46、樹最適合用來表示i)。
A.
有序數(shù)據(jù)元素
B.
無序數(shù)據(jù)元素
C.
元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.
元素之間無聯(lián)系的數(shù)據(jù)
答案:【O
47、設(shè)一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持
有序,則該操作的時間復(fù)雜度為()。
A.
O(log2n)
B.
0(1)
C.
0(n2)
D.
0(n)
答案:【D】
48、設(shè)一棵完全二叉樹中有65個結(jié)點,則該完全二叉樹的深度為()。
A.
8
B.
7
C.
6
D.
5
答案:【B】
49、設(shè)二叉排序樹中有n個結(jié)點,則在二叉排序樹的平均杳找長度為().
A.
0(1)
B.
O(log2n)
C.
O(nlog2n)
D.
0(n2)
答案:【B】
50、設(shè)有5000個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個記
錄關(guān)鍵字,則用下列()方法可以達到此目的。
A.
快速排序
B.
堆排序
C.
歸并排序
D.
插入排序
答案:【B】
一、簡答(每題參考分值5分)
1、二維數(shù)組inta[10][10],以行優(yōu)先存儲,第1個元素的首址是100,每個
元素的長度為4,求A[4][5]的存儲首址。
正確答案:
A[4H5]的存儲首址
=100+(4*10+5)*4=100+45*2
=280
二、辨析(每題參考分值5分)
2、閱讀下列算法,并回答問題。
floatwhat(floatx,intn){
floaty=x;
while(n>l)
{y=y*x;n=n^Cl;}
returny;}
問題:(1)該算法的功能是計算
(2)該算法的時間復(fù)雜度是_______
正確答案:
xn,0(n)
三、計算(每題參考分值5分)
3、對對{278,109,63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排
序,寫出每一趟排序過程
正確答案:
第一趟排序后(個位有序):
930,063,083,184,505,278,008,109,589,269
第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):
505,008,109,930,063,269,278,083,184,589
第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):
008r063,083,109,184,269,278,505,589,930
4、對給定的單鏈表L,下面算法完成刪除L中值為x的結(jié)點的直接前驅(qū)結(jié)點。請?zhí)羁铡?/p>
voidDeleteX(LinkListL,DataTypex)
{/*L是帶頭結(jié)點的單鏈表*/
ListNode*p,*q;
q=L;p=L->next;
while(p&&p->data!=x)
{q=p;
P=_________;}
if()
Error("xisthefirstnode,ithasnopriornode");
q->data=x;
q->next=p->next;
free();
)
正確答案:
解:
(l)p->next(2分)
(2)p==NULL(2分)
⑶P(1分)
5、以{45,53,12,37,24,100,3,61,90,78}
構(gòu)造二叉排序樹。
正確答案:
6、設(shè)無向圖G(如右圖所示),給出該圖的最小生成樹上邊的集合并計算最小生成樹各
邊上的權(quán)值之和。
正確答案:
解:E={(1,5),(5,2),(5,3),(3,4)},W=1O
7、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷
序列是:皿a曲;寫出后序遍歷序列。
正確答案:
后序遍歷序列:cdbgfea
8、設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。
正確答案:
解:設(shè)計將所有奇數(shù)移到所有偶數(shù)之前的算法。
voidquickpass(intr[],ints,intt)
inti=sj=t/x=r[s];
while(i<j)
(
while(i<j&&r[j]%2==0)j=j-l;if(i<j){r[i]=r[j];i=i+l;}
while(i<j&&r[i]%2==l)i=i+l;if(i<j){r[j]=r[i];j=j-l;}
)
r[i]=x;
)
9、voidABC(BTNode*BT)
(
ifBT(
ABC(BT->left);
ABC(BT->right);
cout<<BT->data<<'
)
)
該算法的功能是:
正確答案:
解:遞歸地后序遍歷鏈?zhǔn)酱鎯Φ亩鏄洹?/p>
10、在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。
正確答案:
解:在鏈?zhǔn)酱鎯Y(jié)構(gòu)上建立一棵二叉排序樹。
#definen10
typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;
voidbstinsert(bitree*&btjntkey)
(
if(bt==O){bt=(bitree*)malloc(sizeof(bitree));
bt->key=key;bt->lchild=bt->rchild=O;}
elseif(bt->key>key)bstinsert(bt->lchild,key);else
bstinsert(bt->rchild,key);
}
voidcreatebsttree(bitree*&bt)
inti;
for(i=l;i<=n;i++)bstinsertfbt/andomflOO));
)
四、單選(每題參考分值2.5分)
11、深度為k的完全二叉樹中最少有()個結(jié)點。
A.
2k-i-l
B.
2匕1
C.
2匕1+1
D.
2k-l
答案:【B】
12、設(shè)輸入序列1、2、3、…、n經(jīng)過棧作用后,輸出序列中的第一個元素是n,則輸出
序列中的第i個輸出元素是()。
A.
n-i
B.
n-1-i
C.
n+l-i
D.
不能確定
答案:【O
13、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)二key%p,則p最好選擇()。
A.
小于等于m的最大奇數(shù)
B.
小于等于m的最大素數(shù)
C.
小于等于m的最大偶數(shù)
D.
小于等于m的最大合數(shù)
答案:【B】
14、某二叉樹的后序遍歷序列為DABEC、中序遍歷序列為DEBAC,則前序遍歷為
A.
ACBED
B.
DECAB
C.
DEABC
D.
CEDBA
答案:【D】
15、下列排序算法中時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響,恒為0(己)的是
A.
堆排序
B.
冒泡排序
C.
直接選擇排序
D.
快速排序
答案:【。
16、利用直接插入排序法的思想建立一個有序線性表的時間復(fù)雜度為()。
A.
O(n)
B.
O(nlog2n)
C.
0(n2)
D.
O(log2n)
答案:【C】
17、圖G的某一最小生成樹的代價一定小于其他生成樹的代價
A.
一定是
B.
肯定不是
C.
不一定是
D.
都不對
答案:【。
18、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹講行順序編號,則編號為
i結(jié)點的左孩子結(jié)點的編號為()。
A.
2i+l
B.
2i
c.
i/2
D.
2i-l
答案:【B】
19、兩個字符串相等的充要條件是()。
A.
兩個字符串的長度相等
B.
兩個字符串中對應(yīng)位置上的字符相等
C.
同時具備(A)和(B)兩個條件
D.
以上答案都不對
答案:【C】
20、設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏5臈m?,則刪除棧頂元素的操作序列為()。
A.
top=top+l;
B.
top=top-l;
C.
top->next=top;
D.
top=top->next;
答案:【D】
21、設(shè)某無向圖有n個頂點,則該無向圖的鄰接表中有()個表頭結(jié)點。
A.
2n
B.
n
C.
n/2
D.
n(n-l)
答案:【B】
22、Jll頁序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時間復(fù)雜度為()。
A.
0(n)
B.
0(n2)
c.
0(nV2)
D.
O(log2n)
答案:【A】
23、設(shè)III頁序線性表中有n個數(shù)據(jù)元素,則刪除表中第i個元素需要移動()個元素。
A.
n-i
B.
n+1-i
C.
n-1-i
D.
答案:【A】
24、算法必須具備輸入、輸出和
A.
計算方法
B.
排序方法
C.
解決問題的有限運算步驟
D.
程序設(shè)計方法
答案:
25、()是線性表。
A.
(1,2,3,...)
B.
{a,b,c,d,e}
C.
(L3,5,7)
D.
{4:B';C'}
答案:【C】
26、下列各種排序算法中平均時間復(fù)雜度為0(d)是()。
A.
快速排序
B.
堆排序
c.
歸并排序
D.
冒泡排序
答案:【D】
27、設(shè)二叉排序樹上有n個結(jié)點廁在二叉排序樹上查找結(jié)點的平均時間復(fù)雜度為()。
A.
0(n)
B.
0(M)
C.
O(nlog2n)
D.
0(10020)
答案:【D】
28、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為()。
A.
0(n)
B.
O(log2n)
C.
O(nlog2n)
D.
0(M)
答案:【B】
29、設(shè)某哈夫曼樹中有199個結(jié)點,則該哈夫曼樹中有()個葉子結(jié)點。
A.
99
B.
100
C.
101
D.
102
答案:【B】
30、設(shè)指針變量p指向雙向鏈表中結(jié)點A,指針變量s指向被插入的結(jié)點X,則在結(jié)點
A的后面插入結(jié)點X的操作序列為()。
A.
p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B.
s->left=p;s->right=p->right;p->right=s;p->right->left=s;
c.
p->right=s;p->right->left=s;s->left=p;s->right=p->right;
D.
s->left=p;s->right=p->right;p->right->left=s;p->right=s;
答案:【A】
31、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu),則有向圖G中頂點i的入度為()。
A.
第i行非0元素的個數(shù)之和
B.
第i歹IJ非0元素的個數(shù)之和
C.
第i行0元素的個數(shù)之和
D.
第i列0元素的個數(shù)之和
答案:【B】
32、設(shè)輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為()。
A.
5,3,4,6,1,2
B.
3,256,4,1
C.
3,1,2,5,4,6
D.
1,5,4,6,2,3
答案:【B】
33、設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點,則其判空條件是().
A.
head==O
B.
head->next==O
C.
head->next==head
D.
head!=O
答案:[A]
34、設(shè)某強連通圖中有n個頂點,則該強連通圖中至少有()條邊。
A.
n(n-l)
B.
n+1
c.
n
D.
n(n+l)
答案:【O
35、設(shè)順序表的長度為n,貝州頁序查找的平均比較次數(shù)為()。
A.
n
B.
n/2
C.
(n+l)/2
D.
(n-l)/2
答案:【。
36、設(shè)一棵三叉樹中有2個度數(shù)為1的結(jié)點,2個度數(shù)為2的結(jié)點,2個度數(shù)為3的結(jié)
點,則該三叉樹中有()個度數(shù)為0的結(jié)點。
A.
5
B.
6
C.
7
D.
8
答案:【。
37、若線性表最常用的澡作是存取第i個元素的值,則采用存儲方式節(jié)省時間。
A.
單鏈表
B.
雙鏈表
C.
單循環(huán)鏈表
D.
順序表
答案:【D】
38、設(shè)某散列表的長度為100,散列函數(shù)H(k)=k%P,則P通常情況下最好選擇(
A.
99
B.
97
c.
91
D.
93
答案:【B】
39、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值,則用線性探測法把這n個關(guān)鍵字映射到
HASH表中需要做()次線性探測。
A.
n2
B.
n(n+l)
C.
n(n+l)/2
D.
n(n-l)/2
答案:【D】
40、設(shè)某無向圖中有n個頂點e條邊,則建立該圖鄰接表的時間復(fù)雜度為()。
A.
O(n+e)
B.
0(小)
C.
O(ne)
D.
O(n3)
答案:【A】
41、設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為No,度數(shù)為1的結(jié)點數(shù)為N................
m的結(jié)點數(shù)為Nm,則N0=()。
A.
N1+N2+.....+Nm
B.
I+N2+2N3+3N4+.....+(m-l)Nm
C.
N2+2N3+3N4+.....+(m-l)Nm
D.
2NI+3N2+......+(m+l)Nm
答案:【B】
42、設(shè)指針q指向單躡中結(jié)點A,指針p指向單鏈表中結(jié)點A的后繼結(jié)點B,指針s
指向被插入的結(jié)點X,則在結(jié)點A和結(jié)點B插入結(jié)點X的操作序列為()。
A.
s->next=p->next;p->next=-s
B.
q->next=s;s->next=p
C.
p->next=s->next;s->next=p
D.
p->next=s;s->next=q
答案:【B】
43、對n個記錄的文件講行快速排序,所需要的輔助存儲空間大致為()
A.
0(1)
B.
0(n)
C.
O(log2n)
D.
O(n2)
答案:【o
44、二叉樹的第k層的結(jié)點數(shù)最多為()。
A.
2k-l
B.
2K+1
C.
2K-1
D.
2k-l
答案:【D】
45、設(shè)輸入序列是1、2、3..........n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則
輸出序列中第i個輸出元素是()。
A.
n-i
B.
n-1-i
C.
n+1-i
D.
不能確定
答案:
46、設(shè)一棵完全二叉樹中有65個結(jié)點,則該完全二叉樹的深度為()。
A.
8
B.
7
C.
6
D.
5
答案:【B】
47、樹最適合用來表示]).
A.
有序數(shù)據(jù)元素
B.
無序數(shù)據(jù)元素
C.
元素之間具有分支層次關(guān)系的數(shù)據(jù)
D.
元素之間無聯(lián)系的數(shù)據(jù)
答案:【C】
48、設(shè)一個有序的單鏈表中有n個結(jié)點,現(xiàn)要求插入一個新結(jié)點后使得單鏈表仍然保持
有序,則該操作的時間復(fù)雜度為()。
A.
O(log2n)
B.
0(1)
C.
0(M)
D.
0(n)
答案:【D】
49、設(shè)有5000個待排序的記錄關(guān)鍵字,如果需要用最快的方法選出其中最小的10個記
錄關(guān)鍵字,則用下列()方法可以達到此目的。
A.
快速排序
B.
堆排序
C.
歸并排序
D.
插入排序
答案:【B】
50、設(shè)二叉排序樹中有n個結(jié)點,則在二叉排序樹的平均查找長度為()。
A.
0(1)
B.
O(log2n)
C.
O(nlog2n)
D.
0(?。?/p>
答案:【B】
一、計算(每題參考分值5分)
1、對對{278,109,63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排
序,寫出每一趟排序過程
正確答案:
第一趟排序后(個位有序):
930,063,083,184,505,278,008r109,589,269
第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):
505,008,109,930,063,269,278,083,184,589
第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):
008,063,083,109,184,269,278,505,589,930
2、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。
00150022COco
QOco11QCcoco
co3coccco28
22co00QCcoco
00coQOQCcoco
15COcoCCcoCO
正確答案:
3、設(shè)通信用8個字符abcdefgh,各字符使用的相對頻率分別
為25,36,2,5,8,10,14,50,構(gòu)造哈夫曼樹,設(shè)計哈夫曼編碼,求該樹的帶樹路
徑長度WPLe
正確答案:
OTOW
IOOI:9
IOOOI:P
OOOOI:)
io:q
oo:e
g:1011
h:ll
WPL=(25+36+50)*2+(8+10+14)*4+(2+5)*5
二385
4、用kruskal方法求下圖的最小生成樹
正確答案:
5、對{49,38,65,97,76,13,27,49)進行直接插入排序,寫出每一趟排序
過程
正確答案:
第1趟i=2(3849)659776132749
第2趟i=3384965)9776132749
第3趟i=438496597)76132749
第4趟i=53849657697)132749
第5趟i=6(133849657697)2749
第6趟i=7(13273849657697)49
第7趟i=8(1327384949657697
6、以{45,53,12,37,24,100361,90,78}
構(gòu)造二叉排序樹。
正確答案:
7、以{24Z68,2755,23,11,10,19,20,79,84},構(gòu)造hash表并求平均查找
長度。表長度為
hash17,hash(key)=key%17o
用線性探測法解決沖突。
正確答案:
012345678910111213141516
68119205523271110791484
ASL=(l*10+3*2)/12=16/12
8、對對{278,109f63,930,589,184,505,269,8,83}用基數(shù)排序方法進行排
序,寫出每一趟排序過程
正確答案:
第一趟排序后(介位有序):
930,063,083,184,505,278,008f109f589,269
第二趟排序后(在個位有序的基礎(chǔ)上使拾位有序):
505,008,109,930,063,269,278,083,184,589
第三趟排序后(在拾位有序的基礎(chǔ)上使百位有序):
008,063,083,109,184,269,278,505,589,930
9、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷
序列是:史更必寫出后序遍歷序列。
正確答案:
后序遍歷序列:cdbgfea
二、論述(每題參考分值5分)
10、設(shè)線性表存于整型數(shù)據(jù)a[l..MAXSIZE]的前n個分量中且遞增有序,將x
插入到線性表的適當(dāng)位置。
正確答案:
voidinsert(){
if(nv=MAXSIZE)〃當(dāng)順序表不滿時
{inti=n;
while(i>=l&&x<a[i])
{a[i+l]=a[i];i-;)
//我插入位置,并后移
a[i+l]=x;
n++;
}
)
p=p->next;
else
mark=O;
returnmark;
)
一、辨析(每題參考分值5分)
1、分析下列的算法,求T(n).(用大0表示)
i=l;j=O;
while(i+j<=n)
if(i>j)j++;elsei++;
正確答案:
T(n)=O(n)
二、計算(每題參考分值5分)
2、設(shè)有一組初始記錄關(guān)鍵字為(45,80,48,40,22,78),要求構(gòu)造一棵二叉排序樹
并給出構(gòu)造過程。
正確答案:
78-
3、請畫出下圖的鄰接矩陣和鄰接表。
正確答案:
解:鄰接矩陣:
01110
10101
11011
10101
01110
鄰接表:
4、設(shè)關(guān)鍵字序列(%,k2,…,kn-i)是堆,設(shè)計算法將關(guān)鍵字序列(ki,k2,…,kn-i,x)
調(diào)整為堆。
正確答案:
解:設(shè)關(guān)鍵字序列,是堆,設(shè)計算法將關(guān)鍵字序列(%,
(ki,k2…,kn-i)k2kn-i,x)
調(diào)整為堆。
voidadjustheap(intr[],intn)
(
intj=nj=j/2,temp=r[j-l];
while(i>=l)if(temp>=r[i-l])break;else{r[j-l]=r[i-l];j=i;i=i/2;}
r[j-l]=temp;
)
5、已知二叉樹先序遍歷序列是:abcdefg;中序遍歷
序列是:但a四寫出后序遍歷序列。
正確答案:
后序遍歷序列:cdbgfea
6、設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。
正確答案:
解:設(shè)計在鏈?zhǔn)浇Y(jié)構(gòu)上實現(xiàn)簡單選擇排序算法。
voidsimpleselectsorlklist(lklist*&head)
Iklist*p,*q,*s;intmin,t;
if(head==0||head->next==O)return;
for(q=head;q!=0;q=q->next)
min=q->data;s=q;
for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}
if(s!=q){t=s->data;s->data=q->data;q->data=t;}
)
}
7、已知一個網(wǎng)的鄰接矩陣A如下,試畫出該網(wǎng)。
00150022coQO
on0011on0Oon
co3QOccco28
22coQOQCQOco
00co00QCQOco
15coCOccCOCO
正確答案:
8、已知一個散列表如下圖所示:
012345678910
2457364668
其散列函數(shù)為h(key)=key%U,處理沖突的方法為二次探查法,探查序列為:
22222
hi=(h(key)+di)%mdi=l/-l,2/-2,...,±k,(k<m/2)i=
回答下列問題:
(1)對表中關(guān)鍵字36,46,68和24進行杳找時,所需進行的比較次數(shù)各為多少?
(2)該散列表在等概率查找時查找成功的平均查找長度為多少?
正確答案:
解:(1)杳找36,46,68和24時,所需進行的匕徽次數(shù)各為1,4,5和3次。(2
分)
(2)ASLsuCC=(l+l+3+4+5)/5=14/5(3分)
9、已知二叉樹的前序遍歷序列是AEFBGCDHIKJ,中序遍歷序列是EFAGBCHKIJD,畫
出此二叉樹,并畫出它的后序線索二叉樹。
正確答案:
解:
NULL八,
10、設(shè)有一組初始記錄關(guān)鍵字序列(Ki,K2,...,Kn),要求設(shè)計一個算法能夠在O(n)
的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部
分的每個關(guān)鍵字均大于等于心
正確答案:
解:設(shè)有一組初始記錄關(guān)睇字序列(Ki,K?,…,Kn),要求設(shè)計一個算法能夠在O(n)
的時間復(fù)雜度內(nèi)將線性表劃分成兩部分,其中左半部分的每個關(guān)鍵字均小于Ki,右半部
分的每個關(guān)鍵字均大于等于心
voidquickpass(intr[],ints,intt)
inti=sj=t,x=r[s];
while(i<j){
while(i<j&&r[j]>x)j=j-l;if(i<j){r[i]=r[j];i=i+l;}
while(i<j&&r[i]<x)i=i+l;if(i<j){r[j]=r[i];j=j-l;}
r[i]=x;
)
三、單選(每題參考分值2.5分)
11、設(shè)有序順序表中有n個數(shù)據(jù)元素,則利用二分查找法查找數(shù)據(jù)元素X的最多比較次
數(shù)不超過()0
A.
Iog2n+1
B.
Iog2n-1
C.
log2n
D.
Iog2(n+1)
答案:【A】
12、下面關(guān)于線性表的敘述錯誤的是()o
A.
線性表采用順序存儲必須占用一片連續(xù)的存儲空間
B.
線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間
C.
線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn)
D.
線性表采用順序存儲便于插入和刪除操作的實現(xiàn)
答案:【D】
13、隊列是一種()的線性表。
A.
先進先出
B.
先進后出
C.
只能插入
D.
只能刪除
答案:【A】
14、在二叉排序樹中插入一個關(guān)鍵字值的平均時間復(fù)雜度為().
A.
0(n)
B.
O(log2n)
C.
O(nlog2n)
D.
0(小)
答案:【B】
15、深度為k的完全二叉樹中最少有()個結(jié)點。
A.
2匕1-1
B.
21
C.
2k-1+l
D.
2k.i
答案:【B】
16、若線性表最常用的操作是存取第i個元素的值,則采用_____存儲方式節(jié)省時間。
A.
單鏈表
B.
雙鏈表
C.
單循環(huán)鏈表
D.
順序表
答案:【D】
17、設(shè)某棵二叉樹中只有度數(shù)為0和度數(shù)為2的結(jié)點二度數(shù)為0的結(jié)點數(shù)為n,則這棵
二叉中共有()個結(jié)點。
A.
2n
B.
n+l
C.
2n-l
D.
2n+l
答案:【C】
18、()二叉排序樹可以得到一個從小到大的有序序列.
A.
先序遍歷
B.
中序遍歷
C.
后序遍歷
D.
層次遍歷
答案:【B】
19、下面程序的時間復(fù)雜度為()
for(i=l,s=0;i<=n;i++){t=l;for(j=l;j<=i;j++)t=t*j;s=s+t;}
A.
0(n)
B.
0(n2)
C.
0(n3)
D.
0(n4)
答案:【B】
20、設(shè)有n個待排序的記錄關(guān)鍵字,則在堆排序中需要()個輔助記錄單元。
A.
1
B.
n
C.
nlog2n
D.
n2
答案:[A]
21、設(shè)一棵完全二叉樹中有65個結(jié)點,則該完全二叉樹的深度為()。
A.
8
B.
7
C.
6
D.
5
答案:【B】
22、利用直接插入排序法的思根建立一個有序線性表的時間復(fù)雜度為().
A.
0(n)
B.
O(nlog2n)
C.
0(己)
D.
O(log2n)
答案:【C】
23、二路歸并排序的時間復(fù)雜度為()。
A.
0(n)
B.
0(小)
C.
O(nlog2n)
D.
O(log2n)
答案:【。
24、設(shè)輸入序列是1、2、3..........n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則
輸出序列中第i個輸出元素是()。
A.
n-i
B.
n-1-i
C.
n+1-i
D.
不能確定
答案:
25、設(shè)有一個二維數(shù)組A[mi[n\,假設(shè)40]⑼存放位置在644(i0),42][2]存放位置在
676(io),每個元素占一個空間,問43][3]QO)存放在什么位置?腳注(10)表示用10進制表
A.
688
B.
678
C.
692
D.
696
答案:【。
26、一隊列的入隊序列是1,2,3,4,則隊列的輸出序列是
A.
1,2,3,4
B.
4,3,2,1
c.
1,4,3,2
D.
3,2,4,1
答案:【A】
27、下列四種排序中()的空間復(fù)雜度最大。
A.
插入排序
B.
冒泡排序
C.
堆排序
D.
歸并排序
答案:【D】
28、若有18個元素的有序表存放在一維數(shù)組A[19]中,第一個元素放A[l]中,現(xiàn)進行
二分查找,則查找A[3]的比較序列的下標(biāo)依次為()
A.
1,2,3
B.
952,3
C.
9,5,3
D.
9,4,2,3
答案:【D】
29、對于線性表(7,34,55,25,64,46,20,10)進行散列存儲時,若選用H(K)
=K%9作為散列函數(shù),則散列地址為1的元素有()個。
A.
1
B.
2
C.
3
D.
4
答案:【D】
30、設(shè)指針變量front表示鏈?zhǔn)疥犃械年狀^指針,指針變量rear表示鏈?zhǔn)疥犃械年犖仓?/p>
針,指針變量s指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為().
A.
front->next=s;front=s;
B.
s->next=rear;rear=s;
C.
rear->next=s;rear=s;
D.
s->next=front;front=s;
答案:【C
31、設(shè)一棵m叉樹中有Ni個度數(shù)為1的結(jié)點,Nz個度數(shù)為2的結(jié)點.....Nm個度
數(shù)為m的結(jié)點,則該樹中共有()個葉子結(jié)點。
A.
m
}=i
B.
m
1=1
c.
2地
2=2
D.
m
1+Z(-1)M
2=2
答案:【D】
32、一個非空廣義表的表頭
A.
一定是子表
B.
一定是原子
C.
不能是子表
可以是原子,也可以是子表
答案:【B】
33、單鏈表的存儲密度
A.
大于1
B.
等于1
C.
小于1
D.
不能確定
答案:【C】
34、設(shè)某哈夫曼樹中有199個結(jié)點,則該哈夫曼樹中有()個葉子結(jié)點。
A.
99
B.
100
C.
101
D.
102
答案:【B】
35、建立一個長度為n的有序單鏈表的時間復(fù)雜度為()
A.
O(n)
B.
0(1)
C.
0(己)
D.
O(log2n)
答案:【C】
36、設(shè)某有向圖的鄰接表中有n個表頭結(jié)點和m個表結(jié)點,則該圖中有()條有向邊。
A.
n
B.
n-1
C.
m
D.
m-1
答案:【。
37、設(shè)一組初始記錄關(guān)鍵字序列為(25,50,15,35,80,85,20,40,36,70),其
中含有5個長度為2的有序子表,則用歸并排序的方法對該記錄關(guān)鍵字序列進行一趟歸
并后的結(jié)果為()。
A.
15,25,35,50,20,40,80,85,36,70
B.
15,25,35,50,80,20,85,40,70,36
C.
15,25,35,50,80,85,20,36,40,70
D.
15,25,35,50,80,20,36,40,70,85
答案:【A】
38、設(shè)完全無向圖中有n個頂點,則該完全無向圖中有()條邊。
A.
n(n-l)/2
B.
n(n-l)
C.
n(n+l)/2
D.
(n-l)/2
答案:[A]
39、具有n個結(jié)點的完全二叉樹的深度為
A.
riog2nj+1
B.
Iog2n+1
c.
log2n
D.
[logznj
答案:【D】
40、下列算法的時間復(fù)雜度是
for(i=0;i<n;i++)c[i]=i;
A.
0(1)
B.
0(n)
C.
O(log2n)
D.
O(nlog2n)
答案:【B】
41、設(shè)某棵三叉樹中有40個結(jié)點,則該三叉樹的最小高度為()。
A.
3
B.
4
C.
5
D.
6
答案:【B】
42、若有18個元素的有序表存放在一維數(shù)組A[19]中,第一個元素放A[l]中,現(xiàn)進行
二分查找,則查找A[3]的比較序列的下標(biāo)依次為()
A.
1,2,3
B.
952,3
C.
9,5,3
D.
9,4,2,3
答案:【D】
43、循環(huán)隊列SQ的存儲空間是數(shù)組d[m],隊頭、尾指針分別是front和rear,則執(zhí)行
入隊后其尾指針值rear是
A.
rear=rear+l
B.
rear=(rear+l)%(m-l)
C.
rear=(rear+l)%m
D.
rear=(rear-l)%m
答案:【O
44、設(shè)無向圖G中有n個頂點,則該無向圖的最小生成樹上有()條邊c
A.
n
B.
n-1
C.
2n
D.
2n-l
答案:【B】
45、設(shè)一組初始記錄關(guān)鍵字序列為(45,80,55,40,42,85),則以第一個記錄關(guān)鍵
字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是()。
A.
40,42,45,55,80,83
B.
42,40,45,80,85,88
C.
42,40,45,55,80,85
D.
42,40,45,85,55,80
答案:【。
46、對n個記錄的文件進行快速排序,所需要的輔助存儲空間大致為()
A.
0(1)
B.
0(n)
C.
0(log2n)
D.
0(n2)
答案:【C】
47、設(shè))1質(zhì)序線性表的長度為30,分成5塊,每塊6個元素,如果采用分塊查找,則其
平均查找長度為()。
A.
6
B.
11
C.
5
D.
6.5
答案:【D】
48、設(shè)散列表中有m個存儲單元,散列函數(shù)H(key)=key%p,則p最好選擇(
A.
小于等于m的最大奇數(shù)
B.
小于等于m的最大素數(shù)
c.
小于等于m的最大偶數(shù)
D.
小于等于m的最大合數(shù)
答案:【B】
49、設(shè)無向圖G中有n個頂點e條邊,則其對應(yīng)的鄰接表中的表頭結(jié)點和表結(jié)點的個數(shù)
分別為()。
A.
n,e
B.
e,n
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年安陽市疾病預(yù)防控制中心公開招聘工作人員15名模擬試卷(含答案詳解)
- 影視廣告三方協(xié)議6篇
- 遼寧省沈陽市重點學(xué)校2024-2025學(xué)年高三上學(xué)期10月月考地理試卷(解析版)
- 2025甘肅祁連山水泥集團有限公司招聘考前自測高頻考點模擬試題及答案詳解(新)
- 2025甘肅金昌市公安局招聘公益性崗位人員58人考前自測高頻考點模擬試題及一套答案詳解
- 2025安徽馬鞍山市博望區(qū)人民醫(yī)院招聘派遣制人員8人考前自測高頻考點模擬試題及答案詳解(典優(yōu))
- 2025年度中國農(nóng)業(yè)科學(xué)院哈爾濱獸醫(yī)研究所公開招聘18人考前自測高頻考點模擬試題及答案詳解(必刷)
- 2025年松原市繁榮社區(qū)衛(wèi)生服務(wù)中心公開招用編外(聘用)人員的(20人)模擬試卷參考答案詳解
- 2025廣東湛江法院勞動合同制司法輔助人員招聘9人模擬試卷及一套完整答案詳解
- 一本啟迪心靈的書魯濱遜漂流記讀后感5篇
- 生物試劑庫存管理辦法
- 海上風(fēng)電場安全監(jiān)測技術(shù)的現(xiàn)狀與未來發(fā)展趨勢
- 渠道考試題及答案
- QC/T 983-2025汽車變速器總成清潔度檢測方法
- 村級財務(wù)業(yè)務(wù)知識培訓(xùn)課件
- 美術(shù)基礎(chǔ) 課件全套 第1-5章 美術(shù)簡介 -中國民間美術(shù)
- 2025年青少年法制知識競賽題庫
- 2025年《臨床輸血技術(shù)規(guī)范》
- 《中職工程測量技術(shù)專業(yè)《GNSS測量技術(shù)與應(yīng)用》課程標(biāo)準(zhǔn)》
- 公安部門大數(shù)據(jù)管理辦法
- 骨科患者圍手術(shù)期營養(yǎng)管理
評論
0/150
提交評論