1、重庆理工大学硕士研究生试题专用纸重庆理工大学2014年攻读硕士学位研究生入学考试试题 学院名称：计算机科学与工程学院 学科、专业名称：计算机科学与技术 考试科目（代码）：计算机学科专业基础综合（810）A卷 （试题共 6 页）注意：1.所有试题的答案均写在专用的答题纸上，写在试题纸上一律无效。2.试题附在考卷内交回。一单选题(每题2分，共50分)1顺序表的第1个元素存储地址是100，每个元素占用2个存储单元，则该顺序表的第4个元素地址是（ ）A110 B108 C112 D1062一个具有n个顶点的无向完全图的边数为（ ）An(n+1)/2 Bn(n-1)/2 Cn(n-1) Dn(n+1)3
2、深度为2（根结点的层次为1）的满二叉树的叶子节点个数为（ ）A2 B4 C6 D84双向链表中每个结点的指针域的个数为（ ）A0 B1 C2 D35完全二叉树，按层次序列对每个结点编号（根结点编号为1），则编号为7的结点的双亲编号为（ ）A1 B2 C3 D46下列属于线性结构的是（ ）A线性表 B树 C查找 D图7在一个无向图中，所有顶点的度数之和等于所有边数的（ ）A1倍 B2倍 C4倍 D8倍8栈的特点是（ ）A先进后出 B先进先出 C后进后出 D前出前进9深度为3（根的层次号为1）的满二叉树结点个数为（ ）A4 B6 C7 D810不带头结点的单链表head为空的判定条件是（ ）Ahe
3、ad=NULL Bhead-next=NULL Chead!=NULLDhead-next!=NULL11有一个有序表为2，3，8，10，30，当折半查找到8时，需要的比较次数为（ ） A. 1 B. 2 C. 3 D. 412栈的插入与删除操作在（ ）A栈顶 B栈底 C队头 D队尾13一个栈的入栈顺序是a,b,c，则该栈的不可能的输出序列是（ ）Aabc Bcba Cacb Dcab14设先序遍历某二叉树的序列为ABC，中序遍历该二叉树的序列为BAC，则后序遍历该二叉树的序列为（ ）AABC BCBA CACB DBCA15设一组初始记录关键字序列(5，2，6，3)，以第一个记录关键字5为基
4、准进行一趟快速排序的结果为（ ）A2，3，5，6 B5，2，3，6 C3，2，5，6 D2，3，6，516在计算机中配置操作系统的主要目的是( )A. 增强计算机的功能 B. 提高系统资源的利用率 C. 提高系统的运行速度 D. 合理组织系统的工作流程17从静态角度讲，进程由程序段、数据段和( )组成，它是进程存在的唯一标志。AJCB B. PCB C.FCB D. 代码段 18临界区是指( )A. 进程中用于访问共享资源的那段代码。B. 进程中用于实现进程同步的那段代码。C. 进程中用于实现进程互斥的那段代码。D. 进程中用于访问临界资源的那段代码。19下面哪种情况不会引发进程调度？( )
5、A. 进程正常结束或异常中止。B. 正在执行的进程因I/O请求而被阻塞。C. 某等待打印机的进程发现其它使用打印机的进程已经打印完毕。D. 在引入时间片的系统中，时间片用完。20内存管理的基本任务是提高内存的利用率，使多道程序能在不受干扰的环境中运行，这主要是通过下面哪种功能实现的？( )A. 内存分配 B. 内存扩充 C. 内存保护 D. 兑换21在一般大型系统中，主机对外围设备的控制可通过通道、控制器和设备三个层次来实现。从下述中选择一个正确的叙述。( )A. 通道控制控制器，设备在控制器控制下工作。B. 控制器可控制通道，设备在通道控制下工作。C. 通道和控制器分别控制设备。D. 控制器
6、控制通道和设备。22在文件系统中，必须为每个文件建立( ), 其中包括文件名和文件的物理地址等信息。A. 用户文件描述符表 B. 索引结点C. 文件控制块 D. 索引表23磁盘调度的策略主要是为了优化( )A. 交换时间 B. 寻道时间 C. 旋转延迟时间 D. 传输时间24动态重定位的主要目的是使作业在内存中移动，动态重定位发生在( )A. 编译过程 B. 装入过程 C. 链接过程 D. 运行过程25在命令行接口中，使命令的执行结果不在屏幕上显示，用于把第一条命令的输出作为第二条命令的输入，第二条命令的输出作为第三条命令的输入的功能设施称为( )A. 管道 B. 链接 C. 脱机输入 D.
7、联机输出二简答题(每题5分，共60分)26计算程序段的时间复杂度。（5分）for (i=1; i=n; i+)x+;27设给定权集W=2，3，4，7，试构造关于W的一棵赫夫曼树，并求其带权路径长度WPL。（5分）28设有一序列30,19,3,61，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度ASL。（5分）29写出下图所示二叉树的先序，中序和后序遍历序列。（5分）ABDE 30什么是线性表? 线性表的元素之间的关系是什么?（5分）31 已知待散列的线性表为（8，15，40，63），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探
8、查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。（5分）012345632. 请画图说明进程的三种基本状态及各状态间的转换，并说明引发状态转换的典型事件。（5分）33. 什么是操作系统，简述操作系统的主要功能。（5分）34. 什么是死锁，分析死锁发生的主要原因。（5分）35. 虚拟存储器的基本特征有哪些？为什么说请求分页系统是实现虚拟存储器是一种方式？（5分）36.什么是中断，描述CPU访问中断的一般过程。（5分）37. 在公共汽车上，司机与售票员的工作流程如下图所示。为保证乘客安全，司机和售票员必须密切配合协调工作，售票员在关车门之后向司机发送开车信号，司机接到开车信号后启动车辆
9、，汽车正常行驶时售票员可以售票，到站时司机停车，售票员在停车后开门让乘客下车，请用信号量来实现司机与售票员之间的同步。（5分）三综合题(每题10分，共40分)38编写一个函数，实现对数组a(元素个数为n)中元素进行冒泡排序的算法。（10分） void bubblesort(int a)39编写两个函数，分别实现对二叉树的先序遍历(preorder)和中序遍历(inorder)的递归算法。（10分）二叉树结点的结构体为 struct BiTreeNode int data;struct BiTreeNode * leftChild;struct BiTreeNode * rightChild;
10、typedef struct BiTreeNode Node; void preorder (Node * t) /*t为指向二叉树的根结点的指针*/ void inorder (Node * t) /*t为指向二叉树的根结点的指针*/40. （本题10分）有四个进程P1,P2,P3,P4，它们进入就绪队列的先后顺序为P1,P2,P3,P4，它们的优先级和需要的处理机时间如下表。假定这四个进程在执行过程中不会发生等待事件，忽略进程调度所花费的时间，从某个时刻开始进程调度，请回答下面的问题：进程要求的处理时间优先级P183P261P3225P444(1) 采用“先来先服务”调度算法时，写出进程的
11、执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（4分）(2) 采用“非抢占式的优先级”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；（4分）(3)说明采用“时间片轮转法”调度算法时，写出进程的执行顺序，计算各进程在系统中停留的时间以及平均停留的时间。（2分）41. （本题10分）某系统采用页式存储管理策略，请回答下面的问题：(1) 若逻辑空间为32页，每页2K，物理空间1M，写出逻辑地址的格式。若不考虑访问权限等，进程的页表有多少项，每项至少多少位？如果物理空间减少一半，页表结构应相应地怎样变化。（6分）(2) 假定页表放在内存中，如果访问内存需要0.3s，计算有效访问时间；（2分）(3) 如果加一快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少？（2分）第1页
