05到09年福建專升本數(shù)據(jù)結(jié)構(gòu)真題詳解

第第頁05到09年福建專升本數(shù)據(jù)結(jié)構(gòu)真題詳解這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

06年轉(zhuǎn)升本數(shù)據(jù)結(jié)構(gòu)考題

一、單項(xiàng)選擇題〔共12小題，每題2分,共24分〕1、已知單鏈表結(jié)構(gòu)為structnode{intdata;

structnode*ne*t;}*p,*q,*r;

刪除單鏈表中結(jié)點(diǎn)p(由p指向的結(jié)點(diǎn))后面的結(jié)點(diǎn)的操作不正確的選項(xiàng)是__C__A、

q=p-ne*t;p-ne*t=q-ne*t;

B、p-ne*t=p-ne*t-ne*t;

C、r=p-ne*t;p-ne*t=q-ne*t;

D、

q=p-ne*t;r=q-ne*t;p-ne*t=r;

2、假設(shè)待排序?qū)ο笮蛄性谂判蚯耙呀?jīng)根據(jù)關(guān)鍵字遞增排列，那么采納__A__比較次數(shù)最少。

A、徑直插入排序O(n)B、快速排序O(n2)C、合并排序

D、簡約選擇排序O(n2)

3、圖的深度優(yōu)先遍歷類似于樹的__C__A、后序遍歷B、層次遍歷C、前序遍歷D、中序遍歷

4、求賦權(quán)有向圖的最短路徑常用的算法有___D___

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

A、Prim算法和Kruskal算法B、Prim算法和Dijkstra算法C、Kruskal算法和Dijkstra算法D、Dijkstra算法和Floyd算法

5、單鏈表中有n個(gè)結(jié)點(diǎn)，在其中查找值為*的結(jié)點(diǎn)，在查找勝利時(shí)需要比較的平均次數(shù)是___D___。A、n

B、(n-1)/2C、n/2D、(n+1)/2解答：

查詢每個(gè)元素需要比較次數(shù)之和查詢平均繁復(fù)度=

元素個(gè)數(shù)

1+2+3+...+nn+1==

n2

思索：假如查找不勝利，計(jì)算結(jié)果如何？

6、線性表采納鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址__B___A、需要是不連續(xù)的B、連續(xù)與否均可C、需要是連續(xù)的

D、和頭結(jié)點(diǎn)的存儲(chǔ)地址項(xiàng)連續(xù)

7、一棵非空的二叉樹中，設(shè)根結(jié)點(diǎn)在第0層，在第i層上最多有___D__個(gè)結(jié)點(diǎn)。A、2(i+1)B、2iC、2(i-1)D、2i

根層01個(gè)/\

AB層12個(gè)

/\/\

ABCD層24個(gè)

8、在以下的排序算法中，算法的時(shí)間繁復(fù)度是O(n*log2n)是___D__。A、冒泡排序B、簡約選擇排序C、徑直插入排序D、堆排序

9、運(yùn)用一個(gè)棧，每次限制進(jìn)棧和出棧一個(gè)元素。假設(shè)進(jìn)棧的元素序列依次是a、b、c、d；指出不可能的出棧序列___B____。A、abcdB、adbc

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

C、acbdD、dcba解答：A、push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(),B、沒方法C、push(a)、pop()、push(b)、push(c)、pop()、pop()、push(d)、pop()D、push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop()

10、設(shè)數(shù)組queue[]作為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front作為隊(duì)頭指針，rear作為隊(duì)尾指針，那么執(zhí)行出隊(duì)操作后其頭指針front的值為__A___。A、front=(front+1)%mB、front=(front+1)%(m-1)C、front=(front-1)%mD、front=front+1

解答：與方案1、2無關(guān)。

11、對(duì)圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常采納__C__來實(shí)現(xiàn)A、字符串B、B樹C、隊(duì)列E、棧

12、一個(gè)有n個(gè)結(jié)點(diǎn)k叉樹，樹中全部結(jié)點(diǎn)的度數(shù)之和是__B__。A、k+nB、n-1C、knD、n2解答：

思路1：樹中結(jié)點(diǎn)的度數(shù)=結(jié)點(diǎn)的兒子數(shù)n個(gè)結(jié)點(diǎn)k叉樹，每個(gè)結(jié)點(diǎn)最多有k個(gè)兒子，葉子沒有兒子，因此答案不是k*n。思路2：正確的做法：

樹中全部結(jié)點(diǎn)的度數(shù)之和=樹中全部邊條數(shù)，

每一條邊指向一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有一條天線，指向父親結(jié)點(diǎn)，除了根結(jié)點(diǎn)之外。故答案是B，n-1

二、填空題〔共8小題，11空，每空2分,共22分〕

13、已知二叉樹后序列表為CEDBA，中序列表為CBEDA，那么它的前序列表為__ABCDE__。

解答：后序列表為CEDBA，因此根是A，

中序列表為CBEDA，因此根只有左子樹CBED，沒有右子樹

A/

CEDB后序，根是B

CBED中序，左子樹C，右子樹ED

A/B

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

/\

CED后序

ED中序A/B

/\

CD

/E

14、N個(gè)結(jié)點(diǎn)的有向圖，最多有___N*(N-1)_____條邊。

15、存儲(chǔ)圖的最常用方法有兩種，它們是___鄰接矩陣____和____鄰接表____。16、設(shè)有一個(gè)閉散列表的容量為m，用線性探測(cè)法解決沖突，要插入一個(gè)鍵值，假設(shè)插入勝利，至多要進(jìn)行______比較。

17、一棵哈夫曼樹有29個(gè)結(jié)點(diǎn)，其葉子的個(gè)數(shù)是___15____。解答：哈夫曼樹沒有度為1的結(jié)點(diǎn)，葉子數(shù)=內(nèi)結(jié)點(diǎn)數(shù)+1結(jié)點(diǎn)總數(shù)

=葉子數(shù)+內(nèi)結(jié)點(diǎn)數(shù)=2*葉子數(shù)-1=2*內(nèi)結(jié)點(diǎn)數(shù)+1

18、已知單鏈表的結(jié)點(diǎn)定義為structnode{intdata;

structnode*ne*t;};

在單鏈表中搜尋結(jié)點(diǎn)p(由指向的結(jié)點(diǎn))的后繼結(jié)點(diǎn)的操作是____p=p-ne*t___。19、已知雙鏈表結(jié)點(diǎn)定義為structnode{intdata;

structnode*left,*right;};

雙鏈表中結(jié)點(diǎn)的left和right分別指向前驅(qū)和后繼結(jié)點(diǎn)，在雙鏈表中刪除結(jié)點(diǎn)p(由指向的結(jié)點(diǎn))的操作是：p-left-right=___p-right______；和p-right-left=___p-left_____。

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

20、對(duì)于隊(duì)列，只能在__隊(duì)尾___插入元素，在___隊(duì)頭____刪除元素。三、應(yīng)用題〔共4小題，每題8分，共32分〕21、對(duì)圖1所示的樹

〔1〕結(jié)點(diǎn)A的度是_____3______。〔2〕樹的度是______3_____。

〔3〕畫出其轉(zhuǎn)換成相應(yīng)二叉樹的樹形A

/|\BCD

/\/\EFGH/

I

解答：一般樹轉(zhuǎn)換成二叉樹步驟：

將父親管理兒子方式改為父親管理大兒子，

大兒子管理二兒子〔二兒子變成大兒子的右孩子〕

二兒子管理三兒子〔三兒子變成二兒子的右孩子〕

AABEFCDGIH前

/EFBCIGHDA中B

/\FEIHGDCBA后EC\\FD

/G/\IH

22、已知參與排序的正整數(shù)序列是：90、70、180、30、520、40、60、80、50、130。以第一個(gè)元素90作為基準(zhǔn)元素，依據(jù)快速排序算法，寫出完成第一趟劃分后序列重新排列的狀況。

60、70、50、30、80、40、90、520、180、130

23、一次輸入如下序列中的各個(gè)整數(shù)，構(gòu)造其相應(yīng)的二叉搜尋樹，只需要畫出最末生成的二叉搜尋樹的樹形。整數(shù)序列是180、160、250、300、170、120、125、290、380。

180

/\160250/\\120170300

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

\/\

125290380

24、用Prim算法求圖2所示的無向帶權(quán)連通圖的最小生成樹。要求依次畫出從頂點(diǎn)1出發(fā)的最小生成樹的生成過程。

四、算法設(shè)計(jì)〔共2小題，第25小題10分，第26小題12分，共22分〕25、二叉樹以二叉表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)的定義如下，請(qǐng)寫出一個(gè)求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)的算法。

typedefstructbtnode*btlink;structbtnode{

TreeItemelement;btlinkleft;btlinkright;}Btnode

解答：與05年考題不一樣

intf(指向樹根的指針){//f()計(jì)算樹中葉子節(jié)點(diǎn)的個(gè)數(shù)if(指向樹根的指針==NULL)return0;

*=f(指向樹根的左孩子指針);//左子樹中葉節(jié)點(diǎn)數(shù)；y=f(指向樹根的右孩子指針);//右子樹中葉節(jié)點(diǎn)數(shù)；if(root-left==NULLroot-right==NULL)return1;

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

elsereturn*+y;/*或者

if(*==0y==0)return1;elsereturn*+y;*/}

intf(btlinkroot){//f()計(jì)算樹中葉子節(jié)點(diǎn)的個(gè)數(shù)if(root==NULL)return0;

*=f(root-left);//左子樹中葉節(jié)點(diǎn)數(shù)；y=f(root-right);//右子樹中葉節(jié)點(diǎn)數(shù)；if(*==0y==0)return1;elsereturn*+y;}

T(n)=1+T(n1)+T(n2)n1+n2=n

=1+1+T(n11)+T(n12)+1+T(n21)+T(n22)n1=n11+n12n2=n21+n22

25、二叉樹以二叉表為存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)的定義如下，請(qǐng)寫出一個(gè)求二叉樹的高度算法。解答：

inth(指向樹根的指針){//f()計(jì)算樹高度if(指向樹根的指針==NULL)return0;

*=h(指向樹根的左孩子指針);//左子樹高度；y=h(指向樹根的右孩子指針);//右子樹高度；if(*y)return*+1;elsereturny+1;

//return(*y?*:y)+1;}

26、閱讀以下程序，它是在已知的數(shù)組a中查找數(shù)值為*的元素，假如存在那么輸出“found”，否那么輸出“notfound”。試問它是什么方法實(shí)現(xiàn)的？并請(qǐng)完善程序。

用__________查找法。#defineN10

voidbs(inta[],int*){intl,r,m;l=0;r=N-1;

m=___(l+r)/2______;

while((_____l=r_______)(*!=a[m])){if(*a[m])l=_____m+1______;elser=m-1;m=(l+r)/2;}

if(___l=r____)

printf(notfound);else

printf(found);}

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

main(){

inta[N]={10,20,30,40,50,60,70,80,90,100};int*;

printf(input*:=);scanf(%d,*);bs(____a,*_______);}

05專升本數(shù)據(jù)結(jié)構(gòu)考題

一、單項(xiàng)選擇題：〔每題2分，共24分〕

1、雙向鏈表的一個(gè)結(jié)點(diǎn)有(B)個(gè)指針。A、1B、2C、0D、3

2、在n個(gè)結(jié)點(diǎn)的順次表中，算法的時(shí)間繁復(fù)度都是O(1)的操作是(A)。A、訪問第i個(gè)結(jié)點(diǎn)(1≤i≤n)和求第i個(gè)結(jié)點(diǎn)的徑直前趨(2≤i≤n)B、在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1≤i≤n)C、刪除第i個(gè)結(jié)點(diǎn)(1≤i≤n)D、將n個(gè)結(jié)點(diǎn)從小到大排序

3、在隊(duì)列中存取數(shù)據(jù)的原那么是(A)。A、先進(jìn)先出B、后進(jìn)后出?C、先進(jìn)后出D、不進(jìn)不出

4、在棧中，出棧操作的時(shí)間繁復(fù)度為(A)。A、O(1)B、O(logn)C、O(n)D、O(n*n)

5、設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，假設(shè)只設(shè)頭指針，那么人隊(duì)操作的時(shí)間繁復(fù)度為(C)。A、O(1)B、0(logn)C、0(n)D、O(n*n)

6、假如二叉樹的葉結(jié)點(diǎn)數(shù)為n0，那么具有雙分支的結(jié)點(diǎn)數(shù)n2等于(D)。A、nO+lB、n0C、2*n0D、n0-1

7、一棵二叉樹滿意以下條件：對(duì)任一結(jié)點(diǎn)，假設(shè)存在左、右子樹，那么其值都小于它的左子樹上全部結(jié)點(diǎn)的值，而大于右子樹上全部結(jié)點(diǎn)的值。現(xiàn)采納(B)遍歷方式就可以得到這棵二叉樹全部結(jié)點(diǎn)的遞增序列。A、先根B、中根

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

C、后根D、層次

8、用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，其非遞歸算法通常采納(A)來實(shí)現(xiàn)算法。

A、棧B、隊(duì)列C、樹D、圖

9、廣度優(yōu)先遍歷類似于二叉樹的(D)。A、先序遍歷B、中序遍歷C、后序遍歷D、層次遍歷

10、在一個(gè)有向圖中，全部頂點(diǎn)的人度之和等于全部頂點(diǎn)的出度之和的(B)。A、1／2倍B、1倍C、2倍D、4倍

11、任何一個(gè)帶權(quán)無向連通圖的最小生成樹(B)。A、只有一棵B、一棵或多棵C、肯定有多棵D、可能不存在

12、設(shè)非空單鏈表的數(shù)據(jù)域?yàn)閐ata，指針域?yàn)閚e*t，指針P指向單鏈表的第i個(gè)結(jié)點(diǎn)，s指向生成的新結(jié)點(diǎn)，現(xiàn)將s結(jié)點(diǎn)插入到單鏈表中，使其成為第i結(jié)點(diǎn)，以下算法段能正確完成上述要求的是(C)。A、s-ne*t=p-；p-ne*t=s

B、p-ne*t=s；s-ne*t=p-ne*t；

C、S-ne*t=p-ne*t；p-ne*t=s；交換p-data和s-dataD、p=s；s-ne*t=p

二、填空題〔每空2分，共20分〕

1、數(shù)據(jù)的規(guī)律結(jié)構(gòu)反映_____成分?jǐn)?shù)據(jù)規(guī)律關(guān)系______。

2、對(duì)于隊(duì)列，只能在___隊(duì)尾_____插入元素，在____隊(duì)頭_____刪除元素。3、算法是一運(yùn)算序列，它應(yīng)有：有限性、____確定性____、可行性、可以無任何輸入，但需要___有輸出____。

4、由一棵二叉樹的前序序列和____中序序列____可唯一確定這棵二叉樹的結(jié)構(gòu)。

5、假如圖的存儲(chǔ)結(jié)構(gòu)用____鄰接表/鄰接矩陣___表示，從某指定頂點(diǎn)作為初始點(diǎn)進(jìn)行廣度優(yōu)先搜尋，得到的廣度優(yōu)先搜尋序列唯一。

6、用Dijkstra算法求某一頂點(diǎn)到其余各頂點(diǎn)間的最短路徑是按路徑長度____遞增___的次序來得到最短路徑的。

7、線性表(a1，a2，a3，an)(n=1)中，每個(gè)元素占c個(gè)存儲(chǔ)單元，m為a1首地址，那么按順次存儲(chǔ)方式存儲(chǔ)線性表，ai存儲(chǔ)地址是_____m+(i-1)*c___。8、n個(gè)結(jié)點(diǎn)的無向圖，最多有___n*(n-1)/2__條邊。三、應(yīng)用題(本大題共4小題，每題8分，共32分)

1、用Prim算法求下列圖連通的帶權(quán)圖的最小代價(jià)生成樹，在算法執(zhí)行的某一刻，已選取的頂點(diǎn)集合U=[1，2，3]，邊的集合TE=[(1，2)，(2，3)]，要選取下一條權(quán)值最小的邊，應(yīng)當(dāng)從哪些邊中選擇?

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

2、假設(shè)用插入排序方法對(duì)線性表(25，84，21，47，]5，27，68，35，20)進(jìn)行排序時(shí)，請(qǐng)給出前四趟排序結(jié)點(diǎn)序列的改變狀況。答：25

2584212584212547843、已知一棵二叉樹的中序序列和后序序列分別為BDCEAFHG和DECBHGFA，請(qǐng)畫出該二叉樹。

A/\

BDCEFHG中DECBHGF后

4、設(shè)將整數(shù)a，b，c，d依次進(jìn)棧，請(qǐng)回答：假設(shè)入、出棧次序?yàn)镻ush(a)，Pop()，Push(b)，Push(c)，Pop()，Push(d)，Pop()，那么出棧的字符序列是什么?答：acd

四、算法設(shè)計(jì)(本大題共3小題，每題8分，共24分)

1、二叉樹以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，類型聲明如下，請(qǐng)寫出一個(gè)求二叉樹中結(jié)點(diǎn)個(gè)數(shù)的算法。

typedefstructnode{datatypedata；

structnode*Lchild；structnode*Rchild；}BinaTree；

答：intf(BinaTree*t){

if(t==NULL)return;else

returnf(t-left)+f(t-right)+1;

}

2、設(shè)線性表用順次結(jié)構(gòu)實(shí)現(xiàn)，聲明如下：typedefstructsqlist{chardata[ma*size]；intn；

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

請(qǐng)寫一個(gè)算法，判斷其是否回文?(順讀與倒讀一樣如：“ababbaba為回文)答：

解法1：形參和實(shí)參徑直傳遞結(jié)構(gòu)變量#includestdio.h

#defineMA*LENGTH100

typedefstructsqlist{

chardata[MA*LENGTH];intn;}Sqlist;

voidf(Sqlista){inti;

if(a.n=0)return;

for(i=0;i(a.n)/2;i++){

if(a.data[i]!=a.data[a.n-i]){

printf(No);return;

}

printf(Yes);}}

voidmain(){Sqlists;

printf(輸入n:);scanf(%d,s.n);

printf(輸入字符串:);scanf(%s,s.data);f(s);}

解法2：形參是指針變量，實(shí)參是結(jié)構(gòu)變量地址值voidf(Sqlist*a){inti;

if(a-n=0)return;for(i=0;i(a-n)/2;i++)

if(a-data[i]!=a-data[a-n-i-1]){printf(No);return;}

printf(Yes);}

voidmain(){

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

printf(inputn:);scanf(%d,(s.n));printf(inputdata:);scanf(%s,s.data);f(s);}

解法3：類似解法2，為指針變量定義了類型List#includestdio.h

#defineMA*LENGTH100

typedefstructsqlist*List;

typedefstructsqlist{

chardata[MA*LENGTH];intn;}Sqlist;

voidf(Lista){inti;

if(a-n=0)return;for(i=0;i(a-n)/2;i++)

if(a-data[i]!=a-data[a-n-i-1]){printf(No);return;}

printf(Yes);}

voidmain(){Sqlists;

printf(inputn:);scanf(%d,(s.n));printf(inputdata:);scanf(%s,s.data);f(s);}

3、閱讀以下程序，判斷它是用什么方法實(shí)現(xiàn)排序(升序)的?并完善以下程序。#includestdio.h

voidbubble(int[],int);

main(){

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

intarray[]={55，2，6，4，32，12，9，73，26，37};intsize=sizeof(array)/sizeof(int)；bubble(_array,10___)；}

voidbubble(inta[]，intsize){inti，temp；

intend_____=0__________；intpass=1；

//=======================while(!endpasssize){end=1；

for(i=0，isize-pass；i++)if(—a[i]a[i+1]—){temp=a[i]；a[i]=a[i+1]；a[i+1]=temp；

end=___0__________；}

__pass++__________________;}

//=======================for(i=0；isize；i++)printf(%d，a[i])；}

第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)〔共100分〕

一、單項(xiàng)選擇題〔本大題共12小題，每題2分，共24分〕

在每題列出的四個(gè)備選項(xiàng)中只有一個(gè)符合題目要求，請(qǐng)將正確答案代碼填寫在答題紙相應(yīng)的位置上。寫在試卷上不得分。

1．在待排序記錄已基本有序的前提下,下述排序方法中效率最高的是：

A)徑直插入排序B)簡約選擇排序C)快速排序D)歸并排序

2．以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？

A)棧B)閉散列表C)線索二叉樹D)雙向鏈表

3．有6個(gè)元素6,5,4,3,2,1的順次進(jìn)棧，問以下哪一個(gè)不是合法的出棧序列：

A)5,4,3,6,1,2B)4,5,3,1,2,6C)3,4,6,5,2,1D)2,3,4,1,5,64．下述哪一條是順次存儲(chǔ)方式的優(yōu)點(diǎn)？

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

C)刪除運(yùn)算方便D)可方便地用于各種規(guī)律結(jié)構(gòu)的存儲(chǔ)表示5．對(duì)于只在表的首、尾進(jìn)行插入操作的線性表，宜采納的存儲(chǔ)結(jié)構(gòu)為:

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

A)順次表B)用頭指針表示的單循環(huán)鏈表C)用尾指針表示的單循環(huán)鏈表D)單鏈表6．對(duì)包含n個(gè)元素的散列表進(jìn)行查找，平均查找長度

A)為O(log2n)B)為O(n)C)為O(nlog2n)D)不徑直依靠于n7．以下哪一種圖的鄰接矩陣是對(duì)稱矩陣？

A)有向圖B)無向圖C)AOV網(wǎng)D)AOE網(wǎng)

8.設(shè)表(a1,a2,a3,,a32)中的元素已經(jīng)按遞增順次排好序，用二分法檢索與一個(gè)給定的值k相等的元素，假設(shè)a1ka2，那么在檢索過程中比較的次數(shù)是：A)3B)4C)5D)69.具有3個(gè)結(jié)點(diǎn)的二叉樹最多可有多少種不同的形態(tài)。

A〕2B〕3C〕4D〕5

10．對(duì)二叉樹從1開始編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左右孩子的編號(hào)，同一個(gè)結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，那么可采納的編號(hào)方法是：

A、先序遍歷B、中序遍歷C、后序遍歷D、從根開始進(jìn)行層次遍歷

11.在長度為n的順次表的第i(1≤i≤n+1)個(gè)位置上插入一個(gè)元素，元素的

移動(dòng)次數(shù)為：

A)n-i+1B)n-iC)iD)i-112.對(duì)于一個(gè)無向圖，以下說法正確的選項(xiàng)是

A)每個(gè)頂點(diǎn)的入度大于出度；

B)每個(gè)頂點(diǎn)的度等于其入度與出度之和；C)無向圖的鄰接矩陣肯定是對(duì)稱矩陣；

D)有向圖中全部頂點(diǎn)的入度之和大于全部頂點(diǎn)的出度之和；

二、填空題〔本大題共10小題，每空2分，共22分〕

請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。

13.設(shè)一哈希表表長M為100，用除留余數(shù)法構(gòu)造哈希函數(shù)，即H〔K〕=K%P

〔P=M〕,為使函數(shù)具有較好性能，P應(yīng)選97

14.N個(gè)結(jié)點(diǎn)的二叉樹采納二叉鏈表存放，共有空指針域個(gè)數(shù)為15.假設(shè)一個(gè)算法中的語句頻度之和為T(n)=3720n+4nlogn，那么算法的時(shí)間繁復(fù)

度為_______O(nlogn)_________。

16.已知有向圖的鄰接矩陣，要計(jì)算i號(hào)結(jié)點(diǎn)的入度，計(jì)算方法是：將累加。

17.深度為6〔根深度為1〕的二叉樹至多有18.一棵具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中，結(jié)點(diǎn)總數(shù)為。

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

19.設(shè)單鏈表結(jié)點(diǎn)的定義如下：

structnode{

intdata,

structnode*ne*t;};

要在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)子鏈表，子鏈表第一個(gè)結(jié)點(diǎn)的地址為s，子鏈表最末一個(gè)結(jié)點(diǎn)的地址為t,那么應(yīng)執(zhí)行操作：________和_________。

20.設(shè)單鏈表結(jié)點(diǎn)的定義如19題，現(xiàn)有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為head,

那么判斷該單鏈表是否為空表的條件為head-ne*t==NULL。

21.n個(gè)頂點(diǎn)的連通無向圖至少有條邊。

22.在順次存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)元素，平均需要移動(dòng)素.

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

三、應(yīng)用題：〔本大題共4小題，每題8分，共32分〕請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。

23．已知有向圖如圖1所示：

〔1〕寫出頂點(diǎn)B的度〔2分〕；

〔2〕寫出從結(jié)點(diǎn)D開始的兩個(gè)廣度優(yōu)先搜尋序列〔2分〕；〔3〕畫出該圖的鄰接表〔4分〕。解答:

〔1〕頂點(diǎn)B的度:_______3________(2分)

〔2〕_________DBCA______和_____DCBA______(2分)〔3〕(4分

)

圖1

或

24.已知二叉樹的中序序列為DBGEAFC，后序序列為DGEBFCA，畫出對(duì)應(yīng)的二叉樹。解答:

A/\

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

BC

/\/DEF/G

25.圖2表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線路花費(fèi)的代價(jià)，請(qǐng)畫出該圖的最小代價(jià)支撐樹，并計(jì)算最小代價(jià)支撐樹的權(quán)。

圖2

解答:

〔每條邊1分，畫方框的兩條邊任選一條〕

最小代價(jià)支撐樹的權(quán)=56〔3分〕

26.設(shè)一個(gè)閉散列表具有10個(gè)桶，散列函數(shù)H〔*〕=*%7，假設(shè)元素輸入順次為：

{50，42，85，22，76，19，34，68}，解決沖突用線性重新散列技術(shù)，要求畫出構(gòu)造好的散列表。

解答:〔8分，第二行每個(gè)數(shù)字1分〕

四、算法設(shè)計(jì)〔本大題共2小題，第27小題10分，第28小題12分，共22分〕請(qǐng)?jiān)诖痤}紙相應(yīng)的位置上填寫正確答案。寫在試卷上不得分。

27.二叉搜尋樹T用二叉鏈表存儲(chǔ)結(jié)構(gòu)表示，其中各元素的值均不相同。編寫算

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

法，按遞減順次打印T中各元素的值。結(jié)點(diǎn)結(jié)構(gòu)定義如下：typedefintTreeItem;

typedefstructbtnode*btlink;typedefstructbtnode{TreeItemdata;btlinkleft,right;}BTNODE;解答:

voidf(btlinkt){//或voidf(BTNODE*t)if(t){

f(t-right);

printf(%d,t-data);f(t-left);}}

28.閱讀下面程序，其功能是調(diào)整線性表中的元素，將全部奇數(shù)放在表的左邊，將全部偶數(shù)放在表的右邊。請(qǐng)?zhí)羁胀瓿稍摮绦颉！裁靠?分，共12分〕

#defineMA*SIZE100typedefintElemType;typedefstruct{

ElemTypeelem[MA*SIZE];intlast;/*末元素下標(biāo)*/

}SeqList;

voidAdjustSqlist(SeqList*L){

ElemTypetemp;inti=0,while(ij){

]%2!=0

i++;

]%2==0)

j--;

)break;

temp=L-elem[i];

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

}

}

voidmain(){

SeqList;

intr,i;}

解答:〔每空1分，共12分，大小寫不能錯(cuò)〕

⑴、_______L-last_____________⑶、_______iL-last或ij______⑸、_______j0或ij_____________⑺、_______L-elem[j]__________⑼、_______*sq_________________⑾、_______r-1_________________

⑵、_______i______________________⑷、_______j______________________⑹、_______i=j___________________⑻、______temp__________________⑽、_______SeqList*_____________⑿、_______sq-elem[i]____________

)malloc(sizeof(SeqList));printf(請(qǐng)輸入線性表的長度:);scanf(%d,r);

sq-last=printf(請(qǐng)輸入線性表的各元素值:\n);

);AdjustSqlist(sq);

08專升本數(shù)據(jù)結(jié)構(gòu)考題解答

一、單項(xiàng)選擇題〔共12小題，每題2分，共24分〕1．用非遞歸方法實(shí)現(xiàn)遞歸算法時(shí)通常要運(yùn)用A．循環(huán)隊(duì)列B．棧

C．二叉樹

D．雙向隊(duì)列

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

06年轉(zhuǎn)升本數(shù)據(jù)結(jié)構(gòu)考題

一、單項(xiàng)選擇題〔共12小題，每題2分,共24分〕1、已知單鏈表結(jié)構(gòu)為structnode{intdata;

structnode*ne*t;}*p,*q,*r;

刪除單鏈表中結(jié)點(diǎn)p(由p指向的結(jié)點(diǎn))后面的結(jié)點(diǎn)的操作不正確的選項(xiàng)是__C__A、

q=p-ne*t;p-ne*t=q-ne*t;

B、p-ne*t=p-ne*t-ne*t;

C、r=p-ne*t;p-ne*t=q-ne*t;

D、

q=p-ne*t;r=q-ne*t;p-ne*t=r;

2、假設(shè)待排序?qū)ο笮蛄性谂判蚯耙呀?jīng)根據(jù)關(guān)鍵字遞增排列，那么采納__A__比較次數(shù)最少。

A、徑直插入排序O(n)B、快速排序O(n2)C、合并排序

D、簡約選擇排序O(n2)

3、圖的深度優(yōu)先遍歷類似于樹的__C__A、后序遍歷B、層次遍歷C、前序遍歷D、中序遍歷

4、求賦權(quán)有向圖的最短路徑常用的算法有___D___

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

A、Prim算法和Kruskal算法B、Prim算法和Dijkstra算法C、Kruskal算法和Dijkstra算法D、Dijkstra算法和Floyd算法

5、單鏈表中有n個(gè)結(jié)點(diǎn)，在其中查找值為*的結(jié)點(diǎn)，在查找勝利時(shí)需要比較的平均次數(shù)是___D___。A、n

B、(n-1)/2C、n/2D、(n+1)/2解答：

查詢每個(gè)元素需要比較次數(shù)之和查詢平均繁復(fù)度=

元素個(gè)數(shù)

1+2+3+...+nn+1==

n2

思索：假如查找不勝利，計(jì)算結(jié)果如何？

6、線性表采納鏈?zhǔn)酱鎯?chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)地址__B___A、需要是不連續(xù)的B、連續(xù)與否均可C、需要是連續(xù)的

D、和頭結(jié)點(diǎn)的存儲(chǔ)地址項(xiàng)連續(xù)

7、一棵非空的二叉樹中，設(shè)根結(jié)點(diǎn)在第0層，在第i層上最多有___D__個(gè)結(jié)點(diǎn)。A、2(i+1)B、2iC、2(i-1)D、2i

根層01個(gè)/\

AB層12個(gè)

/\/\

ABCD層24個(gè)

8、在以下的排序算法中，算法的時(shí)間繁復(fù)度是O(n*log2n)是___D__。A、冒泡排序B、簡約選擇排序C、徑直插入排序D、堆排序

9、運(yùn)用一個(gè)棧，每次限制進(jìn)棧和出棧一個(gè)元素。假設(shè)進(jìn)棧的元素序列依次是a、b、c、d；指出不可能的出棧序列___B____。A、abcdB、adbc

這是我自己整理的福建省專升本數(shù)據(jù)結(jié)構(gòu)歷年真題的具體答案,盼望對(duì)學(xué)弟學(xué)妹們有所援助,那些去補(bǔ)習(xí)的都是沒什么用的!

C、acbdD、dcba解答：A、push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)