《软件技术基础》模拟试题A
一、单项选择题（每小题1分，共20分）
1. 若某线性表的常用操作是插入和删除，则采用（B）存储方式节省时间。
A.顺序表
B.单链表
C.双链表
D.都可以
2. 深度为6（根的层次为1）的二叉树总结点数至多有（B）个。
A.64
B.63
C.31
D.32
3. 将含有100个结点的完全二叉树从根这层开始，每层从左到右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为（A）。
A.23
B.24
C.25
D.无法确定
4. 二分查找要求被查找的表是（C）。
A.键值有序的链表
B.链表 D.顺序表
C.键值有序的顺序表
5. 已知入栈序列为ABC，以下序列（D）是不可能的出栈序列。
A.ABC
B.ACB
C.BCA
D.CAB
6. 队列的对头指针是front，队尾指针式rear，在进行入队操作时，应该将指针修改为（C）。
A. front=front+1 C.rear=rear+1
B.front=front-1 D.rear=rear-1
7. 队列的假溢出现象可以用（B）方法来解决。
A.顺序队列 B.循环队列 C.虚拟队列 D.假队列
8. 若二维数组Amn按行优先存储，元素A00的存放位置是LOC[A00]，每个元素占S个存储单元，则元素Aij的存放地址是（B）
A. (n*i+j)*S
B. LOC[A00]+(n*i+j)*S D. LOC[A00]+(n*(i+1)+j+1)*S
C. LOC[A00]+(n*(i-1)+j-1)*S 9. 树中一个节点的度表示（A）。
A.它拥有子树的数目 C.它的编号值
B.它所在的层次数 D.就是该树的度
10. 完全二叉树和满二叉树的关系是（C）。
A.是完全二叉树就是满二叉树
B.是完全二叉树不是满二叉树
C.是满二叉树一定是完全二叉树 D.是满二叉树不一定是完全二叉树
《软件技术基础》模拟试题A
11. 一棵二叉树的叶子结点数为x，度为2的结点数为y，则x与y的关系是（A）。
A.x=y+1
B.x=y-1
C.y=x+1
D.y=x-1
12. 有n个结点的二叉树，其二叉链表存储结构中空的指针域有（C）个。
A.2n
B.n-1
C.n+1
D.n
13. 二叉树的根为第1层，则第i层的结点数最多为（B）。
A.2i+1
B.2i-1
C.2i+1
D.2i-1
14. 二叉排序树的（B）遍历序列是一个从小到大排列的线性序列。
A.先序
B.中序
C.后序
D.层次
15. 哈希查找又称散列查找，查找过程中，待查找的关键字的存储地址是通过（C）得到的。
A.公式计算 B.顺序比较 C. 哈希函数
D.索引比较
16. 有一组数据为（2,7,5,4,3,1），若采用简单选择排序，则第1趟的执行结果是（D）。
A.2,7,5,4,1,3 C.7,5,4,3,1,2
B. 1,2,7,5,4,3 D.1,7,5,4,3,2
17. 以下（A）不是进程具备的基本特征。
A.交互性
B.动态性
C.并发性
D.独立性
18. 若系统中有五台打印机，有多个进程均需要使用两台，规定每个进程一次仅允许申请一台，则至多允许（C）个进程参与竞争才不会发生死锁。
A.2
B.3
C.4
D.5
19. 有三个节点，分别用它们构造树和二叉树，则可构造出（B）种。
A.3和3
B.2和5
C.2和3
D.3和5
20. 软件需求分析阶段的主要任务是（B）。
A.分析开发软件需要的技术和条件 B.分析软件要做些什么 C.分析软件要怎么做 D.分析软件运行的环境
二、名词解释（每小题4分，共24分） 1. 算法
2. 二叉树
3. 重定位
《软件技术基础》模拟试题A
4. 死锁 5. 虚拟设备 6. 临界资源
答案：1.算法——算法是为解决给定问题的有穷操作步骤的描述。
2.二叉树——是n个节点的有限集合，这个集合可以是空，或者由一个根节点和两个互不相交的左右子树组成。
3.重定位——操作系统在进行存储管理时，将程序执行时要访问的地址空间中的逻辑地址转换成内存空间中对应的物理地址的过程称为重定位。
4.死锁——在多个进程并发执行过程中，采用动态分配资源时，若多个进程彼此互相等待对方所拥有且又不放的资源，结果只能永远等待下去，这样的现象称为死锁。
5.虚拟设备——是指采用SPOOLING技术，将某个独占设备改为供多个用户使用的共享设备。
6.临界资源——以互斥关系使用的共享资源称为临界资源。 三、简答题（共30分）
1. 数据的逻辑结构和存储结构各有哪几种？ （6分）
2. 堆栈和队列各有什么特点？试举例说明它们分别用于何处？ （4分） 3. 写出以下二叉树的先序遍历、中序遍历和后序遍历序列。（6分）
4. 进程是操作系统进行资源分配和调度的基本单位，进程的基本状态有哪些？
这些状态是如何转换的？（7分）
5. 操作系统中常用的内存管理方法有哪些？ （3分）
6. 设备管理的主要任务是控制外设与内存或CPU之间的数据传送。常用的
数据传送控制方式有哪几种？ （3分）
G D H B E A C F K 《软件技术基础》模拟试题A
四、简答题（每小题5分，共30分）
（6分）1.逻辑结构有线性结构和非线性结构。（2分）
存储结构有顺序存储、链式存储、索引存储以及散列存储。（4分） （4分）2.堆栈具有先进后出的特性，如子程序调用时的断点保护。（2分） 队列具备先进先出的特性，比如设备缓冲区以及优先级选择都要用到队列。（2分）
（6分）3.先序：ABDGEHCFK 中序：GDBHEACKF 后序：GDHEBKFCA （7分）4.进程基本状态有就绪，阻塞和执行三种。（3分） 转换过程：（4分，画图也可以） 就绪到执行：进程调度 执行到就绪：时间片完
执行到阻塞：I/O请求或等待事件发生 阻塞到就绪：I/O完成或等待事件已发生
（4分）5.常用的内存管理方法有：分区式、分页式、分段式、段页式。 （3分）6.常用的数据传送控制方式有：中断控制方式、DMA方式、通道方式。
《软件技术基础》模拟试题A
五、算法设计题（共26分）
（6分）1. 假设已有如下单链表head，请写出访问该单链表中所有结点的算法。假设已有结点类型定义： struct node{
int data;
struct node *next;};
（10分）2. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：
①用PV操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值（>0、=0和<0）的含义。
②若欲购票者最多为n个人，写出信号量可能的变化范围（最大值和最小值）？ （10分）3.假设某通信系统中有符号集X包含7个符号：（s1，s2，s3，s4，s5，s6，s7），它们各自出现的概率分别为：（0.31，0.22，0.18，0.14，0.1，0.04，0.01）。试求每个字符的哈夫曼编码。 1. 单链表访问算法： void access(struct node *head) {
struct node *p; p=head;
;初始化1分
;定义1分
while(p->next!=NULL) { p=p->next;