23秋国家开放大学《数据结构与算法》形考任务1-2参考答案

国家开放大学《数据结构与算法》形考任务1-2参考答案《数据结构与算法》是“数据科学与大数据技术”专业（本科）的一门统设必修课。课程编号：04692形考任务1一、单项选择题1.下面说法错误的是（）。A.数据结构是指互相之间存在着一种或多种关系的数据元素的集合B.数据(Data)是指客观事物的符号表示C.数据元素是表示数据的不可分割的最小标识单位D.数据的基本单位是数据元素2.数据结构中的线性结构是指（）。A.数据元素之间属于同一个集合B.数据元素之间存在着一对一的线性关系C.数据元素之间存在着一对多的线性关系D.数据元素之间存在着多对多的线性关系3.下列有关递归的说法错误的是（）。A.递归需要有边界条件、递归方程两部分构成。B.递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。C.递归通常把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。D.只有在函数中直接调用自身才能叫做递归函数。4.根据数据元素之间关系的不同，数据结构分为（）。A.物理结构，逻辑结构B.集合结构，线性结构，树结构，图结构C.顺序结构，链表结构D.递归结构，普通结构5.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，下列（）序列是可能的出栈序列。A.E、D、C、B、A、FB.B、C、E、F、A、DC.B、D、C、F、E、AD.A、D、F、E、B、C6.顺序循环队列容量为50，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为31，队尾为8的时候，队列中共有（）个元素。A.25B.26C.27D.287.对线性表，在下列（）情况下应当采用链表表示。A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变8.若用一个大小为8的数组来实现循环队列，且当tail和head的值分别为6，0。当从队列中删除两个元素，再加入一个元素后，tail和head的值分别为（）。A.6和5B.7和2C.2和7D.5和69.设循环队列的元素存放在一维数组Q[50]中，head指向队头元素，tail指向队尾元素的后一个位置。若head=27,tail=6,则该队列中的元素个数为（）。A.19B.20C.29D.4010.下列有关队列及其应用叙述错误的是（）。A.队列是操作受限制的线性表B.队列的入队顺序和出队顺序是一致的C.解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区是一个队列结构D.设计一个判别表达式中左右括号是否配对的算法，采用队列数据结构最佳11.一个栈的输入序列为1234，则下列序列中不可能是栈的输出序列的是（）。A.2314B.3241C.1234D.312412.用链接方式存储的非空队列，队列长度为6，在该链队列中删除一个元素时（）。A.仅修改队头指针B.队头、队尾指针都要修改C.仅修改队尾指针D.队头、队尾指针都不需修改13.下列有关队列及其应用叙述正确的是（）。A.队列中每一个元素都有唯一的直接前驱和唯一的直接后继B.队列的插入在队头进行C.队列的删除在队尾进行D.队列中的队头元素有唯一的直接后继14.设有字符串p，返回字符在字符串中第一次出现的位置称作（）。A.查找B.求子串C.求串长D.连接15.串S1=“ab123”，S2=“ab45”，则S1（）S2。A.>B.<C.=D.不确定16.广义表G=(a,G)的长度为（）。A.1B.2C.3D.无穷大17.树的度是指（）。A.树中某个结点拥有的子树棵数B.树中所有结点度的和C.树中所有结点度的最大值D.树中所有结点度的最小值18.如果二叉树根结点的层次为1，二叉树共4层，则整棵二叉树最多有（）个结点。A.15B.16C.17D.1819.二叉树如图所示，其先序遍历结果为（）。A.(BDEFHMPRTWZ)B.(HDBFERMPWTZ)C.(BEFDRMPWTZH)D.(BEFDPMTZWRH)20.为4个使用频率不等的字符设计哈夫曼（Huffman）编码，不可能的方案是（）。A.110，10，01，00B.000，001，010，01C.001，010，000，011D.001，01，11，10二、判断题21.算法的设计取决于所选定的存储结构。（×）22.数据结构中的树结构是指数据元素之间存在着一对一的线性关系。（×）23.顺序表会开辟连续的存储空间存储数据。（√）24.栈只能在栈底端进行插入删除。（×）25.在顺序栈中，TOP始终指向栈底的位置，就是放置新元素的位置。（×）26.字符串是一种操作受限的线性表。（×）27.单字符链表每个结点只存储一个字符。（√）28.广义表可以被其他广义表共享。（√）29.由中序序列和后序序列可以构造出一棵唯一的二叉树。（√）30.哈夫曼树中结点的度可以是0,1,2。（×）形考任务2一、单项选择题1.无向图的顶点个数为n，则图中边数的最大值为（）。A.n×(n-1)B.n×(n-1)/2C.n-1D.n2.在一个无向图中，所有顶点的度数之和等于所有边数的（）。A.3倍B.2倍C.1倍D.0.5倍3.在图的邻接矩阵存储结构中删除一个顶点，下列说法错误的是（）。A.直接在删除顶点处做删除标记即可B.删除顶点顺序表中的该顶点C.删除邻接矩阵中该顶点所在的行D.删除邻接矩阵中该顶点所在的列4.一个有e条边的无向图，邻接表中包含的边结点的总数是（）。A.eB.e-1C.e+1D.2e5.对于下图的无向图，插入一个顶点E后，顶点顺序表为（）。A.选项AB.选项BC.选项CD.选项D6.对于下面的图，从结点0开始进行深度优先搜索，可能的搜索结果是（）。A.0,1,2,3,4,5B.0,1,2,3,5,4C.0,2,3,4,1,5D.0,4,3,1,2,57.对于下面的图，从结点1开始进行广度优先搜索，可能的搜索结果是（）。A.1,3,2,4,0,5B.1,0,4,2,3,5C.1,3,0,2,4,5D.1,5,0,2,4,38.设一组初始记录关键字序列为(17，29，32，48，51，63，78，92，151)，则利用顺序查找方法查找关键字78需要比较的关键字个数为（）。A.5B.6C.7D.89.设一组初始记录关键字序列为(12，25，27，37，52，61，72，89，97),则利用折半查找过程中第一个比较的关键字是（）。A.12B.17C.52D.6110.设一组初始记录关键字序列为(28，32，49，53，67，71，86，94，115，128，136)，则利用折半查找关键字128需要比较的关键字个数为（）。A.1B.2C.3D.411.按{12，24，36，90，52，30}的顺序构成的二叉排序树，其叶子结点是（）。A.30，52B.24，36C.52，90D.12，2412.将{12，24，36，90，52，30}6个元素构成平衡二叉排序树，其根结点是（）。A.12B.24C.52D.3613.对于折半查找法，一般选择（）作为其存储结构。A.顺序表B.循环表C.双链表D.单链表14.基本有序的序列适合用（）排序算法进行排序。A.归并B.直接插入C.快速D.堆15.直接插入排序的时间复杂度是（）。A.O(n2)B.O(n)C.O(nlog2n)D.O(1)16.对序列{82614377}进行从头到尾的冒泡排序，第一趟扫描排序结果为（）。A.61824377B.61437782C.61438277D.4361778217.判别下列序列中，不是堆的是（）。A.（3，7，17，25，36，47，85，29，52）B.（82，57，63，41，35，48，52，21，30）C.（5，8，10，12，30，9，17，36，45）D.（95，43，65，23，38，57，80，15，17）18.对序列{4553583672304893}进行归并排序，第二趟两两归并结果为（）。A.（36455358）（30487293）B.（45535836）（72304893）C.（4553）（3658）（3072）（4893）D.（3036454853587293）19.下列关于回溯法的描述错误的是（）。A.回溯法按照规则去试探B.回溯法就是是穷举式搜索C.回溯法中候选解满足问题的所有要求，该候选解就是问题的一个解D.回溯是指放弃当前的候选解，退到上一步20.将大问题化为相互独立的相同的小问题，然后各个击破，解决完小问题后再合成大问题的解是（）算法的算法思想。A.动态规划算法B.分治法C.回溯算法D.贪心算法二、判断题21.有n个顶点的有向完全图，有n(n-1)条边。（√）22.有向图的邻接矩阵一定是不对称的。（×）23.邻接表只适于无向图的存储，不适合有向图的存储。