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

MOOC计算机软件基础-常州工学院中国大学慕课答案线性表单元测验1、问题：数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）选项：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构正确答案:【顺序存储结构】2、问题：一个顺序表第一个元素的顺序存储地址是100，每个元素的长度为2，则第5个元素的地址是（）选项：A、110B、108C、100D、120正确答案:【108】3、问题：循环队列的人队操作应为()。选项：A、sq.rear=sq.rear+1；sq.data[sq.rear]=x；B、sq.data[sq.rear]=x；sq.rear=sq.rear+1；C、sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；D、sq.data[sq.rear]=x；sq.rear=(sq.rear+1)%maxsize；正确答案:【sq.rear=(sq.rear+1)%maxsize；sq.data[sq.rear]=x；】4、问题：假设用一维数组变量sq[0..n-1]实现循环队列，front和rear分别是队头和队尾指针，则出队的操作是（）。选项：A、sq.front=(sq.ftont+1)%maxsizeB、sq.front=sq.front+1C、sq.rear=（sq.rear+1）%maxsizeD、sq.rear=sq.rear+1正确答案:【sq.front=(sq.ftont+1)%maxsize】5、问题：若已知一个栈的入栈序列是1，2，3，，，，n，其输出序列为pl，p2，p3，?，pn，若p1=n，则pi为（）选项：A、iB、n-iC、n-i+1D、不确定正确答案:【n-i+1】6、问题：若入栈序列是a,b,c,d,e，则不可能的出栈序列是（）。选项：A、edcbaB、decbaC、dceabD、abcde正确答案:【dceab】7、问题：假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为（)选项：A、(rear-front+m)%mB、rear-front+1C、(front-rear+m)%mD、(rear-front)%m正确答案:【(rear-front+m)%m】8、问题：最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（)选项：A、(rear+l)MODn=frontB、rear=frontC、rear+l=frontD、(rear-1)MODn=front正确答案:【rear=front】9、问题：顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）选项：A、正确B、错误正确答案:【错误】10、问题：顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）选项：A、正确B、错误正确答案:【错误】11、问题：链表的物理存储结构具有同链表一样的顺序。（）选项：A、正确B、错误正确答案:【错误】12、问题：链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（）选项：A、正确B、错误正确答案:【错误】13、问题：线性表在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上相邻。（）选项：A、正确B、错误正确答案:【正确】14、问题：栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。选项：A、正确B、错误正确答案:【正确】15、问题：对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。选项：A、正确B、错误正确答案:【正确】16、问题：栈和队列是一种非线性数据结构选项：A、正确B、错误正确答案:【错误】17、问题：栈和队列的存储方式既可是顺序方式，也可是链接方式。选项：A、正确B、错误正确答案:【正确】18、问题：队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。选项：A、正确B、错误正确答案:【错误】19、问题：一个栈的输入序列是12345,则栈的输出序列不可能是12345。选项：A、正确B、错误正确答案:【错误】20、问题：栈和队列逻辑上都是线性表。选项：A、正确B、错误正确答案:【正确】21、问题：栈和队列都是限制存取点的线性结构。选项：A、正确B、错误正确答案:【正确】22、填空题：在有n个元素的顺序表中删除一个元素，需要平均移动____个元素.正确答案:【n/2##%_YZPRLFH_%##一半】23、填空题：向一个长度为n的的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素正确答案:【n-i+1】24、填空题：一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动个元素。正确答案:【n-i】树和二叉树单元测验1、问题：不含任何结点的空树选项：A、是一棵树B、是一棵二叉树C、是一棵树也是一棵二叉树D、既不是树也不是二叉树正确答案:【是一棵树也是一棵二叉树】2、问题：二叉树是非线性数据结构，所以选项：A、它不能用顺序存储结构存储B、它不能用链式存储结构存储C、顺序存储结构和链式存储结构都能存储D、顺序存储结构和链式存储结构都不能使用正确答案:【顺序存储结构和链式存储结构都能存储】3、问题：具有n(n0)个结点的完全二叉树的深度为选项：A、log2(n)B、?log2(n)?C、?log2(n)?+1D、log2(n)+1正确答案:【?log2(n)?+1】4、问题：假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为选项：A、15B、16C、17D、47正确答案:【16】5、问题：按照二叉树的定义，具有3个结点的不同形状的二叉树有______种选项：A、3B、4C、5D、6正确答案:【5】6、问题：按照树的定义，具有3个不同数据结点的不同的树有几种？选项：A、2B、3C、4D、5正确答案:【2】7、问题：深度为7的二叉树至多有_____个结点选项：A、64B、128C、127D、14正确答案:【127】8、问题：任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序选项：A、不发生改变B、发生改变C、不能确定D、以上都不对正确答案:【不发生改变】9、问题：某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是选项：A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca正确答案:【gdbehfca】10、问题：在一非空二叉树的中序遍历序列中，根结点的右边选项：A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点正确答案:【只有右子树上的所有结点】11、问题：二叉树中每个结点的两棵子树的高度差等于1选项：A、正确B、错误正确答案:【错误】12、问题：二叉树中每个结点的两棵子树是有序的选项：A、正确B、错误正确答案:【正确】13、问题：二叉树中每个结点有两棵非空子树或有2棵空子树选项：A、正确B、错误正确答案:【错误】14、问题：选项：A、正确B、错误正确答案:【错误】15、问题：具有20个结点的完全二叉树有9个度为2的结点选项：A、正确B、错误正确答案:【正确】16、问题：二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树选项：A、正确B、错误正确答案:【错误】17、问题：二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法选项：A、正确B、错误正确答案:【正确】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、问题：图中有关路径的定义是（）选项：A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不是正确答案:【由顶点和相邻顶点序偶构成的边所形成的序列】2、问题：设无向图的顶点个数为n，则该图最多有（）条边。选项：A、n-1B、n(n-1)/2C、n(n+1)/2D、n正确答案:【n(n-1)/2】3、问题：—个n个顶点的连通无向图，其边的个数至少为（）选项：A、n-1B、nC、n+1D、nlogn正确答案:【n-1】4、问题：要连通具有n个顶点的有向图，至少需要（）条边。选项：A、n-1B、nC、n+1D、2n正确答案:【n】5、问题：n个结点的完全有向图含有边的数目（）选项：A、n*nB、n(n+1)C、n/2D、n*(n-1)正确答案:【n*(n-1)】6、问题：在一个无向图中，所有顶点的度数之和等于所有边数（）倍选项：A、1/2B、2C、1D、4正确答案:【2】7、问题：在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍选项：A、1/2B、2C、1D、4正确答案:【1】8、问题：下列说法不正确的是（）选项：A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、遍历的基本算法有两种：深度遍历和广度遍历C、图的深度遍历不适用于有向图D、图的深度遍历是一个递归过程正确答案:【图的深度遍历不适用于有向图】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、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b正确答案:【a,e,d,f,c,b】10、问题：关键路径是是事件结点网络中（）选项：A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路正确答案:【从源点到汇点的最长路径】11、问题：有e条边的无向图，在邻接表中有e个结点选项：A、正确B、错误正确答案:【错误】12、问题：有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数选项：A、正确B、错误正确答案:【错误】13、问题：强连通图的各顶点间均可达选项：A、正确B、错误正确答案:【正确】14、问题：有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。选项：A、正确B、错误正确答案:【正确】15、问题：无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。选项：A、正确B、错误正确答案:【错误】16、问题：邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它选项：A、正确B、错误正确答案:【错误】17、问题：用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。选项：A、正确B、错误正确答案:【正确】18、问题：不同的求最小生成树的方法最后得到的生成树是相同的.选项：A、正确B、错误正确答案:【错误】19、问题：连通图上各边权值均不相同，则该图的最小生成树是唯一的。选项：A、正确B、错误正确答案:【正确】20、问题：树中的结点和图中的顶点就是指数据结构中的数据元素选项：A、正确B、错误正确答案:【正确】查找单元测验1、问题：用折半查找法的查找速度比用顺序查找法的查找速度_________.选项：A、必然慢B、必然快C、速度相等D、快慢不定正确答案:【快慢不定】2、问题：适合折半查找的表的存贮方式及元素排列要求为()选项：A、链式存贮元素无序B、链式存贮元素有序C、顺序存贮元素无序D、顺序存贮元素有序正确答案:【顺序存贮元素有序】3、问题：折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。选项：A、20，70，30，50B、30，88，70，50C、20，50D、30，88，50正确答案:【20，70，30，50】4、问题：折半搜索与二叉搜索树的时间性能（）选项：A、相同B、完全不同C、有时不相同D、数量级都是O（log2n）正确答案:【数量级都是O（log2n）】5、问题：将10个元素散列到100000个单元的哈希表中，则（????）产生冲突。选项：A、一定会B、一定不会C、仍可能会D、以上都不对正确答案:【仍可能会】6、问题：若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为(??)。选项：A、nB、n+1C、（n-1）/2D、（n+1）/2正确答案:【（n+1）/2】7、问题：对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为(??)。选项：A、20/9B、18/9C、25/9D、22/9正确答案:【25/9】8、问题：对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为(??)。选项：A、3B、4C、5D、6正确答案:【4】9、问题：对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为(??)。选项：A、2B、3C、4D、5正确答案:【4】10、问题：对具有n个元素的有序表采用折半查找，则算法的时间复杂度为(??)。选项：A、O(n)B、O()C、O（1）D、O（log2(n)）正确答案:【O（log2(n)）】11、问题：若采用链地址法解决冲突，散列函数为H（key）=key?MOD?17，则需?(（1）)?个链表。这些链的链首指针构成一个指针数组，数组的下标范围为（（2））选项：A、13B、16C、17D、任意E、0至16F、1至16G、0至17H、1至17正确答案:【17#0至16】12、问题：执行折半查找法要求查找表必须为顺序结构的有序表。选项：A、正确B、错误正确答案:【正确】13、问题：100个元素的有序表中，折半查找成功的最大查找长度为8选项：A、正确B、错误正确答案:【正确】14、问题：二叉判定树是一棵完全二叉树选项：A、正确B、错误正确答案:【错误】15、问题：在二叉排序树中插入一个结点，总是插入到叶子结点的下面选项：A、正确B、错误正确答案:【错误】16、问题：在二叉排序树中插入一个新的结点，那么它必定是叶子结点选项：A、正确B、错误正确答案:【正确】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、填空题：已知一