《计算机软件技术基础》复习题含答案（参考）.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! 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.以下 ABD 是C语言中”abcd321ABCD”的子串。 A. abcd B. 321AB C. “abcABC” D. “21AB” 20.若串S=”software”，其子串的数目是 B 。 A. 8 B. 37 C. 36 D. 9 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 ；前序遍历和后序遍历结果相同