搜索
南京邮电大学2012年攻读硕士学位研究生入学考试数据结构试题（回忆版不具真实性）注：此版本为真题回忆版，不是真题。题型是对的，有2-3题不记得了，但是和前几年类似。（数字和题目顺序不一定正确，请谅解勿传播）一、判断题（类似题）1、线性表采用链式存储方式时，既存储了数据本身又存储了数据间的关系。（）2、消除递归必须用栈来实现（）3、算法必须至少有一个输入，否则就不能称为一个算法（）4、对于有n（n1）个结点的二叉搜索树，给定其后续遍历序列和先序遍历序列不能够唯一确定一棵二叉搜索树（）5、在胜方数上输出一个结点后，从根在该节点的路径上所以结点都必须更新。（）二、单选（类似题）1、链表不具有的特点（）A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计`存储空间D所需空间与线性长度成正比2、初始序列经过第一趟排序后，不能确定任何一个元素最终位置的排序算法是____A两路合并排序B拓扑排序C无序的D按关键字有序3、下面_____算法可用于求无向图的所有连通分量A广度优先遍历B拓扑排序C求最短路径D求关键路径4、二叉树中第5层上的结点个数最多为________，假定根节点层次为1A32B8C16D155、设高度为h的二叉树上、只有度为0和度为2的结点，则这一类二叉树中所包含的结点数至少为（）Ah-1BhC2h-1D2h6、现实生活中具有谱系结构的数据，在计算机中处理时一般采用_____结构表示。A线性B树C集合D图7、一个索引文件，如果经常需要插入和删除元素，宜采用______做索引。A二叉排序树B二叉平衡树CB–树DB+树8、以下排序算法中，一趟排序后所有元素的最终位置暂不能确定的算法是（）A直接插入排序B快速排序C冒泡排序D简单选择排序9、倒排文件的主要优点是（）A便于进行插入删除运算B便于进行文件的合并C能大大提高次关键字的查找速度D能大大节省存储空间三、填空（类似题）1、设a=6,b=4,c=2,d=3,e=2,则后缀表达式abc-/de*+的值为__________2、简单选择算法的最好和最坏情况时间复杂度分别为______和_________3、若某二叉树的先序和中序遍历的结点次序相同，则该二叉树形一定是_________4、在有序表（11，23，34，45，56，65，75，87，97）中以对半搜索算法查找元素34时，所需的关键字之间的比较次数为（）次5、设二叉树根节点的层次为1。在所有含135个结点的二叉树中，最小高度是______6、散列文件一般采用______解决冲突。7、用BFS遍历一个有向无环图，并在DFS算法退栈返回时打印当前顶点，则输出的顶点序列式________。8、有n个顶点的无向联通图最少有_______条边9、现在值分别为A，B，C的3个元素，可组成_____个不同值的二叉树。10.对线性表进行存储时，若无足够连续存储空间，宜使用______存储空间四、解答00-11年试卷上全部出现过，只是改了数字，具体不举例了。五、算法设计题1、单链表相关编程（关于排序）2、平衡二叉树相关编程20131.设计将一维数组中所有奇数移到所有偶数之前的算法。2.设二叉树以二叉链表作为存储结构，且树种各结点的关键字均不同，编写一个判别给定二叉树是否为二叉排序树的算法。3.设计一个算法，判断一个无向图G是否为一棵树，若无向图是树，则算法返回true，否则返回flash.4.设一棵满二叉树（所有结点值均不相同），已知其先序为pre，设计一个算法，求其后序序列post.5.编程实现选择问题。即在数组L[0,1,2，，，，，，n-1]中找出第K小元素，使算法时间复杂度尽可能小，要求对算法的平均时间复杂度作简要分析。