《软件技术基础》课程自测题一
一、单项选择题（每题2分，共40分）
● 采用二元描述法可描述任意数据结构为（K ，R ），其中K 和R 分别代表（C ）的集合
A 算法和操作 B 逻辑结构和存储结构 C 数据元素和关系 D 结构和算法 ● 计算机算法指的是（C ）
A 计算方法 B 程序 C 解决问题的方法和步骤 D 调度方法
● 一个栈的元素进栈顺序是1、2、3、4、5，则出栈顺序不可能是（C ）
A 1、2、3、4、5 B 2、3、1、5、4 C 4、3、5、1、2 D 4、5、3、2、1 ● 一个队列的入队序列是1、2、3、4，则队列的输出顺序为（B ）
A 4、3、2、1 B 1、2、3、4 C 1、2、4、3 D 2、1、3、4
● 在链接式队列中删除结点时，执行的操作为（B ）
A rear = front->next B front = front->next C front = rear->next D rear = rear->next ● 如图所示的二叉树中，（C ）不是完全二叉树
● 具有4个结点的二叉树的形状有（A ）种。
A 16 B 5 C 80 D 20
● 一个有n 个顶点的无向图最多有（D ）条边
A n－1 B n＋1 C n（n ＋1）/2 D n（n －1）/2
● 线性表必须先（C ）后，才能对线性表进行折半检索。
A 元素连续存放 B 元素链接式存放 C 元素按关键值大小排列 D 元素按存放地址高低排列
● 从未排序子表中依次取出元素放入到已排序子表的正确位置上的方法是（D ）
A 简单选择排序 B 快速排序C 冒泡排序 D 简单插入排序
● 一个计算机系统由（D ）组成
A CPU、存储器 B CPU和外设 C 操作系统和用户程序 D 硬件和软件 ● 在SPOOLing 技术中，系统实际上将（B ）分配给用户进程
A 设备的信号量 B 磁盘上的一块区域，即虚拟设备 C 设备的一段使用时间 D 设备的缓冲区
● 分页式存储管理是基于（D ）实现的。
A 固定分区 B 动态分区 C 静态重定位 D 动态重定位
● 进程的状态转换不可以是（A ）
A 从阻塞态到执行态 B 从执行态到阻塞态 C 从阻塞态到结束态 D 从阻塞态到就绪态 ● 原语是一段程序，它和普通程序本质不同在于（B ）
A 原语提供系统服务 B 原语具有不可中断性 C 原语程序很短 D 原语执行不同的指令集 ● 假设有5个进程J1～J5同时到达系统，它们的运行时间为10，6，2，4和8分钟，它们的优先级分别为3，5，2，1和4（5为最低优先级），若采用优先级调度算法，假设进程是依次执行完毕的，则平均周转时间为（C ）
A 20分钟 B 6分钟 C 16分钟 D 10分钟
● 虚拟设备技术是一种（D ）
A 把共享设备改为某作业的独占设备，集中完成I/O请求B 把I/O请求交给多个物理设备分散完成 C 把I/O信息先放在外存，然后由一台物理设备分批完成 D 利用外存作为缓冲，将作业与外存交换信息和外存与物理设备交换信息两者独立起来，并使它们并行工作 ● 系统总是选择（A ）状态的进程占用处理器
A 就绪B 等待 C 阻塞 D 挂起
● 存储管理的目的是（B ）
A 方便用户 B 提高内存利用率 C 扩充内存实际容量 D 减少系统开销
● 文件的物理结构通常有以下几种（B ）
A 记录式文件、流式文件 B 连续文件、链接文件 C 顺序存取文件、随机存取文件 D 可读文件、可写文件
二、判断题（每题1分，共10分）
（T ）二维数组可以看作是数据元素为线性表的线性表。
（F ）若某二叉树的先序遍历和中序遍历序列相同，则此二叉树一定有且仅有一个结点 （F ）顺序存储方式只能用于存储线性结构
（T ）如果已知二叉树先序遍历和中序遍历序列，可以得到该二叉树的后序遍历顺序。 （T ）一个元素集合形成的二叉排序树不是唯一的，但根据一个元素序列形成的二叉排序树是唯一的。
（F ）无论采用哪种存储管理方式，程序的逻辑地址均是连续的。
（F ）程序是计算机操作系统中能独立运行的基本单位。
（T ）利用信号量机制不能预防死锁的发生。
（T ）OS 的设计必须要保证进程的执行结果具有可再现性。
（T ）通道是特殊的处理机，能够与CPU 并行工作以提高效率。
三、填空题（每题1分，共15分）
● 利用二维数组a 存放元素，设元素个数为M ，分为I 行和J 列，每个元素占8字节空间，
则共需要 8M 字节，第4行和第5列的元素加起来占用 （I ＋J －1）×8 字节空间，如果按照行优先存放，元素a 34存放位置与按照列优先存放的元素的行号和列号分别为 （2×J ＋4）%I、 （2×J ＋4）/I＋1 存放位置相同。
● 在双链表中，每个节点具有个指针。
● 分块查找算法中，块间元素的排列是的。 ● 存储管理应实现的功能是：主存空间的共享和
保护， 虚拟存储管理
● 分时系统追求的目标是 人机交互 ，实时系统追求的目标是 即时响应
● 在操作系统中，可以利用
方式在进程间传递大量数据
● 分页式存储管理中，页表是用来指出 ● 从人机交互方式来看，操作系统是用户与计算机之间的
四、简答与简单应用题（共20分）
● 简述下列术语：树结点的度、树的度、图顶点的度，如果把树看作是有向图，则树结点
的度是否等于图顶点的度？
答：树结点的度指结点子树的数量，树的度是树上各结点度的最大值，无向图中顶点的度是该顶点边的数量，有向图顶点的度是以该顶点为弧头（入度）和以该顶点为弧尾（出度）的弧的总和。如果将树看作是有向图，则树结点的度仅仅是出度。
● 已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组
a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。
答：
● 请画出分页存储管理方式下的地址变换结构并简要描述其过程
答：
地址变换过程如下：
1）将程序的逻辑地址形成有效地址，页号＋页内地址形式
2）根据页表始址和页号找到页表并查询页表相应表项；
3）得到物理块号，将块号放入物理地址寄存器；
4）将页内地址作为块内地址填入物理地址寄存器
5）根据块号和块内地址访问内存
● 什么是死锁，死锁产生的原因和必要条件有哪些？
答：当两个或两个以上进程因竞争资源而无休止地处于相互等待状态，称为死锁。死锁是由于多个进程竞争资源，系统资源不够，且进程推进顺序不当而引起。产生死锁的必要条件有：互斥条件、不剥夺条件、部分分配条件和环路条件，死锁产生缺一不可。
解决死锁的办法有哪些？（请简要描述这些方法的基本原理）
答：有死锁的预防，通过破坏死锁产生的四个必要条件的一个或几个，具体有资源静态分配、按序分配、剥夺资源和进程一次申请所有的资源等方法；避免死锁，在系统运行过程中，尽力避免进入不安全状态，即将导致死锁的状态；检测死锁和解除，系统不断检测当前是否出现死锁，然后以一定方法解除进程间的死锁，如撤销进程或剥夺资源。
● 请简要描述几个常用的页面置换（淘汰）算法基本原理
答：常见的页面淘汰算法有：FIFO 算法、LRU 算法和LFU 算法。
FIFO 算法：选择进程当前页面中最先进入内存的页面淘汰
LRU 算法：选择进程当前页面中最近一段时间最久没有使用过的页面
LFU 算法：选择进程当前页面中最近一段时间使用频率最小的页面
五、应用题（共15分）
● 已知一棵二叉树的中序和先序序列如下，
中序序列：c ，b ，d ，e ，a ，g ，I ，h ，j ，f
先序序列：a ，b ，c ，d ，e ，f ，g ，h ，I ，j
（1）求该二叉树的后序遍历序列，
（2）试构造该二叉树。
答：
本题先构造二叉树，再完成后序遍历更容易
后序遍历：c ，e ，d ，b ，I ，j ，h ，g ，f ，a
● 下面是用C 语言写的单链表直接选择排序算法，排序的结果是单链表按关键字值升序
排列。算法中有若干处语句和判断条件空缺，请在空缺处填上适当的语句或条件。（提示：该算法的基本思想是，每次从链表p 中找出最大的元素，从链表取下元素，放在新链表t 的第一个位置，如此反复，t 链表就成为一个升序排列的链表）
typedef struct node{
int key;
struct node *next;
}node;
node *selectsort(node *head){
node *p，*q，*r，*s，*t;
t=NULL;
while(head!=NULL){
p=head;
q=NULL;
s=head;
r=NULL;
while(p!=NULL){
;
; }
q=p;
p=p->next;
}
if(s= =head) head=head->next;
else
s->next=t;
t=s;
}
head=t;
return(head);
}
答：
p->key > s->key
s = p
r = q
r->next = s->next