2014年南邮考研数据结构初试真题

-2014年南邮考研数据结构初试真题一.判断题（15„*2=30）：太多了没什么好回忆的，请大家复习千万抓基础，啃王道那本书去。二.选择题（15‟*2=30）：同选择。也是要千万抓基础，啃王道那本书。但是选择题有一些是王道书上的原题，大家别抱着侥幸心理，把王道书上每道题目弄懂就好。三.简单题（10„*5=50）：1.简述数据逻辑结构、存储结构、数据运算三者的关系。（看，是绪论里面的题目吧？你注意这是简答题，所以你必须对这三者之间的关系理解特别深透，能用自己的话总结出来，在这你才能写的出东西！）2.试着从算法分析的角度分析简单选择、折半插入排序、冒泡、希尔、快速、堆排序、几个排序方法之间的不同。（这个题目其实王道书排序那章最后有总结，但是如果你靠死记硬背肯定是记不住的，也没有价值意义。重要的，首先，从分类上：哪些是插入排序，哪些是选择排序，哪些是交换排序？接着就是T(n)和S(n)上的差距。最好多少，最坏多少？你都要能说的头头是道。我还是那句话，这是简答题，你闭着眼睛想想，如果理解不到位，你什么本事写出那么多东西）？3.一道建堆的题目，并画出调整后的4.一道线索二叉树的题目5.怎样用队列实现栈的功能，并且如何判断栈空栈满。四、算法题(10'*4=40)1.两个链表LA、LB，将其合并成递增有序的单链表。（王道书上原题，属于链表操作里面的基本题）2.BST树，给一个结点，求其层次。（王道书上原题，考察层序遍历算法，层序遍历要用到栈，所以栈的知识你又会不会）？3.现有一个邻接表表示的有向图，写一个算法将它逆转。4.求一个二叉树只有一个孩子结点的结点个数（感谢三楼那哥们儿，这题当时没动脑子，所以印象不深。用递归就好了，这题王道书上应该也有）======能回忆起来的就这么多了，还有一道算法题我想起来再回来补充。唉，这帖子越写越伤感。还是回到数学上来，从初中到高中到大学我一直数学不是很好，但是今年这数二的卷子考的真心是我最无语的一次。我可以很自信地说：“199-2013年的数二真题，我每一道都弄懂了”，但是今年考数学的时候不知道为什么突然一点感觉都没有了。而且，大家在复习的时候一定要注意调整好心理状态。我总结我今年数学考砸了很大部分原因也有心理因素。至今考试时的感觉历历在目。很多题目我都知道有哪些题型，要怎么做，可就是套不进去。而且感觉我考试心理素质特别差。平时做历年真题，选择+填空加起来50min我就能搞定了，今年光选择就花了我将近50min，从那之后我就慌神了，以至于后面的都没答好。下了考场之后和我们班一个数学好的同学交流了一下才知道，原来他今年光选择题也花了将近50多分钟。我才知道我当时的慌乱是多么地可笑。考试这东西最怕慌，一慌，什么节奏都乱了。所以大家千万要连就自己的心理素质。至于专业课的复习，大家还是要打好基础。从5号考完，到现在21号01：13分我给大家写这些东西之前，我真的是一点一点都没有再碰考研的任何东西。但是你看，数据结构的东西，甚至知识，我还是可以记得比较清楚，就是因为在我脑子里成体了。大家在复习数据结构的时候千万要把知识串起来记，考试是很灵活的。就像今年考的算法题第2题。求层次-层序遍历的算法你会吗？-层序遍历要用到栈-栈的基本操作的代码你会吗？-上面这些东西都会-转换成代码你会写吗？诸如此类的知识关联在考试中举不胜举。计算机这种科目，最怕的就是死记硬背。我记得13年暑假的时候我们两个班全体学生去苏州昆山那边实训了两个星期，学RedHat的Linux服务器配置，那么多linux命令，班上很多同学（女生居多）上课的时候无比认真，拿纸拿笔认认真真地把老师的每一个命令都记下来，到了自己电脑上挨个敲，把自己活生生变成打字员。最后呢？每个人机器的配置不一样，环境不一样，换个环境，你不知道这命令是干嘛的，还是不会写。（这也解释了为什么计算机专业很多“学霸”，“考霸”可能是女生，但一旦上手写代码做东西的时候却往往是男生弄得比较好）。说实话实训的那两周是我觉得上大学期间最快活的时候，因为理解了之后，上手做起来特别快。好几次实验我都是第一个交的（因为好几次我交完之后看FTP服务器上基本上其他人文件夹里是空的）。所以，大家在复习数据结构的时候，该记的东西你要记，记完之后一定要自己理解了才行！(比如说线性表、链表那章会有这种选择题：给你几个数据操作，问你选择哪种数据结构（线性表or链表，仅有头指针or仅有尾指针，单链or双向链，循环or不循环，这些东西排列组合一些可以形成好几种结构，你能说出每种的区别吗？）)简答题（50分）：1.用算法分析对直接插入，冒泡，选择，希尔，快排，归并，堆排进行对比分析2.有三道小题，主要关于逻辑结构，存储结构，数据操作，数据结构间基本概念的关系（基础知识不扎实就呵呵了）3.用两个栈实现队列的入队，出队，判断队空的操作4.给出一组数据，构造大顶堆（画图）5.给出一组数据，构造二叉树，同时利用中序遍历将其转换成二叉线索树（画图）算法题（40分）：1.讲两个递增的表归并为一个递减的表（利用原表中的结点）2.算出一棵二叉树中单孩子结点的个数3.查找二叉排序树中某个结点所在层数4.给出一个邻接表，转换出其反向邻接表，算法复杂度O（n+e）