华中师范大学考研资料数据结构数据结构注意事项.pdf

数据结构注意事项 第一章 一、相关概念 （背 ） 注意判断逻辑结构与物理结构 ：eg ：栈是不是逻辑结构 二、 注意：1、 O(log2n)不一定小于 O(n2) 2、一个算法的时间复杂度与实现算法的语言无关 3、时间复杂度是问题规模 （n ）的函数 4、时间复杂度与 执行次数 （资料 2 P14类似数组画 ）区别 5、堆可看成完全二叉树 ，但是它是元素序列 ，存在一维数组中 ，可看成线性结构 6、O(n2)表示执行时间与 n2成正比 7、顺序结构不需要存储数据结构中元素之间的关系 ，而链式的需要 第二章 线性表 1、 考虑表空时 ，资 2-P23 第三章 栈与队列 1、 队列 ：n个数的输入顺序总是与 输出顺序一致 ；而 栈不一定 ； 2、 链队的插入和删除可能同时改变 rear和 front 指针 3、 队列的运算 是 二叉树的层次遍历 ；栈的运算与 先序遍历有关 4、 n个数入栈 ，出栈的序列 公式 ：1/ （n+1 ）*(2n)!/( (n!) *(n!)); 与二叉树的构成序列一样的公式 ； 第四章 数组 1、 基本操作 ：查找与修改 ；不能插入与删除 2、 三元组还有一个总的列 第八章 1、处理冲突的办法中 ，eg ：平方探测法 ： 设发生冲突的地址为 d ，则平方探测序列为 d*d+1*1 2、ASL不成功 ：线性探测—数到空格 平方探测数下面的 线性表满条件 链表删除：while （p！NuLL…）然后if （） 数据结构常见问题 一、 链表 1、插入||删除：  插入||删除位置的前驱  P-next 发生改变 二、 建表类 1、尾插：linklist *p L-next , *r; r ha; … r-next null; （最后要） 2、直插：linklist *p L-next , *q; L-next null; (可能有) q p-next ; … ;p q ; (可能有) 三、 顺序表：有2个结构，所以要考虑L.lengh 四、 循环 循环3要素：  初始状态：i 0  循环条件：in  i++; 五、 排序 注意有一个 tmp 字符串：2点_最后与开头 链表插入：2_前驱与p-next变