1、宁波大学2020年硕士研究生招生考试初试试题(A卷) (答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法一、 选择题： （每个选择2分，共30分）1. 在单链表指针为P的结点之后插入指针为s的结点，正确的操作是（ ）。A. p-next=s; s-next=p-next; B. p-next=s-next; p-next=s; C. s-next=p-next; p-next=s; D. p-next=s; p-next=s-next;2. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）。A3，2，6，1，4，
2、5B3，4，2，1，6，5C1，2，5，3，4，6 D5，6，4，2，3，13. 循环队列用数组A0.m-1存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是 ( )。A. rear-front-1 B. rear-front+1 C. (rear-front+m)%m D. rear-front4. 二分查找算法的时间复杂度是（ ）。 A. O(n*n) B. O(n) C. O(n*log n) D . O(log n) 5. 向顺序存储的循环队列 Q 中插入新元素的过程分为三步：（ ）。A.进行队列是否满的判断，存入新元素，移动队尾指针B.进行队列是否空的判断，
3、存入新元素，移动队尾指针C.进行队列是否满的判断，移动队尾指针，存入新元素D.进行队列是否空的判断，移动队尾指针，存入新元素6. 设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是 ( )。A. x是y的左兄弟 B. x是y的右兄弟 C. x是y的祖先 D. x是y的子孙7. 下列二叉树中，( )可用于实现符号的不等长高效编码。 A. 最优二叉树 B. B-树 C. 平衡二叉树 D. 二叉排序树8. 已知哈希表地址空间为A9，哈希函数为H(k)=k mod 7，采用线性探测再散列处理冲突。若依次将数据序列：76,45,88,21,94,77,
4、17存入该散列表中，则元素17存储的下标为( )；在等概率情况下查找成功的平均查找长度为( )。A. 0 B. 1 C. 2 D. 3E. 4 F. 5 G. 6 H. 79、设问题规模为N时，某递归算法的时间复杂度记为T(N)，已知T(1)=1，T(N)=2T(N/2)+N*N/2，用O表示的时间复杂度为（ ）。A、O(logN) B、O(N) C、O(N2logN) DO(NlogN) 10、右图所示带权无向图的最小生成树的权为( )。A.17B.15C.14D.1811、下面说法不正确的是（ ）。A、在聚集分析中，堆栈操作PUSH、POP、MULTIPOP的平均代价都是O(1)。B、在记
5、账方法中，某些操作的费用比它们的实际代价或多或少。C、势能方法中，势是与整个数据结构而不是其中的个别对象发生联系的。D、平摊分析就是将最坏和最好情况下的时间代价进行平均计算得到平摊时间复杂度。12.求最长公共子序列时最适合使用的算法是（ ）。A、分支界限法 B、动态规划法 C、贪心法D、回溯法13. 下面的叙述中不正确的是（ ）。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，将使整个工程提前完成C所有关键活动都提前完成，则整个工程将提前完成D某些关键活动若提前完成，将使整个工程提前完成14. 设计一个判别表达式中左、右括号是否配对出现的算法，采用( )数据结构最佳。
6、A. 线性表 B. 栈 C. 队列 D. 广义表二、填空题：（每空2分，共20分）1.5.在一棵m阶B-树中，除根结点外非叶结点至少有_棵子树，至多有_棵子树。2.堆排序的最坏时间复杂度为 。3.带头结点的单链表逆置算法如下： voidinvert(LinkList L) p=L-next;L-next=NULL; while(p) q=p; p=p-next; _; _ ; 4. 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_算法，最费时间的是_算法。5. 表达式3+(12*3-2)/4+4*5/7)+18/9的后缀表达式是 。6. 著名的八皇后问题是在8x
7、8的国际象棋棋盘上放置8个皇后，使其任意2个都不在相互攻击的位置，该问题可以通过_方法求解，总共有_个解。 三、简答题：（每题8分，共40分）1已知一棵度为m的树中：n1个度为1的结点，n2个度为2的结点，nm个度为m的结点，问该树中共有多少个叶子结点？2给定关键字集合 12, 21, 3, 13, 4, 43, 35, 64, 5, 14 ，构造哈希表，采用线性探测再散列处理冲突方法。设定哈希函数 H(key) = key MOD 13 ( 表长=13 )。发生冲突时请给予说明。3.如果二个排序算法A和B的时间复杂度分别为 fa(n) = n*log n 和 fb(n) = n1.5，请问哪
8、个算法时间复杂度低？试给出简要证明。4.已知一组待执行任务的优先级分别如下: 37,24,42,6,53,8,72,11,3,9。假设任务的优先级越小，该任务的优先级别越高，请设计合理的数据结构和算法，为这些待执行的任务建立一个优先队列。5.已知待排序的一组记录关键字的初始排列如下: 37,24,42,6,53,8,72,11,3,9。需按关键字递增有序排序，请给出：(1).快速排序完成第一趟划分之后的记录排列序列（以第一个关键字为基准）；(2).堆排序初始建堆（大顶堆）的序列；(3).第一趟基数排序后的序列。四、算法填空题 （每空3分，共36分）1.请完善以下的两两顶点之间的最短路值计算程序
9、，其中V为顶点集合，|V|为顶点个数，二维数组weight初始值为图中连接的加权。FPath(matrix weight) for i=1 to |V| for j=1 to |V| for k=1 to |V| if ( （1） ) weightjk = （2） ;2、一场演唱会，现有N(1=N=200)个歌迷排队买票。售票处规定，一个人每次最多只能买两张票。假设：（1）第i(1=i=N)位歌迷买一张票需要时间Ti；（2）队伍中相邻的两位歌迷（第i个人和第i+1个人）可以由其中一人合买两张票，则两位歌迷买两张票的时间变为Ri，这样做可以缩短后面歌迷等待的时间。现给出N,Ti和Ri，求使所有人
10、都买到票的最短售票时间。输入第一行输入人数N；第二行N个数，表示单买的时间代价Ti；第三行N-1个数，表示由前1人合买的时间代价Ri。输出最短售票时间。#include#include#define N 10010int min2(int a,int b) return （3） ;int main() int i,j,n,tN=0,rN=0,dpN=0; scanf(%d,&n); for (i=1;i=n;i+) scanf(%d,&ti); for (i=1;i= （4） ;i+) scanf(%d,&ri);dp1= （5） ;for(i=2;i=n;i+)dpi=min2( （6） )
11、; printf(%dn, （7） ); return 0;3、有一个由数字 0、1 组成的方阵中，存在任意形状的一个或多个封闭区域，封闭区域由数字1 完整包围构成，封闭区域内至少有一个0 。每个节点只能走上下左右 4 个方向。现要求把封闭区域内的所有0空间都填写成2 。输入第一行一个整数 n，表示方阵的大小(1n30)；接下来 n 行，由 0 和 1 组成的 nn 的方阵。输出填好数字 2 的完整方阵。#include#define N 32int n,p,q,gridNN= 0,queueN*N2=0; struct Position int row; int col;void addin
12、(int i, int j) queueq0=i; queueq1=j; (8) ;int main() int i,j;scanf(%d,&n); for (i=1;i=n;i+) for (j=1;j=n;j+)scanf(%d,&gridij); struct Position offset4; struct Position nbr; offset0.row = 0; offset0.col = 1; offset1.row = 1; offset1.col = 0; offset2.row = 0; offset2.col = -1; (9) for (i = 0; i = n+1;
13、 i+) grid0i = gridn+1i = -2; / 边界围栏 for (i = 0; i = n+1; i+) (10) = -2; p=0;q=0; for (i=1;i=n;i+)if (grid1i=0) addin(1,i);if (gridni=0) addin(n,i);if (gridi1=0) addin(i,1);if (gridin=0) addin(i,n);while (pq) gridqueuep0queuep1=-1; for (int i = 0; i 4; i+) nbr.row = queuep0 + offseti.row; nbr.col = q
14、ueuep1 + offseti.col; if (gridnbr.rownbr.col = 0) (11) ; p+; for (i=1;in+1;i+) for (j=1;jn+1;j+) if (gridij=-1) printf(0 ); else if (gridij=0) (12) ; else printf(1 ); printf(n); return 0;五、算法设计题：（每题12分，共24分）1.如果二叉树的结构定义如下:typedef struct BiTNode char data; struct BiTNode *lchild,*rchild; BiTNode, *BiTree;试设计程序计算一棵二叉树中包含的叶子结点的总数。 2.某大学组织n个学生去多家单位实习，如果所有单位总共可以提供m个实习岗位，实习生和实习单位经过洽谈后双方自愿进行，校方则希望能够达到实习人数的最大化，假设双方对彼此只有同意或不同意，没有优先程度考虑，试采用合适的二分图结构表示该过程，并设计合理的算法实现二分图的最大匹配，即达到实习人数的最大化。第 7 页 共 8 页
