《电子科技大学820计算机专业基础考研试题》由会员分享，可在线阅读，更多相关《电子科技大学820计算机专业基础考研试题（8页珍藏版）》请在金锄头文库上搜索。
1、dow nl oad.kaoya n. com电子科技大学2011年攻读硕士学位研究生入学试题考试科目：820计算机专业基础注建所有答案必须写在答题纸上，做在试卷或草藕纸上无效数据结构75分选择题(每小题1分，共8分)1. 若结点的存储地址与其关键字值之间存在某种对应关系，则称这种存储结构 为()A.顺序存储结构链式存储结构U索引存储结构D散列存储结构2*能在0(!)时何内访问线性表的第i个元素的结构是(A 顺序表单链表C.单向循环链表D.双向链表3. 个nxn的对称矩阵.如果以行主序存储，每个元素占一个单元片则其需要的垠大存储空间为n/2 D (n+l)x(n+l)/24. 已知一稀疏矩阵的
2、三元组表为半(】2 3), (1. 6. 1). (3. 1 5), (3, 2, -1), (4, 5 4). (5, h3).则其转置矩阵的三元组表中第3个三元组为( )A”(2, b 3)B.(3, b 5)C(3# 2* -1)D.(2* 3, “)5. 在有n个结虑的二叉链表中，值为空的链域的个数为()A, n-1 B. n+1 C 2n-l D, 2n+l6. 对于一个具言ii个顶点的无向图，若采用邻接表表示，则存放表头结点的数 组的大小为()AnB.n+1Cn-1D.n+1 边数7.下所示的二叉树是()#dow nl oad.kaoya n. comA.二叉判定树 二叉排序树 C
3、.二叉平衡树D.堆#dow nl oad.kaoya n. com&用某种排序方法对关键字序列C25, 行排序时，序列的变化惰况如下j20,15,21,25,4727*6&15,20,21.25,35,27,47,1520,21,25,27,35,47,则所采用的排序方法是()A+选择排序B帑尔排序84, 21* 47, 15. 27, 6& 35. 20）进35* 8468, 8468 84C.归并排序 D.快速排序二轄填空题(每小题1分，共8分)1, 若一个隽法中的语句频度之和为T(n)=3720n+4nlogn,则算法的时间复杂度为。2. 在长度为I的顺序表的第i(li 12, 34.
4、38, 33, 27. 22”构造一个表长为11的散列 表，并求其查找成功的平均长度，#dow nl oad.kaoya n. com.算法题（共23分）L (6分)阅读算法testOl,说明其功能；int resiOlfint afjjnt lowjnt high, int x)/low和曲曲分别为数据区的下界和上界 inf ijtt;i-low;jhigh;while(ij)whiie(iJ & aJx幼一; while(ij &if(aijda(a); test02 (roof-lchild); printfC%c* roQt-data); testO2 (root-rchild);1
5、（11分）编写一算法将顺序表转存为带头节点的单循环链表姿算法中所用到的数据结构需自行定义。2S0dow nl oad.kaoya n. com操作系统部分7S分x单项选择题（每小题2分*共16分，下面每题给出的四个选项中，只有一个最符 合试题要求K机票订购系统处理来自各个终缩的股务请求，处理后通过终端冋答用户，所以它足一个 ）.甩分时系统氐多道批处理系统C计算机网络D实时信息处理系统2. 操作系统在计算机系统中位于（之何.A.CPU和用户之间中央处理器CPUC计算机硬件和用户D 计算机碘件和软件之间3在单处理机系统中，可并行的是（1进程与进程 II处理机与设备Ill处理机与通道IV设备与设备九
6、 I . H 利UB. I . II 和 IVC I . Ill和IVD. IK Ill和 IV4. 进程具有3种基本状态丁就绪状态、执行状态和阻塞状态.进程在执行过程中.其状态 总是不停地发生变化下面关于进程扶态变化的说法中正确的足（）.A.个进程必須经过进程的3种基本状态才能结束B*在分时系统中* 一个正在运行进程的时间片如果终结*该进程将转入就绪状态C.三种进程状态是进程运行过程中的基本状态.进程可能同时处于某几种状态中Dia穆一旦形成，首先进入的是运行状态5. 采用中断屏蔽技术*会封锁（）的响应A.与自己级别相同的中断事件3比自己级别高的中断事件C与中断屏抵标志相对应的事件D上匕自己级
7、别低的中断事件6. 页表的作用是实现从页号到物理块号的（）A 逻辑映射B物理陕射C地址映射D逻辑地址映肘7. 分贞式處拟存储管理系统中，页面的大小与可能产生的缺页中断次数（人A.成正比B.成反比U无关D.成固定值緘 下面4个选项中不属于SPOOLing系统特点的是（）A.提高了内存的利用率B提高了 I/O撫作的速度C檢独占设备改造为共寧设各 D实现J虚拟设备功能二、填空题（每空2分，共11题，22分）1. 文件系统的主要目标是提离存储空间的利用率和一2. 可变分区管理方式常用的主存分配算法有：最先适应分配算法、和3. 进程可以井发执行.着干个并发执行的进程交替占用处理器，而进程各种状态的转换不
8、是事先预定的.也不是完全由操作系统来确定的，而是在SE件和操作系统的相互配合下完成的.起主要作用的是一4. 在存储管理方案中.可用上、下限寄存器实现存储保护的是5. 位图可以用來播示磁盘存储空脚的使用1W况.一个磯盘组的分块确定后f根据可分配的总块数决定位图由多少个字组成.位图中的毎一位与一块对应V状态我示相应块 已 0状态表示该块*6. 死锁的4个必要条件是.不可抢夺资源和循环等持瓷7. 当一个进程独占处理器顺序执疔时.具有两个特性：和三、简答题（每小题6分，共5小题，30分）K请描述在当前运行进程状态改变时.操作系统进疔进程切换的步驟*2. 试写出P （S操作的主要探作步骤。3. 阐述对于互斥临界区的管理要求.4. 为什么要在设备管理中引入緩冲技术？操作系统如何实现缓冲技术？5. 解释页式存储曽理中为什么要设置页表和快表.四、计算题（7分）现有一个仅460个字节的程序的下述内存访问序列（该序列的下标均从0开始h 10. 小】04. 170. 73、309悟 185. 245 246、434. 458. 364* 且页面大小为 100字节；（1）写出页面的访问序列* （2分）（2）假设内存中仅有200字节可供程序使用且釆用FIFO算法，那么共发生多少次缺 页中斷？（3分（3）如果采用舉近罐久未使用的算法，则又会发生多少次缺贡中斷？（3分）#
