2014奥赛考前复习—数据结构论述.ppt

2. 循环队列的进队和出队 （1）队头指针: front = (front + 1) % maxSize; （2）队尾指针: rear = (rear + 1) % maxSize; （3）队列初始化：front = rear = 0; 3. 循环队列的队空队满问题 （1）队满：(rear+1) % MaxSize==front (2)队空: front = rear ;3. 队列适用于下列（　　）种应用 A. 表达式求值 　 B. 堆排序算法实现　 C. 树的层次遍列算法实现 D. 二叉树中序遍列算法实现 E. 二叉树先序遍列算法实现;10 链表 ;1. （十六普）双向链表中有两个指针域llink和rlink，分别指向该结点的前驱及后继。设p指向链表中的一个结点，它的左右结点均为非空。现要求删除结点p，则下列语句序列中错误的是(??? )。 A．p^.rlink^.llink=p^.rlink; ??p^.llink^.rlink=p^.llink; delete p; B．p^.llink^.rlink=p^.rlink; ?p^.rlink^.llink = p^.llink; delete p; C．p^.rlink^.llink = p^.llink; p^.rlink^.llink ^.rlink = p^.rlink; delete p; D．p^.llink^.rlink = p^.rlink; p^.llink^.rlink^.link = p^.llink; delete p;;11 树 ;11.4树的遍历 ;11. 5 Huffman树;构造二叉哈夫曼树;11.6 堆 ;堆(以小根堆为例);堆——选择与维护;11. 7 二叉有哪些信誉好的足球投注网站树;;二叉有哪些信誉好的足球投注网站树的删除 ;11. 8 并查集 ;11.8.3并查集操作;12 图;12.1.2图的存储结构;12.3 最小生成树 ;12.3.2 Kruskai算法;12.4 拓扑排序关键路径 ;;12.5 最短路径;12.4 欧拉图与哈密顿图 ;（1）无向图G是欧拉图? G是连通的且G中所有顶点都是偶数度 （2）有向图D是欧拉图? D是强连通的且每个顶点的出度等于入度。 （3）无向图G是半欧拉图? G是连通的且恰有两个奇度顶点。;12.4.2 哈密顿概念;13.1选择类排序;13.2 插入类排序;13.3交换类排序 ;13.4其它类型排序 ;14 查找;14.1顺序查找 且顺序查找的时间复杂度为O(n) 14.2 二分查找 二分查找又称折半查找，首先要求待查找的表是有序表 二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)。 最好的情况是指针mid指的第一个数就是要找的值 14.3 二叉排序树 满二叉树 完全二叉树 丰满树 平衡树 ;14.9 哈希表