中国计量大学2019年《806数据结构与操作系统》考研专业课真题试卷

中国计量大学2019年硕士研究生招生考试试题考试科目代码：806 考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。

一、 单项选择题：1～30小题，每小题2分，共60分。

1.以下T(n)表示各算法中最耗时操作的执行次数，n表示数据量，请按照时间复杂度从小到大排列，正确的是（）。

T1(n) = 100n + 200logn2T2(n) = 3n2T3(n) = 10000000nT4(n) = 300log2A.T1<T2<T3<T4 B．T2<T1<T4<T3C．T3<T4<T1<T2 D．T3<T1<T4<T22.在一个无序数据序列上进行查找，分别采用以下算法，速度最快的是（ ）。

A．折半查找 B．顺序查找 C．二叉排序树查找 D．哈希表查找3.下列关于线性表的描述，错误的是（ ）。

A.顺序表不能进行插入操作B.顺序表可以进行插入操作C.顺序表适宜于随机存取D.链表适宜于顺序存取4.往队列中依次输入序列{1,2,3,4}，经过若干入队与出队操作，队列中剩下的数据可能是（ ）。

A．1 B．2 C．3 D．4《数据结构与操作系统》试卷第1页共9 页5.往栈中依次输入序列{1,2,3,4}，经过若干入栈队与出栈操作，关于栈中剩下的数据正确的是（ ）。

A.不可能是4 B．无法确定C．不可能是2 D．不可能是16.已知一棵完全二叉树的第3层有3个叶子节点（树根为第1层），则这棵完全二叉树的节点个数最多有几个（ ）。

A．6 B．8 C．9 D．127.下列关于堆的描述，错误的是（ ）。

A．堆是满二叉树B．大根堆的树根关键字大于其子树中的所有结点的关键字C．堆一般用数组来表示D．大根堆的右子树中所有结点的关键字小于树根关键字8.关于图1的邻接矩阵，如果结点A的出度为2，则描述错误的是（ ）。

A．结点A到结点C的最短路径长度为4B. 结点A的度为3C．结点A到C只有2条路径D．结点E的度为2A B C D E FA 1 2B 34C 5 6D 7E 8F 9图1. 题8的邻接矩阵9.下列排序算法中，时间复杂度与快速排序相同的是（ ）。

2022年中国计量大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。

A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）8、有n（n>0）个分支结点的满二叉树的深度是（）。

中国计量大学
2020年硕士研究生招生考试试题
考试科目代码：806考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，答在试卷或草稿纸上无效。

一、单项选择题（共30题，每小题2分，共60分）
1.关于下面两个程序段，描述正确的是（ ）。

程序段1：
double fun1(int n)
{ if( n = = 1 )
return 1;
return n * fun( n - 1 );
}
程序段2：
double fun2(int n)
{ double s = 1;
for(int i=2; i<=n; i++)
s *= i;
return s;
}
A.两个程序段的时间复杂度相同 B．fun1的时间复杂度小于fun2
C．fun1的时间复杂度大于fun2 D．fun1的实际运行时间小于fun2
2.对一个已经有序的数据序列进行排序操作，下面的描述正确的是（ ）。

A.快速排序的时间复杂度是O(N)
B. 归并排序的时间复杂度是O(N)
C．选择排序的时间复杂度是O(N) D.插入排序的时间复杂度是O(N)
3.对于只在表的一端进行删除和插入操作的线性表，宜采用的存储结构为（ ）。

A. 队列
B. 顺序表
C. 栈
D. 双向链表
《数据结构与操作系统》试卷第1页共9 页。

中国计量大学
2019年硕士研究生招生考试试题
考试科目代码：806 考试科目名称：数据结构与操作系统所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。

一、 单项选择题：1～30小题，每小题2分，共60分。

1.以下T(n)表示各算法中最耗时操作的执行次数，n表示数据量，请按照时间复
杂度从小到大排列，正确的是（）。

T1(n) = 100n + 200log
n
2
T2(n) = 3n2
T3(n) = 10000000
n
T4(n) = 300log
2
A.T1<T2<T3<T4 B．T2<T1<T4<T3
C．T3<T4<T1<T2 D．T3<T1<T4<T2
2.在一个无序数据序列上进行查找，分别采用以下算法，速度最快的是（ ）。

A．折半查找 B．顺序查找 C．二叉排序树查找 D．哈希表查找
3.下列关于线性表的描述，错误的是（ ）。

A.顺序表不能进行插入操作
B.顺序表可以进行插入操作
C.顺序表适宜于随机存取
D.链表适宜于顺序存取
4.往队列中依次输入序列{1,2,3,4}，经过若干入队与出队操作，队列中剩下的数
据可能是（ ）。

A．1 B．2 C．3 D．4
《数据结构与操作系统》试卷第1页共9 页。

2018年中国计量大学硕士研究生入学考试试题806数据结构与操作系统一、单项选择题（每小题2分，共60分）1.下面程序段的时间复杂度为（）。

float fun(int n, float x){ float result = 1.0f;int num = n * n / 4;for(int i=0; i < num; ++i)if( i % 2 == 0 )result *= x;return result;}A．O( (n2/2)! ) B．0(n2/4) C．0(n2/2) D．O(n2)2.下列排序算法中，平均时间复杂度最小的是（）。

A．基数排序 B．直接插入排序 C．快速排序 D．希尔排序3.关于线性表的描述错误的是（）。

A. 采用顺序存储时，其存储地址必须是连续的B. 采用链式存储时，其存储地址可能是连续的C. 采用链式存储时，其存储地址必须是不连续的D. 采用链式存储时，其存储地址可能是不连续的4.往队列中输入序列{1,2,3,4,5}，在若干入队与出队操作后，下列描述错误的是（）。

A．输出序列第一个元素肯定是1 B．队列中的数据有可能只有1,3 C．输出序列最后一个元素肯定是5 D．队列中的数据有可能只有4,5 5.往栈中输入序列{1,2,3,4,5}，在若干入栈与出栈操作后，下列描述错误的是（）。

A．最后出栈的元素肯定是1B．栈有可能为空C．栈中的数据有可能只有1,5D．栈中的数据有可能只有26.已知一棵完全二叉树的第4层有4个叶子节点（树根为第1层），则这棵完全二叉树的节点个数至少是（）。

A．11 B．24 C．23 D．287.在电子地图中，为了给用户寻找最快的路线和最短的路线，使用哪种数据结构比较合适（）。

A．平衡二叉查找树B．哈希表C．图 D．线性表8.关于邻接矩阵的描述正确的是（）。

A．有向图的邻接矩阵一定是非对称矩阵B. 无向图的邻接矩阵一定是对称矩阵C．若图G的邻接矩阵是对称的，则G一定是无向图D．有向图的邻接矩阵一定是下三角矩阵9.下列排序算法中，时间复杂度最小的是（）。

2019年中国计量大学考研专业课初试考试真题试卷
中国计量大学
2019年硕士研究生招生考试试题
考试科目代码：803 考试科目名称：传感器技术1 所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。

一、填空（每空1分，共1×30=30分）
1.能量转换型传感器主要由能量变换元件构成，它不需要外电源。

如基于、
、等的传感器都属于此类传感器。

2.对传感器进行动态标定的目的是确定动态指标，主要是、
、。

3.各种电阻应变片的结构大体相同，通常由、、
、组成。

4.在光线作用下电子逸出物体表面向外发射称效应；半导体材料在光线作用下其电阻值往往会变小，这种现象称效应；半导体材料吸收光能后在PN结上产生电动势的效应称效应。

5.热电偶传感器产生的热电动势包括电势和电势两部分；热电偶的
定律为热电偶制定分度表提供了理论依据；根据定律，可允许采用第三种材料的导线连接热电偶。

6.压电式传感器的输出须先经过前置放大器处理，此放大电路有和两种形式。

压电式传感器在使用电压放大器时，连接电缆长度会影响系统；而使用电荷放大器时，其输出电压与传感器的成正比。

7.电感式传感器是以电和磁为媒介，利用电磁感应原理将被测非电量如压力、位移、流量等非电量转换成线圈或的变化，再由测量电路转换为电压或电流的变化量输出的装置。

8.应变片温度补偿的措施有、。

《传感器技术1》试卷 第1 页 共5 页。