宁波大学916数据结构与算法2019-2021年考研专业课初试真题

1、宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法一、选择题： （共 30 分，每题 2 分）采用链式存储结构表示数据时，相邻的数据元素的存储地址（）。一定不连续B. 不一定连续C. 一定连续D. 部分连续，部分不连续在一个单链表中，*p 节点不是最后节点，*p 之后插入节则执行（）。s-next = p; p-next = s;B. s-next = p-next ; p-next = s;C. s-next = p-next ; p = s;D. p-next = s; s-nex

2、t = p;用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移的操作(。j=j-nextB. j=rj.nextC .j=j+1D. j=rj- next向一个栈顶指针为HS 的链栈（带头结点）中插入一个s 所指结点时，则执行（）。s-next = HS ;HS = s;B.HS-next = s;C. s - next = HS-next ; HS-next = s;D.s-next = HS ; HS = HS-next;已知一个推入堆栈的字符序列顺序是a,b,c,d,e, 下列哪个字符序列是不能通过堆栈操作得到的字符序列（）。A. e,d,c,b,

3、aB. d,e,c,b,aC. d,c,e,a,bD. a,b,c,d,e循环队列存储在数组A0.m中，则入队时的操作为（）。rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)在一个具有n 个单元的顺序存储的循环队列中假定front 和rear 分别为队首指针和队尾指针则判断队空的条件是（）。front = = (rear +1) % nB. front = = rearC. front = =0D. (front +1) % n = = rear元素时平均要移动表中的（）个元素

4、。A. (n1)/2B. nC. n/2D. (n1)/29. 对广义表 A.（）a,(b,(c,(),执行操作gettail(gethead(gettail(A)的结果是（B. （）C. dD. (d)）。10.(25,21,30,13,4,43,35,64,5,17,2,8) H(key)=key%15，采用链地址法解决冲突。查找64 的关键字比较次数是（）。A.1B.2C. 4D .3第 1 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法下图是一个二叉树后序遍

5、历的结果是 （）。A、abcdefB 、 cfabdeC、dbaecfD 、 cbfade现有以下按前序和中序遍历二叉树的结果：GAHFDBCEAHGBDCF() 。A . GHABCDEFC. ABCDEFGHB. HABCDEFGD. HABCGDEF一棵完全二叉树的第6 层（设根为第1 层）有8 个叶结点，则该完全二叉树的结点个数最是（）。A .39B. 119C.111D. 239一棵非空二叉树的先序遍历序列与后序遍历序列正好相反， 则该二叉树一定满足（）。A . 是一棵满二叉树B. 所有的结点均无右孩子C. 所有的结点均无左孩子D. 只有一个叶子结点任何一个连通图的最小生成树 ()。

6、A只有一棵B. 有一棵或多棵C. 一定有多棵D. 可能不存在二、填空题：（共 28 分，每空 2 分）已知某二叉树的先序遍历次序为 abcdefg，中序遍历次序为 badcgfe，则该二叉树的后序遍次序，层次遍历次序。对于长度为 n 的关键字有序的线性表，若进行顺序查找，则平均时间复杂度；采用二分法查找，则平均时间复杂度；在一棵度为3 的树中度为3 的结点个数为度为2 的结点个数为度为1 的结点个数为则度为0 的结点个数。在一棵m 阶B-树中，除根结点外非叶结点至少棵子树，至多棵子树。第 2 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点

7、提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是 算法，最费时间的算法如图所示的有向无环图可以排种不同的拓扑序列。给定一组数据6，2，7，10，3，12，以它构造一棵哈夫曼树，则树高为，带路径长度WPL 的值为。8. 已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,42；则快速排序一趟排序的结果是，希尔排序（初始步长为3）一趟排序的果是。三、简答题：（共 52 分）13、24、3790、53、34 分）该平衡二叉树的高度是多少？其根节点的关键字是

8、什么？其中经过了哪些调整？（指出调整名称和次数）根据下图G 以及它的存储，分别写出广度和深度遍历结果。设第一个访问结点是1。（6 分）第 3 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法下图所示的AOE 分）完成整个工程所需的总时间是多少？给出整个工程的关键活动和关键路径。设散列表的长度为 13，散列函数为 H（k）=k%13，给定的关键码序列为 68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。 分）0123456789101112如何选择能沟

9、通每个城市且总代价最省的n-1 条线路，画出所有可能的选择。 分）6. 已知关键字序列（60，20，31，1，5，44，55，61，200），写出对它进行第一趟快速排序（以第一个关键字为基准）后的序列的值，并指出它的稳定性（6 分）第 4 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法请给出Dijkstra 1 Dijkstra 算法是否还能正常运行？ 为什么？ 如果不能正常运行请给出解决方法。 分）已知关键字序列在R1.8中的初始状态为R4870336524561

10、29212345678写出在将它调整为大根堆的过程中每一次筛选后R 的状态。 （6 分）四、算法设计题：（共 40 分）请设计合理算法，在O(n)时间复杂度条件下，将中缀式a + 3*b + 4*(c-d) 式并计算出表达式的值，若a=1，b=2，c=4，d=3，给出计算结果。 分）假设二叉树采用二叉链存储结构进行存储，每个结点有data、lchild 和 rchild 三个域。设计一x （值的节点），并给出你所写出的算法的时间复杂度。（设二叉树中结点个数为n）（10 分）请采用递归方式实现二路归并排序程序MergeSort(data, first, last)O(n*logn)时间内完成排序

11、，以数组 D=8，6，4，10，5，3，7，18顺序，以及对应的系统栈中的变化情况。分）第 5 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法一、选择题： （每个选择 2 分，共 30 分）在单链表指针为P的结点之后插入指针为s的结点，正确的操作是（）。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;若进栈

12、序列为 且进栈和出栈可以穿插进行则可能出现的出栈序列（。A3，2，6，1，4，5 C1，2，5，3，4，6B3，4，2，1，6，5 D5，6，4，2，3，1循环队列用数组A0.m-1存放其元素值，设头尾指针分别为front 和 rear的元素个数是 ( )。rear-front-1 B. rear-front+1 C. (rear-front+m)%m D. rear-front二分查找算法的时间复杂度是（）。O(n*n)B. O(n)C. O(n*log n)D . O(log n)向顺序存储的循环队列 Q 中插入新元素的过程分为三步：（ ）A.进行队列是否满的判断，存入新元素，移动队尾指针

13、B.进行队列是否空的判断，存入新元素，移动队尾指针C.进行队列是否满的判断，移动队尾指针，存入新元素D.进行队列是否空的判断，移动队尾指针，存入新元素xyxy 之前，而在后根序列中x之后，则xyxyB. xyC. xyD. xy下列二叉树中可用于实现符号的不等长高效编码。最优二叉树 B. -树 C. 平衡二叉树 D.已知哈希表地址空间为A9，哈希函数为H(k)=k mod 17A. 0B. 1C. 2D. 3第 6 页 共 20 页宁波大学 2019-2021 年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法E.

14、 4F. 5G. 6H. 79、设问题规模为 N 时，某递归算法的时间复杂度记为 T(N)，已知 T(1)=1， T(N)=2T(N/2)+N*N/2，用O表示的时间复杂度为（）。A、O(logN)、O(N)、DO(NlogN)10A.17B.15 C.14 D.1811、下面说法不正确的是（ ）。A、在聚集分析中，堆栈操作PUSH、POP、MULTIPOP 的平均代价都是O(1)。B、在记账方法中，某些操作的费用比它们的实际代价或多或少。C、势能方法中，势是与整个数据结构而不是其中的个别对象发生联系的。D、平摊分析就是将最坏和最好情况下的时间代价进行平均计算得到平摊时间复杂度12.求最长公共

15、子序列时最适合使用的算法是（）。A、分支界限法B、动态规划法C、贪心法D、回溯法下面的叙述中不正确的是（） 。 A关键活动不按期完成就会影响整个工程的完成时间 B任何一个关键活动提前完成，将使整个工程提前完成C所有关键活动都提前完成，则整个工程将提前完成 D某些关键活动若提前完成，将使整个工程提前完成设计一个判别表达式中左、右括号是否配对出现的算法，采(数据结构最佳。A. 线性表B.栈C.队列D.广义表二、填空题：（每空 2 分，共 20 分）第 7 页 共 20 页2019-2021(A(答案必须写在考点提供的答题纸上)科目代码： 9162019-2021(A(答案必须写在考点提供的答题纸上

16、)科目代码： 916总分值： 150科目名称：数据结构与算法第 第8页 共 20 页在一棵m阶B-树中，除根结点外非叶结点至少棵子树，至多棵子树。堆排序的最坏时间复杂度为。带头结点的单链表逆置算法如下：voidinvert(LinkList L)p=L-next;while(p) q=p; p=p-next; ; ;分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是 算法，最费时间的算法。5. 表达式3+(12*3-2)/4+4*5/7)+18/9的后缀表达式是。6. 著名的八皇后问题是在8x8的国际象棋棋盘上放置8个皇后，使其任意2个都不在相互攻的位置，该问题可以

17、通方法求解，总共个解。三、简答题：（每题 8 分，共 40 分）已知一棵度为m12个度为m该树中共有多少个叶子结点？2给定关键字集合 12, 21, 3, 13, 4, 43, 35, 64, 5, 14 ，构造哈希表，采用线性探测再散列处理冲突方法。设定哈希函数 H(key) = key MOD 13 ( 表长=13 )。发生冲突时请给予说明。如果二个排序算法A 和Bfa(n) = n*log n 和 fb(n) = 法时间复杂度低？试给出简要证明。已知一组待执行任务的优先级分别如下 : 37,24,42,6,53,8,72,11,3,9。假设任务的优先级越2019-2021(A(答案必须写

18、在考点提供的答题纸上)科目代码： 9162019-2021(A(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法第 第10页 共 20 页先队列。已知待排序的一组记录关键字的初始排列如下: 37,24,42,6,53,8,72,11,3,9有序排序，请给出：(1).快速排序完成第一趟划分之后的记录排列序列（以第一个关键字为基准 (2).堆排序初始建堆（大顶堆）的序列；(3).第一趟基数排序后的序列。四、算法填空题 （每空 3 分，共 36 分）V 为顶点集合，weightFPath(matrix weight) for i=1 to |V|for j=

19、1 to |V| for k=1 to if () weightjk = （2） 2、一场演唱会，现有N(1=N=200)个歌迷排队买票。售票处规定，一个人每次最多只能买两张票。假设：第i(1=i=N)位歌迷买一张票需要时间Ti；队伍中相邻的两位歌迷（第i 个人和第 i+1 个人）歌迷买两张票的时间变为 Ri，这样做可以缩短后面歌迷等待的时间。现给出 N,Ti和Ri，求使所有人都买到票的最短售票时间。输入第一行输入人数N；第二行N 个数，表示单买的时间代价Ti；第三行N-1 个数，表示由前 1 人合买的时间代价Ri。输出最短售票时间。#include #include #define N 10

20、010int 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）);printf(%dn,（7）return 0;3、有一个由数字 0、1 组成的方阵中，存在任意形状的一个或多个封闭区域，封闭区域由数字1 完整包围构成，封闭区域内至少有一个 0 。每个节点只能走上下左右 4 个方向。现要求把封闭区域

21、内的所有 0 空间都填写成 2 。输入第一行一个整数 n，表示方阵的大小(1n30)；接下来 n 行，由 0 和 1 组成的2019-2021(A(答案必须写在考点提供的答题纸上)科目代码： 9162019-2021(A(答案必须写在考点提供的答题纸上)科目代码： 916总分值： 150科目名称：数据结构与算法第 第12页 共 20 页nn 的方阵。输出填好数字 2 的完整方阵。#include#define N 32int n,p,q,gridNN= 0,queueN*N2=0; struct Positionint row; int col;void addin(int i, int qu

22、eueq0=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; i+) grid0i = gridn+1i = -

23、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 = queuep1 + offseti.col; if (gridnbr.

24、rownbr.col = 0) (11) ;p+;for (i=1;inext=p;p-next=link-next; link-next=p;p-next=link; link=p;p-next=link; link=link-next;2、 用邻接表存储图所用的空间大小（）。只与图的边数有关只与图的顶点数有关与边数的平方有关与图的顶点和边数有关3循环队列qu 的队满条（front 指向队首元素的前一位置 指向队尾元素（。(qu.rear+1) % MaxSize=(qu.front+1) % MaxSize(qu.rear+1) % MaxSize=qu.front+1(qu.rear+1

25、) % MaxSize=qu.frontqu.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-i+1D) 不确定6、 表达式a*(b+c)-d 的后缀表达式是（）。A) abcd*+-B) abc+*d-C) abc*+d-D) -+*abcd716 54 3 3 4 2 2 个，则该图有（ ）个顶点。A) 10B) 11C) 12D) 138、 m 行n 列的稀疏矩阵采用十字

26、链表表示时，其中单链表的个数为（）。A) m+1B) n+1C) m+n+1D) MAXm,n+19、以下排序算法中（在最后一趟排序结束之前可能所有元素都没有放到最终位置上。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-树的说

27、法错误的(。根结点至多有m棵子树所有叶子都在同一层次上非叶结点至少有m/2 (m为偶数)m/2+1（m为奇数）棵子树根结点中的数据是有序的14、 nn A，如果采用以列优先（列序为主序）B 中，则B 的容量为（ ）。A) n2B) n2/2C) n(n+1)/2D) (n+1)2/215、 在一个具有 n 个结点的有序单链表中插入一个新结点使其仍然有序，其算法的时间复杂度为 （ ） 。A) O(log2 n)B) O(1)C) O(n2)D) O(n)16若某线性表中最常用的操作是取第i 个元素和找第i （ 存储方式最节省运算时间。单循环链表B) 单链表C) 双向链表D) 顺序表17、 构造散

28、列(12,21,3,13,4,43,35,64,5,14)，散列H(key)=key%13，采用线性开放定址法解决冲突。在等概率的情况下，查找成功的平均查找长度是 （ ） 。A) 12/10B) 13/12C) 14/12D) 15/1218、递归程序可借助于 () 转化为非递归程序。线性表B) 队列C) 栈D) 数组19、 若某二叉树有 20 个叶子结点，有 20 个结点仅有一个孩子，则该二叉树的总结点数是()。A) 40B) 55C) 59D) 6120、 下面关于B-树和B+树的叙述中，不正确的结论是 ()。B-树和B+树都能有效地支持顺序查找。B-树和B+树都能有效地支持随机查找。B-

29、树和B+树都是平衡的多叉树。B-树和B+树都可用于文件索引结构。21、 假设用于通讯的电文仅由 6 个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32,6 （新生成的二叉树总是插入在最右），则频率为32 的字符编码是（ ）。A) 00B) 01C) 10D) 1122、 下面哪个算法的实现无关贪心策略（）。单源最短路径中的Dijkstra算法最小生成树的Prim算法最小生成树的Kruskal 算法字符串匹配中的KMP 算法23、下面哪一种方法不是平摊分析的常用技术（）。A) 聚集分析B) 动态表C) 记账方法D) 势能方法24使用二分搜索算法在 n 个有序元素表中搜索一个

30、特定元素在最好情况和最坏情况下索的时间复杂性分别为（）。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，则可能的出栈序列有（1）种。2、有n 个顶点的强连通图G 至少有（2）条边。3、 有 n e G v 度 为 （3） 。4、 设用希尔排序对序列 36, -

31、9, 0, 47, 23, 1, 8, 10, 进行排序，给出的步长依次为5,2,1， 则排序需（4）趟，第2 趟结束后，序列中数据的排列次序为 （5）。5、 B+树有两个查找的入口指针，其中一个指向根结点，另一个指向（6）。6、 设只含根结点的二叉树的高度为0，则高度为k 的二叉树的最大结点数为(7),最小点数_(8)。7、 后缀表达式 a b c + * d e * f g + / 的中缀表达式为（9）。8、 20 个节点的AVL 树的最大深度为（10）。 设根节点深度为0)9、 著名的汉诺塔问题可以通过递归求解，解决10 个盘片的汉诺塔问题共需要（11）次盘片移动。1010 米范围内的红

32、包这 11 个位置），且每秒种只能在移动不超过一米的范围内接住红包。有一个同学一开始站在这个位置，因此在第一秒，他只能接到 4,5,6 这三个位置中其中一个位置上的红包。问最多可能接到多少个红包？输入第一行 1 个整数，表示红包的总个数n；第二行开始n 2 输出一个整数，表示能接到的最多的红包个数。（每空仅限一条语句）#include #include #define N 100010 int 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) if (n=0) break;memset(dp, 0, sizeof(dp);