山東財(cái)經(jīng)大學(xué)成人高等教育期末考試-算法與數(shù)據(jù)結(jié)構(gòu)-17專科計(jì)算機(jī)復(fù)習(xí)資料

算法與數(shù)據(jù)結(jié)構(gòu)17專科計(jì)算機(jī)復(fù)習(xí)資料

一、單選題

在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行

（B）。

A.HL=p;p->next=HL;B.p->next=HL->next;HL->next=p;

C.p->next=HL;p=HL;D.p->next=HL;HL=p;

若順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,則該隊(duì)列最多可存儲(chǔ)（B）個(gè)元

素.A.nB.n-1C.n+1D.不確定

下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？（A）

A.存儲(chǔ)密度大B.插入和刪除運(yùn)算方便

C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快

設(shè)有一個(gè)二維數(shù)組A[m][n],假設(shè)A[0][0]存放位置在600,陽，A[3][3]存放位置在678<⑹，

每個(gè)元素占一個(gè)空間，問A[2][3]n。）存放在什么位置？（腳注（⑹表示用10進(jìn)制表示,m〉3）C

A.658B.648C.633D.653

下列關(guān)于二叉樹遍歷的敘述中，正確的是（D）。

A.若一個(gè)樹葉是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序遍歷最

后—個(gè)結(jié)點(diǎn)

B.若二窄點(diǎn)是某二叉樹的前序遍歷最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷的最后

一個(gè)結(jié)點(diǎn)

C.春二個(gè)結(jié)點(diǎn)是某二叉樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的前序最后一

個(gè)結(jié)點(diǎn)

D.若二個(gè)樹葉是某二叉樹的前序最后一個(gè)結(jié)點(diǎn)，則它必是該二叉樹的中序遍歷最后一個(gè)

結(jié)點(diǎn)

k層‘二叉樹的結(jié)點(diǎn)總數(shù)最多為（A）.

A.2k-1B.2K+1C.2K-1D.2k-1

對(duì)線性表進(jìn)行二分法查找，其前提條件是（C）.

A.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

B.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

C.線性表以順序方式存儲(chǔ)，并且按關(guān)鍵碼值排好序

D.線性表以鏈接方式存儲(chǔ)，并且按關(guān)鍵碼值的檢索頻率排好序

對(duì)n個(gè)記錄進(jìn)行堆排序，所需要的輔助存儲(chǔ)空間為（C）

A.O（log2n）B.O（n）C.O（1）D.O（n2）

對(duì)于線性表（7,34,77,25,64,49,20,14）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%7

作為散列函數(shù)，則散列地址為0的元素有（D)個(gè),

A.1B.2C.3D.4

下列關(guān)于數(shù)據(jù)結(jié)構(gòu)的敘述中，正確的是（D).

A.數(shù)組是不同類型值的集合

B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉

C.樹是一種線性結(jié)構(gòu)

D,用一維數(shù)組存儲(chǔ)一棵完全二叉樹是有效的存儲(chǔ)方法

在決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮（A）o

A.各結(jié)點(diǎn)的值如何B.結(jié)點(diǎn)個(gè)數(shù)的多少

C.對(duì)數(shù)據(jù)有哪些運(yùn)算D.所用的編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便

需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其存儲(chǔ)結(jié)構(gòu)是（B）。

A.單鏈表B.靜態(tài)鏈表C.線性鏈表D.順序存儲(chǔ)結(jié)構(gòu)

設(shè)指針變量p指向單鏈表中結(jié)點(diǎn)A,若刪除單鏈表中結(jié)點(diǎn)A,則需要修改指針的操作序列

為（A

A.q=p->next；p->data=q->data；p->next=q->next；free（q）；

B.q=p->next；q->data=p->data；p->next=q->next；free（q）；

C.q=p->next；p->next=q->next；free（q）；

D.q=p->next；p->data=q->data；free(q)；

設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E,下列(C)是不可能的出棧

序列。

A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A

一個(gè)非空廣義表的表頭(D)。

A.不可能是子袤B.只能是子表

C.只能是原子D.可以是子表或原子

設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行

出隊(duì)操作后其頭指針front值為(D)。

A.front=front+lB.front=(front+1)%(m-1)

C.front=(front-1)%mD.front=(front+1)%m

若串S='software',其子串的數(shù)目是(B)。

A.8B.37C.36D.9

在線索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來說明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還

是線索化信息，若0標(biāo)識(shí)樹結(jié)構(gòu)信息，1標(biāo)識(shí)線索，對(duì)應(yīng)葉結(jié)點(diǎn)的左右鏈域，應(yīng)標(biāo)識(shí)為

(D)。

A.00B.01C.10D.11

以下說法錯(cuò)誤的是(B)o

A.散列法存儲(chǔ)的思想是由關(guān)鍵字值決定數(shù)據(jù)的存儲(chǔ)地址

B.散列表的結(jié)點(diǎn)中只包含數(shù)據(jù)元素自身的信息，不包含指針

C.負(fù)載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的飽滿程度

D.散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處理沖突的方法。

設(shè)一組初始記錄關(guān)鍵字序列(5,2,6,3,8),以第一個(gè)記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速

排序的結(jié)果為(C)?

A.2,3,5,8,6B.3,2,5,8,6

C.3,2,5,6,8D.2,3,6,5,8

二、填空題

了前程序段的時(shí)間復(fù)雜度為—0(22)________

product=1;

for(i=n;i>0;i—)

for(j=i+l;j<n;j++)

product*=j;

若以鄰接軸陣表示看向圖，則鄰接矩陣上第i行中非零元素的個(gè)數(shù)即為頂點(diǎn)vi的出度。

假定一棵樹的廣義表表示為A(D(E,G),H(I,J)),則樹中所含的結(jié)點(diǎn)數(shù)為7

個(gè)，樹的深度為2,樹的度為2。

后綴算式79230+-42/*的值為94。中綴算式(3+X*Y)-2Y/3

對(duì)應(yīng)的后綴算式為—3XY*+2Y*3/-o

在一個(gè)具有10個(gè)頂點(diǎn)的無向完全圖中，包含有45條邊，在一個(gè)具有n個(gè)頂點(diǎn)

的有向完全圖中，包含有____n(nzl)條邊。

數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)和圖結(jié)構(gòu)四種。

一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2,其數(shù)量級(jí)表示為0(n)一。

對(duì)于一個(gè)長度為n的單鏈存儲(chǔ)的隊(duì)列，在表頭插入元素的時(shí)間復(fù)雜度為0(1),在表

尾插入元素的時(shí)間復(fù)雜度為0(1)。

假定一個(gè)線性表為(12,17,74,5,63,49,82,36),若按Key/4條件進(jìn)行劃分，使得同一余

數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為(12,36)(17,5,49)(74,

82)和(63)。

對(duì)一棵B_樹進(jìn)行刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并時(shí)，會(huì)使新樹的高度比原

樹的高度減少1(或減少)。

在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為—O(nlog2n)______,整

個(gè)堆排序過程的時(shí)間復(fù)雜度為—O(nlog2n)_

空串的長度是0.；空格串的長度是空格的戮耳.。

在一棵度為3的樹中，度為-2的結(jié)點(diǎn)個(gè)數(shù)是1,國為0的結(jié)點(diǎn)個(gè)數(shù)是6,則度為4.的結(jié)點(diǎn)

個(gè)數(shù)是2

在串S=Structure7'中，以t為首字符的子串有12個(gè)。

在線性表的散列存儲(chǔ)中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待

散列存儲(chǔ)的元素的個(gè)數(shù)，則a等于一n/m_o

當(dāng)問題的規(guī)模n趨向無窮大時(shí)，算法執(zhí)行時(shí)間T(n)的數(shù)量級(jí)被稱為算法的，時(shí)回復(fù)圣封=

在鏈表的結(jié)點(diǎn)中，數(shù)據(jù)元素所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)量之比稱作存儲(chǔ)密度。

在一棵高度為5的理想平衡樹中，最少含有個(gè)結(jié)點(diǎn)，最多含有結(jié)點(diǎn)。

在樹中，一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的孩子(或子)結(jié)點(diǎn)____________o一個(gè)

結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的—跖親(或父)結(jié)點(diǎn)。

棧頂?shù)奈恢檬请S著—進(jìn)棧了口出棧操作而變化的。

三.判斷題

二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩

子的殖。(X)

循環(huán)鏈表不是線性表。(X)

對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須以鏈?zhǔn)椒绞酱鎯?chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列。

(X)

具有n個(gè)結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。(V)

對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(義)

廣義表(((a),b),c)的袤又是((a),b),表尾是(c)。(V)

用一一個(gè)維廣義數(shù)賣組的存表儲(chǔ)頭主版攵杲樹一時(shí)個(gè)，總廣是義以表前c(序遍X歷順)序存儲(chǔ)結(jié)點(diǎn)。(X)

強(qiáng)連通圖的各頂點(diǎn)間均可達(dá)。(V)

在平衡二叉樹中，任意結(jié)點(diǎn)左右子樹的高度差(絕對(duì)值)不超過1。(V)

四、操作題

假設(shè)以數(shù)組se哭［m］存放循環(huán)隊(duì)列的元素,設(shè)變量rear和quelen分別指示循環(huán)隊(duì)列中

隊(duì)尾元素的位亶和元素的個(gè)數(shù)。

(1)寫出隊(duì)滿的條件表達(dá)式;

(2)寫出隊(duì)空的條件表達(dá)式；

(3)浚m=40,rear=13,quelen=19,求隊(duì)頭兀素的位置;

(4)寫出一般情況下隊(duì)頭元素位置的表達(dá)式。

答：(1)quelen==m

(2)quelen==0

(3)(13-19+40)%40=34

(4)(rear-quelen+m)%m

設(shè)無向圖G(所下鼠所示)，要求給出該圖的深度優(yōu)先和廣度優(yōu)先遍歷的序列并給出該圖的

最小生成樹。

答:深度優(yōu)先遍歷序列：125364,廣度優(yōu)先遍歷序列：123456,最小生成樹T的邊集為￡={(1,

4),(1,3),(3,5),(5,6),(5,6)}

設(shè)一組有序的記錄關(guān)鍵字序列為(13,18,24,35,47,50,62,83,90),查找方法用二

分查找，要求計(jì)算出查找關(guān)鍵字62時(shí)的比較次數(shù)并計(jì)算出查找成功時(shí)的平均查找長度。

答：ASL=91*l+2*2+3*4+4*2)=25/9

已知一棵二叉樹的中序序列為ABCDEFG,層序序列為BAFEGCD,請(qǐng)畫出該二叉樹。

答：1)(A),B,(CDEFG)

2)(A),B,((CDE),F,(G))

B

AF

EG

C

\

D

五.閱讀算法

現(xiàn)面算法的功能是什么？

voidABC(BTNode*BT)

(

ifBT{

cout?BT->data?";

ABC(BT->left);

ABC(BT->right);

答：前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹。

在下面的每個(gè)程序段中，假定線性表La的類型為List,元素類型ElemType為int,并假定

每個(gè)程序段是連續(xù)執(zhí)行的。試寫出每個(gè)程序段執(zhí)行后所得到的線性表La。

(1)InitList(La);

Inta[]={100,26,57,34,79);

For(i=0;i<5;i++)

Insert(La,a[i]);

TraverseList(La);

(2)DeleteFront(La);

InsertRear(La,DeleteFront(La));

TraverseList(La);

(3)ClearList(La);

For(i=0;i<5;i++)

InsertFront(La,a[i]);

TraverseList(La);

答：(1)La=(26,34,57,79,100)

(2)La=(57,79,100,34)

(3)La=(79,34,57,26,100)

六.算法設(shè)計(jì)題

試寫出在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法，以及判斷一棵二叉樹是否是二叉排序樹

的算法

答：在解式存儲(chǔ)結(jié)構(gòu)上建立一棵二叉樹的算法。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

voidcreatebitree(bitree*&bt)

(

charch;scanf(n%cn,&ch);

{bt=O;return;}

bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;

createbitree(bt->lchild);createbitree(bt->rchild);

判斷一棵二叉樹是否是二叉排序樹的算法。

intminnum=-32768,flag=l;

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidinorder(bitree*bt)

(

if(bt!=O)

{inorder(bt->lchild);if(minnu