《计算机软件技术基础复习题和答案》由会员分享，可在线阅读，更多相关《计算机软件技术基础复习题和答案（28页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础试题2.线性表是具有n个 C 的有限序列。A. 表元素B. 字符C. 数据元素D. 数据项E. 信息项1.线性表的链式存储结构与顺序存储结构相比优点是 CD 。A. 所有的操作算法实现简单B. 便于随机存取C. 便于插入和删除D. 便于利用零散的存储器空间3.若长度为n的线性表采用顺序存储结构，在其第I个位置插入一个新元素的算法的时间复杂度为 C 。（1In+1）A. O(0)B. O(1)C. O(n)D. O(n2)4.设A是一个线性表(a1,a2,an)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为 B ，平均每删除一个元素需要移动的元素
2、个数为 A ；若元素插在ai与ai+1之间(0In-1)的概率为，则平均每插入一个元素所要移动的元素个数为 C ；A. B. C. D. 5.下列函数中，按它们在时的无穷大阶数，最大的是 D 。A. lognB. nlognC. 2n/2D. n!7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是 A 。A. nB. 2n-1C. n-1D. 2n8.下面的程序段是合并两个无头结点链表(ha和 hb)为一个无头结点链表ha的过程，作为参数的两个链表都是按结点的data域由大到小链接的。合并后新链表的结点仍按此方式链接。请填写下述空框，使程序能正确运行。spnextnextne
3、xt6.将下图所示的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;13.用单链表表示的链式队列的队头在链表的 A 位置。A. 链头B. 链尾C. 链中14.若用单链表表示队列，则应该选用 B 。A. 带尾指针的非循环链表B. 带尾指针的循环链表C. 带头指针的非循环链表D. 带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一
4、个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个 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，输出序列为a1,a2,a10，若a5=10，则a7为 C 。A. 4B. 8C.不确定D.718.设栈的输入序列是1,2,3,4，则 D 不可能是其出栈
5、序列。A 1243B. 2134C. 1432D. 431219.以下 D 是C语言中”abcd321ABCD”的子串。A. abcdB. 321ABC. “abcABC”D. “21AB”20.若串S=”software”，其子串的数目是 C 。A. 8B. 37C. 36D. 921.将一个A1:100,1:100的三对角矩阵，按行优先存入一维数组B1:298中，A中元素A66,65(即该元素的下标)在B数组中位置k为 B 。A. 198B. 195C. 197D. 19622.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为 B ，至多为 F 。高为h的完全二叉树的结点数
6、至少为 E ，至多为 F 。A 2hB. 2h-1C. 2h+1D.h+1E. 2h-1F. 2h-1G. 2h+1-1H. 2h+123.一棵有124个叶结点的完全二叉树，最多有 B 个结点。A. 247B. 248C. 249D. 25124.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。A. 满二叉树B. 哈夫曼树C. 堆D. 二叉查找树25.前序遍历和中序遍历结果相同的二叉树为 F ；前序遍历和后序遍历结果相同的二叉树为 B 。A. 一般二叉树B. 只有根结点的二叉树C. 根结点无左孩子的二叉树D. 根结点无右孩子的二叉树E. 所有结点只有左孩
7、子的二叉树F. 所有结点只有右孩子的二叉树27.若在线性表中采用折半查找法查找元素，该线性表应该 C 。A. 元素按值有序B. 采用顺序存储结构C. 元素按值有序，且采用顺序存储结构D. 元素按值有序，且采用链式存储结构28.在分块检索中，对256个元素的线性表分成 16 块最好，每块的最佳长度是 16 ；若每块的长度为8，其平均检索长度为 21 。29.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行 D 次探测。A. K-1次B. K次C. K+1次D. K(K+1)/2次30.在n个记录的有序顺序表中进行折半查找，最大的比较次数是。31.Hash技术广泛应
8、用于查找过程，选择Hash函数的标准是 和 。处理冲突的技术有优有劣，其共同标准是 。32.在下述排序算法中，所需辅助存储空间最多的是 B ，所需辅助存储空间最小的是 C ，平均速度最快的是 A 。A.快速排序B. 归并排序C. 堆排序33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是 A 。A. 直接插入排序B. 冒泡排序C. 简单选择排序34.快速排序在最坏情况下时间复杂度是O(n2)，比 A 的性能差。A. 堆排序B. 冒泡排序C. 简单选择排序35.若需在O(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是 C 。A. 快速排序B. 堆排序C
9、. 归并排序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.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已
10、排序序列的合适位置，该排序方法称为 A 排序法。A. 插入排序B. 交换排序C. 选择排序D. 归并排序40.直接插入排序在最好情况下的时间复杂度为 B 。A. O(logn)B. O(n)C. O(nlogn)D. O(n2)41.表是一种数据结构，链表是一种 (1) 。队列和栈都是线性表，栈的操作特性是 (2) ，队列的操作特性是 (3) 。今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进栈、进栈、出栈、进栈、进栈、出栈的操作，则此操作完成后，栈S的栈顶元素为 (4) ，栈底元素为 (5) 。供选答案：(1):A. 非顺序存储线性表B. 非顺序存储非线性表C. 顺序存储
11、线性表D. 顺序存储非线性表(2):A. 随机进出B. 先进后出C. 先进先出D. 出优于进(3):A. 随机进出B. 先进后出C. 后进后出D. 进优于出(4):A. fB. cC. aD. b(5):A. bB. cC. aD. d答案：ABCBC42.操作系统主要是对计算机系统全部 (1) 进行管理，以方便用户、提高计算机使用效率的一种系统软件。它的主要功能有：处理机管理、存储管理、文件管理、 (2) 管理和设备管理等。Windows和Unix是最常用的两类操作系统。前者是一个具有图形界面的窗口式的 (3) 系统软件，后者是一个基本上采用 (4) 语言编制而成的的系统软件。在 (5) 操
12、作系统控制下，计算机能及时处理由过程控制反馈的信息并作出响应。供选答案：(1):A. 应用软件B. 系统软硬件C. 资源D. 设备(2):A. 数据B. 作业C. 中断D. I/O(3):A. 分时B. 多任务C. 多用户D. 实时(4):A. PASCALB. 宏C. 汇编D. C(5):A. 网络B. 分时C. 批处理D. 实时答案：CBBDD44.计算机数据处理的对象是具有不同结构的各种数据，可以访问的最小数据信息单位是 (1) ，可以引用的最小命名数据单位是 (2) 。线性表是最简单的一种数据结构，有顺序和链接两种存储方式。线性表按链接方式存储时，每个结点的包括 (3) 两部分。线性表的查找有 (4) 和 (5) 两种，但 (5) 只能用于顺序存储的情况。供选答案：(1):A. 数字B.
