沈阳工业大学2021年硕士初试专业课真题《数据结构与算法》模拟题(二).pdf
-1-模拟题(二)一、解释下列名词(共20分,每小题4分)1.数据结构2.栈3.二叉树4.査找5.排序二、填空(共30分,每空3分)1.数据的逻辑结构被分为集合结构、线性结构、_和图结构四种。2.种数据结构的元素集合K和它的二元关系R为:K=a,b,c,d,e,f,g,hR=,则该数据结构具有_结构。3.下面程序段的时间复杂度为_。for(inti=0;in;i+)for(intj=0;jn;j+)aij=i*j;4.队列是限制插入操作只能在表的一端,而删除操作在表的另一端进行的线性表,其特点是_。5.在一棵树中,每个结点最多有_个直接前驱结点。6.己知一个无序表为(12,18,98,25,29,83,40,62,20,90,95,32),要查找90时,采用从头至尾顺序査找时,需要_次比较才能查找成功。7.从一棵二叉排序树中查找一个元素时,若元素的值等于根结点的值,则表明查找成功,若元素的值小于根结点的值,则继续向左子树査找,若元素的值大于根结点的值,则继续向_查找。8.二叉树的中序遍历是先中序遍历它的左子树,然后访问_,再中序遍历它的右子树。9.对一组数据(54,38,96,23,15,72,60,45,83)进行直接插入排序时,第一趟排序的结果是_。10.图的遍历方法有_和广度优先遍历。-2-三.解答下列问题(共50分)1.设元素1,2,3,4,5依次进栈,要在输出端得到序列3,4,2,5,1,写出进栈和出栈的过程。(8分)2.设有如下二叉树:(12分)解答下列问题:(1)写出它的前序、中序和后序遍历序列。(2)该二叉树的高度、单分支结点数、叶子结点数各是多少?3.已知一个无向图的邻接表如下图所示:(7分)0123456解答下列问题:(1)画出这个无向图。(2)写出从顶点V0出发的深度优先遍历序列。(3)写出从顶点V0出发的广度优先遍历序列。4.如下图所示的无向带权图(7分)解答下列问题:(1)写出它的邻接矩阵。(2)根据普利姆(Prim)算法从f出发求它的最小生成树,画出最小生成树的生成过程。-3-5.设有一个输入数据的序列是46,25,78,62,12,37,70,29,试画出从空树起,逐个输入各个数据而生成的每个二叉排序树。(9分)6.设有关键字序列72,73,71,23,94,16,05,68,采用简单选择排序算法进行从小到大排序,写出每一趟排序的结果。(7分)四.编写算法,设计语言不限(除C、C+外请标明是哪种语言)(50分,每题10分)1.已知数组An中的元素为整型,设计一个函数将这个数组调整为左右两部分,左边所有元素为奇数,右边所有元素为偶数。数组和元素个数n作为参数传入。2.已知单链表中各结点的元素值为整型且递增有序,设计一个函数删除链表中所有大于mink且小于maxk的元素,并释放被删结点的存储空间。链表头指针和mink、maxk值作为参数传入。3.设计一个函数统计出单链表HL中结点的值等于给定值x的结点数。链表头指针和x作为参数传入。4.写出二叉树前序遍历的递归算法。5.设计一个函数,求用邻接矩阵表示的有向图中序号为num的顶点的度(入度和出度之和),其中邻接矩阵、有向图的顶点数、num的值作为参数传入。