资源描述：
《计算机软件技术基础课后答案.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、计算机软件技术基础课后答案【篇一：《计算机软件技术基础》复习题(含答案)】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)，采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需
2、要移动的元素个数为b，平均每删除一个元素需要移动的元素个数为a；若元素插在ai与ai+1之间(0≤i≤n-1)的概率为元素所要移动的元素个数为c；2(n?i)，则平均每插入一个n(n?1)n?122n?1c.3a.n23n?1d.4b.5.下列函数中，按它们在n??时的无穷大阶数，最大的是d。a.lognb.nlognn/2c.2d.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
3、;7.将两个各有n个元素的有序表归并为一个有序表时，其最少的比较次数是a。a.nc.n-1b.2n-1d.2n13.用单链表表示的链式队列的队头在链表的a位置。a.链头b.链尾c.链中14.若用单链表表示队列，则应该选用。a.带尾指针的非循环链表b.带尾指针的循环链表c.带头指针的非循环链表d.带头指针的循环链表15.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印，先放入打印缓冲区的数据先被打印。该缓冲区应该是一个b结构。a.堆栈b.队列c.数组d.线性表16.
4、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为b。a.1和5b.2和4c.4和2d.5和117.设栈的输入序列为1,2，?,10，输出序列为a,a,?,a，若a=10，则a为c。（未要求一次性全部输入或输出）a.4b.8c.不确定d.718.设栈的输入序列是1,2,3,4，则d不可能是其出栈序列。a．1243b.2134c.1432d.431219.以下abd是c语言中”abcd321abcd”的子串。a.abcdb.321abc.“abcabc”d.
5、“21ab”20.若串s=”software”，其子串的数目是。a.8b.37c.36d.922.设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为b，至多为f。高为h的完全二叉树的结点数至少为e，至多为f。a．2hb.2h-1c.2h+1d.h+1h-1hh+1he.2f.2-1g.2-1h.2+123.一棵有124个叶结点的完全二叉树，最多有b个结点。a.247b.248c.249d.25124.若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是c。（记）a.满二叉树c.堆b.哈夫曼树d.二叉查找树25.前序遍
6、历和中序遍历结果相同的二叉树为；前序遍历和后序遍历结果相同的二叉树为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
7、.归并排序c.堆排序33.在文件局部有序或文件长度较小的情况下，最佳内部排序的方法是a。a.直接插入排序b.冒泡排序c.简单选择排序34.快速排序在最坏情况下时间复杂度是o(n)，比a的性能差。2a.堆排序b.冒泡排序c.简单选择排序35.若需在o(nlogn)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是c。a.快速排序b.堆排序c.归并排序d.希尔排序36.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用b方法最快。a.冒泡排序b.快速排序c.希尔排序d.堆排序e.简单选择排序37.以下结点序列是堆的为a。
8、a.100,90,80,60,85,75,20,25
