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

A．1 至-(m-1)
B．1 至 m-1 C．1 至-m
D．1 至 m
29. 在下列选项中，属于解除死锁的方法是（ ）。
A．剥夺资源法
B．资源分配图简化法
C．银行家算法
A．有向图的邻接矩阵不一定是对称矩阵
B. 无向图的邻接矩阵不一定是对称矩阵
C．若图 G 的邻接矩阵是对称的，则 G 不一定是无向图
D．若图 G 的邻接矩阵是对称的，则 G 不一定是有向图
9. 折半查找算法中查找的时间复杂度是（ ）。
A．O( n )
B．0(nlogn) C．0(logn)
D．O(n2)
一、 单项选择题：1～40 小题，每小题 2 分，共 80 分。在每小题给出的四
个选项中，请选出一项最符合题目要求的。
1. 在下面的程序段中，时间复杂度为（ ）。
int fun( int n)
{ if( n = = 1 )
return 1;
return n * fun( n - 1 );
} A．O( 2n )
B．虚拟存储管理、处理机管理、进程调度、文件系统；
C．处理机管理、存储器管理、设备管理、文件系统；
D．进程管理、中断管理、设备管理、文件系统；
26. 在下面关于并发性的叙述中正确的是（ ）。
A．并发性是指若干事件在同一时刻发生；
《数据结构与操作系统》试题 第 3页 共 7 页
B．并发性是指若干事件在不同时刻发生；
《数据结构与操作系统》试题 第 1页 共 7 页
10. 一个有序数据序列中有 15 个数据，采用折半查找法在其中查找一个数据，
最多需要比较几次就能得到结果（ ）。
A.4
B．5
C. 7

中国计量大学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.下列排序算法中，时间复杂度与快速排序相同的是（ ）。

刘A学长提供
中国计量大学 2020 年硕士研究生招生考试试题
考试科目代码：806
考试科目名称：数据结构与操作系统
所有答案必须写在报考点提供的答题纸上，答在试卷 或草稿纸上无效。
一、单项选择题（共 30 题，每小题 2 分，共 60 分）
1. 关于下面两个程序段，描述正确的是（ ）。
程序段 1：
double fun1(int n)
16. 在请求分页存储管理中，若采用先进先出的 FIFO 页面置换算法，则当进程分配
到的物理块数增加时，那么缺页中断的次数将（ ）。
A. 一定会减少
B. 一定不会增加
C. 无影响
D. 可能减少也有可能增加
17. 在采用高响应比优先调度算法中，如果所有的进程都同时到达时间（即等待时
间一样），则此时的优先权调度算法实际上和（ A．先来先服务调度算法
C．fun1 的时间复杂度大于 fun2
D．fun1 的实际运行时间小于 fun2
2. 对一个已经有序的数据序列进行排序操作，下面的描述正确的是（ ）。 A. 快速排序的时间复杂度是 O(N) B. 归并排序的时间复杂度是 O(N) C．选择排序的时间复杂度是 O(N) D.插入排序的时间复杂度是 O(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

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 页。

B. 有上邻空闲区，也有下邻空闲区
C.有下邻空闲区但无上邻空闲区;或有上邻空闲区但无下邻空闲区
D.上述答案都不是
25. 假设某一机器的内存有 4G,硬盘为 500G,请问使用虚拟内存技术后，其虚
拟 内容的容量为（ ）
A. 496G B. 4G
C. 500G
D. 504G
26.在基本分页存储管理中，逻辑地址转换为物理地址时，若页号超过页表长
块号
0
3
1
1
2
4
3
7
Байду номын сангаас
假设页的大小为512字节（ 即页内地址长度为9位），请把以下以十六进
制表示的逻辑地址0x567，通过页表转换为物理地址（也用十六进制表示）
是 （ ）。 A. 0x3417 B. 地址转换错误
C. 0x967
D. 0x567
39. 以下不是设备分配算法的是（ ）
A. 先来先服务
B. 短作业优先
43. (10 分) 在银行家算法中，若出现下述资源分配情况(5 个进程，4 类资
源)：
process Max (最大需求) Allocation（已分配） Available（系统资
源）
ABC D
A B C D ABCD
P1
275 0
1 0 0 0 1622
P2
0 6 6 10
0014
P3
3 6 10 9
到的物理块数目增加时，缺页中断的次数（ ）
A. 可能减少或不变
B.一定减少
C. 无影响
D.可能增加也可能
34. 基本分段内存管理系统中，访问一条指令需要几次访问内存（ ）？
A. 3

6. 已知一棵完全二叉树的第 4 层有 4 个叶子节点（树根为第 1 层），则这棵
完全二叉树的节点个数至少是（ ）。
A．11 B．24
C．23
D．28
《数据结构与操作系统》试卷 第 2 页 共 6 页
7. 在电子地图中，为了给用户寻找最快的路线和最短的路线，使用哪种数
据结构比较合适（ ）。
A．平衡二叉查找树 B．哈希表 C．图
B．队列中的数据有可能只有 1,3
C．输出序列最后一个元素肯定是 5 D．队列中的数据有可能只有 4,5
5. 往栈中输入序列{1,2,3,4,5}，在若干入栈与出栈操作后，下列描述错误
的是（ ）。
A．最后出栈的元素肯定是 1
B．栈有可能为空
C．栈中的数据有可能只有 1,5
D．栈中的数据有可能只有 2
9，则采用的排序算法是（ ）。
A．直接插入排序 B．冒泡排序 C．归并排序 D．快速排序
《数据结构与操作系统》试卷 第 3 页 共 6 页
15. 把数据序列 1，2，3，4，5，6，7 通过插入操作构造二叉查找树，下面 4
种插入顺序构造了 4 棵二叉查找树，在这些树上查找数字 8，比较次数最
多的是（ ）。
《数据结构与操作系统》试卷 第 1 页 共 6 页
一、单项选择题（每小题 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)
19. 假设磁头当前位于 100 道，现有一个磁道访问请求序列为 45，12，68，

中国计量大学
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 页。

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

一、单项选择题（共30题，每小题2分，共60分）1.关于时间复杂度的描述，正确的是（）。

A.两个程序段的时间复杂度相同，则其实际运行时间也相同B.如下时间复杂度是递增的：O(1),O(log2N),O(N),O(nlog2N)C.1000N+N2/99999=O(N)D.如果两个算法在最坏情况下时间复杂度相同，则平均情况下，其时间复杂度也相同2.对线性表的描述，正确的是（）。

A.在顺序表上的插入操作，其平均时间复杂度为O(N)B.在链表上的插入操作，其平均时间复杂度为O(N)C.在顺序表上访问第i个元素的操作，其平均时间复杂度为O(N)D.在链表上访问第i个元素的操作，其平均时间复杂度为O(1)3.在一个空栈上进行如下操作：PUSH1，PUSH2，PUSH3，POP，PUSH4，PUSH5，POP，POP，以下描述正确的是（）。

A.最终的栈顶元素是1B.出栈的顺序是：1，2，3C.最终的栈底元素是1D.最终留在栈中的元素是：3，4，54.在一个空队列中依次进行如下操作：ENQUEUQE1,ENQUEUQE2,ENQUEUQE3，DEQUEUE,ENQUEUQE4，ENQUEUQE5，DEQUEUE，DEQUEUE，以下描述正确的是（）。

A．队列中还剩下的元素是：1 B.最先出队的元素是：3C.最后出队的元素是：4D.出队顺序是：1，2，35.对图1的二叉树，描述正确的是（）。

A．树的高度为2 B.中序遍历结果为：ABCEFC.这是一棵AVL树D.节点C的度为3图1.二叉树6.对图2的二叉查找树，描述正确的是（）。

A．该树的深度是4B．这是一棵AVL树C．删除节点E时，可用把节点D移到原E的位置D．节点A到G的路径长度是4图2.二叉查找树7.如果把图2当作图(Graph)，则描述正确的是（）。

中国计量大学2019年硕士研究生招生考试试题考试科目代码：445 考试科目名称：汉语国际教育基础 所有答案必须写在报考点提供的答题纸上，做在试卷或草稿纸上无效。

第一部分：中外文化及跨文化交际基础知识（共50分）一、单项选择题（共25小题，每小题1分，共25分）1.我国古代保留神话资料最多的著作是（ ）A．《山海经》 B．《庄子》 C．《吕氏春秋》 D．《淮南子》2.南宋时期的书院多达136所，特别有名的是“南宋四大书院”，下面哪一个不属于“南宋四大书院”（ ）A．岳麓书院 B．东林书院 C．白鹿洞书院 D．象山书院3.“学富五车，才高八斗”的“八斗”指的是（ ）A．诸葛亮 B．曹植 C．苏轼 D．纪晓岚4.《西厢记》的作者是（ ）A．马致远 B．白朴 C．王实甫 D．关汉卿5.“丝绸之路”中东段路线：从长安到玉门关、阳关是在（ ）朝代开辟的。

A．汉代 B．东晋 C．西晋 D．唐代《汉语国际教育基础》试卷 第1 页 共 8 页6. 中国传统文化以（ ）为主体的文化。

A．儒家文化、道家文化、法家文化 B．儒家文化、道家文化、墨家文化C．儒家文化、道家文化、佛家文化 D．儒家文化、道家文化、农家文化7. 下面有力地促进秦朝各地经济文化交流的措施主要是（ ）A．统一货币、文字、度量衡 B．修驰道 C．“焚书坑儒” D．修筑长城8. 孔子的哪一位弟子喜欢过“一箪食，一瓢饮，在陋巷”的生活（ ）A．子路 B．颜回 C．公西华 D．子贡9.“吾生也有涯，而知也无涯”一语出自（ ）A．《荀子· 劝学》 B．《孟子·滕文公上》C．《庄子·养生主》 D．《庄子·逍遥游》10. 我国现存最古老的藏书楼是（ ）A．汲古阁 B．海源阁 C．天一阁 D．南三阁11.“英国诗歌之父”是（ ）A．莎士比亚 B．乔叟 C．斯宾塞 D．勃朗宁夫人12. 文艺复兴时期的名著《十日谈》的核心思想是（ ）A．反对个人主义 B．宣扬“幸福在人间” C．倡导英雄主义 D．宣扬封建迷信 13. 阿拉伯文学史上第一部成文的散文巨著是（ ）A．《古兰经》 B．《卡里莱和笛木乃》 C．《玛卡梅韵文故事》 D．《一千零一夜》 《汉语国际教育基础》试卷 第2 页 共 8 页14. 民族管弦乐曲《春江花月夜》的原名是（ ）A．《阳关三叠》 B．《潇湘水云》 C．《夕阳萧鼓》 D．《高山流水》15. 古代计时法多种多样，有一种以人一天生活为法计时。

C．深度优先搜索的结果可能不唯一
D．广度优先搜索的结果可能不唯一
9. 下列排序算法中，哪个是不稳定的（不稳定指的是：关键字相同的两个 数据，排序后它们的先后位置会变化）（ ）。
《数据结构与操作系统》试卷 第 2 页 共 7 页
A．希尔排序 B．简单选择排序 C．插入排序 D．冒泡排序 10. 二叉查找树中有 1023 个结点，查找其中一个数据时，描述正确的是（ ）。 A．至少要比较 10 次 B．最多比较 10 次 C．不可能超过 10 次 D．如果是平衡二叉查找树，可能要比较 1023 次
6. 层数为 8 的二叉树其结点个数最多有（ ）。
A．1023
B．511
C．255
D．127
7. 有 100 个结点的无向图要确保是一个连通图至少应有（ ）。
A．101 条边
B．99 条边 C．50 条边
D．6 条边
8. 关于图的描述，错误的是（ ）。
A．有向图的邻接矩阵一定是对称矩阵
B. 完全图中的边一定比连通图中的边多
25. 假设某一机器的内存有 2G,硬盘为 300G,请问使用虚拟内存技术后，其虚拟 内容的容量为（ ）
《数据结构与操作系统》试卷 第 4 页 共 7 页
A. 2G
B. 4G
C. 300G D.302G
26.在基本分段存储管理中，逻辑地址转换为物联地址时，若段号超过段表长度，
则会引起( )。
A. 输入输出中断 B. 缺段中断 C. 越界中断 D. 缺页中断
A．实用软件 B.系统软件 C. 应用软件 D. 工具软件
22. 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度

2019年中国计量大学考研专业课初试考试真题试卷
中国计量大学 2019 年硕士研究生招生考试试题
考试科目代码：815
考试科目名称：综合课 2
所有答案必须写在报考点提供的答题纸上，做在试卷 或草稿纸上无效。
一、名词解释（每小题 5 分，共 40 分） 1.职务作品 2.演绎权 3.服务商标 4.商标异议 5.市场退出 6.垄断协议 7.产品缺陷 8.再贴现 二、简答题（每小题 10 分，共 50 分） 1.简述知识产权的基本特征 2.简述授予发明专利权的条件 3.简述经济法与行政法的区别
【完】
《综合课 2》试卷 第 2 页 共 2 页
《综合课 2》试卷 第 1 页 共 2 页
2019年中国计量大学考研专业课初试考试真题试卷
4.简述不正当竞争行为的表现形式 5.简述税法与税收的关系 三、论述题（每小题 30 分，共 60 分） 1.《中华人民共和国消费者权益保护法》第 28 条规定：“采用网络、电视、电话、邮 购等方式提供营 者，应当向消费者提供经营地址、联系方式、商品或者服务的数量和质量、价款或者 费用、履行期限和方式、安全注意事项和风险警示、售后服务、民事责任等信息。”请 结合该条文，试论述经营者的信息披露义务。 2.试论述生产者、销售者的产品质量义务