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

计算机软件技术基础课程学习练习题赵俊生 编内蒙古工业大学信息工程学院2011-3-1计算机软件技术基础课程学习练习题目 录计算机软件技术基础练习题（一） .1计算机软件技术基础练习题（二） .7计算机软件技术基础练习题（三） .14计算机软件技术基础练习题（四） .18计算机软件技术基础练习题（一）参考答案 .21计算机软件技术基础练习题（二）参考答案 .24计算机软件技术基础练习题（三）参考答案 .27计算机软件技术基础练习题（四）参考答案 .31计算机软件技术基础课程学习练习题第 1 页 共 37 页计算机软件技术基础练习题（一）一、填空题（请在每个题目中的横线上填上准确的内容。 ）1衡量算法的优劣，通常用计算机执行时的 时间 和空间资源的消耗多少作为评价标准。2空间复杂度是以在算法中所需的 辅助 空间单元的多少来衡量的。3线性表有两种存储结构，分别是 向量 和链表。4线性表的结构特点是：数据元素之间是线性关系，在表中除第一个元素外，每个元素有且只有一个 前趋元素 ；除最后一个元素外，每个元素有且只有一个后继元素。5用一组地址 连续 的存储单元存放线性表的数据元素，称为线性表的顺序存储结构。6在线性表的链式存储结构中，每一个数据元素由两个域组成，一个是存放元素值的 数据域 ，另一个是存放后继元素存储地址的指针域。7在栈中，允许插入或删除的一端称为 栈顶 ，另一端称为栈底(bottom)。8在树结构中，度为零的结点称为 叶子 结点，又称端结点。9二叉树的第 i 层上至多有 2i-1 个结点。10哈夫曼树又称最优树，是一类带权路径 最短 的树。11计算机硬件部分包括处理机、 存储器 、输入输出设备和各种通信设备。12 “批处理”是指用户与作业之间没有 交互作用 ，用户不能直接控制作业的运行。13分时系统是指多个用户 共享 同一台计算机，系统将 CPU 的时间片轮流分配给多个用户。14处理机管理主要解决 CPU 的 分配策略 、实施方法以及资源的分配和回收问题。15文件管理的基本功能是实现对文件的 存取 和检索，为用户提供方便灵活的操作命令以及实现文件共享、安全、保密等措施。16虚拟是指通过某种技术把一个物理实体变为若干个 逻辑上 的对应物。17当目标程序装入主存后占用的一系列物理单元的集合，称为 存储空间 。计算机软件技术基础课程学习练习题第 2 页 共 37 页18可重定位分区分配是在可变分区分配基础上增加内存 紧缩功能 形成的。19常用的两种页面置换算法为 先进先出 法和最近最少使用法。20进程的三种基本状态有就绪状态、执行状态和 阻塞状态 。21顺序程序执行的特点有顺序性、 封闭性 和可再现性。22设备分配算法有先请求先服务和 优先数 两种。23常见的文件物理结构有顺序结构、 链接结构 和索引结构三种。24可行性研究主要集中在经济可行性和 技术可行性 两个方面。25软件工程的基本原则包括划分软件生命期、进行计划评审和 编制软件文档 。26软件维护主要包括 改正性维护 、适应性维护和完善性维护三个方面。27软件测试有 黑盒测试 和白盒测试两类方法。28数据处理问题的两种类型有 变换型 和事务处理型。29软件开发人员的组织原则有 尽早落实责任 和减少接口。30软件开发小组内部人员的组织形式主要有 民主制 和主程序员制两种。二、单项选择题（请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括弧中，多填不得分。 ）1以下程序段的时间复杂度为（ C ） 。for i=1 to nfor j=1 to nfor k=1 to nxx+1end(k)end(j)end(i)（A） O(n) （B） O(n2) （C） O(n3) （D） O(3n)2在数据结构中，从逻辑上可以把数据结构分成（C ） 。（A）动态结构和静态结构 （B）内部结构和外部结构（C）线性结构和非线性结构 （D）紧凑结构和非紧凑结构3时间复杂度可以评估一个算法的（ A ） 。（A）时间增长趋势 （B）具体执行时间计算机软件技术基础课程学习练习题第 3 页 共 37 页（C）复杂程度 （D）正确性4以下对线性表的描述，正确的是（ B ） 。（A） 向量的存储空间是动态分配的（B） 线性链表只能顺序存取（C） 栈是先进先出的线性表（D） 队是先进后出的线性表5在单链表中，在 p 指针之后插入一个 s 指针所指的结点，则需执行（ A ） 。（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); snext(p)6有一颗具有 n 个结点的 k 叉树，则有 nk 个指针域，其中有用的指针域为（ C ）个。（A）n （B）nk-1 （C）n-1 （D）nk7以下二叉树的带权路径长度为（ A ） 。（A）44 （B）48 （C）40 （D）568下图的深度优先遍历序列正确的是（ A ） 。（A）V 2V 1V 3V 5V 4V 6 （B）V 2V 1V 3V 5V 6V 4 （C）V 2V 5V 1V 3V 4V 6 （D）V 2V 5V 1V 3V 6V 4a b c d8 6 3 5125346计算机软件技术基础课程学习练习题第 4 页 共 37 页9表长为 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,5,9,7,6,2，则利用冒泡排序的方法，经过第一次扫描得到的排序结果为（ A ） 。（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,912操作系统的主要功能是管理计算机系统中的（ C ） 。（A）程序和数据 （B）作业（C）资源 （D）进程13允许多个用户以交互方式使用计算机的操作系统称为（ A ） 。（A）分时操作系统 （B）实时操作系统（C）批处理操作系统 （D）多处理机操作系统14批处理系统的主要缺点是（ C ） 。（A）CPU 利用率低 （B）不能并发执行（C）缺少交互性 （D）以上都不是15下列哪个选项不是操作系统关心的问题（ D ） 。（A）管理计算机裸机 （B）设计、提供用户程序与计算机硬件系统的界面（C）管理计算机系统资源 （D）高级程序设计语言的编译器16最佳适应算法的空闲块是（ C ） 。（A）按大小递减顺序连在一起 （B）按地址由小到大排列（C）按大小递增顺序连在一起 （D）按地址由大到小排列17软件测试的目标是（ A ） 。（A）找出错误 （B）验证计划计算机软件技术基础课程学习练习题第 5 页 共 37 页（C）得出结果 （D）提高效率18以下哪项不是软件测试的步骤（ B ） 。（A）单元测试 （B）流程测试（C）组装测试 （D）确认测试19为保证软件开发的质量，一般不采取的措施是（ D ） 。（A）技术审查 （B）管理复审（C）测试 （D）监督20结构化分析方法不包括（ C ） 。（A）数据流图 （B）数据词典（C）编写代码 （D）结构化语言三、判断题（请判断每个题干是否正确，正确在括弧中打，错误在括弧中打。 ）1 （ ）线性表的长度是指线性表所占的存储空间的大小。2 （ ）线性表就是顺序表。3 （ ）栈和队是运算受限制的线性表。4 （ ）若一棵树中某结点的度为 1，则该结点仅有一棵子树。5 （ ）在执行排序算法中，出现了排序的关键字朝着和最终排序序列位置相反的方向移动，则该算法是不稳定的。6 （ ）快速排序中，以待排序的 n 个记录中的第 1 个记录的关键字值为基准，将所有记录分为两组，该记录就在这两组中间，这也是该记录的最终位置。7 （ ）原语在执行时是不能中断的。8 （ ）程序并发执行是指同一时刻有两个以上的程序指令在同一处理器上执行。9 （ ）缓冲技术是借用一部分外存储器区域作为缓冲池。10 （ ）PV 操作可实现进程的同步和共享资源的互斥使用，但不能排除死锁。四、问答题（请按照题目要求回答问题。 ）1一棵二叉树其中序和后序遍历为： 中序：BDCEAFHG 后序：DECBHGFAABCD EFGH计算机软件技术基础课程学习练习题第 6 页 共 37 页画出这棵二叉树的逻辑结构，并写出先序遍历结果。 答：逻辑结构为：先序遍历为：ABCDEFGH2设一棵完全二叉树有 20 个结点，试问： a) 有多少个叶子结点；b) 有多少个度为 2 的结点；c) 有多少个结点只有非空左子树。答：（1）有 10 个叶子结点（2）有 9 个度为 2 的结点（3）有 1 个结点只有非空左子树3给定一组元素17,28,36,54,30,27,94,15,21,83,40，画出由此生成的二叉排序树。4给定一组权值 W=8,2,5,3,2,17,4，画出由此生成的哈夫曼树1715212728303694834054175 82 2 3 441249 154 7计算机软件技术基础课程学习练习题第 7 页 共 37 页5 请说明分页管理的优缺点是什么？ 答：优点是：不要求作业在内存中连续存放，较好的解决了碎片问题。作业地址空间不受内存的限制，为用户提供足够大的存储空间，更有利于多道程序作业。缺点是：要求一定的硬件支持，增加了成本。系统要增加页表及其管理程序，因而增加了内存的开销。6 引入缓冲区的主要原因是什么？ 答：缓解了 CPU 的高速与 I/O 设备低速之间速度不匹配的矛盾。减少了 CPU 的中断频率，降低了 CPU 中断访问时间的限制。提高了 CPU 与 I/O 设备之间的并行性。提高了资源利用率和系统吞吐量。7 操作系统的基本功能是什么？ 答：处理器管理； 存储管理； 设备管理； 文件管理； 用户接口。五、算法填空题（根据算法内容，在横线上填入合适的内容，使算法完整。 ）1单链表的结点类型 node 定义如下：typedef struct linknode int data;struct linknode *next;node;输入一系列整数，以 0 标志结束，将这些整数作为 data 域建立一个单链表的函数如下：void creat()计算机软件技术基础课程学习练习题第 8 页 共 37 页node *head,*p,*s;int x,cycle=1; head=(node*)malloc(sizeof(node) ;p=head;while(cycle)scanf(“%d“,if(x!=0)s=(node *)malloc(sizeof(node);s-data= x ;p-next= S ; p=s;else cycle=0;head=head-next;p-next=NULL; 计算机软件