2020年宁波大学数据结构与算法考研真题916.doc0页

2020年宁波大学数据结构与算法考研真题916.doc 宁波大学 2020 年硕 士 研 究 生 招 生考 试 初 试 试 题(A 卷) ( 答案必须写在考点提供的答 题纸上) 第 1 页 共 7 页 科目代码： 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 ，且 进栈 和出 栈 可以穿 插进 行， 则可 能出 现的出 栈序 列为 （ ） 。 A ．3，2 ，6 ，1 ，4，5 B．3，4，2 ，1 ，6，5 C．1 ，2，5 ，3 ，4，6 D ．5，6，4 ，2 ，3，1 3. 循 环队 列用 数组A[0..m-1]存 放其 元素 值， 设头 尾 指针分 别 为front 和rear ，则当 前队 列中 的元 素个 数是 ( ) 。 A. rear-front-1 B. rear-front+1 C. (rear-front+m)%m D. rear-front 4. 二 分查 找算 法的 时间 复 杂度是 （ ）。 A. O(n*n) B. O(n) C. O(n*log n) D . O(log n) 5. 向 顺序 存储 的循 环队 列 Q 中 插入 新元 素的 过程 分 为三步 ：（ ） 。 A.进行 队列 是否 满的 判断 ，存入 新元 素， 移动 队尾 指针 B.进行 队列 是否 空的 判断 ，存入 新元 素， 移动 队尾 指针 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. 已 知哈 希表 地址 空间 为 A[9] ，哈 希函 数为 H(k)=k mod 7 ，采 用线 性探 测 再散列 处理 冲突 。若 依次 将 数据序 列：76,45,88,21,94,77,17 存入 该散 列表 中 ，则元 素 17 存储 的下 标 为( ) ；在 等概 率情 况下查 找成 功的 平均 查找 长度为( ) 。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 H. 7 9、设 问题 规模 为N 时 ，某 递归算 法的 时间 复杂 度记 为 T(N) ，已 知T(1)=1 ，T(N)=2T(N/2)+N*N/2， 用O 表 示的 时间 复杂 度为 （ ） 。 A、O(logN) B 、O(N) C 、O(N 2 logN) D ．O(NlogN)