计算机软件技术基础课后答案【篇一：《计算机软件技术基础》复习题(含答案)】txt>1.线性表的链式存储结构与顺序存储结构相比优点是a. 所有的操作算法实现简单c. 便于插入和删除 b. 便于随机存取d. 便于利用零散的存储器空间2.线性表是具有n个的有限序列。

a. 表元素d. 数据项 b. 字符 c. 数据元素e. 信息项3.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为c 。

（1≤i≤n+1）a. o(0)b. o(1)2c. o(n) d. o(n)4.设a是一个线性表(a1,a2,?,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 b，平均每删除一个元素需要移动的元素个数为 a；若元素插在ai与ai+1之间(0≤i≤n-1)的概率为元素所要移动的元素个数为 c； 2(n?i)，则平均每插入一个n(n?1) n?1 22n?1c.3a. n 23n?1d. 4b.5.下列函数中，按它们在n??时的无穷大阶数，最大的是 d。

a. lognb. nlognn/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-next;d. s-next=p-next; p-next=s;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 a 。

a. nc. n-1b. 2n-1 d. 2n13.用单链表表示的链式队列的队头在链表的a 位置。

a. 链头b. 链尾c. 链中14.若用单链表表示队列，则应该选用。

a. 带尾指针的非循环链表b. 带尾指针的循环链表c. 带头指针的非循环链表d. 带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。

该缓冲区应该是一个b 结构。

a. 堆栈b. 队列c. 数组d. 线性表16.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为b 。

a. 1和5b. 2和4c. 4和2d. 5和117.设栈的输入序列为1,2，?,10，输出序列为a,a,?,a，若a=10，则a为 c 。

121057（未要求一次性全部输入或输出）a. 4b. 8c.不确定d.718.设栈的输入序列是1,2,3,4，则d 不可能是其出栈序列。

a． 1243b. 2134c. 1432 d. 431219.以下 abd 是c语言中”abcd321abcd”的子串。

a. abcdb. 321abc. “abcabc”d. “21ab”20.若串s=”software”，其子串的数目是。

a. 8b. 37c. 36d. 922.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为b ，至多为 f 。

高为h的完全二叉树的结点数至少为 e ，至多为 f 。

a． 2h b. 2h-1c. 2h+1 d.h+1h-1hh+1he. 2 f. 2-1g. 2-1 h. 2+123.一棵有124个叶结点的完全二叉树，最多有b 个结点。

a. 247b. 248c. 249d. 25124.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是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(k+1)/2次30.在n个记录的有序顺序表中进行折半查找，最大的比较次数是?log2n??1。

32.在下述排序算法中，所需辅助存储空间最多的是b ，所需辅助存储空间最小的是c ，平均速度最快的是a 。

a.快速排序b. 归并排序c. 堆排序33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是a 。

a. 直接插入排序b. 冒泡排序c. 简单选择排序34.快速排序在最坏情况下时间复杂度是o(n)，比a 的性能差。

2a. 堆排序b. 冒泡排序c. 简单选择排序35.若需在o(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是c 。

a. 快速排序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,50b. 100,70,50,20,90,75,60,25,10,85,65,8038.若要尽可能快地完成对实数数组的排序，且要求排序是稳定的，则应选c 。

a. 快速排序b. 堆排序c. 归并排序d. 希尔排序39.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为a 排序法。

a. 插入排序b. 交换排序c. 选择排序d. 归并排序40.直接插入排序在最好情况下的时间复杂度为b 。

a. o(logn)b. o(n)2c. o(nlogn) d. o(n)46. 从未排序的序列中，依次取出元素，与已排序序列的元素比较后，放入已排序序列中的恰当位置上，这是(1) 排序。

从未排序的序列中，挑选出元素，放在已排序序列的某一端位置，这是(2) 排序。

逐次将待排序的序列中的相邻元素两两比较，凡是逆序则进行交换，这是(3) 排序。

如果整个排序过程都在内存中进行，称为 (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. 占用存储多少和处理的数据量大小答案：baaba47.操作系统是对计算机资源进行的(1) 系统软件，是(2) 的接口。

在处理机管理中，进程是一个重要的概念，它由程序块、(3) 和数据块三部分组成，它有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. cdromd. 寄存器答案：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;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. 分析算法的易懂性和文档性55.算法分析的两个主要方面是d 。

a. 间复杂性和时间复杂性b. 正确性和简明性c. 可读性和文档性d. 数据复杂性和程序复杂性56.一个线性顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址为b 。

a. 110b. 108c. 100d. 12057.若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3,?,pn，若p1=n，则pi为c 。

a. ib. n-ic. n-i+1d.不确定58.对于一个栈，给出输入项a,b,c。

如果输入项序列由a,b,c所组成，则不可能产生的输出序列是a 。

a. cabb. cbac. abcd. acb59.设有如下的单链表的按序号查找的算法，其时间复杂度为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【篇二：《计算机软件技术基础(第三版)》的课后答案】是信息？信息与数据的区别和联系在何处？信息定义之一：信息是现实世界中存在的客观实体、现象、关系进行描述的数据。

信息定义之二：信息是经过加工后并对实体的行为产生影响的数据。

与数据的区别和联系：数据定义：数据是现实世界客观存在的实体或事物的属性值，即指人们听到的事实和看到的景象。

我们把这些数据收集起来，经过处理后，即得到人们需要的信息。

信息和数据的关系可以归结为： 1. 信息是有一定含义的数据。

2. 信息是经过加工（处理）后的数据。