2011年三峡大学硕士微机复试真题

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

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

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

）1.设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是。

x=2；while(x<n/2)x=2*x；A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)2.元素a，b，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是。

A．3 B．4 C．5 D．63.已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front 和rear 分别指向队头元素和队尾元素。

若初始时队列为空，且要求第 1 个进入队列的元素存储在A[0]处，则初始时front和rear 的值分别是。

A．0，0 B．0，n-1 C．n-1，0 D．n-1，n-1 4．若一棵完全二叉树有768 个结点，则该二叉树中叶结点的个数是A．257 B．258 C．384 D．385 5．若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4 和4，3，2，1，则该二叉树的中序遍历序列不会是。

A．1，2，3，4 B．2，3，4，1 C．3，2，4，1 D．4，3，2，1 6．已知一棵有2011 个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是。

A．115 B．116 C．1895 D．18967.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是。

A．95，22，91，24，94，71 B．92，20，91，34，88，35 C．21，89，77，29，36，38 D．12，25，71，68，33，348.下列关于图的叙述中，正确的是。

Ⅰ．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路A．仅ⅡB．仅Ⅰ、ⅡC．仅ⅢD．仅Ⅰ、Ⅲ 9．为提高散列（Hash）表的查找效率，可以采取的正确措施是。

2011年计算机考研统考真题【1】设n是描述问题规模的非负整数，下面的程序片段的时间复杂度是（）。

x=2;while(x<n/2)x=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)【解析】A。

容易看出，程序基本操作为x=2*x;基本操作执行的次数即为程序的时间复杂度，因此可设基本操作执行k次结束，则有：执行第1次：x=2×2=21+1=4；执行第2次：x=4×2=22+1=8；执行第3次：x=8×2=23+1=16；……执行第k次：x=2k+1。

由循环结束条件知：x<n/2，即2k+1<n/2时结束，即k<log2n-2，即k=log2n+C（为方便说明，其中C为起修正作用的常数）。

综上得：时间复杂度为O(log2n)。

【2】元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。

A.3B.4C.5D.6【解析】B。

若要保证出栈序列以d开头，则前三个元素必连续进栈，中间不能出现出栈的情况，然后d出栈，此时栈内元素由底到顶为，a,b,c，栈外元素为e，出栈序列中元素为d。

因为a,b,c三个元素在栈内的顺序已定，由栈的先进后出原则，其在出栈序列中的相对位置必为…c…b…a…；加上d的位置已定，所以出栈待定序列必为d…c…b…a…。

显然在栈外的e可以在任何时候出栈入栈，即可以出现在以上待定序列中任何一个省略号的位置，即出栈序列可为：1:d,e,c,b,a；2:d,c,e,b,a；3:d,c,b,e,a；4:d,c,b,a,e。

【3】已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。

一、单项选择题1-40小题，每小题2分，共80分。

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

1 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是____。

x：2：while(x<n／2)x=2*x：（A）O(log2n)（B）O(n)（C）O(nlog2n)（D）O(n2)2 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是____。

（A）3（B）4（C）5（D）63 已知循环队列存储在一维数组A[0…n一1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是____。

（A）0，0（B）0，n一1（C）n—1，0（D）n一1，n—14 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（A）257（B）258（C）384（D）3855 若一棵二叉树的前序遍历序列和后序遍历序列分别为1，2，3，4和4，3，2，1，则该二又树的中序遍历序列不会是____。

（A）1，2，3，4（B）2，3，4，1（C）3，2，4，1（D）4，3，2，16 已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是____。

（A）115（B）116（C）1895（D）18967 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是____。

（A）95，22，91，24，94，71（B）92，20，91，34，88，35（C）2l，89，77，29，36，38（D）12，25，71，68，33，348 下列关于图的叙述中，正确的是____。

I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（A）仅Ⅱ（B）仅I、Ⅱ（C）仅Ⅲ（D）仅I、Ⅲ9 为提高散列(Hash)表的查找效率，可以采取的正确措施是____。

南京航空航天大学2011年硕士研究生入学复试试题考试科目：微机原理及应用说明：答案必须填在答题纸上，写在试卷上无效一、简答题（简要回答，不必展开）（60分）1、将十进制数 315.6875 分别转化成二进制和十六进制数。

23、堆栈的作用是什么？它的操作规则是什么？4、什么是部分地址译码？什么是全地址译码？5、什么是“量化误差”？如何减少A/D转换器的“量化误差”？6、简述中断响应的一般过程。

7、什么是BCD码？进行BCD码运算时为何要进行BCD码调整？8、冯·诺伊曼计算机的设计思想是什么？9、简述串行通信与并行通信的特点。

10、（1）针对8086/8088系统操作数的八种寻址方式，分别写出一例句（指令语句）。

（选8086/8088机型的考生回答该题）（2）针对MCS-51系统操作数的七种寻址方式，分别写出一例句（指令语句）。

（选MCS-51机型的考生回答该题）11、（1）微机系统中，输入/输出接口的编址方式一般有哪几种？各有何特点？（选8086/8088机型的考生回答该题）（2）单片机与外部设备进行数据交换有哪几种工作方式？各有何特点？（选MCS-51机型的考生回答该题）12、（1）简述宏指令和子程序的异同？编程时如何选用？（选8086/8088机型的考生回答该题）（2）MCS-51单片机内部定时器/计数器有四种工作方式，试简述其中的两种方式。

（选MCS-51机型的考生回答该题）二、分析题（24分）三、编程题（26分）1、假设在8086/8088内存中（或8051系统的某外部存储芯片中）有20个连续存储的单字节无符号数，首地址为BUFFER。

试编程找出这20个数中的最大和最小数，分别存入地址是MAX和MIN的单元内。

（15分）2、某八位寄存器（BL或R0）中存放着两个压缩BCD码，试编程将其转换为ASCII码，结果放入其它寄存器中。

（11分）四、应用题（40分）1、分析下列电路原理图，分别指出两片静态RAM 6116（2K*8B）中存储单元的基本地址分布范围。

南京理工大学2011年硕士学位研究生入学考试复试试题考试科目：控制理论基础考试时间：4月10日19:30—21:30一．（15分）已知某状态方程x(t)=[300130001--] x(t)+[011] y(t)=[110]x(t)1).求系统的可控性，可观性。

（不可控，不可观）2).求系统的传递函数。

（31+s ） 3).{-2,-2，-2}和{-1，-2，-3}哪个可以通过状态反馈实现，无需计算状态反馈。

二．（10分）某闭环离散采样系统如图所示，其中ZOH 为零阶持器，Gp(S)为连续对象的传递函数，已知采样周期T=1，Gp(S)=11).试确定闭环传递函数。

（264.0+z ） 2).当r （t ）=1（t ）时，试确定系统的终值。

（0.5）（参考2010年第8题）三．（10分）非线性系统结构如图所示，N(A)=15++A A ,G(S)=)2)(1(++s s s k 1).求系统稳定，不稳定，临界稳定时K 的取值范围。

(0<K<1.2，稳定1.2<K<6，临界稳定6<K ，不稳定)2).求系统临界稳定时的振幅和角频率。

（A=kk --615，w =√2） 四．（15分）此题为实验设计题，题目较长。

大概是设计实验求出一阶惯性系统的参数 G(S)=12+S T TI 五．（20分）微机填空题，每空一分。

（参考教材第四，第六，第九章）六．（15分）微机存储芯片扩展从1800h 开始连续分配4KB ROM(低地址),4KB RAM(高地址)）所用芯片为2K*8 EPROM2716，1K*4 RAM2114。

完成硬件设计，并写出芯片地址范围。

（参考教材100页）七．（15分）一个由0809和8259和8088组成的系统。

（图与教材235页图9-22类似）完成从0809INT1通道连续采集20个数据程序的设计。

写出8259初始化程序，完成主程序的设计（包括中断向量初始化，主程序和中断服务子程序）。

2011 年考研计算机学科专业基础综合一．选择题1．设n是描述问题规模的非负整数，下面程序片段的时间复杂度是x = 2;while ( x < n/2 )x = 2*x;A．O(log2n) B．O(n) C．O(n log2n) D．O(n2)2．元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A．3 B．4 C．5 D．63．已知循环队列存储在一维数组A[0..n-1] 中，且队列非空时front和rear 分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear 的值分别是A．0, 0 B．0, n-1 C．n-1, 0 D．n-1, n-14．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A．257 B．258 C．384 D．3855．若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不．会是A．1, 2, 3, 4 B．2, 3, 4, 1 C．3, 2, 4, 1 D．4, 3, 2, 16．已知一棵有2011 个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是A．115 B．116 C．1895 D．18967．对于下列关键字序列，不．可能构成某二叉排序树中一条查找路径的序列是A．95, 22, 91, 24, 94, 71 B．92, 20, 91, 34, 88, 35C．21, 89, 77, 29, 36, 38 D．12, 25, 71, 68, 33, 348．下列关于图的叙述中，正确的是I．回路是简单路径II．存储稀疏图，用邻接矩阵比邻接表更省空间III．若有向图中存在拓扑序列，则该图不存在回路A．仅II B．仅I、II C．仅III D．仅I、III9．为提高散列（Hash）表的查找效率，可以采取的正确措施是I．增大装填（载）因子II．设计冲突（碰撞）少的散列函数III．处理冲突（碰撞）时避免产生聚集（堆积）现象您所下载的资料来源于 考研资料下载中心获取更多考研资料，请访问A．仅I B．仅II C．仅I、II D．仅II、III10．为实现快速排序算法，待排序序列宜采用的存储方式是A．顺序存储B．散列存储C．链式存储D．索引存储11．已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是A．1 B．2 C．4 D．512．下列选项中，描述浮点数操作速度指标的是A．MIPS B．CPI C．IPC D．MFLOPS13．float型数据通常用IEEE 754单精度浮点数格式表示。

2011年秋季工学硕士研究生学位课程（数值分析）真题试卷B(总分28,考试时间90分钟)1. 填空题填空题请完成下列各题，在各题的空处填入恰当的答案。

1. 设｜x｜>>1，计算时，为了提高精度应把它变形为______2. 求积分∫abf（x）dx的两点Gauss公式为______3. 设A=则‖A‖∞=______，‖A‖2=______．4. 给定f(x)=x4，以0为三重节点，2为二重节点的f(x)的Hermite插值多项式为______．5. 己知差分格式当步长比r≤______时，该差分格式在L∞范数下是稳定的．2. 计算题1. 给定方程lnx-x2+4=0，分析该方程存在几个根，并用迭代法求此方程的最大根，精确至3位有效数字．2. 用列主元Gauss消去法求下面线性方程组的解：3. 综合题1. 设A=是非奇异矩阵，试用α，β表示求解方程组．Ax=b的Jacobi迭代法与Gauss-Seidel 迭代法收敛的充分必要条件．2. 设x0，x1，x2为互异节点，a，b，m为已知实数．试确定x0，x1，x2的关系，使满足如下三个条件p(x0)=a，p"(x1)=m，p(x2)=b的二次多项式p(x)存在且唯一，并求出这个插值多项式p(x)．3. 求y=｜x｜在[-1，1]上形如c0+c1x2的最佳平方逼近多项式．4. 已知函数f(x)∈C3[0，3]，试确定参数A，B，C，使下面的求积公式≈Af(0)+Bf(1)+Cf(2)代数精度尽可能高，并给出此时求积公式的截断误差表达式．5. 给定常微分方程初值问题取正整数n，并记h=a／n，xi=a+ih，0≤i≤n．证明：用梯形公式求解该初值问题所得的数值解为且当h→0时，yn收敛于y(a)．6. 已知椭圆方程边值问题其中Ω={0＜x＜3，0＜y＜3)．试用五点差分格式求u(1，1)，u(1，2)，u(2，1)，u(2，2)的近似值．。