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