2007年电子科技大学计算机专业基础试题

电子科技大学

2007年攻读硕士学位研究生入学试题

考试科目： 413 计算机专业基础

注意：所有答题必须写在答题纸上，做在试卷或草稿纸上无效。

第一部分 数据结构 （共 75分）

一、单项选择题（每题 2分，共10分）

1．表头表尾均为空表的广义表是（ ）。
① （） ② （（）） ③ （（），（）） ④ （（（）））

2. 对 下列 4个序列,以第一个关键字为基础进行用快速排序算法进行排序，在第一趟过程中移动记录次数最多的是 ( )

① 92，96，100，110，42，35，30，88

② 92，96，88，42，30，35，110，100

③ 100，96，92，35，30，110，88，42

④ 42，30，35，92，100，96，88，110

3． 实现图的广度优先搜索算法时，使用的数据结构是 （ ）

① 栈 ② 队列 ③ 十字链表 ④ 三元组

4．在有向图G的邻接矩阵中，顶点Vi 的度是 （ ）。

① 邻接矩阵中第 i行元素之和

② 邻接矩阵中第 i列元素之和

③ 邻接矩阵中第 i行和第i列元素之和

④ 邻接矩阵中第 i行元素之和与第i列元素之和的最大值

5．能有效缩短关键路径长度的方法是（ ）

① 缩短任意一个活动的持续时间

② 缩短关键路径上任意一个关键活动的持续时间

③ 缩短多条关键路径上共有的任意一个关键活动的持续时间

④ 缩短所有关键路径上共有的任意一个关键活动的持续时间

二、填空题（每空 2分，共 8 分）

1． 由一棵二叉树的后序序列和 可唯一确定这棵二叉树。

2． 二叉树结点数 n与边数e的关系为 。

3． 在各种查找算法中，平均查找长度与关键字个数 n无关的方法是 。

4． 若希望得到树高较矮的生成树，则采用图的 遍历算法。

三、判断题（用√表示对，用×表示错。每题 2分，共 12 分）

1． 循环队列中不存在队列满的问题。（ ）

2． 将一个新结点插入到二叉排序树中，该结点一定成为叶结点。（ ）

3． 用单链表示的有序表可以使用折半查找方法来提高查找速度。（ ）

4． 若有向图中每个顶点的入度和出度均为 1，则该有向图必有回路。（ ）

5． 已知二叉排序树的先序序列，能唯一确定该二叉排序树。（ ）

6． 交换完全二叉树所有结点的左右子树，得到的二叉树仍是完全二叉树。（ ）

四、简答题（每题 6分，共 30 分）

1．若一个有向图的邻接矩阵中主对角线以下的元素均为0，则该图一定不存在回路。该说法是否正确？为什么？

2． 在完全二叉树中，设结点数为 n，

（ 1）如何断定该完全二叉树中度为1的结点数n₁?

（ 2）给定结点x的编号m，又如何根据该编号断定x是否为叶结点？

3． 当查找表有既能较快查找又能适应动态变化的需求时，选用什么查找方法最适合？并简述其理由。

4． 在某个通信系统中，报文的字符集为 a,b,c,d,e,f,g,h八种，其出现频率分别为6，28,8,9,13,22,4和1,试为各字符设计二进制编码，使得报文编码长度最短。给出各字符的二进制编码和报文编码长度。

5． 设 L是不带头结点单链表的头指针，P是指向链表中某个结点的指针，该结点既不是第一个结点，也不是最后一个结点，S是指向待插入新结点的指针，用下面 ① -- ⑦选项完成 A、B功能。

A. 在P所指结点前面插入 S所指结点的语句序列是（ ）；

B. 在第一个结点前面插入 S所指结点的语句序列是（ ）；

① P↑.next ：=S；

② Q:= P；

③ L:= S；

④ P:= L；

⑤ WHILE ( P↑.next <> Q ) DO P：= P↑.next；

⑥ S↑.next：= P↑.next；

⑦ S↑.next：= L↑.next；

五、算法题（共 15 分）

1． 设p,q分别指向两个不带头结点的单循环链表中的某个结点，试编写一个算法，用O(1)时间将这两个单链表合并为一个，并令p指向p和q两者data域值较小的结点。（5分）

PROC xyz( p, q )；

{ p,q分别指向两个不带头结点的单循环链表中的某个结点,结点结构为数据域data和指针域next}

ENDP；

2． 设二叉树采用二叉链表存储，结点结构为 lchild、data和rchild，试编写输出二叉树中从根结点到每个叶结点的路径的算法。设二叉树最长路径结点个数小于m，可以使用队列S[1：m]，初始时S.rear=S.front=1。（10分）

PROC RootToLeaf(bt：bitreptr )；

{ bt为二叉树根指针，S[1：m]为队列, 初始时S.rear=S.front=1}

ENDP；{ RootToLeaf }

第二部分 操作系统 （共 75分）

六、单项选择题（在每小题 2分，共 20 分）

1． 在 UNIX中的索引结点可以看成：（ ）

① 文件目录 ② 文件相关信息说明

③ 设备控制块 ④ 访问的主机对象

2．根据作业说明书中的信息，对作业进行控制, 称此种作业为( )

①计算型作业 ②终端型作业 ③联机作业 ④脱机作业

3．不会产生内部碎片的存储管理（ ）。

① 分页式存储管理 ② 分段式存储管理
③ 固定分区式存储管理 ④ 段页式存储管理

4．空白表中，空白区按其长度由小到大进行查找的算法称为（ ）算法。

① 最佳适应 ② 最差适应 ③ 最先适应 ④ 先进先出

5．为使虚存系统有效地发挥其预期的作用，所运行的程序应具有的特性是（ ）。

① 该程序不应含有过多的I/O操作

② 该程序的大小不应超过实际的内存容量

③ 该程序应具有较好的局部性(Locality)

④ 该程序的指令相关不应过多。

6．快表在计算机系统中是用于（ ）的。

① 存储文件信息 ② 与主存交换信息

③ 地址变换 ④ 存储通道程序

7．在下列文件中，不便于文件增、删操作的是（ ）。

① 索引文件 ② 连续文件 ③ Hash文件 ④ 串联文件

8．在采用SPOOLing技术的系统中，用户的打印数据首先被送到（ ）。

① 磁盘固定区域 ② 内存固定区域 ③ 终端 ④ 打印机

9．如果I/O设备与存储设备间的数据交换不经过CPU来完成，则这种数据交换方式是（ ）

① 程序查询方式 ② 中断方式

③ DMA方式 ④ 无条件存取方式

10．在可变式分区存储管理中的拼接技术可以（ ）。

① 缩短访问周期 ② 增加主存容量

③ 加速地址变换 ④ 使空闲区集中

七、多项选择题（在每小题的五个备选答案中，选出二个至五个正确的答案 ,并将其号码分别填在题干的括号内，多选，少选、错选，均无分。每小题2分，共10分）

1． 采用按序分配资源策略的目的是（ ）

① 预防死锁的方法 ② 占有且等待资源 ③ 非抢夺资源

④ 破坏循环等待资源 ⑤ 互斥使用资源

2．如果系统中有N个进程，则在等待队列中的进程个数可能为（ ）。

① 1 ② N ③ N-1 ④ N-2 ⑤ N+1

3．一个进程被唤醒意味着（ ）。

① 该进程重新占有了CPU ② 它的优先权变为最大
③ 其PCB移到等待队列队首 ④ 进程变为就绪状态

⑤ 进程获得了资源，具备了运行条件

4．当用户程序执行访管指令时，中断装置将使中央处理器（ ）

① 维持在目态 ② 从目态转换到管态

③ 从管态转换到目态 ④ 维持在管态

⑤ 从管态转换到目态执行系统调用

5．采用动态重定位方式装入的作业，在执行中允许（ ）。

① 用户有条件地移动 ② 地址变换

③ 操作系统有条件地移动 ④ 操作系统无条件地移动

⑤ 用户无条件地移动

八、判断并改错题（正确的划上 “√”,错误的划上“╳”,每小题2分,共20分）

1．（ ）在串信通信中引入缓冲区，假设增加一位缓冲区则可以放宽1个单位的中断响应时间，给定8位缓冲则放宽8个单位的中断响应时间。

2．（ ）分页存储管理采用重定位技术实现页式地址变换的。

3．（ ）在页式管理中采用可变分配局部置换能使系统中的物理块得到充分利用，但有可能影响其他进程的运行。

4．（ ）索引顺序文件是按记录键排序的。

5．（ ）设备控制器是CPU与I/O设备之间的接口，它接收从CPU发来的命令，并控制I/O设备工作。

6．（ ）程序链接是讨论程序怎样装入内存的方法。

7．（ ）银行家的算法中的安全检查就是检查系统是否存在安全序列。

8．（ ）在有线程和进程的系统中，CPU的占用是由线程调度和进程调度协调进行的，才能保证CPU的正常执行。

9．（ ）对换空间管理的主要目标是提高进程换入和换出的速度。

10．（ ）多级反馈队列静态调度算法，能较好地满足各种类型用户的需求。

九、简答题 （共 25分）

1．（9分）某系统采用页式存储管理策略拥有逻辑空间32页，每页2K，拥有物理空间1M。写出页的逻辑地址格式。若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？如果物理空间减少一半，页表相应作怎样的改变？

2．（8分）一个多道程序系统,用户空间为100K,有四台打印机;采用在主存的作业不能移动的动态分区方式管理主存。主存空间采用首次适应算法，静态分配打印机，对作业采用计算时间短的作业优先调度算法管理。今有如下所示的作业序列，请分别列出各个作业的开始执行时间、完成时间和周转时间（按十进制计算）。注意：忽略系统开销。

3．（8分）假设一个文件系统基于索引分配策略来管理块，假设每个文件有一个目录项，该目录项可给出文件名字、第一个索引块以及文件的长度。第一个索引块最多依次指向249个文件数据块并且指向下一个索引块。如果文件的当前位置在逻辑块1992处，并且下一个操作将访问逻辑块308，那么必须从磁盘中读取多少个物理块？解释一下您的答案。