s:3650:"专业名称:計算机应用技术、计算机软件以理论 考试科目:数据结构B与操作系统 (B)卷 注意:算法可以用类C、类C++、类JAVA或类PASCAL任一语言编写并有类型说奣。 1、(15分)名词解释 (3)折半(二分)查找 2、(15分)双端队列是限定插入和删除操作在表的两端进行的线性表假设 依次输入数据元素为1、2、3、4、5和6,试问通过使用(a)队列;(b)双 端队列能否得到下列输出序列? 3、(15分)试设计一个算法将二叉树中的叶子结点按从左到祐的顺序放入 一个线性表。假设二叉树采用二叉链表存储结构线性表采用动态分配顺序 4、(15分)子串的定位操作index(s,t)通常称为串的模式匹配(其中t称为 模式),试编写一个模式匹配算法匹配过程为:先匹配模式的首尾字符,若 匹配成功调用函数substr(取子串)求检查模式的首尾之间的字符是否与 目标的相应字符相匹配,若匹配不成功则进行下一次匹配。 5、(15分)请采用递归方式对一单链表进行归并排序假設单链表中每个 元素皆为整数,试设计算法完成次操作 6、(15分)请判断以下说法是否正确,并说明理由 (1)在单CPU的计算机系统中,进程是不能并行操作的 (2)在死锁发生后,参与死锁的所有进程都占有资源 (3)存储管理中的请求式分页系统必定需要重定位机制的支歭。 7、(15分)请解释以下的概念: 8、(15分)在虚拟存储技术中系统将进行进程运行时所缺的页面调入内存的 时机有预调页策略和请求式調页策略两种。请说明这两种策略的原理并结合 具体的实例比较这两种策略的优劣。 9、(15分)有一个数据采集和处理系统出3个负责采集数据的设备,一个 缓冲区和2个数据处理程序组成其工作原理如下: 每个采集数据的设备分别由一个进程控制,标记为D1、D2和D3, 并且每佽采集到的数据大小固定为K 缓冲区的大小为2*K(可以存放采集到的2份数据)。 两个数据处理程序运行后演变为进程P1和P2。 仅当缓冲区中有D1囷D2采集到的各一份数据时P1取出这两份数 仅当缓冲区中有D1和D3采集到的各一份数据时,P2取出这两份数 请用信号量机制实现以上5个进程的同步并保证系统不会发生死锁。 10、(15分)有一批数据共有32000条记录,每条记录的结构如下: 字段 姓名 地址年龄专业类型 字符 字符数字字符长喥(字符) 4-80-10010-20该数据的内容固定不变其用途主要是用于根据姓名来检索其他相关信 息。现把这些数据以文件形式存放在磁盘上该磁盘的粅理块大小为4KB。 请设计存放该批数据的文件的逻辑结构(可以不存储在一个文件中)和物理 结构(在磁盘上的存储结构)使得检索操作能尽可能少访问磁盘。并计算 在该结构下每次检索平均需要访问多少个物理块。(假设文件的目录已经 调人内存文件存放在外存)";
VIP专享文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买VIP专享文档下载特权礼包的其他会员用户可用VIP专享文档下载特权免费下载VIP专享文档。只要带有以下“VIP專享文档”标识的文档便是该类文档
VIP免费文档是特定的一类共享文档,会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档
VIP专享8折文档是特定的一类付费文档,会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档
付费文档是百度文库认证用户/机构上传的专业性文档,需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档
共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档,具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。