《2018年辽宁沈阳工业大学数据结构考研真题.doc》由会员分享，可在线阅读，更多相关《2018年辽宁沈阳工业大学数据结构考研真题.doc（3页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2018年辽宁沈阳工业大学数据结构考研真题一、解释下列名词（共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.已知一个无序表为
2、（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.图的遍历方法有（）和广度优先遍历。三.解答下列问题（共50分）1.设元素1，2，3，4，
3、5依次进栈，要在输出端得到序列3，4，2，5，1，写出进栈和出栈的过程。（8分）2.设有如下二叉树（12分）解答下列问题（1）写出它的前序、中序和后序遍历序列。（2）该二叉树的高度、单分支结点数、叶子结点数各是多少？ 3.已知一个无向图的邻接表如下图所示（7分）解答下列问题（1）画出这个无向图。（2）写出从顶点V。出发的深度优先遍历序列。（3）写出从顶点V。出发的广度优先遍历序列。4.如下图所示的无向带权图（7分）解答下列问题（1）写出它的邻接矩阵。（2）根据普利姆（Prim）算法从f出发求它的最小生成树，画出最小生成树的生成过程。 5设有一个输入数据的序列是（46，25，78，62，12，3
4、7，70，29），试画出从空树起，逐个输入各个数据而生成的每个二叉排序树。（9分）6.设有关键字序列72，73，71，23，94，16，05，68，采用简单选择排序算法进行从小到大排序，写出每一趟排序的结果。（7分）四编写程序，程序设计语言不限（除C、C+外请标明是哪种语言）（50分，每题10分）1.已知数组A【m】中的元素为整型，设计一个函数将这个数组调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数。数组和元素个数n作为参数传入。2.已知单链表中各结点的元素值为整型且递增有序，设计一个函数删除链表中所有大于mink且小于maxk的元素，并释放被删结点的存储空间。链表头指针和mink、maxk值作为参数传入。3.设计一个函数统计出单链表HL中结点的值等于给定值x的结点数。链表头指针和x作为参数传入。4.写出二叉树前序遍历的递归算法。5.设计一个函数，求用邻接矩阵表示的有向图中序号为mum的顶点的度（入度和出度之和），其中邻接矩阵、有向图的顶点数、num的值作为参数传入。