计算机软件技术基础课后答案
【篇一：《计算机软件技术基础》复习题(含答案)】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 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-next;
d. s-next=p-next; p-next=s;
7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 a 。
a. n
c. n-1
b. 2n-1 d. 2n
13.用单链表表示的链式队列的队头在链表的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和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. 8
c.不确定
d.7
18.设栈的输入序列是1,2,3,4，则d 不可能是其出栈序列。
a． 1243b. 2134c. 1432 d. 4312
19.以下 abd 是c语言中”abcd321abcd”的子串。
a. abcd
b. 321ab
c. “abcabc”
d. “21ab”
20.若串s=”software”，其子串的数目是。
a. 8
b. 37
c. 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. 248
c. 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(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. 快速排序
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.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为a 排序法。
a. 插入排序
b. 交换排序
