一、数据结构部分
1、选择题
（1）一个运算次数为n*n+nlog2n+n+1的程序时间复杂度为多少
A.O(n*n)
B.O(nlog2n)
C.O(n)
D.O(1)
（2）下列哪个算法适合求稀疏图的最小生成树
A.Prim
B.Kruskal
C.Dijkstra
D.Floyd
（3）.......
2、判断题(5个）
（1）栈和队列是双端队列的特殊情况
（2）树的子结点可以有任意多个，二叉树的孩子节点至多有两个，所有二叉树是树的特殊情况
（3）一个带有头结点的单链表，结点数据类型为整形（1）编写算法将结点元素为负整数的放到链表前面，将结点元素为正整数的放到链表后面（2）对于上述问题用何种物理结构实现较好
（4）对于一颗二叉树，打印从根节点到先序遍历下最后一个节点的路径（5）图用邻接表实现，打印从顶点i 到顶点j 的所有简单路径
二、操作系统部分
一、判断题(5个）
（1）最早的gui 界面是在window 系统上
二、操作计算题
1. 一个可抢占的动态优先级调度算法，优先数大的优先级高
（1）等待状态下，进程优先级以a 速度变化
（2）运行状态下，进程优先级以b 速度变化
2. 进程优先级变化不同，会成为不同的调度算法
问：（1）a>b>0 时是什么调度算法
（2）a< b< 0 时是什么调度算法
3. 一个含有一百万条记录的文件，每个文件16kb 到到32kb 不等，每个物理块4kb
（1）如何设计文件目录，目录文件如何实现
（2）
（3）设计文件的物理结构
（4）基于上述设计，访问某个文件的某个字节信息，最多访问几次磁盘，最少访问几次
4. 磁盘16 年第七题原题
有一个计算机的虚存系统采用请求式分页机制。其中，从内存读/写-个单元需要花费100ms。该虚存系统由内存和硬盘组成，硬盘具有以下参数：转速
7200RPM，磁盘块大小4KB，平均寻道时间5ms，传输率16b/s，控制开销为
0.1ms。请回答以下问题:
(1) 假如缺页率为0，则该虚存系统的有效访问时间是多少?
(2) 从硬盘读入或写出一个磁盘块的平均时间是多少?
(3)如果缺页率为1%，缺页时页面被修改的比例是20%，不考虑缺页时的系统开销，则该虚存系统的有效访问时间是多少?
5. 2016pv 操作题稍作修改:
有四个进程S1、S2、R1 和R2，其中S1、S2 向缓冲区BUFF 发送消息，
R1 和R2 从缓冲区BUFF 接收消息。发送和接收规则如下::
数据结构与算法考研真题
(a)S1,S2 向有可以存放两个消息的缓冲区发送消息:
(b)进程S1 发送消息M1,M2，进程S2 发送E1,E2;:
(c)缓冲区只能存放一S1 发送的消息和一个S2 发送的消息，不能存放同一进程发送的两个消息;(一共有四种可能< M1,E1>,< M2,E1>,< M1,E2>< M2,E2>):
(d)接收进程R1 只能接收接收进程R2 只能接收:
(e)当接收进程接收完成后清空缓冲区请用信号量机制来实现这4 个进程间的同步。:

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。