2024年高等教育工学类自考-02331数据结构笔试历年真题荟萃含答案

2024年高等教育工学类自考-02331数据结构笔试历年真题荟萃含答案（图片大小可自由调整）答案解析附后卷I一.参考题库(共25题)1.二叉树中不存在度大于2的结点，当某个结点只有一棵予树时无所谓左、右子树之分。2.为多个值相同的元素分配一个存储空间；对零元素不分配空间，称为（）。3.设有森林B=（D，S）， D={A，B，C，D，E，F，G，H，I，J}，r∈S r={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈C，F〉，〈G，H〉，〈G，I〉，〈I，J〉}请回答：写出此二叉树的前序、中序、后序遍历序列。4.设无向图G（如图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。 5.写出下面函数被调用执行后，得到的以HL为表头指针的单链表中的数据元素序列。 6.数据结构中常用的存储方法有：（）7.对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为（）。8.二叉树是一棵结点的度最大为二的树。9.对用数组存储的线性表（16，15，32，11，6，30），用快速排序算法进行由小到大排序，若排序下标范围为0~5，选择元素16作为支点，调用一趟快速排序算法后，元素16在数组中的下标位置为（）10.若以{4，5，6，7，8}作为权值构造哈夫曼树，则该树的带权路径长度为（）。A、67B、68C、69D、7011.简述多重表文件和倒排文件两种多关键字文件的组织方法。12.在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较（）次。（由小到大排序）13.广义表的（a，（a，b），d，e，（（i ，j），k））深度是（）。14.具有什么性质的问题适合贪心策略求解？15.广义表的组成元素可以是不同形式的元素。16.若L是splist类型的顺序表，则表中的第i个数据元素是（）。17.在线索化二叉树中，t所指节点没有左子树的充要条件是（）A、t-＞left=NULLB、t-＞ltag=1C、t-＞ltag=1且t-＞left=NULLD、以上都不对18.如何实现线性表的顺序存储结构？19.已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是（）20.设单循环链表L1，对其遍历的结果是：x1，x2，x3，…，xn-1，xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1，x3，…；L2中含有原L1表中序号为偶数的结点且遍历结果为：…，x4，x2。21.数据结构里，strlen计算字符串长度时候计算’/0’在内。22.一个算法应该是（）。A、程序B、问题求解步骤的描述C、要满足五个基本特性D、A和C23.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为（）。 24.设计计算二叉树中所有结点值之和的算法。25.有一个顺序存储的栈，最大存储空间MaxSize=5，栈顶指针top，现有A、B、C、D四个元素。画出以上四个元素依次进栈后的状态。卷II一.参考题库(共25题)1.设有10阶矩阵A，其对角线以上的元素aij均取值为-3，其他矩阵元素为正整数，现在将矩阵A压缩存放在一维树组F[m]中，则m为（）。A、45B、46C、55D、562.设有串P1=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四个串中最小的是（）。3.入栈的先后顺序为a，b，c，d，e，（入栈和出栈可以间隔进行）则出栈顺序可能是（）。A、a，b，c，d，eB、e，d，c，b，aC、c，b，a，d，eD、d，b，c，a，e4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）A、当前位置B、任意位置C、前一个位置D、后一个位置5.下列选项中是C语言中的字符串的结束符是（）。A、‘/0’B、‘/n’C、‘/t’D、‘/a’6.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。7.为提高在外排序过程中，对长度为N的初始序列进行“置换—选择”排序时，可以得到的最大初始有序段的长度不超过N/2。8.一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。A、14B、15C、19D、189.设有森林如图所示，请回答： 画出该二叉树的中序线索二叉链表的图示并给出C语言描述。10.线性表就是顺序存储的表11.对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。12.具有n个顶点的强连通图至少有多少条边？这样的图应该是什么形状？13.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。14.已知关键字序列（38，12，21，77，65，7，38，53）给出采用快速排序方法按关键字增序排序时的第一趟块排过程，并举出一个反例说明快速排序是不稳定排序。15.表长为0的线性表称为（）16.在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。17.折半搜索与二叉搜索树的时间性能（）A、相同B、完全不同C、有时不相同D、数量级都是O（log2n）18.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。A、54321B、45321C、43512D、1234519.树的先根遍历20.二维数组A的每个元素是由10个字符组成的串，其行下标i=0，1，„，8，列下标j=1，2，„，10。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。A、A[8，5]B、A[3，10]C、A[5，8]D、A[0，9]21.计算机算法指的是（）A、计算方法B、调度方法C、排序方法D、解决某一问题的有限运算序列22.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。23.数据结构里，抽象数据类型是由（）组成的。A、一个数学模型B、定义在该模型上一组操作C、抽象的概念D、数据的概念24.引入二叉线索树的目的是（）A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一25.稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。卷III一.参考题库(共25题)1.设哈希函数H（key）=keyMOD13，用线性探测再散列法解决冲突.对关键字序列{55，19，01，68，23，27，20，84}在地址空间为0-10的散列区中建哈希表，画出此表，并求等概率情况下查找成功时的平均查找长度.2.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为（），采用邻接表表示的空间复杂性为（）3.在栈中存取数据遵从的原则是（）。4.对一个具有n个元素的线性表，建立其单链表的时间复杂度为（）A、O（n）B、O（1）C、O（n2）D、O（nlog2n）5.栈的特性是先进先出。6.假定一个待散列存储的线性表为（32，75，29，63，48，94，25，46，18，70），散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。7.设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。A、2m-1B、2mC、2m+1D、4m8.已知一棵二叉树的中序遍历结果为D、G、B、A、E、C、H、F、I，后序遍历结果为G、D、B、E、H、I、F、C、A，请给出该二叉树的先序遍历结果。9.从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一部分中所有元素都小于等于所选元素，后一部分中所有元素都大于或等于所选元素，而此时所选元素处在排序的最终位置。这种排序法称为（）排序法。10.输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求： ⑴画出该二叉排序树； ⑵画出删除结点302后的二叉排序树。11.完全二叉树12.每种数据结构都应具备三种基本运算：插入、删除和搜索。13.下面程序段的时间复杂度为（） 14.二又树第i（i>=1）层上至多有（）个结点。15.如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（）就是不稳定的排序方法。A、起泡排序B、归并排序C、Shell排序D、直接插入排序16.对一组记录（1，3，9，2，12，7，5，4，6）进行直接插入排序（由小到大排序），当把第6个记录7插入有序表，为寻找插入位置需比较（）次。17.假设在算法描述语言中引入指针的二元运算“异或”，若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指向链表中的最右结点，则可实现从左向右或从右向左遍历此双向链表的操作。试写一算法按任一方向依次输出链表中各元素的值。18.一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。19.某内排序方法的稳定性是指（）。A、该排序算法不允许有相同的关键字记录B、该排序算法允许有相同的关键字记录C、平均时间为0（nlogn）的排序方法D、以上都不对20.表达式a*（b+c）-d的后缀表达式是（）。21.一个图的（）表示法是惟一的。22.查找相同结点的效率折半查找总比顺序查找高。23.具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。24.关于顺序表、链表，以下描述错误的是（）。A、链表中的头结点仅起到标识的作用。B、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。C、顺序存储方式只能用于存储线性结构。D、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。25.一棵深度为h的B-树，任一个叶子结点所处的层数为（），当向B-树中插入一个新关键字时，为检索插入位置需读取（）个结点。卷I参考答案一.参考题库1.参考答案:错误2.参考答案:压缩存储3.参考答案:前序遍历序列：ABECFDGHIJ 中序遍历序列：EBFCDAHJIG 后序遍历序列：EFDCBJIHGA4.参考答案:5.参考答案:（12，26，9，8，15，30，50）6.参考答案:顺序，链接，索引，散列7.参考答案:n（n-1）/28.参考答案:错误9.参考答案:310.参考答案:C11.参考答案:多重表文件是将索引方法和链接方法相结合的一种文件组织方式，对主关键字建立的索引称为主索引，对每个需做查询操作的次关键字建立的索引称为次索引。在多重表文件中，记录通常按主关键字顺序排列，同时将具有相同次关键字值的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字作为对应次索引表中的索引项。 与多重表文件不同，倒排文件中具有相同次关键字的记录之间不进行链接，而是在对次关键字建立的索引中列出具有该次关键字值的所有记录的物理地址。倒排文件中的次关键字索引称为倒排表，倒排表与主文件一起就构成了倒排文件。12.参考答案:313.参考答案:314.参考答案:具有如下性质： 第一、最优子结构性质； 第二、贪心选择性质。15.参考答案:正确16.参考答案:Lelem[i-1]17.参考答案:B18.参考答案:把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里就构成了线性表的顺序存储，采用顺序存储结构的线性表简称顺序表。线性表的顺序存储结构有如下特点： 线性表中所有元素所占的存储空间是连续的； 线性表的逻辑顺序与物理顺序一致； 数组中的每一个元素的位置可以用公式来确定。假设线性表中的第一个数据元素的存储地址（指第一个字节的地址，即首地址）为LOC（e1），每一个数据元素占k个字节，则线性表中第i个元素ei在计算机存储空间中的存储地址为：19.参考答案:将矩阵第i行全部置为020.参考答案:算法如下： 21.参考答案:错误22.参考答案:B23.参考答案:（38，56，25，60，42，74）24.参考答案:25.参考答案:卷II参考答案一.参考题库1.参考答案:D2.参考答案:P13.参考答案:A,B,C4.参考答案:C5.参考答案:A6.参考答案:7.参考答案:错误8.参考答案:C9.参考答案:10.参考答案:错误11.参考答案:错误12.参考答案:具有n个顶点的强连通图至少有n条边，这样的图是一个由n个顶点构成的环。 强连通图是相对于有向图而言的。由于强连通图要求图中任何两个顶点之间能够相互连通，因此每个顶点至少要有一条以该顶点为弧头的弧和一条以该顶点为弧尾的弧，每个顶点的入度和出度至少各为1，即顶点的度至少为2，这样根据图的顶点数、边数以及各项点的度三者之间的关系计算可得：边数=2×n/2=n。13.参考答案:错误14.参考答案:15.参考答案:空表16.参考答案:正确17.参考答案:C18.参考答案:C19.参考答案:若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。20.参考答案:B21.参考答案:D22.参考答案:正确23.参考答案:A,B24.参考答案:A25.参考答案:三元组顺序表；十字链表卷III参考答案一.参考题库1.参考答案: ASLsucc=(1+2+1+2+1+1+3+1)/8=1.52.参考答案: