1、重庆理工大学硕士研究生试题专用纸重庆理工大学2017年攻读硕士学位研究生入学考试试题 学院名称:计算机科学与工程学院 学科、专业名称:计算机科学与技术 考试科目(代码):计算机学科基础综合(813)A卷 (试题共 4 页)注意:1.所有试题的答案均写在专用的答题纸上,写在试题纸上一律无效。2.试题附在考卷内交回。一单选题(每题2分,共50分)1数据元素之间的存储结构,除了链式存储结构,另外一种存储结构是( )A线性存储结构 B树形存储结构 C顺序存储结构 D图形存储结构2图形结构之间是( )A一对多关系 B一对一关系 C多对多关系 D一对二关系3算法有5个特性,下列哪项不是算法的特性( )A有
2、穷性 B输入 C可行性 D队列4带头结点的单链表H为空的条件是( )AH=NULL BH-next=NULL CH!=NULL DH-next!=NULL5完全二叉树,按层次序列对每个结点编号(根结点编号为1),则编号为8的结点的双亲编号为( )A3 B4 C5 D66下列属于线性结构的是( )A栈 B树 C查找 D图7顺序表的第1个元素存储地址是700,每个元素占用3个存储单元,则该顺序表的第4个元素地址是( )A703 B706 C709 D71288个顶点连通图的最小生成树中边的数目是( )A4 B5 C6 D79深度为5(根的层次号为1)的满二叉树结点个数为( )A15 B16 C31
3、 D3210在一个无向图中,边的数目为6,则所有顶点的度数之和为( )A6 B12 C18 D2411有一个有序表为4,5,7,8,9,当折半查找到4时,需要的比较次数为( ) A. 1 B. 2 C. 3 D. 412一个栈的入栈顺序是ABCDEF,则该栈不可能的输出序列是( )AABCDEF B FEDCBA CDCBAEF DCABFDE13完全二叉树共有22个结点,按层次序列对每个结点编号(根结点编号为1),则编号为4的结点的右孩子编号为( )A7 B8 C9 D1014设先序遍历某二叉树的序列为ABCDE,中序遍历该二叉树的序列为CBAED,则后序遍历该二叉树的序列为( )AABCD
4、E BCBAED CCBEDA DCBDEA15深度为4(根结点的层次号为1)的满二叉树的叶子节点个数为( )A8 B10 C12 D1616. 在汽车电子系统中使用的操作系统属于( )A个人计算机操作系统 B分布式操作系统C嵌入式操作系统 D批处理操作系统17下列选项不属于操作系统的特征的是( )A并发性 B共享性 C虚拟性 D确定性18在操作系统中,一般不实现进程从( )状态的转换A就绪等待 B执行就绪 C就绪执行 D等待就绪19对进程的控制和管理使用( )A原语 B指令 C信号量 D通信20下列进程调度算法中,综合考虑等待时间和执行时间的是( ) A时间片轮转调度算法 B短进程优先调度算
5、法C先来先服务调度算法 D高响应比优先调度算法21死锁和安全状态的关系是( )A死锁状态有可能是安全状态 B死锁状态一定是不安全状态C安全状态也可能是死锁状态 D不安全状态必定产生死锁22为了保证CPU执行程序指令时,能够正确访问内存单元,需要将用户进程中的逻辑地址转换为运行时可由CPU寻址的物理地址,这一过程称为( )A地址分配 B地址映射 C地址计算 D地址查询23下列关于虚拟存储的叙述中,正确的是( )A虚拟存储容量只受外存容量的限制B虚拟存储容量只受内存容量的限制C虚拟存储只能基于连续分配技术D虚拟存储只能基于非连续分配技术24在I/O数据传送控制中,CPU干预最少的是( )A中断控制
6、方式 BDMA方式 C通道方式 D程序直接控制方式25文件系统采用多级目录结构后,对于不同用户的文件,其文件名( )A应该相同 B应该不同 C可以相同,也可以不同 D受系统约束二简答题(每题5分,共50分)26队列的定义是什么? 队列的特点是什么?(5分)27计算程序段的时间复杂度(N为常量)和语句的语句频度(5分) m=0; for(i=1;i=N;i+) for(j=1;j=N;j+) m+;28设有一序列25,16,3,88,13,58,请按该序列构成一棵二叉排序树,并求其查找成功时的平均查找长度ASL。(5分)29设给定权集W=3,4,5,8,9,试构造关于W的一棵赫夫曼树,并求其带权
7、路径长度WPL。(5分)30树的定义是什么? 树的元素之间的关系是什么?(5分)31高级调度和低级调度的主要任务是什么?为何要引入中级调度?(5分)32请简要说明分页式和分段式内存管理的异同。(5分)33什么是SPOOLing技术?SPOOLing系统有哪几部分组成?(5分)34如果信号量的初值是5,现在信号量的值是-5,那么系统中的相关进程至少执行了几个P(S)操作?与信号量S相关的处于阻塞状态的进程有几个?如果要使信号量的值大于0,应该进行怎样的操作?(5分)35三个进程共享四个资源,这些资源的分配与释放只能一次一个。已知每一进程最多需要两个资源,问该系统会发生死锁吗?请说明理由。(5分)
8、三综合题(共50分)36假设二叉树采用如下的存储结构,其中lchild和rchild为分别指向左右孩子的指针。 typedef struct node int data; struct node *lchild,*rchild; TwoTree;编写2个算法,分别用递归方法求二叉树的深度(Deeptree)和二叉树叶子结点个数(Leafcount)。 (10分)int Deeptree(TwoTree *bt) /*bt为指向二叉树的根结点的指针*/int Leafcount(TwoTree *bt) /*bt为指向二叉树的根结点的指针*/37编写2个算法,分别实现对数组a(元素个数为n)中元
9、素进行简单选择排序(selectsort)和快速排序(quicksort)算法,其中low为下界,high为上界。(15分) void selectsort(int a, int n) void quicksort(int a, int low, int high)38(10分)某采用分页存储管理的系统中,物理地址占20位,逻辑地址中页号占6位,页大小为1KB,请分析:(1)该系统的内存空间大小为多少?每个内存块的大小为多少?(4分)(2)逻辑地址共几位?每个作业最大长度为多少?(4分)(3)若某作业的第0、1、2页分别放在内存的第3、7、9块中,则逻辑地址0420H对应的物理地址是多少?(2分)39(15分)假设磁盘有200个磁道,磁盘请求到达次序为98,183,37,122,14,125,60,66,当前磁头在53号磁道上,并向磁道号减小的方向移动。(1)采用FCFS(先来先服务)进行磁盘调度时,请分析上述磁盘请求对应的磁盘服务次序,并计算平均寻道长度。(5分)(2)采用SSTF(最短寻道时间优先)进行磁盘调度时,请分析上述磁盘请求对应的磁盘服务次序,并计算平均寻道长度。(5分)(3)采用SCAN(扫描算法)进行磁盘调度时,请分析上述磁盘请求对应的磁盘服务次序,并计算其平均寻道长度。(5分) 第5页