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

第1页 / 共5页

第2页 / 共5页

第3页 / 共5页

第4页 / 共5页

第5页 / 共5页

2019 年浙江宁波大学数据结构与算法考研真题一、选择题：（共 30 分，每题 2 分） 1. 采用链式存储结构表示数据时，相邻的数据元素的存储地址（）。 A. 一定不连续 C. 一定连续 B. 不一定连续 D. 部分连续，部分不连续 2. 在一个单链表中，若*p 节点不是最后节点，在*p 之后插入节点*s，则执行（）。 A. s->next = p; p->next = s; C. s->next = p->next ; p = s; B. s->next = p->next ; p->next = s; D. p->next = s; s->next = p; 3. 用数组 r 存储静态链表，结点的 next 域指向后继，工作指针 j 指向链中结点，使 j 沿链移动的操作为( A. j=j->next next )。 B. j=r[j].next C .j=j+1 D. j=r[j]-> 4. 向一个栈顶指针为 HS 的链栈（带头结点）中插入一个 s 所指结点时，则执行（）。 A. s->next = HS ; C. s -> next = HS->next ; HS->next = s; HS = s; B. D. HS->next = s; s->next = HS ; HS = HS->next; 5. 已知一个推入堆栈的字符序列顺序是 a,b,c,d,e, 下列哪个字符序列是不能通过堆栈操作得到的字符序列（）。 A. e,d,c,b,a B. d,e,c,b,a C. d,c,e,a,b D. a,b,c,d,e 6. 循环队列存储在数组 A[0..m]中，则入队时的操作为（）。 A. rear=rear+1 C. rear=(rear+1) mod m B. rear=(rear+1) mod (m-1) D. rear=(rear+1)mod(m+1) 7. 在一个具有 n 个单元的顺序存储的循环队列中，假定 front 和 rear 分别为队首指针和队尾指针，则判断队空的条件是（）。 A. front = = (rear +1) % n C. front = =0 B. front = = rear D. (front +1) % n = = rear 8. 对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概念的，插入一个元素时平均要移动表中的（）个元素。 A. (n－1)/2 B. n C. n/2 D. (n＋1)/2 9. 对广义表 A=（（a,(b)）,(c,()),d）执行操作 gettail(gethead(gettail(A))) 的结果是：（）。 A.（） B. （（）） C. d D. (d) 10. 构造哈希表的关键字的输入序列为(25,21,30,13,4,43,35,64,5,17,2,8)，哈希函数 H(key)=key%15，采用链地址法解决冲突。查找 64 的关键字比较次数是（）。 A. 1 B. 2 C. 4 D . 3

11. 下图是一个二叉树后序遍历的结果是（）。 A、 abcdef C、 dbaecf B、 cfabde D、 cbfade 12. 现有以下按前序和中序遍历二叉树的结果：前序：GAHFDBCE 中序：AHGBDCFE，该二叉树的后序遍历序列为 ( ) 。 A . GHABCDEF C. ABCDEFGH B. HABCDEFG D. HABCGDEF 13. 一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是（ A . D. 239 B. 119 ）。 39 C. 111 14. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。 A . 是一棵满二叉树 C. 所有的结点均无左孩子 B. 所有的结点均无右孩子 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,42；则快速排序一趟排序的结果是的结果是，希尔排序（初始步长为 3）一趟排序。一、简答题：（共 52 分） 1. 按关键字 13、24、37、90、53、34 的次序构造一棵平衡二叉树，回答以下问题：（8 分）（1）该平衡二叉树的高度是多少？（2）其根节点的关键字是什么？（3）其中经过了哪些调整？（指出调整名称和次数） 2. 根据下图 G 以及它的存储，分别写出广度和深度遍历结果。设第一个访问结点是 1。（6 分） 3. 下图所示的 AOE 网络用于描述一项工程，其中的顶点表示事件，边代表一次活动，边上的权值表示完成该活动所需的时间，试回答以下问题：（6 分） (1) 完成整个工程所需的总时间是多少？ (2) 给出整个工程的关键活动和关键路径。

4. 设散列表的长度为 13，散列函数为 H（k）=k%13，给定的关键码序列为 19，14，23，01， 68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（5 分） 0 1 2 3 4 5 6 7 8 9 10 11 12 5. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的 n-1 条线路，画出所有可能的选择。（7 分） 6. 已知关键字序列（60，20，31，1，5，44，55，61，200），写出对它进行第一趟快速排序（以第一个关键字为基准）后的序列的值，并指出它的稳定性（6 分） 7. 请给出 Dijkstra 最短路径算法的主要步骤，如果加权图如下所示，请计算从顶点 1 到其它所有顶点的最短路径，给出算法具体执行过程中顶点集合的扩展情况。如果有些弧上加权为负，请问 Dijkstra 算法是否还能正常运行？为什么？如果不能正常运行请给出解决方法。（8 分） 8. 已知关键字序列在 R[1..8]中的初始状态为 R 48 70 33 65 24 56 12 92

1 2 3 4 5 6 7 8 写出在将它调整为大根堆的过程中每一次筛选后 R 的状态。（6 分）一、算法设计题：（共 40 分） 1.请设计合理算法，在 O(n)时间复杂度条件下，将中缀式 a + 3*b + 4*(c-d)转化为对应的后缀表式并计算出表达式的值，若 a=1，b=2，c=4，d=3，给出计算结果。（15 分） 2. 假设二叉树采用二叉链存储结构进行存储，每个结点有 data、lchild 和 rchild 三个域。设计一个算法，计算一棵给定二叉树中节点值为 x 的节点个数（注意在一棵二叉树中可能存在相同节点值的节点），并给出你所写出的算法的时间复杂度。（设二叉树中结点个数为 n）（10 分） 3. 请采用递归方式实现二路归并排序程序 MergeSort(data, first, last)，在 O(n*logn) 时间内完成排序，以数组 D={8，6，4，10，5，3，7，18}为例，分析给出函数每一次递归调用的具体参数和顺序，以及对应的系统栈中的变化情况。（15 分）

资料库

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

相关推荐

考研

热门标签

最新资料