首都师范大学计算机学科综合历年考研试题

文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题： 140 小题，每小题 2 分，共 80 分。

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

请在答题卡上将所选项的字母涂黑。

1．已知程序如下： int s(int n) {return (n<=0) ? 0 : s(n-1) +n;}void main() { cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ． main()->S(1)->S(0) B ． S(0)->S(1)->main() C ． main()->S(0)->S(1)D ． S(1)->S(0)->main()2． 先序序列为 a,b,c,d 的不同二叉树的个数是 A ． 13B ．14C ．15D ．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是序序列。

下列关于该平衡二叉树的叙述中，正确的是5. 设有向图 G=(V,E)，顶点集 V={V o ,V i ,V 2,V 3}，边集 E={<v 0,v i >,<v 0,v 2>,<v o ,v 3>,<v i ,v 3>}, 若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A. 2 B . 3C . 4D . 56.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(kruskal )算法第二次选 中但不是普里姆( Prim )算法(从 V 4开始)第 2 次选中的边是A. (V1,V3)B . (V1,V4)C . (V2,V3)D . (V3,V4)A ． 24， 10， 5 和 24，10，7 C ．24，10，10 和 24， 14，114．现在有一颗无重复关键字的平衡二叉树B ．24，10，5 和 24， 12，7 D ．24，10，5 和 24，14，6( AVL 树) ,对其进行中序遍历可得到一个降A .根节点的度一定为 2 C .最后插入的元素一定是叶节点B .树中最小元素一定是叶节点 D .树中最大元素一定是无左子树文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持7. 下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，450&已知字符串S为“ abaabaabacacaabaabcc模式串t为“ abaabc '采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5, 则下次开始匹配时，i 和j 的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5 ，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A .直接插入排序B .起泡排序C .基数排序D .快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A. 1B. 2C. 3D. 411.希尔排序的组内排序采用的是()A .直接插入排序B .折半插入排序C .快速排序D .归并排序12.计算机硬件能够直接执行的是()I.机器语言程序n.汇编语言程序川.硬件描述语言程序A. 仅I B .仅I n C .仅I 川D. In出13.由 3 个“ 1 ”和5 个“ 0”组成的8位二进制补码, 能表示的最小整数是()A.-126 B . -125C. -32D. -314.下列有关浮点数加减运算的叙述中, 正确的是()I.对阶操作不会引起阶码上溢或下溢n.右规和尾数舍入都可能引起阶码上溢川.左规时可能引起阶码下溢I V 尾数溢出时结果不一定溢出A.仅n 川 B .仅inv C .仅I川V D. In川V15.假定主存地址为32 位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4 个字，每字32位，采用回写( Write Back )方式，则能存放4K 字数据的Cache 的总容量的位数至少是()A. 146kB. 147KC. 148KD. 158K16.假定编译器将赋值语句“x=x+3;转换为指令” add xaddt, 3,其'中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持且Cache使用直写(Write Through )方式，则完成该指令功能需要访问主存的次数至少是()文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持A ． 0B ．1C ．2D ．317．下列存储器中，在工作期间需要周期性刷新的是() A ． SRAMB ．SDRAMC ．ROMD ．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序 列为 8005， 8006，8007， 8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲 突的地址对是()B ．8002、8007C ．8001、 8008D ．8000、8004 19．下列有关总线定时的叙述中，错误的是()A •异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制20. 若磁盘转速为 7200转/分，平均寻道时间为 8ms,每个磁道包含1000个扇区，则访 问一个扇区的平均存取时间大约是 ( )A. 8.1ms B . 12.2msC . 16.3msD . 20.5ms21. 在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口之 间交换的信息不可能是 ( )A .打印字符B .主存地址C .设备状态D .控制命令22. 内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。

2010年代码：750 名称：计算机应用综合考试一、填空题（每空2分，共50分）1、（）是一系列按顺序执行的指令，这些指令告诉计算机怎样处理数据。

2、（）是将计算机数据存储的最小单位。

3、ROM是（）存储器，用户只能读取它的内容，而不能写入。

4、互联网上用于指定信息的标准标识符是（）5、在互联网上支持电子邮件的协议是（）6、网络上为数据包选择路径的网络连接设备称为（）7、局域网LAN可以设计成（）、环形或（）等几种拓扑结构。

8、OSI模型的七层分别是：物理层、（）、（）、传输层、（）、表示层、应用层。

9、c语言中的标准数据类型有整型、（）和（）。

10、C语言中用于判断的语句有if-else和（）。

11、C语言中循环语句有（）、for和（）。

12、数据库管理系统的（）定义了数据的逻辑视图、数据模型、模式。

13、软件开发的两种主要模型是（）和（）。

14、（）是对程序中处理过程相关密切程度的度量。

15、（）是对程序中两个模块相互绑定密切程度的度量。

16、线性列表的四种常用操作是插入、（）、检索和（）。

17、若一个树中任何节点的子节点个数不超过2个，则称该树为（）。

18、在图的（）遍历算法中，先处理一个节点的所有子节点，然后再处理该节点的临近节点。

二、选择题（每题3分，共60分）1、计算机中运行程序的三个步骤是按（）的持定顺序执行的。

A.取指令、执行、译码B.译码、执行、取指令C.取指令、译码、执行D.译码、取指令、执行2、（）是可以存放临时数据的独立存储单元。

A.算术逻辑单元B.寄存器C.控制单元D.磁盘驱动器3、（）是在网络上用来控制不同设备交互的一套规则。

A.模型B.协议C.对话D.同步4、根据冯.诺依曼体系结构，（）被存在存储器中。

A.数据B.程序C.数据和程序D.以上都不是5、在扩展ASCII码表示中，每个符号使用（）位。

A.8B.7C.9D.106、（）型拓扑结构的网络要使用集线器或交换机。

中国科学院大学攻读硕士学位研究生入学统一考试试题科目名称：计算机专业综合考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

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

3．试卷共16道大题，每题15分，共240分，考生可以任意选择其中10道大题回答，并在答题纸的该题答案前标明“选做本题”。

4．如果选做的题目多于10道，则判卷将按照所选做试题的题号顺序选择前10道大题计分，后续所做视为无效考试内容。

第一部分：《数据结构》第一题，简答题，共15分（1）请给出下列程序的时间复杂度（n>0）。

（2分）void func(int n) {int i,j;for(i=1,j=0; j<=n; j=j+i) i++;}（2）现有一个线性表的应用，线性表的元素总数不确定，其主要的操作是插入元素、删除表尾元素、查找表尾结点和查找指定结点的前驱结点，那么请问用怎样的数据结构比较好？请给出理由和该数据结构的C语言定义。

（3分）（3）若循环队列存储在数组A[0..m]，头指针Front指向当前队头元素，尾指针Rear指向当前队尾元素的下一个位置，那么当前实际存储有多少队列元素？现有元素x需要入队，请写出元素入队的语句。

（3分）科目名称：计算机专业综合第1页共6页（4）用如下数据结构存储广义表：typedef enum {ATOM, LIST} ElemTag;typedef struct GLNode {ElemTag tag;union {AtomType atom;struct {struct GLNode *hp, *tp;} ptr;}} *Glist;那么，对于广义表X=(A,((),(B,C)),(D,E))，给出其存储结构图，并利用Head、Tail 操作分离出元素E。

（3分）（5）现在需要从5000个元素组成的序列中，用最快的速度挑出前10个最大的元素。

请在插入排序、快速排序、堆排序、归并排序、基数排序中选择一个最合适的排序方法，并说明理由。

考研计算机学科专业基础综合真题汇编及答案解析（9）(1/27)单项选择题第1题文件系统用位图法表示磁盘空间的分配情况，位图存于磁盘的32～127号块中，每个盘块占1024个字节，盘块和块内字节均从0开始编号。

假设要释放的盘块号为409612，则位图中要修改的位所在的盘块号和块内字节序号分别是_______。

A.81、1B.81、2C.82、1D.82、2下一题(2/27)单项选择题第2题假设磁头当前位于第105道，正在向磁道序号增加的方向移动。

现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度(电梯调度)算法得到的磁道访问序列是_______。

A.110，170，180，195，68，45，35，12B.110，68，45，35，12，170，180，195C.110，170，180，195，12，35，45，68D.12，35，45，68，110，170，180，195上一题下一题(3/27)单项选择题第3题某硬盘有200个磁道(最外侧磁道号为0)，磁道访问请求序列为：130，42，180，15，199，当前磁头位于第58号磁道并从外侧向内侧移动。

按照SCAN调度方法处理完上述请求后，磁头移过的磁道数是_______。

A.208B.287C.325D.382上一题下一题(4/27)单项选择题第4题本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是_______。

A.命令解释程序B.中断处理程序C.系统调用服务程序D.用户登录程序上一题下一题(5/27)单项选择题第5题用户程序发出磁盘I／O请求后，系统的正确处理流程是_______。

A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序上一题下一题(6/27)单项选择题第6题操作系的I／O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序是_______。

计算机专业基础综合名校计算机基础综合考研真题一、首都师范大学908计算机学科综合考研真题二、计算机组成原理考研真题一、选择题1下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是（）。

[2019年408统考]A．程序的功能都通过中央处理器执行指令实现B．指令和数据都用二进制表示，形式上无差别C．指令按地址访问，数据都在指令中直接给出D．程序执行前，指令和数据需预先存放在存储器中【答案】C @@【解析】根据冯·诺依曼体系结构的基本思想可知，所有的数据和指令序列都是以二进制形式存放在存储器中，计算机根据周期来区分指令和数据，因此数据是从存储器读取而非在指令中给出，因此C项是错误的。

2下列有关处理器时钟脉冲信号的叙述中，错误的是（）。

[2019年408统考]A．时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成B．时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频C．时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定D．处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令【答案】D @@【解析】计算机完成一条指令的时间称为指令周期，而一条指令通常是由几个时钟周期组成的，因此计算机不可能每来一个时钟脉冲就执行一个新指令，所以D项是错误的。

3某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。

对于下列给定部件，该指令在取数及执行过程中需要用到的是（）。

[2019年408统考]Ⅰ．通用寄存器组（GPRs）Ⅱ．算术逻辑单元（ALU）Ⅲ．存储器（Memory）Ⅳ．指令译码器（ID）A．仅Ⅰ、ⅡB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅰ、Ⅲ、Ⅳ【答案】B @@【解析】一条指令的执行过程为取指令、分析指令、执行指令。

题目中的指令用到了寄存器和寄存器间接寻址，因此该指令在取数过程中一定会被使用到，同时寄存器间接寻址在取数阶段一定会使用存储器，最后进行加操作时一定会用到算数逻辑单元，指令译码器是属于分析指令阶段，在取数和执行指令阶段之前，因此该指令在取数及执行过程中需要用到的是Ⅰ、Ⅱ、Ⅲ。

目 录
2011年首都师范大学881计算机应用基 础综合考试考研真题
2012年首都师范大学881计算机应用基 础综合考试考研真题
2013年首都师范大学881计算机应ห้องสมุดไป่ตู้基 础综合考试考研真题
2014年首都师范大学881计算机应用基 础综合考试考研真题
2015年首都师范大学881计算机应用基 础综合考试考研真题
2011年首都师范大学881计算机应用基础综合考试考研真题
2012年首都师范大学881计算机应用基础综合考试考研真题
2013年首都师范大学881计算机应用基础综合考试考研真题
2014年首都师范大学881计算机应用基础综合考试考研真题
2015年首都师范大学881计算机应用基础综合考试考研真题

精选文档2019 年全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：1~40 小题，每题 2 分，共 80 分。

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

1.设 n 是描绘问题规模的非负整数，以下程序段的时间复杂度是x=0 ；while ( n>= ( x+l ) * ( x+l ))x=x+l ；B. O( n1/2 )C. O( n)D. O( n2)A. O( log n)2. 若将一棵树 T 转变为对应的二又树BT ，则以下对 BT 的遍历中，其遍历序列与T 的后根遍历序列同样的是A. 先序遍历B. 中序遍历C. 后序遍历D. 按层遍历3. 对 n 个互不同样的符号进行哈夫曼编码。

若生成的哈夫曼树共有115 个结点，则 n 的值是4. A. 56 B. 57( AVLC. 58D. 60T ，再将 w 插入 T 形成在随意一棵非空均衡二又树树 ) T 中，删除某结点v 以后形成均衡二又树1 2 2均衡二又树 T 3。

以下对于 T 1与 T3的表达中，正确的选项是I. 若 v 是 T 1的叶结点，则 T1与 T3可能不同样Ⅱ .若 v 不是 T1 的叶结点，则T1 与 T 3 必定不同样Ⅲ .若 v 不是 T1 的叶结点，则T1 与 T 3 必定同样A. 仅 IB. 仅 IIC. 仅 I 、ⅡD. 仅 I、Ⅲ5. 以下图所示的 AOE 网表示一项包含8 个活动的工程。

活动 d 的最早开始时间和最迟开始时间分别是A. 3 和 7B. 12 和 12C. 12 和 14D. 15 和 156.用有向无环图描绘表达式 ( x+y ) *(( x+y ) /x) ，需要的极点个数起码是A. 5B. 6C. 8D. 97.选择一个排序算法时，除算法的时空效率外，以下要素中，还需要考虑的是I. 数据的规模Ⅱ .数据的储存方式Ⅲ .算法的稳固性V. 数据的初始状态A.仅ⅢB. 仅 I、ⅡC. 仅Ⅱ、Ⅲ、 IVD. I、Ⅱ、Ⅲ、Ⅳ8. 现有长度为11 且初始为空的散列表HT ，散列函数是H( key) =key%7 ，采纳线性探查( 线性探测再散列)法解决矛盾将重点字序列87，40， 30，6， 11，22， 98，20 挨次插入到HT 后， HT 查找失败的均匀查找长度是A. 4B. 5.25C. 6D. 6.299.设主串 T=“ abaabaabcabaabc，模”式串 S=“ abaabc，”采纳 KMP 算法进行模式般配，到般配成功时为止，在般配过程中进行的单个字符间的比较次数是A. 9B. 10C. 12D. 1510. 排序过程中，对还没有确立最后地点的全部元素进行一遍办理称为一“趟”。