数据结构总复习和作业

《数据结构总复习和作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构总复习考试时间：第10周周日(5月10日)九、十节考试教室安排：考试方式：闭卷笔试考试成绩＝卷面(80％)＋平时作业(20％)考试题型(参考）：1、判断对错、选择、填空2、综合应用3、算法设计数据结构答疑安排：大黑楼A802或A718周三(5月6日)下午1:30～5:00第一章绪言基本概念和术语（掌握）数据结构，数据，数据元素，数据项逻辑结构与存储结构算法分析（掌握）算法定义算法特性：算法评价：时间复杂度与空间复杂度（了解）第二章线性表逻辑结构（掌握）存储结构（掌握）顺序存储结构链式存储结构单链表双向链表循环链表双向循环链表静态链表（了解

2、）基本操作（掌握）插入删除查找应用------一元多项式相加（掌握）时间复杂度第三章栈和队列---操作受限的线性表栈特点（掌握）：FILO(LIFO)存储结构（掌握）：顺序栈与链栈基本操作（掌握）：入栈与出栈应用（掌握）：回文、括号匹配、表达式求值3队列特点（掌握）：FIFO（LILO）存储结构（掌握）：顺序队列链队列循环队列（掌握）基本操作（掌握）入队出队应用（了解）：迷宫，优先队列等队空、队满条件第四章数组线性结构存储结构顺序存储结构（掌握）：次序约定（算法实现不要求）压缩存储（掌握）对称矩阵对角矩阵三角矩阵稀疏矩阵算法：求转置矩阵（了解）三

3、元组表行逻辑链接的顺序表带行指针向量的单链表十字链表第五章树逻辑结构：按分支关系定义的层次结构定义（掌握）：深度、度、叶子等满二叉树、完全二叉树二叉树性质（掌握）：5存储结构树（掌握）双亲表示法孩子表示法（孩子链表与多重链表）孩子兄弟表示法（二叉链表）二叉树（掌握）顺序存储结构二叉链表三叉链表树、森林与二叉树转换（掌握）遍历按层次、先序、中序、后序遍历递归（掌握）与非递归算法（了解）遍历算法应用（掌握）由先序序列建立二叉链表统计叶子结点求二叉树深度已知先序和中序序列，构造二叉树应用Huffman树（掌握）定义，WPL构造方法有n个叶子结点的Huf

4、fman树共有2n-1个结点应用Huffman编码与译码最佳判定树第六章图定义（掌握）：图、有向图、度、连通、完备图等存储结构邻接矩阵（掌握）邻接表与逆邻接表（掌握）十字链表（了解）邻接多重表（了解）遍历：深度优先与广度优先（掌握遍历策略及算法）深度优先生成树、广度度优先生成树构成特点(与顶点度关系)应用（掌握求解过程，不要求写算法）最小生成树（Prim与Kruscal）拓扑排序最短路径（Dijkstra）第七章查找静态查找表顺序查找（掌握）折半查找（掌握）分块查找（了解）动态查找表（了解）二叉排序树定义构造方法生成、插入、删除与查找中序遍历二叉

5、排序树可得到结点有序序列比较、ASL哈希查找（掌握）定义、基本思想Hash函数构造方法处理冲突方法哈希表构造哈希查找过程与ASL第八章排序掌握排序的基本概念和性能分析方法，排序策略插入排序直接插入排序（掌握）折半插入排序（掌握）希尔排序（了解）交换排序冒泡排序（掌握）快速排序（了解）选择排序简单选择排序（掌握）堆排序（掌握，不考算法）归并排序：2-路归并排序（了解）基数排序：链式基数排序（了解）排序方法思想每趟排序结果排序方法性能分析评价本章"了解"的排序方法不要求掌握算法作业1.线性表从键盘读入n个整数（升序），请编写算法实现：CreateLi

6、st()：建立带表头结点的单链表；PrintList()：显示单链表(形如:H->10->20->30->40);InsertList()：在有序单链表中插入元素x；ReverseList()：单链表就地逆置；DelList()：在有序单链表中删除所有值大于mink且小于maxk的元素。选作：使用文本菜单完成功能选择及执行。思考题：你能将上述算法改为双向循环链表吗？作业1L3124^5qp^tempq单链表就地逆置L1324^5p^tempqq单链表就地逆置L2134^5^tempqptempq单链表就地逆置L5214^3qp^tempq单链表就

7、地逆置L4523^1^voidListReverse_L(LinkList&L){LinkListp,q,u;p=L->next;if(p==NULL

8、

9、p->next==NULL)//空链表或只有一个结点return;q=L->next->next;//q指向第二个结点p->next=NULL;while(q){u=q->next;q->next=L->next;L->next=q;q=u;}}单链表就地逆置L3124^5qp^pretempq单链表就地排序L1324^5p^pretempqq单链表就地排序L1234^5^tempqqppre单

10、链表就地排序L1234^5^tempqqppre单链表就地排序L1234^5^tempqqppre^单链表就地排序L1234^5qppr