2023年全国计算机二级考试数据结构与算法

全国计算机二级考试第一章 数据结构与算法1.一个算法一般都可以用_、_ 、 _三种控制结构组合完毕。解析顺序、选择（分支）、循环（反复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是_。解析算法的控制结构 在一般的计算机系统中，有算术运算、逻辑运算、关系运算和_四类基本的操作和运算。解析数据传输2.常用于解决“是否存在”或“有多少种也许”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（）A列举法 B.归纳法 C.递归法 D.减半递推法解析列举就是列举出所有也许性，将所有也许性统统列举出来，然后解决问题的方法。所以A3.根据提出的问题，列举所有也许的情况，并用问题中给定的条件检查哪些是需要的，哪些是不需要的，这是算法设计基本方法中的_。解析列举法4.通过列举少量的特殊情况，通过度析，最后找出一般的关系的算法设计思想是（）A列举法 B.归纳法 C.递归法 D.减半递推法解析B5.在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是（） A列举法 B.归纳法 C.递归法 D.减半递推法解析二分法就是从一半处比较，减半递推技术也称分治法，将问题减半。所以D6.将一个复杂的问题归结为若干个简朴的问题，然后将这些较简朴的问题再归结为更简朴的问题，这个过程可以一直做下去，直到最简朴的问题为止，这是算法设计基本方法中的_。假如一个算法P显式地调用自己则称为_。假如算法P调用另一个算法Q,而算法Q又调用算法P，则称为_.解析 递归法 直接递归 间接递归调用7.算法中各操作之间的执行顺序称为_。描述算法的工具通常有_、_ 、 _。解析控制结构 传统流程图、N-S结构化流程图、算法描述语言8.从已知的初始条件出发，逐步推出所规定的各中间结果和最后结果，这是算法设计基本方法中的( )解析递推法9.将问题的规模减半，而问题的性质不变，再反复“减半”的过程，这是算法设计基本方法中的（）解析减半递推技术10.通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再试探，这是算法设计基本方法中的解析回溯法1.下列叙述中对的的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C顺序存储结构能存储有序表，链式存储结构不能存储有序表D链式存储结构比顺序存储结构节省存储空间解析顺序存储结构中各数据元素在存储空间中是按照逻辑顺序依次连续存放的，在链式存储结构中元素之间的关系通过指针来连接，所以不规定存储空间一定是连续的；顺序存储结构（或链式存储结构）既可以针对线性结构，也可以针对非线性结构，但像栈、队列这样的线性结构一般采用顺序存储结构（但也可以采用链式结构）；树、二叉树这样的非线性结构一般采用链式存储结构（但也可以采用顺序存储结构）；链式存储结构既可以存储无序表，也可以存储有序表，注意，链式存储结构存储的即使是有序表，也不能进行二分查找；链式存储结构比顺序存储结构要多使用存储空间，由于链式存储结构中要用额外空间来保存指针。所以A 顺序存储方式重要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。2.数据的存储结构是指（）A存储在外存中的数据 B.数据所占的存储空间量 C.数据在计算机中的顺序存储方式 D.数据的逻辑结构在计算机中的表现解析数据的逻辑结构是指数据元素之间的逻辑关系的数据结构。数据的存储结构则是数据的逻辑结构在计算机中的物理实现，有时也称作数据的物理结构。两者的区别是数据的逻辑结构只涉及到数据之间抽象的数学关系，存储结构则涉及到如何在计算机中通过对数据的物理存储进行组织来表达数据元素之间的逻辑关系。比如在线性表的顺序存储中是运用物理存储空间上的连续性来表达线性表中数据的前后件关系；在线性表的链式存储中是通过指针域构成的逻辑链条来表达数据的前后件关系。一般的，一种数据的逻辑机构相应的物理实现，即数据的存储结构不止一种。所以D3.在长度为n的顺序存储结构的线性表中，要在第i（1in）个元素之前插入一个新元素，则需要移动表中的（）个元素，表的长度变为（）；若删除表中的第i（1in）个元素，则需要移动表中的（）个元素，表的长度变为（）。解析n-i+1 ；n+1；n-i；n-14.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素出栈的顺序是（）A12345ABCDE B.EDCBA54321 C.ABCDE12345 D.54321EDCBA解析栈是按照“先进后出（FILO）”或“后进先出（LIFO）”的原则组织数据的，栈职能在栈顶插入数据（称为入栈）和删除数据（称为出栈）。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依次出栈，则元素的出栈顺序是EDCBA54321。所以B5.下列关于栈的描述中错误的是（）A栈是先进后出的线性表 B.栈职能顺序存储C栈具有记忆作用 D.对栈的插入与删除操作中，不需要改变栈底指针解析栈是一种先进后出的线性表；栈既可以顺序存储，也可以链式存储；栈可以用开保护断点信息，具有记忆作用；只允许在栈顶插入和删除元素，所以对栈的插入与删除操作，不要用改变栈底指针1. 线性表的存储结构重要分为顺序存储结构和链式存储结构。队列是一种特殊是线性表，循环队列是队列的_存储结构。解析顺序2.数据结构分为线性结构和非线性结构，带链的队列属于_解析线性 总结：常用的数据结构比如：线性表、栈、队列是线性结构（不管是采用顺序存储还是链式存储结构）；树、二叉树、图都是非线性结构（不管是采用顺序存储结构还是链式存储结构）3.已知元素的入栈顺序为abcde，则下列哪种出栈顺序是不也许的？（）Aedcba B.cabde C.dcbae D.bcdea解析abcde依次入栈，再再次出栈，得到出栈顺序edcba，所以选项A也许；选项B，第一个出栈的是C，可以肯定栈中有b、a，等待入栈的是d、e，此时出栈的也许是b或d（d入栈立即出栈），不也许是a，所以选项B不也许；选项C，第一个出栈的是d，可以肯定栈中有c、b、a，等待入栈的是e，此时出栈的也许是c或e，若c、b、a依次出栈，e入栈立即出栈，刚好得到出栈顺序dcbae，因此选项C也许；选项D，第一个出栈的是b，可以肯定栈中有a，等待入栈的是c、d、e，c、d、e分别入栈又出栈得到出栈顺序bcde，最后a出栈，行号得到出栈顺序bcdea，所以选项D也许。因此本题对的答案是B。4.假如刚开始时栈为空，依次有A、B、C、D四个元素入栈，此时栈底指针指向元素_，栈顶指针值为_(假如每个元素的长度为1)。执行四次出栈操作后把E、F、G压入栈，问此时栈底指针指向元素_，此时栈的长度为_.解析A;4;E;35. 下列叙述中对的的是A循环队列有对头和队尾两个指针，因此，循环队列是非线性结构B在循环队列中，只需要对头指针就能反映队列中元素的动态变化情况C.在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况D循环队列中元素的个数是由对头指针和队尾指针共同决定解析所谓循环队列，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列中，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置，因此，从排头指针front指向的后一个位置直到队尾指针real指向的位置之间所有的元素均为队列中的元素。求解队列中元素个数的方法是：若frontrear，队列中有n-front+rear个元素（其中n为循环队列的容量）；若frontrear，队列中有real-front个元素；若front=rear，队列中有n个或0个元素。循环队列是线性结构。所以D6. 在一个容量为15的循环队列中，若头指针front=6，尾指针rear=4，则该循环队列中共有_个元素；若front=4，rear=6，则该循环队列中有_个元素；若front=6，rear=6，则该循环队列中共有_个元素。解析本题重要考核对循环队列的存储形式和入队运算、出队运算的理解。求解队列中元素个数的方法是：1. 若frontrear，队列中有n-front+rear个元素（其中n为循环队列的容量）；2. 若frontrear，队列中有real-front个元素；3. 若front=rear，队列中有n个或0个元素。循环队列是线性结构。所以 13；2；0或151. 下列对于线性链表的描述中对的的是（）A.存储空间不一定是连续，且各元素的存储顺序是任意的B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的解析线性链表是通过增长一个指针域来把相邻的数据元素链接成一个线性序列。线性链表的这种结构使得它存储数据的空间可以是离散的，并不像顺序表那样一定规定物理上的连续空间。所以A2.在线性链表的插入算法中，若要把结点q插在结点p后面，下列操作对的的是（）A使结点p指向结点q，再使结点q指向结点p的后件结点B使结点q指向p的后件结点，再使结点p指向结点qC使结点q指向结点P，再使结点P指向结点q的后件结点D使结点p指向q的后件结点，再使结点q指向结点p解析在修改结点指针域的操作中，有一个操作顺序的问题。比较选项A和B只是操作顺序颠倒了一下。A中先使结点p指向q后，q就称为p新的后件结点了，原先通过结点p指向的后件结点与结点p脱节了那么后面的一步操作没有任何意义的。使结点q指向p的后件结点即使结点q成为自己的后件结点。按照B指定的顺序操作就不会出现引用结点p的指针域之前已经把它的值修改了的情形。至于C和D是命题者设计的干扰项想让考生把p和d的顺序搞混。总结，做这种类型的试题，最佳画图。插入结点：若结点p的后面是结点s，要在p和s之间插入结点q，一般先将结点q指向结点s，再讲结点p指向q，顺序不能颠倒。 删除结点：若结点p的后面是结点q，结点q的后面是结点s，若要删除结点q，只需将结点p指向s即可。3.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为（）A63 B.64 C.6 D.7解析只要是顺序查找（不管线性表是有序还是无序），都是从表头到表尾逐个比较，若相同则结束查找，否则一直继续比较下一个表中元素，指导整个表都遍历完。对于长度为64的线性表，平均要进行64/2=321次比较，在最坏的情况下要进行64次比较。若采用二分（折半）查找，则最坏情况下需要比较的次数为log264=6次，弹药注意采用二分（折半）查找的条件，必须是线性表采用顺序存储结构，并且线性表中的元素要有序，这两个条件缺一不可。若对线性链表进行查找，则不管线性链表中的元素是有序还是无序职能采用顺序查找。因此本题B.4.在一个nm的二维线性表中顺序查找一个数据元素的算法时间复杂度是（）A.O(n+m) B.O(nm) C.O（n2） C.O（m2）解析在一维线性表中顺序查找一个数据元素的算法时间复杂度是O（n），其中n是线性表的长度，二维线性表的顺序查找方法和一维线性表相似，只但是是多了一维罢了。在二维表中进行顺序查找有两个方法：一是把二维线性表当作是n个长度为m的一维线性表，顺序查找就是对这n个一维线性表依次实行顺序查找，因此它的算法时间复杂度是O（n） O（m）= O(nm)；二是直接把nm的二维线性当作一个nm的一维线性表，那么在它当中用顺序查找法查找一个元素的算法时间复杂度是O(nm)。5.下列叙述中对的的是（）A.线性链表是线性的链式存储结构 B.栈与队列是非线性结构C双向链表是非线性结构 D.只有根结点的二叉树是线性结构解析线性表的链式存储结构称为线性链表；栈、队列、双向链表都是线性结构；树、二叉树（不管它有多少个结点）都是非线性结构。所以A6.下列关于链表结构的叙述对的的是（）A.线性链表、带链的栈和带链的队列的结点的结构都是相同的 B. 双向链表也就是循环链表C线性链表与带链的结点的结构是不同的D.在循环链表中通过任意一个结点可以找到链表中其他所有的结点，而在双向链表中做不到这一点解析A、C线性链表、带链的栈和带链的队列：结点（表达数据元素）=数据域（数据元素的映像）+指针域（指示后继元素存储位置）。B、D双向链表：也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分表指向直接后继和直接前驱。循环链表：循环 链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。1.一棵度数为4的树，它的4度结点有1个，3度结点有2个，2度结点有3个，1度结点4个，问它的叶子结点有多少个？A5 B.6 C.9 D.11解析假如注意观测树的结构，你会发现树中的结点数总是比树中的分支数多，其实也可以这么理解：假如在根结点前面加一条分支线，那么分支数和结点数就同样多了。在树的结点里，n度结点可以射出条分支，叶子结点是0度结点，因此它射出的分支数为0。此题中指导了1到4度结点的个数，就可以计算出树的总分支数：41+32+23+14=20.因此树的总结点数是21，减去其他读书的结点数10就得到0度结点（叶子结点）的个数11了。所以D2.在深度为7的满二叉树中，叶子结点的个数为（）A32 B.31 C.64 D.63解析在满二叉树中每层的结点数都达成最大值，并且叶子结点所有出现在最底层。第1层（根结点所在的层）有20个结点，第2层有21个结点，第n层有2n-1个结点。在深度为7的满二叉树中，第7层有27-1=64个结点（所有是叶子结点），在深度为7的满二叉树中，共有27-1=64个结点，本题为C3.某二叉树有5个度为2的结点，则该项树中的叶子结点数是（）A10 B.8 C.6 D.4解析根据二叉树的性质，在任意二叉树中，度为0的结点（即叶子结点）数总是比度为2的结点数多一个。所以C4.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为（）An+1 B.n-1 C.2n D.n/2解析二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。所以某二叉树中共有n个度为2的结点，则该二叉树的叶子结点数为n+1。所以本题为A5.一科二叉树中共有70个叶子结点和80个度为1的结点，该二叉树的总结点数为（）A219 B.221 C.229 D.231解析二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点（叶子结点）总是比度为2的结点多一个。本题告知，叶子结点有70个，那度为2的结点既有69个，度为1的结点有80个，这颗二叉树共有70+69+80=219个结点。所以A6.在深度为7的满二叉树中，度为2的结点个数为（）解析满二叉树的定义是除最后一层外，每一层的所有结点都有两个子结点（即每一层上的结点数均达成最大值）。第1层（根结点在第1层）拥有的结点数是20=1，第2层拥有的结点数是21=2，第3层拥有的结点数是22=4，第n层拥有的结点数是2n-1。在深度为7的满二叉树中，叶子结点所有在第7层，其余结点都是2度结点。在满二叉树中，第7层拥有的结点数是27-1=64。二叉树具有这样一个性质：在任意一棵二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个，所以度为2的结点个数为64-1=63。7.具有8个结点的完全二叉树中编号为4的结点的右子结点的编号为（）A8 B.9 C.无此结点 D.8或9解析设完全二叉树共有n个结点，假如从根结点开始，按层序（每一层从左到右）用自然数1，2，n给结点进行编号（i=1，2，n），有以下结论：1. 若i=1，则该结点为根结点，它没有父结点；若i1，则该结点的父结点编号为i/2；其中i/2表达取i/2的整数部分。2. 若2in，该结点无左子结点（也无右子结点）；若2in，则编号为i的结点的左子结点编号为2i；3. 若2i+1n，该结点无右子结点；若2i+1n，则编号为i的结点的右子结点编号为2i+1。所以本题为C1.设一棵二叉树的中序遍历结果为DBEACF，前序遍历结果为ABDECF，则后续遍历结果为（）解析我们可以根据前序遍历的结果ABDECF，拟定第一个元素A是根结点，再看中序遍历的结果DBEACF，A前面的DBE应当在左子树，A后面的FC应当在右子树。根据前序遍历的结果和中序遍历的结果，我们可以推导出：A是根结点，B是A的左结点，D是B的左结点，E是B的右结点，C是A的右结点，F是C的右结点。画出二叉图，对后续遍历的结果为DEBFCA.2.树是一种简朴的_结构，在树中，所有数据元素之间的关系具有明显的_特性。解析非线性；层次3.拥有奇数个结点的完全二叉树中有4个内部结点（非叶子结点），请问它的叶子结点数是解析5 分析由于完全二叉树是自上而下、自左而右的从1开始连续编码的，因此完全二叉树要么不存在一度结点（当结点个数为奇数个数时），要么存在一个一度结点，并且唯一的一个一度结点就是最后编号为n（n为偶数）的叶子结点的父结点。而在二叉树中零度结点个数总比二度结点个数多1，因此拥有4个二度结点的二叉树的叶子结点个数是4+1=5.总结，设n为完全二叉树的结点数，n0为叶子结点数，n1为度为1的结点数，n2为度为2的结点数，则n=n0+n1+n2，n0=n2+1。若n为奇数，则n1=0；若n为偶数，则n1=1（注意一定要是完全二叉树）。4. 设一棵完全二叉树共有700个结点，则在该二叉树中有（）个叶子结点。解析完全二叉树的特点：假如结点总数是偶数则（度为1的结点）N1=1；假如结点总数为奇数，则N1=0；二叉树始终n0=n2+1，n2= n0-1，结点总数= n0+n1+n2（将n2= n0-1，n1=1代入公式）；则有700= n0 +1+n0-1，所以n0=3505. 具有16个结点的完全二叉树的深度为（ ）解析5；二叉树的特点：具有n个结点的完全二叉树的深度为log2n+1，所以具有16个结点的完全二叉树的深度为log216+1=56. 在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是 AO(n) B.O(n2) C.O（log2n） D.O(nlog2n)解析对于长度为n的线性表进行顺序查找，平均要进行n/2次比较，在最坏情况下要进行n次比较；对于长度为n的线性表进行二分查找，在最坏的情况下要进行log2n次比较（但二分查找规定线性表是顺序存储的有序表）。因此本题答案为C7.请写出用二分查找法在有序顺序表1，2，3，4，6，8，9，11中查找3的比较序列（）解析4，2，3；可采用擦去法做这类二分法查找序列的题：每次从序列中找出中间元素，刚开始时是4，由于3比4小，只能存在在4之前的序列中，于是把4以后的序列擦去，只剩下序列1，2，3，在反复以上过程直到查找元素或是序列为空。1. 通过相邻数据元素的互换逐步使线性表变成有序的排序方法是（）A.冒泡排序法 B.简朴选择排序法 C.简朴插入排序法 D.希尔排序法解析冒泡排序法是一种最简朴的互换类排序方法，它是通过相邻数据元素的互换逐步将线性表变成有序，每次只能消除一个逆序。简朴插入排序法，是将无序序列中的元素插入有序的线性表中，并依次与前面的元素进行比较，直到大于前面的元素为止，最多需要比较n（n-1）/2次。希尔排序法是简朴插入排序法的优化，每进行依次可以消除多个逆序。简朴选择排序法是指扫描整个线性表，从中选出最小的元素，将它互换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。2.冒泡排序在最坏情况下的比较次数是( )A.n（n+1）/2 B.nlog2n C.n(n-1)/2 D.n/2解析对于长度为n的线性表，在最坏的情况下，冒泡排序需要进行的比较次数是n（n-1）/2。本题答案为C2.快速排序法属于（）A.选择类排序法 B.互换类排序法 C.插入类排序法 D.归并类排序法解析互换类排序法涉及冒泡和快速排序法；插入类排序法涉及简朴插入和希尔排序法；选择类排序法涉及简朴选择和堆排序法。本题为B3.下列排序方法中，最坏情况下比较次数最少的是（）A.冒泡排序 B.简朴选择排序 C.直接插入排序 D.堆排序解析冒泡排序、简朴选择排序和直接插入排序法在最坏的情况下的比较次数为n（n-1）/2。而堆排序法在最坏情况下的比较次数为O(nlog2n)，本题为D4. 长度为10的顺序表的首地址是1023开始的，顺序表中每个元素的长度为2，在第4个元素前面插入一个元素和删除第7个元素后，顺序表的总长度还是不变。问顺序表中第5个元素在执行插入和删除操作后在顺序表中的存储地址是（）A.1028 B.1029 C.1031 D.1033解析由于问的是本来顺序表中的第5个元素，它在插入操作后变成了第6个元素（由于插入的元素在它前面）。由于删除的第7个元素在它后面，不会影响它在顺序表中的排位。因此在执行插入和删除操作后原先顺序表中的第5个元素变成了新的顺序表中的第6个元素。再按照线性表的随机存取地址的计算公式ADD（ai）=ADD(a1)+（i-1）k计算ADD(a6)=ADD（a1）+（6-1）2=1023+52=1033，所以选D5. _是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。解析 算法6.在最坏的情况下，冒泡排序的时间复杂度为_，简朴插入排序的时间复杂度为_，希尔排序的时间复杂度为_，简朴选择排序的时间复杂度为_，堆排序的时间复杂度为_。解析 O(n（n-1）/2)；O(n（n-1）/2)；O(n1.5)；O(n（n-1）/2)；O(nlog2n)；7.以下排序技术中属于互换类排序法的有_,属于插入类排序法的有_，属于选择类排序法的有_。A.简朴插入排序 B.冒泡排序 C.希尔排序 D.堆排序 E.快速排序 F.简朴选择排序解析BE；AC；DF7. 算法中各操作之间的执行顺序称为（）。描述算法的工具通常有（）、（）、（）解析算法的控制结构；传统的流程图；N-S结构化流程图、算法描述语言1.请写出冒泡排序法对序列5，1，7，3，1，6，9，3，2，7，6进行第一遍扫描后的排序结果是_.解析1,1,5,3,2,6,7,3,6,7,9分析冒泡排序法的基本过程：一方面，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小，若前面的元素大于后面的元素，则将他们互换，这样最大者互换到了表的最后面；然后，从后往前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小若后面的元素小于前面的元素，则将他们互换看，这样最小者互换到了表的最前面；从前往后和从后往前扫描一个来回称为一遍；对剩下的线性表反复上述过程，直到剩下的线性表变为空为止，这样线性表就变为有序了。现在我们来看看对线性表5，1，7，3，1，6，9，3，2，7，6从前往后进行扫描的过程：51，5和1互换位置得到1，5，7，3，1，6，9，3，2，7，657不管，继续往后扫描，扫描到773，7和3互换位置得到1，5，3，7，1，6，9，3，2，7，671，7和1互换位置得到1，5，3，1，7，6，9，3，2，7，676，7和6互换位置得到1，5，3，1，6，7，9，3，2，7，679不管，继续往后扫描，扫描到993，9和3互换位置得到1，5，3，1，6，7，3，9，2，7，692，9和2互换位置得到1，5，3，1，6，7，3，2，9，7，697，9和7互换位置得到1，5，3，1，6，7，3，2，7，9，696，9和6互换位置得到1，5，3，1，6，7，3，2，7，6，9从前往后扫描结束，9互换到了线性表的最后。现在我们来看看对剩下的线性表1，5，3，1，6，7，3，2，7，6，9从后往前进行扫描的过程67，6和7互换位置得到1，5，3，1，6，7，3，2，6，7，962不管，继续往前扫描，扫描到223，2和3互换位置得到1，5，3，1，6，7，2，3，6，7，927，2和7互换位置得到1，5，3，1，6，2，7，3，6，7，926，2和6互换位置得到1，5，3，1，2，6，7，3，6，7，921不管，继续往前扫描，扫描到113，1和3互换位置得到1，5，1，3，2，6，7，3，6，7，915，1和5互换位置得到1，1，5，3，2，6，7，3，6，7，92.请写出用希尔排序法对序列5，1，7，3，1，6，9，3，2，7，6进行第一遍扫描后的排序结果是_.解析5，1，3，2，1，6，9，7，3，7，6希尔排序法的基本思想：将整个无序序列分割成若干的子序列分别进行插入排序（插入排序：开始线性表中只有第1个元素，然后从线性表的第2个元素开始指导最后一个元素，逐次将其中的每一个元素插入到前面已有序的子表中）子序列的分割方法：将相隔某个增量h（ht=n/2k（k=1，2，3log2nn为待排序的线性表的长度）的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时进行一次插入排序，排序完毕。按以上分析，第1次分割子序列h=n/2=11/2=5，构成的子序列有5，6、1，9、7，3、3，2、1，7、6（最后一个元素6成单），每一个序列进行插入排序，结果为5，6、1，9、7，3、3，2、1，7、6（最后一个元素6成单），所以第一遍扫描后的结果是5，1，3，2，1，6，9，7，3，7，63. 请写出用简朴选择排序法对序列5，1，7，3，1，6，9，3，2，7，6进行第一遍扫描后的排序结果是_.解析 1， 5，3，2，1，6，9，7，3，7，6扫描整个线性表，从中选择最小的元素，将它互换到表的最前面，对剩下的子表采用同样的方法，直到子表为空。我们对线性表5，1，7，3，1，6，9，3，2，7，6进行第1遍扫描，可以看出元素1最小，将1和第一个位置上的元素5互换，就得到第1编扫描的结果 1， 5，3，2，1，6，9，7，3，7，6线性链表1. 下列对于线性链表的描述中对的的是 。（2023年4月）A. 存储空间不一定是连续，且各元素的存储顺序是任意的B. 存储空间不一定是连续，且前件元素一定存储在后件元素的前面C. 存储空间必须连续，且前件元素一定存储在后件元素的前面D. 存储空间必须连续，且各元素的存储顺序是任意的答案 A2. 下列叙述中对的的是 。（2023年4月）A. 线性链表是线性表的链式存储结构 B. 栈与队列是非线性结构C. 双向链表是非线性结构 D. 只有根结点的二叉树是线性结构答案 A3. 数据结构分为线性结构和非线性结构，带链的队列属于 。（2023年9月） 答案 线性结构4. 线性表采用链式存储时，结点的存储地址 。A. 必须是不连续的 B. 连续与否均可 C. 必须是连续的D. 和头节点的存储地址相连续答案 B5. 在循环链表中，增长头结点的目的是_。A. 方便运算的实现 B. 使单链表至少有一个结点C. 标记表结点中首结点的位置 D. 说明单链表是线性表的链式存储实现答案 A6. 下列叙述中，错误的是_。A. 线性表是由n个数据元素组成的一个有限序列 B. 线性表是一种线性结构C. 线性表的所有结点有且只有一个前件和一个后件 D. 线性表可以是空表答案 C7. 用链表表达线性表的优点是_。A. 便于插入和删除操作 B. 数据元素的物理顺序与逻辑顺序相同C. 花费的存储空间较顺序存储少 D. 便于随机存取答案 A8. 下列描述的不是链表的优点的是_。A. 逻辑上相邻的结点物理上不必相邻 B. 插入、删除运算操作方便，不必移动结点C. 所需存储空间比线性表节省 D. 无需事先估计存储空间的大小答案 C9. 下列叙述中对的的是 。（2023年3月）A.栈是“先进先出”的线性表B.队列是“先进后出”的线性表C.循环队列是非线性结构D.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构答案 D10. 下列数据结构中，属于非线性结构的是 。（2023年9月）A.循环队列 B.带链队列 C.二叉树 D.带链栈答案 C11. 下列叙述中对的的是 。（2023年9月）A. 线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的B. 线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构C. 线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构D. 上述三种说法都不对答案 B