山东省2008年普通高等教育专升本统一考试 计算机科学与技术专业综合一试卷
本试卷共10页。满分100分，考试时间180分钟。考试结束后，将本试卷交回。答题前考生务必将自己的姓名、准考证号、座号和所在学校填写在规定的位置。 操作系统原理（50分）
一、单项选择题（10分，每题1分）
1.以下不适合直接存取的外存分配方法是（）
A.连续分配
B.链接分配
C.索引分配
D.都适合 2.下面对进程描述错误的是（）
A.进程是动态的概念
B.进程执行需要处理机 C.进程是有生命期的
D.进程是指令集合
3.在下列文件的物理结构中，不利于文件长度动态增长的文件物理结构是（）
A.连续结构
B.链接结构
C.索引结构
D.Hash结构 4.通道用于实现__________之间信息传输。（）
A.内存与外设
B.CPU与外设
C.外存与外设
D.用户与外设 5.存储管理方案中，___________存储管理可采用交换技术。（）
A.单一连续区
B.可变分区
C.段式
D.请求分页 6.进程调度又称为低级调度，其主要功能是（）
A.选择一个作业调入内存
B.选择一个主存中的进程调出到外存 C.选择一个外存中的进程调入到主存
D.讲一个就绪的进程投入运行
7.设系统中有5个并发进程，共同竞争资源S，且每个进程都需要2个S资源，则该系统最少要有S资源_________个才不会发生死锁。（）
A.11
B.15
C.6
D.无法预计
8.考虑下面的页面访问序列：
5、
6、
5、
2、
6、
3、
5、
3、
2、
5、
1、
3、
5、
3、
1、
3、
6、
1、
5、2假定分配给该进程3个物理块，采用最近最久未使用算法，则出现__________次缺页中断。（提示：所给定的物理块初始均为空，所以，首次访问一页时就会发生缺页中断）。（） A.11
B.9
C.10
D.12 9.设计实时操作系统时，首先应考虑系统的（）
A.可靠性和灵活性
B.实时性和可靠性
C.灵活性和实时性
D.优良性和分配性 10.______选项体现了原语的主要特点。（）
A.并发性
B.异步性
C.共享性
D.不可分割性
二、判断题（正确的打√，错误的打×，每小题1分，共6分） 1.采用多道程序设计能充分发挥CPU与外设并行工作的能力。（）
2.引入设备独立性是为了提高设备分配的灵活性、利用率个方便实现输入/输出重定向。 （）
3.操作系统是对计算机硬件进行管理的软件。（）
4.系统中的某个进程P被唤醒后立即就获得了CPU，这是因为系统采用了抢占调度方式。 （）
5.内存动态分区分配算法中的最佳适应算法要求空闲分区按地址递增的次序排列。（）
三、应用题（24分，每题8分）
1.假定一磁盘有200个磁道，编号为0到199，在完成了磁道135处的请求后，当前正在磁道153处为一个请求服务。若请求队列的先后顺序为： 96，157，101，187，104，160，112，185，140 试分别采用最短寻道时间优先、扫描算法完成上述请求，写出磁头移动的顺序，并计算磁头的磁道移动总量。
2.见下表给出的作业
1、
2、
3、4的到达时间和运行时间，采用短作业和先来先去服务调度算法，试问作业执行顺序和平均周转时间？（时间单位：分钟，以十进制计算） 作业号
到达时间
运行时间
1 0 11
2 4 4
3 10 3
4 12 10
3.系统某时刻出现如下表所示的资源分配情况： 进程
Allocation
Need
Available
P0
2 3 0 0
2 1 0 0
2 2 6 1
P1
4 5 3 1
6 5 3 2
P2
4 1 0 0
6 5 6 0
P3
0 0 0 1
0 5 7 1
P4
2 3 3 0
2 5 6 0
试问：（1）该状态是否安全？为什么？ （2）如果进程P2申请资源（2，2，2，1），系统能否将资源分配给它？为什么？
四、算法题（10分）
某高校一机房面向全校开放，机房有40台计算机供学生上机使用。如果机房有空机位的话，要上机的学生则在登记薄上登记班级、姓名、开始时间，即可上机；如果没有空机位的话，则在门外等候；学生上机结束后，在登记薄上记载上机结束时间后离开。使用P、V操作描述进程的并发过程。
微机原理与接口技术（50分）
五、单项选择题（共10分）
通常所说的32位计算机，是指计算机中的CPU（）
A.有32个控制器
B.共有32个运算器和控制器 C.由32个运算器组成
D.能够同时处理32位二进制数 中断向量是（）
A.中断服务程序入口地址
B.子程序入口地址 C.中断服务程序入口地址的地址
D.中断类型码
计算机的字长越长，一个字所能表示的数据精度就越高，在完成同样精度的运算时，数据处理速度（） A.越慢
B.越快
C.不定
D.无影响
8086CPU的下列寄存器中，不能用作寄存器间接寻址方式时寄存器的是（） A.SI
B.CX
C.DX
D.BX CPU相应中断请求和相应DMA请求的本质区别是（）
A.程序控制
B.中断时CPU仍控制总线，而相应DMA时须让出总线 C.需要CPU干预相应
D.速度快
将三片8259A进行级联后，可以响应____级中断（） A.24级
B.22级
C.16级
D.21级 8086CPU中的通用寄存器是指（）
A.AX、BX、CX、DX
B.BP、SP
C.SI、DI
D.上述三者 当CPU使用中断方式从读取数据时，DAC0809向CPU发出中断请求的信号是 A.START
B.EOC
C.OE
D.INTR 在DMA方式下，外设数据输入内存的路径是（）
A.外设(DMAC(内存
B.外设(CPU(DMAC(内存
C.外设(内存
D.外设(DMAC(CPU (存储器 10. 8255内部B组控制（）
A.PB口和PC口的低4位
B.PA口
C.PB口
D.PB口和PC口
六、填空题（10分，每题1分）
CPU内部数据寄存器用来暂存________________，地址寄存器用于暂存_____________。 已知一个机器数的原码为11100100，则它所对应的真值为_____________、对应的补码为_____________。
8086/8088的3个控制标志是_____________、_____________、____________。 8253进行初始化编程时，先写入_____________字后再写入计数初值。 Intel 8086工作在最大模式时，需要_____________芯片提供控制信号。 某一DRAM芯片，其为512x8位，该芯片需要_________条地址线，_______条数据线。 在8086系统中，规定内存中地址为_______至______的内存单元存放中断向量表。
若采用8255A的PA口输出控制一个七段LED显示器，8255A的PA口对应工作方式_____________。
8237芯片是_____________芯片，它占用_____________个端口地址。 每片8259A芯片可管理_________级中断，占用______个端口地址。
七、判断题（每题1分，共5分；正确答“Y”，错误答“N”） 在计算器中，所有运算最终都是对“0”，“1”的运算，实质是逻辑代数运算。（） 一个指令周期包括若干个总线周期，每个总线周期不一定只包括4个时钟周期。（）
程序计数器用于存放下一条要执行的指令的首地址。80486CPU中等效于程序计数器的寄存器是CS: EIP。（）
在存储器系统中，仅全译码和部分译码方式能实现片选控制。（） 8253-5能产生连续方波输出的工作方式是方式2。（）
八、简答题（15分，每题5分）
什么是微处理器（2分）？简述其具体功能（3分）。 写出寄存器AX、BX、CX、DX、SI的隐含用法。 简述8086中逻辑地址与物理地址的关系。
九、应用题（10分）
若已知加在8253上的外部的计数时钟频率为1MHz，在不增加其他硬件芯片的情况下，欲使8253产生周期为8ms的对称方波，试回答问题： 应选用哪种工作方式？（2分） 计数初值为多少？（3分） 写出初始化程序段（5分）（注：端口地址是40H~43H） 计算机科学与技术专业综合二试卷
本试卷共10页。满分100分，考试时间180分钟。考试结束后，将本试卷交回。答题前考生务必将自己的姓名、准考证号、座号和所在学校填写在规定的位置。 数据结构（50分）
一、单项选择题（10分，每题1分）
1.若一个栈的输入序列为1，2，3，„，n，输出序列的第一个元素是i，则第i个输出元素是（）
A．i-j-1
B.i-j
C.j-i+1
D.不确定的 2.循环队列存储在数组A[0..m]中，则入队的操作为（） A.rear=rear+1
B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m
D.rear=(rear+1)mod(m+1) 3.二维数组A的每个元素是由6个字符组成的串，其行下表i=0，1，„，8，列下表j=1,2，„，10。若A按行序为主序存储，元素A[8][5]的起始地址与当A按列序为主序存储时的元素_________的起始地址相同。（设每个字符占一个字节）（）
A.A[8][5]
B.A[3][10]
C.A[5][8]
D.A[0][9] 4.下面说法不正确的是（）
A.广义表的表头总是一个广义表
B.广义表的表尾总是一个广义表 C.广义表难以用顺序存储结构
D.广义表可以是一个多层次的结构 5.算术表达式A+B*C-D/E转为前缀表达式后为（）
A.-A*C/DE
B.-A+B*CD/E
C.-+ABC/DE
D.-+A*BC/DE 6.有n个叶子的哈夫曼树的结点总数为（） A.不确定
B.2n
C.2n+1
D.2n-1 7.若X是中序线索二叉树中一个有左孩子的结点，且X不为根，则X的前驱为（） A.X的双亲
B.X的右子树中最左的结点 C.X的左子树中最右结点
D.X的左子树中最右叶结点 8.无向图G=（V，E），其中V={a，b，c，d，e，f}，E={{a，b}，{a，e}，{a，c}，{b，e}，{c，f}，{f，d}，{e，d}}，对该图进行广度优先遍历，得到的顶点序列正确的是（） A.a，b，e，c，d，f
B.a，c，f，e，b，d C.a，e，b，c，f，d
D.a，e，d，f，c，b 9.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行_________探测。（）
A.k-1次
B.k次
C.k+1次
D.k（k+1）/2次
10.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是（）
A.直接插入排序
B.快速排序
C.直接选择排序
D.堆排序
二、填空题（5分，每题1分）
1.在有序表A[1..12]中，采用折半查找算法查等于A[12]的元素，所比较的元素下标依次为_____________________________。
2.求图的最小生成树有两种算法，________________ 算法适合于求稀疏图的最小生成树。 3.一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为_____________。 4.在单链表L中，指针p所指结点有后继结点的条件是________________________。 5.一个深度为k，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依次对结点编号，则编号是i的结点所在的层次号是_______________________（跟所在的层次号规定为1层）。
三、判断题（5分，每题1分）
1.链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（）
2.对一棵二叉树进行层次遍历时，应借助于一个栈。（） 3.将一棵树转成二叉树，跟节点没有左子树。（）
4.一个有向图的邻接表和逆邻接表中结点的个数可能不等。（） 5.在待排序数据有序的情况下，快速排序效果好。（）
四、应用题（20分，每题5分）
1.用集合{46，88，45，39，70，58，101，10，66，34}建立一棵二叉排序树，画出该树，并求在等概率情况下的平均查找长度。
2.设一组关键字{9，01，23，14，55，20，84，27}，采用哈希函数：H（key）=key mod 7和二次探测再散列法解决冲突，对该关键字序列构造表长为10的哈希表。 3.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.0
7、0.
19、0.0
2、0.0
6、0.
32、0.0
3、0.
21、0.10，试为这8个数字设计哈夫曼编码。 4.用普里姆算法构造下图的一棵最小生成树，并给出选点顺序。（以①为起点）
五、算法设计题（10分）
编写一个算法来交换单链表中指针P所指接点与其后继结点，HEAD是该链表的头结点，P指向该链表中的某一结点。
