1、宁波大学2021年硕士研究生招生考试初试试题(A卷) (答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法一、选择题（每题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) 与图的顶点和边数
2、有关3、循环队列qu的队满条件（front指向队首元素的前一位置，rear指向队尾元素）是（ ）。A) (qu.rear+1) % MaxSize=(qu.front+1) % MaxSizeB) (qu.rear+1) % MaxSize=qu.front+1C) (qu.rear+1) % MaxSize=qu.frontD) qu.rear =qu.front4、 若串s=”software”，其子串个数是（ ）。A) 8B) 37C) 36D) 95、 已知一个栈的进栈序列是（1,2,3,n）,其输出序列是p1,p2,pn, 若p1=n,则pi的值为（ ）。A) iB) n-iC) n
3、-i+1D) 不确定6、 表达式a*(b+c)-d的后缀表达式是（ ）。A) abcd*+-B) abc+*d-C) abc*+d-D) -+*abcd7、 一个无向连通图中有16条边，所有顶点的度均小于5，度为4的顶点有3个，度为3的顶点有4个，度为2的顶点有2个，则该图有（ ）个顶点。A) 10B) 11C) 12D) 138、 m行n列的稀疏矩阵采用十字链表表示时，其中单链表的个数为（ ）。A) m+1B) n+1C) m+n+1D) MAXm,n+19、 以下排序算法中，（ ）在最后一趟排序结束之前可能所有元素都没有放到最终位置上。A) 快速排序B) 希尔排序C) 堆排序D) 冒泡排序
4、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) 所有叶子都
5、在同一层次上C) 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树D) 根结点中的数据是有序的14、 一个nn的对称矩阵A，如果采用以列优先（列序为主序）的压缩方式存放到一个一维数组B 中，则B的容量为（ ）。A) n2 B) n2/2 C) n(n+1)/2 D) (n+1)2/215、 在一个具有n个结点的有序单链表中插入一个新结点使其仍然有序，其算法的时间复杂度为（ ）。A) O(log2 n) B) O(1) C) O(n2) D) O(n)16、 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用（ ）存储方式最节省运算时间。A) 单循环链表 B)
6、 单链表 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/1218、 递归程序可借助于 ( ) 转化为非递归程序。A) 线性表 B) 队列 C) 栈 D) 数组 19、 若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是 ( )。A) 40 B) 55 C) 59 D) 6120、 下面关于B
7、-树和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) 单源最短路径中的Dijks
8、tra算法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) 所有
9、的结点均无右孩子。 C) 只有一个叶子结点。 D) 是任意一棵二叉树。二、填空题（每空3分，共45分）1、 进栈序列是1,2,n，则可能的出栈序列有 （1） 种。2、有n个顶点的强连通图G至少有 （2） 条边。3、 有n个顶点和e条边的图G采用邻接表表示，从顶点v出发进行深度优先遍历的时间复杂度为 （3） 。4、 设用希尔排序对序列（98, 36, -9, 0, 47, 23, 1, 8, 10, 7）进行排序，给出的步长依次为5,2,1，则排序需 （4） 趟，第2趟结束后，序列中数据的排列次序为 （5） 。5、 B+树有两个查找的入口指针，其中一个指向根结点，另一个指向 （6） 。6、 设只
10、含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为 (7) ,最小结点数为_ (8) 。 7、 后缀表达式 a b c + * d e * f g + / 的中缀表达式为 （9） 。8、 20个节点的AVL树的最大深度为 （10） 。 (设根节点深度为0)9、 著名的汉诺（Hanoi）塔问题可以通过递归求解，解决10个盘片的汉诺（Hanoi）塔问题总共需要 （11） 次盘片移动。10、 据说双十一这两天会下红包雨，但有个规则：只能接掉落在身旁10米范围内的红包（0-10这11个位置），且每秒种只能在移动不超过一米的范围内接住红包。有一个同学一开始站在5这个位置，因此在第一秒，他只能接
11、到4,5,6这三个位置中其中一个位置上的红包。问最多可能接到多少个红包？输入第一行1个整数，表示红包的总个数n；第二行开始n行，每行2个整数，表示红包掉落的位置和时间。输出一个整数，表示能接到的最多的红包个数。（每空仅限一条语句）#include#include#define N 100010int dpN11=0;int max2(int a,int b) return a=ab?a:b;int max3(int a,int b,int c) a=ac?a:c; （12） ; return a;int main() int n,t,x,i,j,maxt; while(scanf(%d, &n
12、) if (n=0) break;memset(dp, 0, sizeof(dp); maxt=0; for(i=0;i=0;i-) for(j=0;j11;j+)if(j=0) dpij+=max2(dpi+1j,dpi+1j+1); else if(j=10) dpij+=max2(dpi+1j-1,dpi+1j); else dpij+= （14） ; printf(%dn, （15） ); return 0;三、简答题（每题6分，共30分）1. 图G是一个非连通无向图，共有28条边，则该图至少有多少个顶点，并说明理由。2. 若一个序列含有n个整数，只想得到第k(1kn)个最小元素之前的
13、部分排序序列，请问在堆排序、直接插入排序、冒泡排序和简单选择排序中个最好采用什么排序方法？并说明理由。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. 数组aMaxSize用作一个循
14、环队列，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）求出关键路径并指明完成该工程所需的最短时间。工序代号ABCDEFGH所需时间32234321先序工序-AABAC、ED第 5 页 共 5 页
