下载文档原格式
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快速排序，从小到大一次划分结果为（）。
![宁波大学2022年[数据结构与程序设计]考研真题](https://img.taocdn.com/s1/m/2f25eac2f80f76c66137ee06eff9aef8951e4870.png)
宁波大学2022年[数据结构与程序设计]考研真题数据结构部分一、单选题1、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5，3，4，6D．5，6，4，2，3，12、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目3、下列二叉树中，（）可用于实现符号的不等长高效编码。
A.最优二叉树B.B-树C.平衡二叉树D.二叉排序树4、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（ ）A．iB．i+1C．n-iD．n-i+15、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（ ）A．f,c,bB．f,d,bC．g,c,bD．g,d,b6、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。
A．快速排序B.堆排序C.归并排序D.插入排序7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）A.选择排序B.快速排序C.冒泡排序D.插入排序8、有n个结点的有向完全图的弧数是（ ）A.n2B.2nC.n(n-1)D.2n(n+1)9、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）A．求关键路径的方法B.求最短路径的Dijkstra方法C.深度优先遍历算法D.广度优先遍历算法10、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A.s→link=p→link;p→link=s;B.p→link=s;s→link=q;C.p→link=s→link;s→link=p;D.q→link=s;s→link=p;二、简答题1. 一颗二叉树的前序遍历的结果是1，2，3，4，5，6, 中序遍历的结果是3，2，4，6，5，1。
2019年宁波大学硕士研究生招生考试初试科目考试大纲科目代码、名称: 911电子线路（模拟电路+数字电路）一、考试形式与试卷结构（一）试卷满分值及考试时间本试卷满分为150分，考试时间为180分钟。
（二）答题方式答题方式为闭卷、笔试。
试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。
（三）试卷内容结构考试内容主要包括模拟电路和数字电路。
（四）试卷题型结构1.选择题2.简答题3. 分析计算题二、考查目标课程考试的目的在于测试考生对于模拟电路和数字电路相关的基本概念、基本理论、基础知识的掌握情况以及综合运用分析和解决电子电路现实问题的能力。
三、考查范围或考试内容概要（一）模拟电路1、常用半导体器件掌握自由电子与空穴，扩散与漂移，复合，空间电荷区、PN结、耗尽层，导电沟道等基本概念；二极管单向导电性，稳压管的稳压作用，晶体管与场效应管的放大作用的基本原理；掌握半导体二极管、晶体管、场效应管的外特性、主要参数的物理意义。
了解单结管和晶闸管的工作原理和电特性。
掌握以下基本概念和定义：放大、静态工作点、饱和失真和截止失真、直流通路与交流通路、直流负载线与交流负载线，H参数模型、放大倍数、输入电阻与输出电阻、最大不失真输出电压、静态工作点的稳定;复合管。
掌握组成放大电路的原则和各种基本放大电路的工作原理及特点，能够根据具体要求选择电路类型；掌握放大电路的分析方法，能够正确估算晶体管和场效应管基本放大电路的静态工作点和动态参数Au、Ri、Ro。
了解稳定静态工作点的必要性方法。
3、多级放大电路掌握零点漂移与温度漂移，共模信号与差模信号，共模放大倍数与差模放大倍数，共模抑制比概念和各种耦合方式的特点；正确计算多级放大电路的Au、Ri、Ro；掌握差分放大电路的静态工作点和放大倍数的计算方法；理解互补电路的接法和输入输出关系；了解共模抑制比的意义、计算方法，变压器耦合和光电耦合方式.4、集成运算放大电路掌握电流源电路的工作原理；熟悉集成运放的组成及各部分的作用，正确理解主要指标参数的物理意义及使用注意；了解典型运放的工作原理。
(答案必须写在考点提供的答题纸上)科目代码：916 总分值：150 科目名称：数据结构与算法(答案必须写在考点提供的答题纸上)科目代码：916 总分值：150 科目名称：数据结构与算法11. 下图是一个二叉树后序遍历的结果是（）。
A、abcdefB、cfabdeC、dbaecfD、cbfade12. 现有以下按前序和中序遍历二叉树的结果：前序：GAHFDBCE 中序：AHGBDCFE，该二叉树的后序遍历序列为( ) 。
A . GHABCDEF B. HABCDEFGC. ABCDEFGHD. HABCGDEF13. 一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（）。
A . 39 B. 119 C. 111 D. 23914. 一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。
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-树中，除根结点外非叶结点至少有________棵子树，至多有________棵子树。
(答案必须写在考点提供的答题纸上)科目代码：916 总分值：150 科目名称：数据结构与算法5. 分别采用堆排序、快速排序、冒泡排序和归并排序，对初态为有序的表，则最省时间的是________算法，最费时间的是________算法6. 如图所示的有向无环图可以排出________种不同的拓扑序列。
宁波大学2019年硕士研究生招生考试初试试题(A 卷)(答案必须写在考点提供的答题纸上)第 0 页 共 2 页科目代码： 871 总分值： 150 科目名称： 高等代数一、计算问答题（每小题10分，共60分）1. 设是一个阶矩阵，又设满足，用行列式的定义求2. 若向量组线性无关，试讨论的线性相关性.3. 解方程组4. 已知二次型的秩为 (1) 求的值.(2) 求正交变换，将化为标准形.(3) 求方程的解.5. 设求矩阵的不变因子，初等因子，若当标准形，有理标准形.6. 设线性变换定义为(1) 求出在下述基下的矩阵： (2) 求出在下述基下的矩阵： (3) 写出到的过渡矩阵.()ij n n a ⨯=A n .d =A ()ij n n b ⨯=B 2=, 0-≠i j ij ij b c a c .B 12,,,(2)s s >ααα 122311,,,,s s s -++++αααααααα 12312321231,,.x x x x x x x x x λλλλλ++=⎧⎪++=⎨⎪++=⎩()()()22212312312(,,)11221f x x x a x a x x a x x =-+-+++ 2.a =X QY 123(,,)f x x x 123(,,)0f x x x =131616576687⎛⎫ ⎪=--- ⎪ ⎪---⎝⎭A ，A 33:R R σ→2.σ++⎛⎫⎛⎫ ⎪ ⎪=-+ ⎪ ⎪ ⎪ ⎪-⎝⎭⎝⎭x x y z y x y z z y z σ123(1,0,0),(0,1,0),(0,0,1).e e e '''===σ123(1,1,1),(1,1,2),(0,1,1).ααα'''==-=123,,ααα123,,e e e。
2019年宁波大学硕士研究生招生考试初试科目考试大纲科目代码、名称: 917数据结构与程序设计一、考试形式与试卷结构（一）试卷满分值及考试时间本试卷满分为150分，考试时间为180分钟。
（二）答题方式答题方式为闭卷、笔试。
试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。
（三）试卷内容结构考试内容主要包括C语言程序设计（30%-40%）和数据结构（70%-60%）。
（四）试卷题型结构1.选择题2.简答题3.算法和程序设计填空题4.应用题二、考查目标在考查基本概念、基本知识、基本方法的基础上，注重考查学生运用基本知识来分析和解决实际问题的能力，注重考查数据结构算法和程序设计的能力。
三、考查范围或考试内容概要（一）C语言程序的基本结构1. 数据类型及表达式2. 基本语句、选择结构、循环结构3. 数组：掌握一维数组和二维数组的定义、初始化和数组元素的引用。
4. 函数：掌握函数的定义、参数和返回值的定义、函数原型声明。
掌握形参和实参的定义和传递。
掌握递归函数的使用。
理解和使用局部变量、静态变量、全局变量。
掌握变量的存储类别和使用，变量的作用域和生存期。
5. 指针：理解地址与指针变量的概念，掌握指针的定义、使用和相关运算符。
掌握数组指针和字符串的指针操作、能用指针作为函数参数和返回值。
理解和掌握指针数组，指向指针的指针6. 结构体与共同体：掌握结构体和共用体类型数据的定义使用，掌握结构体相关的运算符的使用。
能熟练使用结构体构成链表，掌握链表的建立、删除、插入与查找，掌握内存的动态分配和释放。
（二）一般线性表1. 基于顺序存储的定义和实现2. 基于链式存储的定义和实现3. 线性表的应用(三)特殊线性表（栈、队列、字符串、数组）1. 栈、队列、字符串、数组的基本概念、特点2. 栈和队列基于顺序存储的定义与实现（方式、特点）3. 栈和队列基于链式存储的定义与实现（方式、特点）4. 稀疏矩阵的压缩存储及转置算法实现（四）树与二叉树1. 二叉树①二叉树的定义、主要特征及相关特征的证明②二叉树基于顺序存储和链式存储的实现③二叉树重要操作的实现（建立、遍历、计算叶子结点、结点、深度等）④线索二叉树的基本概念和构造2. 树、森林①树的存储结构（重点掌握子女-兄弟表示）②森林与二叉树的相互转换③树和森林的遍历3.特殊二叉树及应用①哈夫曼（Huffman）树和哈夫曼编码的构造过程②二叉排序树③平衡二叉树④堆（堆的构造和调整过程）(五) 图1. 图的基本概念2. 图的存储及基本操作①邻接矩阵存储（无向图、有向图、无向带权图、有向带权图）②邻接表存储（无向图、有向图、无向带权图、有向带权图）③各种存储方式下操作的算法实现（图的建立、遍历、插入边、删除边等）3.图的遍历①深度优先遍历（思想、过程及算法实现）②广度优先遍历（思想、过程及算法实现）4.图的基本应用（掌握算法的思想、过程）①最小生成树问题②最短路径问题③有向图与工程（AOV 网与拓扑排序，AOE 网与关键路径）(六) 查找1.查找的基本概念2.顺序查找法（监视哨法的思想和算法）3.折半查找法（思想和算法）4. B 树及其基本操作、B+树的基本概念（思想和过程）5.散列（Hash）表（Hash 函数和解决冲突的方法的思想和过程）6.查找算法的时间复杂度、平均查找长度的分析（七）排序1.排序的基本概念2.基于"插入"思想的排序方法①直接插入排序②折半插入排序（思想和过程）③希尔排序（思想和过程）3.基于"交换"思想的排序方法①冒泡排序（思想、过程和算法）②快速排序（思想、过程和算法）4.基于"选择"思想的排序方法①简单选择排序（思想、过程和算法）②堆排序（思想和过程）5. 基于"归并"思想的排序方法二路归并排序（思想、过程）6.各种常用内部排序算法的特点及应用四、参考教材或主要参考书：《C程序设计》(第4版)，谭浩强，清华大学出版社，2010。
宁波大学2019年硕士研究生招生考试初试试题(A卷)(答案必须写在考点提供的答题纸上)科目代码：916总分值：150科目名称：数据结构与算法、、选择题：（共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].next C .j=j+1 D. j=r[j]-> next4. 向一个栈顶指针为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,e6. 循环队列存储在数组A[0..m]中，则入队时的操作为（）。
A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1)mod(m+1)7.在一个具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是（）。
浙江省考研计算机科学与技术复习资料数据结构重点复习与实战演练数据结构是计算机科学与技术专业中的一门重要课程，它是研究数据存储、组织和管理的方法与技术。
在浙江省考研计算机科学与技术专业的学习中，数据结构也被视为一个重点知识点。
本文将从数据结构的概念、常用数据结构、重点知识点以及实战演练等方面进行详细介绍。
一、数据结构概念数据结构是指数据元素之间的关系，以及数据元素本身的存储结构。
它主要包括逻辑结构和存储结构两个方面。
逻辑结构是指数据元素之间的逻辑关系，常见的逻辑结构有线性结构、树形结构和图形结构等。
存储结构是指数据元素在计算机内存中的物理存储方式，常见的存储结构有顺序存储结构和链式存储结构等。
二、常用数据结构1. 数组数组是一种线性结构，它由相同数据类型的元素组成，并按照一定顺序存储在连续的内存空间中。
数组的特点是可以通过下标直接访问元素，具有随机访问的优势。
在实际应用中，数组常用于存储一组数据。
2. 链表链表是一种常见的线性结构，它由一系列节点组成。
每个节点包含数据和指向下一个节点的指针。
链表的特点是可以在运行时动态地分配内存空间，但访问元素时需要遍历整个链表，效率较低。
在实际应用中，链表常用于实现队列、栈等数据结构。
3. 栈栈是一种特殊的线性结构，它的特点是只能在一端进行插入和删除操作。
栈的插入操作称为入栈，删除操作称为出栈。
栈具有后进先出（LIFO）的特点，常用于实现函数调用、表达式求值等。
4. 队列队列是一种特殊的线性结构，它的特点是只能在一端插入元素，在另一端删除元素。
队列的插入操作称为入队，删除操作称为出队。
队列具有先进先出（FIFO）的特点，常用于实现任务调度、广度优先搜索等。
5. 树树是一种非线性结构，它由节点和边组成。
每个节点存储数据，每条边连接两个节点。
树的特点是具有层次性和递归性，常用于组织数据、实现搜索算法等。
常见的树结构有二叉树、二叉搜索树、平衡二叉树等。
三、数据结构重点知识点在考研计算机科学与技术专业的复习中，数据结构的重点知识点主要包括以下几个方面：1. 线性表线性表是由零个或多个数据元素组成的有限序列，它包括顺序表和链表两种存储结构。
2019年宁波大学硕士研究生招生考试初试科目考试大纲科目代码、名称: 915计算机控制一、考试形式与试卷结构（一）试卷满分值及考试时间本试卷满分为150分，考试时间为180分钟。
（二）答题方式答题方式为闭卷、笔试。
试卷由试题和答题纸组成；答案必须写在答题纸（由考点提供）相应的位置上。
（三）试卷内容结构考试内容主要包括计算机控制系统组成结构、计算机控制系统通道结构、数字控制基础及基本的离散化方法、典型系统的数字控制方法、现场总线及工业网络控制基本知识（四）试卷题型结构填空题、选择题、简答题、分析计算与设计题二、考查目标课程考试的目的在于测试考生对于计算机控制系统的基本概念、基本理论、基础知识的掌握情况以及综合分析和用计算机实现工程实际控制问题的能力。
三、考查范围或考试内容概要1．计算机控制系统组成结构计算机控制系统的组成及计算机控制系统的典型形式，计算机控制系统的性能及其指标，计算机控制技术的发展；2. 计算机控制系统通道结构过程通道的类型和组成，过程的基本输入输出通道组成；3. 数字控制基础及基本的离散化方法控制采样过程，计算机控制系统的数字滤波、非线性处理、标度变换等基本数据处理技术方法，数字控制器的离散方法，数字控制系统性能分析及稳态误差及输出的求取；4. 典型系统的数字控制方法数字PID及其改进型数字PID控制器的设计、最少拍无纹波控制器的设计，熟悉最少拍系统的改进措施、掌握施密斯（Smith）预估控制、达林（Dahlin）算法等大时滞系统设计方法。
5. 现场总线及工业网络控制基本知识网络功能及分类、控制网络的特点、工业控制网络与信息网络的区别、集散控制系统（DCS）的特点、集散控制系统的体系结构、几种有影响的现场总线和现场总线控制系统(FCS)的体系结构。
参考教材或主要参考书：《计算机控制系统》刘士荣，机械工业出版社，2012.。
