2019年宁波大学信息科学与工程学院硕士自命题科目真题916数据结构与算法

2022年宁波大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序3、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。

A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、有关二叉树下列说法正确的是（）。

A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。

2019年宁波大学硕士研究生招生考试初试科目考试大纲科目代码、名称: 916数据结构与算法一、考试形式与试卷结构（一）试卷满分值及考试时间本试卷满分为150分，考试时间为180分钟。

（二）答题方式答题方式为闭卷、笔试。

试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。

（三）试卷内容结构数据结构与基本算法。

（四）试卷题型结构1.选择题2.简答题3.算法和程序设计填空题4.应用题二、考查目标重点考查学生对数据结构、计算机算法、基本理论、基础知识的掌握程度。

考生应熟练掌握数据结构的基本概念、设计方法和实际应用；熟练掌握重要计算机算法的基本思想、算法设计基本策略、算法复杂度分析；考生应能熟练掌握一些基本数据结构，并解决实际问题。

三、考查范围或考试内容概要（一）基础1. 计算机中算法的角色2. 算法复杂度分析3. 递归（二）线性表1. 基于顺序存储的定义和实现2. 基于链式存储的定义和实现3. 线性表的应用(三)特殊线性表（栈、队列、字符串、数组）1. 栈、队列、字符串、数组的基本概念、特点2. 栈和队列基于顺序存储的定义与实现3. 栈和队列基于链式存储的定义与实现4. 稀疏矩阵的压缩存储及转置算法实现（四）树与二叉树1. 二叉树①二叉树的定义、主要特征②二叉树基于顺序存储和链式存储的实现③二叉树重要操作的实现④线索二叉树的基本概念和构造2. 树、森林①树的存储结构②森林与二叉树的相互转换③树和森林的遍历3.特殊二叉树及应用①哈夫曼（Huffman）树②二叉排序树③平衡二叉树④堆（堆的构造和调整过程）(五) 图1.基本的图算法2.最小生成树3.单源最短路径4.最短路径5.最大流(六) 查找1.顺序查找法2.折半查找法3. B 树及其基本操作、B+树的基本概念4.散列（Hash）表（七）排序1.排序的基本概念2.基于"插入"思想的排序方法①直接插入排序②折半插入排序③希尔排序3.基于"交换"思想的排序方法①冒泡排序②快速排序4.基于"选择"思想的排序方法①简单选择排序②堆排序5. 基于"归并"思想的排序方法二路归并排序6.各种常用内部排序算法的特点及应用(八) 高级的设计与分析技术1. 动态规划2. 贪婪算法3. 分摊分析四、参考教材或主要参考书：《C程序设计》(第4版)，谭浩强，清华大学出版社，2010年。

2013年宁波大学912信号处理基础 （信号与系统＋数字信号处理）
考研真题
2014年宁波大学912信号处理基础 （信号与系统＋数字信号处理）
考研真题
2015年宁波大学912信号处理基础 （信号与系统＋数字信号处理）
考研真题
2016年宁波大学912信号处理基础 （信号与系统＋数字信号处理）
目 录
2013年宁波大学912信号处理基础（信号与系统＋数字信号处理）考研 真题 2014年宁波大学912信号处理基础（信号与系统＋数字信号处理）考研 真题 2015年宁波大学912信号处理基础（信号与系统＋数字信号处理）考研 真题 2016年宁波大学912信号处理基础（信号与系统＋数字信号处理）考研 真题 2017年宁波大学912信号与系统考研真题 2018年宁波大学912信号与系统考研真题 2019年宁波大学912信号与系统考研真题
考研真题
2017年宁波大学912信号与系统考 研真题
2018年宁波大学912信号与系统考 研真题
2019年宁波大学9

data;
ArcNode
*firstarc;
} VertexNode;
typedef struct{
VertexNode
vertex［MAX-VERTEX-NUM］;
int vexnum, arcnum;
/*图的顶点数和弧数*/
GraphKind
kind;
}AdjList;
第 2 页 共 11 页
2. 请用 Prim 算法画出右图最小生成树的生成过程。
3. 请根据输入序列{100 28 6 72 130 54 180 110 138}构造二叉查找树。如果删除元素 28，那么二
叉树又是如何？
4. 什么是 B-树？ 有何特点？ 就下列关键字序列，画出一棵 5 阶 B-树。
（20，54，69，84，71，30，78，25，93，41，7，76）
宁波大学 2019 年硕士研究生招生考试初试试题(A 卷)
(答案必须写在考点提供的答题纸上)
科目代码： 917 总分值： 150 科目名称：
数据结构与程序设计
2．已知一个单链表 L, 函数 converse 倒置该链表的结点，请在空白处正确填写代码。
Struct SLNode { DateType date; 【1】 ;
for (i=0; i< 【1】
; i++)
{ k=i ; for (j= i+1; j<=n-1; j++)
if (R[ j ] 【2】 R[ k ] )
k=j;
if （k!=i）
{ temp=R[ i ]; R[ i ] = R[ k ]; R[ k ]=temp; }
}
}