數(shù)據(jù)結(jié)構(gòu)（Java語言版）模擬試卷3（含參考答案）

數(shù)據(jù)結(jié)構(gòu)試卷（三）一、選擇題(每題2分，共20分)1.設(shè)某數(shù)據(jù)結(jié)構(gòu)的二元組形式表示為A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，則數(shù)據(jù)結(jié)構(gòu)A是(B)。A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.物理結(jié)構(gòu)D.圖形結(jié)構(gòu)2.下面程序的時(shí)間復(fù)雜度為(B)。

1

i=1

2

s=0

3

whilei<=n:

4

i+=1

5

t=1

6

forjinrange(1,i):

7

t=t*j

8

s=s+tA.O(n)B.O(n2)C.O(n3)D.O(n4)3.設(shè)指針變量p指向單鏈表中的結(jié)點(diǎn)A，若刪除單鏈表中的結(jié)點(diǎn)A，則需要修改指針的操作序列為(A)。A.q=p.next；p.data=q.data；p.next=q.next；B.q=p.next；q.data=p.data；p.next=q.next；C.q=p.next；p.next=q.next；D.q=p.next；p.data=q.data；4.設(shè)有n個(gè)待排序的記錄關(guān)鍵字，在堆排序中需要(A)個(gè)輔助記錄單元。A.1B.nC.nlog2nD.n25.設(shè)一組記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(A)。A.10，15，14，18，20，36，40，21B.10，15，14，18，20，40，36，21C.10，15，14，20，18，40，36，21D.15，10，14，18，20，36，40，216.設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則二叉排序樹的平均查找長度為(B)。A.O(1)B.O(log2n)C.O（n）D.O(n2)7.設(shè)無向圖G中有n個(gè)頂點(diǎn)、e條邊，則其對應(yīng)的鄰接表中的表頭結(jié)點(diǎn)和表結(jié)點(diǎn)的個(gè)數(shù)分別為(D)。A.n、eB.e、nC.2n、eD.n、2e8.設(shè)某強(qiáng)連通圖中有n個(gè)頂點(diǎn)，則該強(qiáng)連通圖中至少有(C)條邊。A.n(n-1)B.n+1C.nD.n(n+1)9.設(shè)有5000個(gè)待排序的記錄關(guān)鍵字，如果需要用最快的方法選出其中最小的10個(gè)記錄關(guān)鍵字，則用下列(B)方法可以達(dá)到此目的。A.快速排序B.堆排序C.歸并排序D.插入排序10.下列4種排序中(D)的空間復(fù)雜度最大。A.插入排序B.冒泡排序C.堆排序D.歸并排序二、填空題(每空1分，共20分)1.數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種情況。2.設(shè)一棵完全二叉樹中有500個(gè)結(jié)點(diǎn)，則該二叉樹的深度為____9_____；若用二叉鏈表作為該完全二叉樹的存儲(chǔ)結(jié)構(gòu)，則共有_____501____個(gè)空指針域。3.設(shè)輸入序列為（1，2，3），則經(jīng)過棧的作用后可以得到___5______種不同的輸出序列。4.設(shè)有向圖G用鄰接矩陣A[n][n]作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上的所有元素之和等于頂點(diǎn)i的_____出度____，第i列上的所有元素之和等于頂點(diǎn)i的___入度______。5.設(shè)哈夫曼樹中共有n個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有____0_____個(gè)度數(shù)為1的結(jié)點(diǎn)。6.設(shè)有向圖G中有n個(gè)頂點(diǎn)、e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d，則e和d的關(guān)系為____e=d_____。7.____中序_____遍歷二叉排序樹中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。8.設(shè)查找表中有100個(gè)元素，如果用二分查找方法查找數(shù)據(jù)元素X，則最多需要比較_____7____次就可以斷定數(shù)據(jù)元素X是否在查找表中。9.不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為___O(1)______。10.設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹，如果按照從自上到下、從左到右從1開始順序編號，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為___i/2(向下取整)______，右孩子結(jié)點(diǎn)的編號為___2*i+1______。11.設(shè)一組初始記錄關(guān)鍵字為(72，73，71，23，94，16，5)，則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序的結(jié)果為___5167123729473______。12.設(shè)有向圖G中的有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓?fù)湫蛄袨開__1423______。13.下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字的功能，請?jiān)谙庐嬀€處填上正確的語句。

1

classrecord(object):

2

def__init__(self,key,others):

3

self.key=key

4

self.others=others

5

6

defhashSqSearch(hashTable,k):

7

i=j=k%P

8

whilehashTable[j].key!=kandhashTable[j].flag!=0:

9

j=___j+1___%m

10

ifi==j:

11

return-1

12

if_hashtable[j].key==__k___:

13

returnj

14

elsereturn-114.下列算法實(shí)現(xiàn)在二叉排序樹上查找關(guān)鍵值k的功能，請?jiān)谙庐嬀€處填上正確的語句。

1

defFind(BST,k):

2

#BST是搜索二叉樹的結(jié)點(diǎn)，k是查找的元素

3

ifBSTisNone:

4

returnfalse#查找失敗

5

ifk==BST.data:

6

k=BST.data#查找成功

7

return_true_____

8

elifitem<BST.data:

9

returnFind(__BST.lchild____,k)

10

else:

11

returnFind(__BST.rchild____,k)三、計(jì)算題(每題10分，共30分)1.已知二叉樹的前序遍歷序列是AEFBGCDHIKJ、中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并畫出它的后序線索二叉樹。2.已知待散列的線性表為(36，15，40，63，22)，散列用的一維地址空間為[0..6]，假定選用的散列函數(shù)是H(K)=Kmod7，若發(fā)生沖突采用線性探查法處理，試計(jì)算以下問題：(1)計(jì)算出每一個(gè)元素的散列地址并在圖A.5中填寫出散列表。圖A.5填寫散列表01234566336152240(2)求出在查找每一個(gè)元素概率相等情況下的平均查找長度。(1+2+1+1+3)/5=1.6。3.已知序列(10，18，4，3，6，12，1，9，18，8)，請用快速排序?qū)懗雒恳惶伺判虻慕Y(jié)果。第一趟排序結(jié)果：9436110121818第二趟排序結(jié)果：1436910121818第三趟排序結(jié)果：1436910121818第四趟排序結(jié)果：1346910121818四、算法設(shè)計(jì)題(每題15分，共30分)1.設(shè)計(jì)在單鏈表中刪除值相同的多余結(jié)點(diǎn)的算法。class

Node:

def

__init__(self,

data=None,

nxt=None):

self.data

=

data

self.next

=

nxt

def

delete_same_node(node):

p

=

node

if

p

is

None:

return

elif

p.next

is

None:

return

else:

q

=

node.next

while

q!=None:

if

p.data==q.data:

p.next

=

q.next

p

=

q

q

=

q.next

else:

p

=

p.next

q

=

q.next

return

classNode{intdata;Nodenext;Node(intdt){data=dt;next=null;}}voiddelete_same_node(Nodenode){Nodep=node;if(p==null)return;elseif(p.next==null)return;else{Nodeq=node.next;while(q!=null){if(p.data==q.data){p.next=q.next;p=q;q=q.next;}else{p=p.next;q=q.next;}}}}2.設(shè)計(jì)一個(gè)求結(jié)點(diǎn)x在二叉樹中的雙親結(jié)點(diǎn)的算法。class

TreeNode:

def

__init__(self,

data=None,

lchild=None,

rchild=None):

self.data

=

data

self.lchild

=

lchild

self.rchild

=

rchild

def

find_parent(root,

target):

if

root

is

None:

return

None

elif

root.lchild

is

target

or

root.rchild

is

target:

return

root

elif

root.lchild

is

None

and

root.rchild

is

None:

return

None

else:

return

find_parent(root.lchild,

target)

or

find_parent(root.rchild,

target)

classTreeNode{intdata;TreeNodelchild;TreeNoderchild;TreeNode(intdata,TreeNodelchild,TreeNoderchild){this.data=data;this.lchild=lchild;this.rchild=rchild;}}TreeNodefind_parent(TreeNoderoot,TreeNodetarget){if(root==null)returnnull;elseif(root.lchild==target||root.rchild==target)re