2024年高等教育工学类自考-02331数据结构考试近5年真题附答案

（图片大小可自由调整）2024年高等教育工学类自考-02331数据结构考试近5年真题荟萃附答案第I卷一.参考题库(共100题)1.求解平方根的迭代函数定义如下： 其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。2.一棵深度为8（根的层次号为1）的满二叉树有（）个结点。A、256B、255C、128D、1273.数据结构主要研究（），（），（）三个方面的内容。4.在链表中，每个结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是（）。5.数据的存储结构是数据的逻辑结构的存储映象。6.请利用两个栈S1和S2来模拟一个队列。已知栈的三个运算定义如下：PUSH（ST，X）：元素X入ST栈；POP（ST，X）：ST栈顶元素出栈，赋给变量X；Sempty（ST）：判ST栈空否。那么如何用栈的运算来实现该队列的三个运算：enqueue：插入一个元素入队列；dequeue：删除一个元素出队列；queue_empty：判队列为空。（请写明算法的思想及必要的注释）7.下列对于线性链表的描述中正确的是（）。A、存储空间不一定是连续，且各元素的存储顺序是任意的B、存储空间不一定是连续，且前件元素一定存储在后件元素的前面C、存储空间必须连续，且前件元素一定存储在后件元素的前面D、存储空间必须连续，且各元素的存储顺序是任意的8.在对n个元素进行冒泡排序的过程中，至少需要（）趟完成。A、1B、nC、n-1D、n/29.若一个元素序列基本有序，则选用（）排序较快。A、堆排序B、快速排序C、直接插入法D、直接选择排序10.队列是特殊的线性表，其特殊性在于（）11.数据结构里，栈的应用很广泛，递归问题的解决都要靠栈来完成，以下可以递归实现的有（）。A、斐波那契数列B、n！（n的阶乘）C、汉诺塔问题D、迷宫问题12.排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。13.设关键字序列为（71，12，88，53，11，25，65，27，16），散列函数为H（key）=key%7，采用链地址法解决冲突。请回答：请求等概率下查找成功的平均查找长度ASL14.（101，88，46，70，34，39，45，58，66，10）是堆。15.二叉排序树中，最小值结点的（）。A、左指针一定为空B、右指针一定为空C、左、右指针均为空D、左、右指针均不为空16.循环队列解决了普通队列的什么问题（）。A、假溢出B、溢出C、空D、都不对17.通常使用队列来处理函数或过程的调用。18.如果要将序列（50，16，23，68，94，70，73）建成堆，只需把16与（）交换。19.散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。20.顺序表是逻辑结构是线性结构而存储结构是（）的数据结构。A、顺序存储结构B、链式存储结构C、花式存储结构D、跳跃存储结构21.通过建立索引表来存取数据的文件有（）A、散列文件B、VSAM文件C、ISAM文件D、顺序文件E、倒排文件22.在构造哈希表的过程中，不可避免地会出现冲突，通常解决它的方法有（）A、平方取中法B、开放地址法C、随机探查法D、再哈希法E、拉链分散法（链地址法）23.已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。24.在初始数据表已经有序时，快速排序算法的时间复杂度为O（nlog2n）。25.设有森林如图所示，请回答： 画出该二叉树的中序线索二叉链表的图示并给出C语言描述。26.通常对数组进行的两种基本操作是（）。A、建立与删除B、索引和修改C、查找和修改D、查找与索引27.已知一组元素为（46，25，78，62，12，37，70，29），画出按元素排列顺序输入生成的一棵二叉搜索树。28.数据结构里，树是一种特殊的一对多的逻辑结构，当一个结点也没有时，它就称为（）。A、满树B、空树C、二叉树D、多叉树29.在散列技术中，处理冲突的两种主要方法是（）和（）。30.栈是后进先出（先进后出）的（）。A、线性表B、链表C、单链表D、索引表31.朴素模式匹配算法，算法运行时间为O（m*n）。32.由带权为，9、2.5，7，的四个叶子结点构造一裸哈夫曼树.该树的带权路径长度为（）。33.链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比34.什么是算法分析？算法分析主要考虑哪几方面的内容？35.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是：（）A、M1B、M1+M2C、M3D、M2+M336.算法中R[n+1]的作用是什么？37.有向图G可拓扑排序的判别条件是（）。38.链式存储的线性表中的指针指向其（）。A、前趋结点B、后继结点C、物理前趋D、物理后继39.设输入序列为20，45，30，89，70，38，62，19依次插入到一棵2-3树中（初始状态为空）。 再删除38，该B-树为（）。A、aB、bC、cD、dE、eF、f40.下面程序段的时间复杂度为（）。 i=1； while（iA、O（n）B、O（3n）C、O（log3n）D、O（n3）41.对于双目操作符，其重载函数带有（）个参数，其中至少有一个为（）的类型。42.数据结构里，实参和形参的关系（）。A、实参传给形参B、实参的类型要与形参一致C、实参的个数要与实参一致D、实参的名称要与形参的一致43.下面程序的时间复杂为（） A、AB、BC、CD、D44.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。 A、AB、BC、CD、D45.若一个图的边集为{，，，，，}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为（）。A、 1，2，3，4，5B、 1，2，4，3，5C、 1，2，4，5，3D、 1，4，2，5，346.网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。 47.二叉树是否可以为空二叉树？（）。A、不可以为空B、可以为空C、不确定D、都不对48.n个顶点的强连通有向图G，最多有（）条边，最少有（）边。强连通图即是任何两个顶点之间有路径相通，当所有结点在一个环上时，必定是强连通图。49.找出所有满足下列条件的二叉树： （a）它们在先序遍历和中序遍历时，得到的节点访问序列相同； （b）它们在后序遍历和中序遍历时，得到的结点访问序列相同； （c）它们在先序遍历和后序遍历时，得到的节点访问序列相同。50.设有一个栈，按A、B、C的顺序进栈，则下列（）为不可能的出栈序列。A、ABCB、CBAC、CABD、ACB51.数据结构里，二叉树中的结点都是度为2的结点。52.简述栈与队列的相同点与不同点。53.在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（）对相邻元素之间的交换。A、 n／2B、 n-1C、 nD、 n+154.数据结构里，在顺序表中，插入和删除时移动元素的个数与该元素的位置有关。55.设要将序列（q，h，c，y，p，a，m，s，r，d，f，x）中的关键码按字母升序重新排序，回答。（）是初始步长为4的shell排序一趟扫描的结果。A、f，h，c，d，p，a，m，q，r，s，y，xB、p，a，c，s，q，d，f，x，r，h，m，yC、a，d，c，r，f，q，m，s，y，p，h，xD、h，c，q，p，a，m，s，r，d，f，x，yE、h，q，c，y，a，p，m，s，d，r，f，x56.假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是（）A、B、C、D、A、EB、E、D、A、C、BC、B、C、A、D、ED、A、E、D、C、B57.在顺序表（n足够大）中进行顺序查找，其查找不成功的平均长度是（）。A、（n+1）/2B、n/2+1C、nD、n+158.对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为（）。A、 k1B、 k2C、 k1-k2D、 k1+k259.对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。A、k1B、k2C、k1-k2D、k1+k260.求子串在主串中首次出现的位置的运算称为（）。61.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为（）。A、236B、239C、242D、24562.（）遍历二叉排序树可得到一个有序序列。63.数据结构里，下列选项中关于顺序表的概念理解正确的是（）。A、线性表采用链式存储结构B、线性表采用顺序存储结构C、线性表采用索引存储结构D、线性表采用散列存储结构64.具有n个顶点的连通图至少有多少条边？65.在深度为7的满二叉树中，叶子结点的个数为（）A、32B、31C、64D、6366.串是一种特殊的线性表，其特殊性体现在（）A、可以顺序存储B、数据元素是一个字符C、可以链式存储D、数据元素可以是多个字符67.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。A、最大概率B、最小概率C、平均概率D、同等概率68.算法分析的目的是（），算法分析的两个主要方面是（）。69.下面关于工程计划的AOE网的叙述中，不正确的是（）A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动都提前完成，那么整个工程将会提前完成D、某些关键活动若提前完成，那么整个工程将会提前完70.（）二叉排序树可以得到一个从小到大的有序序列。A、先序遍历B、中序遍历C、后序遍历D、层次遍历71.稀疏多项式采用的顺序存储结构SqPoly定义为： 采用上题给定的条件和存储结构，编写求P（x）=Pn1（x）-Pn2（x）的算法，将结果多项式存放在新辟的空间中，并分析你的算法的时间复杂度。72.有一个n个顶点的有向完全图的弧数（）。73.下列选项中属于算法的特性是（）。A、可行性B、数据C、数据项D、程序74.广义表A=（（a），a）的表头是（）。A、aB、B.C、bD、D.（）75.对稀疏矩阵进行压缩存储是为了节省存储空间。76.p是一个结构体指针变量，它有一个成员变量叫sex，则使用格式正确的是（）。A、p->sexB、p%sexC、p#sexD、p&sex77.字符在串中的位置，即是字符在该序列中的（）78.设有一个空栈，栈顶指针为1000H，现有输入序列为12345，push，push，pop，push，pop，push，push后，输出序列为（），栈顶指针是（）。79.满二叉树是完全二叉树的特例。80.算法的特性包括：输入、输出、有穷性、确定性、可行性。81.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。82.斐波那契数列的计算，可以使用递归的方式计算，则需要使用哪项来帮助完成。（）A、栈B、图C、二叉树D、队列83.在所有排序方法中，（）方法采用的是两两有序表合并的思想。84.假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要（）趟完成。85.在双向链表存储结构中，删除p所指的结点时须修改指针（）。A、p-＞next-＞prior=p-＞prior； p-＞prior-＞next=p-＞next；B、p-＞next=p-＞next-＞next； p-＞next-＞prior=p；C、p-＞prior-＞next=p； p-＞prior=p-＞prior-＞prior；D、p-＞prior=p-＞next-＞next； p-＞next=p-＞prior-＞prior；86.设二维数组A[1„m，1„n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为（）。A、n*（i－1）＋jB、n*（i－1）＋j－1C、i*（j－1）D、j*m＋i－187.一棵二叉树的广义表表示为a（b（c，d），e（f（，g））），它含有双亲结点（）个，单分支结点（）个，叶子结点（）个。88.深度为h的非空二叉树的第i层最多有2i-1个结点。89.顺序表和链表中能实现随机存取的是（），插入、删除操作效率高的是（）90.n个结点无向完全图的的边数为（），n个结点的生成树的边数为（）。91.对于一棵完全二叉树采用顺序存储，设一个结点的编号为i（根结点的编号为1，若它的左孩子结点存在，则其编号为（）92.在一个带头结点的单循环链表中，P指向尾结点的直接前驱，则指向头结点的指针head可用P表示为head=（）。93.设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。94.对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序（由小到大排序），当把第6个记录7插入有序表，为寻找插入位置需比较（）次。95.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。96.下列排序方法中，哪一种方法的比较次数与纪录的初始排列状态无关（）A、直接插入排序B、起泡排序C、快速排序D、直接选择排序97.对于给定的n个元素，可以构造出的逻辑结构有（）、（）、（）、（）四种。98.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为（）。A、归并排序B、选择排序C、交换排序D、插入排序99.若邻接表中有奇数个表结点，则一定（）A、图中有奇数个顶点B、图中有偶数个顶点C、图为无向图D、图为有向图100.序列13，11，14，12，17，15，采用冒泡排序算法，经一趟冒泡后，序列的结果是（）。第I卷参考答案一.参考题库1.参考答案：2.参考答案：B3.参考答案：数据的逻辑结构；数据的存储结构；数据的运算4.参考答案：2/35.参考答案：正确6.参考答案：7.参考答案：A8.参考答案：A9.参考答案：C10.参考答案：只允许在表的一端进行元素插入而在另一端进行元素的删除11.参考答案：A,B,C,D12.参考答案：正确13.参考答案：ASL成功=（1*5+2*2+3*1+4*1）=16/914.参考答案：正确15.参考答案：A16.参考答案：A17.参考答案：错误18.参考答案：5019.参考答案：正确20.参考答案：A21.参考答案：B,C,E22.参考答案：B,C,D,E23.参考答案：24.参考答案：错误25.参考答案：26.参考答案：C27.参考答案：28.参考答案：B29.参考答案：开放定址法；拉链法30.参考答案：A31.参考答案：正确32.参考答案：4433.参考答案：A34.参考答案：算法的研究与实际问题直接相关，用来解一个问题可以有很多不同的算法，他们之间的效果可能会有很大差异。算法设计者最关心的就是什么是有效的算法，如何评价一个算法的优劣，如何从多种算法中选择好的算法。除了要首先考虑算法的正确性外，还要分析和评价算法的性能。分析和评价算法的性能主要要考虑以下两个方面： ①时间代价：执行算法所耗费的时间。一个好的算法首先应该比其他算法的运行时间代价要小。算法的时间代价的大小用算法的时间复杂度来度量。 ②空间代价：执行算法所耗费的存储空间，主要是辅助空间。算法运行所需的空间消耗是衡量算法优劣的另一个重要因素。算法的空间代价的大小用算法的空间复杂度来度量。35.参考答案：D36.参考答案：哨兵。避免边界检测，提高程序运行效率。37.参考答案：没有回路38.参考答案：B39.参考答案：F40.参考答案：C41.参考答案：2；用户自定义42.参考答案：A