2014(下)数据结构复习

《2014(下)数据结构复习》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014下《数据结构》复习提纲第1章绪论有关术语；算法、算法复杂度的分析和计算方法例题：1．下面算法的时间复杂度为O(n)。intf(unsignedintn){if(n==0

2、

3、n==1)return1;elsereturenn*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章线性表，栈和队列线性表的概念、存储结构、插入与删除操作；栈和队列的概念，理解栈顶指针、队首、队尾指针的意义和作用，特别是循环队列的头、尾指针的设置。为什么要这样设置。它们基本操作的实现。判空和判

4、满？了解有关应用。例题：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。执行出队操作后其头指针fr

5、ont如何?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章树和二叉树树和二叉

6、树的定义、完全二叉树及其性质、存储表示及遍历算法（递归和非递归）、哈夫曼树的概念。例题：1．在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加1）;对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中n-1个用于链接孩子结点，n+1个空闲着。2.n个权构成一棵Huffman树，其节点总数为2n-1.3.设用权6，10，13，14，20，37构造Huffman树，则该Huffman树的根结点的权值为100.（仔细验算构造Huffman树）4.一棵深度为k的满二叉

7、树的结点总数为2k-1，一棵深度为k的完全二叉树的结点总数的最小值为2k-1，最大值为2k-1。5.深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树.6.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，后序遍历序列为DEBFCA.7.一棵完全二叉树中共有768结点，则该树中共有384个叶子结点。8.深度为k的完全二叉树中最少有2k-1个结点。9.二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是任一结点无右孩子第7章图图的存储及遍历算法，图的有关概念，最短路径,（最小）生成树例题

8、：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条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先

9、遍历时的时间复杂度为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/211.掌握最小生成树算法.例如使用普里姆（Prim）算法以A为源点，构造下图的最小代价生成树，画出各步的结果。AFGDBCAFADFACDFAG