计算机软件技术基础课程练习题

1、百度文库计算机软件技术基础课程学习练习题赵俊生编内蒙古工业大学信息工程少2011-3-1目录/2计算机软件技术基础练习题（一）2计算机软件技术基础练习题（二）10计算机软件技术基础练习题（三）17计算机软件技术基础练习题（四）21计算机软件技术基础练习题（二）参考答案25计算机软件技术基础练习题（三）参考答案28计算机软件技术基础练习题（四）参考答案32计算机软件技术基础练习题（一）、填空题（请在每个题目中的横线上填上准确的内容。）1 .衡量算法的优劣，通常用计算机执行时的时间和空间资源的消耗多少作为评价标准。2 .空间复杂度是以在算法中所需的辅助空间单元的多少来衡量的。3 .线性表有两种存储

2、结构，分别是向量'和链表。4 .线性表的结构特点是：数据元素之间是线性关系，在表中除第一个元素外，每个元素有且只有一个前趋元素；除最后一个元素外，每个元素有且只有一个后继元素。5 .用一组地址_连续的存储单元存放线性表的数据元素，、称为线性表的顺序存储结构。6 .在线性表的链式存储结构中，每一个数据元素由两个域组成，一个是存放元素值的数据域,另一个是存放后继元素存储地址的指针域。7 .在栈中，允许插入或删除的一端称为栈顶，另一端称为栈底(bottom)。8 .在树结构中，度为零的结点称为叶子结点,又称端结点。9 .二叉树的第i层上至多有2i-1个结点。10 .哈夫曼树又称最优树，是一类

3、带权路径最短的树。11 .计算机硬件部分包括处理机、存储器、输入输出设备和各种通信设备。12 .“批处理”是指用户与作业之间没有交互作用，用户不能直接控制作业的运行。13 .分时系统是指多个用户共享同一台计算机,系统将CPU的时间片轮流分配给多个用户。14 .处理机管理主要解决CPU的分配策略、实施方法以及资源的分配和回收问题。15 .文件管理的基本功能是实现对文件的存取和检索,为用户提供方便灵活的操作命令以及实现文件共享、安全、保密等措施。16 .虚拟是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。17 .当目标程序装入主存后占用的一系列物理单元的集合，称为/"存储空间。1

4、8 .可重定位分区分配是在可变分区分配基础上增加内在紧缩功能形成的。19 .常用的两种页面置换算法为先进先出法和最近最少使用法。20 .进程的三种基本状态有就绪状态、执行状态和阻塞状态。21 .顺序程序执行的特点有顺序性、_封闭性和可再现性。22 .设备分配算法有先请求先服务和优先数两种23 .常见的文件物理结构有顺序结构、2链接结构和索引结构三种。24 .可行性研究主要集中在经济可行性和'岐术可行性两个方面。25 .软件工程的基本原则包括划分软件生命期、进行计划评审和编制软件文档26 .软件维护主要包括改正性维护、适应性维护和完善性维护三个方面。27 .软件测试有黑盒测试和白盒测试两

5、类方法。28 .数据处理问题的两种类型有变换型和事务处理型。29 .软件开发人员的组织原则有尽早落实责任和减少接口。30/软件开发小组内部人员的组织形式主要有民主制和主程序员制两种。二、单项选择题(请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括弧中，多填不得分。)1 .以下程序段的时间复杂度为(C)。fori=1tonforj=1tonfork=1tonxx+1end(k)end(j)end(i)(A)qn)(B)Qnj(C)Qn3)(D)Q3n)2 .在数据结构中，从逻辑上可以把数据结构分成(C)。(B)内部结构和外部结构(D)紧凑结构和非紧凑结构A )。(B)具体执行时间(

6、D正确性B )。/(A)动态结构和静态结构(C)线性结构和非线性结构3 .时间复杂度可以评估一个算法的(A)时间增长趋势(C)复杂程度4 .以下对线性表的描述，正确的是(A)向量的存储空间是动态分配的(B)线性链表只能顺序存取(C)栈是先进先出的线性表(D)队是先进后出的线性表115 .在单链表中，在p指针之后插入一个s指针所指的结点，则需执行（(A)next(s) next(p);next(p) s(B)next(p) s; next(s) next(p)(C)next(p) next(s); next(p) s(D)next(s) next(p); s next(p)6 .有一颗具有n个结

7、点的k叉树，则有nk个指针域，其中有用的指针域为个。(A) n(B) nk-1(C) n-17.以下二叉树的带权路径长度为（A ）。(D) nk8.9.(A) 44(B)A )。下图的深度优先遍历序列正确的是(A) V2Vi-M一V5一V4V6(B)7广 Vi-V5V6 V4表长为n的线性表，在等概率情况下，线性查找的平均查找长度为（(C)(A) n/2(B) (n-1)/2(C) (n+1)/2(D) n10 .对有序表（18,20,25,34,48,62,74,85）用对分查找法查找74,查找成功时所需的比较次数为(B)次(A) 2(B) 3(C) 4(D) 511 .一组记录的关键字为3

8、,8,5,9,7,6,2小则利用冒泡排序的方法，经过第次扫描得到的排序结果为(A)0(A) 3,5,8,7,6,2,9(B) 3,8,5,7,6,2,9(C) 3,5,6,7,8,2,9(D) 2,3,5,8,7,6,9(B)作业(D)进程13 .允许多个用户以交互方式使用计算机的操作系统称为( A )0(A)分时操作系统(C)批处理操作系统14 .批处理系统的主要缺点是(A) CPURJ用率低(C)缺少交互性(B)实时操作系统(D)多处理机操作系统C )。(B)不能并发执行(D)以上都不是15 .下列哪个选项不是操作系统关心的问题( D )。(A)管理计算机裸机(B)设计、提供用户程序与计算

9、机硬件系(C)管理计算机系统资源16 .最佳适应算法的空闲块是(C(A)按大小递减顺序连在一起(C)按大小递增顺序连在一起(D)(B)(D)统的界面高级程序设计语言的编译器按地址由小到大排列按地址由大到小排列17 .软件测试的目标是(A(A)找出错误(C)得出结果18 .以下哪项不是软件测试的步骤(A)单元测试(C)组装测试19 .为保证软件开发的质量,(A)技术审查(C)测试(B)(D)(B)(D)验证计划提高效率流程测试 确认测试般不采取的措施是(D )。 (B)管理复审(D)监督12 .操作系统的主要功能是管理计算机系统中的(C)。(A)程序和数据(C)资源20.结构化分析方法不包括(C

10、)(A)数据流图(B)数据词典(C)编写代码(D)'结构化语言、判断题(请判断每个题干是否正确，正确在括弧中打，错误在括弧中打X。)1. (X)线性表的长度是指线性表所占的存储空间的大小。2. (X)线性表就是顺序表。3. (，)栈和队是运算受限制的线性表。4. (Vz)若一棵树中某结点的度为1,则该结点仅有一棵子树。5. (X)在执行排序算法中，出现了排序的关键字朝着和最终排序序列位置相反的方向移动，则该算法是不稳定的。'6. (，)快速排序中，以待排序的n个记录中的第1个记录的关键字值为基准，将所有记录分为两组，该记录就在这两组中间，这也是该记录的最终位置。7. (V)原语

11、在执行时是不能中断的。8. (x)程序并发执行是指同一时刻有两个以上的程序指令在同一处理器上执行。9. (x)缓冲技术是借用一部分外存储器区域作为缓冲池。10. (V)P.V操作可实现进程的同步和共享资源的互斥使用，但不能排除死锁。四、问答题(请按照题目要求回答问题。)1 .一棵二叉树其中序和后序遍历为：中序：BDCEAFHG后序：DECBHGFA画出这棵二叉树的逻辑结构，并写出先序遍历结果答：逻辑结构为：先序遍历为：ABCDEFGH2 .设一棵完全二叉树有,20个结点，试问：a)有多少个叶子结点；b)有多少个度为2的结点；c)有多少个结点只有非空左子树答：(1)有10个叶子结点(2)有9个度

12、为2的结点(3)有1个结点只有非空左子树3 .给定一组元素17,28,36,54,30,27,94,15,21,83,40,画出由此生成的二叉排序树。4 .给定一组权值W=8,2,5,3,2,17,4,画出由此生成的哈夫曼树5 .请说明分页管理的优缺点是什么？/答：优点是：不要求作业在内存中连续存放，较好的解决了碎片问题。作业地址空间不受内存的限制，为用户提供足够大的存储空间，更有利于多道程序作业。缺点是：要求一定的硬件支持，增加了成本。系统要增加页表及其管理程序，因而增加了内存的开销。6 .引入缓冲区的主要原因是什么？'、答：缓解了CPU勺高速与I/O设备低速之间速度不匹配的矛盾。减

13、少了CPU勺中断频率，降低了CPlfr断访问时间的限制。提高了CPUfI/O设备之间的并行性。提高了资源利用率和系统吞吐量。7 .操作系统的基本功能是什么？答：处理器管理；'存储管理；设备管理；文件管理；用户接口。五、算法填空题(根据算法内容，在横线上填入合适的内容，使算法完整。)1 .单链表的结点类型node定义如下：typedefstructlinknodeintdata;structlinknode*next;node;输入一系列整数，以0标志结束，将这些整数作为data域建立一个单链表的函数如下：voidcreat()node*head,*p,*s;intx,cycle=1;h

14、ead=(node*)malloc(sizeof(node):p=head;while(cycle)/scanf("%d",&x);if(x!=0)s=(node*)malloc(sizeof(node);s->data=x;p->next=S;p=s；elsecycle=0;head=head->next;p->next=NULL;计算机软件技术基础练习题(二)一、填空题(请在每个题目中的横线上填上准确的内容。)1 .时间复杂度是以算法中最大的语句来衡量的。2 .线性表的主要运算有、删除、查找和排序。3 .在线性表的顺序存储结构中，插入或删

15、除一个数据元素时，平均需要移动表中元素。4 .向量的存储空间是分配的，而线性链表的存储空间是在执行过程中动态分配的。5 .在队中，允许插入的一端称为队尾，允许删除的一端称为。6 .树中结点的最大层次数称为树的。7 .深度为h的二叉树中至多含有个结点。8 .图的常用存储结构有邻接矩阵和。/9 .实现图的遍历有和广度优先搜索两种方法。/10 .二叉排序树中,其左子树上所有结点的数据值均根结点的数据值。11 .通道是一种特殊的,它使外部设备和内存之间能直接进行数据传输，而与中央处理机无关。12 .“多道”是指在计算机同时可以存放多道作业。13 .并发是指两个或多个事件在同一、内发生。14 .一个目标

16、程序所占有的地址范围称为/。15 .在实存储管理中，分区分配有固定分区分配和两种形式。16 .主存中空闲区分配算法有算法、最佳适应算法和最差适应算法三种分配策略。17 .分段管理中的地址结构包括段号和两项。18 .局部性概念包括时间局部性和。19 .进程调度又称/或微观调度。20 .按设备的使用性质分类，设备可分为、共享设备和虚拟设备。21 .设备分配算法有和优先数法两种。22 .文件的逻辑结构是从的角度看到的文件组织形式。23 /文件的物理结构是指一个逻辑文件在上的存放形式。24 .常见的文件物理结构有、链接结构和索引结构三种。25 .软件开发过程模型主要有瀑布模型和模型两类。"2

17、6 .软件测试的步骤一般分为、组装测试和确认测试三步。27 .设备处理程序的最基本任务是使与处理机之间进行通信。28 .测试方案包括预定测试的功能、应该输入的测试数据和。29 .为保证软件的质量，主要采取的措施有、管理复审和测试。30 .软件开发人员的组织结构模式通常有、按职能划分和矩阵模式三种。二、单项选择题(请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括弧中，多填不得分。)1.、以下程序段的空间复杂度为()。fori=1tonforj=1tonfork=1tonxx+1end(k)end(j)end(i)(A)O(n)(B)Q1)2.空间复杂度可以衡量算法中(A)辅助空间单

18、元(C)程序占用空间(C)O(n2)/(D)O(n3)的多少。/(B)原始数据占用空间(D)使用变量)3队是先进后出的线性表向量的存储空间是静态分配的4需执行)(B)next(q)(D)52h2h-12+1)64246a7bdc24下图的广度优先遍历序列正确的是)7(B)(D)1421236深度为h且含有q -next(p);RET(q);next(p)next(p) next(q);q next(p);RET(q)next(p) next(q);RET(q);q next(p)q next(p);next(p) next(q);RET(q)以下对线性表的描述，正确的是 (A)栈是先进先出的线

19、性表35(B) 31(D) 2h-18 .在一个长度为n的顺序表中删除第i个数据元素Y0&i&n-1)时，需向前移动()个元素。(A)n-i/(B)n-i+1(C)n-i-1(D)i9 .一组记录的关键字为46,79,56,38,40,84,则利用快速排序的方法，以第一个记录为基准得到的一趟排序结果为()。(A)38,40,46,56,79,84(B)40,38,46,79,56,84(040,38,46,84,56,79(D)40,38,46,56,79,8410 .操作系统是一种()。(A)应用软件(B)系统软件(C)软件包(D)通用软件11 .下面对临界区的论述中，正确的

20、是()。(A)临界区是指进程中用于实现进程互斥的那段代码(B)临界区是指进程中用于实现进程同步的那段代码(C)临界区是指进程中用于访问共享资源的那段代码(D)临界区是指进程中访问临界资源的那段代码12 .允许多个用户将多个作业交给计算机集中处理的操作系统称为()。(A)批处理操作系统(B)分时操作系统(C)实时操作系统(D)网络操作系统13 .引入多道程序设计的主要目的为()。/(A)提高实时响应速度(B)充分利用处理机/(C)有利于代码共享(D)减少存储碎片/14 .以下哪项是一级目录的优点()。/(A)实现简单(B)访问速度慢/(C)文件名不能相重(D)主要用于单用户系统中15 .以下哪一

21、项不是软件开发中的系统分析与设计方法()。(A)结构化系统方法(B)理论化系统方法(C)快速原型方法(D)面向对象方法4216 .以下哪一项不是面向对象方法的优点(A)可重用性(C)可虚拟性17.高质量的软件文档不应该取决于(B)可维护性(D)表示方法的一致性)。(B)概括性(D)完整性(B)适应性维护(D)运行平台维护(A)精确性(C)清晰性18 .软件维护不包括()(A)改正性维护/(C)完善性维护19 .需求分析阶段确定系统的要求时不包括()(B)系统功能要求(D)系统运行要求(B) 20世纪60年代末(D) 20世纪80年代末(A)系统模糊要求(C)系统性能要求20 .软件危机出现在(

22、)(A)20世纪50年代末(Q20世纪70年代末、判断题(请判断每个题干是否正确，正确在括弧中打，错误在括弧中打X。)1 .()线性表惟一的存储形式是链表。2 .()线性表只能借助于指针和动态变量来实现。3 .()栈为空的情况下，不能作出栈的操作，否则产生下溢出。4 .、()在循环队列中，若尾指针r大于头指针f,则其元素数为r-f。5 .()二叉树只能采用二叉链表来存储。6 .()理想情况下，在散列表中查找一个元素的时间复杂度为0(1)。7 .()文件目录是由文件控制块组成的。8 .()请求分页存储管理系统若把页面的大小增加一倍，则缺页中断次数会减少一半。9 .()如果信号量当前值是-4,表示

23、系统中在该信号量上有/4个等待进程。10 .()银行家算法是用于防止进程死锁的。/四、问答题(请按照题目要求回答问题。)般树化为二叉树1 .将下列的2 .有一组关键字序列为38,19,65,13,97,49,41,95,1,73,采用冒泡排序方法由小到大排序，请写出每趟结果。3 .如下所示有向图：(1)写出每一结点的入度和出度各为多少；(2)写出上图的邻接矩阵。4 .请说明分段管理的优缺点是什么？5 .什么是死锁？产生死锁的原因和必要条件是什么？6 .请说明SPOOLin源统的组成？五、算法填空题(根据算法内容，在横线上填入合适的内容，使算法完整。)1.按先序遍历序列建立二叉树的二叉链表，已知

24、先序序列为：/FC从ADBAGHLAP*AA其中表示结束符。/二叉链表的生成：输入：二叉链表的头指针BT为空；根结点标志k=0。输出：二叉链表的头指针BT0#include""/#include""/structbtnodeintd;structbtnode*lchild;structbtnode*rchild;；/structbtnode*creatbt(bt,k)structbtnode*bt;intk;intb;structbtnode*p,*t;printf("inputb:")；scanf("d,&b);i

25、f(b!=0)p二p>d=b;p>lchild=NULLp>rchild=NULLif(k=0)t=p;if(k=1)bt>lchild=p；if(k=2)bt>rchild=p；return(t)计算机软件技术基础练习题（三）一、填空题（请在每个题目中的横线上填上准确的内容。）1 .线性表的结构特点是数据元素之间是关系。2 .在线性表的顺序存储结构中，插入或删除一个数据元素时，平均需要移动表中数据元素。3 .在队中，允许插入的一端称为,允许删除的一端称为队头。4 .C语言中数组是按优先顺序存放的。5 .二叉树的深度为树中结点的最大。6 .图的常用存储结构有和邻接

26、表。7 .多道系统是指在计算机同时可以容纳多道作业，并且可以并发的运行这些作业。8 .虚拟存储技术有、分段存储管理和段页存储管理。9 .实存储管理中，分区分配有和可变分区分配两种形式。10 .常见的文件物理结构有顺序结构、和索引结构三种。，/11 .网络层数据的传输单位是或包。/12 .路由器除了提供桥接功能外，还提供复杂的和管理。13 .Internet白C类地址用于大量的小型网，地址的最高3位为。14 .软件开发过程模型主要有'模型和渐增模型两类。15 .软件测试的步骤一般分为单元测试、/和确认测试三步。二、单项选择题（请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括

27、弧中，多填不得分。）1.以下程序段的时间复杂度为(fori=1tonforj=1tonxx+1)end(j)end(i)(A)O(n)(B)QI)2.以下对线性表的描述，正确的是(2(C)O(n)°(D)O(n3)(B)(A)栈是先进先出的线性表队是先进后出的线性表(C)向量的存储空间是静态分配的(D)线性链表可以随机存取3.在单链表中，若p指针所指结点不是最后结点，删除p之后所指的结点，则需执行(.(A)(B)(0(D)q-next(p);RET(q);next(p)next(q)qnext(p);next(p)next(q);RET(q)next(p)next(q)

28、;qnext(p);RET(q)next(p)next(q);RET(q);qnext(p)一个长度为n的顺序表中在第i(0&i<n)个数据元素前插入一个数据时，需向后移动()个元素。(A)n-i(B)n-i+1(C)i一组记录的关键字为46,79,56,38,40,84个记录为基准得到的一趟排序结果为(A)40,38,46,56,79,84(Q40,38,46,84,56,79操作系统是一种(')(A)应用软件(C)系统软件(B)(D)(D)n-i-1,则利用快速排序的方法，以第40,38,46,79,56,84(B)工具软件(D)通用软件允许多个用户以交互方式使用计算

29、机的操作系统称为(A)批处理操作系统(C)实时操作系统(B)分时操作系统(D)网络操作系统38,40,46,56,79,848 .广域网与广域网之间连接时需用()。(A)转发器(B)网桥(C)路由器(D)网关9 .TCP/IP协议的最低层是()。(A)应用层/(B)传输层(C)网间网层/(D)网络接口层10 .高质量的软件文档不应该取决于()。(A)精确性(B)清晰性/(C)概括性(D)完整性三、判断题(请判断每个题干是否正确，正确在括弧中打，错误在括弧中打X。)1 .()线性表只能借助于指针和动态变量来实现。2 .()向量是线性表唯一的一种存储形式。3 .()在循环队列中，若尾指针r大于头指

30、针f,则其元素数为r-f。'4 .()栈为空的情况下，不能作出栈的操作，否则产生下溢出。5 .()二叉树只能采用二叉链表来存储。6 .()单级文件目录也可以允许文件重名。7 .()计算机系统发生死锁纯粹是由于系统资源不足造成的。8 .()如果信号量当前值是-4,表示系统中在该信号量上有5个等待进程。9 .()在域名系统中，树根是唯一的中央管理机构。10 .()大型软件的开发由于软件计划不周可能造成一半以上的项目失败。四、算法分析应用题1. 一棵二叉树其中序和后序遍历为：中序：DGBAHECF后序：GDBHEFCA画出这棵二叉树的逻辑结构，并写出先序遍历结果。2 .给定一组元素35,25

31、,10,58,90,15,21,77,50,画出由此生成的二叉排序树。3 .有一组关键字序列为9,15,1,10,8,6，采用简单选择排序方法由小到大排序，请写出每趟排序结果。(6分)/4 .如下所示有向图：(6分)/(1)写出每一结点的入度和出度各为多少;(2)写出下图的邻接表。五、简答题1 .请说明分段管理的优缺点各是什么？2 .请说明什么是进程的三种基本状态？并画图说明进程各状态之间的转换过程？3 .请说明引入缓冲技术的根本原因是什么？4 .简述计算机网络协议采取层次结构的好处？5 .如果详细划分软件生命期的话，具体来说有哪七个阶段？计算机软件技术基础练习题（四）一、填空题（请在每个题目

32、中的横线上填上准确的内容。）1 .向量的结构特点是数据元素之间是关系。2 .在单向线性链表存储结构中，查找一个数据元素时，只能从开始。3 .在栈中，只能从进行插入或删除操作。4 .数组可以按或按列优先顺序存放。5 .在树结构中，没有前趋的结点称为结点。6 .用矩阵表示的图的存储结构称为。7 .计算机硬件部分包括、存储器、输入输出设备和各种通信设备。8 .分时系统是指多个用户共享同一台计算机，系统将CPU勺轮流分配给多个用户。9 .虚存储管理中，主要有和分段及段页式存储形式。10 .进程的三种基本状态有就绪状态、和阻塞状态。/11 .物理层数据的传输单位是。/12 .因特网的网络协议主要有协议。

33、13 .顶层域名如果是EDU的话，则为机构。/14 .为了保证软件的质量，主要通过、管理复审和测试来实施。15 .软件测试有和白盒测试两类方法。二、单项选择题（请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括弧中，多填不得分。）1 .在数据结构中，从逻辑上可以把数据结构分成（）0(A)动态结构和静态结构(B)内部结构和外部结构(C)线性结构和非线性结构/(D)紧凑结构和非紧凑结构2 .有一颗具有n个结点的k叉树，则有nk个指针域，其中有用的指针域为()个(A)n(B)nk-1(C)n-1(D)nk3 .对有序表(18,20,25,34,48,62,74,85)用对分查找法查找74

34、,查找成功时所需的比较次数为()次。(A) 2(B) 3(C) 44. 一组记录的关键字为3,8,5,9,7,6,2扫描得到的排序结果为()0(A) 3,5,8,7,6,2,9(C) 3,5,6,7,8,2,95.操作系统的主要功能是管理计算机系统中的(D) 5,则利用冒泡排序的方法，经过第一次 (B) 3,8,5,7,6,2,9(D) 2,3,5,8,7,6,9)。(A)程序和数据(C)硬件和软件资源6 .批处理系统的主要缺点是()(A) CPURJ用率低(C)缺少交互性7. TCP/IP协议的最高层是() (A)应用层(C)网间网层8 .路由器是()0(A)物理层中继系统(C)网络层中继系

35、统9 .软件测试的目标是()。(A)找出错误(C)得出结果10 .软件需求分析应包括()。(A)用户需求(C)软件需求(B)作业(D)进程(B)不能并发执行(D)以上都不是(B)传输层(D)网络接口层(B)数据链路层中继系统(D)网络层以上中继系统(B)验证计划(D)提高效率(B)硬件需求(D)以上全是、判断题(请判断每个题干是否正确，正确在括弧中打，错误在括弧中打X。)1 .()线性表的长度是指线性表所占的存储空间的大小。2 .()栈和队是运算受限制的线性表。3 .()若一棵树中某结点的度为1,则该结点仅有一棵子树。4 .()栈为满的情况下，不能作入栈的操作，否则产生下溢出。5 .()原语在

36、执行时是不能中断的。''6 .()缓冲技术是借用一部分外存储器区域作为缓冲池。7 .()两级以上文件目录就可以允许文件重名。8 .()网络操作系统是将连入网络的所有计算机和各种软硬件资源当成一个整/体。/9.()远程登录Telnet无法实现与另外的计算机进行交互式会话。10.()软件工程是一门集程序设计方法、工具和管理的科学。四、算法分析应用题1 .设一棵完全二叉树有50个结点，试问：、(1)有多少个叶子结点；(2)有多少个度为2的结点；(3)有多少个结点只有非空左子树。2 .给定一组元素10,6,15,20,18,30,画出由此生成的二叉排序树。(6分)3 .给定一组权值W=

37、8,15,3,2,20,4,画出由此生成的哈夫曼树(左分支结点'值小于右分支结点值)。(6分)4 .CQ0:9为一循环队列，初态front=rear=0,画出下列操作后队的头、尾指示器状态(5分)(1) a,b,c,d,e入队(2) a,b出队f,g,h,i,j入队/(4) c出队/(5) k,l,m,n,o入队/五、简答题1 .简述虚拟地址空间受哪些条件制约？实现虚拟存储技术需要解决哪些问题？2 .简述操作系统的基本功能是什么？/3 .简述开放系统互联参考模型OSI共分为哪七个层次？4 .软件工程按软件开发活动步骤应该制定哪些计划?计算机软件技术基础练习题（二）参考答案一、填空题1.

38、频度/2.插入3.一半4.静态5.队头6.深度7.2h-18.邻接表9.深度优先搜索10.小于11.处理机12.内存中13.时间间隔14.地址空间15.可变分区分配16、首次适应17.段内地址18.空间局部性19.低级调度20.独享设备21.先请求先服务22.用户23.外存储器24.顺序结构25.渐增26.单元测试27.外部设备28.预期结果29.技术审查30.按课题划分二、单项选择题三、判断题1.x2.x3.V4.V5.x6.V7.V8.x9.V10.x四、问答题1 .答：2 .答：38,19,65,13,97,49,41,95,1,7319,38,13,65,49,41,95,1,73,9

39、719,13,38,49,41,65,1,73,95,9713,19,38,41,49,1,65,73,95,9713,19,38,41,1,49,65,73,95,9713,19,38,1,41,49,65,73,95,9713,19,1,38,41,49,65,73,95,9713,1,19,38,41,49,65,73,95,971,13,19,38,41,49,65,73,95,973 .答：入度出度302212222114邻接矩阵如下：00，000、1001000100010010101100000J10110)/4 .答：/分段管理的优点是：便于程序模块化处理。便于处理变化的数据。便于共享分段。分段管理的缺点是：增加了硬件成本，地址变换花费了CPUJ间，增加了附加的存储空间分段尺寸的大小受主存限制，会出现碎片问题。5 .答：死锁是指多个并发执行的进程由于竞争资源不当所产生的一种僵持状态，处于这种僵持状态时，如无外力作用，所有进程都将无法再向前推进。产生死锁的原因是：系统资源不足。进程推进的顺序不当。产生死锁的必要条件是： 所用资源是非共享的。 进程请求新资源时，继续占用已分配到的资源。/一个进程占有的资源不能被其他进程强行抢占。一个进程获得的资源同时被另