第一章绪论
1.有如下程序段：
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
++t;
}
他的算法时间复杂度为：n n
第二章线性表
1.若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？
2.线性表有两种存储结构：一是顺序表，二是链表。试问：
（1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？链表
（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？顺序表
3.在顺序表中，逻辑上相邻的元素，其物理位臵相邻。在单链表中，逻辑上相邻的元素，其物理位臵相邻。
4.线性结构包括哪几种？
5.已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是：。
b. 在P结点前插入S结点的语句序列是：。
c. 在表首插入S结点的语句序列是：。
d. 在表尾插入S结点的语句序列是：。
供选择的语句有：
（1）P->next=S;
（2）P->next= P->next->next;
（3）P->next= S->next;
（4）S->next= P->next;
（5）S->next= L;
（6）S->next= NULL;
（7）Q= P;
（8）while(P->next!=Q) P=P->next;
（9）while(P->next!=NULL) P=P->next;
（10）P= Q;
（11）P= L;
（12）L= S;
（13）L= P;
第三章栈和队列
1.有5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
2.栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过S栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3,a5,a6,a4,a2,a1，则栈S至少应该容纳个元素。
3.循环队列引入原因，循环队列如何判断队空队满
第四章串
1.下面关于串的的叙述中，哪一个是不正确的？（）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
2.求串‘ababaaababaa’的next数组
3.求字符串‘ababaabab’的nextval数组
4.设字符串S=‘aabaabaabaac'，P=‘aabaac'
（1）给出S和P的next值和nextval值；
（2）若S作主串，P作模式串，画出利用KMP算法进行模式匹配时每一趟的匹配过程。
第五章数组
1.设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址是多少;若以列序为主序顺序存储，则元素a[45,68]的存储地址是多少。
2.设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，求上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位臵
3.设矩阵A=
⎥
⎥
⎥
⎥
⎦
⎤⎢
⎢
⎢
⎢
⎣
⎡
4
3
3
4
2
(1) 若将A视为对称矩阵，画出对其压缩存储的存储表，并讨论如何存取A中元素
a ij (0<=i,j<4)；
(2) 若将A视为稀疏矩阵，画出A的十字链表结构。
(3) 若将A视为稀疏矩阵，画出其三元组表形式压缩存储表。
第六章树和二叉树
1.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为_________。
2.一棵完全二叉树上有1001个结点，其中叶子结点的个数是
3.设给定权值总数有n 个，其哈夫曼树的结点总数为
4.一个具有1025个结点的二叉树的高h为（）
A．11 B．10 C．11至1025之间 D．10至1024之间
5.一棵深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按从上到下，从左到右顺序从1开始对全部结点编号，问：（1）各层的结点数目是多少？（2）编号为p的结点的父结点(若存在)的编号是多少？（3）编号为p的结点的第i个儿子结点(若存在)的编号是多少？（4）编号为p 的结点有右兄弟的条件是什么？其右兄弟的编号是什么？
6.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。
A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历
7. 某二叉树中序序列为A,B,C,D,E,F,G ，后序序列为B,D,C,A,F,G,E 则前序序列是多少？ 这棵二叉树对应的森林包括多少棵树
8. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
A ．所有的结点均无左孩子
B ．所有的结点均无右孩子
C ．只有一个叶子结点
D ．是任意一棵二叉树
9. 算术表达式a+b*（c+d/e ）转为后缀表达式后是什么
10. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码
第七章 图
1. 设无向图的顶点个数为n ，则该图最多有（ ）条边
2. 从邻接阵矩
⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=010101
010
A 可以看出，该图共有（ ）个顶点；如果是有向图该图共有（ ） 条弧；如果是无向图，则共有（ ）条边。
3. 当一个有N 个顶点的无向图用邻接矩阵A 表示时，顶点Vi 的度是（ ），若是当一个有N 个顶点的有向图用邻接矩阵A 表示时，顶点Vi 的度是（ ）
4. 已知一无向图G=（V ，E ），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a 开始遍历图，得到的序列为abecd ，则采用的是____________遍历方法
5. 已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5 }，
E={,,,,,,,},G 的拓扑序列可能是几个
6. 有向图的邻接表存储如下：（1）．画出其邻接矩阵存储；（2）．写出图的所有强连通分量；（3）画出其逆邻接表。
7. 下面的邻接表表示一个给定的无向图
（1）给出从顶点v1开始,对图G 用深度优先搜索法进行遍历时的顶点序列；
（2）给出从顶点v1开始,对图G 用广度优先搜索法进行遍历时的顶点序列。
