本帖最后由 yaamiao 于 2016-12-30 08:59 编辑
【2017年南京邮电大学_数据结构初试_回忆版】
本来只想发这个的，但是想了想还是整合了自己复习一年来收集的各年份的数据结构初试试卷，以及答案解析！！！（虽然是自己写的orz虽然字写的贼丑orz但是你不会做又找不到答案的时候可以参考一下下....）
绝大部分试卷来源于论坛dalao 陈杨@chenyangnjit
剩余一部分是自己网上收集的！
2017年的回忆版是自己回忆的！
答案解析是自己写的笔记，供大家找不到答案的时候参考用的！绝不代表完全正确和最优解！！（嘛~绝大部分都是正确的啦(`･ω･´)ゞ ）
回忆版，不提供具体题目，可能会有偏差，请勿广泛传播（意思就是说传播的时候低调点orz） 照着前2-3年南邮数据结构出题的尿性，我是抱着10判断10选择5解答4算法的题型准备的，而且重点抓了这两年出题的形势，一些面试递归题啊，一些九几年的北邮、西电数据结构试卷啊，历年南邮的试卷题目啊，王道书上的基本概念和一些习题啊（后期发现编程题没时间做了...）。结果发了卷子居然变成没有判断，20个选择，8个解答题，3个编程题。对手工模拟以及一些书本知识的理论加强了考察，而实际编程的份额居然被弱化了... 实际操作起来不是很困难，解答题有些内容没复习过就懵逼了，算法题有一题把树看成了二叉树，用左右子树的结构体写的一身劲....（我已经是一条废狗了orz）
下面不多说，上题目 一、选择题【对！它上面写的就是选择题！写成单选题好嘛！强迫症受不了啊！】 20个选择（20*2=40）考完就忘，选择是啥？有这种题？十分基础，没什么难题。实在不会就举个特例...
二、解答题【题号不对应，共8个解答（8*10=80）】 1>.for(i=1;i<=n;i++){ for(j=1;j<=i;j++){ for(k=1;k<=j;k++){ K++; } } } 问k++这条语句的执行频度是多少？问该算法的时间复杂度是多少？
2>.给12个数，要求建立小根堆，并给出详细的过程
3>.给出一个有序序列，要求1.画出二叉判定树 2.求ASL成功
4>.B-树的插入，插入一个数，我记得只做了两次分裂就搞定了
B-树的删除，删除的是非叶子结点，直接与最左下交换然后删除它就结束了，没有合并。
5>.散列表的填写，给了一个散列表，表长11，里面给你填了三个数，用除留取余发构造散列函数，给了四个数让你顺序填入散列表中，用二次探测法解决冲突。
6>.“计数排序法”，（就是一种每次从一个数组存储的序列中依次挑出每一个数）问你这种排序方法给n个元素排序要比较多少次 问你这种排序方法和简单选择排序相比，谁更好？（我写的是因为计数排序法要多用一个数组来保存排序数据，所以空间复杂度是O（n），于是果断觉得简单选择好！！）
7>.证明深度优先遍历一个连通图的每条边，总是能得到一棵树（这题我题目没看懂，感觉往生成树的方向写？）
8>.栈的应用：给了一串中序操作数和操作符，让你求值并写出栈的变化过程，最后还问了最小栈容量是多少。（这串操作数我回忆一下，貌似是1422*21/-3^2+ 大概是这个形式，具体的实在记不清了= = 反正加减乘除乘方都有了）
三、算法设计题（一共3题 3*10=30） 1.运用数据结构中所学知识，设计一个算法求树的带权路径长度。
2.运用数据结构中所学知识，设计一个算法求二叉树中指定结点的深度。
3.运用数据结构中所学知识，设计一个算法将一个图的邻接表表示转换成邻接矩阵表示。
这三道算法题都不难，就算没有做过类似题目考中了也不用慌，抓住基本数据结构体，知道怎么调用里面的成员，比多背多做两个题赌他出原题的效果好（但是我看错题了orz）
【总结】 做了十几年的南邮数据结构真题，有很多卷子都是学长学姐们传递出来的，我非常感谢他们，“计利当计天下利”我想将这根接力棒传递下去。 这几年南邮数据结构真题的出题形式不是很固定，千万不要研究过多出题重点，比如说前三年必考的一道递归算法题，今年完全消失；比如说99年到10年前后每年必考的图的四大应用手工模拟，近三年完全没有涉及（今年我记得就给了个选择题） 以现在的出题模式来看，他出什么题的可能都有，没有什么必出题，没有什么绝对重点，今年考10分的简答题，明年可能完全不考orz。如果说真的有什么重点，这几年排序年年考，每年固定一道大题；B-树这几年年年考，固定处大题；这几年二叉树的算法题年年考，每年固定一道大题。我不想给大家压重点，因为他的出题根本没有什么规律，什么都可能出现，什么都可能消失。希望大家端正心态，“全面与重点相结合”，不能因小失大也不能因为思想上的倾向错失了另一种倾向。 祝大家复习顺利(`･ω･´)ゞ ！
| 
发表于 2016-12-26 19:57
收藏
分享
支持
反对
楼主
