下载文档原格式
中国计量大学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年中国计量大学数据科学与大数据技术专业《操作系统》科目期末试卷B（有答案）一、选择题1、下列关于批处理系统的叙述中，正确的是（）I.批处理系统允许多个用户与计算机直接交互II.批处理系统分为单道批处理系统和多道批处理系统III.中断技术使得多道批处理系统的1/O设备可与CPU并行工作A.仅II、IIIB.仅IIC.仅I、IID. 仅I、III2、实时操作系统必须在（）内处理完来白外部的事件。
A.一个机器周期B.被控对象规定时间C.周转时间D.时间片3、在个交通繁忙的十字路口，每个方向只有一个车道，如果车辆只能向前直行，而不允许转弯和后退，并未采用任何方式进行交通管理。
下列叙述正确的是（）。
A.该十字路口不会发生死锁，B.该十字路口定会发生死锁C.该上字路口可能会发生死锁，规定同时最多3个方向的车使用该十字路是最有效的方法D.该十字路口可能会发生死锁，规定南北方向的两个车队和东西方向的两个车队互斥使用十字路口是最有效的方法4、关于临界问题的一个算法（假设只有进程P0和P1，能会进入临界区）如下（i为0或1代表进程P0或者P1）：Repeatretry：if（turn！=-1）turn=i；if（turn！=i）go to retry；turn=-1；临界区：turn=0；其他区域；until false；该算法（）。
A.不能保持进程互斥进入临界区，且会出现“饥饿”B.不能保持进程互斥进入临界区，但不会出现“饥饿”C.保证进程互斥进入临界区，但会出现“饥饿”D.保证进程互斥进入临界区，不会出现“饥饿”5、若系统S1采用死锁避免方法，S2采用死锁检测方法。
下列叙述中，正确的是（）。
I.S1会限制用户申请资源的顺序，而S2不会II.S1需要进程运行所需资源总最信息，而S2不需要III.SI不会给可能导致死锁的进程分配资源，而S2会A.仅I、IIB.仅II、IIIC. 仅I、IID. I、II、III6、若I/O所花费的时间比CPU的处理时间短很多，则缓冲区（）A.最有效B.几乎无效C.均衡D.以上都不是7、用户程序发出磁盘1/0请求后，系统的正确处理流程是（）A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序8、某文件系统中，针对每个文件，用户类别分为4类：安全管理员、文件上、文件主的伙伴、其他用户：访问权限分为5类：完全控制、执行、修改、读取、写入。
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）个分支结点的满二叉树的深度是（）。
2022年中国计量大学现代科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.332、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、静态链表中指针表示的是（）。
A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。
A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。
8、有关二叉树下列说法正确的是（）。
A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。
数据结构考研真题及其答案完整版数据结构是计算机科学与技术领域中的一门重要课程，也是计算机考研中必考的一门科目。
通过研究数据结构，可以帮助我们更好地理解和应用计算机算法，提高计算机程序的效率和性能。
为了帮助考生更好地备考数据结构，本文将分享一些数据结构考研真题及其答案，供考生参考。
一、选择题1. 下列关于栈的叙述中，错误的是（）A. 栈是一种线性数据结构，具有后进先出（LIFO）的特点B. 栈可以用数组实现，也可以用链表实现C. 栈的插入和删除操作都是在同一端进行的D. 栈的插入和删除操作的时间复杂度都是O(1)答案：C解析：栈的插入操作叫做入栈，删除操作叫做出栈。
入栈和出栈操作都是在栈顶进行的，而不是同一端。
2. 假设要对n个整数关键字进行排序，以下排序算法中，平均时间复杂度最小的是（）A. 冒泡排序B. 快速排序C. 归并排序D. 直接插入排序答案：C解析：归并排序的时间复杂度是O(nlogn)，平均时间复杂度最小。
二、填空题1. 下列关于图的遍历顺序的说法中，正确的是：深度优先搜索访问的顺序是________，广度优先搜索访问的顺序是________。
答案：前序遍历，层次遍历解析：深度优先搜索即前序遍历，广度优先搜索即层次遍历。
2. 给定一个最小堆，若删除堆顶元素后，需要对堆进行调整，所采用的操作是________。
答案：下滤解析：删除堆顶元素后，将最后一个叶子节点放到堆顶，然后进行下滤操作。
三、简答题1. 请简要说明动态规划算法的基本思想和应用场景。
答：动态规划算法的基本思想是将问题分解为多个子问题，通过求解子问题的最优解来得到原问题的最优解。
它通常适用于具有重叠子问题和最优子结构性质的问题。
动态规划算法可以大大减少问题的重复计算，提高算法的效率和性能。
它在求解最短路径、最长公共子序列、背包问题等具有广泛的应用。
2. 请简要介绍红黑树的特点和应用场景。
答：红黑树是一种自平衡的二叉查找树，它具有以下特点：1) 每个节点都有一个颜色，红色或黑色；2) 根节点是黑色的；3) 叶子节点（NIL节点）都是黑色的；4) 如果一个节点是红色的，则它的两个子节点都是黑色的；5) 从根节点到叶子节点的路径上，不同路径上黑节点的个数相同。
中国计量大学
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 页。
