2019年浙江宁波大学数据结构与算法考研真题.doc

2019年浙江宁波大学数据结构与算法考研真题
选择题：（共30分，每题2分）
1.采用链式存储结构表示数据时，相邻的数据元素的存储地址（）。
A.一定不连续B.不一定连续
C.一定连续D.部分连续，部分不连续

2.在一个单链表中，若*p节点不是最后节点，在*p之后插入节点*s，则执行（）。
A.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->next=p;

3.用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为()。
A.j=j->nextB.j=r[j].nextC.j=j+1D.j=r[j]->next

4.向一个栈顶指针为HS的链栈（带头结点）中插入一个s所指结点时，则执行（）。
A.s->next=HS;HS=s;B.HS->next=s;
C.s->next=HS->next;HS->next=s;D.s->next=HS;HS=HS->next;

5.已知一个推入堆栈的字符序列顺序是a,b,c,d,e,下列哪个字符序列是不能通过堆栈操作得到的字符序列（）。
A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e

6.循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A.rear=rear+1B.rear=(rear+1)mod(m-1)
C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)

7.在一个具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（）。
A.front==(rear+1)%n B.front==rear
C.front==0 D.(front+1)%n==rear

8.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概念的，插入一个元素时平均要移动表中的（）个元素。
A.(n－1)/2B.nC.n/2D.(n＋1)/2

9.对广义表A=（（a,(b)）,(c,()),d）执行操作gettail(gethead(gettail(A)))的结果是：（）。
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
11.下图是一个二叉树后序遍历的结果是（）。

A、abcdefB、cfabde
C、dbaecfD、cbfade

12.现有以下按前序和中序遍历二叉树的结果：
前序：GAHFDBCE中序：AHGBDCFE，该二叉树的后序遍历序列为()。
A.GHABCDEFB.HABCDEFG
C.ABCDEFGHD.HABCGDEF

13.一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。
A.39B.119C.111D.239

14.一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
A.是一棵满二叉树B.所有的结点均无右孩子
C.所有的结点均无左孩子D.只有一个叶子结点

15.任何一个连通图的最小生成树()。
A．只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在

填空题：（共28分，每空2分）
1.已知某二叉树的先序遍历次序为abcdefg，中序遍历次序为badcgfe，则该二叉树的后序遍历次序为____________，层次遍历次序为___________。

2.对于长度为n的关键字有序的线性表，若进行顺序查找，则平均时间复杂度为________；若采用二分法查找，则平均时间复杂度为________；

3.在一棵度为3的树中，度为3的结点个数为3，度为2的结点个数为2，度为1的结点个数为1，则度为0的结点个数为________。

4.在一棵m阶B-树中，除根结点外非叶结点至少有________棵子树，至多有________棵子树。
5.分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是________算法，最费时间的是________算法

6.如图所示的有向无环图可以排出________种不同的拓扑序列。

7.给定一组数据{6，2，7，10，3，12}，以它构造一棵哈夫曼树，则树高为__________，带权路径长度WPL的值为__________。

8.已知一组待排序的记录关键字初始排列如下：56,26,86,35,75,19,77,58,48,