2009年考研计算机专业统考解析
- 格式:doc
- 大小:61.50 KB
- 文档页数:5
一、单项选择题1-40小题,每小题2分,共80分。
下列每题给出的四个选项中,只有一个选项是最符合题目要求的。
1 【正确答案】 B【试题解析】考查栈和队列的特点及应用。
C和D直接排除,缓冲区的特点需要先进先出,若用栈,先进入缓冲区的数据则要排队到最后才能打印,不符题意,故选B。
2 【正确答案】 C【试题解析】考查栈的最大递归深度。
时刻注意栈的特点是先进后出。
出入栈的详细过程见表A-3。
栈内的最大深度为3,故栈S的容量至少是3。
3 【正确答案】 D【试题解析】考查二叉树的特殊遍历。
分析遍历后的结点序列,可以看出根结点是在中间被访问的,而右子树结点在左子树之前,得遍历的方法是RNL。
本题考查的遍历方法并不是二叉树的三种基本遍历方法,对于考生而言,重要的是要掌握遍历的思想。
4 【正确答案】 B【试题解析】考查平衡二叉树的定义。
根据平衡二叉树的定义有,任意结点的左、右子树高度差的绝对值不超过1。
而其余三个答案均可以找到不符合的结点。
5 【正确答案】 C【试题解析】考查完全二叉树的特点。
完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层有叶结点。
第6层有叶结点则完全二叉树的高度可能为6或7,显然树高为7时结点更多。
若第6层上有8个叶结点,则前六层为满二叉树,而第7层缺失了8×2=16个叶结点,故完全二叉树的结点个数最多为27一1-16=111个结点。
6 【正确答案】 B【试题解析】考查森林和二叉树的转换。
森林与二叉树的转换规则为“左孩子右兄弟”。
在最后生成的二叉树中,父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形I:若结点v是结点u的第二个孩子结点,在转换时,结点v就变成结点u第一个孩子的右孩子,符合要求。
情形Ⅱ:结点u和v是兄弟结点的关系,但二者之中还有一个兄弟结点k,则转换后,结点v就变为结点k的右孩子,而结点k则是结点u的右孩了,符合要求。
2009-2010年计算机统考考研真题解析os2009年计算机统考真题解析(含答案)一、单项选择题,每小题 2 分,共 80 分。
23.单处理机系统中,可并行的是I 进程与进程 II 处理机与设备 III 处理机与通道 IV 设备与设备A.I、II 和 III B. I、II 和 IV C. I、III 和 IV D. II、III 和 IV24.下列进程调度算法中,综合考虑进程等待时间和执行时间的是A.时间片轮转调度算法B.短进程优先调度算法C.先来先服务调度算法 D.高响应比优先调度算法25.某计算机系统中有 8 台打印机,有 K 个进程竞争使用,每个进程最多需要 3 台打印机。
该系统可能会发生死锁的 K 的最小值是A.2 B.3 C.4 D.526.分区分配内存管理方式的主要保护措施是A.界地址保护 B.程序代码保护 C.数据保护 D.栈保护27.一个分段存储管理系统中,地址长度为32 位,其中段号占8 位,则最大段长是A.28 字节 B.216 字节 C.224 字节 D.232 字节28.下列文件物理结构中,适合随机访问且易于文件扩展的是A.连续结构B.索引结构C.链式结构且磁盘块定长D.链式结构且磁盘块变长29.假设磁头当前位于第 105 道,正在向磁道序号增加的方向移动。
现有一个磁道访问请求序列为 35,4 5,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,19530.文件系统中,文件访问控制信息存储的合理位置是A.文件控制块 B.文件分配表 C.用户口令表 D.系统注册表31.设文件F1 的当前引用计数值为1,先建立F1 的符号链接(软链接)文件F2,再建立F1 的硬链接文件F3,然后删除F1。
2009统考计算机考研试题【3】(1) 依次访问上述三个虚地址,各需多少时间?给出计算过程。
(2) 基于上述访问序列,虚地址1565H的物理地址是多少?请说明理由。
47.(9分)某公司网络拓扑图如下图所示,路由器R1通过接口E1、E2分别连接局域网1、局域网2,通过接口L0连接路由器R2,并通过路由器R2连接域名服务器与互联网。
R1的L0接口的IP地址是202.118.2.1;R2的L0接口的IP地址是202.118.2.2,L1接口的IP地址是130.11.120.1,E0接口的IP地址是202.118.3.1;域名服务器的IP地址是202.118.3.2。
将IP地址空间202.118.1.0/24划分为两个子网,分配给局域网1、局域网2,每个局域网分配的地址数不少于120个,请给出子网划分结果。
说明理由或给出必要的计算过程。
请给出R1的路由表,使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。
请采用路由聚合技术,给出R2到局域网1和局域网2的路由。
2009年计算机统考真题参考答案一. 选择题1 2 3 4 5 6 7 8 9 10B C D B C B A D A B11 12 13 14 15 16 17 18 19 20C D D C D C A A D B21 22 23 24 25 26 27 28 29 30D A D D C A C B A A31 32 33 34 35 36 37 38 39 40B A B BC AD D C A1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,该缓冲区的逻辑结构应该是(队列)栈的定义:栈是只准在表尾进行插入和删除的线性表,称为LIOFO(即后进先出表)。
允许插入和删除的一端叫栈顶,另一端叫栈底。
队列的定义:队列是允许在一端进行插入而在另一端进行删除的线性表。
允许插入的一端称为队尾,允许删除的一端称为队头。
2009年真题1.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中,CPU区分它们的依据是A.指令操作码的译码结果 B.指令和数据的寻址方式C.指令周期的不同阶段 D.指令和数据所在的存储单元2.一个C语言程序在一台32位机器上运行。
程序中定义了三个变量x,y和z,其中x和z为int型,y为short型。
当x=127,y=-9时,执行赋值语句z=x+y后,x,y和z的值分别是A.x=0000007FH,y=FFF9H,z=00000076HB.x=0000007FH,y=FFF9H,z=FFFF0076HC.x=0000007FH,y=FFF7H,z=FFFF0076HD.x=0000007FH,y=FFF7H,z=00000076H3.浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。
设浮点数的阶码和尾数均采用补码表示,且位数分别为5和7位(均含2位符号位)。
若有两个数x=27*29/32,y=25*5/8,则用浮点加法计算x+y的最终结果是A. 001111100010 B. 001110100010 C. 010********* D. 发生溢出4.某计算机的Cache共有16块,采用2路组相联映射方式(即每组2块)。
每个主存块大小为32字节,按字节编址。
主存129号单元所在主存块应装入到的Cache组号是A. 0 B. 1 C. 4 D. 65.某计算机主存容量为64KB,其中ROM区为4KB,其余为RAM区,按字节编址。
现要用2K×8位的ROM芯片和4K×4位的RAM芯片来设计该存储器,则需要上述规格的ROM芯片数和RAM芯片数分别是A.1,15 B.2,15 C.1,30 D.2,306.某机器字长16位,主存按字节编址,转移指令采用相对寻址,由两个字节组成,第一字节为操作码字段,第二字节为相对位移量字段。
假定取指令时,每取一个字节PC 自动加1。
2009-2013考研计算机基础统考试题含答案2009年统考计算机考研真题 (2)⼀.单项选择题,每⼩题2分,共80分。
(2)⼆.综合应⽤题。
共70分。
(5)2009年计算机统考真题参考答案 (8)⼀.选择题 (8)⼆.综合应⽤题 (19)2010年全国研究⽣考试计算机统考试题及答案 242009年统考计算机考研真题⼀.单项选择题,每⼩题2分,共80分。
1.为解决计算机与打印机之间速度不匹配的问题,通常设置⼀个打印数据缓冲区,主机将要输出的数据依次写⼊该缓冲区,⽽打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进⼊栈S。
若每个元素出栈后⽴即进⼊队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量⾄少是 A.1 B.2 C.3 D.43.给定⼆叉树图所⽰。
设N代表⼆叉树的根,L代表根结点的左⼦树,R代表根结点的右⼦树。
若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历⽅式是 A.LRN B.NRL C.RLN D.RNL4.下列⼆叉排序树中,满⾜平衡⼆叉树定义的是5.已知⼀棵完全⼆叉树的第6层(设根为第1层)有8个叶结点,则完全⼆叉树的结点个数最多是A.39 B.52 C.111 D.1196.将森林转换为对应的⼆叉树,若在⼆叉树中,结点u是结点v的⽗结点的⽗结点,则在原来的森林中,u 和v可能具有的关系是 I.⽗⼦关系 II.兄弟关系 III. u的⽗结点与v的⽗结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于⽆向连通图特性的叙述中,正确的是I.所有顶点的度之和为偶数 II.边数⼤于顶点个数减1 III.⾄少有⼀个顶点的度为1A.只有IB. 只有IIC.I和IID.I和III8.下列叙述中,不符合m阶B树定义要求的是A.根节点最多有m棵⼦树 B.所有叶结点都在同⼀层上C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5,8,12,19,28,20,15,22是⼩根堆(最⼩堆),插⼊关键字3,调整后得到的⼩根堆是A.3,5,12,8,28,20,15,22,19B. 3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D. 3,12,5,8,28,20,15,22,1910.若数据元素序列11,12,13,7,8,9,23,4,5是采⽤下列排序⽅法之⼀得到的第⼆趟排序后的结果,则该排序算法只能是A.起泡排序 B.插⼊排序 C.选择排序 D.⼆路归并排序码的译码结果 B.指令和数据的寻址⽅式C.指令周期的不同阶段D.指令和数据所在的存储单元12.⼀个C语⾔程序在⼀台32位机器上运⾏。
2009年计算机统考真题一.单项选择题,每小题2分,共80分。
1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。
若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是A.1 B.2 C.3 D.43.给定二叉树图所示。
设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。
若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是A.LRN B.NRL C.RLN D.RNL4.下列二叉排序树中,满足平衡二叉树定义的是A. B. C. D.5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是A.39 B.52 C.111 D.1196.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是I.父子关系 II.兄弟关系 III. u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述中,正确的是I.所有顶点的度之和为偶数 II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB. 只有IIC.I和IID.I和III8.下列叙述中,不符合m阶B树定义要求的是A.根节点最多有m棵子树 B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是A.3,5,12,8,28,20,15,22,19B. 3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D. 3,12,5,8,28,20,15,22,1910.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是A.起泡排序 B.插入排序 C.选择排序 D.二路归并排序11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中,CPU区分它们的依据是A.指令操作码的译码结果 B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元12.一个C语言程序在一台32位机器上运行。
2009年计算机统考真题一.单项选择题,每小题2分,共80分。
1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。
若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是A.1 B.2 C.3 D.43.给定二叉树图所示。
设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。
若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是A.LRN B.NRL C.RLN D.RNL4.下列二叉排序树中,满足平衡二叉树定义的是A. B. C. D.5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则完全二叉树的结点个数最多是A.39 B.52 C.111 D.1196.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是I.父子关系 II.兄弟关系 III. u的父结点与v的父结点是兄弟关系A.只有IIB.I和IIC.I和IIID.I、II和III7.下列关于无向连通图特性的叙述中,正确的是I.所有顶点的度之和为偶数 II.边数大于顶点个数减1III.至少有一个顶点的度为1A.只有IB. 只有IIC.I和IID.I和III8.下列叙述中,不符合m阶B树定义要求的是A.根节点最多有m棵子树 B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后得到的小根堆是A.3,5,12,8,28,20,15,22,19B. 3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D. 3,12,5,8,28,20,15,22,1910.若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是A.起泡排序 B.插入排序 C.选择排序 D.二路归并排序11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中,CPU区分它们的依据是A.指令操作码的译码结果 B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元12.一个C语言程序在一台32位机器上运行。
2009统考计算机考研试题【5】38.主机甲和主机乙之间建立一个TCP连接,主机甲向主机乙发送了两个连续的TCP段,分别含300字节和500字节的有效载荷,第一个段的序列号为200,主机乙正确接收到两个段后,发送给主机甲的确认序列号是(1000)。
例如,序列号等于前一个报文段的序列号与前一个报文段中数据字节的数量之和。
例如,假设源主机发送3个报文段,每个报文段有100字节的数据,且第一个报文段的序列号是1000,那么接收到第一个报文段后,目的主机返回含确认号1100的报头。
接收到第二个报文段(其序号为1100)后,目的主机返回确认号1200。
接收到第三个报文段后,目的主机返回确认号1300。
39.确定拥塞窗口的大小的过程:在刚建立连接时,将拥塞窗口的大小初始化为该连接所需的最大连接数据段的长度值,并发送一个最大长度的数据段(当然必须是接收窗口允许的)。
如果在定时器超时前得到确认,将拥塞窗口的大小增加一个数据段的字节数,并发送两个数据段,如果每个数据段在定时器超时前都得到确认,就再在原基础上增加一倍,即为4个数据段的大小,如此反复,每次都在前一次的基础上加倍。
当定时器超时或达到发送窗口设定值,停止拥塞窗口尺寸的增加。
这种反复称为慢速启动,所有的TCP协议都支持这种方法。
一个TCP连接总是以1KB的最大段发送TCP段,发送方有足够多的数据要发送。
当拥塞窗口为16KB时发生了超时,如果接下来的4个RTT(往返时间)时间内的TCP段的传输都是成功的,那么当第4个RTT 时间内发送的所有TCP段都得到肯定应答时,拥塞窗口大小是(9KB)。
40.FTP客户和服务器间传递FTP时,使用的连接是(建立在TCP 之上的控制连接)。
二. 综合应用题41.该方法求得的路径不一定是最短路径。
例如,对于下图所示的带权图,如果按照题中的原则,从A到C的最短路径为A→B→C,事实上其最短路径为A→D→C。
42. (1)算法基本思想如下:从头至尾遍历单链表,并用指针P指向当前节点的前K个节点。
5.解析:完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点,而最后一层之上是个满二叉树,并且只有最后两层有叶结点。
第6层有叶结点则完全二叉树的高度可能为6或7,显然树高为7时结点更多。
若第6层上有8个叶结点,则前六层为满二叉树,而第7层缺失了8x2 = 16个叶结点,故完全二叉树的结点个数最多为(27-1)-16 = 111个结点。
6.解析:森林与二叉树的转换规则为“左孩子右兄弟”。
在最后生成的二叉树中,父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。
情形I:若结点v是结点u的第二个孩子结点,在转换时,结点v就变成结点u第一个孩子的右孩子,符合要求。
情形II:结点u 和v 是兄弟结点的关系,但二者之中还有一个兄弟结点k,则转换后,结点v就变为结点K的右孩子,而结点k则是结点u的右孩子,符合要求。
喜``。
嘉``II情形III:若结点u的父结点与v的父结点是兄弟关系,则转换后,结点u和v分别在两者最左父结点的两棵子树中,不可能出现在同一条路径中。
分图III【逆向法】由题意可知u 是v 的父结点的父结点,如下图所示有4种情况:����根据树与二叉树的转换规则,将这4种情况转换成树种结点的关系。
(1)在原来的树中u 是v的父结点的父结点;(2)在树中u是v的父结点;(3)在树中u是v的父结点的兄弟;(4)在树中u与v是兄弟关系。
由此可知I 和II正确。
7.解析:每条边都连接了两个结点,在计算顶点的度之和时每条边都被计算了两次(出度和入度),故所有顶点的度之和为边数的两倍,I正确。
n个顶点、n-l条边可以构成无向连通图,比如树,II错误。
顶点数为N (N�l)的无向完全图中不存在度为1的顶点,III错误。
8.解析:选项A、B和C都是B-树的特点,而选项D则是B+树的特点。
注意区别B-树和B+树各自的特点。
9.解析:根据关键字序列得到的小顶堆的二叉树形式如下图所示。
19 15 15 1522 22 22(I)插入关键字3时,先将其放在小顶堆的末端,如图(2)所示。
2009年计算机统考真题(完整版)一.单项选择题,每小题 2 分,共80 分。
1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是 A.栈 B.队列 C.树 D.图2.设栈S 和队列Q 的初始状态均为空,元素abcdefg 依次进入栈S。
若每个元素出栈后立即进入队列Q,且7 个元素出队的顺序是bdcfeag,则栈S 的容量至少是A.1 B.2 C.3 D.43.给定二叉树图所示。
设N 代表二叉树的根,L 代表根结点的左子树,R 代表根结点的右子树。
4.若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是A.LRN B.NRL C.RLN D.RNL5.下列二叉排序树中,满足平衡二叉树定义的是6.已知一棵完全二叉树的第 6 层(设根为第 1 层)有8 个叶结点,则完全二叉树的结点个数最多是A.39 B.52 C.111 D.1197.将森林转换为对应的二叉树,若在二叉树中,结点u 是结点v 的父结点的父结点,则在原来1的森林中,u 和v 可能具有的关系是I.父子关系II.兄弟关系III. u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III8.下列关于无向连通图特性的叙述中,正确的是I.所有顶点的度之和为偶数II.边数大于顶点个数减 1 III. 至少有一个顶点的度为 1A.只有IB. 只有IIC.I 和IID.I 和III9.下列叙述中,不符合m 阶B 树定义要求的是A.根节点最多有m 棵子树 B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接10.已知关键序列5,8,12,19,28,20,15,22 是小根堆(最小堆),插入关键字3,调整后得到的小根堆是A. 3,5,12,8,28,20,15,22,19B. 3,5,12,19,20,15,22,8,28C. 3,8,12,5,20,15,22,28,19D. 3,12,5,8,28,20,15,22,1911.若数据元素序列11,12,13,7,8,9,23,4,5 是采用下列排序方法之一得到的第二趟排序后的结果,则该排序算法只能是A.起泡排序 B.插入排序 C.选择排序 D.二路归并排序12.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中,CPU 区分它们的依据是A.指令操作码的译码结果 B.指令和数据的寻址方式C.指令周期的不同阶段D.指令和数据所在的存储单元13.一个 C 语言程序在一台32 位机器上运行。
文章标题:深入探讨2009年408算法题的暴力解法1. 引言2009年408算法题是计算机科学领域的一个重要问题,涉及到对一系列数字的组合与计算。
本文将深入探讨这个问题,并着重介绍其暴力解法。
2. 2009年408算法题概述2009年408算法题是一个经典的组合与计算问题,要求对给定的一组数字进行加减乘除运算,以获得特定的结果。
这个问题涉及到搜索算法、组合数学以及动态规划等多个领域的知识。
3. 暴力解法的基本思路暴力解法是一种最简单、直观的解题方法,即对所有可能的情况进行枚举和计算,然后找出符合条件的结果。
在解决2009年408算法题时,暴力解法通常是从最基本的情况出发,逐步进行组合与运算,直到找到符合条件的结果。
4. 从简到繁的案例分析为了更好地理解暴力解法的思路,我们可以从一个简单的案例出发,逐步增加数字的个数与难度,进行分析与求解。
以此类推,直到掌握了解题的一般方法。
5. 暴力解法的优缺点暴力解法的优点在于思路直接,容易理解与实现。
然而,其缺点也是显而易见的:计算量大,效率低下。
尤其是在遇到规模较大的问题时,暴力解法往往无法满足实际需求。
6. 总结与回顾通过本文的深入探讨与案例分析,我们对2009年408算法题的暴力解法有了更深刻的理解与认识。
也意识到了暴力解法在实际应用中的局限性与不足之处。
在实际工作中,我们需要结合其他更高效的算法与思路,来解决类似的组合与计算问题。
7. 个人观点与理解作为一个计算机科学领域的从业者,我认为要理解和掌握一种解题方法,需要深入思考和实践。
暴力解法虽然简单,但也是我们在学习和探索算法的过程中必不可少的一步。
只有通过对基本方法的理解,我们才能更好地掌握更复杂、更高效的算法思想。
以上是对2009年408算法题暴力解法的深入探讨与分析,希望可以帮助您更深入地理解这一经典的计算机算法问题。
2009年408算法题是一个经典的组合与计算问题,要求对给定的一组数字进行加减乘除运算,以获得特定的结果。
2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题一、单项选择题:1~40小题,每小题2分,共80分。
下列每题给出的四个选项中。
只有一个选项是最符合题目要求的。
1.为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是()。
A.栈B.队列C.树D.图2.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈S。
若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是()。
A.1B.2C.3D.43.给定二叉树如下图所示。
设N代表二叉树的根,L代表根结点的左子树,R代表根结点的右子树。
若遍历后的结点序列为3,1,7,5,6,2,4,则其遍历方式是()。
A.LRNB.NRLC.RLND.RNL4.下列二叉排序树中,满足平衡二叉树定义的是()。
5.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点,则该完全二叉树的结点个数最多是()。
A.39B.52C.111D.1196.将森林转换为对应的二叉树,若在二叉树中,结点u是结点v的父结点的父结点,则在原来的森林中,u和v可能具有的关系是()。
Ⅰ.父子关系Ⅱ.兄弟关系Ⅲ.u的父结点与v的父结点是兄弟关系A.只有ⅠB.Ⅰ和ⅡC.Ⅰ和ⅢD.Ⅰ、Ⅱ和Ⅲ7.下列关于无向连通图特性的叙述中,正确的是()。
Ⅰ.所有的顶点的度之和为偶数Ⅱ.边数大于顶点个数减1Ⅲ.至少有一个顶点的度为1A.只有ⅠB.只有ⅡC.Ⅰ和ⅡD.Ⅰ和Ⅲ8.下列叙述中,不符合m阶B树定义要求的是()。
A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接9.已知关键字序列5,8,12,19,28,20,15,22是小根堆(最小堆),插入关键字3,调整后的小根堆是()。
2009年全国研究生统一入学考试“操作系统”试卷浅析摘要:本文是作者在评阅“操作系统”试卷后,进行的初步的分析和总结。
论文重点对计算机学科专业基础综合科目的第45题各种答案进行了评析。
最后针对某省考生的计算机学科专业基础综合科目得分情况进行了分析。
关键词:计算机学科专业基础综合;操作系统;考试教育部决定,从2009年起对全国硕士研究生统一入学考试计算机科学与技术学科的初试科目进行调整及命题形式进行改革。
计算机科学与技术学科的初试科目调整后为4门,即政治理论、外国语、数学一和计算机学科专业基础综合。
计算机学科专业基础综合的考试内容包括:数据结构、计算机组成原理、操作系统和计算机网络,重点考查考生掌握相关基础知识、基本理论和分析问题解决问题的能力。
根据2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲的规定,试卷的内容结构为:数据结构45分,占30%;计算机组成原理45分,占30%;操作系统35分,约占23%;计算机网络25分,约占17%。
试卷题型结构为:单项选择题80分(40小题,每小题2分),综合应用题70分。
计算机学科专业基础综合总分为150分。
从2009年的试题看,试卷题目分布如下:(1) 数据结构范围内的选择题10题(第1~10题),每题2分,共20分;综合应用题2题(第41、42题),共25分;总计是45分。
(2) 计算机组成原理范围内的选择题12题(第11~22题),每题2分,共24分;综合应用题2题(第43、44题),共21分;总计是45分。
(3) 操作系统范围内的选择题10题(第23~32题),每题2分,共20分;综合应用题2题(第45、46题),第45题7分、第46题8分,共15分;总计是35分。
(4) 计算机网络范围内的选择题8题(第33~40题),每题2分,共16分;综合应用题1题(第47题),共9分;总计是25分。
22009年“操作系统”考题分析2009年计算机学科专业基础综合科目考试操作系统第23-32题是选择题,第45、46题是综合应用题。
2009年考研计算机专业(基础综合)真题试卷(总分:108.00,做题时间:90分钟)一、单项选择题(总题数:41,分数:82.00)1.单项选择题1-40小题。
下列每题给出的四个选项中,只有一个选项是最符合题目要求的。
(分数:2.00)__________________________________________________________________________________________ 解析:2.为解决计算机主机与打印机之间速度不匹配问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。
该缓冲区的逻辑结构应该是____。
(分数:2.00)A.栈B.队列√C.树D.图解析:解析:考查栈和队列的特点及应用。
C和D直接排除,缓冲区的特点需要先进先出,若用栈,先进入缓冲区的数据则要排队到最后才能打印,不符题意,故选B。
3.设栈S和队列Q的初始状态均为空,元素a,b,c,d,e,f,g依次进入栈s。
若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b,d,c,f,e,a,g,则栈S的容量至少是____。
(分数:2.00)A.1B.2C.3 √D.4解析:解析:考查栈的最大递归深度。
时刻注意栈的特点是先进后出。
出入栈的详细过程见表A-3栈内的最大深度为3,故栈S的容量至少是3。
4.给定二叉树如图A-1所示。
设N代表二叉树的根,L代表根结点的左了树,R代表根结点的右子树。
若遍历后的结点序列是3,1,7,5,6,2,4,则其遍历方式是____(分数:2.00)A.LRNB.NRLC.RLND.RNL √解析:解析:考查二叉树的特殊遍历。
分析遍历后的结点序列,可以看出根结点是在中间被访问的,而右子树结点在左子树之前,得遍历的方法是RNL。
本题考查的遍历方法并不是二叉树的三种基本遍历方法,对于考生而言,重要的是要掌握遍历的思想。
5.下列二叉排序树中,满足平衡二叉树定义的是____。
2009考研计算机统考专业大纲解析主持人:大家好,2009是计算机专业实行全国统考的第一年,我们邀请到海天跨考专业课辅导中心张老师来给大家讲讲2009考研计算机大纲,张老师好!张文平:主持人好,大家好!主持人:2009年计算机专业考研主要在哪些方面做了改革?张文平:计算机专业考研在2009年做了非常重大的改革,首先是采用了全国统考的方式来实行统一命题;其次,考试的范围(针对各校初试而言)加大至四门科目,即数据结构、计算机组成原理、操作系统、计算机网络四个部分组成;第三,专业课复试的比例和权重将会有所增加。
因为到目前为止,绝大部分公布了招生简章的学校都表示将参加计算机统考,但是各个学校的计算机专业的侧重点和研究方向还是差异非常大的,这就导致了将会有比较多的学校会通过复试的方式来选拔自己所需的人才。
主持人:2009计算机大纲大概的范围是怎么分布的?张文平:各个科目之间所占分数如下:数据结构和计算机组成原理各占45分,操作系统占了35分,计算机网络占了25分。
总的来看,计算机统考后加大了考试的范围和考试的知识面,但总体的考试的重难点还是传统的考试科目占据优势,比如数据结构和计算机组成原理(一般学校的统考前的必考科目)占据了90分,所以说重难点还是在这两个科目上面,其他的像操作系统和计算机网络占据分值较少,并且相对来讲比数据结构和计算机原理简单,所以说复习的重难点还是在前两个科目上。
比如,清华大学和北京航空航天大学这几年的初试科目均为数据结构、计算机组成原理和操作系统,北京邮电大学为数据结构和计算机组成原理,北京大学为数据结构和操作系统。
主持人:2009计算机统考的题型是怎么分布的?张文平:统考后计算机只有两种题型:单项选择题和综合应用题,选择题占了80分,共四十道题,从这点上可以很明显的看出来,考查的知识点将会相对的比较全面,此外综合应用题占了70分,针对操作系统和数据结构的综合应用题都相对简单些,所以这块的重难点还是在数据结构和计算机原理上面。
一般来讲,专业课统考第一次考试都往往比较简单,主要是方便广大考生备考,然后接下来的考试难道慢慢加大。
这个从往年的那些统考科目里面得到了充分的体现,所以同学们完全没有必要担心考试科目和考试范围的加大,只要用心复习,按照大纲的要求把具体的考点掌握全,掌握牢固,拿高分还是非常有希望的。
我对比了下统考后大纲的题型和往年各大高校的考试题型,像北京大学主要有填空题、简答题和算法分析题等。
清华、北航主要有简答题、填空题、判断题和运算题等。
所以,题型还是变化蛮大的,再者,从各科公布的考试知识点来讲,总体上并不是特别难,这给备考的同学们带来了很大的信心。
主持人:大纲公布后大家用什么参考书目比较合适?张文平:由于统考课程分为数据结构、计算机组成原理、操作系统和计算机网络四个部分,因此,建议大家每个部分都找相应的专业课教材进行复习。
数据结构大家可以选择清华大学出版社的《数据结构(第二版)》(严蔚敏主编)。
这本书有多种语言的版本,建议选择C语言的版本,在复习的过程中,还可以配以相应的习题集。
操作系统方面建议大家选择西安电子科技大学出版社的《计算机操作系统(第三版)》(汤小丹、汤子瀛等主编),该教材适合于初学者,写得比较简单。
同时,也配以《计算机操作系统学习指导与题解》(西安电子科技大学出版社,汤子瀛等主编),效果会比较好。
计算机组成原理的复习,建议选择高等教育出版社的《计算机组成原理(第2版)(唐朔飞主编),该书写得比较好,曾经获得优秀教材称号,同时也是国家高等教育“十一五”教材。
在学习的过程中,同样,配以《计算机组成原理:学习指导与习题解答》(唐朔飞,高等教育出版社)。
在计算机网络方面,推荐大家使用电子工业出版社的《计算机网络(第5版)》(谢希仁主编)。
另外,高等教育出版社的《数据通信与计算机网络(第2版)》(高传善、毛迪林、曹袖主编)也可以用来自学。
对于教材的学习,重点在于对基本概念和基本理论的理解,特别是计算机组成原理和计算机网络,概念性的知识居多,需要我们有充分的耐心,认真对待。
而对于数据结构、操作系统,则除了掌握基本原理以外,还需要掌握理论知识的实际应用。
这一点在综合应用题中将会体现的非常明显,一定要引起大家的足够重视。
主持人:如何参照大纲进行复习?张文平:严格按照考试大纲复习。
大纲出来后,一定要以考试大纲为准绳,科学安排如前分析,统一考试试卷最鲜明的特点就是严格按照考试大纲命题,无论命题思路、题型、比例乃至考查方式,无一不体现了考试大纲的要求。
因此,复习最根本的要求就以大纲为指导确定复习内容和复习强度,全面复习与重点复习相结合。
保证对知识点都能掌握,考试的重难点都能够把握。
暑假参加计算机统考的同学专业课应该开始复习了。
前期可以多看几遍书,不停的看,反复看。
这样慢慢就会品出不同的滋味或者说找到自己复习知识时的盲点,仔细把课本从头到位看四五遍甚至更多这是很必要的。
关于相应的复习规划这个届时各大网站都将有相关的复习攻略,这里就不多讲了。
主持人:是不是所有的学校都参加统考?张文平:从目前的情况来看,绝大部分的学校都将参加计算机的统考。
目标公布的参加统考的学校中,北大、清华、浙大、北航、北邮、上交大、西交大等都赫然在列,有这些学校作为带头,相信参加统考的学校的规模一定不少。
所以同学们也可以放心的准备了,即使目前学校还没有定下来也没有关系,一般的学校都会参加统考。
具体的择校咨询咱们可以在下期的节目中再做深入的交流。
张文平:谢谢大家,谢谢主持人。
今天我们来解析一下计算统考大纲计算机组成原理部分及其相关知识点。
计算机组成原理占了45分,和数据结构部分同一个比重,以往各个学校的考研大纲中有些没有计算机组成原理,即使有了很少有和数据结构所占比重相同的情况,当然了个别学校比如国防科技大学专业课考试只有一门计算机组成原理150分。
笔者认为这主要是因为计算机全国统考的原因,统考不会针对某个学校的具体情况,而是从宏观上考虑问题,数据结构是计算机软件类的必修基础课程,计算机组成原理是计算机硬件类的必修基础课程,在统考第一年把它们放到同一比重还是比较科学的。
统考大纲把计组的考查目标定位为理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式,具有完整的计算机系统的整机概念;理解计算机系统层次化结构概念,熟悉硬件与软件之间的界面,掌握指令集体系结构的基本知识和基本实现方法;能够运用计算机组成的基本原理和基本方法,对有关计算机硬件系统中的理论和实际问题进行计算、分析,并能对一些基本部件进行简单设计。
计算机软件基础总体上来说是一门识记和理解类的科目,即便是考查设计应用类的题目也不会很难,因此得高分的关键对相关概念和原理的充分识记和理解。
鉴于考试科目比较多,推荐大家用唐朔飞老师的书作为辅导教材,这本书讲的比较透彻详细,而且这本书有本配套习题集,只要把书认真看两遍,把习题集上的东西搞懂,考试是没有问题的。
下面我们来解析一下知识点。
计算机系统概述这一章里面需要识记和了解的内容比较多,出大题的可能性几乎为零,大家要注意的两个知识但就是计算机的工作过程和计算机组成原理与计算机系统结构的区别。
一些计算机常用的评价参数大家一定要弄明白具体含义,不要依靠自己主观理解,这些概念在后续章节经常用到,大家要知道的不能仅限于大纲上罗列出来的名词。
数据的表示和运算可以考查的知识点比较多。
计算机中常用的数据表示方法有哪几种,常用的编码方法有哪几种,常用的检验码有哪几种,他们都有一些什么样的区别和联系,要熟练掌握各种方法之间转换,要做到拿到题就能转换,不经过大脑思考的地步。
另外要注意的一个问题就是新加的字符和字符串这个知识点,这个考点在数据结构中给剔除了,把它放在了计算机组成原理里面,实际上是降低了它的重要性,比如令人头痛的KMP算法是不会考了,但是大家要仔细体会这里面的不同,注意考查角度的不同。
数据的运算分为定点和浮点运算,这个地方大家一定要重点掌握,这历来都是经常出大题的一个地方,尤其是定点数运算。
最后大家要关注的就是数据运算的部件---ALU,大家要掌握是ALU的功能和结构,串行加法器和并行加法器的原理和区别。
存储器的层次结构。
这一章中我们建立存储器体系的“CACHE-内存-外存”三层结构,要掌握存储器的分类以及各类存储器的基本工作原理和主存储器(内存)与CPU的连接和数据交换、双口RAM和多模块存储器。
关于外存的知识点主要放在了输入输出系统一章考查。
这一章中两个必须要掌握的地方就是高速缓冲存储器(Cache)和虚拟存储器。
其实存储器这一章在复习的时候可以结合操作系统的存储器管理来加深理解。
要明白引入CACHE和虚拟的存储器的目的,他们的工作原理,实现方法。
能说出几种主存容量扩张方法、访问Cache 的过程,计算硬盘的容量和访问时间。
指令系统。
在这一章中需要掌握的是指令的格式和指令的寻址,其中指令寻址是考试容易考查的重点。
要知道指令的基本格式结构,定长操作码的格式和扩展操作码的格式结构,熟悉常见指令的意义。
熟悉常见的寻址方式和利用它们寻找有效地址的步骤。
掌握RISC和CISC的定义和区别中央处理器。
中央处理器就是我们常说的CPU,它是由ALU和CU(控制单元)两大部件构成。
这一章里面我们要熟悉CPU的功能和基本结构,数据通路的功能和结构,准确理解指令的执行过程。
熟悉控制单元的设计和实现,掌握组合逻辑和时序逻辑的特点和区别,掌握指令执行周期的概念和指令流水线的分析。
总线。
总线就是一组进行互连和传输信息(指令、数据和地址)的信号线,我们要识记总线的基本概念,总线的分类,以及总线的组成和性能指标。
这一章要掌握总线仲裁方法(包括集中仲裁方式和分布仲裁方式)和总线操作和定时(包括同步定时方式和异步定时方式)。
大家要对总线的标准有所了解,总线的标准可以分为正式标准和工业标准两种,总线标准主要规定总线的机械结构规范、功能结构规范和电气规范,当然相应的规范都有其对应的性能参数。
这一章不是考试的重点,比较热的地方就是总线的仲裁方式和定时方式。
输入输出系统。
这一章,我们要掌握I/O系统的基本概念。
外部设备这一部分不是考试的热点,但是大家要识记各种外部设备,其中包括输入设备(键盘、鼠标、扫描仪等)、输出设备(显示器、打印机等)、外存储器(硬盘存储器、磁盘阵列、光盘存储器等)。
要理解这些设备的基本工作原理和常见的性能指标。
例如显示器的分辨率、磁盘的读写时间等,特别是磁盘的有关读写过程(寻道时间、等待时间等),是一定要掌握的。
我们要掌握I/O控制器的功能和基本结构、I/O端口及其编址方式。
在I/O方式中,主要掌握程序查询方式、程序中断方式、DMA方式、通道方式的基本概念、工作原理和过程,以及这些方式之间的区别、各自的优点和缺点、应用场合。