《软件技术基础》复习题
一、填空题（每空1分，共20分）
1、当今计算机基本都以原理为基础，其五大功能部件为；
2、使用汇编语言（或者高级语言）写出的程序称为；将以上程序翻译成机器语言的程序称为；经过翻译转换后能由计算机直接执行的机器指令程序称为；
3、从计算机系统角度来看，Windows XP属于软件；Office 2003属于软件；
4、数据结构是研究的一门学科；它包括三方面的容：、、；
5、数据在存储器中的存储有四种基本的映像方法，它们是：、、、；
6、对于数据的插入、删除等操作，堆栈式结构遵循的原则，而队式结构遵循的原则；
7、设s[1，…，max]为一个顺序结构栈，变量top指示栈顶位置，栈为空的条件是，栈为满的条件是。

8、具有100个结点的完全二叉树的深度为。

9、有n个叶子结点的哈夫曼树中，总结点数是。

10、3个结点可以构成棵不同形态的树。

11、从资源分配的角度看P.V操作，P操作意味着向系统资源，而V操作意味着向系统资源。

12、设某进程的访问页面走向为1，3，1，2，4，页架数为3，按FIFO页面替换算法，当访问到4号页面时，应淘汰号页面。

13、DBMS就是它是位于和之间的一层管理软件。

14、数据独立性又可分为和。

15、现实世界的事物反映到人的头脑中经过思维加工成数据，这一过程要经过三个领域，它们依次是、和。

16、关系代数运算中，专门的关系运算有、和。

17、一个作业从进入系统到运行结束，一般要经历、、、 4种状态。

18、进程的基本状态是、和。

19、存储分配策略分为、和三种。

20、文件的存取方法有和。

二、单项选择题（每题2分，共20分）
1、算法指的是（）
A计算机程序B解决问题的计算方法
C排序方法D解决问题的有限运算序列
2、数据的存储结构包括顺序、、散列和（）4种基本类型
A索引B数组C集合D向量
3、执行下面程序段时，S语句的执行次数为（）。

for(int i=1;i<=n;i++)
for(int j=1,j<=i;j++)
S;
A.n(n-1)/2
B.n(n+1)/2
C.n2/2
D.n
4、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（）。

A.(n+1)/2
B.n/2
C.n
D.n+1
5、一个栈输入序列为1，2，3，4，5，则下列序列中不可能是栈的输出序列是（）。

（A）1 2 3 4 5 （B）5 4 3 2 1 （C）2 3 4 5 1 （D）4 1 2 3 5
6、有64个结点的完全二叉树深度为（）
（A）8 （B）7 （C）6 （D）5
7、在有n个结点的二叉链表中，值为非空的域的个数为（）。

（A）n-1 （B）2n-1 （C）n+1 （D）2n+1
8、在操作系统中P.V操作是一种（）。

（A）机器指令（B）系统调用命令
（C）作业控制命令（D）低级进程通信原语
9、把作业地址空间中的逻辑地址变为存中物理地址称为（）。

（A）加载（B）重定位（C）物理化（D）逻辑化10、文件系统使用（）组织文件。

（A）堆栈（B）指针（C）目录（D）路径
11、在操作系统中死锁的出现是因为（）。

(A)计算机系统发生重大故障
(B)资源数目远远少于进程数
(C)若干进程因竞争资源无限等待其他进程释放已占有的资源
(D)进程同时申请的资源数超过资源总数
12、操作系统中，当（），进程从执行状态转变为就绪状态。

（A）进程被进程调度程序选中（B）时间片完
（C）等待某一事件（D）等待的事件发生
13、（）是存储在计算机中有结构的数据的集合。

（A）数据库系统（B）数据库
（C）数据库管理系统（D）数据结构
14、数据库的核心是（）。

（A）数据库（B）数据库管理系统
（C）数据模型（D）软件工具
15、数据库（DB）,数据管理系统（DBS）和数据库管理系统（DBMS）三者之间的关系是（）。

（A）DBS包括DB、DBMS （B）DBMS包括DB、DBS
（C）DB包括DBS、DBMS （D）DBS就是DB也就是DBMS 16、在一个顺序循环队列中，队首指针指向队首元素的（）位置。

A前一个B后一个C当前D最后
17、在一棵具有n个结点的二叉树的第i层上，最多具有（）个结点。

A.2i
B.2i+1
C.2i-1
D.2n
18、利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（）。

A.55
B.29
C.58
D.38
19、对于顺序存储的有序表（5，12，20，26，37，42，46，50，64），若采用二分查找，则查找元素26的查找长度为（）。

A.2
B.3
C.4
D.5
20、关系数据模型（）。

（A）只能表示实体间1：1联系（B）只能表示实体间1：m联系
（C）只能表示实体间1：n联系（D）可以表示实体间上述三种联系
三、应用分析题（6题，共60分）
1、在一棵二叉树如图1.11所示。

写出对此树进行先序，中序，后序遍历时得到的结点序列。

图 1.11
答案：
2、设散列函数为H(K)=k mod 7，散列表地址空间为0～8，开始时散列表为空，用线性探测法解决冲突，请画出依次插入关键字值为100，20，21，35，3，78，99，45后的散列表，并求出在等概率下的平均查找长度。

答案：
3、有一组关键字序列为(38，19，65，13，97，49，41，95，1，73)，采用冒泡排序方法有小到大进行排序，请写出每趟结果。

答案：
4、将图1.12所示的树转换成二叉树。

图 1.12
答案：
5、对于如图1.15所示的有向图，请给出对应的邻接矩阵，并给出A ，B ，C 三
个顶点的出度与入度。

3
1
A 543
146
4图 1.14
67
8
650
1
12
24
2083812
图 1.15
答案：
6、假设图的顶点是A 、B 、C 、D ，请根据下述邻接矩阵判断并画出相应的有向图和无向图。

（1）
0 1 1 1 （2） 0 1 1 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 1 0 0 0 1 1 1 1 0 0 1 0 1 0
答案：
7、对长度为11有序集，进行折半查找，试画出它的一棵判定树，并求在等概率情况下的平均查找长度。

答案：
8、假定一个线性表为（38，52，25，74，68，16，30，54，90，72）画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。

答案：
9、进程和程序有什么区别和联系？
答案：
10、简述页式存储管理体制中逻辑地址到物理地址的转换过程？
答案：。