精华内容
下载资源
问答
  • 哈尔滨工业大学数据结构与算法2012年的期末考试试题以及答案,供备考的同学们使用。
  • 哈尔滨工业大学数据结构与算法试卷 1.深(高)度为 6(根的层次为 1)的完全二叉树至少有( )结点。 A. 64 B.32 C.31 D.63 2.若具有 n 个结点、k 条边的非连通无向图是森林(n>k),则该森林中必有( )棵树。 ...
  • 哈工大数据结构13年期末试卷
  • 哈工大 计算机专业 数据结构 期末试题 2003-2005
  • 哈工大2021年数据结构期末试题学生整理回忆版

    2021.11.27上午10:00~12:00,笔者经历了数据结构考试,现将回忆版的试题放在下面,供学弟学妹们参考。

    在这里感谢整理好之前往年题目的学长、学姐们,向您们致以崇高的敬意!

    如果本文章对您有用,也欢迎您对本文章点赞~

    因笔者没有刷过题(在考前一周才发现身边的同学都在刷王道考研题,且还有其他一些事情需要处理),也没有任何算法竞赛经验与经历,外加出来考场听同学们谈论问题时就已经发现错了一道算法题了,故本人答案没有任何参考价值,不附之。下面是今年的题目:

    注:由于本人喜欢把题目印下来做,所以也适当进行了排版,增大了大题之间的空隙,方便打印使用!

    注:有无前端大佬可以带带我呀,球球辽~联系方式见Github个人介绍

     

     

     

     

     

     

     附上学长/学姐整理好的往年题目链接,感谢您们做出的贡献!

    哈工大2020数据结构期末_The best wjh的博客-CSDN博客_哈工大数据结构考完人没了,听说老师觉得以前总是有学生一个小时就交卷子,他们觉得很没面子所以今年就加大难度了,总算是没人提前交卷子了,呜呜呜,好吧,昨天刚考完,趁还记得题目给后来的兄弟姐妹提个醒一.选择题 五个每个两分1.循环链表逆置的时间复杂度2.按照字典序列深度搜索的二叉树问题3.拓扑排序,若邻接矩阵只有上三角,那么拓扑序列是不是唯一5.255个序列块用分块查找后顺序查找的最短比较次数二.填空题 十个每个一分1.栈的运算,进栈出栈2.一个n个元素的小根堆,要求其中最大最小元素需要比较次数3.11个初始https://blog.csdn.net/qq_45979209/article/details/110791617哈工大2019秋数据结构期末试题_dream or nightmare的博客-CSDN博客_哈工大数据结构期末虽然隔了一年,但是数据结构题目题型我还是记得的。期末试题总分601.选择题十个还是十五个来着,一个一分考察:算法复杂度比如经典的Dijkstra算法、Floyd算法,十大排序算法。选择题考察的很细,涉及到二叉树的算法、图的算法的具体某一个步骤。强烈建议搞懂每个算法的实现原理和具体的实现过程。!!!我清楚的记得,有一道选择题,给了四个排序算法,问哪个算法是稳定的?2.填空题填空题同选择题一样,也考的特别的细,细到问你3.大题除了画图填表的图算法之外!其他的算法基本都手写好像是四道题还https://blog.csdn.net/weixin_45406155/article/details/109347546哈工大2017秋数据结构期末试题_dream or nightmare的博客-CSDN博客哈工大2012秋数据结构期末试题(含答案)哈工大2019秋数据结构期末试题哈工大2015秋数据结构期末试题(含答案)哈工大2013秋数据结构期末试题(含答案)(由于版权限制,无法将2015、2016年数据结构算法的答案发到网上,需要的私聊我。)...https://blog.csdn.net/weixin_45406155/article/details/110529899哈工大2013秋数据结构期末试题(含答案)_dream or nightmare的博客-CSDN博客哈工大2013秋数据结构期末试题原题答案其他年份的题原题答案其他年份的题哈工大2012秋数据结构期末试题(含答案)哈工大2019秋数据结构期末试题找到了其他年份的接着更新需要pdf的可以联系我...https://blog.csdn.net/weixin_45406155/article/details/109788356哈工大2012秋数据结构期末试题(含答案)_dream or nightmare的博客-CSDN博客_哈工大数据结构期末哈工大2012秋数据结构期末试题原题答案需要pdf文件的可以私聊我原题答案需要pdf文件的可以私聊我https://blog.csdn.net/weixin_45406155/article/details/109788019 

    展开全文
  • 哈工大03年数据结构期末试卷答案,望对大家有益
  • 专业课: (1)数据结构: 书:王道+严蔚敏《数据结构》 题:王道选择+哈工大考研真题 数据结构一开始上手感觉难,书过了三四遍之后就不觉得了,王道的知识点只能当概览,对于细节的理解还是要看书。王道的选择我刷了...
    经常会有小伙伴咨询我跨考计算机的问题,问我计算机难不难、怎么复习?因为我本身不是跨考的,没办法从零基础感知跨考的难度,今天就给大家带来一位小伙伴的原创投稿,用她自身的经历来给大家讲讲跨考计算机的过程。不过这位同学是比较优秀的,只用了四个月复习就上岸了,对于大部分的同学而言,计算机考研没有十个月的复习是不现实的,几个月上岸的消息年年有,但奇迹并不属于每一个人,但唯有脚踏实地,才适合每一个人,
    本科读的是211的一个文科,大学没学过数学,也没接触过计算机。8月末才开始正式准备考计算机是因为学校磨蹭到8月才出保研名单,而我,差一名,不在上面(要怪就怪学校有论文加保研分的这个破政策)。 初试分数345,复试排20名左右,跨考哈工大计科学硕上岸。 我的分数排名都不是很高,加上是文科跨考,所以这个经验贴可能参考价值没有很高,大佬们请自觉绕路。

    英语:

    四级604,六级548,曾经获得大学生英语竞赛二等奖,所以对英语花费时间很少。 我自己觉得自己英语水平还挺好的,但是一开始做往年真题还是错一大片。也是很头疼了,每天都在想在自己擅长的学科花这么多时间数学可怎么办啊。 最后是查了别人的经验贴,反观自己已经做过的真题,发现自己错的题目都有类似之处。 然后我把自己做错的题目归类,都是掉入了出题人设计的什么样的陷阱。找到出题人的规律以后,拿到一道题就知道出题人会用什么套路,哪里容易设置障碍,然后返回原文一一去找。经过一下午的研究之后,第二天做了一套阅读,就错了两三题,感觉这种程度够了,之后对英语的复习就做到保持手感。考试前一天抽时间又做了19年英语的题,阅读就错了1个,感觉这是唯一让我放心的科目了。 没想到啊没想到,最后小作文格式我没背,太大意了,最后我对了答案,觉得分都是扣在作文上了..... 在此奉劝各位考生,所有作文的格式都要会背会默!!!! 在此奉劝各位考生,所有作文的格式都要会背会默!!!! 在此奉劝各位考生,所有作文的格式都要会背会默!!!!

    政治:

    一开始对着精讲精练做1000题,一天花一个半小时也不见得做多少题(我也抽不出来更多时间)。 最后刚做完马原,觉得时间已经来不及了,这时候肖八已经出来了,于是我直接开始做肖八,用肖八带动对其他内容的复习。最后一周猛嗑肖四,虽然今年压的题变少了,但是对我这种前期政治学的很少又没有政治觉悟的人来说,只能靠背过的答案的说话套路再加点材料来作答了。 政治我强烈建议对专题内容进行分类汇总,汇总到最后一天,每天看汇总内容,直到最后一天。为什么这么说呢,因为我考试前一天刚复习刚整理的专题知识点第二天就考了。 对于政治,只要你不是太废,建议不要过早花太多功夫,只要别的科目都复习好,最后一段时间抓紧搞一搞分数不会难看(为什么不用我说了吧,懂的都懂)。

    数学:

    数学真的是最让人爱和最让人恨得一门学科了。我高中是学理科的,大学从来没有学过一点数学,相当于八月末开始学大学数学,入完门就要刷题,刷完题就要考试,真是一波极限操作。 入门我是配合着汤家凤的基础课+汤家凤的全书+1800题。大概在九月末结束了一遍,1800基础篇做完了。 强化看的也是汤家凤的强化课+1800题的强化部分。分专题做题,分专题总结。 然后开始我的刷题道路,首先是刷真题,我全都按照考试时间做的,当然一开始惨不忍睹,只能六七十分。然后我开始看我错的题目的类型是什么,针对专题找出以前的笔记和习题练习,慢慢地,也能做到一百一十到一百二十之间(当然我自己给自己算了步骤分)。 最后一段时间就是复习笔记+做李林的6套卷+4套卷。 (没想到啊没想到,最后的题好难,但是我还是在考场上尽量稳住心态做到最后一秒; 没想到啊没想到,最后没给我算步骤分,再加上小题错太多,最后居然和政治和英语一个分数) 对于数学做题顺序,我有一点技巧,不知道大家是不是都是这么做的。就是做完填空题会做的能梦的之后,然后做高数前两题简单题,然后翻过来做线代和概率,然后再回头做高数的难题。这样能保证自己会做的尽量都拿到分数。 线代和概率一定不能马虎,如果这部分分数没拿到,那我觉得数学一定给垮了。

    专业课:

    (1)数据结构: 书:王道+严蔚敏《数据结构》 题:王道选择+哈工大考研真题 数据结构一开始上手感觉难,书过了三四遍之后就不觉得了,王道的知识点只能当概览,对于细节的理解还是要看书。王道的选择我刷了也有3.4遍,真题刷了2.3遍,最后这部分感觉几乎都会了,没想到这部分最后考的挺简单。 代码题对于跨专业的来说真是一个大坎,我差点栽倒在上面。这部分建议就是反复写,反复练,把王道上所有的代码题都整会了就没问题了。 (2)计算机网络 书:王道+大黑书+计网mooc 题:王道+408选择题 这部分我真是吃了大亏,一直绕着王道转,最后好多大题没把握是对的,估计分数也是扣在这上面了。 我强烈建议今年考研的同学看大黑书,只把王道的知识点当做概述。虽然外国人写书啰嗦,但是知识点全,建议把废话能过就过,把关键知识点搞透,重视大题。 (3)CSAPP--秃顶原因找到了 这部分资料挺少的,所以要好好利用现有资源。 第一遍啥也不懂; 第二遍找了个pro给我讲了一遍,懂了很多; 第二遍的时候做了一遍课后题, 后来又单独做了遍题。 第三遍复习、加深印象。 踩的坑:曾经做了北大的期末试卷,南大的期末试卷,浪费了不少时间,因为太难了,死磕都嗑不出来结果。 第一年考出的题还是基础题,后面代码题考的就是书上源代码,虽然我不完全明白,但是把书啃了三遍的我还是熟练地把代码写了上去。

    考研心得:

    没有人能拯救你,只有你才能拯救你自己。 无论有再大的困难,想想录取时的激动,也就过去了。 看完第一件事,记得扫码关注我的备用号【启舰】,以后较为敏感的信息和实事热评都会发在备用号上了,等你来哦。 b4b2959806ef8fbf1bdafe604b210436.png

    ——End——

    最近因为公众号改版,时间线被打乱了,启舰发布的文章你们有可能错过啦。

    所以如果你喜欢启舰,觉得启舰的文章对你们有帮助,记得把我标星,多点在看,微信会感受到你的爱,就能更及时地为你推送我的文章(以及摸鱼活动)啦0080d4f1e7c174e722976fa0dae9da2b.png

    往期推荐:

    为什么有人考研付出了巨大努力,还是成为炮灰?

    程序员怎样才能实现财务自由?

    今年大三,年入六万,经验分享

    记得帮我点赞/在看哦

    展开全文
  • 哈工大2019秋数据结构期末试题

    千次阅读 多人点赞 2020-10-29 21:39:44
    虽然隔了一年,但是数据结构题目题型我还是记得的。 期末试题总分60 1.选择题 十个还是十五个来着,一个一分 考察:算法复杂度 比如经典的Dijkstra算法、Floyd算法,十大排序算法。 选择题考察的很细,涉及到二叉树的...

    虽然隔了一年,但是数据结构题目题型我还是记得的。

    期末试题总分60
    选择10分+填空10分+简答25分+算法设计25分

    1.选择题

    十个,一个一分
    考察

    选择题考察的很细,涉及到二叉树的算法、图的算法的具体某一个步骤。 比如经典的Dijkstra算法、Floyd算法,十大排序算法。强烈建议搞懂每个算法的实现原理和具体的实现过程。!!!

    我清楚的记得,有一道选择题,给了四个排序算法,问哪个算法是稳定的?

    在这里插入图片描述

    2.填空题

    10道,一道一分。
    填空题同选择题一样,也考的特别的细。
    但是都不难,考的很基础。

    3.简答题(25分)

    简答题总共三道题目,主要考察查找(平衡树、散列)、堆、线性表等知识。

    第一题内容是给出一个二叉搜索树的后序遍历,问能不能确定这个二叉树。(很简单,举例说明即可)

    第二题内容分为两个小问,第一个小问是根据快递单号确定快递存放的货柜,方便查找,体现了什么思想,第二问是已知货柜号和快递单号,在取快递时,可以采用哪些策略来快速查找到快递。

    第三题内容是银行系统中,每个客户对应一个权限,要求银行每一次可以选取一个权重最高或者权重最低的客户来服务,问采用什么数据结构?怎么实现它?(显而易见是堆 了,但是如果你只写一个字堆你觉得老师会给你几分?是不是还得写个伪代码啥的说明一下算法的实现?)

    4.算法设计题(25分)

    这部分题要求自行设计数据结构,给出c/c++/java语言代码,分析复杂度。个人觉得本部分题最拉开差距。

    第一题是给出中序线索二叉树的一个节点p,设计一个算法,求它的前驱节点p$。(赶快去看看线索二叉树!)

    第二题是给出两个升学排列的数组A,B,长度分别为m,n,设计一个算法,输入一个数k,返回数组A,B中第k小的元素。(就双指针走呗,都已经是升学数组了)

    第三题是给出一个有向图G,设计一个算法,判断任意两个顶点是否连通。(注意是有向图,我tm当时做的时候搞成了无向图。这道题就手写广度优先遍历呗,但是注意要从两个顶点都得开始遍历,笔者的痛。)[15分]

    建议大家把二叉树的遍历、图的遍历、搜索算法、排序算法都熟悉熟悉,没准又让你手写课本学习的算法呢。

    所以,总的来说就是熟悉PPT,熟悉学过的算法和数据结构。

    还有就是实验分基本你写了验收了就是满分。

    数据结构90分不难,只要你实验搞懂了,PPT搞懂了,刷刷纸张记忆的题,绝对没问题的。(95分也不是问题)

    感谢一位同学的分享,之前更新的数据结构题目有点偏差,这次保证是最全最正确的哈工大2019秋数据结构期末试题。也希望他早日实现自己的梦想!

    5.其他年份的期末考试原题

    哈工大2012秋数据结构期末试题(含答案)
    哈工大2013秋数据结构期末试题(含答案)
    哈工大2015秋数据结构期末试题(含答案)
    哈工大2017秋数据结构期末试题(含答案)
    (哈工大2016年数据结构期末题及答案由于版权原因不能发到博客上,需要的私聊我)

    找到了其他年份的题接着更新
    需要pdf的私聊我

    展开全文
  • 哈工大2018年秋数据结构期末复习

    千次阅读 2020-06-02 21:39:29
    就是一篇很普通的数据结构的复习时的笔记而已 本文原载于我的博客,地址:https://blog.guoziyang.top/archives/19/

    本文原载于我的博客,地址:https://blog.guoziyang.top/archives/19/

    第二章 线性表

    1. 线性表是有限的,也是有序的。

    2. 线性表的实现:三种存储结构。

      • 连续的存储空间(数组),静态存储。
      • 非连续的存储空间,指针(链表),动态存储。
      • 游标(连续存储空间+动态管理思想),静态链表。
    3. 顺序表,是指用一组地址连续的存储单元依次存储线性表的数据元素。特点:

      • 元素上的逻辑关系用物理上的相邻关系表示。
      • 是一种随机(任意)存储结构,可以随机存取表中的任意元素。
      • 高级语言通常使用数组。
    1. 线性表的指针实现:单链表,每个结点均含有两个域:存放元素的信息域和存放后继结点的指针域,这样就形成了一条(线性)单向链表。

      • 逻辑次序和物理次序不一定相同
      • 元素的逻辑关系用指针表示
      • 需要额外的空间存储元素之间的关系
      • 非随机存储结构
    2. 线性表的游标实现:静态链表,将线性表的元素存放在数组的单元中(不一定按照逻辑顺序),每个单元不仅存放元素本身,还存放其后继元素所在的数组单元下表(游标)。

    3. 双向链表:对每个单向链表的结点增加一个指针指向前驱结点。可实现双向查找。

    4. 栈,后进先出,是限定只在表尾进行插入和删除操作的线性表。

    5. 使用游标形式使得多个栈共享空间:上层元素记录着下层元素的索引位置,前n个元素无数据,仅用于记录n个栈的栈顶。

    6. 中缀表达式转换为后缀表达式

      • 遇到操作数直接输出
      • 遇到操作符,如果比栈顶元素优先级高,则直接入栈;否则弹栈输出至栈顶操作符优先级小于操作符,接着在入栈
      • 遇到左括号,直接入栈,遇到右括号则弹栈输出至左括号为止,右括号不入栈,左括号弹栈不输出
    7. 由后缀表达式计算表达式的值

    • 遇到数字直接入栈
    • 遇到操作符,则弹栈两次,用取出的数进行运算,结果入栈
    • 最后栈内的元素即为结果
    1. 递归,步骤分为递推和回归。递归必须有递归结束条件,过程是首先一级一级递推,满足递归结束条件时结束递推,再一级一级回归。

    2. 队列,先进先出,将线性表的插入和删除操作分别限定在表的两端进行,即只可以插入到表尾,删除表头。C语言的队列数组使用指针指向队首和队尾,可能造成假溢出的情况。可使用循环队列解决。

    3. 串是线性表的一种特殊形式,表中每个元素的类型为字符,C语言使用字符数组或字符指针来表示串。

    4. 模式匹配算法:判断某个子串是否在主串中。简单的匹配算法,一旦某个字符匹配失败,将从头(子串)开始。

    5. KMP算法:利用已经得到的部分匹配的结果,将子串向右滑动一段距离(next数组)之后,继续比较。next数组的第一个元素为-1,第二个元素为0,从第三个元素开始计算,数值是该字符前字符 串的最大前缀后缀(都是正序)的值。滑动子串指针到next+1处继续比较即可。

    6. 二维数组: a i j a_{ij} aij前面的元素个数: i × n ( 每 行 元 素 个 数 ) + j i\times n(每行元素个数)+j i×n()+j

    7. 对称矩阵的压缩:只存储下三角部分的元素。

    8. 稀疏矩阵的压缩:只存储非零元素,三元组(行号、列号、元素值)。

    9. 广义表,元素可以是不同类型,元素可以是空,可以是其它类型的直接元素,也可以是广义表(嵌套)。

    • 长度:直接元素的个数
    • 深度:括号的最大嵌套层数
    • 表头:第一个元素
    • 表尾:除表头外其余元素组成的广义表
    1. 广义表的存储:链式结构存储。

    第三章 树与二叉树

    1. 树形结构是一种非线性结构,反映结点间的层次关系(一对多)。除了根结点外,每个结点有且只有一个直接前驱,但可有0或更多直接后继。

    2. 树的基本术语:

      • 结点的度:结点具有的子树个数(出度)
      • 树的度:树中各结点度的最大值
      • 叶子结点:度为0的结点
      • 分支结点:度不为0的结点
      • 路径长度:路径上边的个数
    3. 二叉树,除非为空,由一个根结点和两棵互不相交的、分别称为左子树和右子树的二叉树(递归)构成。二叉树是有序树。

    4. 满二叉树,高度为k且由 2 k − 1 2^k-1 2k1个结点的二叉树,即每个分支结点都有两棵子树且叶子结点都在最后一层。

    5. 完全二叉树,所有的叶子都在k或k-1层,k-1层的所有叶都在非终结结点的右边,除了k-1层的最右非终结结点可能有一个分支(只可能是左分支)外,其余的非终结结点都有两个分支。

      • 深度为k的完全二叉树的前k-1层一定是满二叉树。
      • 如果有度为1的结点,那一定是k-1层上的最右非终结结点,且该结点只有左孩子。
    6. 二叉树的性质:

      • 二叉树的第i层最多有 2 i − 1 2^{i-1} 2i1个结点。
      • 高度为k的二叉树最多有 2 k − 1 2^k-1 2k1个结点(一定是满二叉树),最少有k个结点(不一定是斜树)。
      • 在一个非空二叉树中,如果叶子结点数为 n 0 n_0 n0,度为2的结点数为 n 2 n_2 n2,那么 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
      • 具有n个结点的完全二叉树高度为 [ l o g 2 ( n + 1 ) ] [log_2(n+1)] [log2(n+1)]
    7. 完全二叉树的顺序存储结构:按照自顶向下、同一层从左至右连续编号,并按照编号存储在对应下标的数组中。空出第0个元素,编号从1开始。

      • 若i>1,则i的父结点为 [ i / 2 ] [i/2] [i/2]
      • 2 × i ≤ n 2\times i\le n 2×in,则i有左儿子且为2*i。若 2 × i + 1 ≤ n 2\times i+1\le n 2×i+1n,则i有右儿子且为2*i+1。
      • 若i为偶数,则i有右兄弟i+1。
    8. 二叉树的遍历:前序中序后序递归算法(前序例子)。

      • 若当前结点不为空
        • 访问当前结点
        • 递归遍历左子树
        • 递归遍历右子树
    9. 二叉树的存储:动态二叉链表,三个域:数据,左指针,右指针。

      • n个结点的二叉链表有n+1个空指针,有n-1个指向孩子结点的指针,共有2n个指针。
    10. 先序遍历的非递归算法:

      1. 初始化栈
      2. 循环直到root为空且栈为空
         1. 当root不空时循环
            1. 输出root
            2. 将root结点保存在栈中
            3. 将root指向其左子树
         2. 如果栈不空
            1. 将栈顶弹出,赋给root
            2. 将root指向其右子树
      
    11. 中序遍历的非递归算法:

      1. 初始化栈
      2. 循环直到root为空且栈为空
      	1. 当root不空时循环
        	1. 将root结点保存在栈中
          2. 将root指向其左子树
        2. 如果栈不空
        	1. 将栈顶弹出,赋给root
          2. 输出root
          3. 将root指向其右子树
      
    12. 后序遍历的非递归算法(1):

      1. 栈初始化
      2. 循环直到root为空且栈为空
         1. 当root非空时循环
            1. 将root连同标志flag=1入栈
            2. 将root指向左子树
         2. 当栈不空且栈顶元素标志为2时循环
            1. 输出栈顶元素并弹栈
         3. 若栈不空
            1. 将栈顶元素标志为设为2
            2. 将root指向栈顶元素右结点
      
    13. 层序遍历二叉树:

      1. 队列初始化
      2. 如果二叉树非空,根结点入队
      3. 若队列不空,循环
         1. 当前结点为队首结点,且出队
         2. 输出当前结点
         3. 如果当前结点有左孩子,则左结点入队
         4. 如果当前结点有右孩子,则右结点入队
      
    14. 二叉树的其它链式存储结构:动态三叉链表,在二叉链表的基础上增加一个指向双亲的指针域。

      静态二叉链表和静态三叉链表,游标的形式

    15. 已知中序和先序序列构造二叉树(递归)

      前序遍历先访问根结点,因此前序遍历序列的第一个字母肯定就是根结点,即A是根结点;然后,由于中序遍历先访问左子树,再访问根结点,最后访问右子树,所以我们找到中序遍历中A的位置,然后A左边的字母就是左子树了,也就是CBD是根结点的左子树;同样的,得到EF为根结点的右子树。

      将前序遍历序列分成BCD和EF,分别对左子树和右子树应用同样的方法,递归下去,二叉树就成功构建好了

    16. 二叉树的线索链表存储:线索二叉树

      若结点有左孩子,则指向其左孩子结点,否则指向其(先序、中序、后序、层序)前驱。

      若结点有右孩子,则指向其右孩子结点,否则指向其(先序、中序、后序、层序)后继。

      每结点增加两个标志位,以区分两个域是指向前驱后继还是左右孩子。

    17. 在中序线索二叉树中求一个结点的中序后继:

      • 若右结点是后继,则直接可得
      • 若不是,则中序后继是右子树的最左结点
    18. 求中序线索二叉树中结点的先序顺序的后继结点:

      • 左子树不为空则为左儿子
      • 左子树空右子树不空则为右儿子
      • 左右子树均空,右线索序列的第一个有右孩子的右儿子即为后继,否则头结点是后继
    19. 二叉树的线索化算法:

      按照某种次序遍历二叉树,在遍历过程中用线索取代空指针即可,设置一个指针始终指向刚刚访问的结点即可。

    20. 相似二叉树:具有相同结构的二叉树

      等价二叉树:相似且对应结点包含相同信息的二叉树

    21. 一种特殊形式的完全二叉树——堆

      最大堆:任意一个非终结结点的元素都不小于其左儿子结点和右儿子结点(如果有),最小堆同理

      可使用线性存储(层次编号)

      堆可用于实现优先级队列

    22. 大根堆的插入操作:

      将元素插在大根堆数组的尾部,在依次向上调整,逐个调换父结点和子结点

    23. 大根堆的删除操作:大根堆仅能删除最大结点(数组头):

      用最后一个元素(数组尾)元素代替根元素(数组头),再从头向下依次调整

    24. 归并:假设有k个已排序的序列,将其合并成一个单独的排序序列,称为归并,归并可使用选择树(胜者树)。选择树是一棵完全二叉树,其中每个结点代表两个儿子的较小者,这样,根结点就表示树的最小元素结点

    25. 修改选择树中一个结点的值,很容易修改这棵树,只需要沿着从该结点到根结点的路径修改即可。

    26. 败者树是胜者树的变体,父结点记录左右结点进行比赛的败者,而让胜者参与下一次比赛。败者树的根结点记录的是败者,需要额外增加一个结点记录胜利者。败者树的高度为 [ l o g 2 ( k + 1 ) ] [log_2(k+1)] [log2(k+1)],在每次调整,找下一个具有最小关键字的记录时,最多做 [ l o g 2 k ] [log_2k] [log2k]次关键字比较。

    27. 树的遍历方式有先序、后序、层序。中序无意义。

    28. 树的存储结构:

      • 双亲表示法,将每个结点按照层序存储在一维数组中,并记录其父结点在数组中的下标
      • 孩子链表表示法(邻接表),把每个结点的孩子看作一个线性表,且以单链存储,再将每个单链表的表首结点指针组织成一个线性表(顺序存储)
      • 双亲孩子表示法,在邻接表中增加一个域记录父结点的下标
      • 二叉链表表示法:左指针指向第一个孩子结点,右指针指向右兄弟结点,这种表示的先序遍历与原来相同,而二叉树的中序序列是树的后序序列
    29. 树(森林)转换为二叉树(二叉链表表示):

      • 连线:把每株树的各个兄弟结点连接起来,把各株树的根节点连接起来
      • 抹线:对于每个结点,只保留其与最左儿子的连线,抹去其它连线,包括与父节点
      • 旋转:按顺时针旋转45度(左链竖画,右链横画的情况)
    30. 用树表示集合:???

    31. 判定树:一棵判定树是一个算法的描述,每个叶子对应一个解,一个判定树是所有可能解的集合。

    32. 扩充二叉树(增长树),由外结点和内结点构成,在原二叉树中,对于每个结点,若出现空子树,则为其加上一个特殊结点(外结点),原来的结点称为内结点,得到新的二叉树称为原二叉树的扩充二叉树

      • 没有度数为1的结点
      • 外结点数 = 内结点数 + 1
      • 有n个外结点的扩充二叉树共有2n-1个结点
    33. 扩充二叉树外路径长E(根到每个外结点路径长之和)和内路径长I(根到每个内结点路径长之和)
      E = I + 2 × n E=I+2\times n E=I+2×n

    34. 扩充二叉树的加权路径长,外结点的数据 × \times ×根到外结点的路长

    35. 哈夫曼树(最优二叉树):加权路径长最小,可用于编码

      • 权值越大的叶子越靠近根节点
      • 只有度为0的结点(叶子结点)和度为2(分支结点)的结点,不存在度为1的结点
      • n个结点的哈夫曼树的结点总数为2n-1个
      • 哈夫曼树不唯一,但是最短加权路径长唯一
    36. 哈夫曼树的构造方法

      1. 初始化,由给定的n个权值构造n棵只有一个根节点的二叉树
      2. 选取与合并,选取根节点权值最小的二叉树分别作为左右子树合成一棵新的二叉树,新二叉树的根结点权值为左右结点权值之和
      3. 删除作为左右子树的二叉树,并将新建的树加入
      4. 重复2、3两步,直到只剩一棵二叉树为止,该树就是哈夫曼树
      
    37. 树的应用:表达式求值,叶节点为操作数,非叶节点为运算符,利用后序遍历遍历表达式树。

    第四章 图结构及其应用算法

    1. 图描述数据之间的任意关系,图是由定点的有穷非空集合和边集合组成的。顶点表示数据对象,边表示数据对象之间的关系。

    2. 完全图:无向完全图,任意两个顶点都存在边;有向完全图,任意两个顶点都存在方向相反的两条弧。

    3. 在无向图中,各顶点度数之和是边的数量的二倍。在有向图中,各顶点出度之和等于各顶点入度之和等于边数。

    4. 若一个无向图的任意一对顶点都是连通的,则称为连通图。非连通图的最大连通子图叫连通分量。强连通定义于有向图,要求存在双向路径。

    5. 图的存储:邻接矩阵存储,邻接表存储

      • 正邻接表,顶点表连接出边表
      • 逆邻接表,顶点表连接入边表
    6. 十字链表存储有向图

      结点分为顶点结点和弧结点,顶点结点使用一维数组组织在一起,弧结点使用链表连接在一起

      顶点结点包括第一个出弧和第一个入弧的域

    7. 多重邻接表存储无向图

      与十字链表类似,分为边结点和顶点结点

    8. 图的遍历:深度优先和广度优先

    9. 从一个顶点出发的深度优先遍历

      1. 访问第一个顶点v,并设为访问过的
      2. root设为v的第一个邻接点
      3. 当root不为空循环
         1. 若root未被访问,则递归执行该函数
         2. root设为v的下一个邻接点
      
    10. 从一个顶点出发的广度优先遍历:

      1. 初始化队列
      2. 访问顶点v,设为访问过的,并入队
      3. 当队列不为空时循环
         1. 将v设为队首元素,并出队
         2. 将w设为v的第一个邻接点
         3. 当w不为空循环
            1. 若w未被访问过,则访问顶点w,将w设为已访问过的,并入队
            2. w设为v的下一个邻接点
      
    11. 先深搜索对边的分类:树边,在搜索中经过的边;回退边,其它边。树边从先深编号较小的指向较大的。

    若图中存在环路,则在先深搜索过程中必遇到回退边

    1. 先广搜索对边的分类:树边,在搜索中经过的边;横边,其它边。树边从先深编号较小的指向较大的。

    若图中存在环路,则在先广搜索过程中必遇到横边

    1. 连通而无环的无向图称为开放树
    • 具有n个顶点的开放树有n-1条边
    • 如果在开放树中任意加一条边,便得到一个回路
    1. 最小生成树:图的所有生成树中,代价最小的生成树
    • 必须使用且仅使用该连通图中n-1条边连通n个顶点
    • 不能使用产生回路的边
    • 权值总和最小
    • 如果某条边的权值最小,则必存在包含改边的最小生成树(mst性质)
    1. Prim算法思想:

      从集合V中任取一顶点放入集合U

      接着找出权值最小的边(u, v),且 u ∈ U u\in U uU v ∈ ( V − U ) v\in (V-U) v(VU),且将边加入TE,并将顶点v加入集合U

      重复上述操作直到U=V,此时TE中有n-1条边,T=(U, TE)就是一棵最小生成树

    2. 克鲁斯卡尔(Kruskal)算法思想:

      设无向连通网G=(V, E),令G的最小生成树为T=(U, TE),令其初态为U=V,TE={ }。

      按照边的权值由小到大排序,依次考察G的边集E中的各条边。

      若被考察的边连接的是两个不同的连通分量,则将此边作为最小生成树的边加入T中,同时把两个连通分量连接为一个连通分量

      若被考察的边连接的是同一个连通分量,则舍去此边,以免造成回路

      如此循环至T中的连通分量个数为1时,此连通分量变为G的一棵最小生成树

    3. 关节点:删除该点及其相邻的边,会将图的一个连通分量分割为两个或以上的连通分量

    双连通图:无关节点的连通图,任何一对顶点间至少存在两条路径

    判断关节点:

    • 若生成树的根有两株或以上的子树,则此根结点必为关节点(第一类关节点)
    • 若生成树的非叶顶点v,其某株子树的根和子树的其它结点均没有指向v的祖先的回退边,则v是关节点(第二类关节点)
    1. 求无向图的双连通分量

      1. 对图进行深搜,计算每个结点v的先深编号dnf[v],形成先深生成树S=(V, T)
      2. 计算low[v],按后根顺序计算,low[v]取下述三个的最小者: 
          - dnf[v]
          - dfn[w],凡是有回退边(v, w)的任何结点w
          - low[y],对v的任何儿子y
      
    2. 求关节点

      1. 树根是关节点,当且仅当它有两个或两个以上的儿子
      2. 非树根结点v是关节点当且仅当v有某个儿子使得low[y] ≥ \ge dnf[v]
    3. 无环有向图可用于描述偏序关系:自反、反对称、传递

    拓扑排序:由某个集合上的一个偏序得到该集合的一个全序的过程,得到的线性序列称为拓扑序列

    AOV网:表示工程的有向图,顶点表示活动,弧表示活动之间的优先关系

    1. 利用AOV网进行拓扑排序(不唯一):
    1. 从AOV网中选择一个没有前驱的顶点并输出它
    2. 从AOV网中删除该顶点和所有以该顶点为尾的弧
    3. 重复上述两步,直到所有顶点都没输出或AOV网中不存在没有前驱的顶点
    
    1. 利用队列进行拓扑排序(广度优先)
    1. 初始化队列
    2. 将所有入度为0的顶点入队
    3. 若队列不空循环
       1. 输出队首结点
       2. 记下输出结点的数目
       3. 删去与之关联的出边
       4. 若有入度为0的结点,入队
    
    1. 利用栈结构进行拓扑排序:将以上队列改成栈即可

    2. 基于深搜的拓扑排序:将顶点入栈,标记为访问过的,遍历所有与栈顶邻接的顶点,若没访问过,则递归

    3. AOE网:在带权的有向图中,用顶点表示事件,边表示活动,边上的权表示开销

    4. 关键路径算法:

    • 关键路径:完成工程的最短时间是从源点到汇店的最大路径长度,该路径即为关键路径
    • 关键活动:关键路径上的活动
    1. 事件 V j V_j Vj最早可能发生的时间VE(j),是从源点 V 1 V_1 V1 V j V_j Vj到最长路径长度

    活动 a i a_i ai的最早可能开始时间E(i),是从源点到活动的前一个事件的最长路径长度

    事件 V k V_k Vk的最迟发生时间VL(k),是汇点的最早发生时间VE(n)减去 V k V_k Vk V n V_n Vn到最大路径长度

    活动 a i a_i ai的最迟允许开始时间L(i),是活动的后一个事件的最迟发生时间(VL(k))减去活动持续时间

    1. 关键路径算法的步骤:

      1. 从开始点出发,令VE(1)=0,按拓扑排序序列求其它各顶点的最早发生时间(最大)

      2. 从完成点出发,令VL(n)=VE(n),按照逆拓扑排序序列求其它各顶点的最迟发生时间(最小)

      3. 求每一项活动 a i a_i ai a i a_i ai在事件 v j v_j vj v k v_k vk之间:

        E ( i ) = V E ( j ) E(i) = VE(j) E(i)=VE(j)

        L ( i ) = V L ( k ) − A C T ( a i ) L(i) = VL(k) - ACT(a_i) L(i)=VL(k)ACT(ai)

      4. 选取E(i) = L(i)的活动即为关键路径上的活动

    2. 单源最短路径问题:求某个顶点到图中其它顶点的最短路径(Dijkstra算法)

      1. 将V分割成两个集合S(最短路径已确定)和V-S(未确定),初始S={1},一维数组D表示源点到顶点的当前最短路径长度,一维数组P表示源点到顶点的当前最短路径上最后经过的点,P[i]=1
      2. 从V-S中选取一个顶点w使得D[w]最小,于是从源点到达w只经过S中的顶点,且是一条最短路径,把w加入S
      3. 调整D中记录的从源点到V-S中每个顶点的最短距离,即从原来的D[v]和D[w]+C[w][v]中选择最小值作为D[v]的新值,且P[v]=w(选择第二个时)
      4. 重复2和3,直到S中包含V的所有顶点,D记录了从源点到各顶点的最短距离,P记录最短路径
    3. 任意两个顶点之间的最短路径(多源最短路径):Floyd算法,动态规划

    设 C 为n行n列的代价矩阵,c[ i, j ]为i —> j的权值。如果i=j;那么c[i, j] = 0。如果i和j之间无有向边;则c[ i, j ] = ∞

    1、使用n行n列的矩阵A用于计算最短路径。初始时,A[ i, j ] = c[ i, j ]

    2、进行n次迭代

    在进行第k次迭代时,将使用如下的公式:
    KaTeX parse error: No such environment: equation at position 11: \begin{̲e̲q̲u̲a̲t̲i̲o̲n̲}̲A_k[i,j]=min\be…

    注意:第 k 次迭代时,针对结点 k 进行。原 A k − 1 A_{k-1} Ak1矩阵的第k行,第k列保持不变。左上至右下的对角线元素也不变。

    1. 某个顶点到另一个顶点的最短距离的最大值称为该顶点的偏心度,具有最小偏心度的点称为图的中心点

    第五章 查找

    1. 静态查找:查找后的数据集合不改变

      动态查找:查找后的数据集合可能改变(插入删除)

    2. 查找算法的时间性能由关键字的比较次数来度量

    3. 折半(二分)查找:采用顺序式存储结构,关键字有序,仅适用于静态查找,折半查找的循环条件是 l o w ≤ u p low\le up lowup

    4. 折半查找判定树:

      当n>0时,折半查找判定树的根结点是有序表中序号为 m i d = n + 1 2 mid=\frac{n+1}{2} mid=2n+1的记录,根结点的左子树是有序表F[1]F[mid-1]对应的折半查找判定树,根结点的右子树是与F[mid+1]F[n]相对应的折半查找判定树

      判定树的高度是
      h = n + 1 n l o g 2 ( n + 1 ) − 1 h=\frac{n+1}{n}log_2(n+1)-1 h=nn+1log2(n+1)1

    5. 分块查找:均匀分块、块间有序、块内无序、建块索引,建立索引表,分块查找的平均长度为
      A S L ( L ) = n L + L 2 + 1 ASL(L)=\frac{\frac{n}{L}+L}{2}+1 ASL(L)=2Ln+L+1

    6. 二叉查找树(BST):左子树上所有结点的关键字小于根结点,右子树上所有结点的关键字大于根结点

      每个结点的右子树的最左结点称为其继承结点

    7. 二叉查找树的新插入的结点必为叶结点

      二叉查找树的删除:

      1. 如果是叶结点,则直接删除
      2. 如果被删除的结点只有一株左子树或右子树,则直接继承,将该子树移动到被删除结点的位置
      3. 如果被删除结点有两棵子树,则用继承结点代替被删除结点(数值替代),相当于删除继承结点(递归)
    8. 二叉查找树的查找性能在O( l o g 2 n log_2n log2n)到O(n)之间。

    9. AVL树是具有如下性质的BST:根结点的左右子树高度差绝对值不超过1

    10. AVL树调整:

    leftrightrotate.jpg

    左旋右旋:参与者三个结点

    参与者三个结点:最上面的结点为第一个出现不平衡的结点

    理解!!!

    1. AVL树的插入和删除和BST树相同,之后需要重新平衡该树。

    2. 一个包含n个结点的AVL树,最坏情况下的插入时间为O(logn)。

    3. m-路查找树:满足如下性质:

    • 根结点最多有m棵子树

    • 子树 A i A_i Ai的所有关键字都小于 K i + 1 K_{i+1} Ki+1而大于 K i K_i Ki

    • 树中可容纳关键字个数最大为 m h − 1 m^h-1 mh1

    1. B-树:一棵m阶B-树是一棵m-路查找树,满足一下性质:
    • 树中每个结点至多有m棵子树
    • 根结点至少有2棵子树
    • 除根结点和失败结点外,所有结点至少有[m/2]棵子树
    • 所有终端结点和叶子结点(失败结点)都位于同一层
    1. 若树中有关键字N个,则失败结点的个数为N+1

    设m阶B-树都高为h,失败结点位于h+1层,则关键字个数最少为
    2 [ m 2 ] h − 1 − 1 2[\frac{m}{2}]^{h-1}-1 2[2m]h11

    反之,如果在一棵m阶B-树中有N个关键字,则最大高度h满足
    h − 1 ≤ l o g [ m / 2 ] ( ( N + 1 ) / 2 ) h-1\le log_{[m/2]}((N+1)/2) h1log[m/2]((N+1)/2)

    1. B-树的插入操作:

    先确定可以插入的终端结点,这个结点的关键字个数应当在 [ [ m / 2 ] − 1 , m − 1 ] [[m/2]-1, m-1] [[m/2]1,m1]之间,若插入后小于上界,则可以直接插入,否则需要调整(自底向上分裂):

    1. 将该结点首先分裂为两个结点
    2. 将新插入的结点插入到父节点上
    3. 递归
    
    1. B-树的删除操作:

      若不是在叶结点上删除,则找到其左子树的最右节点或右子树的最左节点来代替,将删除转化为叶结点上的删除

      在叶结点上的删除分为四种情况:

      • 该结点同时也是根结点,则直接删去

      • 不是根结点,删除前该结点关键字个数 n ≥ [ m / 2 ] n\ge [m/2] n[m/2],则直接删去该结点

      • 被删除前关键字个数 n = [ m / 2 ] − 1 n=[m/2]-1 n=[m/2]1,若此时其右兄弟(或左兄弟)的关键字的个数 n ≥ [ m / 2 ] n\ge [m/2] n[m/2],则按照以下步骤调整:

        1. 将双亲结点中大于(小于)被删除关键字的最小(最大)关键字下移至结点p
        2. 将右兄弟(左兄弟)结点中最小(最大)关键字上移到双亲结点
        3. 将右兄弟(左兄弟)结点的最左(最右)子树指针平移到被删除关键字所在结点的最后(最前)子树指针位置
        4. 在右兄弟(左兄弟)结点中,将被移走的关键字位置用剩余的关键字和指针填补调整
      • 被删除关键字所在的叶结点p删除前关键字个数 n = [ m / 2 ] − 1 n=[m/2]-1 n=[m/2]1,若此时右兄弟(左兄弟)的关键字个数n= [ m / 2 ] − 1 [m/2]-1 [m/2]1,则合并结点,父节点下移,接着合并

    2. B+树的元素只存放在叶结点中,不是叶结点的结点称为中间结点,起到路标作用

    3. 散列技术:不依赖比较进行查找

      将记录的位置与关键字的值建立映射关系,该映射称为散列函数

      映射到的数组称为散列表,数组的每个元素称为一个桶

      不同关键字可能具有相同的散列地址的现象称为散列冲突,发生冲突的两个关键词称为同义词

    4. 散列函数的构造方法:

      • 直接定址法,散列函数是线性函数
      • 质数取余法
      • 平方取中法,取 k e y 2 key^2 key2的中间几位数作为散列地址
      • 折叠法,将地址分为若干段,将各段叠加和(舍去进位)作为散列地址
    5. 冲突的处理办法:开放定址法

      发生冲突时寻找下一个空的散列地址

      • 线性探测法,当发生冲突时,从冲突位置的下一个起,依次寻找空的散列地址,可能造成堆积(非同义词争夺同一个散列地址)

      • 线性补偿探测法:步长为某常数

      • 二次探测法:步长为某常数的平方

      • 随机探测法:步长为随机数,注意,插入、删除、查找需要用同一随机序列

    6. 冲突处理方法:带溢出表的内散列法

      每个桶带一个溢出部分用于存放多余的数值

    7. 冲突处理方法:拉链法(链地址法)

      将所有散列相同的记录,即所有同义词存储在一个单链表中,在散列表中中存储的是所有同义词子表的头指针

    第六章 内排序

    1. 排序不改变相同值的相对位置则称其为稳定的,否则就是不稳定的

    2. 气泡排序

      void BubbleSort(int n, LIST &A)
      {
          for(int i = 1; i < n; i ++)
          {
              for(int j = n; j > i; j ++)
              {
                  if(A[j].key < A[j-1].key)
                  {
                      swap(A[j], A[j-1]);
                  }
              }
          }
      }
      

      最好情况(正序):比较次数n-1,移动次数0,时间复杂度O(n)

      最坏情况(反序):比较次数 n ( n − 1 ) 2 \frac{n(n-1)}{2} 2n(n1),移动次数 3 n ( n − 1 ) 2 \frac{3n(n-1)}{2} 23n(n1),时间复杂度O( n 2 n^2 n2)

      平均时间复杂度 O ( n 2 ) O(n^2) O(n2)

    3. 快速排序

      1. 选择基准元素
      2. 划分
      3. 递归求解
      4. 组合

      基准元素的选取,从A[i].key到A[j].key最先找到的两个不同关键字中的最大者

      int FindPivot(int i, int j)
      {
          keytype firstkey = A[i].key;
          int k;
          for(k=i+1; k <= j; k ++)
          {
              if(A[k].key > firstkey)
                  return k;
              else if(A[k].key < firstkey)
                  return i;
          }
          return 0;	//找完全都相等,不需要排序
      }
      

      无序区的划分(分割)

      int Partition(int i, int j, keytype pivot)
      {
          int l, r;
          do{
              //移动前指针直到找到第一个比基准元素大的或等于的
              for(l = i; A[l].key < pivot; l++)//移动后指针直到找到第一个比基准元素小的
              for(r = j; A[l].key >= pivot; r--);
              if(l < r)swap(A[l], A[r]);
          }while(l <= r);
          return l;
      }
      

      快排

      void QuickSort(int i, int j)
      {
          keytype pivot;
          int k;
          int pivotindex;
          pivotindex = FindPivot(i, j);
          if(pivotindex != 0)
          {
              pivot = A[pivotindex].key;
              k = Partition(i, j, pivot);
              QuickSort(i, k-1);
              QuickSort(k, j);
          }
      }
      

      快速排序性能分析:

      最好情况:完全平均分割,时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),空间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n)

      最坏情况:时间复杂度 O ( n 2 ) O(n^2) O(n2),空间复杂度O(n)

      平均情况:时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),空间复杂度 O ( l o g 2 n ) O(log_2n) O(log2n)

    4. 直接选择排序

      每趟排序中当前排序序列中选出关键字最小(最大)的记录

      void SelectSort(int n, LIST A)
      {
          keytype lowkey;
          int i, j, lowindex;
          for(i = 1; i < n; i ++)
          {
              lowindex = i;
              lowkey = A[i].key;
              for(j = i+1; j <= n; j ++)
              {
                  if(A[j].key < lowkey)
                  {
                      lowkey = A[j];
                      lowindex = j;
                  }
              }
              swap(A[i], A[lowindex]);
          }
      }
      

      移动次数:最好(正序)0次,最坏3(n-1)次

      比较次数: 1 2 n ( n − 1 ) \frac{1}{2}n(n-1) 21n(n1)= O ( n 2 ) O(n^2) O(n2)

      时间复杂度 O ( n 2 ) O(n^2) O(n2),空间复杂度 O ( 1 ) O(1) O(1)

    5. 堆排序

      把具有如下性质的数组A表示的完全二叉树称为最小堆

      • 若2*i ≤ \le n,则A[i].key ≤ \le A[2*i].key(子节点大于父节点)
      • 若2*i+1 ≤ \le n,则A[i].key ≤ \le A[2*i+1].key

      堆排序的基本思想:

      • 将待排序的记录序列用完全二叉树表示
      • 接着完全二叉树构造一个堆
      • 将关键字最小者移走,将剩余的记录调整成堆,直到堆中只有一个根

      实现步骤:

      • 将记录用完全二叉树的数组表示
      • 初始建堆:把数组对应的完全二叉树以堆不断扩大的方式整理成堆。令i=n/2,…,2,1并分别把以n/2,…,2,1为根堆完全二叉树整理成堆,即执行PushDown(i, n)
      • 堆排序,令i=n, n-1, …, 2
        1. 交换,把堆顶元素(当前最小)与位置i(当前最大的叶结点下标)的元素交换
        2. 整理,把剩余的i-1个元素整理成堆,即执行PushDown(1, i-1)
        3. 重复执行,得到A[1], …, A[n]

      PushDown()函数:整理堆的函数,不断将根的元素下推到合适位置,遍历集合的一半元素并执行此动作

      算法性能分析:最好、最坏、平均时间复杂度 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n),空间复杂度O(1)

    6. (直接)插入排序

      每次将一个待排序的序列的记录按照关键字的大小插入到一个已经排好序的有序序列中

      void InsertSort(int n, LIST A)
      {
          int i, j;
          A[0].key = 负无穷;	//哨兵
          for(i = 1; i <= n; i ++)
          {
              j = i;
              while(A[j].key < A[j-1].key)
              {
                  swap(A[j], A[j-1]);
                  j = j - 1;
              }
          }
      }
      

      i的前半部分为已排好的记录,默认插在已排好的记录最后,再进行交换整理

      最好情况(正序):比较次数n-1,移动次数0,时间复杂度O(n)

      最坏情况(反序):比较次数 ( n + 2 ) ( n − 1 ) 2 \frac{(n+2)(n-1)}{2} 2(n+2)(n1),移动次数 ( n + 4 ) ( n − 1 ) 2 \frac{(n+4)(n-1)}{2} 2(n+4)(n1),时间复杂度 O ( n 2 ) O(n^2) O(n2)

      平均情况:比较次数 ( n + 2 ) ( n − 1 ) 4 \frac{(n+2)(n-1)}{4} 4(n+2)(n1),移动次数 ( n + 4 ) ( n − 1 ) 4 \frac{(n+4)(n-1)}{4} 4(n+4)(n1),时间复杂度 O ( n 2 ) O(n^2) O(n2)

    7. 希尔排序(分组插入排序)

      将全体记录分割为若干子序列,在子序列内部进行直接插入排序,待整个序列基本有序时,在对整个序列进行直接插入排序

      void ShellSort(int n, LIST A)
      {
          int i, j, d;
          for(d = n/2; d >= 1; d = d/2)		//步长除2
          {
              for(i = d+1; i <= n; i ++)
              {
                  A[0].key = A[i].key;
                  j = i - d;
                  while(j > 0 && A[0].key < A[j].key)
                  {
                      A[j+d] = A[j];
                      j = j - d;
                  }
                  A[j+d] = A[0];
              }
          }
      }
      

      时间复杂度在 O ( n 2 ) O(n^2) O(n2) O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)之间

    8. (二路)归并排序

      void Merge(int s, int m, int t, LIST A, LIST B)
      {
          int i = s; j = m + 1, k = s;
          while(i <= m && j <= t)
              B[k++] = (A[i].key <= A[j].key) ? A[i++]:A[j++];
          while(i <= m)
              B[k++] = A[i++];
          while(j <= t)
              B[k++] = A[j++];
      }
      

      以上代码A分为两路归并段,B用于存储归并后的序列

      归并:

      将一个待排序的序列看成n个长度为1的有序序列,多次两两归并,直到得到一个长度为n到有序序列

      以下为步长为h的一趟归并

      void MergePass(int n, int h, LIST A, LIST B)
      {
          int i, t;
          for(i = 1; i+2*h-1 <= n; i += 2*h)
              Merge(i, i+h-1, i+2*h-1, A, B);
          if(i+h-1<n)
              Merge(i, i+h-1, n, A, B);
          else
              for(t = i; t <= n; t ++)
                  B[t] = A[t];
      }
      

      完整归并

      void MergeSort(int n, LIST A)
      {
          int h = 1;
          LIST B;
          while(h < n)
          {
              MergePass(n, h, A, B);
              h = 2 * h;
              MergePass(n, h, B, A);
              h = 2 * h;
          }
      }
      

      最好、最坏、平均的时间复杂度为 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)

      空间复杂度O(n)

      使用分治法思想递归地进行归并:

      void MergeSort(LIST A, LIST B, int low, int high)
      {
          int mid = (low + high) / 2;
          if(low < high)
          {
              MergeSort(A, B, low, mid);
              MergeSort(A, B, mid+1, high);
              Merge(low, mid, high, A, B);
          }
      }
      
    9. 基数排序(桶排序)

      基本思想:

      1. 初态,设置10个队列,Q[0]~Q[9],均为空
      2. 分配,依次从原始队列中取出data,第pass遍时考察data右起第pass位数据,设其为r,将data插入Q[r],取尽A
      3. 从Q[0]开始依次取出所有Q队列的全部数据插入A
      4. 重复123步,关键字有figure位需要重复figure遍

    第七章 外排序

    1. 外部排序归并方法:

      1. 将文件中的数据分段输入到内存,在内存中采用内部排序的方法
      2. 将有序段写回外存
      3. 多次操作后外存中形成多个初始归并段
      4. 对这些初始归并段采用某种归并排序,进行多遍归并,最后形成整个文件的单一归并段。
    2. 通常,m个归并段,采用k路归并,需要[ l o g k m log_km logkm]遍归并。

    3. 在归并过程中,需要重复地输出各个归并段的第一个元素的最小值。可以采用选择树的思想来输出。一棵选择树是一棵二叉树(胜者树),其中每个结点代表两个儿子结点中的最小者,这样根结点就表示树中最小的元素。

    4. 第一次建立选择树所花时间O(k-1)=O(k)。之后每次重建选择树需要O( l o g 2 k log_2k log2k)。n个记录处理时间为初始建立选择树的时间加上n-1次重建选择树的时间:
      O ( ( n − 1 ) ⋅ l o g 2 k ) + O ( k ) = O ( n ⋅ l o g 2 k ) O((n-1)\cdot log_2k)+O(k)=O(n\cdot log_2k) O((n1)log2k)+O(k)=O(nlog2k)
      ​ 这时k路归并一遍所需的CPU时间,归并总遍数为 l o g k m log_km logkm,总时间为:
      O ( n ⋅ l o g 2 k ⋅ l o g k m ) = O ( n ⋅ l o g 2 m ) O(n\cdot log_2k\cdot log_km)=O(n\cdot log_2m) O(nlog2klogkm)=O(nlog2m)
      ​ 即K路归并CPU时间与k无关

    5. 初始归并段的生成(选择树法,初始归并段长度大于等于缓冲区长度)

      初始待排序文件为输入文件FI,初始归并段文件为输出文件FO,内存缓冲区为W,可容纳P个记录

      1. 从FI输入P个记录到缓冲区W
      2. 从W中选出关键字最小的记录MIN
      3. 将MIN输出到FO
      4. 若FI不空,则从FI输入下一条记录到W
      5. 从W中所有关键字比MIN关键字大的记录中选出最小关键字记录,作为新的MIN
      6. 重复3~5,直到在W中选不出新的MIN位置,得到一个初始归并段,输出归并段结束标志到FO中
      7. 重复2~6,直到W为空,由此得到全部到初始归并段
    6. 最佳归并树,外存读写次数最少

      Huffman树是一棵正则三叉树,若不足时可以添加虚设结点,虚设结点长度为0且离树根最远

      对于k路归并而言,设初始归并段为m,哈夫曼树为m叉,若
      ( m − 1 ) % ( k − 1 ) = 0 (m-1)\%(k-1)=0 (m1)%(k1)=0
      则不需要添加虚设,否则添加虚设的个数为:
      k − ( m − 1 ) % ( k − 1 ) − 1 k-(m-1)\%(k-1)-1 k(m1)%(k1)1
      读写次数为所有叶结点加权外通路长度的两倍。

    展开全文
  • 哈工大2013秋数据结构期末试题(含答案)

    千次阅读 多人点赞 2020-11-18 22:05:32
    哈工大2013秋数据结构期末试题原题答案其他年份的题 原题 答案 其他年份的题 哈工大2012秋数据结构期末试题(含答案) 哈工大2019秋数据结构期末试题 找到了其他年份的接着更新 需要pdf的可以联系我 ...
  • 哈工大2017秋数据结构期末试题

    千次阅读 2020-12-03 14:07:31
    哈工大2012秋数据结构期末试题(含答案) 哈工大2019秋数据结构期末试题 哈工大2015秋数据结构期末试题(含答案) 哈工大2013秋数据结构期末试题(含答案) (由于版权限制,无法将2015、2016年数据结构算法的答案发到网上...
  • 工大数据结构期末试卷。
  • 哈工大2020数据结构期末

    千次阅读 多人点赞 2020-12-07 09:59:01
    以上的算法总结都是笔者啃书,啃网课(B站王道考研,慕课 武大李春葆的数据结构)为期末准备做的笔记,有一些自己的看法,各位兄弟姐妹可以参考。 想要拿高分最好还是多刷题,考前一两个星期就要开始刷题了,纸张...
  • 因为考完试没有收演草纸,所以题中数据与考试差距不大。选项顺序可能略有差异;选择第5题希尔排序的序列数据是后编的;简答第3题B-树的插入序列顺序可能不同,但是考察的点是一样的。其他题的数据基本可以保证和原题...
  • 哈工大2012秋数据结构期末试题原题答案需要pdf文件的可以私聊我 原题 答案 需要pdf文件的可以私聊我
  • 班号 学号 姓名 哈工大2010年春季学期 数据结构与算法 A 试 卷 题号 一 二 三 四 总分 分值 15 15 20 20 70 得分 一填空题每空1分共15分 注意行为规范遵守考场纪律1. 在顺序存储的二叉树中编号为i和j的两个结点处在...
  • 文 彦 考 研让 | 梦想 | 有迹可循老师简介 逐勋师兄,2015年以专业课分数117的成绩考入哈尔滨工业大学计算机学院,连续3年从事哈工大计算机专业课考研辅导工作,精通计算机系统基础(csapp),计算机网络和数据结构,...
  • 哈工大2003年春季学期数据结构期末试卷,希望对大家有益
  • 哈尔滨工业大学数据结构试题,解压密码为:hitmath2010@126.com
  • 哈尔滨工业大学数据结构试题
  • 数据结构 学的怎么样 不好学吧 不要紧 把它看会你就过了
  • 数据结构,csapp往年期末题,数据结构真题,和2020年真题,mooc计网课件,包括解析(160买的。。)
  • 数据结构哈工大

    2013-12-25 14:36:31
    哈工大校本教材
  • 一、选择题 1. B 【详解】本题考查完全二叉树定义及性质,高度为 6 的完全二叉树最少结点数,应该是高度 为 5 的满二叉树的结点数加 1,即 25-1+1=32,所以选 B。 2.C 【详解】本题考查的是图的定义,树的定义。...
  • 此乃哈工大软件学院08年的数据结构考试试题,授课老师是黄虎杰
  • #include<iostream> #include<fstream> #include<...struct BTnode{ //声明一个树的节点,它包含这个节点的数据以及指向左儿子和右儿子的指针 char data; Tnode lchild,rchild; //指向左
  • 数据结构期末试题及答案 绝对经典! 你值得拥有
  • 数据结构哈工大期末考试 很好的题目 哈工大2003年春季学期
  • 第一章绪论一定要注意黑体字的概念,每年都有几分的填空!!! 增加分配空间的算法一定要注意成功或者不成功。 链队列设链队列指针目的是减少搜索 循环队列注意空,满的判断。 关于栈的应用看表达式求值。

空空如也

空空如也

1 2 3 4 5 ... 19
收藏数 364
精华内容 145
关键字:

哈工大数据结构期末

数据结构 订阅