2024年高等教育工学类自考-02331数据结构历年高频考点试卷专家荟萃含答案

2024年高等教育工学类自考-02331数据结构历年高频考点试卷专家荟萃含答案（图片大小可自由调整）第1卷一.参考题库(共25题)1.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（）A、直接插入排序B、起泡排序C、快速排序D、直接选择排序2.在单链表中，NULL称为（），它不指向任何结点，只起（）作用。3.数据的存储结构是数据的逻辑结构的存储映象。4.下面关于线性表的叙述错误的是（）A、线性表采用顺序存储必须占用一片连续的存储空间B、线性表采用链式存储不必占用一片连续的存储空间C、线性表采用链式存储便于插入和删除操作的实现D、线性表采用顺序存储便于插入和删除操作的实现5.下面叙述中，不正确的是（）。A、线性表中除第一个元素和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继B、树中有且仅有一个结点没有前驱C、环形队列中任何一个元素都有且仅有一个直接前驱和一个直接后继D、在树中，一个结点可以有多个直接后继6.一棵二叉树，有1个2度结点，，2个1度结点，则该树共有（）个结点。7.建立一个长度为n的有序单链表的时间复杂度为（） A、AB、BC、CD、D8.若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。A、j-iB、i-j-1C、i-jD、i-j+19.把下列森林转换为二叉树。 10.简述归并排序的处理步骤。11.用数组Q表示一个环形队列，f为当前对头元素的钱一位置，r为队尾元素的位置。假定队列中元素个数总小于n，求队列中元素个数公式是（）。12.对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为（）；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为（）13.研究数据结构就是研究（）。A、数据的逻辑结构B、数据的存储结构C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其基本操作14.假设在算法描述语言中引入指针的二元运算“异或”，若a和b为指针，则a⊕b的运算结果仍为原指针类型，且a⊕（a⊕b）=（a⊕a）⊕b=b；（a⊕b）⊕b=a⊕（b⊕b）=a。则可利用一个指针域来实现双向链表L。链表L中的每个结点只含两个域：data域和LRPtr域，其中LRPtr域存放该结点的左邻与右邻结点指针（不存在时为NULL）的异或。若设指针L.Left指向链表中的最左结点，L.Right指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。15.在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较（）次。16.已知一无向图G=（V，E），其中V={a，b，c，d，e}E={（a，b），（a，d），（a，c），（d，c），（b，e）}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是（）方法。17.下列图的深度优先遍历序列为（）。 A、ABCDEFGHB、ABDHECFGC、ABEDHCFGD、ABCFGEDH18.数组是同类型值的集合。19.无向图中，两顶点之间有边则互为（）。A、邻接点B、兄弟C、堂兄弟D、邻居20.线性表的链接存储结构是一种（）存储结构。A、 随机存取B、 顺序存取C、 索引存取D、 散列存取21.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。22.当结点之间存在M对N（M：N）的联系时，称这种结构为（）23.如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。24.下列选项中是结构体普通变量或指针变量引用其成员时使用时的符号的是（）。A、->符号B、.符号C、->>符号D、#符号25.在长度为n的循环队列中，删除其节点为x的时间复杂度为（）。第2卷一.参考题库(共25题)1.一个队伍的入队列是1234，则队列的输出顺序是（）。2.查找3.在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。4.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（） A、AB、BC、CD、D5.树的后根遍历序列等同于与该树对应的二叉树的哪种序列？（）A、 前序序列B、 中序序列C、 后序序列D、 层序序列6.数据结构里，函数参数为哪项时，参数传递属于值传递。（）A、数组B、指针C、字符数组D、int型7.数据结构里，结构体数组，即定义数组的每个元素都是一个结构体类型的。8.数据结构里，逻辑结构和存储结构指的是同一件事。9.在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链接的表头指针向量大小至少为（）A、nB、2nC、eD、2e10.数据结构是研讨数据的（）和（），以及它们之间的相互关系，并对与这种结构定义相应的（），设计出相应的（）11.在队列中，下列说法正确的是（）。A、每次插入总是在队尾，每次删除总是在队头B、每次插入总是在队尾，每次删除也总是在队尾C、每次插入总是在队头，每次删除也总是在队头D、每次插入总是在队头，每次删除总是在队尾12.对平衡二叉树进行中根遍历，可得到结点的有序序列。13.设计判断单链表中元素是否是递增的算法。14.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。15.假定对长度n=50的有序表进行二分查找，则对应的判定树高度为（），判定树中前5层的结点数为（），最后一层的结点数为（）。16.在一个顺序栈中，若栈顶指针等于（），则为空栈；若栈顶指针等于（），则为满栈。17.下面程序段的时间复杂度为（） 18.广义表19.连续存储设计时，存储单元的地址（）A、一定连续B、一定不连续C、不一定连续D、部分连续，部分不连续20.数据结构被形式地定义为＜D，R＞，其中R是（）的有限集。A、算法B、数据元素C、数据操作D、逻辑结构21.假定一个待哈希存储的线性表为（32，75，29，63，48，94，25，46，18，70），哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。 22.以下与数据的存储结构无关的术语是（）。A、循环队列B、链表C、哈希表D、栈23.具有n个顶点的有向无环图最多有多少条边？24.在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。A、p->next=q；q->prior=p；p->next->prior=q；q->next=q；B、p->next=q；p->next->prior=q；q->prior=p；q->next=p->next；C、q->prior=p；q->next=p->next；p->next->prior=q；p->next=q；D、q->next=p->next；q->prior=p；p->next=q；p->next=q；25.根据使用频率为5的字符设计的哈夫曼编码不可能是（）A、0，100，101，110，111B、0000，0001，001，01，1C、000，001，010，011，11D、00，01，10，110，111第3卷一.参考题库(共25题)1.如果只想得到一个序列中第k个最小元素之前的部分排序序列，最好采用什么排序方法？为什么？对于序列{57，40，38，11，13，34，48，75，25，6，19，9，7}，得到其第4个最小元素之前的部分序列{6，7，9，11}，使用所选择的排序算法时，要执行多少次比较？2.顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？3.下面算法的时间复杂度为（） A、O（1）B、O（n）C、O（n2）D、O（n!）4.（）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。5.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是（）、（）、（）。6.稀疏多项式采用的循环链表存储结构LinkedPoly定义为： 试以循环链表作稀疏多项式的存储结构，编写求其导函数的方法，要求利用原多项式中的结点空间存放其导函数多项式，同时释放所有无用结点。7.算法分析的两个主要方面是（）。A、空间复杂度和时间复杂度B、正确性和简单性C、可读性和文档性D、数据复杂性和程序复杂性8.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。9.设无向图G（如图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 10.如果将所有中国人按照生日来排序，则使用（）算法最快。A、归并排序B、希尔排序C、快速排序D、基数排序11.若串S＝‘software’，其子串的数目是（）。A、8B、37C、36D、912.已知函数定义如下：intfun（inta[]） { ......；//函数体省略 }则该函数的参数传递属于（）。A、值传递B、地址传递C、形参传递D、实参传递13.设计算法，将一个无向图的邻接表转换成邻接矩阵。14.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。A、LLB、LRC、RLD、RR15.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（）。A、 k1B、 k2C、 k1-k2D、 k1+k216.数据结构里，B有6个兄弟（不算自己），A是B的双亲，则A的度是（）。A、3B、6C、7D、817.线性表在物理存储空间中也一定是连续的。18.如果有向图中各个顶点的度都大于2，则该图中必有回路。19.已知一组元素的排序码为： （46，74，16，53，14，26，40，38，86，65，27，34）利用归并排序的方法写出每一趟二路归并排序后的结果。20.什么叫二维数组的行序优先存储？什么叫二维数组的列序优先存储？21.集合与线性表的区别在于是否按关键字排序22.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）A、CBEFDAB、FEDCBAC、CBEDFAD、不定23.写出快速排序的非递归调用算法。24.广义表（（a），a）的表尾是（）25.一组记录的关键字序列为（12，45，22，4，6，50），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）A、6，4，12，45，22，50B、6，4，12，22，45，50C、6，4，12，50，22，45D、4，6，12，22，45，50第1卷参考答案一.参考题库1.参考答案:D2.参考答案:空指针；标志3.参考答案:正确4.参考答案:D5.参考答案:C6.参考答案:57.参考答案:C8.参考答案:D9.参考答案:10.参考答案:归并排序的处理步骤为： A.记录分段处理：将文件中的记录按照可用内存大小划分为若干段，依次将每段记录读入到内存中对其进行内部排序，并将排序结果输出到子文件中。这样可以生成多个有序的子文件（即文件内的记录是有序的），通常称经过排序后的段为初始归并段。 B.文件归并处理：对上一步得到的初始归并段加以归并，直至将多段中的记录归并为一个有序文件为止。11.参考答案:（r-f+n）%n12.参考答案:O（1）；O（n）13.参考答案:D14.参考答案:15.参考答案:316.参考答案:深度遍历17.参考答案:B18.参考答案:错误19.参考答案:A20.参考答案:A21.参考答案:正确22.参考答案:网状结构23.参考答案:5024.参考答案:A,B25.参考答案:O(n)第2卷参考答案一.参考题库1.参考答案:1、2、3、42.参考答案:根据给定的关键字值，在特定的表中，确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。这个过程叫查找。3.参考答案:错误4.参考答案:C5.参考答案:B6.参考答案:D7.参考答案:正确8.参考答案:错误9.参考答案:A10.参考答案:逻辑结构；物理结构；操作（运算）；算法11.参考答案:A12.参考答案:正确13.参考答案:14.参考答案:错误15.参考答案:6；31；1916.参考答案:–1；StackMaxSize-117.参考答案:O(n)18.参考答案:广义表简称表，是零个或多个原子表所组成的有限序列。19.参考答案:A20.参考答案:C21.参考答案:22.参考答案:D23.参考答案:具有n个顶点的有向无环图最多有n×（n—1）/2条边。 这是一个拓扑排序相关的问题。—个有向无环图至少可以排出一个拓扑序列，不妨设这n个顶点排成的拓扑序列为v1，v2，v3，„，vn，那么在这个序列中，每个顶点vi只可能与排在它后面的顶点之间存在着以vi为弧尾的弧，最多有n-i条，因此在整个图中最多有（n-1）+（n-2）+„+2+1=n×（n-1）/2条边。24.参考答案:C25.参考答案:C第3卷参考答案一.参考题库1.参考答案:采用堆排序最合适，依题意可知只需取得第k个最小元素之前的排序序列时，堆排序的时间复杂度Ο（n+klog2n），若k≤nlog2n，则得到的时间复杂性是Ο（n）。 对于上述序列得到其前4个最小元素，使用堆排序实现时，执行的比较次数如下：初始建堆：比较20次，得到6； 第一次调整：比较5次，得到7； 第二次调整：比较4次，得到9； 第三次调整：比较5次，得到11。2.参考答案:一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。 采用循环队列是解决