宁波大学2020年《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快速排序，从小到大一次划分结果为（）。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、二、运算题（每题 6 分，共24分）1. 1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。

(答案必须写在考点提供的答题纸上)一、选择题（每小题5分，共5题，共25分）1. 测得 PNP 型三极管各电极对地电位分别为 VE ＝ -4V ， VB ＝-4.7V ， VC ＝-4.6V ，说明此三极管处在哪个工作区（ ）。

A. 放大区B. 饱和区C. 截止区D. 反向击穿区2.如下图所示单相桥式整流、电容滤波电路，电容量足够大时，已知副边电压有效值为210V U =，测得输出电压的平均值() 4.5V O AV U =，则下列描述正确的是（ ）。

A. 电路正常工作B. 电容C 开路C. 负载R L 开路D. 电容C 和二极管D 1同时开路3. LC 正弦波振荡电路如图所示，该电路（ ）。

A. 由于无选频网络不能产生正弦波振荡B. 由于不满足相位平衡条件，不能产生正弦波振荡C. 由于放大器不能正常工作，不能产生正弦波振荡D. 满足振荡条件能产生正弦波振荡科目代码： 911总分值： 150科目名称：电子线路（模拟电路+数字电路）(答案必须写在考点提供的答题纸上)4. 如图所示电路中晶体管饱和管压降的数值为│U C E S │，则最大输出功率P O M ＝( ) 。

A ．L 2CES CC 2)21(R U V -B ．L2CES CC )21(R U V - C ． L 2CES CC 2)(R U V - D.2()CC CES L V U R -5. 在图示电路中，稳压管 D Z 的稳定电压 U Z = 6V ，最小稳定电流 I Zm i n = 5 mA ，输入电压 U I =12V ，电阻 R=100，要保证输出稳定电压6V ，I L 最大不应超过 ( )。

A. 60 mAB. 55 mAC. 45 mAD. 40 mA二、简答题（每小题5分，共5题，共25分）1． 用逻辑代数的基本公式和常用公式将化为最简与或式。

ABC C AB C B A BC A C B A Y ++++=2. 如图所示，请写出Y 的表达式。

(答案必须写在考点提供的答题纸上)科目代码：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，5B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，13. 循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是 ( )。

A. rear-front-1B. rear-front+1C. (rear-front+m)%mD. rear-front4. 二分查找算法的时间复杂度是（）。

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 mod7，采用线性探测再散列处理冲突。

上海科技大学2020年攻读硕士学位研究生招生考试试题科目代码：991 科目名称：数据结构与算法考生须知：1. 本试卷满分为150分，全部考试时间总计180分钟。

2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

3. 每道题的英文部分均已翻译为中文，考生可在中英文中任选一种语言作答。

1. True or False (totally 20 points, 2 points each) 判断题（共20分，每题 2 分）Please indicate in the answer sheet whether each statement is true or false. Write down “T” for being true and “F” for being false.请在答题纸上写明下列每个命题的真假。

真则打“ ”，假则打“ ”。

1.Given three functions f(n), g(n) and h(n), if f(n)ϵΩ(h(n)) and g(n)ϵΩ(h(n)), then f(n)∙g(n)ϵΩ([h(n)]2). （）给定3个函数f(n)，g(n) 和h(n)，如果f(n)ϵΩ(h(n)) 而且g(n)ϵΩ(h(n))，那么f(n)∙g(n)ϵΩ([h(n)]2)。

（）2.If a problem is in NP, it cannot be solved by a deterministic algorithm in polynomial time.（）如果一个问题属于NP，它将不能被一个时间复杂度为多项式的确定性算法解决。

（）3.The in-order depth-first traversal of a binary search tree (BST) produces elements indescending order. （）二叉搜索树的中序深度优先遍历可以产生一个降序的有序序列。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）;A．效率 B. 复杂性 C. 现实性 D. 难度2. 算法的时间复杂度取决于（）;A．问题的规模 B. 待处理数据的初态 C. A和B3.计算机算法指的是（），它必须具备（）这三个特性;(1)A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2)A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性4．一个算法应该是（）;A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 5. 下面关于算法说法错误的是（）;A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）;(1）算法原地工作的含义是指不需要任何额外的辅助空间;（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类;A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）;A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）;A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）;A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）;FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n)12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）;A. O（n）B. O(nlogn)C. O(n3)D. O(n2)13．以下哪个数据结构不是多型数据类型（）;A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构;A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构;A．栈 B. 队列 C. 完全二叉树 D. 堆16．连续存储设计时，存储单元的地址（）;A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）;A．顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。

宁波大学2020年硕士研究生招生考试初试试题(A卷)(答案必须写在考点提供的答题纸上)科目代码：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，5B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，13. 循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是 ( )。

A. rear-front-1B. rear-front+1C. (rear-front+m)%mD. rear-front4. 二分查找算法的时间复杂度是（）。

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. 下列二叉树中，( )可用于实现符号的不等长高效编码。

宁波大学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分别为队首指针和队尾指针，则判断队空的条件是（）。