计算机软件基础-常州工学院中国大学mooc课后章节答案期末考试题库2023年

计算机软件基础_常州工学院中国大学mooc课后章节答案期末考试题库2023年最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（)

参考答案:

rear=front

假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（)

参考答案:

(rear-front+m)%m

若入栈序列是a,b,c,d,e，则不可能的出栈序列是（）。

参考答案:

dceab

在二叉排序树中插入一个新的结点，那么它必定是叶子结点

参考答案:

正确

链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）

参考答案:

错误

已知一个顺序存储的有序表为（13，24，32，37，42，55，59，60，75，81）共10个元素，按折半查找算法，求其平均查找长度

参考答案:

2.9##%_YZPRLFH_%##29/10

用折半查找法的查找速度比用顺序查找法的查找速度_________.

参考答案:

快慢不定

适合折半查找的表的存贮方式及元素排列要求为()

参考答案:

顺序存贮

元素有序

一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动个元素。

参考答案:

n-i

向一个长度为n的的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素

参考答案:

n-i+1

在有n个元素的顺序表中删除一个元素，需要平均移动____个元素.

参考答案:

n/2##%_YZPRLFH_%##一半

栈和队列都是限制存取点的线性结构。

参考答案:

正确

一个栈的输入序列是12345,则栈的输出序列不可能是12345。

参考答案:

错误

队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。

参考答案:

错误

栈和队列逻辑上都是线性表。

参考答案:

正确

已知一组记录为(5948759786233760)，给出采用堆排序法，进行排序时的（1）建立的初始堆结果（2）第2趟的排序结果注意：2个答案之间用分号分隔,2，如：12345678;12345678

参考答案:

9786756059233748;7560374859238697##%_YZPRLFH_%##9786756059233748；7560374859238697##%_YZPRLFH_%##97867560592337487560374859238697

已知一组记录为(5948759786233760)，给出采用基数排序法，进行排序时的第1趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

6023758697374859

已知一组记录为(5948759786233760)，给出采用归并排序法，进行排序时的第2趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

4859759723376086

已知一组记录为(5948759786233760)，给出采用希尔排序法，且步长分别等于4，2，1时，进行排序时的第2趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

3723594875608697

已知一组记录为(4938659776132750)，给出采用插入排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

3849657697132750

已知一组记录为(4938659776132750)，给出采用直接选择排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

1327384976976550

已知一组记录为(4938659776132750)，给出采用冒泡排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

3813274950657697

已知一组记录为(4938659776132750)，给出采用快速排序法进行排序时的第一趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788

参考答案:

2738134976976550

线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上相邻。（）

参考答案:

正确

循环队列的人队操作应为()。

参考答案:

sq.rear=(sq.rear+1)%maxsize；

sq.data[sq.rear]=x；

对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

参考答案:

正确

链表的物理存储结构具有同链表一样的顺序。（）

参考答案:

错误

二叉判定树是一棵完全二叉树

参考答案:

错误

100个元素的有序表中，折半查找成功的最大查找长度为8

参考答案:

正确

执行折半查找法要求查找表必须为顺序结构的有序表。

参考答案:

正确

若采用链地址法解决冲突，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为（（2））

参考答案:

17_0至16

对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(  )。

参考答案:

O（log2(n)）

设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝KMOD16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，试回答下列问题：（1）若查找关键字63，需要依次与哪些关键字进行比较？（2）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。注意：（1）答案中数据之间全部用英文逗号分隔或全部用全角逗号分隔，不能加空格，数字及除号用半角英文格式（2）2个题之间用分号分隔答案格式如：3，4；2/5

参考答案:

31，46，47，32，17，63；21/11##%_YZPRLFH_%##31,46,47,32,17,63;21/11

折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

参考答案:

20，70，30，50

若已知一个栈的入栈序列是1，2，3，，，，n，其输出序列为pl，p2，p3，„，pn，若p1=n，则pi为（）

参考答案:

n-i+1

折半查找有序表（4、6、12、20、28、38、50、70、88、100），若查找表中元素20，它将依次与表中元素（）比较大小。注意：答案中数据之间全部用英文逗号分隔或全部用全角逗号分隔，不能加空格，数字用半角英文格式

参考答案:

28,6,12,20##%_YZPRLFH_%##28，6，12，20

对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(  )。

参考答案:

4

折半搜索与二叉搜索树的时间性能（）

参考答案:

数量级都是O（log2n）

对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(  )。

参考答案:

25/9

将10个元素散列到100000个单元的哈希表中，则（    ）产生冲突。

参考答案:

仍可能会

栈和队列是一种非线性数据结构

参考答案:

错误

若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(  )。

参考答案:

（n+1）/2

假设用一维数组变量sq[0..n-1]实现循环队列，front和rear分别是队头和队尾指针，则出队的操作是（）。

参考答案:

sq.front=(sq.ftont+1)%maxsize

对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(  )。

参考答案:

4

顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）

参考答案:

错误

一个顺序表第一个元素的顺序存储地址是100，每个元素的长度为2，则第5个元素的地址是（）

参考答案:

108

在对有二十个数据有序表作二分查找时有___________个结点的查找长度是4

参考答案:

8

数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）

参考答案:

顺序存储结构

顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）

参考答案:

错误

在二叉排序树中插入一个结点，总是插入到叶子结点的下面

参考答案:

错误

二叉树中每个结点的两棵子树的高度差等于1

参考答案:

错误

二叉树中每个结点的两棵子树是有序的

参考答案:

正确

二叉树中每个结点有两棵非空子树或有2棵空子树

参考答案:

错误

树中的结点和图中的顶点就是指数据结构中的数据元素

参考答案:

正确

连通图上各边权值均不相同，则该图的最小生成树是唯一的。

参考答案:

正确

不同的求最小生成树的方法最后得到的生成树是相同的.

参考答案:

错误

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。

参考答案:

正确

邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它

参考答案:

错误

无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

参考答案:

错误

有n个顶点