2023年高等教育工学类自考-02331数据结构考试历年高频考点试题含答案

2023年高等教育工学类自考-02331数据结构考试历年高频考点试题含答案（图片大小可自由调整）第1卷一.参考题库(共50题)1.一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？2.简述在磁盘上存储信息的原则。3.不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。4.顺序表中，插入一个元素所需移动的元素平均数是（）。A、（n-1）/2B、n/2C、n+1D、（n+1）/25.算法分析的目的是（），算法分析的两个主要方面是（）。6.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的（）、（）和（）。7.空串是（），其长度等于（）。8.表示图的三种存储结构为（）、（）和（）。9.简述Floyd算法的作用和具体步骤。10.快速排序的时间复杂性不受数据初始状态影响，恒为O（nlog2n）。11.简述文件各维护操作的含义和过程。12.已知二叉排序树的左右子树均不为空，则（）上所有结点的值均小于它的根结点的值（）上所有结点的值均大于它的根结点的值。13.带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。14.（）是HASH查找的冲突处理方法。A、求余法B、平方取中法C、二分法D、开放地址法15.用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。16.树若不是空树，则有一个结点叫做什么，它没有前驱（）。A、叶子B、根结点C、树叉D、终端结点17.如果以链表作为栈的存储结构，则出栈操作时（）A、必须判别栈是否满B、必须判别栈是否空C、必须判别栈元素类型D、队栈可不做任何判别18.算法的空间复杂度记为：S（n）=O（f（n））。19.数据结构里，结构体的名字可以是关键字，如float。20.线性表是n个（）的有限序列。A、表元素B、字符C、数据元素D、数据项21.允许在线性表的一端插入，另一端进行删除操作的线性表称为（）。插入的一端为（），删除的一端为（）。22.在散列存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越（）；α值越小，则存取元素发生冲突的可能性就越（）。23.若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到（）的序列。A、1，2，3B、1，3，2C、2，1，3D、2，3，1E、3，1，2F、3，2，124.在线性表的哈希存储中，装填因子又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则α等于（）25.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个节点。26.对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。A、k1B、k2C、k1-k2D、k1+k227.在哈夫曼树中，权值最小的结点离根结点最近28.在队列这章中，循环队列解决了普通队列遇到的（）问题。A、空间不足B、假溢出C、元素过多D、分配不出空间29.广义表（a，b，c）的表尾是（）。A、b，cB、（b，C.C、cD、D.30.具有4个顶点的无向完全图有（）条边。A、20B、16C、12D、631.下列四种排序方法中，不稳定的方法是（）A、直接插入排序B、冒泡排序C、归并排序D、直接选择排序32.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。A、2B、3C、4D、633.若一条路径上的开始点和结束点为同一个顶点，则称该路径为（）。34.在索引顺序表的查找中，对索引表既可以采取顺序查找，也可以采用折半查找。35.假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。36.若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。37.A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。A、i（i+1）/2+jB、j（j+1）/2+iC、i（j-i）/2+1D、j（i-1）/2+138.数据结构里，单链表是指（）。A、有两个指针域的链表。B、只有一个指针域的链表。C、有三个指针域的链表。D、没有指针域的链表。39.树若有根结点，只能有一个。40.下面（）是顺序存储结构的优点。A、存储密度大B、插入运算方便C、查找方便D、适合各种逻辑结构的存储表示41.已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a.在P结点后插入S结点的语句序列是（）。 b.在P结点前插入S结点的语句序列是（）。 c.删除P结点的直接后继结点的语句序列是（）。 d.删除P结点的直接前驱结点的语句序列是（）。 e.删除P结点的语句序列是（）。 （1）P->next=P->next->next； （2）P->priou=P->priou->priou； （3）P->next=S； （4）P->priou=S； （5）S->next=P； （6）S->priou=P； （7）S->next=P->next； （8）S->priou=P->priou； （9）P->priou->next=P->next； （10）P->priou->next=P； （11）P->next->priou=P； （12）P->next->priou=S； （13）P->priou->next=S； （14）P->next->priou=P->priou； （15）Q=P->next； （16）Q=P->priou； （17）free（P）； （18）free（Q）；42.栈的应用比较广泛，入栈和出栈都在栈的一端，这端称为（）。A、栈顶B、栈底C、栈中D、都不对43.对于一个有向图（如图），假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 44.用顺序存储结构存储串S，编写算法删除S中第i个字符开始的连续j个字符。45.有数组A[4][4]，把1到16个整数分别按顺序放入A[0][0]，……，A[0][3]，A[1][0]，……，A[1][3]，A[2][0]，……，A[2][3]，A[3][0]，……，A[3][3]中，编写一个函数获得数据并求出两条对角线元素的乘积。46.下列四个序列中，（）是堆。A、75，65，30，15，25，45，20，10B、75，65，45，10，30，25，20，15C、75，45，65，30，15，25，20，10D、75，45，65，10，25，30，20，1547.有回路的图不能进行拓扑排序。48.在作进栈运算时，应先判别栈是否（）。A、空B、满C、上溢D、下溢49.数据结构里，在算法时间复杂度中，O（log2n）属于（）。A、常数阶B、线性阶C、平方阶D、对数阶50.下列选项中关于算法的理解描述错误的是（）。A、算法是程序设计的灵魂B、程序=数据结构+算法C、算法就是解决问题的方法和步骤D、算法是关于数学中数字的运算与计算机处理无关第1卷参考答案一.参考题库1.正确答案:一个带权无向图的最小生成树不一定是唯一的。从Kruskal算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。2.正确答案:盘面的转速很快，磁盘读写数据的时间大部分花在柱面定位上。寻查时间的长短取决于读写磁头移过的柱面数，所以在磁盘上存储信息时应尽量将相关的信息放在同一柱面或者邻近柱面上，以减少寻查时间。3.正确答案:正确4.正确答案:B5.正确答案:分析算法的效率以求改进；空间性能和时间性能6.正确答案:行下标列下标元素值7.正确答案:零个字符的串；零8.正确答案:邻接矩阵；邻接表；边集数组9.正确答案:10.正确答案:错误11.正确答案:文件维护是指对文件中记录所进行的插入、删除、修改等操作。这些操作的具体含义和操作过程描述如下： A.插入：向文件中添加一条新的记录。若文件按某个关键字顺序排列，则插入记录前一般要先通过检索确定插入点的位置。 B.删除：从文件中删除一条记录。删除记录前一般要先通过检索确定所要删除记录的位置。 C.修改：对记录中的一个或多个数据项进行修改。若文件按某个关键字顺序排列，且对关键字值进行了修改操作，则修改后还需将记录移动到正确的位置（一般采用先删除再插入的方式实现）。12.正确答案:左子树；右子树13.正确答案:正确14.正确答案:D15.正确答案:正确16.正确答案:B17.正确答案:B18.正确答案:正确19.正确答案:错误20.正确答案:C21.正确答案:队列；队尾；队头22.正确答案:大,小23.正确答案:E24.正确答案:n/m25.正确答案:正确26.正确答案:A27.正确答案:错误28.正确答案:B29.正确答案:B30.正确答案:D31.正确答案:C32.正确答案:C33.正确答案:回路成环34.正确答案:正确35.正确答案:任何前n个序列中S的个数一定大于X的个数。 设两个合法序列为： T.1=S……X……S…… T.2=S……X……X…… 假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。 第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。36.正确答案:错误37.正确答案:B38.正确答案:B39.正确答案:正确40.正确答案:C41.正确答案:a.（7）（3）（6）（12） b.（8）（4）（5）（13