华南理工考研计算机历年真题.doc

华南理工大学2004年攻读硕士学位研究生入学考试试卷（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回）科目名称：计算机专业综合一(组成原理、数据结构、操作系统)适用专业：计算机系统结构、计算机应用技术、软件工程、计算机应用技术I. 计算机组成原理试题 （50分）一填空题（共10分）1计算机的工作过程主要是周而复始地A、B和C的过程。2在浮点运算中，当运算结果阶码大于所能表示的A时称为溢出，若阶码用双符号S0S0的移码表示，则当S0S0 =B时为溢出。3双端口存储器和多模块交叉存储器属于 A 存储器结构；前者采用 B 并行技术，后者采用 C 并行技术。4在微程序控制器中，一般采用较简单的 A 、 B 二级时序体制。5CPU响应中断时保护两个关键的硬件状态是 A 和 B 。2 选择题（共6分）1设浮点数的阶为8位（其中1位阶符），用移码表示，尾数为24位（其中1位数符），用原码表示。则它所能表示的最大规格化正数是（）。 A(27-1)(1-2-23 ) B (1-2-23 ) C (1-2-23 ) D (1-2-22 )2下列说法正确的是（）。A. 微程序控制方式和硬布线方式相比较，前者可以使指令的执行速度更快B. 若采用微程序控制方式，则可用PC取代PCC. 控制存储器可以用ROM实现D. 指令周期也称为CPU周期3下列说法正确的是（ ）。A. 程序中断过程是由硬件和中断服务程序共同完成的B. 每条指令的执行过程中，每个总线周期要检查一次有无中断请求C. 检测有无DMA请求，一般安排在一条指令执行过程的末尾D. 中断服务程序的最后指令是无条件转移指令三完成下列各题（共36分）1设A补an-1an-2a1 a0，式中an-1为补码符号位，求证真值：（8分）2假设主存只有a，b，c三个页框，组成a进c出的FIFO队列进程，访问页面的序列是0，1，3，4，3，2，0，2，1，3，2号。若采用：FIFO算法；FIFO+LRU算法。用列表法求以上两种策略的命中率。 （12分）3某CPU的部分数据通路如图1所示。WA和WB是分别写入寄存器A和B的控制信号。WA和WB能否包含在一条微指令中？为什么？如要将WA和WB包含在一条微指令中，要采取什么措施？（10分）4在图2中，当CPU对设备B的中断请求进行服务时，设备A能否提出中断请求？为什么？如果设备B一提出中断请求总能立即得到服务，问怎样调整才能满足此要求？ （10分）II 数据结构试题 （50分） 填空题?（每小题2分，共16分）1 若用两个堆栈实现队列操作，在队中插入或删除一个元素的时间复杂性是_。2 在向量存储的二叉树中，根结点编号为1，则编号为i和j的两个结点处在同一层的条件是 _。3 n个顶点的无向图G每个顶点的度最大可能是_。4 高度为5的3阶B树至少有_结点。5 已知A为n阶（n=1）的对称矩阵，现将其下三角部分按行优先存放在一维数组B中。矩阵元素Aij (i =j ) 在B中的下标是_。6 用邻接矩阵求最短路径的Floyd算法的时间复杂性为_。7 若一个无向图有n个顶点，e条边(ne)，且是一个森林。则它有_棵树。8对n个元素进行归并排序，需要的辅助空间为_。二 解答题（共14分）1 一棵树的先序和后序序列分别如下，画出该树。（3分）先序序列：ABCDEFGHIJKLM后序序列：CDBEFGJKLMIHA2 对下面的递归算法，写出调用f(4)的执行结果。（3分）void f(int k) if( k0 ) printf(%d ,k);f(k-1);f(k-1);华南理工大学2005年计算机综合431考研试卷数据结构（75分）一 选择题（每题只有一个答案正确，每题2分，共24分）1. 广义表A=（a,b,c,(d, (e,f)），则下面式子的值为 ；(Head与Tail分别是取表头和表尾的函数)Head(Tail(Tail(Tail(A)A(d,(e,f) B. d C.f D.(e,f)2. 一棵深度为4的完全二叉树，最少有_个结点。A. 4 B. 8 C. 15 D. 63. 稀疏矩阵一般的压缩存储方法有两种，即_。A二维数组和三维数组 B三元组表和散列C三元组表和十字链表 D散列和十字链表4. 下列判断中，_是正确的。A. 二叉树就是度为2的树 B. 二叉树中不存在度大于2的结点C. 二叉树是有序树 C. 二叉树的每个结点的度都为25. 在构造哈希表方面，下面的说法_是正确的。A链地址法在处理冲突时会产生聚集B线性探测再散列在处理冲突时会产生聚集C好的哈希函数可以完全避免冲突D在哈希表中进行查找是不需要关键字的比较的6. 以下图的叙述中，正确的是_。A强连通有向图的任何顶点到其它所有顶点都有弧B任意图顶点的入度等于出度C有向完全图一定是强连通有向图D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图7. 一棵共有n个结点的树，其中所有分枝结点的度均为k，则该树中叶子结点的个数为_。An(k-1)/k Bn-k C(n+1)/k D(nk-n+1)/k8. 具有n个顶点的无向图至多有_条边。An-1 Bn(n-1)/2 C. n(n+1)/2 D. n2/29. 深度为4 的101阶B树，最少有_个结点。A. 154 B. 105 C. 103 D. 15110. 利用逐点插入法建立序列(60，74，44，99，75，30，36，45，68，9)对应的二叉排序树以后，查找元素75要进行_元素间的比较。A4次 B3次 C. 7次 D5次11. 对数据结构，下列结论中不正确的是_。A 相同的逻辑结构，对应的存储结构也必相同B 数据结构由逻辑结构、存储结构和基本操作三个方面组成C 数据存储结构就是数据逻辑结构的机内的实现D 对数据基本操作的实现与存储结构有关12. 对AOE网的关键路径，下面的说法_是正确的。A提高关键路径上的一个关键活动的速度，必然使整个工程缩短工期B完成工程的最短时间是从始点到终点的最短路径的长度C一个AOE网的关键路径只有一条，但关键活动可有多个D任何一项活动持续时间的改变都可能会影响关键路径的改变二 解答题（每题4分，共40分）1. 设有关键字序列为： 50，71，80，60，55，40，25，99 ，用数组存储。请以堆排序方式把数据排列成递增序列。给出建堆和每趟堆调整后的数据序列。解：建堆后的数据序列每趟堆调整后的数据序列2. 画出下列矩阵的三元组表示法和十字链表表示法。0 0 0 0 08 0 1 4 00 0 0 0 20 0 2 5 03. 画出下图的邻接表，并用克鲁斯卡尔算法求其最小生成树。4. 有以下算法，分析其时间复杂度。i=1;while(i*i*inext-next的值是（ ）。A、15 B、32 C、78 D、全不是图14 一个nn的对称矩阵，如果以行或列为主序放入内存，其容量为（ ）。A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/25 快速排序在（ ）情况下最不利于发挥其长处。A、被排序的数据量太大 B、被排序的数据中有大量相同C、被排序的数据基本有序 D、被排序的数据太分散6 具有线性结构的数据结构是（ ）。A、文件结构 B、树结构 C、图结构 D、广义表7 在下列网中，（ ）是边不带权值的图。A、邮电网 B、AOV网 C、公路网 D、AOE网8 线索二叉树中某结点为叶子的条件是（ ）。A、p-lchild!=NULL|p-rchild!=NULLB、p-ltag=0|p-rtag=0C、p-lchild!=NULL&p-rchild!=NULLD、p-ltag=1 & p-rtag=19给定整数集合3,5,6,9,12，与之对应的哈夫曼（Huffman）树是（ ）。10图2是一棵( )。A、4阶B-树 B、4阶B+树C、3阶B-树 D、3阶B+树二、 简答题（每小题5分，共30分）1、 对n个顶点的无向图G，采用邻接矩阵A表示。试问：（1） 图G有多少条边？（2） 如何判断顶点i、j之间是否有边相连？（3） 如何计算一个顶点的度？2、 如果一棵二叉树n个顶点，用递归算法执行中序遍历。最坏情况时处理递归的栈至少要多少个单元？为什么？3、 设n0为哈夫曼树的叶子结点数目，简要推导该树的结点总数。4、 设有循环队列存储在结构变量q中，用C/C+编写元素x入队的算法。5、 设有n个关键字，它们具有相同的哈希函数值。若采用线性探测法将它们存放到某个哈希表中，至少需要进行多少次探测？为什么？6、“有序链表”是指什么值有序？其有序性在存储结构上用什么方式表示？三、 算法设计（25分）1、 （6分）编写一个函数，从元素类型为int的有序表A中删除所有元素值在（x, y）之间（xy，不包括x，y）所有元素。并分析你的算法效率。2、 （12分）设计算法，将一棵以二叉链表形式存储的二叉树按顺序方式存储到数组A中。算法由以下几个函数组成：函数count根据树的形态，返回要求顺序存储的数组长度函数setAry建立指定长度n的动态数组函数create把二叉树存放到数组中。其中调用count和setAry函数。3、 （7分）编写算法，求有向图G中距离顶点v的最短路径长度为len的所有顶点。 操作系统部分1 试说明进程在三个基本状态之间转换的典型原因（8分）2 试修改下面消费者生产者问题解法中的错误（12分）Producer:beginrepeatproduce an item in nextp;wait(mutex);wait(empty);buffer(in):=nextp;signal(mutex);until false;endConsumer:beginrepeatwait(mutex);wait(full);nextc:=buffer(out);out:=out+1;signal(mutex);consume item in nextc;until false;end;3 什么是抢占式调度，什么是非抢占式调度？（6分）4 试说明页面替换算法中的clock算法的基本思想（10分）5 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为：1，3，2，1，1，3，5，1，3，2，1，5，当分配给该作业的物理块数分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率。（8分）6 试说明S