1、计算机软件技术基础课后答案计算机软件技术基础课后答案【篇一：计算机软件技术基础复习题(含答案)】txt1.线性表的链式存储结构与顺序存储结构相比优点是 a. 所有的操作算法实现简单 c. 便于插入和删除 b. 便于随机存取 d. 便于利用零散的存储器空间 2.线性表是具有n个的有限序列。 a. 表元素 d. 数据项 b. 字符 c. 数据元素 e. 信息项 3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为c 。（1in+1） a. o(0) b. o(1) 2c. o(n) d. o(n) 4.设a是一个线性表(a1,a2,?,an)，采用顺序存储结构，
2、则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 b，平均每删除一个元素需要移动的元素个数为 a；若元素插在ai与ai+1之间(0in-1)的概率为 元素所要移动的元素个数为 c； 2(n?i)，则平均每插入一个n(n?1) n?1 2 2n?1c.3a. n 23n?1d. 4b. 5.下列函数中，按它们在n?时的无穷大阶数，最大的是 d。 a. logn b. nlogn n/2c. 2 d. n! 6. a. s-next=p+1; p-next=s; b. (*p).next=s; (*s).next=(*p).next; c. s-next=p-next; p-next=s
3、-next; d. s-next=p-next; p-next=s; 7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 a 。 a. n c. n-1 b. 2n-1 d. 2n13.用单链表表示的链式队列的队头在链表的a 位置。 a. 链头b. 链尾c. 链中 14.若用单链表表示队列，则应该选用。 a. 带尾指针的非循环链表b. 带尾指针的循环链表 c. 带头指针的非循环链表d. 带头指针的循环链表 15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数
4、据先被打印。该缓冲区应该是一个b 结构。 a. 堆栈 b. 队列 c. 数组 d. 线性表 16.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为b 。 a. 1和5 b. 2和4 c. 4和2 d. 5和1 17.设栈的输入序列为1,2，?,10，输出序列为a,a,?,a，若a=10，则a为 c 。121057 （未要求一次性全部输入或输出） a. 4 b. 8c.不确定d.7 18.设栈的输入序列是1,2,3,4，则d 不可能是其出栈序列。 a 1243b. 2134c. 1432 d
5、. 4312 19.以下 abd 是c语言中”abcd321abcd”的子串。 a. abcd b. 321ab c. “abcabc” d. “21ab” 20.若串s=”software”，其子串的数目是。 a. 8 b. 37c. 36 d. 9 22.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为b ，至多为 f 。高为h的完全二叉树的结点数至少为 e ，至多为 f 。 a 2h b. 2h-1c. 2h+1 d.h+1 h-1hh+1he. 2 f. 2-1g. 2-1 h. 2+1 23.一棵有124个叶结点的完全二叉树，最多有b 个结点。 a. 247 b. 2
6、48c. 249 d. 251 24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是c 。（记） a. 满二叉树 c. 堆 b. 哈夫曼树 d. 二叉查找树 25.前序遍历和中序遍历结果相同的二叉树为；前序遍历和后序遍历结果相同的二叉树为b 。a. 一般二叉树b. 只有根结点的二叉树 c. 根结点无左孩子的二叉树d. 根结点无右孩子的二叉树 e. 所有结点只有左孩子的二叉树 f. 所有结点只有右孩子的二叉树 29.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行d 次探测。 a. k-1次 b. k次 c. k+1次 d. k(
7、k+1)/2次 30.在n个记录的有序顺序表中进行折半查找，最大的比较次数是?log2n?1。 32.在下述排序算法中，所需辅助存储空间最多的是b ，所需辅助存储空间最小的是c ，平均速度最快的是a 。 a.快速排序 b. 归并排序 c. 堆排序 33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是a 。 a. 直接插入排序 b. 冒泡排序 c. 简单选择排序 34.快速排序在最坏情况下时间复杂度是o(n)，比a 的性能差。 2 a. 堆排序 b. 冒泡排序 c. 简单选择排序 35.若需在o(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是c 。 a
8、. 快速排序 b. 堆排序 c. 归并排序 d. 希尔排序 36.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用 b 方法最快。 a. 冒泡排序 b. 快速排序 c. 希尔排序 d. 堆排序 e. 简单选择排序 37.以下结点序列是堆的为a 。 a. 100,90,80,60,85,75,20,25,10,70,65,50 b. 100,70,50,20,90,75,60,25,10,85,65,80 38.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选c 。 a. 快速排序 b. 堆排序 c. 归并排序 d. 希尔排序 39.从未排序序列中依次取
9、出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为a 排序法。 a. 插入排序 b. 交换排序 c. 选择排序 d. 归并排序 40.直接插入排序在最好情况下的时间复杂度为b 。 a. o(logn) b. o(n) 2c. o(nlogn) d. o(n) 46. 从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是(1) 排序。从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是(2) 排序。逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是(3) 排序。如果整个排序过程都在内存中进行
10、，称为 (4) 排序。排序算法的复杂性与排序算法的(5) 有关。 供选答案：(1): (2): (3): (4): (5): a. 选择b. 插入 c. 比较d. 归并 a. 选择b. 插入 c. 比较d. 归并 a. 冒泡b. 交换 c. 比较d. 散列 a. 外部b. 内部 c. 外存d. 内存 a. 运算量大小与占用存储多少 b. 运算量大小与处理的数据量大小 c. 并行处理能力和占用存储多少 d. 占用存储多少和处理的数据量大小 答案：baaba 47.操作系统是对计算机资源进行的(1) 系统软件，是(2) 的接口。 在处理机管理中，进程是一个重要的概念，它由程序块、(3) 和数据块三
11、部分组成，它有3种基本状态，不可能发生的状态转换是(4) 。 虚拟存储器的作用是允许程序直接访问比内存更大的地址空间，它通常使用(5) 作为它的一个主要组成部分。 供选答案： (1): a. 输入和输出 b. 键盘操作 c. 管理和控制 d. 汇编和执行 (2): a. 软件和硬件 b. 主机和外设 c. 高级语言和机器语言 d. 用户和计算机 (3): a. 进程控制块 b. 作业控制块 c. 文件控制块 d. 设备控制块 (4): a. 运行态转换为就绪态 b. 就绪态转换为运行态 c. 运行态转换为等待态 d. 等待态转换为运行态 (5): a. 软盘b. 硬盘 c. cdrom d.
12、寄存器 答案：cdadb 48.a 是信息的载体，它能够被计算机识别、存储和加工处理。 a. 数据 b. 数据元素c. 结点 d. 数据项 49.下列程序段的时间复杂度为c 。 for(i=1;in;i+) y=y+1; for(j=0;j=(2*n);j+) x+; 供选答案： 2a. o(n-1)b. o(2n)c. o(n)d. o(2n+1) 50.下面程序段的时间复杂度为d 。 i=1; while(i=n) i=i*2; 供选答案： a. o(1) b. o(n) c. o(n2) d. o(log2n)51.下面程序段的时间复杂度为b 。 a=0;b=1; for(i=2;i=n
13、;i+) s=a+b; b=a; a=s; 供选答案： 2a. o(1) b. o(n) c. o(log2n)d. o(n) 52.数据结构是一门研究非数值计算的程序设计问题中，计算机的a 以及它们之间的关系和运算等的学科。 a.操作对象b. 计算方法c. 逻辑存储d. 数据映象 53.在数据结构中，从逻辑上可以把数据结构分成c 。 a. 动态结构和静态结构 b. 紧凑结构和非紧凑结构 c. 线性结构和非线性结构 d. 内部结构和外部结构 54.算法分析的目的是c 。 a. 找出数据结构的合理性 b. 研究算法中输入和输出的关系 c. 分析算法的效率以求改进 d. 分析算法的易懂性和文档性
14、55.算法分析的两个主要方面是d 。 a. 间复杂性和时间复杂性 b. 正确性和简明性 c. 可读性和文档性d. 数据复杂性和程序复杂性 56.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为b 。 a. 110 b. 108 c. 100 d. 120 57.若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3,?,pn，若p1=n，则pi为c 。 a. i b. n-i c. n-i+1d.不确定 58.对于一个栈，给出输入项a,b,c。如果输入项序列由a,b,c所组成，则不可能产生的输出序列是a 。 a. cab b. cba c.
15、 abc d. acb 59.设有如下的单链表的按序号查找的算法，其时间复杂度为b 。 linknode *getnode(linklist head, int i) int j; listnode *p; p = head; j=0; while(p-next ji) p = p-next; j+; if(i=j) return(p); else【篇二：计算机软件技术基础(第三版)的课后答案】是信息？信息与数据的区别和联系在何处？ 信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。 信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。 与数据的区别和联系： 数据
16、定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。 我们把这些数据收集起来，经过处理后，即得到人们需要的信息。 信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。 2. 信息是经过加工（处理）后的数据。 3. 信息是对决策有价值的数据。 1.2 信息有哪些基本属性？ 信息的基本属性有： 1. 事实性。 2. 等级性。 3. 可压缩性。 4. 可扩散性。 5. 可传输性。 6. 共享性。 7. 增值性和再生性。 8. 转换性。 1.3 计算机的主要特点是什么？ 计算机最主要的特点是： 1. 高速自动的操作功能。 2. 具有记忆的能力。 3. 可以进行各种
17、逻辑判断。 4. 精确高速的计算能力。 1.5 完整的计算机系统应该包括哪几部分？ 目前最完整的计算机系统学说认为由五部分组成： 1. 人员 2. 数据 3. 设备 4. 程序 5. 规程 1.6 什么是计算机硬件？什么是计算机软件？ 硬件：泛指实际存在的物理设备，包括计算机本身及其外围设备。 微型计算机的硬件系统：主机、外存储器、输入设备、输出设备、微机的系统总线。 软件：是指计算机程序、方法、规则的文档以及在计算机上运行它时所必须的数据。 计算机软件一般分为系统软件和应用软件。 1.8 软件技术发展的几个阶段各有什么特点？它与硬件的关系如何？第一阶段：高级语言阶段 特点：这一时期，编译技术
18、代表了整个软件技术，软件工作者追求的主要 目的是设计和实现在控制结构和数据结构方面表现能力强的高级语言。但在这一时期内，编译系统主要是靠手工编制，自动化程度很低。硬件关系：此时期计算机的硬件要求仅能用机器指令来编制可运行的程序。第二阶段：结构程序设计阶段 特点：在程序的正确性方面，提出了结构化程序设计思想使程序的可靠性 提高了。 程序设计方法论方面，提出由顶向下法和自底向上法。使程序模块 化，使问题的复杂性和人的思维统一起来了。 出现了软件生产管理。 硬件关系：磁盘问世，操作系统发展，非数值计算应用发展，通信设备完 善，网络发展，集成电路发展等使软件复杂性增加产生软件危机，在此背景下发展了软件
19、技术。 第三阶段：自动程序设计阶段 特点：向集成化、一体化发展。出现了软件开发环境。程序设计基本方法 进一步改进。 硬件关系：集成电路迅速发展以及高分辨率终端的出现，为个人计算机发 展提供了条件，再加上人工智能、专家系统研究的发展，使程序设计进入成熟期。 第二章 2.1 什么是数据结构？它对算法有什么影响？ 数据结构是指同一数据对象中各数据元素间存在的关系。 对算法是影响：算法的实现必须借助程序设计语言中提供的数据类型及其 运算。一个算法的效率往往与数据的表达形式有关，因此数据结构的选择对数据处理的效率起着至关重要的作用。它是算法和程序设计的基本部分，它对程序的质量影响很大。 2.2 何谓算法
20、？它与程序有何区别？ 广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。计算机算法是通过计算机能执行的算法语言来表达的。 和程序的区别：一个程序包括两个方面的内容： （1）、对数据的描述，即数据结构。（2）、对操作的描述，即算法。 所以算法是程序的一个要素。 2.3 何谓频度，时间复杂度，空间复杂度？说明其含义。 频度：在某个算法中某个语句被重复执行的次数就是此语句的频度。 时间复杂度：是用来估算一个算法的执行时间的量，以算法中频度最大的语句来度量。 空间复杂度：指在算法中所需的辅助空间的单元，而不包括问题的原始数据占用的空间。 2.6 数据的存储结构主要有哪两种?它们之间的本质区别
21、是什么？ 数据的存储结构：向量和链表。 本质区别：向量是连续存放的，其存储空间是静态分配的，以存放顺序来表 达元素的前后件的关系。 链式存储结果不需要一组连续的存储单元，其数据元素可以分散存放在存储空间中，其元素关系由指针来指向。 2.16 试比较顺序表和链表的优缺点。 1. 线性表的长度是否固定方面：由于向量的存储空间是静态分配的，链表的存储空间是动态分配的，因此若表长不固定时采用线性链表较好。 2. 线性表的主要操作是什么：由于向量是连续存放的，所以适用于查找操作，不适用插入、删除操作。由于线性链表只能顺序存取，所以适用于插入、删除操作，不适用于查找操作。 3. 采用的算法语言：线性链表要
22、求所使用的语言工具提供指针类型变量。 2.17 试比较单向链表与双向链表的优缺点。 1. 单向链表只能单方向地寻找表中的结点，双向链表具有对称性，从表中某一给定的结点可随意向前或向后查找。 2. 在作插入、删除运算时，双向链表需同时修改两个方向上的指针，单向链表则简便些。 2.23 试画出表达式a*(b-d)/d+c*(e*f)执行过程中ns,os栈的变化情况。 b-d=t1 d/t1=t2t2*a=t3e*f=t4t4*c=t52.26 用三元组和带行辅助向量形式表示下列稀疏矩阵： 80 0?1300026?1500 220?15?0? ? 0113000? 1500600050?（1）：?
23、 ?0?30 403000? ?0 00?600? ? （2）：200040? ?000000? ?00 0? ?000000? ?9100000? ? 00?12?02 0000000? ? 00 28000? ? 000400000? ?70 0000000? ? 12002060030? （1）：三元组 带行辅助向量2.27 试说明树与二叉树有何不同？为何要将一般树转换为二叉树？ 树与二叉树区别：树是由n个（n=0）结点组成的有限集合t，其中有且仅有一个结点称为根结点，在此类元素结点之间存在明显的分支和层次关系。 二叉树是一种特殊的树结构，每一个结点最多只有两个孩子，即最多只有两个分支。
24、 为何要转换：一般树，树中结点次序没有要求，分支庞杂。而二叉树，元素之间存在严谨的前后代关系，在对数据元素进行删除、查找、插入等运算时更加有效率。 2.28 将下列（题图2.3）的一般树化为二叉树。题图2.3 转换后：2.30 设一棵二叉树其中序和后序遍历为 中序：bdceafhg 后序：decbhgfa 画出这棵二叉树的逻辑结构，并写出先序遍历结果。先序遍历：abcdefgh 其逻辑结构如下：【篇三：计算机软件技术基础 习题一解答】正整数, 分析下列各程序段中加下划线的语句的执行次数。 (1) for (int i = 1; i = n; i+) for (int j = 1; j = n;
25、 j+) cij = 0.0; for (int k = 1; k = n; k+)cij = cij + aik * bkj; (2) x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j = i; j+) for (int k = 1; k = j; k+) x = x + y; (3) int i = 1, j = 1; while (i=n j=n) i = i + 1; j = j + i; (4)* int i =1; do for (int j = 1; j = n; j+)i = i + j; while(i100
26、 + n); 【解答】 nnn 3 (1) ?1?n i?1j?1k?1 ? (2) nijnin ?1? i?1 j?1k?1 i?1 j?1 j? i?1 ?i(i?1)?1? 2?2 ?2 n ?i i?1 2 ? 1 n i?2 i?1 1n(n?1)(2n?1)2 6 1n(n?1) 2 ? n(n?1)(n?2) 6 (3)i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1， i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2， i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 )
27、+ 4 = 4 + 1 + 2 + 3， i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4， ? i = k时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + ? + k )， ?j?k?1?k?1? k ?i?n i?1 k?k?1?2 ? k?3k?3 2 2 ?n 解出满足上述不等式的k值，即为语句i = i + 1的程序步数。(4) for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为 1?k n
28、(n?1)2 n(n?1) 2 故最终for语句的执行次数k为满足 1?k n(n?1)2 ?100?n 的最小整数k，语句i = i + j的程序步数为n*k。 4.试编写一个函数计算n!*2的值，结果存放于数组aarraysize的第n个数组元素中，0 ? n ? arraysize。若设计算机中允许的整数的最大值为maxint，则当narraysize或者对于某一个k (0 ? k ? n)，使得k!*2 maxint时，应按出错处理。可有如下三种不同的出错处理方式： (1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误； k n (3) 在函数的参数表设置一个引用
29、型的整型变量来区别是正常返回还是某种错误返回。 试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。 【解答】 #include stdio.h const int arraysize = 100; const int maxint = 0x7fffffff; int calc( int t , int n ) int i, value = 1;t0=1; if ( n != 0 ) void main ( ) int aarraysize; int i; for ( i = 0; i arraysize; i+ ) if ( !calc ( a, i ) ) printf(faile
30、d at %d .n, i ); break; int edge = maxint / n / 2; for ( i = 1; i n; i+ ) value *= i*2; ti = value; if ( value edge ) return 0; value *= n * 2; tn = value; printf(a %d = %dn”,n,tn); return 1; /*-顺序表结构的定义.为简化起见，表元素我们使用整型数据- -数据元素从data0处开始存储-*/ typedef struct /*注意typedef的使用*/ int datamaxsize; /*数据域*/ int length;/*表长*/ listtype; 5.设有一个线性表 (a0, a1, ?, an-2, an-1) 存放在一个一维数组aarr
