1.在线性表中最常用的操作是存取第i个元素及其前驱的值，采用( A )存储方式最省时间。
A.顺序表 B.带头结点的单链表 C.带头指针的双向循环链表 D.带头指针的单向循环链表
2．在一个单链表中，已知z结点，若在z后插入j结点，则须执行( C )。
A. z->next=j->next; j->next=z; B. j->next=z; z->next=j->next C. j->next=z->next; z->next=j; D. z->next=j; j->next=z;
3. 一个稀疏矩阵采用三元组表示压缩存储后，和直接采用二维数组存储相比会失去（ B ）特性。
A.顺序存储 B.随机存取 C.输入输出 D.以上都不对
4. 假设以行序为主序存储二维数组A=array[1..40，1..90]，设每个数据元素占2个存储单元，基地址LOC[1,1]为500，则LOC[35，63]的存储位置为( D)。
解析：Loc(i,j)=Loc(1，1)+[n×(i-1)+j-1]×b，其中，Loc(1，1)是第一个元素A[1][1]的首地址，b是每个元素占用的存储单元个数。代入数据便得LOC[35，63] =500+[90*(35-1)+63-1]*2=6744
A.6746 B.6924 C.6926 D.6744
5.递归过程或函数调用时，处理参数及返回地址要用一种称为( C )的数据结构。
A.队列 B.数组 C.栈 D.线性表
6.一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是( B )。
A.23415 B.54132 C.23145 D.15432
7.设数组Data[m]作为循环队列SQ的存储空间，front为头指针，rear为尾指针，则执行出队操作后，头指针front的值为( D )。
A. front=fornt+1 B. front=(fornt+1)%(m-1) C. front=(fornt-1)%m D. front=(fornt+1)%m
8.设循环队列中数组的下标范围是1至n，其头尾指针分别为f和r，则队列中的元素个数为( D )。
A.r-f B.r-f+1 C.(r-f+1)%n D.(r-f+n)%n
9．对于栈操作数据的原则是( B )。
A.先进先出 B.后进先出 C.后进后出 D.不分顺序
10.一个栈的输入序列为1,2,3,…,n，若输出序列的第一个元素是n，输出第i(1≤i≤n)个元素是( A )。
A.不确定 B.n-i+1 C. i D. n-i
11. 树的后序遍历序列和其转换的二叉树的哪种遍历序列相同( A )。
A.中序遍历 B.层次遍历 C.后序遍历 D.先序遍历
12.如果节点A有3个兄弟，B是A的双亲，则节点B的度为( D )。
A.1 B.2 C.3 D.4
13. 已知顺序表L中有n个数据元素，则读取第i个数据元素的平均时间复杂度为( B )。
A.O(n) B. O(1) C. O(n2) D. O(nlgn)
14.有10个叶子节点的二叉树有( B )个度为2的节点。
A.8 B.9 C.10 D.11
15. 一棵二叉树中总结点个数为200，其中单分支结点个数为19，其叶子结点个数为( B )。
A.90 B.91 C.92 D.93
16. 强连通分量是（ B ）的极大连通子图。
A.网 B.有向图 C.图 D.无向图
17.一棵二叉树的先序序列和后序序列正好相反，则该二叉树一定是( D )。
A.空树或只有一个节点 B.完全二叉树 C.满二叉树 D.高度等于其节点数
18.设有13个值，用它们组成一棵哈夫曼树，则哈夫曼树共有( D )个节点。
A.13 B.12 C.26 D.25
19.无向图的邻接矩阵是一个( A )。
A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵
20. 具有12个顶点,36条边的有向图，所有顶点度的和为( C )。
A.72 B.24 C.36 D.66
(1)简述栈和队列的相同点和不同点。
栈和队列都是线性表，都是限制了插入删除点的线性表。 共同点：都是只能在线性表的端点插入和删除 不同点：栈的插入和删除都在线性表的同一端点，该点统称栈顶，相应的，不能插入删除的另一个端点统称栈底，特性是后进先出 队列在线性表的表尾插入，表头删除，其特性是先进先出。
(2)简述哈夫曼树的构造方法。
哈夫曼树又称最优二叉树，大致分为四步：①初始化②找最小树，也就是选两个最小权值的树，并计算权值之和，最小的两个权值分别作为权值和的左右子树（左小右大）。③删除并加入，删除那两个最小的数，把新树加入到森林中。④判断，重复②③操作，直到森林里只剩下最后一棵树就是哈夫曼树。
(3)简述图的深度优先搜索算法。
①从图中找到某个顶点v0出发，首先访问v0.②找到刚访问过的顶点的第一个未被访问的邻接点，然后访问该顶点。以该顶点为新顶点，重复此步骤，直到刚访问过的顶点没有未被访问的邻接点为止。③返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点；然后执行步骤②
1.写出下列程序段的输出结果(栈的元素类型SElemType为char)。
(1) void main() {
Stack S;
char x,y;
InitStack(S);
x= ‘c’; y= ‘k’;
Push(S,x);
Push(S, ‘a’);
Push(S,y);
Pop(S,x);
Push(S, ‘t’);
Push(S,x);
Pop(S,x);
Push(S, ‘s’);
while(!StackEmpty(S)) { Pop(S,y); printf(y); } printf(x); }
解析：Push(S,x)后栈内为 c，Push(S, ‘a’)；Push(S,y)后栈内为cak; Pop(S,x)后出栈k, 此时x=k，栈内为 ca; Push(S, ‘t’)后栈内为 cat; Push(S,x)后栈内为catk; Pop(S,x)后出栈k,此时x=k,栈内为cat; Push(S, ‘s’)后，栈内为cats; Pop(S,y) printf(y)循环打印栈内元素stac , printf(x)打印出k ，故结果为stack
(2) root为根指针，对右图二叉树B，执行下列算法traversal(root)，试指出其输出结果。
struct node { char data; struct node *lchild, rchild; };
void traversal(struct node *root) {
if (root) {printf(“%c”, root->data);
traversal(root->lchild);
printf(“%c”, root->data);
traversal(root->rchild); } }
解析：这是“先根再左再根再右”，比前序遍历多打印各节点一次，输出结果为：ABCCEEBADFFDGG
一、假定用于通信的电文由8个字母A,B,C,D,E,F,G,H组成，各字母在电文中出现的频率为：5，25，4，7，9，12，30，8，试画出哈夫曼树并为这8个字母设计哈夫曼编码。（编码左0右1）
二、已知二维数组表示的图的邻接矩阵如图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。
三、写出下面树的先根遍历和后根遍历结果，并把它转换为二叉树
四、画出下图的邻接表存储结构
