宁波大学2021年考研真题：916数据结构与算法

考研复习备考最为珍贵资料的就是考研历年真题了，通过研究真题，我们可以从中摸索出考题规律，出题的大概范围，题目的难度等，帮助我们更加有效地备考！启航教育小编为大家整理了宁波大学2021年考研真题：916数据结构与算法，大家可以参考哦！

一、选择题(每题2分，共50分)

1、 向一个不带头结点的单链表link表示的链栈中插入一个p所指结点时，应执行( )。

A) link->next=p;

B) p->next=link->next; link->next=p;

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

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

2、 用邻接表存储图所用的空间大小( )。

A) 只与图的边数有关

B) 只与图的顶点数有关

C) 与边数的平方有关

D) 与图的顶点和边数有关

3、循环队列qu的队满条件(front指向队首元素的前一位置，rear指向队尾元素)是( )。

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

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

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

D) qu.rear ==qu.front

4、 若串s=”software”，其子串个数是( )。

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

5、 已知一个栈的进栈序列是(1,2,3,…,n),其输出序列是p1,p2,…,pn, 若p1=n,则pi的值为( )。

A) i B) n-i C) n-i+1 D) 不确定

6、 表达式a*(b+c)-d的后缀表达式是( )。

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

7、 一个无向连通图中有16条边，所有顶点的度均小于5，度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个，则该图有( )个顶点。

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

8、 m行n列的稀疏矩阵采用十字链表表示时，其中单链表的个数为( )。

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

9、 以下排序算法中，( )在最后一趟排序结束之前可能所有元素都没有放到最终位置上。

A) 快速排序 B) 希尔排序 C) 堆排序 D) 冒泡排序

10、 对有n个元素的序列进行堆排序，最坏情况下的执行时间是( )。

A) O(log2 n) B) O(nlog2 n) C) O(n) D) O(n2)

11、 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。

A) 栈 B) 队列 C) 树 D) 图

12、 如果将所有中国人按照生日(只考虑月、日，不考虑年份)来排序，使用下列( )算法最快。

A) 归并排序 B) 希尔排序 C) 快速排序 D) 基数排序

13、下列关于m阶B-树的说法错误的是( )。

A) 根结点至多有m棵子树

B) 所有叶子都在同一层次上

C) 非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树

D) 根结点中的数据是有序的

14、 一个n×n的对称矩阵A，如果采用以列优先(列序为主序)的压缩方式存放到一个一维数组B 中，则B的容量为( )。

A) n2 B) n2/2 C) n(n+1)/2 D) (n+1)2/2

15、 在一个具有n个结点的有序单链表中插入一个新结点使其仍然有序，其算法的时间复杂度为( )。

A) O(log2 n) B) O(1) C) O(n2) D) O(n)

16、 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用( )存储方式最节省运算时间。

A) 单循环链表 B) 单链表 C) 双向链表 D) 顺序表

17、 构造散列(Hash)表的关键字的输入序列为(12,21,3,13,4,43,35,64,5,14)，散列(Hash)函数H(key)=key%13，采用线性开放定址法解决冲突。在等概率的情况下，查找成功的平均查找长度是( )。

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

18、 递归程序可借助于 ( ) 转化为非递归程序。

A) 线性表 B) 队列 C) 栈 D) 数组

19、 若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是 ( )。

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

20、 下面关于B-树和B+树的叙述中，不正确的结论是 ( )。

A) B-树和B+树都能有效地支持顺序查找。

B) B-树和B+树都能有效地支持随机查找。

C) B-树和B+树都是平衡的多叉树。

D) B-树和B+树都可用于文件索引结构。

21、 假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32, 14。若为这6个字母设计哈夫曼编码(设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右)，则频率为32的字符编码是( )。

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

22、 下面哪个算法的实现无关贪心策略( )。

A) 单源最短路径中的Dijkstra算法

B) 最小生成树的Prim算法

C) 最小生成树的Kruskal算法

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

23、下面哪一种方法不是平摊分析的常用技术( )。

A) 聚集分析 B) 动态表 C) 记账方法 D) 势能方法

24、使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最好情况和最坏情况下搜索的时间复杂性分别为( )。

A) O(1)，O(log2 n) B) O(n)，O(log2 n)

C) O(1)，O(nlog2 n) D) O(n)，O(nlog2 n)

25、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。

A) 所有的结点均无左孩子。 B) 所有的结点均无右孩子。

C) 只有一个叶子结点。 D) 是任意一棵二叉树。

二、填空题(每空3分，共45分)

1、 进栈序列是1,2,…,n，则可能的出栈序列有____种。

2、有n个顶点的强连通图G至少有 ____条边。

3、 有n个顶点和e条边的图G采用邻接表表示，从顶点v出发进行深度优先遍历的时间复杂度为____。

4、 设用希尔排序对序列(98, 36, -9, 0, 47, 23, 1, 8, 10, 7)进行排序，给出的步长依次为5,2,1，则排序需____趟，第2趟结束后，序列中数据的排列次序为 ____。

5、 B+树有两个查找的入口指针，其中一个指向根结点，另一个指向 ____。

6、 设只含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为____，最小结点数为____。

7、 后缀表达式 a b c + * d e * f – g + / 的中缀表达式为____ 。

8、 20个节点的AVL树的最大深度为 (10) 。 (设根节点深度为____

9、 著名的汉诺(Hanoi)塔问题可以通过递归求解，解决10个盘片的汉诺(Hanoi)塔问题总共需要____次盘片移动。

10、 据说双十一这两天会下红包雨，但有个规则：只能接掉落在身旁10米范围内的红包(0-10这11个位置)，且每秒种只能在移动不超过一米的范围内接住红包。有一个同学一开始站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置中其中一个位置上的红包。问最多可能接到多少个红包?

[输入]

第一行1个整数，表示红包的总个数n;

第二行开始n行，每行2个整数，表示红包掉落的位置和时间。

[输出]

一个整数，表示能接到的最多的红包个数。

(每空仅限一条语句)

#include

#include

#define N 100010

int dp[N][11]={0};

int max2(int a,int b){

return a=a>b?a:b;

}

int max3(int a,int b,int c){

a=a>c?a:c;

________ ;

return a;

}

int main(){

int n,t,x,i,j,maxt;

while(~scanf("%d", &n)) {

if (n==0) break;

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

maxt=0;

for(i=0;i

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

dp[t][x]+=1;

maxt= ________ ;

}

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

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

if(j==0) dp[i][j]+=max2(dp[i+1][j],dp[i+1][j+1]);

else if(j==10) dp[i][j]+=max2(dp[i+1][j-1],dp[i+1][j]);

else dp[i][j]+=________ ;

}

printf("%d\n", ________);

}

return 0;

}

三、简答题(每题6分，共30分)

1. 图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点，并说明理由。

2. 若一个序列含有n个整数，只想得到第k(1

3. 给定关键字集合{ 19, 01, 23, 14, 55, 68, 11, 82, 36 }，构造散列(Hash)表，采用线性探测再散列处理冲突方法。设定散列(Hash)函数 H(key) = key MOD 11 ( 表长=11 )。发生冲突时请给予说明。

4. 有一份电文中共使用了5个字符：a、b、c、d、e，它们的出现频率依次为4、7、5、2、9，试画出对应的哈夫曼树(请按左子数根结点的权小于等于右子数根结点的权的次序构造)，并求出每个字符的哈夫曼编码。

5. 数组a[MaxSize]用作一个循环队列，front指向循环队列中队头元素的前一个位置，rear指向队尾元素的位置。

(1) 写出用front、rear、MaxSize表示队列中元素个数的公式;

(2) 设计删除队列中第k个元素的算法;

(3) 指出(2)中函数的时间复杂度。

四、应用题(第1小题10分，第2小题15分，共25分)

1. 假设一元多项式以循环链表表示，链表的结点结构为：

typedef struct PNode {

float coef; //系数

int exp; //指数

struct PNode *next;

}*LinkList;

现需要将一个用循环链表h表示的代数多项式拆分成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。要求利用原链表中的结点构成链表h1和h2。例如多项式7x8+5x3-4x的循环链表为

经拆分之后的情况应是：

请编写完成上述拆分的算法。

2. 下表给出了某工程各工序之间的优先关系和各工序所需的时间(其中“-”表示无先序工序)，

(1)画出相应的AOE图;

(2)列出各事件的最早发生时间和最迟发生时间;

(3)求出关键路径并指明完成该工程所需的最短时间。

工序代号	A	B	C	D	E	F	G	H
所需时间	3	2	2	3	4	3	2	1
先序工序	-	-	A	A	B	A	C、E	D

以上来源于：宁波大学官网

课程推荐:

暑期VIP领学计划 线下＋线下结合 大咖老师授课  助力逆袭提分>>

暑期专属VIP定制班Plus（1V1择校指导＋公共课vip班＋专业课一对一）助力你一站式复习>