甘肅省2024年專升本計算機(jī)科學(xué)與技術(shù)專業(yè)習(xí)題11(師大2024真題)

西北師范高校2024年專升本真題（數(shù)據(jù)結(jié)構(gòu)）

我要升本網(wǎng)第11期

班別學(xué)號姓名成果

一、單項選擇（母小題2分，共24分）

1.若某線性表的常用操作是取第i個元素及其前趨元素，則采納（A）存儲方式最節(jié)約時間

A.依次表B.單鏈表

C.雙鏈表D.單向循環(huán)

2.市是隨意有限個（B）

A.符號構(gòu)成的序列B.字符構(gòu)成的序列

C.符號構(gòu)成的集合D.字符構(gòu)成的集合

3.設(shè)矩陣K=i,j<=10）的元素滿意:

^jj<>0（i>=j:l<=i,j<=10）,aij=0（i<j,l<=i,j<=10）

若將A的全部非0元素以行為主序存于首地址為2000的存儲區(qū)域中，每個元素占4個單元，

則元素A[59]的首地址為（C）

A.2340B.2336C.2220D.2160

4.假如以鏈表作為棧的存儲結(jié)構(gòu)，則退棧操作時（D）

A.必需判別棧是否滿干B.對棧不作任何判別

C.判別棧元素的類型D.必需判別棧是否空

5.設(shè)數(shù)組Data[0..m]作為循環(huán)隊列SQ的存儲空間,front為隊頭指針,rear為隊尾指針,

則執(zhí)行出隊操作的語句為（A）

A.front=（front+l）%（m+l）B.front=（front+l）%m

C.rear=（rear+l）%mD.front=front+l

6.深度為6（根的層次為D的二叉樹至多有（B）結(jié)點

A.64B.63C.31D.32

7.將含100個結(jié)點的完全二叉樹從根這一層起先，每層從左至右依次對結(jié)點編號，根結(jié)點的

編號為1。編號為47的結(jié)點X的雙親的編號為（C）

A.24B.25C.23D.2無法確定

8.設(shè)有一個無向圖G=（V,E）和G'=（V',E'）,假如G'為G的生成樹，則下面不正確的說法是（D）

A.G'為G的子圖B.G'為G的一個無環(huán)子圖

C.G'為G的微小連通子圖且V'=VD.G'為G的連通重量

9.用線性探測法查找閉散列上，可能要探測多個散列地址，這些位置上的鍵值（D）

A.肯定都是同義詞B.肯定都不是同義詞

C.都相同D.不肯定都是同義詞

10.二分查找要求被查找的表是（C）

A.鍵值有序的鏈接表B.鏈接表但鍵值不肯定有序表

C.鍵值有序的依次表1）.依次表但鍵值不肯定有序表

11.當(dāng)時始序列已經(jīng)按鍵值有序，用干脆插入法對其進(jìn)行排序，須要比較的次數(shù)為（B）

A.n"B.n-lC.log2nD.nlog2n

12.堆是一個鍵值序列值1：1（2,...,心，...，m},對：1,2,...,5/2」，滿意（A）

A.Ki<=K2iKi<=K2i+l（2i+l<=n）B.Ki<K2i<K2i+l

C.Ki<=K2i或Ki<=K2i+l（2i+l<=n）D.Ki<=K2i<=K2i+l

二、推斷題（正確的在括號內(nèi)打"V",錯的在括號內(nèi)打每小題1分，共10分）

1.雙鏈表中至多只有一個結(jié)點的后繼指針為空（V）

2.在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向?qū)嶋H的隊尾元素，隊

列為滿的條件是front=rear（X）

3.對線性表進(jìn)行插入和刪除操作時，不必移動結(jié)點。（X）

4.隊可以作為對樹的層次遍歷的一種數(shù)據(jù)結(jié)構(gòu)。（V）

5.在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b>.（X）

6.對有向圖G,假如從任一頂點動身進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜尋就能訪問每個頂點，

則該圖肯定是完全圖。（X）

7.”二分查找法"必需在有序表上進(jìn)行。（V）

8.向二叉排序樹中插入一個新結(jié)點時，新結(jié)點肯定成為二叉排序樹的一個葉子結(jié)點。（V）

9.鍵值序列{A,C,D,B,E,E：F）是一個堆。（X）

10.在二路歸并時，被歸并的兩個子序列中的關(guān)鍵字個數(shù)不行定相等。（V）

三、填空題（每空2分，共24分）

1.設(shè)r指向單鏈表最終一個結(jié)點，要在最終一個結(jié)點之后插入s所指的結(jié)點，需執(zhí)行的三條

語句是r->next=s;r=s;r?>next=NULL。

2

2.在帶頭結(jié)點單鏈表L中，表空的條件是L->next==NULL

3.設(shè)一個鏈棧的棧頂指針為Is,棧中結(jié)點格式為|info|link?？盏臈l件是

ls==NULL>若棧不空，則退棧操作為p=ls；ls=ls->link；free(p).

4.已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該

樹中有12個葉子結(jié)點。

5.樹有三種常用的存儲結(jié)構(gòu)，即孩子鏈表法，孩子兄弟鏈表法和雙親表示法。

6.n-l個頂點的連通圖的生成樹有n-2條邊。

7.一個有向圖G中若有弧<Vj,Vi>、<Vi,Vk>和<Vj,Vk>,則在圖G的拓樸序列中，頂點Vi,Vj

和Vk的相對位置為Vi?>Vi?>Vk。

8.設(shè)表中元素的初始狀態(tài)是按鍵值遞增的，分別用堆排序、快速排序、冒泡排序和歸并排序

方法對其進(jìn)行排序(按遞增依次)，胃泡排序最省時間,快速排序最費時間。

9.下面是將鍵值為X的結(jié)點插入到二叉排序樹中的算法，請在劃線處填上適當(dāng)?shù)膬?nèi)容。

typedefstructnode*pnode

structnode

{intkey;

pnodeleft,right;

)

voidsearchinsert(intx;pnodet);

//t為二叉排序樹根結(jié)點的指針〃

{if(t=NULL)

{p=malloc(size);p->key=x;p->left=ml;p->nght=ml;t=p;}

elseif(x<t->kcy)scarchinscrt(x,t->lcft)

elsesearchinsert(x.t->right):

I

四、應(yīng)用題(本題共28分)

I.給定權(quán)值{5,10,12,15,30,40},構(gòu)造相應(yīng)的哈夫曼樹，要求寫出構(gòu)造步驟。(4分)

哈夫曼樹構(gòu)造步驟：

3

⑤⑩???①)

⑴150。??①)

(5)00)

2.已知一表為(Jan,Feb,Mar,Apr,MayjunJul,Aug,Sep,Oct,Nov,Dec),按表中依次依次插入初始

為空的二叉排序樹，要求：

(1)在右邊畫出建立的二叉排序樹。(4分)

(2)求出在等概率狀況卜查找勝利的平均查找長度。(2分)

ASLsu=(1+2*2+3*3+4*3+5*2+6)/12=42/12=3.5

3.下圖表示?個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結(jié)城市間的馬路，邊上的權(quán)表示修

建馬路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條馬路，畫出全部可能

4.已知一個無向圖的鄰接表為:(本題4分,每小題2分)

4

2V2-------q5--"4|—?fT-A

VlA

V52A

(1)畫出這個圖。

(2)以VI為動身點，對圖進(jìn)行廣度優(yōu)先搜尋，寫出全部可能的訪問序列。

V1->V2->V4->V5->V3

V1->V4->V2->V3->V5

5.設(shè)n個元素的有序表為R,K為一個給定的值，二分查找算法如下：

intbinsearch(sqlistR;keytypeK:);

(

1=1;h=n;suc=falsc;

while(l<=h)&&(!suc)do

{mid=(l+h)/2;

case

K=R[mid].key:suc=lrue;

K<R[mid].kcy:h=niid-l;

K>R[mid].key:l=mid+l

end}

if(sue)return(mid)elsereturn(O)

}

將上述算法中劃線語句改為:K<R[mid].key:h=mid.

問改動后，算法能否正常工作？請說明緣由。

若能正常工作，請給出一個查找序列和查找某個鍵值的比較次數(shù).(本題4分)

答：(1)若K在R中或大于R中的最大值，則算法能正常運行；

若K不在R中或小于R中的最大值，則算法不能正常運行，會出現(xiàn)死循環(huán);

(2)如：在[2,4,6,8]中，當(dāng)K=7時，算法出現(xiàn)死循環(huán)；

5

當(dāng)K=6時，算法能正常運行，查找勝利，比較次數(shù)為2次。

6.有一組鍵值27,84,21,47,15,25,68,35,24,采納快速排序方法由小到大進(jìn)行排序，請寫出每趟

的結(jié)果，并標(biāo)明在第一趟排序過程中鍵值的移動狀況。（本題共6分）

答：（1）每趟的結(jié)果：

（2）第一趟排序鍵值移動狀況:

五、設(shè)計題(本題共14分)

1.一棵二叉樹以二叉鏈表為存儲結(jié)構(gòu)|Ichild|dataIrchild|。設(shè)計一個算法，求在前序序

列中處于第K個位置的結(jié)點。(本題6分)

類型定義如下：

typedefstructnode*pointer;

structnode

{datatypedata;

pointerIchild,rchild;

)