软件技术基础复习题

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

2、p指示栈顶位置，栈为空的条件是 ，栈为满的条件是 。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、关系代数运算

3、中，专门的关系运算有 、 和 。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

4、.n2/2 D.n4、在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。A.(n+1)/2 B.n/2 C.n D.n+15、一个栈输入序列为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 56、有64个结点的完全二叉树深度为（ ）（A）8 （B）7 （C）6 （D）57、在有n个结点的二叉链表中，值为非空的域的个数为（ ）。（A）n-1 （B）2n-1 （C）n+1 （D）2n+18、在操作系统中P.V操作是一种（ ）。（A）机器指令 （B）系统

5、调用命令（C）作业控制命令 （D）低级进程通信原语9、把作业地址空间中的逻辑地址变为内存中物理地址称为（ ）。（A）加载 （B）重定位 （C）物理化 （D）逻辑化10、文件系统使用（ ）组织文件。（A）堆栈 （B）指针 （C）目录 （D）路径11、在操作系统中死锁的出现是因为（ ）。(A)计算机系统发生重大故障(B)资源数目远远少于进程数(C)若干进程因竞争资源无限等待其他进程释放已占有的资源(D)进程同时申请的资源数超过资源总数12、操作系统中，当（ ），进程从执行状态转变为就绪状态。（A）进程被进程调度程序选中 （B）时间片完（C）等待某一事件 （D）等待的事件发生13、（ ）是存储在计算

6、机中有结构的数据的集合。（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也就是DBMS16、在一个顺序循环队列中，队首指针指向队首元素的（ ）位置。A前一个 B后一个 C当前 D最后17、在一棵具有n个结点的二叉树的第i层上，最多具有（ ）个结点。A.2i B.2i+1 C.2

7、i-1 D.2n18、利用3，6，8，12这4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长度为（ ）。A.55 B.29 C.58 D.3819、对于顺序存储的有序表（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所示。写出对此树进行先序，中序，后序遍历时得到的结点序列。答案： 2、设

8、散列函数为H(K)=k mod 7，散列表地址空间为08，开始时散列表为空，用线性探测法解决冲突，请画出依次插入关键字值为100，20，21，35，3，78，99，45后的散列表，并求出在等概率下的平均查找长度。答案：3、有一组关键字序列为(38，19，65，13，97，49，41，95，1，73)，采用冒泡排序方法有小到大进行排序，请写出每趟结果。答案：4、将图1.12所示的树转换成二叉树。答案： 5、对于如图1.15所示的有向图，请给出对应的邻接矩阵，并给出A，B，C三个顶点的出度与入度。答案：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有序集，进行折半查找，试画出它的一棵判定树，并求在等概率情况下的平均查找长度