課程代碼：21049

適用專業(yè)：計(jì)算機(jī)應(yīng)用、計(jì)算機(jī)網(wǎng)絡(luò)

一、判斷題 (本大題共15小題，每小題1分，共15分)

正確的在題后括號內(nèi)劃“√”，錯(cuò)誤的劃“×”。

1.算法一定要有輸入和輸出。( )

2.算法分析的目的旨在分析算法的效率以求改進(jìn)算法。( )

3.非空線性表中任意一個(gè)數(shù)據(jù)元素都有且僅有一個(gè)直接后繼元素。( )

4.數(shù)據(jù)的存儲結(jié)構(gòu)不僅有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，還有索引結(jié)構(gòu)與散列結(jié)構(gòu)。( )

5.線性鏈表中各個(gè)鏈結(jié)點(diǎn)之間的地址不一定要連續(xù)。( )

6.若頻繁地對線性表進(jìn)行插入和刪除操作，該線性表采用順序存儲結(jié)構(gòu)更合適。( )

7.若線性表采用順序存儲結(jié)構(gòu)，每個(gè)數(shù)據(jù)元素占用4個(gè)存儲單元，第12個(gè)數(shù)據(jù)元素的存儲地址為144，則第1個(gè)數(shù)據(jù)元素的存儲地址是101。( )

8.若長度為n的線性表采用順序存儲結(jié)構(gòu)，刪除表的第i個(gè)元素之前需要移動表中n-i+1個(gè)元素。( )

9.符號link(p)出現(xiàn)在表達(dá)式中表示p所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。( )

10.要將指針p移到它所指的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)是執(zhí)行語句p←link(p)。( )

11.在非空線性鏈表中由p所指的結(jié)點(diǎn)后面插入一個(gè)由q所指的結(jié)點(diǎn)的過程是依次執(zhí)行語句：link(q)←link(p);link(p)←q。( )

12.在非空雙向循環(huán)鏈表中由q所指的結(jié)點(diǎn)后面插入一個(gè)由p指的結(jié)點(diǎn)的動作依次為：llink(p)←q,rlink(p)←rlink(q),rlink(q)←p,llink(rlink(q))←p。( )

13.若某堆棧的輸入序列為1,2,3,4，則4,3,1,2不可能是堆棧的輸出序列之一。( )

14.刪除非空鏈?zhǔn)酱鎯Y(jié)構(gòu)的堆棧(設(shè)棧頂指針為top)的一個(gè)元素的過程是依次執(zhí)行:p←top,top←link(p),call RET(p)。( )

15.若隊(duì)列采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，隊(duì)頭指針與指針分別為front和rear，向隊(duì)列中插入一個(gè)數(shù)據(jù)信息為item的新元素的過程是依次執(zhí)行:call GETNODE(p),data(P)←item,rear←p,front←p。( )

二、單項(xiàng)選擇題 (本大題共10小題，每小題2分，共20分)

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其代碼填在題后的括號內(nèi)。錯(cuò)選、多選或未選均無分。

16.廣義表中元素分為 ( )

A.原子元素 B.表元素

C.原子元素和表元素 D.任意元素

17.求字符串T在字符串S中首次出現(xiàn)的位置的操作稱為 ( )

A.串的模式匹配 B.求子串

C.求串的長度 D.串的連接

18.樹型結(jié)構(gòu)最適合用來描述 ( )

A.有序的數(shù)據(jù)元素 B.無序的數(shù)據(jù)元素

C.數(shù)據(jù)元素之間的具有層次關(guān)系的數(shù)據(jù) D.數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)

19.若二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)_______個(gè)葉結(jié)點(diǎn)。 ( )

A.25 B.30

C.31 D.41

20.若深度為6的完全二叉樹的第6層有3個(gè)葉結(jié)點(diǎn)，則該二叉樹一共有______個(gè)結(jié)點(diǎn)。 ( )

A.15 B.16

C.17 D.18

21.若某完全二叉樹的深度為h，則該完全二叉樹中至少有______個(gè)結(jié)點(diǎn)。 ( )

A.2h B.2h-1

C.2h-1-1 D.2h-1+1

22.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該 ( )

A.只有左子樹上的所有結(jié)點(diǎn) B.只有左子樹上的部分結(jié)點(diǎn)

C.只有右子樹上的所有結(jié)點(diǎn) D.只有右子樹上的部分結(jié)點(diǎn)

23.對于任意非空二叉樹，要設(shè)計(jì)出其后序遍歷的非遞歸算法而不使用堆棧結(jié)構(gòu)，最適合的方法是對該二叉樹采用_______存儲結(jié)構(gòu)。 ( )

A.三叉鏈表 B.二叉鏈表

C.順序 D.索引

24.對于一個(gè)數(shù)據(jù)序列，按照“逐點(diǎn)插入方法”建立一個(gè)二叉排序樹，該二叉排序樹的形狀取決于 ( )

A.該序列的存儲結(jié)構(gòu) B.序列中的數(shù)據(jù)元素的取值范圍

C.數(shù)據(jù)元素的輸入次序 D.使用的計(jì)算機(jī)的軟、硬件條件

25.下面關(guān)于哈夫曼樹的說法，不正確的是 ( )

A.對應(yīng)于一組權(quán)值構(gòu)造出的哈夫曼樹一般不是唯一的

B.哈夫曼樹具有最小帶權(quán)路徑長度

C.哈夫曼樹中沒有度為1的結(jié)點(diǎn)

D.哈夫曼樹中除了度為1的結(jié)點(diǎn)外，還有度為2的結(jié)點(diǎn)和葉結(jié)點(diǎn)

三、填空題 (本大題共10小題，每小題2分，共20分)

請?jiān)诿啃☆}的空格上填上正確答案。錯(cuò)填、不填均無分。

26.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的_________倍。

27.圖的深度優(yōu)先搜索方法類似于二叉樹的_________遍歷。

28.帶權(quán)連通圖G=,其中V={v1,v2,v3,v4,v5},E={(v1,v2)7,

29.數(shù)據(jù)文件最重要的操作除了插入、刪除、修改和查找外，還有_________。

30.將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個(gè)一維數(shù)組中，然后采用折半查找方法查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為_________。

31.在索引表，若一個(gè)索引項(xiàng)對應(yīng)基本數(shù)據(jù)中一條記錄，則稱此索引為稠密索引；若索引表中一個(gè)索引對應(yīng)基本數(shù)據(jù)中的若干記錄，則稱此索引為_________索引。

32.每趟排序從未排序的子序列中依次取出元素與已經(jīng)排好序的序列中元素進(jìn)行比較，然后將其放在已經(jīng)排好序的序列的合適位置。這種排序法稱為_________排序法。

33.從未排序序列中選擇一個(gè)元素，該元素將當(dāng)前參加排序的那些元素分成前后兩個(gè)部分，前一部分中所有元素都小于等于所選元素，后一部分中所有元素都大于或等于所選元素，而此時(shí)所選元素處在排序的最終位置。這種排序法稱為_________排序法。

34.謝爾排序法、快速排序法、堆積排序法和二路歸并排序法四種排序法中，要求輔助空間最多的是_________。

35.對序列(49,38,65,97,76,27,13,50)采用快速排序法進(jìn)行排序，以序列的第一個(gè)元素為基準(zhǔn)元素得到的劃分結(jié)果是__________________。

四、問題求解題 (本大題共2小題，每小題10分，共20分)

36.已知某非空二叉排序樹采用順序存儲結(jié)構(gòu)依次將所有結(jié)點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組

ABDIC□EF□□C□□□H

請分別寫出該二叉樹的前序遍歷序列與中序遍歷序列。

37.已某個(gè)不帶權(quán)的無向圖采用鄰接矩陣存儲方法依次將頂點(diǎn)的數(shù)據(jù)信息存放于一維數(shù)組ABCDEFGH中，邊的信息存放于鄰接矩陣中，鄰接矩陣為

0 1 1 0 0 0 0 0

1 0 0 0 1 0 1 1

1 0 0 1 0 1 0 0

0 0 1 0 0 1 0 0

0 1 0 0 0 0 0 1

0 0 1 1 0 0 0 0

0 1 0 0 0 0 0 0

0 1 0 0 1 0 0 0

請寫出從頂點(diǎn)A出發(fā)對該圖進(jìn)行深度有限搜索后得到的頂點(diǎn)序列。

五、算法填空題 (本大題共2小題，共25分)

38.已知長度為n的線性表A=(a1,a2,...,an-1,an)采用順序存儲結(jié)構(gòu)，請寫出一算法，將線性表轉(zhuǎn)換為A'=(an,an-1,...,a2,a1)，要求轉(zhuǎn)換過程中盡可能少的輔助空間。

procedure REVERSE(A,n)

for i←1 to _____ do

temp←A[i]

___________________

___________________ // 這三條語句是交換A中兩個(gè)元素的位置 //

end

end

39.設(shè)非空二叉樹采用二叉鏈表儲存結(jié)構(gòu)，根結(jié)點(diǎn)的指針為T，下面是利用前序遍歷的非遞歸方法刪除該二叉樹該二叉樹中數(shù)據(jù)域內(nèi)容為item的那個(gè)葉結(jié)點(diǎn)的算法。這里，假設(shè)算法中用到的堆棧采用順序存儲結(jié)構(gòu)，并且空間足夠大。

請?jiān)谒惴ǖ目瞻滋幪钊脒m當(dāng)內(nèi)容，使之能夠正常工作。

procedure DELLEAF(T)

top←0 // 堆棧初始置空 //

p←T

repeat

while (p≠nil) do

if __________________________________ then

// 找到了滿足條件的結(jié)點(diǎn)(葉結(jié)點(diǎn))//

[if _______________ then // 若滿足條件的結(jié)點(diǎn)是根結(jié)點(diǎn) //

T←nil

else // 若滿足條件的結(jié)點(diǎn)不是根結(jié)點(diǎn) //

if ______________ then

lchild(q)←nil // 被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)的左指針域置空 //

else

rchild(q)←nil // 被刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)的右指針域置空 //

call RET(p) // 釋放被刪除結(jié)點(diǎn)的存儲空間 //

return]

top←top+1

STACK[top]←p // p 所指結(jié)點(diǎn)的地址進(jìn)棧 //

q←p // 記錄p 所指結(jié)點(diǎn)的雙親結(jié)點(diǎn)的地址 //

p←lchild(p) // p 向下指向其左孩子結(jié)點(diǎn) //

end

p←STACK[top] // 棧頂元素(結(jié)點(diǎn)的地址)退棧送p //

top←top-1

q←p // 記錄p 所指結(jié)點(diǎn)的雙親結(jié)點(diǎn)的地址 //

p←rchild(p)

until ________________________ // p 向下指向其右孩子結(jié)點(diǎn) //

end

總結(jié)

以上是生活随笔為你收集整理的计算机系数据结构03年试题答案,03年北京文考“数据结构”试题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。