当前位置：文档之家 › 2012年中国科学院研究生院计算机技术基础考研试题

2012年中国科学院研究生院计算机技术基础考研试题

  • 格式：pdf
  • 大小：389.68 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

2012年计算机专业考研真题——OS

2012年计算机专业考研真题——OS

2012年计算机专业考研真题——OS一、试题23. 下列选项中，不可能在用户态发生的事件是（）。

A. 系统调用B. 外部中断C. 进程切换D. 缺页24. 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。

A. 程序计数器B. 程序状态字寄存器C. 通用数据寄存器D. 通用地址寄存器25. 下列关于虚拟存储的叙述中，正确的是（）。

A. 虚拟存储只能基于连续分配技术B. 虚拟存储只能基于非连续分配技术C. 虚拟存储容量只受外存容量的限制D. 虚拟存储容量只受内存容量的限制26. 操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。

其合理的层次组织排列顺序是（）。

A. 用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序B. 用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C. 用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D. 用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序27. 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、。

A. P0, P1, P2, P3, P4B. P1, P0, P3, P4, P2C. P2, P1, P0, P3, P4D. P3, P4, P2, P1, P028. 若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。

Ⅰ. 若该文件的数据不在内存，则该进程进入睡眠等待状态Ⅱ. 请求read系统调用会导致CPU从用户态切换到核心态Ⅲ. read系统调用的参数应包含文件的名称A. 仅Ⅰ、ⅡB. 仅ⅡC. 仅ⅢD. Ⅰ、Ⅱ和Ⅲ29. 一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达。

它们的计算和I/O 操作顺序如下：P1：计算60ms，I/O80ms，计算20msP2：计算120ms，I/O40ms，计算40ms若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）。

2012-2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详

2012-2014年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详
圣才电子书 十万种考研考证电子书、题库视频学习平台

2012 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专
业基础综合真题及详解
一、单项选择题：1～40 小题。每小题 2 分，共 80 分。下列每题给出的四个选项中，
只有一个选项是最符合题目要求的。
1．求整数 n（n≥0）阶乘的算法如下，其时间复杂度是（ ）。
A．5 B．7 C．8 D．11 【答案】A 【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。 只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先 计算，同优先级的运算符在栈中的先计算）。表达式 a＋b－a*（（c＋d）/e－f）＋g 产生后缀 表达式的过程如下表所列：
4．若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结 点总数为（ ）。
A．12 B．20 C．32 D．33 【答案】B 【解析】本题题目的实际问题是，具有 6 层结点的平衡二叉树含有最少的结点数是多 少？Nh 表示深度为 h 的平衡二叉树中含有的最少结点数，有 N0＝0，N1＝1，N2＝2……Nh ＝Nh－1＋Nh－2＋1。 由此可得 N5＝20。对应的平衡二叉树如下图所示。
5．对有 n 个顶点 e 条边且使用邻接表存储的有向（ ）。
A．O（n）
4 / 100
圣才电子书 十万种考研考证电子书、题库视频学习平台

B．O（e） C．O（n＋e） D．O（n×e） 【答案】C 【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决 于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时，查找每个顶点的邻接点 所需时间为 O（n2），其中 n 为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所 需时间为 O（e），其中 e 为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结 构时，深度优先搜索遍历图的时间复杂度为 O（n＋e）。即可得出正确答案。

2012年硕士研究生计算机统考408考研真题及答案

2012年硕士研究生计算机统考408考研真题及答案

A. 10
B. 20
C. 32
D. 33
5．对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是
A. 存在，且唯一
B. 存在，且不唯一
A. 程序计数器
B. 程序状态字寄存器
C. 通用数据寄存器
D. 通用地址寄存器
25．下列关于虚拟存储器的叙述中，正确的是
A. 虚拟存储只能基于连续分配技术
B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制
D. 虚拟存储容量只受内存容量的限制
26．操作系的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序 是
A. 不管系统是否支持线程，进程都是资源分配的基本单位
B. 线程是资源分配的基本单位，进程是调度的基本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间
32．下列选项中，不能改善磁盘设备 I/O 性能的是 6
D. 360ms
A. 重排 I/O 请求次序
13．假定编译器规定 int 和 short 类型长度占 32 位和 16 位，执行下列 C 语言语句 unsigned short x = 65530; unsigned int y = x; 得到 y 的机器数为
3
A. 0000 7FFA
2012 年全国硕士研究生入学统一考试—计算机专业基础综合试题

2012计算机考研408真题和答案

2012计算机考研408真题和答案

(Rs)->mem
5
IF
/
ID
/
EX
M
WB


1 int
x
-513
R1
SHL R1 R1
2
4
4
3
x = a+b, x a b int
[x] [a] [b]
44
I1 LOAD R1, [a] I2 LOAD R2, [b] I3 ADD R1, R2 I4 STORE R2, [x]
1 2 3 4 5 6 7 8 9 10 11 12 13 14
}
While(L--)
longList=longList->next;
while(longList!=NULL){
if(longList==shortList)//
return longList;
else{
longList=longList->next;
shortlist=shortlist->next;
41~47
70
41.
1 m+n-1
mn 5
X-5 X
N X
2NN2 N N
42. 1
L1 L2 L
N-1
k L1 L2
L=|L1-L2|
15
X-N+1 X
N
k
2
C
LinkList Search_First_Common(LinkList L1,LinkList L2){
//
int len1=Length(L1);,len2=Length(L2);
IP
TCP
47-a
47-b
bit 0

中国科学院计算机研究所计算机编程基础考试试卷

中国科学院计算机研究所计算机编程基础考试试卷

中国科学院计算机研究所计算机编程基础考试试卷一、单选题1. 下列哪个选项是正确的关于计算机编程的？- [ ] A. 计算机编程是指使用计算机软件进行文档编辑- [ ] B. 计算机编程是指使用计算机语言创建程序- [ ] C. 计算机编程是指管理计算机硬件设备- [ ] D. 计算机编程是指进行网络安全管理2. 在Python编程语言中，用于将字符串转换为大写的方法是：- [ ] A. `lower()`- [ ] B. `capitalize()`- [ ] C. `upper()`- [ ] D. `title()`3. 以下哪种数据结构是先进后出的？- [ ] A. 队列- [ ] B. 栈- [ ] C. 链表- [ ] D. 数组二、多选题4. 下列哪些是常见的编程语言？（选择所有正确答案）- [ ] A. Python- [ ] C. Java- [ ] D. CSS5. 以下哪些是常用的控制流语句？（选择所有正确答案）- [ ] A. if语句- [ ] B. for循环- [ ] C. while循环- [ ] D. switch语句三、填空题6. 在Python中，如何打印输出"Hello, World!"？print("Hello, World!")7. 在C++编程中，声明一个名为`age`的整型变量，并赋值为18。

int age = 18;8. 在Java中，如何创建一个名为`myArray`的字符串数组，包含元素"apple"、"banana"和"cherry"？String[] myArray = {"apple", "banana", "cherry"};四、编程题9. 编写一个Python函数`calculate_average`，接收一个整数列表作为参数，计算并返回列表中所有元素的平均值。

-2012计算机考研真题及答案含选择题解析--资料

-2012计算机考研真题及答案含选择题解析--资料

2009年统考计算机考研真题一．单项选择题，每小题2分。

33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是 BA．数据链路层 B.传输层 C.会话层 D.应用层解析：在OSI参考模型中，自下而上第一个提供端到端服务的层次是（传输层）。

自下而上方法的一般从检查物理层开始。

自下而上分别称为：物理层、数据链路层、网络层、传输层、会话层、表示层和应用层。

传输层是两台计算机经过网络进行数据通信时,第一个端到端的层次，具有缓冲作用。

34．在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是 BA．12kbps B.24 kbps C.48 kbps D.96 kbps解析：1924年奈奎斯特(Nyquist)就推导出在理想低通信道的最高大码元传输速率的公式:理想低通信道的最高大码元传输速率C=2W.log2 N (其中W是想低通信道的带宽,N是电平强度)信道带宽与数据传输速率的关系可以奈奎斯特(Nyquist)准则与香农(Shanon)定律描述。

奈奎斯特定理描述了有限带宽、无噪声信道的最大数据传输速率与信道带宽的关系。

香农定理则描述了有限带宽、有随机热噪声信道的最大传输速率与信道带宽、信噪比之间的关系。

奈奎斯特准则指出：对于二进制数据信号的最大数据传输速率Rmax与通信信道带宽B（B=f,单位Hz)的关系可以写为：Rmax＝2*B(bps)香农定理指出：在有随机热噪声的信道上传输数据信号时，数据传输速率Rmax与信道带宽B、信噪比S/N 的关系为：Rmax＝B*log2(1+S/N)) [以2为底,1+S/N的对数]式中，Rmax单位为bps,带宽B单位为Hz，信噪比S/N通常以dB（分贝）数表示。

若S/N=30(dB),那么信噪比根据公式：S/N(dB)=10*lg(S/N) 则S/N=1000。

若带宽B=3000Hz，则Rma x≈30kbps。

(完整word版)2012年计算机科学与技术基础

(完整word版)2012年计算机科学与技术基础

NJU2012年计算机科学与技术基础试卷与答案科目名称：计算机科学与技术基础一、（10分)函数W 递归定义如下：⎣⎦1)1(;2/)(=+=w n w cn n W证明：)(n O W ∈解：一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：1) 在每一次调用自己时，必须是（在某种意义上）更接近于解;2） 必须有一个终止处理或计算的准则。

考点：求解递归式 算法导论P47-53二、（15分)问题P ：任给一无向图G ，判定它是否含有哈密顿(Hamilton ）回路.我们知道问题P 是NP-完全问题. 问题N ：任给一带权完全图H 与一正整数k ，判定H 中是否含有总权数为k 的哈密顿（Hamilton)回路,这就是著名的“旅行推销员问题"，我们知道问题Q 也是NP-完全问题。

假设对问题Q 做如下简化：每条边的权值只能是1或21。

简述如何利用问题P 的NP —完全性证明简化的问题Q 仍是NP-完全问题。

2。

给出具体的证明.答案来源:算法导论 P624/641课程网址:http://cs.fjzs 。

/ketang/lssxshort/part4/chapter15/15_02_03_03.htm在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的.对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。

从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。

经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。

经过图中所有顶点一次且仅一次的回路称为哈密顿回路。

具有哈密顿回路的图称为哈密顿图,具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。

平凡图是哈密顿图.三、简述软件生命期的瀑布模型.并说明这个模型的优点（10分）瀑布模型（Waterfall Model ）将将软件生命周期划分为系统需求分析、软件需求分析、概要设计、详细设计、编码、测试和运行维护等七个阶段，每一阶段工作的完成需要确认，并且规定了它们自上而下、相互衔接的固定次序，如同瀑布流水，逐级下落,最终得到软件产品，如图1所示。

11、【计算机】计算机2012年真题及解析

11、【计算机】计算机2012年真题及解析

钻石卡高级辅导系统——全程、全方位、系统化解决考研所有问题，成功率趋近 100% 万学教育官方网址：
4
钻石卡高级辅导
„-‟、 „*‟、 „(‟、„(‟、„+‟依次入栈，此时，栈中元素个数为 5，分别为：- * （ （ + ； „+‟出栈，栈中元素个数为 4，分别为：- * （ （ ； „)‟入栈，与栈顶元素„(‟配成一对，都出栈，此时，栈中元素个数为 3，分别为：- * （ ； „/‟入栈，栈中元素个数为 4，分别为：- * （ / ； „/‟出栈，栈中元素个数为 3，分别为：- * （ ； „-‟入栈，栈中元素个数为 4，分别为：- * （ - ； „-‟出栈，栈中元素个数为 3，分别为：- * （ ； „)‟入栈，与栈顶元素„(‟配成一对，都出栈，此时，栈中元素个数为 2，分别为：- * ； „*‟出栈，栈中元素个数为 1：- ； „-‟出栈，栈空； „+‟入栈，栈中元素个数为 1：+ ； „+‟出栈，栈空； 根据以上分析可知，在中缀向后缀转换过程中，栈中操作符个数最多有 5 个，选 A。 3. 若一棵二叉树的前序遍历序列为 a、e、b、d、c，后序遍历序列为 b、c、d、e、a，则根结点的孩子结点 A. 只有 e 【答案】A 【解析】题中已知，二叉树的前序遍历序列为 a、e、b、d、c，后序遍历序列为 b、c、d、e、a，则可确定二叉树的根节点为 a。 前序遍历访问次序为：访问根节点；前序遍历左子树；前序遍历右子树。从而可以确定，e 为左子树或右子树的根节点，即根节点 a 的孩子结点。 ① 假设 e 为左子树根结点，则根据后序遍历结果可知，b、c、d 一定在左子树上，且以 e 为根节点，所以，b、c、d 不可能是 a 的孩子结点。 ② 若 e 为右子树根节点，根据前序遍历结果可知，此二叉树没有左子树，故只有 e 是 a 的孩子结点。 4. 若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为 ： B. 有 e、b C. 有 e、c D. 无法确定

2012年408真题及答案解析

2012年408真题及答案解析

2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是。

int fact(int n){if (n<=1) return 1;return n*fact(n-1);}A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)2．已知操作符包括…+‟、…-‟、…*‟、…/‟、…(‟和…)‟。

将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。

A．5 B．7 C．8 D．113．若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结点。

A. 只有eB. 有e、bC. 有e、cD. 无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为。

A. 10B. 20C. 32D. 335．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。

A．O(n) B．O(e) C．O(n+e) D．O(n*e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是。

A．存在，且唯一B．存在，且不唯一C．存在，可能不唯一D．无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是。

A．d,e,f B．e,d,f C．f,d,e D．f,e,d8．下列关于最小生成树的叙述中，正确的是。

中科大计算机考研2006-2012机试试题

中科大计算机考研2006-2012机试试题

中科大计算机考研 2012 复试机试试题
（感谢王道论坛“林影清风”版主） 本次机试两个半小时，共 5 题。 1. 字符串处理：从 string.in 文件里读入两个字符串，字符串除了数字还可能包括 '—'、 'E'、'e'、'．'，相加之后输出到文件 string.out 中，如果是浮点型，要求用科学计数法表示（最 多包含 10 个有效数字） 。 Sample Input: Sample Output: 34.56 2.7956e2 2.45e2 2. 最大公约数：从 number.in 文件中读入 n 个数，求出这 n 个数的最小值、最大值以 及它们两的最大公约数，输出到文件 number.out 中。number.in 中第一行为 n，接下来为 n 个大于零的整数。 Sample Input: Sample Output: 3 484 486 3. 任务调度：从 task.in 文件中读入任务调度序列，输出 n 个任务适合的一种调度方式 到 task.out 中。每行第一个表示前序任务，括号中的任务为若干个后序任务，表示只有在前 序任务完成的情况下，后序任务才能开始。若后序为 NULL 则表示无后继任务。 Sample Input: Sample Output: Task0(Task1,Task2) Task0 Task1 Task3 Task2 Task1(Task3) Task2(NULL) Task3(NULL) 4. 火车票订购：火车经过 X 站，火车最大载客人数为 m，有 n 个订票请求，请求订购 从 a 站到 b 站的 k 张票， 若能满足订购要求则输出 1， 否则输出 0。 数据从 ticket.in 中输入， 第一行有四个数，分别为 n，m。接下来有 n 行，每行三个数分别为 a，b，k。结果输出到 文件 ticket.out 中。 Sample Input: Sample Output: 5 10 1 4 10 9 0 8 12 2 1 8 12 1 1 14 20 8 0 30 300 15 5. 最短路径：有 n 个城市 m 条道路（n<1000, m<10000)，每条道路有个长度，请找到 从起点 s 到终点 t 的最短距离，并且输出经过的城市的名，如果有多条，输出字典序最小的 那条；若从 s 到 t 没有路径，则输出“can't arrive” 。从 road.in 中读入数据，第一行有四个 数，分别为 n，m，s，t。接下来 m 行，每行三个数，分别为两个城市名和距离。输出结果 到 road.out 中。

2012年中国科学院研究生院计算机技术基础考研试题

2012年中国科学院研究生院计算机技术基础考研试题
7. 无向图的遍历过程中，选择出发顶点 v0 的次数等于该图的_________的 个数。
8. 线索二叉树是利用结点中的空闲字段来记录__________次序的二叉树。
9. 设有三对角矩阵 (aij)n×n (1≤i, j≤n)，将其三条对角线上的元素逐行地存于 数组 B[3n-2]中，使得 B[k]= aij，数组下标从 0 开始，则用 i, j 表示 k 的下 标变换公式为 k =________，用 k 表示 i, j 的下标变换公式为 i =_______， j =_________。
二、判断下列说法的正误，并纠正其中错误的说法（每小题 3 分，共 18 分）
1. 在使用优先级进程调度策略时，不存在高优先级进程等待低优先级进程 的情况。
科目名称：计算机技术基础
第1页 共4页
2. 处于同一个进程中的多个线程，CPU 寄存器对于每个线程来说是私有的。
3. 从一个小根堆中查找具有给定键值的元素，在最坏情况下需要 lgn 次比 较操作。
}
两个进程分时占用处理器使得各自语句交替执行。而在描述进程的源语言
中，“x = x – 1”和“x = x + 1”并非原子操作，它们各由三条指令完成， 用汇编语言描述如下：
x = x + 1:
LD INCR STR
R0, X R0 R0, X
/* 将数据从 X 内存位置加载到寄存器 R0 */ /* R0 值增 1 */ /* 将 R0 中的值存回 X 内存位置 */
x = x - 1:
LD DECR STR
R0, X R0 R0, X
/* 将数据从 X 内存位置加载到寄存器 R0 */ /* R0 值减 1 */ /* 将 R0 中的值存回 X 内存位置 */

2012计算机考研408真题和答案

2012计算机考研408真题和答案

A
100
90 CPU
I/O
CPU
50% I/O
A
()
A. 55
B. 60
C. 65
D. 70
13
int short
32 16
C
unsighned short x = 65530;
unsigned int y = x;
y
()
A. 0000 7FFAH
B. 0000 FFFAH C. FFFF 7FFAH
A. 10
5
n
e
()
A. O(n)
6
()
A.
C.
7
B. 7
C. 8
a, e, b, d, c
B. e b 6
C. e c
B. 20
C. 32
B. O(e)
C. O(n+e)
B. D. Dijkstra b ()
D. O(n2) a+b-a*((c+d)/e-f)+g
() D. 11 b, c, d, e, a D. 1 D. 33
S IP
47-a
IP
40
45 00 00 30 01 9b 40 00 80 06 1d c8 c0 a8 00 08 d3 44 47 50 1
0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00
45 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08 2
1 2 3 4 5 6 7 8 9 10 11 12 13 14
I1 IF ID EX M WB

2012考研计算机真题及答案解析(详细)

2012考研计算机真题及答案解析(详细)

2012年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．求整数n（n≥0）阶乘的算法如下，其时间复杂度是（）。

int fact(int n){if(n<=1)return 1;return n*fact(n-1);}A．O(log2n)B．O(n)C．O(nlog2n)D．O(n2)2．已知操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。

将中缀表达式a+b-a*((c+d)/e-f)+g转换为后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。

若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（）。

A．5B．7C．8D．113．若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。

A．只有e B．有e、b C．有e、c D．无法确定4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（）。

A．12B．20C．32D．335．对有n个顶点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是（）。

A．O(n)B．O(e)C．O(n+e)D．O(n×e)6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（）。

A．存在，且唯一B．存在，且不唯一C．存在，可能不唯一D．无法确定是否存在7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）。

A．d，e，f B．e，d，fC．f，d，e D．f，e，d8．下列关于最小生成树的说法中，正确的是（）。

2012年考研计算机统考408真题

2012年考研计算机统考408真题

2012年考研计算机统考408真题一、单项选择题1.求整数n（n>=0)阶乘的算法如下，其时间复杂度是 1 。

Int fact（int n）｛If(n<=1) return 1；Return n＊fact（n—1);A.O(log2n）B.O（n）C.O（nlog2n)D.O(n2)2.已知操作符包括’+’、'—‘、’＊'、'/'、’（‘和')’。

将中缀表达式a+b—a＊（（c+d/e—f)+g转换为等价的后缀表达式ab+acd+e/f—＊-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空,则转换过程中同时保存在栈中的操作符的最大个数是2 。

A. 5B.7C.8D.113.若一棵二叉树的前序遍历序列为a,e，b，d，c,后序遍历序列为b,c,d,e,a，则根结点的孩子结点 3 。

A.只有eB.有e,bC.有e，cD.无法确定4.若平衡二叉的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为 4 。

A.10B.20C.32D.335.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是 5 。

A.O（n)B.O（e）C.O（n+e)D.O(n*e）6.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零,则关于该图拓扑序列的结论是 6 。

A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在7.对如下有向图带权图，若采用迪杰斯特位（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余最短路径的目标顶点依次是7 。

A.d，e，fB.e，d，fC.f,d，eD.f，e,d8.下列关于最小生成树的叙述中,正确的是8 。

I。

最小生成树的代价唯一.II.所有权值最小的边一定会出现在所有的最小生成树中。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
远得不到执行。
八、（18 分）假定某系统中有 6 个进程 {P0, P1, P2, P3, P4, P5} 和 4 类资源 {A, B, C, D}，各资源的数量分别为 15、6、9、10，采用 Dijkstra 银行家算法来 避免死锁，T0 时刻的资源分配情况如下所示：
Allocation
Max
process A B C D A B C D
x=x-1
LD DECR STR
R0, X R0 R0, X
/* 将数据从 X 内存位置加载到寄存器 R0 */ /* R0 值减 1 */ /* 将 R0 中的值存回 X 内存位置 */
根据上述信息完成下列各题： 1. （3 分）写出一个可能的语句执行序列，直到打印出"x is 10" 2. （5 分）写出一个可能的语句或原子指令执行序列，直到打印出"x is 8" 3. （4 分）利用信号量机制修改上述并发进程 P1 和 P2，使得 printf()永
6. 画出和下列已知访问序列对应的森林 森林的先序次序访问序列为：NHMCLIBKDFJEAG 森林的中序次序访问序列为：MCHLNBIFDJAGEK。
四、（8 分）试编写算法，计算 i 2 (i=0,1,… n-1) 的值并依次存入整数数组 a[MAXSIZE]中。假设计算机中允许的最大整数为 MAXINT。
二、判断下列说法的正误，并纠正其中错误的说法（每小题 3 分，共 18 分）
1. 在使用优先级进程调度策略时，不存在高优先级进程等待低优先级进程 的情况。
科目名称：计算机技术基础
第 页 共4页
2. 处于同一个进程中的多个线程 CPU 寄存器对于每个线程来说是私有的。
3. 从一个小根堆中查找具有给定键值的元素，在最坏情况下需要 lgn 次比 较操作。
}
两个进程分时占用处理器使得各自语句交替执行。而在描述进程的源语言
中，“x = x – 1”和“x = x + 1”并非原子操作，它们各由三条指令完成， 用汇编语言描述如下：
x=x+1
LD INCR STR
R0, X R0 R0, X
/* 将数据从 X 内存位置加载到寄存器 R0 */ /* R0 值增 1 */ /* 将 R0 中的值存回 X 内存位置 */
科目名称：计算机技术基础
第2页 共4页
七、（12 分）现有如下两个并发进程在一个单处理器系统上运行：
P1: { shared int x; x = 10; while (1) { x = x - 1; x = x + 1; if (x != 10) printf("x is %d",x) }
}
P2: { shared int x; x = 10; while (1) { x = x - 1; x = x + 1; if (x != 10) printf("x is %d",x) }
7. 无向图的遍历过程中，选择出发顶点 v0 的次数等于该图的_________的 个数。
8. 线索二叉树是利用结点中的空闲字段来记录__________次序的二叉树。
9. 设有三对角矩阵 (aij)n×n (1≤i j≤n)，将其三条对角线上的元素逐行地存于 数组 B[3n-2]中，使得 B[k]= aij，数组下标从 0 开始，则用 i j 表示 k 的下 标变换公式为 k =________，用 k 表示 i j 的下标变换公式为 i =_______ j =_________。
2. 在段页式系统中（无快表），为获得一条指令或数据，都需三次访问内存： 第一次从内存中取得______________；第二次从内存中取得________ 第三次从内存中取得指令或数据。
3. 所有同步机制都限等 待、___________。
4. 在操作系统环境下，进程对资源共享的方式主要有__________方式和 ___________方式。
4. Huffman 树的结点个数一定是偶数。
5. 在一个包含 n 个元素的线性表中查找指定元素，采用折半查找比采用顺 序查找所需时间少。
6. 广义表 (a, (b c)) 的表头是 a，表尾是 (b c)。
三、简答题（每小题 5 分，共 30 分）
1. 进程控制块（PCB）中的进程控制信息主要包括哪些内容？
中国科学院研究生院 2012 年招收攻读硕士学位研究生入学统一考试试题
科目名称：计算机技术基础
考生须知：
1．本试卷满分为 150 分，全部考试时间总计 180 分钟。 2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、填空题（每空 2 分，共 36 分）
1. 处理机高级调度又称__________或长程调度，其调度对象是________。
五、（16 分）求证：若一棵二叉树的先序序列是 u u2 un ，则其中序序列是 up up up 当且仅当序列1 2 n 可通过一个栈得到序列 p p2 pn 。
六、（12 分）假设以三元组 (F, C, L/R) 的形式输入一棵二叉树的各条边（其中 F 表示父结点标识，C 表示子结点标识，L/R 表示 C 为 F 的左子结点或右子 结点），且在输入的三元组序列中，C 是按层次顺序出现的。设结点的标识 是字符类型。F= ^ 时 C 为根结点标识，若 C 也为 ^ ，则表示输入结束。试 根据上述信息完成下列各题。 1. （4 分）已知一组有效的三元组输入序列为：^AL ABL ACR BDL BER CFR EGL EHR FIL ^^L，请画出其所对应的二叉树； 2. （8 分）试编写算法，由输入的三元组序列建立二叉树的二叉链表。
2. 简述多道批处理系统的优缺点。
3. 简述操作系统的主要任务和功能。
4. 假设 fork()调用成功，则下面的程序可能的输出有哪些？
main() { int pid; pid = fork(); printf(“%d, ”, pid);
}
5. 一个用高级语言编写的程序在计算机上运行时所消耗的时间一般取决于 哪些因素？什么是算法的时间复杂度？
P0
20219555
P1
01112233
P2
41027544
P3
10013332
P4
11005221
P5
10114444
根据上述信息完成下列各题： 1. （3 分）计算 T0 时刻的可用资源向量 Available
科目名称：计算机技术基础
第3页 共4页
2. （4 分）计算 T0 时刻的需求矩阵 Need 3. （5 分）T0 时刻是否安全？若安全，则请给出进程执行顺序，并给出每
5. 后缀表达式 3 2 * 4 – 5 6 3 / * + 的值为_____，表达式 c*(b+2)+(2-a)/3 对 应的后缀表达式为____________________。
6. 用链式存储结构实现二叉树，每个结点除数据域外还包含指向左右子结 点的链接指针，在这种存储结构下，n 个结点的二叉树共有______个指 针域，其中________个指针域存放了地址，而________个指针域存放的 是空指针。
一进程结束后的 Available 向量 若不安全，请说明原因； 4. （6 分）若现在进程 P5 请求资源 (3, 2, 3, 3)，该请求能否得到满足？为
什么？
科目名称：计算机技术基础
第4页 共4页