《2014下数据结构复习.doc

2014下《数据结构》复习提纲 第1章 绪论 有关术语；算法、算法复杂度的分析和计算方法 例题： 1．下面算法的时间复杂度为O( n )。 int f( unsigned int n ){ if ( n = = 0 || n = = 1 ) return 1; else returen n *f ( n – 1 ); } 2．for（i=1，s=0； i=n； i++） {t=1；for(j=1；j=i；j++) t=t*j；s=s+t；}O(n2) 第2-3章 线性表，栈和队列 线性表的概念、存储结构、插入与删除操作； 栈和队列的概念，理解栈顶指针、队首、队尾指针的意义和作用，特别是循环队列的头、尾指针的设置。为什么要这样设置。它们基本操作的实现。判空和判满？了解有关应用。 例题： 1．在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行的语句？（答：q-next=s; s-next=p）；注意在某个已知结点前插需要执行的语句？ 2．注意循环（链）队列的判空和判满的条件？（看书理解！） 3．对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为 O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n)。 4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为 (rear+l)％n= = front。 执行出队操作后其头指针front如何? 5. 线性表采用链式存储时，结点的存储地址连续与否均可; 6. 链式栈删除栈顶元素的操作序列为top=top-next. 7. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是p-next=p-next-next. 8. 判定“带头结点的链队列为空”的条件是Q.front==Q.rear. 9. 假设以数组seqn［m］存放循环队列的元素，设变量rear和quelen分别指示循环队列中队尾元素的位置和元素的个数。队满的条件表达式quelen == m；队空的条件表达式quelen == 0；队头元素位置的表达式 ( rear - quelen + m ) % m 第6章 树和二叉树 树和二叉树的定义、完全二叉树及其性质、存储表示及遍历算法（递归和非递归）、哈夫曼树的概念。 例题： 1．在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0= n2+1。（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加1 ）Huffman树，其节点总数为2n-1. 3. 设用权6，10，13，14，20，37构造Huffman树，则该Huffman树的根结点的权值为100. （仔细验算构造Huffman树） 4. 一棵深度为k的满二叉树的结点总数为 2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1，最大值为2k-1。 5. 深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树. 6. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDECF ，中序遍历序列为DBEAFC ，后序遍历序列为DEBFCA. 7. 一棵完全二叉树中共有768结点，则该树中共有384个叶子结点。 8. 深度为k的完全二叉树中最少有2k-1个结点。 9. 二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是任一结点无右孩子 第7章 图 图的存储及遍历算法，图的有关概念，最短路径,（最小）生成树 例题： 1．由一个具有n个顶点的连通图生成的最小生成树中，具有n-1 条边。 2．有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入度。 3. 若要把n个顶点连接为一个连通图，则至少需要n-1 条边。 4. 连通图G中有n个顶点e条边，则对应的最小生成树上有n-1条边 5．在一个图中，所有顶点的度数之和等于所有边数的 2 倍。 6.在一个具有n个顶点的无向完全图中，包含有n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。 7.无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为O(n2); 用邻接表作为图的存储上述复杂度O(n+e). 8.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为n2－2e. 9.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为d=e. 10. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=d/2 11.掌握最小