复习重点1.数据结构的概念，逻辑结构、物理结构的概念及各自包含的内容2.算法的特性、设计要求，如何度量算法的时间效率。
3.线性表的顺序/链式存储结构的特点，插入、删除算法。
4.栈和队列的逻辑特性，顺序栈的入栈/出栈、循环队列的入队/出队算法。
5.以三元组顺序表存放的稀疏矩阵的转置算法。
6.二叉树的性质及其四种遍历算法。
7.森林与二叉树的相互转换。
8.WPL、前缀编码的概念，哈夫曼树的构造算法。
9.图的相关概念，邻接矩阵及邻接表的存储结构。
10.图的深度优先/广度优先遍历算法。
11.最小生成树的两种算法。
12.拓扑排序的意义和算法。
13.最短路径算法。
14.顺序表、有序表的查找算法。
15.二叉排序树的性质、插入/删除算法、平衡二叉树的性质、插入算法。
16.哈希表的相关概念，常用的冲突处理方法。
17.直接插入排序、希尔排序、快速排序、堆排序、归并排序的算法。
注意：1.上述每个知识点可能会以任何题型出现，复习的时候别把它们当做“简答题”来复习。
2.红色（下划线）标识的知识点或算法，只要求对给出的初始数据，能画出结果则可。
其他的算法则可能会出现在“算法题”中。
自测题第1章绪论一、判断1.顺序存储方式只能用于存储线性结构。
（错）2.顺序查找法适用于存储结构为顺序或链式存储的线性表。
（对）二、选择1.计算机算法必须具备输入、输出、（ B ）等5个特性。
A.可行性、可移植性和可扩展性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、安全性和稳定性2.算法在发生非法操作时可以作出处理的特性称为（C ）。
A.正确性B.易读性C.健壮性D.可靠性3.数据结构是一门研究非数值计算的程序设计问题中计算机的（A ）以及它们之间的（ B ）和运算的学科。
A.操作对象B.计算方法C.逻辑存储D.数据映像A.结构B.关系C.运算D.算法4.在数据结构中，逻辑上数据结构可分为：（B ）A.动态结构和静态结构B.线性结构和非线性结构C.紧凑结构和非紧凑结构D.内部结构和外部结构5.数据结构主要研究数据的（D ）A.逻辑结构B.存储结构C.逻辑结构和存储结构D.逻辑结构和存储结构及其运算的实现6.为了描述n个人之间的同学关系，可用（C ）结构表示A.线性表B.树C.图D.队列7.下面的程序段违反了算法的（A ）原则void sam(){ int n=2;while (!odd(n)) n+=2;printf(n);}A.有穷性B.确定性C.可行性D.健壮性三、问答1.什么是逻辑结构和物理结构？各自包含哪几种？2.线性结构和树型结构的特点分别是什么？3.简述顺序存储结构与链式存储结构在表示数据元素之间关系上的只要区别。
4.简述算法的5个特性。
第2章线性表一、选择1.线性表是具有n个（C ）的有限序列A.表元素B.字符C.数据元素D.数据项E.信息项2.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ A ）A.nB.2n-1C.2nD.n-13.下述哪一条是顺序存储结构的优点？（ A ）A．物理上相邻的元素在逻辑上也相邻B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示4.下面关于线性表的叙述中，错误的是哪一个？（B）A．线性表采用顺序存储，必须占用一段连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链式存储，不必占用一片连续的存储单元。
D．线性表采用链式存储，便于进行插入和删除操作。
5.指针P所指的元素是双向循环链表L的尾元素的条件是（D ）A.P=LB.P=NULLC.P->Link=LD.P->Rlink=L6.在一个单链表中删除P结点的后继结点的语句是（ A ）A.p->next=p->next->nextB.p=p->next；p->next=p->next->next;C.p->next=p->next;D.p=p->next->next;7.循环链表的主要优点是（D ）A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表二、问答1.在非空双向循环表中q所指的结点后面插入p所指的结点的语句是？2.循环队列为满和空时的条件。
3.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？4.设单链表中结点的数据域为data，指针域为next，指针p为表中某一结点的地址，请写出在p结点之前插入一个s结点的C语言描述语句。
第3章栈和队列一、选择1.PUSH和POP命令常用于（C ）操作A.队列B.数组C.栈D.记录2.判断一个表达式中左右括号是否匹配，采用（ D ）实现较为方便A.线性表的顺序存储B.队列C.线性表的链式存储D.栈3.用单链表表示的链式队列的对头在链表的（ A ）位置A.链头B.链尾C.链中4.设栈的输入序列是1,2,3,4，则（ D ）不可能是其出栈序列A.1,2,4,3B.2,1,3,4C.1,4,3,2D.4,3,1,2E.3,2,1,45.循环队列A[0..m-1]存放其元素，用front和rear分别表示队头和队尾，则循环队列满的条件是（ A ）A.（Q.rear+1）%m==Q.frontB.Q.rear==Q.front+1C.Q.rear+1==Q.frontD.Q.rear==Q.front6.一般情况下，将递归算法转换成等价的非递归算法应该设置（ A ）A.栈B.队列C.栈和队列D.数组二、判断1.栈和队列都是限制取点的线性结构。
（对）2.消除递归不一定需要使用栈。
（对）3.栈、先进先出队列、优先级队列、双端队列等都可以看作是一个容器类的派生类。
该容器代表限制存取位置的顺序存取结构。
（对）三、问答1.在操作序列push(1)，push(2)，pop，push(5)，push(7)，pop，push(6)之后，栈顶元素和栈底元素分别是什么？2.在操作序列Qinsert(1)，Qinsert(2)，Qdelete，Qinsert(5)，Qinsert(7)，Qdelete，Qinsert(9)之后，队头元素和队尾元素分别是什么？第5章数组一、选择1.设数组a[1..10,5..15]的元素以行为主序存放，每个元素占用4个存储单元，则数组元素a[i,j](1≤i≤10,5≤j≤15)的地址计算公式为（ D ）A.a-204+2i+jB.a-204+40i+4jC.a-84+i+jD.a-64+44i+4j2.对于二维数组A[1..4,3..6]，设每个元素占两个存储单元，若分别以行和列为主序存储，则元素A[3,4]相对于数组空间起始地址的偏移量分别是（ D ）和（ A ）A.12B.14C.16D.183.将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，A中元素A66,65（即元素下标）在B中的位置K为（ B ）A.198B.195C.1974.三对角线矩阵A[1..n][1..n]以行序为主顺序存储，其存储始址是B，每个元素占一个存储单元，则元素A[i][j]的存储起始地址为（D ）(1≤i,j≤n)A.b+2*j+i-2B.b+2*i+j-2C.b+2*j+i-3D.b+2*i+j-3第6章树和二叉树一、判断1.将一棵树转化为二叉树后，根结点可能有右子树。
（错）2.高度为K的二叉树至多有2k-1个结点。
（错）3.Huffman树、平衡二叉树属于逻辑结构。
（对）二、选择1.在一颗非空二叉树中，叶子节点的总数比度为2的节点总数多（ C ）个A.-1B.0C.1D.22.在一棵完全二叉树中，其根的序号为1，（A ）可判定序号为p和q的两个结点是否在同一层。
A. │log2p」=│log2q」B.log2p=log2qC.│log2p」+1=│log2q」D.│log2p」=│log2q」+13.如果根的层次为1，具有61个结点的完全二叉树的高度为（ B ）A.5B.6C.7D.84.若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为（D ）A. DEBAFCB. DEFBCAC. DEBCFAD. DEBFCA5.由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ C ）A.23B.37C.44D.466.（ C ）的遍历仍需要栈的支持A.前序线索树B.中序线索树C.后序线索树7.对于前序遍历和中序遍历结果相同的二叉树为（ F ）；对于前序遍历和后序遍历结果相同的二叉树为（ B ）。
A.一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树E.所有的结点只有左孩子的二叉树F.所有结点只有右孩子的二叉树8.哈夫曼树是带权路径长度最短的树，路径上权值较小的结点离根（C ）A.不确定B.较近C.较远9.在线索化二叉树中，结点t没有左子树的充要条件是（B ）A.t->lchild=nullB.t->ltag=1C.t->ltag=1 且t->lchild=null D以上都不对三、问答1.假设先根次序遍历某棵树的结点次序为SACEFBDGHIJK，后根次序遍历该树的结点次序为CFEABHGIKJDS，要求画出这棵树。
2.简述二叉哈夫曼树的建树方法。
3.设记录的关键字（key）集合K={26,36,41,44,15,68,12,6,51,25}，以K为权值集合，构建一棵哈夫曼树，依次取K中各值，构建一棵二叉排序树。
第7章图一、判断1、不是所有的AOV网都有一个拓朴序列。
（对）2、每个加权连通无向图的最小生成树都是惟一的。
（错）3、邻接表对于有向图和无向图的存储都适用。
（对）二、选择1、采用邻接表表示一有向图，若图中某顶点的入度和出度分别为d1和d2，则该顶点对应的单链表的结点数为（ B ）A.d1B.d2C.d1-d2D.d1+d22、具有n（n>0）个顶点的无向图最多含有（C ）条边A.n(n-1)B.n(n+1)/2C.n(n-1)/2D.n(n+1)3、无向图中一个顶点的度是指图中（ C ）A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻接的顶点数D.与该顶点连通的顶点数4、一个具有n（n>0）个顶点的连通无向图至少有（ D ）条边A.n+1B.nC.n/2D.n-15、无向图G=(V,A)，其中V={a,b,c,d,e}，A={<a,b>,<a,c>,<d,c>,<d,e>,<b,e>,<c,e>}，对该图进行拓朴排序，下面序列中哪一个不是拓朴序列.（ D ）A.a,d,c,b,eB.d,a,b,c,eC.a,b,d,c,eD.a,b,c,e,d6、在对有向图G进行拓扑排序的目的不是（B ）。