2023年高等教育工学类自考-02331数据结构考试历年参考核心考点荟萃附答案

（图片大小可任意调节）2023年高等教育工学类自考-02331数据结构考试历年参考核心考点荟萃附答案第一卷一.参考题库(共20题)1.已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。2.下列广义表用图来表示时，分支结点最多的是（）。A、L=（（x，（a，B）），（x，（a，B），y））B、A=（s，（a，B））C、B=（（x，（a，B），y））D、D=（（a，B），（c，（a，B），D）3.数据结构里，数据的逻辑结构有哪些（）。A、集合结构B、线性结构C、图形结构D、树形结构4.若一棵满二叉树含有121个结点，则该树的深度为（）。5.简述二叉链表表示和三叉链表表示的二叉树中结点的结构。6.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。A、6B、7C、8D、97.下列关于串的叙述中，不正确的是（）。A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储8.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是（）。A、AB、EC、BD、D9.指出下述程序段的功能是什么？ 10.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）A、23B、37C、44D、4611.数据结构算法中，通常用时间复杂度和（）两种方法衡量其效率。12.对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为（）个，其中（）个用于链接孩子结点，（）个空闲着。13.串的长度是指（）。A、串中所含不同字母的个数B、串中所含字符的个数C、串中所含不同字符的个数D、串中所含非空格字符的个数14.广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。15.下列图的深度优先遍历序列为（）。 A、ABCDEFGHB、ABDHECFGC、ABEDHCFGD、ABCFGEDH16.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。17.设一组初始记录关键字序列为（345，253，674，924，627），则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。A、3B、4C、5D、818.数据结构里，栈和队列都是（）。A、操作受限的线性结构B、先进先出的线性结构C、后进先出的线性结构D、以上都不对19.已知广义表L=（（x，y，z），a，（u，t，w）），从L表中取出的原子项ASCII码最大的运算是（）。A、head（tail（tail（L）））B、tail（head（head（tail（L））））C、head（tail（tail（head（L））））D、head（tail（tail（tail（L））））20.对具有n个元素的有序表采用二分查找法，则算法的时间复杂性为（）A、O（n）B、O（n2）C、O（1）D、O（log2n）第二卷一.参考题库(共20题)1.假定利用数组a[N]顺序存储一个栈，用top表示栈顶元素的下标位置，用top==-1表示栈空，用top==N-1表示栈满，则该数组所能存储的栈的最大长度为（）A、N - 1B、NC、N+1D、N十22.试将折半查找的算法改写成递归算法。3.中缀表达式3*（X+2）-5所对应的后缀表达式为（）。4.每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做（）排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（）排序。5.下列对于线性链表的描述中正确的是（）。A、存储空间不一定是连续，且各元素的存储顺序是任意的B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的6.如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。A、单链表B、双链表C、单循环链表D、顺序表7.快速排序法是一种稳定性排序法。8.简述直接插入排序的具体步骤。9.算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。10.数据结构里，算法的空间复杂度是不能衡量算法存储量的高低的。11.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。12.在一棵二叉排序树上按（）遍历得到的结点序列是一个有序序列。13.若要对1000个元素排序，要求既快又稳定，则最好采用（）方法。A、直接插入排序B、归并排序C、堆排序D、快速排序14.在等概率情况下，顺序表的插入操作要移动（）结点。A、全部B、一半C、三分之一D、四分之一15.简述磁盘的逻辑结构。16.N个结点的m阶B树至少包含（）个关键字。A、（m-1）*nB、nC、（「m/2」-1）*（n-1）+1D、n*「m/2」-1）17.的深度是（）18.在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A、小于顺序表的平均查找长度B、大于顺序表的平均查找长度C、与顺序表的平均查找长度相同D、无法与顺序表的平均查找长度比较19.写出算法的功能。intfun（sqstring*s，sqstring*t，intstart）{inti=start-1，j=0；while（ilen&&jlen）if（s->data[i]==t->data[j]）{i++；j++；}else{i=i-j+1；j=0；}if（j>=t->len）returni-t->len+1；elsereturn-1；}20.已知某森林的二叉树如下所示，试画出它所表示的森林。 第三卷一.参考题库(共20题)1.从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂性为（）。A、O（n）B、O（1）C、O（log2n）D、O（n2）2.元素11，13，15，17按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A、17，15，13，11B、11，13，15，17C、17，15，11，13D、13，11，17，153.一裸树上的任何结点（不包括根本身）称为根的（）。若B是A的子孙.则称A是B的（）。4.什么是广义表？广义表与线性表的区别是什么？5.设二维数组A[0…m-1][0…n-1]按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。A、p+[i*n+j-1]*kB、p+[（i-1）*n+j-1]*kC、p+[（j-1）*n+i-1]*kD、p+[j*n+i-1]*k6.在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。 7.子程序调用过程中，需要把运行现场的数据保存到（）中，返回主调函数在从中间取出。A、栈B、图C、二叉树D、队列8.把算法的工作量大小和实现算法所需的存储单元多少分别称为算法的（）和（）A、可实现性B、时间复杂度C、困难度D、计算有效性E、可行性F、高效性G、空间复杂度9.二叉树采用链式存储结构，结构定义如下，试设计一个递归算法计算一棵给定二叉树的叶子结点数。 10.一个广义表的深度等于（）嵌套的最大层数。11.设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：画出散列表示意图并给出查找每个关键字时需要比较的次数。12.某完全二叉树共有200个结点，则该二叉树中有（）个度为1的结点。13.从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为（）排序法。14.外部排序15.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值。16.具有n个顶点的有向图最多有（）条边。A、NB、n（n-1）C、n（n+1）D、n217.假设以数组Q[m]存放循环队列中的元素，同时以rear和length分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对空条件为（）。18.无向图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，b19.若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（）A、O（1）B、O（n）C、O（n2）D、O（log2n）20.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。第一卷参考答案一.参考题库1.正确答案:二叉树的构造过程如图5-12所示。 2.正确答案:A3.正确答案:A,B,C,D4.正确答案:75.正确答案:在二叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点不包含指向其双亲结点的指针；在三叉链表表示中，双亲结点有指向其孩子结点的指针，而孩子结点也包含指向其双亲结点的指针。6.正确答案:B7.正确答案:B8.正确答案:B9.正确答案:程序段的功能是利用tmp栈将一个非空栈S1的所有元素按原样复制到一个栈S2当中去。10.正确答案:C11.正确答案:空间复杂度12.正确答案:2n；n-1；n+113.正确答案:B14.正确答案:错误15.正确答案:B16.正确答案:错误17.正确答案:A18.正确答案:A19.正确答案:C20.正确答案:D第二卷参考答案一.参考题库1.正确答案:B2.正确答案:3.正确答案:3*2+*54.正确答案:插入；选择5.正确答案:A6.正确答案:D7.正确答案:错误8.正确答案:直接插入排序是一种简单排序算法，其具体步骤为： A.初始已排序区为空，将第一个待排序的元素插入到已排序区中。 B.将后继每一个待排序的元素依次取出，并按照关键字大小将其插入到已排序区中的适当位置，使该序列仍然有序。 C.重复上一步骤直至将待排序的元素都插入到已排序序列中。9.正确答案:错误10.正确答案:错误11.正确答案:错误12.正确答案:中序13.正确答案:B14.正确答案:B15.正确答案:磁盘的结构如下： A.一个磁盘包含若干个盘片，所有盘片组成了盘片组；每个盘片有上下两面，称为盘面；每个盘面上有很多同心圆形式的磁道，数据就存放在这些磁道上；每个磁道又可以划分为若干段，称为扇区，一个扇区就是一次读写的最小数据量。 B.每个盘面都配有一个读写磁头，通过读写磁头可以对磁道上的数据进行读写操作；所有读写磁头都安装在动臂上，通过动臂可以将读写磁头移动到任一磁道上；所有盘面上具有相同半径的磁道就构成了圆柱面，一个磁盘上圆柱面的个数就是一个盘面上的磁道数，同一时刻所有读写磁头都位于一个圆柱面上。 C.主轴带动所有盘面高速旋转，使得读写磁头可以访问到一个磁道上的所有扇区。16.正确答案:C17.正确答案:418.正确答案:C19.正确答案:串的模式匹配算法20.正确答案:第三卷参考答案一.参考题库1.正确答案:A2.正确答案:C3.正确答案:子孙；祖先4.正确答案:广义表又称列表，是由n（n≥0）个元素组成的有穷序列：GL=（e1，e2，……en），但与线性表不同