文档介绍：该【四川轻化工大学2023年《816数据结构与算法》考研专业课真题试卷 】是由【青山代下】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【四川轻化工大学2023年《816数据结构与算法》考研专业课真题试卷 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。四川轻化工大学2024年研究生招生考试业务课样卷(满分:150分,所有答案一律写在答题纸上)招生专业:085404计算机技术、085411大数据技术与工程、085412网络与信息安全考试科目:816数据结构与算法考试时间:3小时一、选择题(每题3分,共45分)()。()。,以下操作中,()在顺序表上实现比在链表上实现效率更高。(1<=i<=n),访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为()。(1),O(1)(n),O(1)(1),O(n)(n),O(n),出栈序列为BAC时,经过的栈操作为()。,pop,push,pop,push,,push,push,pop,pop,,push,pop,pop,push,,push,pop,push,pop,/(b-c)+d*e的后缀表达式是()。-d+e*/-de+**+-/-/de*+第1页(共6页){8,4,9,5,6,1,2,10,20}只能是下列排序算法中的()两趟排序后的结果。,()不能保证每趟排序至少能将一个元素放在其最终位置上。[m][n],设A[0][0]存放位置在644,A[2][2]存放位置在676,每个元素占一个空间,问A[3][3]存放在()位置。,则该二叉树的中序遍历序列不会是()。,则该二叉树的特点是()。,一定是()。,若输入的顶点信息即为顶点编号,则建立邻接表的时间复杂度为()。(n+e)(n*e)(n)(e),假设有k个关键字互为同义词,若用线性探查法把这k个关键字存入,至少要进行的探查次数是()。-+(k+1)/,在()时其查找效率最低。、填空题(每题3分,共30分)。voidfun(intn){inti=1;while(i<=n)i*=2;}第2页(共6页),建立一个有序单链表的最低时间复杂度是________。,其算法的时间复杂度是________。+2*3/(5-2+8*3)求值过程中当描到8时,操作数栈内容为____________。(从栈底依次写),若front与rear分别表示对头元素和队尾元素的位置,则判断循环队列空的条件是__________。,模式串P的长度是n,则经典字符串匹配算法(BF算法)的时间复杂度是__________。=(a,b,(c,d),e),写出得到字符d的操作(取表头用H,表尾用T表示)__________。(设根为第1层)有8个叶子结点,则该完全二叉树的结点个数最多有__________个。,第一、第二、第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是__________。{3,4,5,6,7},根据这些权值构造一棵Huffman树,则该树的带权路径长度WPL为__________。三、算法编程题(共35分)1.(10分)已知:btTree为二叉树结点类型,其左右孩子指针域分别为lchild、rchild,数据域为data,使用递归结构求二叉树的高度。请在depth函数中编写代码,实现上述功能,注意要求采用递归结构。intdepth(btTree*t){inth,lh,rh;//分别为树、左子树、右子树的高度变量//请在此处编写代码,实现本题的功能(每行一条语句,本题<14行)}第3页(共6页)2.(10分)编程实现将顺序表L中所有负数元素删除,返回被删除的元素个数。请在deln函数中编写代码,实现上述功能,注意本题要求时间复杂度为O(n)已知顺序表结点类型为:typedefstruct{intelem[100];intlength;}SQ;intdeln(SQ*L){//请在此处编写代码,实现本题的功能(每行一条语句,本题<12行)}3.(15分)已知递增有序的带头结点单链表A、B(A、B的长度分别为m、n,A中可能存在重复元素),请设计算法,以求出两个单链表A和B的差集A-B,结果示例如下:原A链表:1,2,2,3,4,5,5,8,10原B链表:3,5,6,8,12做差集后A链表:1,2,2,4,10请在Difference函数中编写代码,实现上述功能,本题要求:(1)直接在单链表A上做操作,不能额外申请存储空间,并保持元素的递增有序性。(2)时间复杂度为O(m+n)。已知单链表结点类型为:typedefstructLNode{ElemTypedata;//数据域structLNode*next;//指针域}LNode;voidDifference(LNode*A,LNode*B){//请在此处编写代码,实现本题的功能(每行一条语句,本题<18行)}第4页(共6页)四、应用题(共40分)1.(共7分)一颗二叉树的先序序列是abdcefg,中序序列是adbfegc,请画出这棵树,并求出其后序序列。2.(共6分)已知一个无序序列{5,3,1,7,6,9,4,8,2},则:希尔排序法(dk=3)排序第一轮结果是:_______________;以5为基准,快速排序第一轮结果是:_______________;二路归并排序第一轮结果是:_______________。3.(共7分)已知一个无向图如下图所示,用Prim算法生成最小树(假设以②为起点,请在绘制构造过程)所生成的最小生成树的权值和为_______________。第5页(共6页)4.(共9分)已知某图的邻接矩阵如下。1234561008021820000103000004421300050042006000000(1)自顶点1出发进行深度优先遍历所得的遍历序列是:_______________,(2)自顶点2出发进行广度优先遍历所得的遍历序列是:_______________。(注:(1)(2)两小题采用小序号优先原则,无需任何分隔符)(3)顶点1到顶点6的最短路径长度是:_______________。(4)请绘制该图的逆邻接表。5.(共11分)根据以下元素建立一棵排序二叉树,{7,3,5,15,11,1,9,13}(1)请绘制该排序二叉树。(2)该二叉树是否为平衡二叉树?(3)若查找12,将依次哪些元素比较?(4)计算查找成功的平均查找长度和查找不成功的平均查找长度。第6页(共6页)