2023年数据结构与算法在线作业答案

单选题１.邻接表是图的一种_＿_＿。A顺序存储结构B链式存储结构C索引存储结构D散列存储结构单选题２.具有5个顶点的有向完全图有_＿＿＿条弧。A10B１６Ｃ２０Ｄ２５单选题３.链表不具有的特点是＿__＿_。A可随机访问任一元素B插入和删除不需要移动元素C不必事先估计存储空间D所需空间和线性表长度成正比单选题4.作进栈操作时,应先判断栈是否为_____。Ａ空B满C上溢D下溢单选题5.下面关于图的存储的叙述中,哪一个是对的的?A用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关Ｂ用相邻矩阵法存储图，占用的存储空间数只与图中边数有关,而与结点个数无关Ｃ用邻接表法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关Ｄ用邻接表法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关单选题６.当字符序列ｘ５y作为字符堆栈的输入时,输出长度为3的且可以作为C语言标记符的个数是__＿_。A3个B4个Ｃ５个D6个单选题7.树最适合用来表达__＿＿＿。A有序数据元素B无序数据元素Ｃ元素之间具有分支层次关系的数据D元素之间无联系的数据单选题8.线性表按链式方式存储时,每个结点的存储涉及___＿_两部分。A数据值与符号Ｂ数据与指针C数据与表名Ｄ数据项与符号单选题9．树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里我们把由树转化得到的二叉树叫做这棵树相应的二叉树。那么以下结论中_＿＿__是对的的。A树的先根遍历序列与其相应的二叉树的先序遍历序列相同Ｂ树的后根遍历序列与其相应的二叉树的后序遍历序列相同C树的先根遍历序列与其相应的二叉树的中序遍历序列相同D以上都不对单选题10.设深度为h的二叉树上只有度为0和度为２的结点,则此类二叉树中所包含的结点数至少为＿___(注意C和D中h为指数）。A2h-1Ｂ2(ｈ-１)C2*h－１D2＊h单选题１１.关于二叉树的三种遍历，下列说法对的的是_＿＿_。Ａ任意两种遍历序列都不可以唯一决定该二叉树B任意两种遍历序列都可以唯一决定该二叉树C先序遍历序列和后序遍历序列可以唯一决定该二叉树D先序遍历序列和中序遍历序列可以唯一决定该二叉树单选题１2.计算机算法是指___＿__。Ａ计算方法Ｂ排序方法C调度方法D解决问题的有限运算序列单选题13.若规定能快速地实现在链表的末尾插入和删除结点的运算，则选择＿____最合适。A单链表B带尾指针的单循环链表C双链表D双循环链表单选题14.下列关于图的生成树的唯一性，对的的是＿_＿__。A生成树是唯一的Ｂ生成树是不唯一的C生成树是唯一性不拟定D图的生成树有两棵单选题１5．一组记录的关键字为(４６,79,56,３８，40,84），则运用快速排序的方法,以第一个记录为基准元素得到的一次划分结果为。A38,40,４６,56,79,84Ｂ４0,３8，46,７9，56，８4C40,38,４6，56,７9,84D４0,38,４6,84,5６，79单选题1６．设散列表长为１4，散列函数是H（kｅy)＝key％1１,表中已有数据的关键字为１5，38,61,84共四个,现要将关键字为４9的结点加到表中,用二次探测法解决冲突,则放入的位置是___＿__＿_____。Ａ8B3C５D9单选题17．假如某二叉树的先序遍历序列是ａbdcef，中序遍历序列是dｂaeｆc，则其后序遍历序列是____。AdｂａｆecＢfecdbaＣｅｆcｄbaＤｄbfecａ单选题18.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过_＿＿_。Aｎ/２ＢnC(n+１)／２Dn＋１单选题19.设某二维数组Ａ[1..n,1..n］，则在该数组中用顺序查找法查找一个元素的时间复杂性的量级为_＿____。AＯ（ｌog2n)BＯ(n)CＯ(ｎlog２n)DO（n^2）单选题20.判断一个循环队列是空队列的条件是_____。AQ.reaｒ=＝Ｑ．frｏnｔBQ.fｒonｔ=＝0CQ.ｒear＝＝0Ｄ(Ｑ．ｒeａr+1)%ｍaxsiｚe==Q.front单选题２1．有m个叶子结点的Huｆｆman树所具有的结点总数为____。Am+1B2m-1Ｃ2ｍＤ2ｍ＋1单选题22．在一个无向图中,所有顶点的度数之和等于所有边数的___＿倍。Ａ１／2Ｂ1C2D4单选题23．线性表采用链式存储时，其地址_＿＿__。A必须是连续的B必须是不连续的C连续与否均可D部分地址必须是连续的单选题24.在数据结构中，与所使用的计算机无关的是数据的__＿_结构。Ａ存储B物理C逻辑D物理与存储单选题25.向一个有11５个元素的顺序表中插入一个新元素并保持本来顺序不变,平均要移动_＿__＿个元素。A１1５B１１４C5８D５7单选题26.任何一棵二叉树的叶结点在先序、中序和后序遍历的序列中的相对顺序__＿_。Ａ不发生变化B发生变化C不能拟定Ｄ以上都不对单选题27.将1０个元素散列到1000０0个单元的散列表中,则＿＿_＿______产生冲突。A一定会Ｂ一定不会C仍也许会单选题2８.一组记录的排序码为(20,2９,11，74,35，3,８,5６）,则运用堆排序方法建立的初始(小顶)堆为___＿。A20,2９，11,7４，３5,3，8，56B3,２9,8，56,3５,２0,１1,7４Ｃ3,8,1１,20，29，３5，56,７4D20，2９,3,8,11,３５,74，56单选题29．对线性表进行二分查找时，规定线性表必须____。Ａ以顺序方式存储Ｂ以顺序方式存储且元素有序C以链式方式存储D以链式方式存储且元素有序单选题３０.若由森林转化得到的二叉树是非空的二叉树,则二叉树形状是__＿_。A根结点无右子树的二叉树B根结点无左子树的二叉树C根节点也许有左子树和右子树的二叉树Ｄ各结点只有一个儿子的二叉树单选题3１.设ａ，b为一棵二叉树上的两个结点，在中序遍历时,ａ在b前的条件是__＿_。Ａa是b祖先Ba是ｂ子孙Cａ在b左方Ｄa在b右方单选题32.采用不带尾指针的单链表方式表达一个栈，便于结点的插入与删除。栈顶结点的插入与删除通常在链表的_＿___进行。A任意位置Ｂ链表头尾两端Ｃ链表头一端D链表尾一端单选题３３.用某种排序方法对线性表(２5，84,２1,47，15，27,68，３5,20）进行排序时，元素序列的变化情况如下（１)２0，１5，２1,25,47,２7,6８,３5,８４(2)１５,20，21，25,35,２７,４7,68，84(3)1５,2０,２1，２５,２7,35，47,68，84则所采用的排序方法是＿＿__。A选择排序B希尔排序C归并排序D快速排序单选题３4.关于无向连通图的最小生成树的个数＿_＿__。A一定有多棵B一定只有一棵Ｃ有一棵或多棵D也许不存在单选题3５.已知10个数据元素为（54，２8,16，34，7３,６2，９5,60，26,4３)，对该数列按从小到大排序，通过一趟冒泡排序后的序列为_＿_＿。A16,28，34，５４，７3，６2，60，26,43，95B28,1６,３4,54，62,７3，60，2６，43,95Ｃ2８，16，34,54,６2,60,7３，26，43，９5D16,2８,３4,５４，62，60，7３，26,4３,95单选题36.在一个长度为n的顺序表中,在第ｉ个元素(1<=ｉ<=n)之前插入一个新元素时需向后移动_＿_＿__＿个元素。A１Ｂｎ-iCｎ-i-1Dｎ-i＋１单选题３７．若某堆栈的输入序列为１，２，3,…,n-１,n,输出序列的第1个元素为n,则第i个输出元素为__＿＿__。Ａｎ-i+lＢn-iＣｉD哪个元素无所谓单选题38.在一个具有ｎ个结点的有序单链表中，插入一个新的结点并使之仍然有序的时间复杂度是______。ＡO(n)BO（loｇ2ｎ)CO(1)DO(n＾2)单选题３9．数据结构课程重要研究以下三方面的内容，它们是__＿___。Ａ数据、数据元素、数据类型B数据元素、数据类型、算法实现Ｃ数据元素、数据的逻辑结构、数据的存储结构D数据的逻辑结构、数据的存储结构、数据的运算单选题40．在某棵二叉树的一种序列中,假如发现其中每一结点的左孩子均是其前趋,则可判断定这种序列为中序序列。A对的B不对的单选题41.一个栈的入栈序列是a,ｂ，c，d,则下列序列中不也许的输出序列是＿______。ＡacbｄBdcｂaCacdbDdｂac单选题４2.已知某二叉树的后序遍历序列是ｄａｂec，中序遍历序列是dｅｂac,它的前序遍历序列是____。AacbｅｄＢdeｃabCdeabcDｃedba单选题43.一个栈的进栈序列是ａ,b，c,d,e,则栈的不也许的出栈序列是＿___＿。ＡｅdcｂａＢdceaｂCｄecbａDabcｄe单选题44.栈结构通常采用的两种存储结构是___＿＿。Ａ线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构单选题45.设有100０个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最佳____排序法。A起泡排序B快速排序Ｃ堆排序D基数排序单选题４６．若用二分查找法取得的中间位置元素键值大于被查找值,说明被查找值位于中间值的前面,下次的查找区间为从原开始位置至＿___。Ａ该中间位置B该中间位置-1C该中间位置+1D该中间位置/2单选题47．在长度为ｎ的双链表中某结点（已知其地址)之前,插入一个新结点的时间复杂度是____＿。ＡO(n）BＯ(log2n）CO(1)DO(ｎ^2)单选题４8.队列的操作原则是_＿__＿。A先进先出B先进后出Ｃ只能进行插入D只能进行删除单选题4９.设二叉树根结点的层次为1，所有具有15个结点的二叉树中，最小高度是_____。A6B５C４D3单选题50.设深度为ｈ的二叉树上只有度为0和度为２的结点，则此类二叉树中所包含的结点数至多为__＿__(注意Ｃ和D中h是指数)。A２ｈ-1B2(ｈ-1)C2*h－1D２*ｈ单选题51.下列排序算法的时间复杂度最小的是__＿＿。A冒泡排序B希尔排序Ｃ简朴选择排序D归并排序单选题52.假如无向图G必须进行二次广度优先搜索才干访问其所有顶点,则下列说法中不对的的是_＿＿_＿。AG肯定不是完全图BG一定不是连通图CG中一定有回路ＤG有2个连通分量单选题53.带头结点的单链表Heａd为空表的鉴定条件是___＿__。ＡHead－＞ｎext==ＨeadBHeａd->ｎexｔ=＝NULLCＨｅad!=ＮULLDＨｅaｄ＝=NＵLL单选题５４.在顺序表{2、5、7、1０、14、１5、1８、23、35、41、52}中,用二分法查找关键码12需做____次关键码比较。Ａ2B３C4D5单选题55.顺序表的特点是_＿____。A逻辑上相邻的结点其物理位置不相邻B逻辑上相邻的结点其物理位置亦相邻C顺序表不是随机存储结构D在顺序表中插入和删除操作比在链表上方便单选题５6.设n个顶点e条边的图G用邻接表存储，则求每个顶点入度的时间复杂度为_＿__。ＡO(n)BO(ｎ+e）CO(n*ｎ)DＯ(ｎ*e)单选题57.对于一个具有n个顶点和e条边的无向图，若采用邻接表表达，邻接表中所有结点总数是_＿_＿＿。Ae/２B2eCｅDn+e单选题５8.某非空二叉树的前序序列和后序序列正好相反,则二叉树一定是_____的二叉树。A空或只有一个结点B高度等于其结点数C.任一结点无左孩子D任一结点无右孩子单选题５9.在待排序的元素序列基本有序的前提下,效率最高的排序方法是＿＿__。A插入排序B快速排序C归并排序D选择排序单选题60.对顺序存储的线性表,设其长度为n，且在任何位置上插入或删除操作都是等概率的。则插入一个元素时平均要移动表中的_____个元素。An/２B(n+１)／2C(n－１）/2Dn判断题61.通过关键字比较的方法进行排序，其时间复杂性至少是O（ｎlog2n)。对的错误判断题6２.5个顶点的无向图，若不连通，则最多也许有6条边。对的错误判断题63.由二叉树的前序和中序遍历序列可惟一构造这棵二叉树。对的错误判断题6４.任何一个森林都可以唯一地与一棵二叉树相应。对的错误判断题６5.无向图各顶点度之和就等于边的数量。对的错误判断题６6.图的深度优先遍历和广度优先遍历都包含了图的所有顶点。对的错误判断题67.有向图各顶点入度之和就等于边的数量。对的错误判断题68．在某个实例的排序结果看出，值相同的两个关键字排序前后领先关系不变，由此可知该排序方法是稳定的。对的错误判断题6９.序列{１2,23,15，24,２2,１8,16,３0，