数据结构复习要点及习题.docVIP

复习要点及习题 第一章： 1、算法及特点 1）：有穷性 2）：确定性 3)：输入 4）：输出 5）：可行性 2、算法评价的主要标准 1）：正确性 2）：可读性 3）：健壮性 4）：效率与低存储量需求 习题：P11页： 3、4、 第二章： 1、 线性表的顺序存贮与特点 答：在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素称为线性表的顺序存储结构 2、线性表的链式存贮与特点 答：线性表的链式存储结构就是用一组任意的单元---结点（可以是不联系的）存储线性表的数据元素。表中每一个数据元素都由存放数据元素的数据域和存放直接前驱或直接后继结点的地址（指针）的指针域组成。 习题： P16 算法2.2 顺序表的删除 Int delete(sqlist L,int i) { Int j; If(i0||ilength) {printf(“error!”);return false;} For(j=i+1;jL.length;j++) L.list[j-1]=L.list[j]; L.length--; Return true; } P23 算法 2。7 单链表的删除 Int delet(slnodetype *h,int i) { Slnodetype *p,*s; Int j; P=h;j=-1; While（p-next!=NULLji-1） {p=p-next;j=j+1;/*寻找第i-1个结点，p指向其前驱*/} If(p-next==NULL) {printf(“Error!”); Return FALSE;} s=p-next; p-next=p-next-next; free(s); return TRUE; } 第三章： 1、 栈的定义及特点 答：栈：是一种值允许在一端进行插入和删除的线性表，是一种操作受限的线性表，在表中只允许进行插入和删除的一端称为栈顶（top），另一端称为栈底（buttom），称为后进先出的线性表。 2、栈的顺序存贮结构 答：利用一组地址连续的存储单元依次存放自栈底到栈顶的各个数据元素，称为栈的顺序存储结构。 3、算术表达式的前缀、后缀表示法 4、队列的定义及特点 答：队列是一种只允许在一端进行插入，而在另一端进行删除的线性表，它是一种操作受限的线性表。在表中值允许插入的一端称为队尾（rear），只允许进行删除的一端称为队头（fornt），队头元素总是最先进队列的，也总是最先出队列的，称为：先进先出表 习题： P64 2、3、4 P40 算法3.2 入栈操作、 算法3。3 出栈操作 Int push(sqsstack *s,elemtype x) { If(s-topmaxNum-1) Return false; s-top++; s-stack[s-top]=x; return true; } Int pop(sqsstack *s) { If(s-top0) Return null; X=s-stack[s-top]; s-top--; return x; } 第六章： 1、树的定义 2、二叉树的定义以及与树的区别 3、满二叉树、完全二叉树。 4、遍历二叉树 5、二叉排序树 6、哈夫曼树和哈夫曼算法 习题： P154 1、①②③、2、4、8、9、10 P126 算法 6.4 层次遍历算法 算法 6。5 求树叶结点数 算法6.6 求二叉树的深度算法 Int depth(lnodetype *t) { If(t==null) Return 0; Else Dep1=depth(t-rch); Dep2=depth(t-lch); If(dep1dep2) Return (dep1+1); Else Return (dep2+1); } 第七章： 1、图的相关概念、特点、 无向图、有向图、无向网 2、邻接矩阵的建立、特点 3、邻接表、逆邻接表、特点 4、最小生成树 5、最短路径 习题： P189 1、2、5 第八章： 1、顺序查找 2、哈希法 习题： P201 1、 5 第九章： 9．2 希尔排序 9．5 快速排序 习题 一、选择题： 1、带头结点的单链表L为空的判定条件是( B )。 A．L==NULL B.L-next==null C. L-next==L D.L!=NULL 2、算法分析的二个主要方面是 ( A )。 A．空间复杂度和时间复杂度 B. 正确性和可