《计算机软件技术基础》复习题答案.doc

《计算机软件技术基础》试题
1.线性表的链式存储结构与顺序存储结构相比优点是CD。
A.所有的操作算法实现简单 B.便于随机存取
C.便于插入和删除 D.便于利用零散的存储器空间
2.线性表是具有n个C的有限序列。
A.表元素 B.字符 C.数据元素
D.数据项 E.信息项
3.若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为C。（1≤I≤n+1）
A.O(0) B.O(1)
C.O(n) D.O(n2)
4.设A是一个线性表(a1,a2,…,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为B，平均每删除一个元素需要移动的元素个数为A；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为，则平均每插入一个元素所要移动的元素个数为C；
A. B.
C. D.
5.下列函数中，按它们在时的无穷大阶数，最大的是D。
A.logn B.nlogn
C.2n/2 D.n!
s
p
next
next
next
6.将下图所示的s所指结点加到p所指的结点之后，其语句应为：D。
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 B.2n-1
C.n-1 D.2n

13.用单链表表示的链式队列的队头在链表的A位置。
A.链头 B.链尾 C.链中
14.若用单链表表示队列，则应该选用B。
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，输出序列为a1,a2,…,a10，若a5=10，则a7为C。
A.4 B.8 C.不确定 D.7
18.设栈的输入序列是1,2,3,4，则D不可能是其出栈序列。
A．1243 B.2134 C.1432 D.4312
19.以下D是C语言中”abcd321ABCD”的子串。
A.abcd B.321AB C.“abcABC” D.“21AB”
20.若串S=”software”，其子串的数目是C。
A.8 B.37 C.36 D.9
21.将一个A[1:100,1:100]的三对角矩阵，按行优先存入一维数组B[1:298]中，A中元素A66,65(即该元素的下标)在B数组中位置k为B。
A.198 B.195 C.197 D.196
22.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B，至多为F。高为h的完全二叉树的结点数至少为E，至多为F。
A．2h B.2h-1 C.2h+1 D.h+1
E.2h-1 F.2h-1 G.2h+1-1 H.2h+1
23.一棵有124个叶结点的完全二叉树，最多有B个结点。
A.247 B.248 C.249 D.251
24.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。
A.满二叉树 B.哈夫曼树
C.堆 D.二叉查找树
25.前序遍历和中序遍历结果相同的二叉树为F；前序遍历和后序遍历结果相同的二叉树为B。
A.一般二叉树 B.只有根结点的二叉树
C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树
E.所有结点只有左孩子的二叉树 F.所有结点只有右孩子的二叉树
27.若在线性表中采用折半查找法查找元素，该线性表应该C。
A.元素按值有序 B.采用顺序存储结构
C.元素按值有序，且采用顺序存储结构 D.元素按值有序，且采用链式存