【MOOC】计算机软件基础-常州工学院 中国大学慕课MOOC答案

【MOOC】计算机软件基础-常州工学院中国大学慕课MOOC答案线性表单元测验1、【单选题】数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）本题答案：【顺序存储结构】2、【单选题】一个顺序表第一个元素的顺序存储地址是100，每个元素的长度为2，则第5个元素的地址是（）本题答案：【108】3、【单选题】循环队列的人队操作应为()。本题答案：【sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；】4、【单选题】假设用一维数组变量sq[0..n-1]实现循环队列，front和rear分别是队头和队尾指针，则出队的操作是（）。本题答案：【sq.front=(sq.ftont+1)%maxsize】5、【单选题】若已知一个栈的入栈序列是1，2，3，，，，n，其输出序列为pl，p2，p3，?，pn，若p1=n，则pi为（）本题答案：【n-i+1】6、【单选题】若入栈序列是a,b,c,d,e，则不可能的出栈序列是（）。本题答案：【dceab】7、【单选题】假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（)本题答案：【(rear-front+m)%m】8、【单选题】最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（)本题答案：【rear=front】9、【判断题】顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）本题答案：【错误】10、【判断题】顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）本题答案：【错误】11、【判断题】链表的物理存储结构具有同链表一样的顺序。（）本题答案：【错误】12、【判断题】链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）本题答案：【错误】13、【判断题】线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上相邻。（）本题答案：【正确】14、【判断题】栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。本题答案：【正确】15、【判断题】对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。本题答案：【正确】16、【判断题】栈和队列是一种非线性数据结构本题答案：【错误】17、【判断题】栈和队列的存储方式既可是顺序方式，也可是链接方式。本题答案：【正确】18、【判断题】队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。本题答案：【错误】19、【判断题】一个栈的输入序列是12345,则栈的输出序列不可能是12345。本题答案：【错误】20、【判断题】栈和队列逻辑上都是线性表。本题答案：【正确】21、【判断题】栈和队列都是限制存取点的线性结构。本题答案：【正确】22、【填空题】在有n个元素的顺序表中删除一个元素，需要平均移动____个元素.本题答案：【n/2##%_YZPRLFH_%##一半】23、【填空题】向一个长度为n的的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素本题答案：【n-i+1】24、【填空题】一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动个元素。本题答案：【n-i】树和二叉树单元测验1、【单选题】不含任何结点的空树本题答案：【是一棵树也是一棵二叉树】2、【单选题】二叉树是非线性数据结构，所以本题答案：【顺序存储结构和链式存储结构都能存储】3、【单选题】具有n(n0)个结点的完全二叉树的深度为本题答案：【?log2(n)?+1】4、【单选题】假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为本题答案：【16】5、【单选题】按照二叉树的定义，具有3个结点的不同形状的二叉树有______种本题答案：【5】6、【单选题】按照树的定义，具有3个不同数据结点的不同的树有几种？本题答案：【2】7、【单选题】深度为7的二叉树至多有_____个结点本题答案：【127】8、【单选题】任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序本题答案：【不发生改变】9、【单选题】某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是本题答案：【gdbehfca】10、【单选题】在一非空二叉树的中序遍历序列中，根结点的右边本题答案：【只有右子树上的所有结点】11、【判断题】二叉树中每个结点的两棵子树的高度差等于1本题答案：【错误】12、【判断题】二叉树中每个结点的两棵子树是有序的本题答案：【正确】13、【判断题】二叉树中每个结点有两棵非空子树或有2棵空子树本题答案：【错误】14、【判断题】本题答案：【错误】15、【判断题】具有20个结点的完全二叉树有9个度为2的结点本题答案：【正确】16、【判断题】二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树本题答案：【错误】17、【判断题】二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法本题答案：【正确】18、【填空题】写出下面这棵二叉树的先序遍历本题答案：【FBADCEGIH】19、【填空题】写出下面这棵二叉树的中序遍历本题答案：【ABCDEFGHI】20、【填空题】写出下面这棵二叉树的后序遍历本题答案：【ACEDBHIGF】21、【填空题】写出下面这棵二叉树的先序遍历本题答案：【ABDEGCF】22、【填空题】写出下面这棵二叉树的中序遍历本题答案：【DBGEACF】23、【填空题】写出下面这棵二叉树的后序遍历本题答案：【DGEBFCA】24、【填空题】假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{a(0.07)，b(0.19)，c(0.02)，d(0.06)，e(0.32)，f(0.03)，g(0.21)，h(0.10)}。试构造哈夫曼编码，问：每个字符的编码长度是多少？答案格式为：a?b?c?d?e?f?g?h?问号改为相应的字符编码长度本题答案：【a4b2c5d4e2f5g2h4】25、【填空题】按423056702580365060754590这样的顺序输入构造一个二叉排序树，问：元素305060708090各在二叉树的第几层？注：答案中不要有空格和换行本题答案：【234345】图单元测验1、【单选题】图中有关路径的定义是（）本题答案：【由顶点和相邻顶点序偶构成的边所形成的序列】2、【单选题】设无向图的顶点个数为n，则该图最多有（）条边。本题答案：【n(n-1)/2】3、【单选题】—个n个顶点的连通无向图，其边的个数至少为（）本题答案：【n-1】4、【单选题】要连通具有n个顶点的有向图，至少需要（）条边。本题答案：【n】5、【单选题】n个结点的完全有向图含有边的数目（）本题答案：【n*(n-1)】6、【单选题】在一个无向图中，所有顶点的度数之和等于所有边数（）倍本题答案：【2】7、【单选题】在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍本题答案：【1】8、【单选题】下列说法不正确的是（）本题答案：【图的深度遍历不适用于有向图】9、【单选题】无向图G=（V，E),其中：V={a,b,c,d,e,f}，E={（a,b），（a,e），（a,c），（b,e），（c,f），（f,d），（e,d）}，对该图进行深度优先遍历，得到的顶点序列正确的是（）本题答案：【a,e,d,f,c,b】10、【单选题】关键路径是是事件结点网络中（）本题答案：【从源点到汇点的最长路径】11、【判断题】有e条边的无向图，在邻接表中有e个结点本题答案：【错误】12、【判断题】有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数本题答案：【错误】13、【判断题】强连通图的各顶点间均可达本题答案：【正确】14、【判断题】有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。本题答案：【正确】15、【判断题】无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。本题答案：【错误】16、【判断题】邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它本题答案：【错误】17、【判断题】用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。本题答案：【正确】18、【判断题】不同的求最小生成树的方法最后得到的生成树是相同的.本题答案：【错误】19、【判断题】连通图上各边权值均不相同，则该图的最小生成树是唯一的。本题答案：【正确】20、【判断题】树中的结点和图中的顶点就是指数据结构中的数据元素本题答案：【正确】查找单元测验1、【单选题】用折半查找法的查找速度比用顺序查找法的查找速度_________.本题答案：【快慢不定】2、【单选题】适合折半查找的表的存贮方式及元素排列要求为()本题答案：【顺序存贮元素有序】3、【单选题】折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。本题答案：【20，70，30，50】4、【单选题】折半搜索与二叉搜索树的时间性能（）本题答案：【数量级都是O（log2n）】5、【单选题】将10个元素散列到100000个单元的哈希表中，则（????）产生冲突。本题答案：【仍可能会】6、【单选题】若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(??)。本题答案：【（n+1）/2】7、【单选题】对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(??)。本题答案：【25/9】8、【单选题】对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(??)。本题答案：【4】9、【单选题】对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(??)。本题答案：【4】10、【单选题】对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(??)。本题答案：【O（log2(n)）】11、【多选题】若采用链地址法解决冲突，散列函数为H（key）=key?MOD?17，则需?(（1）)?个链表。这些链的链首指针构成一个指针数组，数组的下标范围为（（2））H、1至17本题答案：【17#0至16】12、【判断题】执行折半查找法要求查找表必须为顺序结构的有序表。本题答案：【正确】13、【判断题】100个元素的有序表中，折半查找成功的最大查找长度为8本题答案：【正确】14、【判断题】二叉判定树是一棵完全二叉树本题答案：【错误】15、【判断题】在二叉排序树中插入一个结点，总是插入到叶子结点的下面本题答案：【错误】16、【判断题】在二叉排序树中插入一个新的结点，那么它必定是叶子结点本题答案：【正确】17、【填空题】在对有二十个数据有序表作二分查找时有___________个结点的查找长度是4本题答案：【8】18、【填空题】折半查找有序表（4、6、12、20、28、38、50、70、88、100），若查找表中元素20，它将依次与表中元素（）比较大小。注意：答案中数据之间全部用英文逗号分隔或全部用全角逗号分隔，不能加空格，数字用半角英文格式本题答案：【28,6,12,20##%_YZPRLFH_%##28，6，12，20】19、【填空题】设哈希（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】20、【填空题】已知一个顺序存储的有序表为（13，24，32，37，42，55，59，60，75，81）共10个元素，按折半查找算法，求其平均查找长度本题答案：【2.9##%_YZPRLFH_%##29/10】排序单元测验1、【填空题】已知一组记录为(4938659776132750)，给出采用快速排序法进行排序时的第一趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788本题答案：【2738134976976550】2、【填空题】已知一组记录为(4938659776132750)，给出采用冒泡排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788本题答案：【3813274950657697】3、【填空题】已知一组记录为(4938659776132750)，给出采用直接选择排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788本题答案：【1327384976976550】4、【填空题】已知一组记录为(4938659776132750)，给出采用插入排序法进行排序时的第4趟的排序结果格式要求：数字之间用空格分隔，如：1122334455667788本题答案：【3849657697132750】5、【填空题】已知一组记录为(5948759786233760)，给出采用希尔排序法，且步长分别等于4，2，1