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

《《计算机软件技术基础》复习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机软件技术基础》试题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，平均每删除一个元素需

2、要移动的元素个数为A；若元素插在ai与ai+1之间(0≤I≤n-1)的概率为，则平均每插入一个元素所要移动的元素个数为C；A.B.C.D.5.下列函数中，按它们在时的无穷大阶数，最大的是D。A.lognB.nlognC.2n/2D.n!spnextnextnext6.将下图所示的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->ne

3、xt=s;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是A。A.nB.2n-1C.n-1D.2n13.用单链表表示的链式队列的队头在链表的A位置。A.链头B.链尾C.链中14.若用单链表表示队列，则应该选用B。26A.带尾指针的非循环链表B.带尾指针的循环链表C.带头指针的非循环链表D.带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个B结构。A.堆栈B.队列C.

4、数组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不可能是其出栈序列。A．1243B.2134C.1432D.431219.以下D是C语言中”abcd321ABCD”的子串。A.abcdB.321ABC.“abcABC”

5、D.“21AB”20.若串S=”software”，其子串的数目是C。A.8B.37C.36D.921.将一个A[1:100,1:100]的三对角矩阵，按行优先存入一维数组B[1:298]中，A中元素A66,65(即该元素的下标)在B数组中位置k为B。A.198B.195C.197D.19622.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为B，至多为F。高为h的完全二叉树的结点数至少为E，至多为F。A．2hB.2h-1C.2h+1D.h+1E.2h-1F.2h-1G.2h+1-1H.2h+123.一棵有124个叶结点的完全二叉树，最

6、多有B个结点。A.247B.248C.249D.25124.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是C。A.满二叉树B.哈夫曼树C.堆D.二叉查找树25.前序遍历和中序遍历结果相同的二叉树为F；前序遍历和后序遍历结果相同的二叉树为B。A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树27.若在线性表中采用折半查找法查找元素，该线性表应该C。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构D.元

7、素按值有序，且采用链式存储结构28.在分块检索中，对256个元素的线性表分成16块最好，每块的最佳长度是16；若每块的长度为8，其平均检索长度为21。29.假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行D次探测。26A.K-1次B.K次C.K+1次D.K(K+1)/2次30.在n个记录的有序顺序表中进行折半查找，最大的比较次数是。31.Hash技术广泛应用于查找过程，选择Hash函数的标准是和。处理冲突的技术有优有劣，其共同标准是。32.在下述排序算法中，所需辅助存储空间最多的是B，所需辅助存储空间最小的是C，平均速度

8、最快的是A。A.快速排序B.归并排序C.堆排序33.在文件局部有序或文件长度较小的情况下，最佳