甘肃政法学院2010年专升本计算机科学与技术.doc

甘肃政法学院2010年专升本招生考试计算机科学与技术专业综合试卷A注意事项：1、答题前，考生务必将自己的姓名、准考证号填写在答题卡、答题纸上。2、单项选择题（操作系统部分和数据结构部分）选择一个正确答案，并将其代码涂在答题卡上，答在试卷上不给分。3、其它答案用钢笔或圆珠笔写在答题纸上，答在试卷上不给分。4、考试结束，将试卷、答题卡和答题纸一并交回。操作系统部分（共100分）一、单项选择题（每小题2分，共50分）1、计算机系统中，最靠近硬件层次的一类软件是（ ）。A.应用软件 B.支撑软件 C.系统软件 D.编译程序2、下列操作系统中，是分时系统的是（ ）。A.CP/M B.MSDOS C.UNIX D.Windows NT3、可执行特权指令的程序是（ ）。A.同组用户 B.操作系统 C.特权用户 D.一般用户4、工业过程控制系统中运行的操作系统最好是（ ）。A.分时系统 B.实时系统 C.分布式操作系统 D.网络操作系统5、进程被创建后即进入（ ）队列。A.阻塞队列 B.就绪队列 C.缓冲队列 D.运行队列6、多道系统环境下，操作系统分配资源的基本单位是（ ）。A.作业 B.指令 C.程序 D.进程7、PCB是指（ ）。A.中断源 B.就绪队列 C.等待队列 D.进程控制块8、等待的资源得到满足时，进程状态变化为（ ）。A.运行态就绪态 B.等待态就绪态 C.等待态运行态 D.就绪态运行态9、采用多线程技术的操作系统，调度、执行的单位是（ ）。A.线程 B.进程 C.程序 D.以上都不对10、下列存储管理方式中，相比而言，碎片最少，而且主存利用率最高的是（ ）。A.固定分区 B.可变分区 C.单用户连续存储管理 D.页式11、单道系统中经常采用的存储管理方式是（ ）存储管理。A.固定分区 B.单用户连续 C.可变分区 D.页式12、下列管理方式中，能实现虚拟存储器的是（ ）。A.单用户连续方式 B.页式存储管理 C.固定分区 D.可变分区13、虚拟存储器管理中，发现所要访问的信息不在主存时，发出的信号是（ ）。A.缺页中断 B.访管中断 C.硬件故障中断 D.时间中断14、文件系统是指（ ）。A.文件的集合 B.文件的目录 C.实现文件管理的一组软件 D.管理文件的软件及数据结构的总体15、主存与外存进行信息交换的物理单位是（ ）。A.数据项 B.卷 C.字节 D.块16、记录是一个有特定意义的信息单位，它是由（ ）组成。A.字 B.字节 C.数据项 D.物理块17、操作系统对文件进行编排、增删、维护和检索是通过（ ）。A.按名存取 B.数据逻辑地址 C.数据物理地址 D.文件属性18、CPU对通道的请求形式是（ ）。A.自陷 B.中断 C.通道命令 D.转移指令19、采用SPOOLING系统后，可以（ ）。A.有效提高共享设备的利用率 B.加快作业执行速度 C.极大缩短作业的周转时间 D.降低I/O操作的出错可能性20、设备管理是按（ ）来启动该设备进行工作的。A.设备号 B.设备类名 C.设备的绝对号 D.设备的相对号21、（ ）是在两种不同速度的设备之间传输信息时平滑传输过程的常用手段。A.中断技术 B.SPOOLING技术 C.通道技术 D.缓冲技术22、进程的执行结果与它的执行速度无关，而只与初始条件有关，这是指进程的（ ）。A.顺序性 B.可再现性 C.封闭性 D.封锁性23、对于临界区（ ）。A.必须同步执行 B.不一定互斥执行 C.必须互斥执行 D.应该共同协调执行24、通道是一种（ ）。A.I/O设备 B.设备控制器 C.I/O处理机 D.I/O控制器25、（ ）是只能由P和V操作所改变的整型变量。A.共享变量 B.锁 C.整型信号量 D.记录型信号量二、填空题（每空2分，共20分）1、计算机系统的资源包括 和 。2、一般情况下，用户程序启动后运行在 下。3、引起中断的事件称为 ，对出现的中断进行处理的程序称为 。4、分页式存储管理器的逻辑地址由两部分组成： 和 。5、逻辑文件有 和 两种形式。6、死锁的检测是为了 。三、简答题（每题5分，共20分）1、从资源管理的观点来看，操作系统有哪些基本功能？2、什么叫虚拟设备？3、简述中断处理过程。4、死锁发生的必要条件有哪些？四、计算题（共6分）假定某采用分页式虚拟存储系统中，主存容量为1M，被分为256块，块号为0，1，2，255。某作业的地址空间占4页，页号为0，1，2，3，被分配到主存的第2，4，1，5块中。回答：（1）主存地址应该用 位来表示。（1分）（2）作业每一页的长度 ；逻辑地址中的页内地址（单元号）应占用 位。（2分）（3）把作业中每一页分到的主存块中的起始地址填入下表：（3分）逻辑页号起始地址0123五、应用题（共4分）如果一个生产者和一个消费者他们共享的缓冲器（B）容量为可以存放n件物品，信号量empty表示缓冲器中可存放多少件物品，信号量full表示缓冲器中存有几件物品，初值为empty=n，full=0；整型变量k，t，初值k=t=0。那么一个生产者和一个消费者同步进行工作可以描述如下：生产者进程： begin L1:produce a product; ; Bk:=product; k:=(k+1)mod n; ; go to L1 end消费者进程： begin L2:Bt take a product from ; t:=(t+1) mod n; ; consume; go to L2 end请在上述程序的填空处填上适当的操作，以保证它们能够正确地并发执行。数据结构部分（共100分）六.单项选择题(每小题2分，共50分)26、数据元素是数据的基本单位，其内（ ）数据项。A.只能包括一个 B.不包含 C.可以包含多个 D.可以包含也可以不包含27、每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ ）存储方式。A.顺序 B.链式 C.索引 D.散列28、设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为 。A. q=p-next；p-data=q-data；p-next=q-next；free(q)；B. q=p-next；q-data=p-data；p-next=q-next；free(q)；C. q=p-next；p-next=q-next；free(q)；D. q=p-next；p-data=q-data；free(q)；29、判定一个循环队列Q（最多元素为m0）为满的条件是_。A.Q.front= =Q. Rear B. Q.front!= Q.rearC.Q.front= =(Q.rear+1) % m0 D. Q.front!=(Q.rear +1) % m030、顺序表的一个存储结点仅仅存储线性表的一个（ ）。A.数据元素 B.数据项 C.数据 D.数据结构31、线性表L=(a, b, c, d, e)，经运算Delete(L, 3)后，L表等于（ ）。A. (a, b, d, e) B. (a, b, c, d) C. (b, c, d, e) D. (d, e)32、在双向链表的一个结点中有（ ）个指针。A.1 B.2 C.0 D.333、4个元素按A、B、C、D顺序连续进S栈，进行Pop(S, x)运算后，x的值是（ ）。A.A B.B C.C D.D34、如图所示的棵二叉树中，_不是完全二叉树。A. B. C. D.35、下面程序的时间复杂度为_。 for(i=0;im:i+) for(j=0;jC. 1，2 ) D. 42、有n个顶点的无向图的邻接矩阵是用（ ）数组存储。A. n行n列 B.一维 C.任意行n列 D. n行任意列43、在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的（ ）。A.先根遍历 B.中根遍历 C.后根遍历 D.按层次遍历44、存放在内存中的数据的组织结构是（ ）。A.数组 B.表 C.文件 D.链表45、顺序查找法适合于（ ）存储结构的查找表。A.压缩 B.散列 C.索引 D.顺序或链式46、设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找键值为20的结点时，经（ ）次比较后查找不成功。A.2 B.3 C.4 D.1247、索引顺序表仅包含（ ）。A.顺序表 B.索引表C.顺序表和索引表 D.索引48、文件是由（ ）组成。A.结点 B.数据项 C.记录 D.物理记录49、直接插入排序的方法是从第（ ）个元素开始，插入前边适当位置的排序方法。A.1 B.2 C.3 D. n50、冒泡排序的方法要求被排序的数据（ ）存储。A.最好是顺序 B.最好是链表 C.顺序或链表 D.二叉树七、填空题（每空2分，共20分）1、 与数据元素本身的内容和形式无关。2、树结构是用来描述 问题的结构。3、有向图的边也称为 。4、在 中存储数据的结构称为表。5、用来标识数据元素的数据项称为 。6、静态查找表包括 、 、 三种基本运算。7、磁盘上的一个存储单位由 、 和扇区三个参数确定。八简答题（共24分）1、写出栈和队列的区别与共同点。（6分）2、已知序列15,18,60,41,6,32,83,75,95。请给出采用冒泡排序法对该序列作升序排序时的每一趟的结果。（10分）3、已知链表的结构如下：（8分） A B CS P(1)写出