數據結構與算法考試參考題

專業：計算機科學與技術13年

一、單選（30分

1.在數據結構中，數據的邏輯結構可分（B.線性結構和非線性結構

2.在以單鏈表為存儲結構的線性表中,數據元素之間的邏輯關系用（C.指向后繼元素的指針表示

3.設p指向單鏈表中的一個結點。S指向待插入的結點，則下述程序段的功能是（D.在結點*p之前插入結點*s

s->next=p->next;p->next=s!

t=p->data;p->data=s->data;s->data=t;

B.在p所指結點的元素之前插入元素D.在結點*p之前插入結點*s

4.棧和隊列都是（C:鏈式存儲的線性結構

A:限制存取位置的線性結構B:順序存儲的線性結構

C:鏈式存儲的線性結構D:限制存取位置的非線性結構

5.下列關于線性表的基本操作中,屬于加工型的操作是（B初始化、插入、刪除操作

6.根據定義,樹的葉子結點其度數（B.必等于0

7.多維數組之所以有行優先順序和列優先順序兩種存儲方式是因為（A.數組的元素處在行和列兩個關系中

8.從廣義表LS=（（p,q,r,s中分解出原子q的運算是<B.head<tall<head<LS?>

9.在具有n個葉子結點的滿二叉樹中，結點總數為（C.2n-l

10.若<Vi,Vj>是有向圖的一條邊，則稱（D.Vi與Vj不相鄰接

11.二叉樹若采用二叉鏈表結構表示，則對于n個結點的二叉樹一定有（B.2n個指針域其中n+1個指針為NULL

12.在一個無向圖中，所有頂點的度數之和等于邊數的（B.2倍

13.一個含n個頂點和e條弧的有向圖以鄰接矩陣表示法為存儲結構，則計算該有向圖中某個頂點出度的時間復雜度為

（A.O<n>

14.散列法存儲中出現的碰撞（沖突現象指的是（B.不同關鍵碼值對應到相同的存儲地址

15.循環鏈表適合的查找方式是（A.順序

二、填空（20分

1.若一棵完全二叉樹中含有121個結點，則該樹的深度為（7

2.若以鄰接矩陣表示有向圖，則鄰接矩陣上第i行中非零元素的個數之和即為頂點Vi的

3.二叉樹的遍歷主要有先序遍歷、后序遍歷和（中序遍歷三種。

4.深度為3的完全二叉樹至少有（4個結點。

5.若圖的鄰接矩陣是一個對稱矩陣，則該圖一定是一個

6.若某無向圖G的鄰接表如下圖所示，試給出以頂點V3為出發點.按廣度優先搜索所產生的結點序列（V3-2V1-V4-V5

7.在無向圖中，若從頂點a到頂點b存在（路徑，則稱a與b之間是連通的。

8.我們通常把隊列中允許刪除的一端稱為（隊頭

9.表頭和表尾均為（a,<b,c>的廣義表L=」_

10.假定對有序表：（進行折半查找，若查找元素24（程序設定為向下取整，需依次與（元素進行比較。

三、解答（50分

1.二維數組A[10.20]采用按行為主序的存儲方式，每個元素占4個存儲單元，若的存儲地址為300,則請算A[10,10]的

存儲地址。

答：300+（9*20+10*

4=300+190*4=300

+760=1060

2.已知樹如右圖所示：

(1畫出由該樹轉換得到的二叉樹；

原圖答圖：

(2寫出該二叉樹的后序序列：

答：后序序列為：EBKJIHGFDCA

3.試給出如圖所示的鄰接矩陣和鄰接表表示。

答：鄰接矩陣

4.己知某二叉排序樹10個結點的值依次為1-10,其結構如圖所示,試標出該二叉排序樹各結點

所對應的具體值。

5.試構造下圖的最小生成樹，要求分步給出構造過程。

原圖:

6.從一個空的二叉排序樹開始，依次插入關鍵字試畫出插入關鍵字后的二叉排序樹，并計算查

找成功時的平均查找長度。averagesearchlength平均查找長度

答：ASL=<l*l+2*2+3*3+4*l>/7=l§<7

主要思想是以第一個數為標準，將比此數小的放在左邊,大的放在右邊,再一一插入,通過比較,找到末端為止。如

13比25小,便在左邊,后15小于25,又在25左端,但是比13大,故放在了13的右邊,每個數都是這樣找到自己的

位置的。

7.為關鍵字(構造一個長度為7的散列表,設散列函數為h<key>=key%7,用開放定址法解決

沖突的探查序列是

Hi=<h<key>+<key%5+l?%70WiW6

<1>畫出構造所得的散列表；

〈2〉求出在等概率情況下查找成功時的平均查找長度。

答：

ASL=<l+l+3+2+4>/5=ll/5

H<17>=17%7=3

H<33>=33%7=5

H<31>=31%7=3沖突

?%=(3+1(31%5+1%7

=5%7=5沖突

Hi=<3+2<31%5+1?%7

=<3+4>%7=0

H<40>=40%7=5沖突

Hi=<5+l<40%5+0?%7

=6%7=6

H<48>=48%7=6沖突

Hi=<6+1<48%5+1?%7

=<6+4>%7=3沖突

Hi=<6+2<48%5+l?%7

=<6+8>%7=0沖突

Hi=<6+3<48%5+l?%7

=<6+12>%7

=18%7

=4

0123456

3117483340

8.……頂點C出發進行深度優先遍歷的序列。

原圖：

答：CDABFE

完

1.已知一棵樹邊的集合為

{<i,m>,<i,n>,<e,i>,<b,e>,<b,d>,<a,b>,<g,j>,<g,k>,<c,g>,<c,f>,<h,1>,<c,h>,<a,c>},

請畫出這棵樹,并回答下列問題：

(1哪個是根結點？(2哪些是葉子結點？(3哪個是結點g的雙親？(4哪些是結點g

的祖先？(5哪些是結點g的孩子？(6哪些是結點e的孩子？

(7哪些是結點e的兄弟？哪些是結點f的兄弟？(8結點b和n的層次號分別是什么？

(9樹的深度是多少？

(10以結點c為根的子樹深度是多少？1.解答：

根據給定的邊確定的樹如圖5-15所示。其中根結點為a；葉子結點有：d、m、n、j、k、f、

1;

c是結點g的雙親；

a、c是結點g的祖先；

j、k是結點g的孩子；m>n是結點e的子孫；e是結點d的兄弟；

g、h是結點f的兄弟；

結點b和n的層次號分別是2和5；樹的深度為5。

4.已知用一維數組存放的一棵完全二叉樹：ABCDEFGHIJKL,寫出該二叉樹的先序、中序和后

序遍歷序列。

4.解答：

先序序列：ABDHIEJKCFLG中序序列：1IDIBJEKALFCG后序序列：HIDJKEBLFGCA

數據結構：在一棵空的二叉查找樹中依次插入關鍵字學列為54,18,66,87,36,12請畫出所

得到的二叉排序樹

數據結構題：二維數組A[10][20]采用列序為主方式存儲，每個元素占一個存儲單元并且A

[0][0]的存儲地址是200

則A[6][12]的地址是326。

還有這題：二維數組A[10..20][5..10]采用行序為主方式存儲，每個元素占4個存儲單元，并且

A[10][5]的存儲地址是1000,則A[18][9]的地址是1208。

答案

第一題: