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

计算机软件技术基础 课程学习练习题 赵俊生 编 内蒙古工业大学信息工程学院 2011-3-1  目 录 《计算机软件技术基础》练习题（一） 1 《计算机软件技术基础》练习题（二） 7 《计算机软件技术基础》练习题（三） 14 《计算机软件技术基础》练习题（四） 18 《计算机软件技术基础》练习题（一）参考答案 21 《计算机软件技术基础》练习题（二）参考答案 24 《计算机软件技术基础》练习题（三）参考答案 27 《计算机软件技术基础》练习题（四）参考答案 31 《计算机软件技术基础》练习题（一） 一、填空题（请在每个题目中的横线上填上准确的内容。） 1．衡量算法的优劣，通常用计算机执行时的 和空间资源的消耗多少作为评价标准。 空间复杂度是以在算法中所需的 空间单元的多少来衡量的。 3．线性表有两种存储结构，分别是 和链表。 4．线性表的结构特点是：数据元素之间是线性关系，在表中除第一个元素外，每个元素有且只有一个 ；除最后一个元素外，每个元素有且只有一个后继元素。 用一组地址 的存储单元存放线性表的数据元素，称为线性表的顺序存储结构。 在线性表的链式存储结构中，每一个数据元素由两个域组成，一个是存放元素值的 ，另一个是存放后继元素存储地址的指针域。 7．在栈中，允许插入或删除的一端称为 ，另一端称为栈底(bottom)。 8．在树结构中，度为零的结点称为 结点，又称端结点。 9．二叉树的第i层上至多有 个结点。 10．哈夫曼树又称最优树，是一类带权路径 的树。 11．计算机硬件部分包括处理机、 、输入输出设备和各种通信设备。 12．“批处理”是指用户与作业之间没有 ，用户不能直接控制作业的运行。 13．分时系统是指多个用户 同一台计算机，系统将CPU的时间片轮流分配给多个用户。 14．处理机管理主要解决CPU的 、实施方法以及资源的分配和回收问题。 15．文件管理的基本功能是实现对文件的 和检索，为用户提供方便灵活的操作命令以及实现文件共享、安全、必威体育官网网址等措施。 16．虚拟是指通过某种技术把一个物理实体变为若干个 的对应物。 17．当目标程序装入主存后占用的一系列物理单元的集合，称为 。 18．可重定位分区分配是在可变分区分配基础上增加内存 形成的。 19．常用的两种页面置换算法为 法和最近最少使用法。 20．进程的三种基本状态有就绪状态、执行状态和 。 21．顺序程序执行的特点有顺序性、 和可再现性。 22．设备分配算法有先请求先服务和 两种。 23．常见的文件物理结构有顺序结构、 和索引结构三种。 24．可行性研究主要集中在经济可行性和 技术可行性 两个方面。 25．软件工程的基本原则包括划分软件生命期、进行计划评审和 。 26．软件维护主要包括 改正性维护 、适应性维护和完善性维护三个方面。 27．软件测试有 黑盒 和白盒测试两类方法。 28．数据处理问题的两种类型有 变换型 和事务处理型。 29．软件开发人员的组织原则有 和减少接口。 30．软件开发小组内部人员的组织形式主要有 和主程序员制两种。 二、单项选择题（请在每个小题的四个备选答案中选择一个正确答案的序号填入题干的括弧中，多填不得分。） 以下程序段的时间复杂度为（ ）。 for i=1 to n for j=1 to n for k=1 to n x←x+1 end(k) end(j) end(i) （A）O(n) （B）O(n2) （C）O(n3) （D）O(3n) 2．在数据结构中，从逻辑上可以把数据结构分成（ ）。 （A）动态结构和静态结构 （B）内部结构和外部结构 （C）线性结构和非线性结构 （D）紧凑结构和非紧凑结构 3．时间复杂度可以评估一个算法的（ ）。 （A）时间增长趋势 （B）具体执行时间 （C）复杂程度 （D）正确性 4．以下对线性表的描述，正确的是（ ）。 向量的存储空间是动态分配的 线性链表只能顺序存取 栈是先进先出的线性表 队是先进后出的线性表 5．在单链表中，在p指针之后插入一个s指针所指的结点