Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 1)几种基本排序方法必须熟练掌握 2)了解几种方法的时间复杂度 3)了解几种排序方法的分类。 交换类: 基本-冒泡(稳定) 改进-快速(不稳定),最好的一种内部排序法 插入类 基本--直接插入(稳定)n很小时很好 改进--2路插入,希尔(不稳定),n不大,基本有序 选择类 基本--简单选择(稳定) 改进--堆排序(不稳定),使用n较大时,要掌握堆排序的方法。 习题: 1长度为12的有序表4,8,12,2,1,7,6,3,5,11,10,9。拆分查找表内元素2的 查找次数?(3) 2哈希表的装填因子定义为什么?(∝=表中记录数表长度) 3向一棵m阶B树插入操作时,当节点的关键字数为(m-1)时,要分裂该节点。删除时 当节点的关键字数为(m/2-1)时,向上取整,需要同左或右兄弟合并。 4在使用索引顺序查找时,除表本身外,尚需要一个(索引表),存放每一块的最大关键字 及该块的起始地址 5在A节点的左孩子B的左子树上插入节点,使平衡因子由1变成2,为了调整为AVL树 需要(LL)型调整 6AVL左子树和右子树深度之差的绝对值小于等于1 7堆排序是(选择类)排序,平均执行时间复杂度为(O(ogn) 8快速排序是(冒泡排序)的改进,属于(交换类),是内部最快的排序方法。 9在哈希表中Keyl<Key2,但f(Keyl)=f(Key2)叫做(冲突)。 0动态查找的定义:查找同时插入表中不存在的元素,查找同时删除表中已存在的元素。 大题: 1画出在递增有序表1。。21中进行折半查找的判定树。 2{86,50,78,59,90,64,55,23,100,40,80,45} 1)构造二叉排序树。 2)按此二叉排序树,如何操作可得一个降序有序序列(逆中序) 3)画出删除50,86的树。 3画AVL树(23,76,47,53,41,12,85,30) 4按以下次序65,23,31,26,7,91,53,15,72,79,68 1)构造哈希函数,使冲突尽可能少。 2)用线性解决冲突,写哈希函数,并写出表,计算ASL。 5(100,85,40,77,80,60,66,98,82,10,20)是不是堆,不是的话调整为小顶堆。 6 (QHCYPAMSRDFX) 1)冒泡排序的一趟结果? 2)初步长为4希尔排序的一趟结果? 3)堆排序初始建堆的结果? 4)快速排序的一趟结果?
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 1） 几种基本排序方法必须熟练掌握。 2） 了解几种方法的时间复杂度。 3） 了解几种排序方法的分类。 交换类： 基本----冒泡（稳定） 改进----快速（不稳定），最好的一种内部排序法 插入类： 基本----直接插入（稳定）n 很小时很好 改进----2 路插入，希尔（不稳定），n 不大，基本有序 选择类： 基本----简单选择（稳定） 改进----堆排序（不稳定），使用 n 较大时，要掌握堆排序的方法。 习题： 1 长度为 12 的有序表 4，8，12，2，1，7，6，3，5，11，10，9。拆分查找表内元素 2 的 查找次数？（3） 2 哈希表的装填因子定义为什么？（ ∝=表中记录数/表长度） 3 向一棵 m 阶 B 树插入操作时，当节点的关键字数为（m-1）时，要分裂该节点。删除时 当节点的关键字数为（|m/2|-1）时，向上取整，需要同左或右兄弟合并。 4 在使用索引顺序查找时，除表本身外，尚需要一个（索引表），存放每一块的最大关键字 及该块的起始地址。 5 在 A 节点的左孩子 B 的左子树上插入节点，使平衡因子由 1 变成 2，为了调整为 AVL 树 需要（LL）型调整。 6 AVL 左子树和右子树深度之差的绝对值小于等于 1 7 堆排序是（选择类）排序，平均执行时间复杂度为（O(㏒ n)）. 8 快速排序是（冒泡排序）的改进，属于（交换类），是内部最快的排序方法。 9 在哈希表中 Key1<>Key2,但 f (Key1)=f (Key2),叫做（冲突）。 10 动态查找的定义：查找同时插入表中不存在的元素，查找同时删除表中已存在的元素。 大题： 1 画出在递增有序表 1。。21 中进行折半查找的判定树。 2 {86，50，78，59，90，64，55，23，100，40，80，45}， 1）构造二叉排序树。 2）按此二叉排序树，如何操作可得一个降序有序序列.(逆中序) 3）画出删除 50，86 的树。 3 画 AVL 树 （23，76，47，53，41，12，85，30） 4 按以下次序 65，23，31，26，7，91，53，15，72，79，68 1）构造哈希函数，使冲突尽可能少。 2）用线性解决冲突，写哈希函数，并写出表，计算 ASL。 5 （100，85，40，77，80，60，66，98，82，10，20）是不是堆，不是的话调整为小顶堆。 6 （Q H C Y P A M S R D F X） 1）冒泡排序的一趟结果？ 2）初步长为 4 希尔排序的一趟结果？ 3）堆排序初始建堆的结果？ 4）快速排序的一趟结果？
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 应用题归类: 树:1已知前序,中序求后序,并画出线索二叉树。 2哈夫曼编码 图:3给一图,写出其邻接矩阵,邻接表的存储结构,并画出强连通分量,指出各点的出 4写深度,广度序列 5会用两种算法画出最小生成树 6用弗洛伊德算法求最短路径 7关键路径 8拓扑排序 查找:9会构造二叉排序树及删除接点后的图形 10二叉平衡树的调整 l1哈希表冲突的解决 12用二叉树二分查找长度为N的有序表的平均比较次数和画出此二叉树 排序:13冒泡排序一趟,给定初步长的希尔一趟,快排一趟,初始堆 05年涉及到的应用题很多,所以上面的题目都应该会熟练的做 06年数据结构的考题大概说明如下: 1.题型:填空,判断,算法填空2题(考法为在一个算法中空出几个空让考生进行填空 应用题3题。整体来说比较简单 2.重点部分大概就如上述资料所述,严的数据结构中比较难的部分,按照05,06的状况 不用花太多的时间去钻研了 3.复习资料强烈推荐李春葆的那本数据结构考硏辅导书,大概是科海出版社出版的,C 语言部分就不要用他的书了,谭浩强的那本C语言习题应该是不错的选择,比较注重基 础,根据05,06的经验数据结构和C考的都比较基础 4.从05开始C语言的编程就已经不考以前那种文件类的大的编程题了,06年两个编程题 非常简单,估计每题需要编写的语句不超过10句,是关于字符串处理的题目 最后,以上说明仅是以前的状况,至于07及以后是否如此,我不敢保证,因此,请各位复 习的考生要有自己的判断,以上资料仅供参考! Andy Xia于2006-4-11 有什么问题可以 EMAIL: suifengl915@163com 以下为04以前的真题,但没有太多的参考价值了,从05开始已经换出题老师了
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 应用题归类： 树： 1 已知前序，中序求后序，并画出线索二叉树。 2 哈夫曼编码 图： 3 给一图，写出其邻接矩阵，邻接表的存储结构，并画出强连通分量，指出各点的出 入度。 4 写深度，广度序列 5 会用两种算法画出最小生成树 6 用弗洛伊德算法求最短路径 7 关键路径 8 拓扑排序 查找：9 会构造二叉排序树及删除接点后的图形 10 二叉平衡树的调整 11 哈希表冲突的解决 12 用二叉树二分查找长度为 N 的有序表的平均比较次数和画出此二叉树 排序：13 冒泡排序一趟，给定初步长的希尔一趟，快排一趟，初始堆 05 年涉及到的应用题很多，所以上面的题目都应该会熟练的做。 PS: 06 年数据结构的考题大概说明如下： 1． 题型：填空，判断，算法填空 2 题（考法为在一个算法中空出几个空让考生进行填空 应用题 3 题。整体来说比较简单 2． 重点部分大概就如上述资料所述，严的数据结构中比较难的部分，按照 05，06 的状况 不用花太多的时间去钻研了 3． 复习资料强烈推荐 李春葆的那本数据结构考研辅导书，大概是科海出版社出版的，C 语言部分就不要用他的书了，谭浩强的那本 C 语言习题应该是不错的选择，比较注重基 础，根据 05，06 的经验数据结构和 C 考的都比较基础。 4． 从 05 开始 C 语言的编程就已经不考以前那种文件类的大的编程题了，06 年两个编程题 非常简单，估计每题需要编写的语句不超过 10 句，是关于字符串处理的题目 最后，以上说明仅是以前的状况，至于 07 及以后是否如此，我不敢保证，因此，请各位复 习的考生要有自己的判断，以上资料仅供参考！ Andy Xia 于 2006-4-11 有什么问题可以 EMAIL:suifeng1915@163.com 以下为 04 以前的真题，但没有太多的参考价值了，从 05 开始已经换出题老师了
Acknowledgement 被軒由05同冰计算机 MS XuWan危费提供现由 bbs. tongji.net宫方网站发布,鹿 费提供给大家使用,禁止任何单位和个人用作其它商业用途! -Andy Xia 04年真题 语言部分 、根据要求写结果(15分,每小题5分) 执行如下程序段 执行下列程序后,输出的结果 include stdi id main [5],b,c,d [0]=b =*a[0]<<2 prI 执行如下程序 Include stdio. h main (int argc, char for (i=l: isar printf(%s%c, argv[i]+i, (i<argc-1)?'': 'In') [0]) 当该程序以cx1.c文件保存,经编译后运行时键入命令 ex1123456798765432 asdfgh 行的结果为 执行如下程序 Fincludestdio h maIn void con (int n, int k) I con(14, 2): printf ((\t") (n>=k) con(n/k, k) con(14, 8): printf("\n") d,n%k):) 显示的结果是 该con函数的功能是
Acknowledgement: 该资料由 同济计算机 05 MS XuWan 免费提供，现由 bbs.tongji.net 官方网站发布，免 费提供给大家使用，禁止任何单位和个人用作其它商业用途！―――Andy Xia 04 年真题