2013年计算机考研专业课真题及答案

2013年全国硕士研究生统一入学考试自命题试题（副卷）
******************************************************************************************** 学科与专业名称：计算机系统结构、计算机软件与理论、计算机应用技术、软件工程
考试科目代码与名称：834 计算机学科与技术基础综合
考试科目：计算机学科与技术基础综合共6 页，第1 页
考试科目：计算机学科与技术基础综合共6 页，第2 页
考试科目：计算机学科与技术基础综合共6 页，第3 页
考试科目：计算机学科与技术基础综合共6 页，第4 页
考试科目：计算机学科与技术基础综合共6 页，第5 页
考试科目：计算机学科与技术基础综合共6 页，第6 页。

2013专业课真题一、选择题(1~20题，共40分)1.在利用栈将中缀表达式A-(B+C/D)×E转化成后缀表达式的过程中，当扫描到符号”)”时，栈中的内容是A (+/B -(+C -(/D -(+/2.现有一颗含有25个结点的4叉树T，若T中所有分支(即度不为0的)结点的度均为4，则T的叶子节点数是A 15B 17C 19D 213.下列序列中，不可能是任意二叉搜索树后序遍历序列的个数是①5,3,4,10,12,8②5,4,3,10,12,18③3,4,5,12,10,8④10,12,5,4,3,8A 0B 1C 2D 34.带权无向图G如下图所示，若分别用Prim算法(从顶点0开始)和Kruskal算法求G的最小生成树，则最后选中的边的权值分别是A 5,3B 3,5C 5,4D 5,55.已知序列25,13,10,12,9,5,6,8是大根堆，在插下新元素20的过程中，共进行比较操作的次数是A 0B 1C 2D 36.若数据元素序列9,10,11,8,5,12,2,4,7是采用下列排序方法之一得到的第二遍排序后的结果，则该排序算法只可能是A 冒泡排序B 选择排序C 插入排序D 二路归并排序7.若依次将关键码20,30,50,52,60,68,70插入到初始为空的3阶B树中，则最后得到B树的根结点中所包含的关键码是A 50B 52 D 60 D 50,528.下列关于机器字长的叙述中，错误的是A通用寄存器位数等于机器字长B系统总线宽度等于机器字长C主存单元长度不大于机器字长 D ALU位数等于机器字长9.为了使计算机的数据传送和数据处理的功能可以并行实现，下列方法中有效的是A多种总线互联B以存储器为中心C多重存储器共存D以运算器为中心10.某计算机存储器按字节编址，主存容量配置为64KB，下列设计方案中，所用芯片的MOS 管门电路等基本元件性能相当，则性能最优的方案是A 4片16KB×8位SRAM芯片B 4片16KB×8位DRAM芯片C 4片32KB×4位SRAM芯片D 8片64KB×1位DRAM芯片11.下列寻址方式中，只能用于指令寻址的是A立即寻址B寄存器寻址 C 相对寻址 D 基址寻址12.下列有关微指令的叙述中，错误的是A垂直型微指令全部是功能性指令B垂直型微指令指令长度比较短C水平型微指令可完成多个微操作D水平型微指令显示表示顺序控制信息13.下列有关总线定时的叙述中，错误的是A异步全互锁定时方式的通信速度最慢B异步不互锁定时方式的通信可靠性最差C异步定时方式的握手信息可不通过联络信号产生D同步定时方式的时钟信号可由设备自行提供14.下列有关I/O接口的描述中，错误的是A每个I/O接口中至少包含一个I/O端口B一个I/O接口可以连接多个I/O设备C程序控制方式的I/O接口中可以没有状态口D不同I/O接口的I/O端口之间允许独立编址15.一个请求分页系统，测得如下利用率：CPU为5%，分页磁盘为97.5%，外设为4%，则下列措施中，可改善CPU利用率的是A更换速度更快的CPU B更换更大容量的分页磁盘C挂起内存中的某个用户进程D增加内存中的用户进程16.以下关于页式内存管理系统页面大小的叙述中，正确的是A页越大，页表也越大B页越大，则I/O开销越大C页越大，则内部碎片越大D页越大，则产生缺页中断的可能性越大17.某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台，为使系统不产生死锁，N的取值最多是A 4B 5C 6D 718.以下关于进程说法正确的是I.进程从运行状态转换到就绪状态，系统一定会发生CPU调度II.当I/O完成时，一个进程的状态有可能从等待状态转换为运行状态III.进程从等待状态转换为就绪状态，系统一定会发生CPU调度IV.进程进入终止状态，系统一定会发生CPU调度A I和IVB II和IIIC III和IVD IV19.页式内存管理系统中，物理内存地址为16位，逻辑地址为24位，页面大小为512B ，采用两级页表结构，外层页表有256页，则以下正确的是I.一个进程中最多有128个页II.一个进程中最多有32K 个页III.逻辑地址中表示外层页表、页号和页内偏移量的位数分别为8、7、9IV.逻辑地址中表示外层页表、页号和页内偏移量的位数分别为7、8、920.系统中四个进程(P1~P4)和三类资源(3个R1，2个R2，2个R3)，进程资源分配和请求状况如下表所示，则正确的是二、综合应用题(21~32，共110分)21(8分)归并排序一般从用2路归并，即在两两归并过程中，从两个有序子序列中逐次挑选关键字最小的元素。

2013年同等学力申硕《计算机科学与技术学科综合水平考试》真题（含部分答案）第一部分 数学基础课程（共40分）一、用逻辑符号表达下列语句（每小题2分，共4分）1．发光的不都是金子。

（注：给出两种表达，一种用存在量词，另一种用全称量词） 答：设M （x ）：x 发光；N （x ）：x 是金子，则：原句用存在量词表示为：∃x （M （x ）∧¬N（x ））原句用全称量词表示为：¬∀x （M （x ）→N （x ））2．有些大学生不尊敬老人。

答：设M （x ）：x 是大学生；N （x ）：x 不尊重老人，则：原句用逻辑符号表达为：∃x （M （x ）∧N （x ））。

二、填空题（第1小题2分，第2到第6小题每宅2分，共16分）1．设集合A 有100个元素，则A 有______个子集。

其中有______个子集其元素个数为奇数。

【答案】2100；299【解析】A 的子集个数=C 0 100+C 1 100+C 2 100+C 3 100+…+C 100100=（1+1）100=2100。

A 的元素个数为奇数的子集个数=C 1 100+C 3 100+…+C 99 100=C 0 99+C 1 99+C 2 99+C 3 99+…+C 98 99+C 99 99=299。

2．任意一个图中度数是奇数的顶点个数一定是______。

【答案】偶数【解析】由握手定理，无向图中各顶点的度数之和为该图中边数的2倍，因而可推出该图中度数是奇数的顶点个数一定是偶数。

3．如果四对夫妻围圆桌就座，没有任何限制条件，共有______种不同的座法；如果这四对夫妻中的四个男士和四个女士排成一排，要求男女交替，则有______种不同的排法；如果这四对夫妻围圆桌就座，要求夫妻相邻的座法有______种。

【答案】7!；1152；96【解析】（1）n个人围圆桌就坐，没有任何限制条件，则有（n-1）!种不同的座法，我们称这种排列为环排列；（2）如果这四对夫妻中的四个男士和四个女士排成一排，要求男女交替可先对四个男士进行全排列，让其站成一排，这样，四个男士之间出现三个空位，根据题意，这三个空位中必须为女士，四个男士排成的队列两边各有一个空位，一共形成5个空位，可对四个女士进行全排列，然后让她们依次插入前四个空位或者后四个空位，这样，易得共有2×4!×4!=1152种不同的排法；（3）先将每对夫妻看成一个整体，对四对夫妻进行环排列，有3!=6种排列方法，然后在每对夫妻内部进行排序，有24=16种排法，共有6×16=96种座法。

2013东南大学935 专业课真题一、选择题(1~20题，共40分)1.在利用栈将中缀表达式A-(B+C/D)×E转化成后缀表达式的过程中，当扫描到符号”)”时，栈中的内容是A (+/B -(+C -(/D -(+/2.现有一颗含有25个结点的4叉树T，若T中所有分支(即度不为0的)结点的度均为4，则T的叶子节点数是A 15B 17C 19D 213.下列序列中，不可能是任意二叉搜索树后序遍历序列的个数是①5,3,4,10,12,8②5,4,3,10,12,18③3,4,5,12,10,8④10,12,5,4,3,8A 0B 1C 2D 34.带权无向图G如下图所示，若分别用Prim算法(从顶点0开始)和Kruskal算法求G的最小生成树，则最后选中的边的权值分别是A 5,3B 3,5C 5,4D 5,55.已知序列25,13,10,12,9,5,6,8是大根堆，在插下新元素20的过程中，共进行比较操作的次数是A 0B 1C 2D 36.若数据元素序列9,10,11,8,5,12,2,4,7是采用下列排序方法之一得到的第二遍排序后的结果，则该排序算法只可能是A 冒泡排序B 选择排序C 插入排序D 二路归并排序7.若依次将关键码20,30,50,52,60,68,70插入到初始为空的3阶B树中，则最后得到B树的根结点中所包含的关键码是A 50B 52 D 60 D 50,528.下列关于机器字长的叙述中，错误的是A通用寄存器位数等于机器字长B系统总线宽度等于机器字长C主存单元长度不大于机器字长 D ALU位数等于机器字长9.为了使计算机的数据传送和数据处理的功能可以并行实现，下列方法中有效的是A多种总线互联B以存储器为中心C多重存储器共存D以运算器为中心10.某计算机存储器按字节编址，主存容量配置为64KB，下列设计方案中，所用芯片的MOS 管门电路等基本元件性能相当，则性能最优的方案是A 4片16KB×8位SRAM芯片B 4片16KB×8位DRAM芯片C 4片32KB×4位SRAM芯片D 8片64KB×1位DRAM芯片11.下列寻址方式中，只能用于指令寻址的是A 立即寻址B 寄存器寻址C 相对寻址D 基址寻址12.下列有关微指令的叙述中，错误的是A垂直型微指令全部是功能性指令B垂直型微指令指令长度比较短C水平型微指令可完成多个微操作D水平型微指令显示表示顺序控制信息13.下列有关总线定时的叙述中，错误的是A异步全互锁定时方式的通信速度最慢B异步不互锁定时方式的通信可靠性最差C异步定时方式的握手信息可不通过联络信号产生D同步定时方式的时钟信号可由设备自行提供14.下列有关I/O接口的描述中，错误的是A每个I/O接口中至少包含一个I/O端口B一个I/O接口可以连接多个I/O设备C程序控制方式的I/O接口中可以没有状态口D不同I/O接口的I/O端口之间允许独立编址15.一个请求分页系统，测得如下利用率：CPU为5%，分页磁盘为97.5%，外设为4%，则下列措施中，可改善CPU利用率的是A更换速度更快的CPU B更换更大容量的分页磁盘C挂起内存中的某个用户进程D增加内存中的用户进程16.以下关于页式内存管理系统页面大小的叙述中，正确的是A页越大，页表也越大B页越大，则I/O开销越大C页越大，则内部碎片越大D页越大，则产生缺页中断的可能性越大17.某系统中有11台打印机，N个进程共享打印机资源，每个进程要求3台，为使系统不产生死锁，N的取值最多是A 4B 5C 6D 718.以下关于进程说法正确的是I.进程从运行状态转换到就绪状态，系统一定会发生CPU调度II.当I/O完成时，一个进程的状态有可能从等待状态转换为运行状态III.进程从等待状态转换为就绪状态，系统一定会发生CPU调度IV.进程进入终止状态，系统一定会发生CPU调度A I和IVB II和IIIC III和IVD IV。

（北京）中国科学院大学2013年考研计算机软件基础真题中国科学院大学2013 年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机软件基础考生须知：1．本试卷满分为 150 分，全部考试时间总计 180 分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

第一部分：数据结构（共 70 分）一、单选题（每题 2 分，共 20 分）1. 下列关于数据的逻辑结构的叙述中，不正确的是【】。

(A) 数据的逻辑结构是数据间关系的描述(B) 线性表是典型的线性结构(C) 数据的逻辑结构分为线性结构和非线性结构(D) 数据的逻辑结构不仅反映数据间的逻辑关系，而且包含其在计算机中的存储方式2. 下列关于数据运算的叙述中，不正确的是【】。

(A) 数据运算是数据结构的一个重要方面(B) 数据运算的具体实现是在数据的逻辑结构上进行(C) 检索是一种常用的运算(D) 插入是一种常用的运算3. 在包含1000个元素的线性表中实现如下各运算，所需执行时间最长的是【】。

(A) 线性表按顺序方式存储，删除线性表的第 900 个结点(B) 线性表按链式方式存储，删除指针 P 所指向的结点(C) 线性表按顺序方式存储，在线性表的第 100 个结点后面插入一个新结点(D) 线性表按链式方式存储，在线性表的第 100 个结点后面插入一个新结点4. 设某散列表的当前状态如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18该散列表的负载因子约为【】。

(A) 0.37 (B) 0.42 (C) 0.58 (D) 0.735. 设有关键码序列（Q,G,M,Z,A,N,B,P,X,H,Y,S,T,L,K,E），采用堆排序法进行排序，经过初试建堆后关键码值 A 在序列中的序号是【】。

(A) 1 (B) 4 (C) 8 (D) 126. 栈和队列的共同特点是【】。

(A) 只允许在端点处插入和删除元素 (B) 都是先进后出(C) 都是先进先出 (D) 没有共同点7. 用链接方式存储的队列，在进行插入运算时【】。

0©0｀妙5)©0乙7最小的带权路径长度为(2+ 3)x3 + (4 + 5)x2 + (6 + 7)x 1 = 46。

5.解析：根据后序线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知X结点的后序后继是其父结点，即其右线索指向的是父结点。

为了更加形象，在解题的过程中可以画出如下草图。

三6.解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。

如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。

7.解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。

各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。

8.解析：此题为送分题。

只要掌握DF S和BF S的遍历过程，便能轻易解决。

逐个代入，手工模拟，选项D是深度优先遍历，而不是广度优先遍历。

f) { g9.解析：找出AOE网的全部关键路径为(b,d c,g)、(b,d e,h)和(b,f,h)。

根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。

利用关键路径算法可求出图中的关键路径共有三条：(b,d c,g)、(b,d e,h)和(b,f,h)。

由此可知，选项A和B中并不能包含(b,f,h)这条路径，选项C中，并不能包含(b,d c,g)和(b,d e,h)这两条路径，只有C包含了所有的关键路径，因此只有加快f和d的进度才能缩短工期（建淘宝店铺：光速考研工作室议考生在图中检验）。

10.解析：对于5阶B 树，根结点只有达到5个关键字时才能产生分裂，成为高度为2的B 树，因此高度为2的5阶B 树所含关键字的个数最少是5。

11.解析：基数排序的第l 趟排序是按照个位数字的大小来排序的，第2趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。

考研专业课复习是考研备考中至关重要的一环，真题是必不可少的备考资料。

中公考研为大家整理了2013年计算机考研专业课真题及答案，供大家下载使用，并且提供计算机考研专业课辅导，更多真题敬请关注中公考研网！2013年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40小题，每小题2分，共80分。

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

1.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是A.()OnB. ()OmnC. (min(,))OmnD. (max(,))Omn2.一个栈的入栈序列为1,2,3, ,n，其出栈序列是123,,, ,npppp。

若23p，则3p可能取值的个数是A. 3nB. 2nC. 1nD. 无法确定3.若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是A. 0B. 1C. 2D. 34.已知三叉树T中6个叶结点的权分别是2，3，4，5，6，7，T的带权（外部）路径长度最小是A. 27B. 46C. 54D. 565.若X是后序线索二叉树中的叶结点，且X存在左兄弟结点Y，则X的右线索指向的是A.X的父结点B. 以Y为根的子树的最左下结点C. X的左兄弟结点YD. 以Y为根的子树的最右下结点6.在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v插入T2形成二叉排序树T3。

下列关于T1与T3的叙述中，正确的是I. 若v是T1的叶结点，则T1与T3不同II. 若v是T1的叶结点，则T1与T3相同III. 若v不是T1的叶结点，则T1与T3不同IV. 若v不是T1的叶结点，则T1与T3相同A.仅I、IIIB. 仅I、IVC. 仅II、IIID. 仅II、IV7.设图的邻接矩阵A如下所示。

各顶点的度依次是0101001101001000AA. 1，2，1，2B. 2，2，1，1C. 3，4，2，3D. 4，4，2，28.若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A.h，c，a，b，d，e，g，fB. e，a，f，g，b，h，c，dB.C. d，b，c，a，h，e，f，g D. a，b，c，d，h，e，f，g9.下列AOE网表示一项包含8个活动的工程。

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

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

1．已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m +n 的降序链表，则最坏情况下的时间复杂度是（ ）。

A ．()O n B ．()O m n ⨯ C ．(min(,))O m n D ．(max(,))O m n 2．一个栈的入栈序列为1,2,3,,n ，其出栈序列是123,,,,n p p p p 。

若23p =，则3p 可能取值的个数是（ ）。

A ．3n -B ．2n -C ．1n -D ．无法确定3．若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T 中，则T 中平衡因子为0的分支结点的个数是（ ）。

A ．0B ．1C ．2D ．34．已知三叉树T 中6个叶结点的权分别是2，3，4，5，6，7，T 的带权（外部）路径长度最小是（ ）。

A ．27B ．46C ．54D ．565．若X 是后序线索二叉树中的叶结点，且X 存在左兄弟结点Y ，则X 的右线索指向的是（ ）。

A ．X 的父结点B ．以Y 为根的子树的最左下结点C ．X 的左兄弟结点YD ．以Y 为根的子树的最右下结点6．在任意一棵非空二叉排序树T 1中，删除某结点v 之后形成二叉排序树T 2，再将v 插入T 2形成二叉排序树T 3。

下列关于T 1与T 3的叙述中，正确的是（ ）。

I ．若v 是T 1的叶结点，则T 1与T 3不同II ． 若v 是T 1的叶结点，则T 1与T 3相同III ．若v 不是T 1的叶结点，则T 1与T 3不同IV ．若v 不是T 1的叶结点，则T 1与T 3相同A ．仅I 、IIIB ．仅I 、IVC ．仅II 、IIID ．仅II 、IV7．设图的邻接矩阵A 如下所示。

各顶点的度依次是（ ）。

831华南理工大学2013年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合(数据结构、操作系统)适用专业：计算机技术(专硕)共4页数据结构一．选择题（每小题2分，共20分）1.一个非空二叉树的中序序列是DBEACGF，后序序列是DEBGFCA，则其前序序列是____。

A）ABCDEFG B）ABDEFGC C）ABEFGDE D）ABDECFG2.顺序存储的循环队列，存储空间大小为n，队头结点下标为front，队尾结点下标为rear。

则此循环队列中的元素个数为______。

A）n+front-rear B)rear-front+1C)(rear-front)%n D)(n+rear-front+1)%n 3.下列排序方法中，平均情况下的时间复杂度是O(nlogn)且稳定的方法是___。

A）归并排序B）快速排序C）简单插入排序D）堆排序4.深度为5的5阶B树，第4层（根结点为第1层）共有最少______个关键字。

A）66B）53C）20D）795.已知广义表((c),(a),(d),((d,f)))，则以下说法正确的是_____。

A）表长为4，表头为(c)，表尾为((d,f))B）表长为4，表头为(c)，表尾为((a),(d),((d,f)))C）表长为5，表头为(c)，表尾为fD）表长为5，表头为©，表尾为((d),((d,f))6.向一棵空的二叉排序树中逐个插入5,28,4,16,32,21,3,9，则查找9的查找长度为______。

A）1B)2C)3D)47.设有一个AOE网，有3条关键路径，共有15个关键活动，下面的说法_____是正确的。

A）提前完成这15个关键活动之外的活动可以缩短工期B）这三条关键路径长度相同C）提前完成这3条关键路径中的任何一个关键活动都能缩短工期D）改变这15个关键活动之外的活动不会影响工期8.一个有向图，有n个顶点，e条边，则对其邻接表以下说法正确的是_____。

中国科学院大学2013年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机技术基础考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

一、单选题（每小题2分，共80分）1.操作系统负责管理和控制计算机系统的__________。

A. 软件资源B. 硬件资源和软件资源C. 对用户有用的资源D. 硬件资源2.UNIX操作系统产生于__________年。

A. 1965B. 1970C. 1973D. 19753.进程和程序的本质区别是_____________。

A. 前者分时使用CPU，后者独占CPUB. 前者存储在内存，后者存储在外存C. 前者在一个文件中，后者在多个文件中D. 前者是动态的，后者是静态的4.__________置换算法会产生Belady现象。

A. 最不常用B. 先进先出C. 最近最久未使用D. 最佳5.下列关于管程的叙述中，错误的是___________。

A. 管程有数据结构，但不包含对数据的操作B. 管程内部定义函数的具体实现对于外部来说是不可见的C. 管程是一个基本程序单位，可以单独编译D. 管程中引入了面向对象的思想6.如果P、V操作的信号量S的初值为3，当前值为-2，则表示有_______个等待进程。

A. 0个B. 1个C. 2个D. 3个7.进程和线程的本质区别是___________。

A. 前者存储在外存，后者存储在内存B. 前者有地址空间，后者没有地址空间C. 前者在一个文件中，后者在多个文件中D. 前者是拥有资源的基本单位，后者是程序执行的基本单位8.关于线程的优点，描述不正确的是___________。

A. 线程是具有最少开销的程序执行实体B. 撤销线程比撤销进程花费的时间短C. 线程间切换比进程间切换花费的时间短D. 由于共享资源，一个进程中的线程不能并发执行9.关于内核线程和用户线程，描述不正确的是___________。