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

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

第1页 / 共5页

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

第2页 / 共5页

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

第3页 / 共5页

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

第4页 / 共5页

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

第5页 / 共5页

2019 年重庆理工大学计算机学科基础综合考研真题 A 卷一、选择题(50 分，25 小题，每小题 2 分) 1.数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的( ) 和运算的学科。 A.结构 B.关系 C.数值 D.算法 2.线性表是一个可在( )位置对数据元素进行插入、删除操作的序列容器。 A.仅表头 B.仅表尾 C.任意 D.都是 3.将长度为 n的单链表连接在长度为 m的仅带头指针的单链表后面，其算法的时间复杂度为( )。 A.O(1) B.O(n) C.O(m) D.O(m + n) 4.在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件， front 和 rear 分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为 maxSize，则队列的判空条件是( )。 A.front== rear B.front!= rear C.front==rear+ 1 D.front==(rear+1)% maxSize 5.下面关于串的叙述中，不正确的是( )。 A.串是字符的有限序列 B.空串是空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 6.对特殊矩阵采用压缩存储的目的主要是为了( )。 A.表达变得简单 B.对矩阵元素的存取变得简单 C.去掉矩阵中的多于元素 D.减少不必要的存储空间 7.对一棵满二叉树，有 A 个叶结点、B 个结点、深度为 C，则( )。 A.B=C+1 B.C+A=2B C.A=C-1 D.B= -1 8.任意一棵二叉树，其叶结点在先根遍历、中根遍历和后根遍历序列中的相对次序( )。 A.保持不变 B.先根遍历和中根遍历有变化，后根遍历无变化 C.先根遍历和后根遍历有编号，中根遍历无变化 D.中根遍历和后根遍历有变化，先根遍历无变化 9.一个有 n 个顶点的无向图最多有( )条边。 A.n B.n(n-1) C.n(n-1)/2 D.2n

10.对某个无向图的邻接矩阵来说，下列叙述正确的是( )。 A.第 i 行上的非零元素个数和第 i 列上的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第 i 行与第 i 列上的非零元素的总数等于顶点 vi 的度数 D.矩阵中非零行的行数等于图中的顶点数 11.对于含有 n 个顶点的带权连通图，它的最小生成树是指图中的任意一个由( )子图。 A.n-1 条权值最小的边构成的 B.n-1 条权值之和最小的边构成的 C.n-1 条权值之和最小的边构成的连通 D.n 个顶点构成的边的权值最小的边构成的极小连通 12.在用邻接表表示图时，拓扑排序算法的时间复杂度为( )。 A.O(n) B.O(n+e) C.O(n2) D.O(n3) 13.内部排序算法的稳定性是指( )。 A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变 B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变 C.排序算法的性能与被排序元素个数关系不大 D.排序算法的性能与被排序元素个数关系密切 14.下列排序算法中，( )排序算法可能会出现下面的情况，初始数据有序时，花费的时间反而更多。 A.快速 B.堆 C.希尔 D.冒泡 15.在下列的排序中，序列( )是堆。 A.1，2，8，4，3，9，10，5 B.1，5，10，6，7，8，9，2 C.9，8，7，6，4，8，2，1 D.9，8，7，6，5，4，3，7 16.操作系统提供给应用程序的接口是( A.P、V 操作 B.中断 C.库函数 )。 D.系统调用 17.现代操作系统基本都采用缓冲技术，目的是为了( A.提高编程效率 C.实现设备无关性 B.提高 CPU 的处理速度 D.提高设备和 CPU 之间的并行程度 )。 18.下列哪个程序可以在用户态执行？( A.时钟中断处理程序 B.游戏程序 C.缺页处理程序 D.进程调度程序 ) 19.外存上存放的数据( A.先要调入虚拟存储器中才能有 CPU 访问 )。

B.CPU 可直接访问 C.必须在访问前先装入主存 D.可以直接调入高速缓冲存储器中 20.下面哪个不属于 I/O 控制方式？( A. 通道技术 B. DMA 方式 ) C.覆盖方式 D.中断方式 21.进程在系统中是否存在的唯一标志是( )。 A.数据集合 B.目标程序 C.源程序 D.进程控制块 22.存储管理技术中通常采用对换技术，目的是( A.提高内存利用率 B.实现主存共享 C.物理上扩充 D.节省存储空间 )。 23.在文件系统中，文件的属性可以集中存放在( A.索引 B.作业控制块 C.目录 24.下列哪种方式不能提高磁盘设备的 I/O 速度？( A.重排 I/O 请求次序 C.预读和滞后写 B.优化文件的物理分布 D.在一个磁盘上设置多个分区 )中以便查找。 D.字典 ) 25.操作系统需要解决的问题不包括( A.提供程序保护和安全机制 C.提供应用程序接口 )。 B.提供高级语言的编译器 D.管理目录，提供文件访问方式二、综合题(100 分，12 小题) 26.(5 分)假设一棵二叉树包含的结点数据值为 1，4，9，3，20，请画出两棵高度最大的二叉树。 27.(5 分)一棵二叉树，其先根遍历序列为 ABDCEGHF，中根遍历序列为 DBAGEHCF，请写出其后根遍历序列。 28.(5 分)已知一无向图 G=(V，E)，其中 V={a，b，c，d，e}，E={ (a，b)，(a，d)，(d， c)，(b，e)}，现用深度优先遍历方法从顶点 a 开始遍历图，写出所得到的遍历序列。 29.(8 分)假定某系统中有 Z1、Z2、Z3 三个资源，现有 A，B，C 三个进程并发工作。如果各个进程运行需要的资源情况为：进程 A 需要资源 Z3 和 Z1，进程 B 需要资源 Z1 和 Z2，进程 C 需要资源 Z2 和 Z3。回答： (1)若对资源分配不加限制，会发生什么情况，举例说明为什么。(3 分) (2)为保证各个进程正常推进，可能采取哪些资源分配策略，阐述原因？(5 分) 30.(8 分)进程运行过程中，可能引起进程状态变化的情况很多，简述什么是进程调度，可能引起进程调度的情况有哪些？

31.(8 分)在请求分页管理系统中，假定有 5 个作业，在某时刻作业要求访问的页面顺序是 4、1、2、3、1、2、4、1、3、2、1、3，若分配的物理块只有 3 块，回答下列问题： (1)解释什么情况下会发生缺页中断？(2 分) (2)分别采用 FIFO、LRU 和 clock 页面分配算法，写出内存块中页面的变化情况，并求各种方式下缺页中断的次数和缺页率。(6 分) 32.(7 分)假设某通信的电文仅由 4 个字符组成，每个字符在电文中出现的频度分别为{32， 7，24，2}。 (1)请为这 4 个字符设计哈夫曼编码。(4 分) (2)该哈夫曼编码的平均码长是多少？与用 2 位二进制数(即 00，01，10，11)对这 4 个字符进行等长编码相比，哈夫曼编码使该电文的总长平均压缩了多少？(3 分) 33.(8 分)请对如图所示的无向图：写出它的邻接矩阵(4 分)，并按照克鲁斯卡尔算法求其最小生成树(4 分)。 34.(10 分)设哈希函数为 H(key)=key mod 13，试用关键字序列{39，25，15，54，26，24， 14，21，37，38}构造哈希表。使用链地址法处理冲突，画出该哈希表的存储结构图(7 分)；在等概率的情况下，计算查找成功时的平均查找长度(3 分)。 35.(10 分)有一个带头结点的单链表 L，设计一个算法，使其元素递增有序。 36.(12 分)有一组进程 P1，P2，P3，P4，P5 需要运行，它们需要的 CPU 时间和优先级如下表。假定这五个进程在 0 时刻按 P5，P4，P3，P2，P1 的顺序到达，在执行过程中不会发生等待，忽略进程调度所花费的时间，从 0 时刻开始进程调度，请回答下面的问题：进程要求的处理时间优先级 P5 P4 P3 P2 P1 1 4 1 3 2 3 4 5 1 3 (1)画出采用先来先服务、短作业优先、时间片轮转的调度算法时，进程执行顺序的甘特图。 (4 分)

(2)计算每个进程的周转时间和平均周转时间。(4 分) (3)计算每个进程的等待时间和平均等待时间。(4 分) 37.(14 分)某快递仓库的工作人员分为两类：快递姐和快递哥，快递姐的任务是接收从外地送到本仓库的快件，快递哥的任务是将本仓库中的快件送到客户手里。该仓库一共能存放 2000 个快件包裹，当仓库未装满时，快递姐可以接收快件放入仓库，否则等待；当仓库不空时，快递哥可以从仓库中取走快件装车，否则等待。要求每次每个快递哥从仓库连续取出 30 件产品后，其他快递哥才可以从仓库中取快件，请用信号量和 P，V 操作实现快递姐和快递哥的操作互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。

资料库

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

相关推荐

考研

热门标签

最新资料