《软件技术基础》模拟试题 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.键值有序的链表 C.键值有序的顺序表 B.链表 D.顺序表 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 C. LOC[A00]+(n*(i-1)+j-1)*S D. LOC[A00]+(n*(i+1)+j+1)*S 9. 树中一个节点的度表示（a）。 A.它拥有子树的数目 B.它所在的层次数 C.它的编号值 D.就是该树的度 10. 完全二叉树和满二叉树的关系是（c）。 A.是完全二叉树就是满二叉树 B.是完全二叉树不是满二叉树 C.是满二叉树一定是完全二叉树 D.是满二叉树不一定是完全二叉树 11. 一棵二叉树的叶子结点数为 x，度为 2 的结点数为 y，则 x 与 y 的关系是（a）。 

《软件技术基础》模拟试题 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. 二叉树 (是 n 个节点的有限集合，这个集合可以是空，或者由一个根节点和两个互不 相交的左右子树组成。) 

《软件技术基础》模拟试题 A 3. 重定位(操作系统在进行存储管理时，将程序执行时要访问的地址空间中的逻辑地址转换 成内存空间中对应的物理地址的过程称为重定位。 ) 4. 死锁 (在多个进程并发执行过程中，采用动态分配资源时，若多个进程彼此互相等待对 方所拥有且又不放的资源，结果只能永远等待下去，这样的现象称为死锁。) 5. 虚拟设备(是指采用 SPOOLING 技术，将某个独占设备改为供多个用户使用的共享设备。) 6. 临界资源(以互斥关系使用的共享资源称为临界资源。) 三、 简答题（共 30 分） 1. 数据的逻辑结构和存储结构各有哪几种？ （6 分） 2. 堆栈和队列各有什么特点？试举例说明它们分别用于何处？ （4 分） 3. 写出以下二叉树的先序遍历、中序遍历和后序遍历序列。（6 分） A E B H C K F D G 4. 进程是操作系统进行资源分配和调度的基本单位，进程的基本状态有哪些？这些状态是 如何转换的？（7 分） 5. 操作系统中常用的内存管理方法有哪些？ （3 分） 6. 设备管理的主要任务是控制外设与内存或 CPU 之间的数据传送。常用的数据传送控制方 式有哪几种？ （3 分） 四、 算法设计题（共 26 分） （6 分）1. 假设已有如下单链表 head，请写出访问该单链表中所有结点的算法。假设已有 结点类型定义： struct node{ int data; struct node *next;}; 

《软件技术基础》模拟试题 A （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）。试求每个字符的 哈夫曼编码。