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

2023年高等教育工学类自考-02331数据结构考试历年重点考核试题含答案（图片大小可自由调整）第1卷一.参考题库(共50题)1.线性表是n个元素的（）2.一个队列的入队序列是1，2，3，4，则队列的出队序列是（）。A、1，2，3，4B、4，3，2，1C、1，4，3，2D、3，4，1，23.对于长度为n的顺序存储的有序表，若采用二分查找法，则对所有元素的最长查找长度为（）的值向下取整再加1。A、log2（n+1）B、n／2C、log2nD、（n+1）／24.对以下单链表分别执行下列各程序段，并画出结果示意图。 5.设有键值序列（k1，k2，…，kn），当i>n/2时，任何一个子序列（ki，ki+1，…，kn）一定是堆。6.如果t中存在等于p的子串，就指出该子串在t中的位置，称为匹配成功；否则称为匹配失败。7.将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。A、O（1）B、O（n）C、O（m）D、O（m+n）8.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明（），若元素的值小于根结点的值，则继续向（）查找，若元素的值大于根结点的值，则继续向（）查找。9.已知一棵二叉树的后序遍历和中序遍历的序列分别为：ACDBGIHFE和ABCDEFGHI。请画出该二叉树，并写出它的前序遍历的序列。10.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用（）存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用（）存储结构为宜。11.设单循环链表中结点的结构为（data，link），且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是（）。A、current->link=nullB、first->link=currentC、first=currentD、current->link=first12.深度为3的二叉树最多有（）个结点。A、7B、8C、5D、613.设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。  ① 线性探测法；  ② 链地址法。14.以折半查找方法在一个查找表上进行查找时，该查找表必须组织成（）存储的（）表15.树的带权路径长度最小的二叉树中必定没有度为1的结点。16.找出所有满足下列条件的二叉树： （1）它们在先序遍历和中序遍历时，得到的遍历序列相同； （2）它们在后序遍历和中序遍历时，得到的遍历序列相同；  （3）它们在先序遍历和后序遍历时，得到的遍历序列相同17.下列与数据的存储结构无关的术语是（）A、栈B、散列表C、双链表D、二叉树18.将关键字（45，87，30，33，63，27，51，76）依次插入到一棵初始为空的二叉排序树中。请回答：若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与哪些关键字进行比较。19.对于一个有向图，不用拓扑排序，如何判定图中是否存在环？20.栈是一种特殊的线性表，允许插入和删除运算的一端称为（）。不允许插入和删除运算的一端称为（）。21.评价排序算法优劣的主要标准是（）和（）22.一个递归算法必须包括（）。A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分23.设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：假定每个关键字的查找概率相等，求查找成功时的平均查找长度。24.在栈这种数据结构中，栈能插入删除的一端称为栈顶。25.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的三项信息是（）、（）、（）。26.计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下： 27.二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节。28.设散列表的长度为16，散列函数为H（k）=k%13，用线性探测法处理冲突，依次插入关键字：19，01，13，23，24，55，20，84，27，68，11，10，77。请回答：画出散列表示意图并给出查找每个关键字时需要比较的次数。29.对于双目操作符，其重载函数带有（）个参数，其中至少有一个为（）的类型。30.一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。31.设有一空栈，现有输入序列1，2，3，4，5，经过push，push，pop，push，pop，push，push后，输出序列是（）32.（）排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。33.二叉树可以是空二叉树。34.二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。35.证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。36.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 37.顶点表示活动，边表示活动之间的先后关系的有向图为顶点活动网称为（）。38.已知数据序列{53，36，48，36，60，7，18，41}，写出采用简单选择排序的每一趟排序结果。39.带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。40.折半查找法适用于（）。A、有序顺序表B、有序单链表C、有序顺序表和有序单链表都可以D、无限制41.对给定的j（142.已知指针p指向单链表中某一结点，将新生成的由s所指结点加到p所指结点之后，其语句应为（）。A、s-＞next=p-＞next；p->next=s；B、（*p）.next=s；（*s）.next=（*p）.next；C、s-＞next=p-＞next；p-＞next=s-＞next；D、s-＞next=p+1； p-＞next=s；43.树若不是空树，则有一个结点叫做什么，它没有前驱（）。A、叶子B、根结点C、树叉D、终端结点44.写出运行下列程序段的输出结果。 45.下列四个说法哪个正确？（）A、堆栈是在两端操作、先进后出的线性表B、堆栈是在一端操作、先进先出的线性表C、队列是在一端操作、先进先出的线性表D、队列是在两端操作、先进先出的线性表46.计算机软件系统中，有两种处理字符串长度的方法：一种是（），第二种是（）47.消除递归不一定需要使用栈。48.堆排序是一种（）排序。A、插入B、选择C、交换D、归并49.对于长度为n的线性表，若采用分块查找（假定总块数和每块长度均接近，用顺序查找确定所在块），则时间复杂性为多少？50.数据结构里，已知product是结构体类型，下列选项中是定义含有十个元素是该类型的数组格式正确的是（）。A、structproducta[10]；B、structproducta{10}；C、structproducta；D、structproducta（10）；第1卷参考答案一.参考题库1.正确答案:有限序列2.正确答案:A3.正确答案:C4.正确答案:5.正确答案:正确6.正确答案:正确7.正确答案:C8.正确答案:查找成功；左子树；右子树9.正确答案:恢复的二叉树为： 10.正确答案:顺序；链接11.正确答案:D12.正确答案:A13.正确答案:14.正确答案:顺序；有序15.正确答案:正确16.正确答案:（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。17.正确答案:D18.正确答案:若在二叉排序树中插入新的关键字60，则为寻找插入位置，分别与关键字45,87,63,51进行比较。19.正确答案:对于无向图，如果在深度优先遍历中遇到回边，则必定存在环。对于有向图，如果从有向图的某个顶点v出发的遍历，在DFS(v)结束之前出现了一条从顶点u指向v的回边，则此有向图必定存在环。因为u在深度优先生成树上是v的子树，即存在u到v的路径，现在又出现一条从u指向v的弧，则它们必然构成一条回路。20.正确答案:栈顶栈底21.正确答案:时间复杂性；算法需要的附加空间22.正确答案:B23.正确答案:对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3+6）＝23/1124.正确答案:正确25.正确答案:行下标；列下标；数组元素26.正确答案:27.正确答案:54028.正确答案:29.正确答案:2；用户自定义30.正确答案:错误31.正确答案:2、332.正确答案:冒泡33.正确答案:正确34.正确答案:错误35.正确答案:任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。 假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。36.正确答案:DLR：A B D F J G K C