2018年重庆理工大学计算机学科基础综合考研真题A卷.doc-资料库

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc.pdf-第1页.jpg

第1页 / 共5页

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc.pdf-第2页.jpg

第2页 / 共5页

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc.pdf-第3页.jpg

第3页 / 共5页

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc.pdf-第4页.jpg

第4页 / 共5页

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc.pdf-第5页.jpg

第5页 / 共5页

2018 年重庆理工大学计算机学科基础综合考研真题 A 卷一、单选题（每小题 2 分，共 40 分） 1．算法分析的目的是（）。 A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和稳定性 2．设某算法完成对 n 个元素进行处理所需的时间是：T(n) = 200log2n + 1000n(log2n + 100) + 100000，则该算法的时间复杂度是（）。 A．O(1) B．O(n) C．O(nlog2n) D．O(nlog2n+log2n) 3．若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 4．在中缀表达式转化为后缀表达式与后缀表达式求值算法中，都需要用到哪种特殊的数据结构（）。 A．栈 B．队列 C．二叉树 D．堆 5．一个队列的入队序列是 1，2，3，4，则队列的出队序列只能是（）。 A．4，3，2，1 B．1，2，3，4 C．1，4，3，2 D．3，2，4，1 6．将含有 100 个结点的完全二叉树从根结点开始编号，根为 0 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为（）。 A．42 B．40 C．21 D．20 7．如果在某二叉树的前序序列、中序序列和后序序列中，结点 b 都在结点 a 的后面（即形如… a…b…），则最有可能的情况是（）。 A．a 和 b 是兄弟 B．a 是 b 的双亲 C．a 是 b 的左孩子 D．a 是 b 的右孩子 8．某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，其前序遍历序列是（）。 A．acbed B．decab C．deabc D．cedba 9．下述编码中，哪一个不是前缀码（）。 A．(0,10,110,111) B．(11,10,001,101,000) C．(00,010,011,1) D．(1,01,000,001) 10．一个有 n 个顶点的无向图最多有（）条边。

A．n B．n(n-1) C．n(n-1)/2 D．2n 11．在现代操作系统中，采用缓冲技术的主要目的是（） A．改善用户编程环境 B．提高 CPU 的处理速度 C．实现与设备无关 D．提高设备与 CPU 之间的并行程度 12．下列哪个事件不可能在用户态发生？（） A．系统调用 B．外部中断 C．进程切换 D．缺页 13．操作系统是对（）进行管理的软件。 A．软件 B．硬件 C．计算机资源 D．应用程序 14．子程序调用和中断处理子程序都是以压入堆栈的方式来保护现场的，下面哪个寄存器中的内容是中断处理一定会保存而子程序调用不用保存的？（） A．程序计数器 B．通用地址寄存器 C．通用数据寄存器 D．程序状态寄存器 15．进程和程序的一个本质区别是（） A．进程是动态的，程序是静态的 B．进程存储在内存，程序存储在外存 C．进程在一个文件中，程序在多个文件中 D．进程分时使用 CPU，程序独占 CPU 16．下列不属于 I/O 控制方式的是（） A．程序查询方式 B．覆盖方式 C．DMA 方式 D．中断方式 17．在内存采取分区管理方式时，分区的保护措施主要是（） A．界限寄存器进行地址保护 B．程序状态保护 C．用户权限保护 D．存取控制保护 18．在一个文件被用户进程首次打开的过程中，操作系统需做的是（） A．将文件内容读入内存 B．将文件控制块读入内存 C．修改文件控制块的读写权限 D．将文件的数据缓冲区首指针返回给用户进程 19．计算机系统的二级存储包括（） A．CPU 寄存器和主存缓存 B．超高速缓存和内存储器 C．主存储器和辅助存储器 D．ROM 和 RAM 20．在不同速度的设备之间传送数据（） A．必须采用同步控制方式 B．必须采用异步控制方式 C．可用同步方式，也可以用异步方式 D．必须采用应答方式二、综合题(110 分)

21．(本小题共 5 分)有如下递归函数 fact(n)，分析其时间复杂度。 fact(int n){ if(n<=1) return(1)； ① else return(n * fact(n-1))； ② } 22．(本小题共 5 分)有一种数据结构 B1=（D，R），其中：D={48，25，64，57，82，36，75}， R={<25，36>，<36，48>，<48，57>，<57，64>，<64，75>，<75，82>}，画出其逻辑结构表示（3 分），指出是什么类型的逻辑结构？（2 分） 23．(本小题共 10 分)有数据{43，54，90，46，31}，列出冒泡排序每趟的结果(6 分)。编写冒泡排序算法 BubbleSort(RecType R[]，int n)的实现程序(4 分)。 24．(本小题共 10 分)假设哈希表长度 m=13，采用除留余数法哈希函数建立如下关键字集合的哈希表：(16，74，60，43，54，90，46，31，29，88，77)。并采用线性探查法解决冲突。 25．(本小题共 5 分)有一组关键字序列{66，89，8，123，9，44，55，37，200，127，98}，请将其调整成初始大根堆，画出初始大根堆的树型表示。 26．(本小题共 9 分)有一份电文中，使用了 a、b、c、d 这 4 个字符，各字符出现频率如下表。字符出现频率 a 23 b 11 c 3 d 5 试构造对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造） (6 分)，并求出每个字符的哈夫曼编码(3 分)。 27．(本小题共 8 分)对于如图所示的带权无向图，给出利用普里姆算法（从顶点 0 开始构造）构造出的最小生成树的结果。（注意：按求解的顺序给出最小生成树的所有边，每条边用(i，j)表示，顺序错误不给分！）

28．(本小题共 8 分)有如下工程项目的 AOE 图，其中数字表示该项活动需要的天数：（1）列出图中各顶点（事件）的最早发生时间和最迟发生时间(4 分)。（2）计算完成该项目所需的时间，指出哪些是关键活动(2 分)。（3）缩短任一关键活动的时间，是否会缩短整个工程的时间？(2 分) 29．(本小题共 8 分)现代操作系统采用分层设计，用户程序发出磁盘 I/O 请求后需经过 4 个层次的调用才能进行实际的 I/O 操作，阐述系统进行 I/O 操作的 4 个层次和具体的处理流程。 30．(本小题共 8 分)在多道系统中，由于有多个进程运行可能导致死锁，阐述什么是死锁，有哪些情况可能会导致死锁，并简要说明阐述死锁的条件。 31．(本小题共 10 分)一个多道批处理系统中仅有 A1 和 A2 两个作业，A2 比 A1 晚 10ms 到达，它们的计算和 I/O 操作顺序如下： A1：计算 60ms，I/O 80ms，计算 20ms A2：计算 120ms，I/O 若不考虑调度和切换时间，则完成两个作业需要的时间最少是多少？说明计算依据？ 40ms，计算 40ms 并用示意图表示进程的运行时间图。

32．(本小题共 10 分)解释什么是最佳适应分区分配算法和最坏适应分区分配算法？各自的空闲分区是怎样组织的？各有什么缺点？设主存的分配情况如下图所示。当有一个用户进程 U 需申请 45KB 的存储区时，若采用最佳适应和最坏适应进行分配，U 所分到的分区首地址分别为多少？ 33． 33．(本小题共 14 分)某企业有多个生产线和多个销售人员，他们共用可存放 100 个产品的仓库，当仓库未装满时，生产线可以将生产的一件产品放入仓库，否则等待；当仓库不空时，销售人员可以取走一件产品出售，否则等待。要求一个销售人员从仓库连续取出 5 件产品后，其他销售人员才可以取产品，请用信号量 P，V（wait，signed）操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。

资料库

2018年重庆理工大学计算机学科基础综合考研真题A卷.doc

相关推荐

考研

热门标签

最新资料