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

《华南理工考研计算机历年真题》由会员分享，可在线阅读，更多相关《华南理工考研计算机历年真题（12页珍藏版）》请在装配图网上搜索。

1、华南理工考研计算机历年真题 - 华南理工大学2022年攻读硕士学位研究生入学考试试卷 试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回 科目名称：计算机专业综合一(组成原理、数据构造、操作系统) 适用专业：计算机系统构造、计算机应用技术、软件工程、计算机应用技术 I. 计算机组成原理试题 50分 一填空题共10分 1计算机的工作过程主要是周而复始地 A 、 B 和 C 的过程。 2在浮点运算中，当运算结果阶码大于所能表示的 A 时称为溢出，假设阶码用双符号S0S0的移码表示，那么当S0S0 = B 时为溢出。 3双端口存储器和多模块穿插存储器属于 A 存储器构造；前者采用 B 并

2、行技术，后者采用 C 并行技术。 4在微程序控制器中，一般采用较简单的 A 、 B 二级时序体制。 5CPU响应中断时保护两个关键的硬件状态是 A 和 B 。 二选择题共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取代PC C. 控制存储器可以用ROM实现 D. 指令周

3、期也称为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

4、的局部数据通路如图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每个顶点的度最大

5、可能是_。 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 后序序列：CDBEFGJKLMIHA 2 对下面的递归算法，写出调用f(4)的执行结果。3分 void f(int k) if(

6、 k0 ) printf(f(k-1); f(k-1); 华南理工大学2022年计算机综合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. 6 3. 稀疏矩阵一般的压缩存储方法有两种，即_。 A二维数组和三维数组 B三元组表和散列 C三元组表和十字链表 D散列

7、和十字链表 4. 以下判断中，_是正确的。 A. 二叉树就是度为2的树 B. 二叉树中不存在度大于2的结点 C. 二叉树是有序树 C. 二叉树的每个结点的度都为2 5. 在构造哈希表方面，下面的说法_是正确的。 A链地址法在处理冲突时会产生聚集 B线性探测再散列在处理冲突时会产生聚集 C好的哈希函数可以完全防止冲突 D在哈希表中进展查找是不需要关键字的比拟的 6. 以以下图的表达中，正确的选项是_。 A强连通有向图的任何顶点到其它所有顶点都有弧 B任意图顶点的入度等于出度 C有向完全图一定是强连通有向图 D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图 7. 一棵共有n个结点的树，其

8、中所有分枝结点的度均为k，那么该树中叶子结点的个数为_。 An(k-1)/k Bn-k C(n+1)/k D(nk-n+1)/k 8. 具有n个顶点的无向图至多有_条边。 An-1 Bn(n-1)/2 C. n(n+1)/2 D. n2/2 9. 深度为4 的阶B树，最少有_个结点。 A. 154 B. 105 C. 103 D. 151 10. 利用逐点插入法建立序列(60，74，44，99，75，30，36，45，68，9)对应的二叉排序树以后，查找元素75要进展_元素间的比拟。 A4次 B3次 C. 7次 D5次 11. 对数据构造，以下结论中不正确的选项是_。 A 一样的逻辑构造，对应

9、的存储构造也必一样 B 数据构造由逻辑构造、存储构造和根本操作三个方面组成 C 数据存储构造就是数据逻辑构造的机内的实现 D 对数据根本操作的实现与存储构造有关 12. 对AOE网的关键途径，下面的说法_是正确的。 A进步关键途径上的一个关键活动的速度，必然使整个工程缩短工期 B完成工程的最短时间是从始点到终点的最短途径的长度 C一个AOE网的关键途径只有一条，但关键活动可有多个 D任何一项活动持续时间的改变都可能会影响关键途径的改变 二 解答题每题4分，共40分 1. 设有关键字序列为： 50，71，80，60，55，40，25，99 ，用数组存储。请以堆排序方式把数据排列成递增序列。给出建

10、堆和每趟堆调整后的数据序列。 解：建堆后的数据序列 每趟堆调整后的数据序列 2. 画出以下矩阵的三元组表示法和十字链表表示法。 0 0 0 0 0 8 0 1 4 0 0 0 0 0 2 0 0 2 5 0 3. 画出以下图的邻接表，并用克鲁斯卡尔算法求其最小生成树。 4. 有以下算法，分析p 其时间复杂度。 i=1; while(i*i*inext-next的值是 。 A、15 B、32 C、78 D、全不是 图1 4 一个nn的对称矩阵，假如以行或列为主序放入内存，其容量为 。 A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2 5 快速排序在 情况下最不利

11、于发挥其长处。 A、被排序的数据量太大 B、被排序的数据中有大量一样 C、被排序的数据根本有序 D、被排序的数据太分散 6 具有线性构造的数据构造是 。 A、文件构造 B、树构造 C、图构造 D、广义表 7 在以下网中， 是边不带权值的图。 A、邮电网 B、AOV网 C、公路网 D、AOE网 8 线索二叉树中某结点为叶子的条件是 。 A、p-lchild!=NULL|p-rchild!=NULL B、p-ltag=0|p-rtag=0 C、p-lchild!=NULL&p-rchild!=NULL D、p-ltag=1 & p-rtag=1 9给定整数集合3,5,6,9,12，与之对应的哈夫曼

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个关键字，它们具有一样的哈希函数值。假设采用线性探测法将

13、它们存放到某个哈希表中，至少需要进展多少次探测？为什么？ 6、“有序链表”是指什么值有序？其有序性在存储构造上用什么方式表示？ 三、 算法设计25分 1、 6分编写一个函数，从元素类型为int的有序表A中删除所有元素值在x, y之间xy，不包括x，y所有元素。并分析p 你的算法效率。 2、 12分设计算法，将一棵以二叉链表形式存储的二叉树按顺序方式存储到数组A中。算法由以下几个函数组成： 函数count根据树的形态，返回要求顺序存储的数组长度 函数setAry建立指定长度n的动态数组 函数create把二叉树存放到数组中。其中调用count和setAry函数。 3、 7分编写算法，求有向图G中

14、间隔 顶点v的最短途径长度为len的所有顶点。 操作系统局部 1 试说明进程在三个根本状态之间转换的典型原因8分 2 试修改下面消费者消费者问题解法中的错误12分 Producer: begin repeat produce an item in nextp; wait(mutex); wait(empty); wait(mutex); wait(full); nextc:=buffer(out); out:=out+1; signal(mutex); consume item in nextc; 3 什么是抢占式调度，什么是非抢占式调度？6分 4 试说明页面交换算法中的clock算法的根本思

15、想10分 5 在一个恳求分页系统中，采用LRU页面置换算法时，假设一个作业的页面走向为：1，3，2，1，1，3，5，1，3，2，1，5，当分配给该作业的物理块数分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率。8分 6 试说明SPOOLing系统的原理。8分 7 某文件系统采用多级索引的方式组织文件的数据存放，假定在文件的i_node中设有13个地址项，其中直接索引10项，一次间接索引项1项，二次间接索引项1项，三次间接索引项1项。数据块的大小为4k，磁盘地址用4个字节表示，问：15分 1 这个文件系统允许的最大文件长度是多少？ 2 一个2G大小的文件，在这个文件系统中实际占用多少空间？不包括i_node占用的空间 8 什么是对称加密算法和非对称加密算法？8分 第 12 页 共 12 页