數(shù)據(jù)結(jié)構(gòu)與算法初試試卷（A卷）-寧波大學(xué)2021年碩士初試自命題科目真題

一、選擇題（每題2分，共50分）

1、向一個(gè)不帶頭結(jié)點(diǎn)的單鏈表link表示的鏈棧中插入一個(gè)p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行（）。

A）link->next=p;

B）p->next=link->next;Iink->next=p;

C）p->next=link;link=p;

D）p->next=link;link=link->next;

2、用鄰接表存儲(chǔ)圖所用的空間大?。?O

A）只與圖的邊數(shù)有關(guān)

B）只與圖的頂點(diǎn)數(shù)有關(guān)

C）與邊數(shù)的平方有關(guān)

D）與圖的頂點(diǎn)和邊數(shù)有關(guān)

3、循環(huán)隊(duì)列qu的隊(duì)滿條件(front指向隊(duì)首元素的前一位置，rear指向隊(duì)尾元素)是()。

A)(qu.rear+1)%MaxSize==(qu.front+1)%MaxSize

B)(qu.rear+1)%MaxSize==qu.front+l

C)(qu.rear+1)%MaxSize==qu.front

D)qu.rear==qu.front

4、若串s=,,software,5,其子串個(gè)數(shù)是()O

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

5、已知一個(gè)棧的進(jìn)棧序列是（l,2,3,...,n），其輸出序列是pi,p2,...,pn,若pi=n，則pi的值為（）?

A)iB)n-iC)j-i+lD）不確定

6、表達(dá)式a*（b+c）-d的后綴表達(dá)式是（)o

A）abcd*+-B）abc+*d-C)abc*+d-D)-+*abcd

7、一個(gè)無向連通圖中有16條邊，所有頂點(diǎn)的度均小于5,度為4的頂點(diǎn)有3個(gè)，度為3的頂點(diǎn)有4個(gè),

度為2的頂點(diǎn)有2個(gè)，則該圖有（）個(gè)頂點(diǎn)。

A）10B）11C）12D）13

8、m行n列的稀疏矩陣采用十字鏈表表示時(shí)，其中單鏈表的個(gè)數(shù)為（）。

A)m+1B)n+1C)m+n+1D)MAX{m,n}+l

9、以下排序算法中，（）在最后一趟排序結(jié)束之前可能所有元素都沒有放到最終位置上。

A）快速排序B）希爾排序C）堆排序D）冒泡排序

10、對(duì)有n個(gè)元素的序列進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間是（）。

A)O(log2n)B)O(nlog2n)C)0(n)D)0(n2)

11、為解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的

數(shù)據(jù)依次寫入該緩沖區(qū)，打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)?該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）.

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

12、如果將所有中國(guó)人按照生日（只考慮月、日，不考慮年份）來排序，使用下列（）算法最快。

A）歸并排序B）希爾排序C）快速排序D）基數(shù)排序

13、下列關(guān)于m階B-樹的說法錯(cuò)誤的是（）。

A）根結(jié)點(diǎn)至多有m棵子樹

B）所有葉子都在同一層次上

C）非葉結(jié)點(diǎn)至少有m/2（m為偶數(shù)）或m/2+1（m為奇數(shù)）棵子樹

D）根結(jié)點(diǎn)中的數(shù)據(jù)是有序的

14、一個(gè)nxn的對(duì)稱矩陣A,如果采用以列優(yōu)先（列序?yàn)橹餍颍┑膲嚎s方式存放到一個(gè)一維數(shù)組B中,

則B的容量為()。

A)n2B)“2/2C)1)/2D)(/1)2/2

15、在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)使其仍然有序，其算法的時(shí)間復(fù)雜度為

()O

2

A)O(log2n)B)O(l)C)O(n)D)0(n)

16、若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)元素，則采用（）存儲(chǔ)方

式最節(jié)省運(yùn)算時(shí)間。

A）單循環(huán)鏈表B）單鏈表C）雙向鏈表D）順序表

17、構(gòu)造散列（Hash）表的關(guān)鍵字的輸入序列為（12,21,3,13,4,43,35,64,5,14）,散列（Hash）函數(shù)

H（key）=key%13,采用線性開放定址法解決沖突。在等概率的情況下，查找成功的平均查找長(zhǎng)度是

()O

A)12/10B)13/12C)14/12D)15/12

18、遞歸程序可借助于（）轉(zhuǎn)化為非遞歸程序。

A）線性表B）隊(duì)列C）棧D）數(shù)組

19、若某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有20個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)是（）。

A)40B)55C)59D)61

20、下面關(guān)于B-樹和B+樹的敘述中，不正確的結(jié)論是（)°

A）B-樹和B+樹都能有效地支持順序查找。

B）B-樹和B+樹都能有效地支持隨機(jī)查找。

C）B-樹和B+樹都是平衡的多叉樹。

D）B-樹和B+樹都可用于文件索引結(jié)構(gòu)。

21、假設(shè)用于通訊的電文僅由6個(gè)字符組成，字母在電文中出現(xiàn)的頻率分別為7,19,22,6,32,14。若為

這6個(gè)字母設(shè)計(jì)哈夫曼編碼（設(shè)生成新的二叉樹的規(guī)則是按給出的次序從左至右的結(jié)合，新生成的二叉

樹總是插入在最右），則頻率為32的字符編碼是（)O

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

22、下面哪個(gè)算法的實(shí)現(xiàn)無關(guān)貪心策略（）。

A）單源最短路徑中的Dijkstra算法

B）最小生成樹的Prim算法

C）最小生成樹的Kruskal算法

D）字符串匹配中的KMP算法

23、下面哪一種方法不是平攤分析的常用技術(shù)（）。

A）聚集分析B）動(dòng)態(tài)表C）記賬方法D）勢(shì)能方法

24、使用二分搜索算法在n個(gè)有序元素表中搜索一個(gè)特定元素，在最好情況和最壞情況下搜索的時(shí)

間復(fù)雜性分別為（）。

A）0（1）,O（log2n）B）0（n）,O（log2n）

C）0（1）,O（nlog2n）D）0（n）,O（nlog2n）

25、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。

A）所有的結(jié)點(diǎn)均無左孩子。B）所有的結(jié)點(diǎn)均無右孩子。

C）只有一個(gè)葉子結(jié)點(diǎn)。D）是任意一棵二叉樹。

二、填空題（每空3分，共45分）

1、進(jìn)棧序列是1,2，…,n,則可能的出棧序列有（1）種。

2、有n個(gè)頂點(diǎn)的強(qiáng)連通圖G至少有（2）條邊。

3、有n個(gè)頂點(diǎn)和e條邊的圖G采用鄰接表表示，從頂點(diǎn)v出發(fā)進(jìn)行深度優(yōu)先遍歷的時(shí)間復(fù)雜度為

（3）o

4、設(shè)用希爾排序?qū)π蛄校?8,36,-9,0,47,23,1,8,10,7）進(jìn)行排序，給出的步長(zhǎng)依次為5,2,1,則排序需

⑷趟,第2趟結(jié)束后，序列中數(shù)據(jù)的排列次序?yàn)椋?）。

5、B+樹有兩個(gè)查找的入口指針，其中一個(gè)指向根結(jié)點(diǎn)，另一個(gè)指向（6）。

6、設(shè)只含根結(jié)點(diǎn)的二叉樹的高度為0,則高度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為（7）.最小結(jié)點(diǎn)數(shù)為

⑻o

7、后綴表達(dá)式abc+*de*f-g+/的中綴表達(dá)式為（9）。

8、20個(gè)節(jié)點(diǎn)的AVL樹的最大深度為（10）。（設(shè)根節(jié)點(diǎn)深度為0）

9、著名的漢諾（Hanoi）塔問題可以通過遞歸求解，解決10個(gè)盤片的漢諾（Hanoi）塔問題總共需要（11）

次盤片移動(dòng)。

10、據(jù)說雙十一這兩天會(huì)下紅包雨，但有個(gè)規(guī)則：只能接掉落在身旁10米范圍內(nèi)的紅包（0-10這11

個(gè)位置），且每秒種只能在移動(dòng)不超過一米的范圍內(nèi)接住紅包。有一個(gè)同學(xué)一開始站在5這個(gè)位置，因

此在第一秒，他只能接到4,5,6這三個(gè)位置中其中一個(gè)位置上的紅包。問最多可能接到多少個(gè)紅包？

［輸入］

第一行1個(gè)整數(shù)，表示紅包的總個(gè)數(shù)n；

第二行開始n行，每行2個(gè)整數(shù)，表示紅包掉落的位置和時(shí)間。

[輸出]

一個(gè)整數(shù)，表示能接到的最多的紅包個(gè)數(shù)。

(每空僅限一條語句)

#include<stdio.h>

#include<string.h>

#defineN100010

intdp[N][ll]={0};

intmax2(inta,intb){

returna=a>b?a:b;

(

intmax3(inta,intb,intc){

a=a>c?a:c;

(⑵：

returna;

)

intmain(){

intn,t,x,i,j,maxt;

while(?scanf("％d”，&n)){

if(n==0)break;

memset(dp,0,sizeof(dp));

maxt=0;

for(i=0;i<n;i++){

scanf("%d%dn,&x,&t);

dp[t][x]+=l;

maxt=(13);

}

for(i=maxt-l;i>=0;i-)

for(j=0;j<ll;j++){

if(j==0)dp[i][j]+=max2(dp[i+l][jl,dp[i+l]fj+l]);

elseif(j==10)dp[i]|j]+=max2(dp[i+l]|j-l],dp[i+l][j]);

elsedp[i][j1+=(14);

)

printf(',%d\n,\(15)):

)

return0;

三、簡(jiǎn)答題（每題6分，共30分）

1.圖G是一個(gè)非連通無向圖，共有28條邊，則該圖至少有多少個(gè)頂點(diǎn)，并說明理由。

2.若一個(gè)序列含有n個(gè)整數(shù)，只想得到第k（l<k<n）個(gè)最小元素之前的部分排序序列，請(qǐng)問在堆排序、直

接插入排序、冒泡排序和簡(jiǎn)單選擇排序中個(gè)最好采用什么排序方法？并說明理由。

3.給定關(guān)鍵字集合｛19,01,23,14,55,68,11,82,36）,構(gòu)造散列（Hash）表，采用線性探測(cè)再散列處理

沖突方法。設(shè)定散列（Hash）函數(shù)H（key）=keyMOD11（表長(zhǎng)=11）。發(fā)生沖突時(shí)請(qǐng)給予說明。

4.有一份電文中共使用了5個(gè)字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為4、7、5、2、9,試畫出對(duì)

應(yīng)的哈夫曼樹(請(qǐng)按左子數(shù)根結(jié)點(diǎn)的權(quán)小于等于右子數(shù)根結(jié)點(diǎn)的權(quán)的次序構(gòu)造)，并求出每個(gè)字符的

哈夫曼編碼。

5.數(shù)組a[MaxSize]用作一個(gè)循環(huán)隊(duì)列，front指向循環(huán)隊(duì)列中隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素

的位置。

(1)寫出用front、rear,MaxSize表示隊(duì)列中元素個(gè)數(shù)的公式；

(2)設(shè)計(jì)刪除隊(duì)列中第k個(gè)元素的算法；

(3)指出(2)中函數(shù)的時(shí)間復(fù)雜度。

四、應(yīng)用題(第1小題10分，第2小題15分，共25分)

1.假設(shè)一元多