1、 带头结点的单链表H为空的条件是：head->next=NULL
2、 设r指向单链表的某个有后继的结点，要删除该结点的后继结
点，需要执行的三条语句：
q=r->next; r->next=r->next->next ;free(q).
3、 用一维数组存放一个完全二叉树的结点 ABCDEFGHI, 则中序遍
历该二叉树的结点序列为 HDIBEAFCG 4、 共有35个结点的完全二叉树的高度是 6 5、 用 循环 链表表示存储线性表，可以从表中任一点出发都能
访问到所有结点。
6、 若以[0…maxsize] 为一个顺序存储的栈，变量top表示下一个要插
入的位置，则栈满的条件是 top= =maxsize 7、由树转换成二叉树时，其根结点的 右 子树总是空的。
8、若要对某二叉排序树进行遍历，保证输出的结点序列按关键字的值递增次序排列，应对该二叉树采 中序 遍历法。9、排序目的 为了提高对数据 检索 操作的效率。
10、有15个元素的有序表A[0…14]作二分检索，在检索其等于A[10]的元素时，被比较的元素的下标依次是 7—11—9—1011、在一个单链表中P所指结点之后插入一个由指针S所指结点，应执行s->next= p->next ;和p->next=s 的操作。
12、大多数排序算法都有两个基本操作： 比较 和移动。
13、稀疏矩阵常用的压缩存储方法是 三元组法 和十字链表法。14、设有稠密图G，则采用 邻接矩阵 存储结构较节省空间。15、二叉树中每个结点最多有 两 子树
16、在队列中存取数据元素的原则为 先进先出 17、在栈中存取数据元素的原则为 后进先出 18、用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i 的 出度 19、对具有n个顶点的无向图，其生成树有且公仅有 n-1 条边。
20、拓扑排序输出的顶点数小于有向图的顶点数，则该图一定存在 环 二、选择题
1、无向图G=（V，E），其中：V={a,b,c,d,e,f}, E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历，得到的顶点序列正确的是 C A） a b e c d f B) a c f e b d C) a e b c f d D) a d e f c b
2、下列各项中属于线性表的是 C A) 由n个实数组成的集合 B) 由所有整数组成的序列
C) 由100个英文字符组成的序列 D) 数组3、线性表的长度 是指 C A) 顺序存储结构中数组所占的空间大小B)链表中所有结点占用的空间大小C)线性表中元素的个数
D)所能存储的最大的数据元素的个数
4、一个序列中有10000个元素，若只想得到其中前10个元素，最好采用 C 方法
A)快速排序 B) 插入排序C)堆排序 D) 二路归并排序
5、空的带头结点的循环单链表head 的尾结点（由p所指向）满足 C A)p->next==null B) p== nullC)p->next==head D) p== head
6、一个具有5层的满二叉树所包含的结点个数为 A A) 31 B) 15 C) 32 D) 63
7、排序的趟数与排序元素的原始状态有关的排序方法是 A A)冒泡排序 B) 快速排序 C) 插入排序 D) 选择排序
8、对于任何一棵二叉树T，如果其叶子结点数为n0,度为2的结点数为n2,则 A A)n0=n2+1 B) n2=n0+1 C) n0=2n2+1 D) n2=2n0+1
9、任何一棵二叉树的叶结点在其先序、中序和后序遍历序列中的相对位置 C A) 肯定发生变化 B)有时发生变化C)肯定不发生变化 D) 无法确定
10、顺序循环队列中(数组的大小为6)，队头指示front 和队尾指示rear 的值分别为3和0，当队列中删除1个元素、再插入2个元素后，front 和rear的值分别为 D A)5 和1 B) 2 和4 C) 1 和5 D) 4 和2
11、下列序列中， A 是执行第一趟快速排序后得到的序列A)[da,ax,eb,bb,bb] ff [ha,gc]B)[gc,ax,eb,cd,bb] ff [da,ha]C)[cd,eb,ax,dq] ff [ha,gc,bb]D)[ax,bb,cd,da] ff [eb,gc,ha]
12、在一个带权连通图G中，权值最小的边一定包含在G的 D 中A) 深度优先生成树 B) 广度优先生成树C) 生成森林中 D) 最小生成树
13、静态查找表与动态查找表两者的根本差别在于 C 。A)逻辑结构不同 B) 存储结构不同
C)施加的操作不同 D) 数据元素类型不同
14、表长为n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为 C A) (n-1)/2 B) (n+1)/2 C) n/2 D) (n-1)/2
15、在有n个结点的二叉链表中，值为非空的链域的个数为 A A) n-1 B) 2n-1 C) n+1 D) 2n+1
16、设数据A[0..10,1..10]中任何一元素A[i , j ]均占存储器3个单元，从首地址2000开始连续存放在主存中，数组按行存放时，元素A[8，6]的地址是 A A)2255 B) 2289 C) 2014 D) 2148
17、已知含有10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下，查找成功的平均查找长度等于 C A) 1.0 B) 3.4 C) 2.9 D) 5.5
18、下列关键字序列中 C 是堆 D是大顶堆A) （10，60，20，50，30，26，35，40）B) （20，60，50，40，30，10，8，72）
C) （10，30，20，50，40，26，35，60） 是小顶堆，书上P249第10行的堆条件
D) （70，40，36，30，20，16，28，10）19、用链表表示线性表的优点是 C 。
A)便于随机存取 B) 花费的存储空间较顺序存储少
C)便于插入和删除 D) 数据元素的物理顺序与逻辑顺序相同
20、G是一个无向连通图，共有28条边，则该图至少有 C 个顶点A) 5 B) 7 C) 8 D) 9三、简答题
1、设有一个栈,其入栈操作为S,出栈操作为X，输入数据的序列为
1,2,3,4,5,6,7, 请判断下面的输出序列是否可得到，如果可以，请给出栈的操作序列。
4 5 1 3 2 7 6 3 2 5 4 7 6 14513276 不能得到
3254761 可以。操作如下
S1 S2 S3 X3 X2 S4 S5 X5 X4 S6 S7 X7 X6 X1
(我把入栈和出栈的相应值写出来了 S1表示1入栈)2、请描述所有满足下列条件的二叉树的特征。
a) 它们在先序遍历和中序遍历时，得到的结点访问序列相同；
b) 它们在后序遍历和中序遍历时，得到的结点访问序列相同c) 它们在先序遍历和后序遍历时，得到的结点访问序列相同答：
a)所有结点只有右孩子或为空的情况下先序遍历和中序遍历时，得到的结点访问序列相同
b)所有结点只有左孩子或为空的情况下先序遍历和中序遍历时，得到的结点访问序列相同
c)空二叉树或仅有一个无孩子的根结点 的情况下在先序遍历和后序遍历时，得到的结点访问序列相同
3、给出一组初始待排序关键字T=（27，46，5，18，16，51，32，26），请分别写出用下列算法从小到大排序时第一趟结束时的序列：1）直接选择排序 2）快速排序答：
1） 直接选择排序：
（5，46，27，18，16，51，32，26） （最小一个数值跟第一个数值交换）2）快速排序
（26，16，5，18，27，51，32，46） 书上P254页 大至过程如下（27，46，5，18，16，51，32，26），
（，，，，，，32， ），
（26， 5，18，16，51，32，46）
（，，，18， ，51，32，46）
（26，16，5，18，27，51，32，46）
4、给出一组关键字：29，18，25，47，58，12，51，10， 分别写出按堆排序进行排序时的变化过程：先建成一个堆，然后从堆顶取下一个元素后，再给出调整后的堆。
建成的堆为
取走10后的堆：
5、有一个无向图的顶点集合为{a,b,c,d,e},其邻接矩阵如下所示。画出该无向图及其的邻接表结构。
1a 24
2b13 3c25
4d15
5e34
0 1 0 1 0 1 0 1 0 0 0 1 0 0 11 0 0 0 10 0 1 1 0无向图如下a b d c e
6、 假设以数组S[0..m-1]作为循环队列的存储结构，同时设变量front
和rear分别指向队头元素的前一个位置和队尾元素位置。试分别给出判别队列满和队列空的条件，并写出计算队列元素个数的方法
答 队列满的条件为： rear+1=front 队列为空的条件为：front=rear
算队列元素个数 (rear-front+m)% m
四、设计题：
1、设有8个字母，他们出现的频率分别为：5，29，7，8，14，23，3，11 ，请为这8个字母设计相应的哈夫曼编码设它们分别代表字母 a b c d e f g h 书上P 221
根据左子向为零，右向这1，这样编码就出来了a ：0110 b: 10c:1110d:1111e:110f:00g:0111h:010
2、已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ，试画出这棵二叉树
3、试求按关键字序列（55，31，11，37，46，73，63，2，7）插入生成二叉排序树，并给出在等 概率情况下查找成功时的平均查找长度。然后画出删除31后的二叉排序树
平均查找长度 =(1*1+2*2+3*2+4*2+5*1)/8=24/8=3删除31后的二叉排序树为：
4、对于有向无环图，请完成以下两个任务：（1） 叙述求拓扑有序序列的步骤；
（2）写出下图的四个不同的拓扑有序序列
②
① ⑦ ⑧ ④
③ ⑥ ⑤
步骤：1、找出任意一个没有前趋的顶点
2、删除该顶点以及所以从该顶点发出的有向边
3、重复1 2 直到所有顶点都被输出或找不到没有前趋的顶点。四种序列：1 2 3 4 7 8 5 6 1 3 2 4 5 7 6 8 1 2 3 5 6 4 7 8 1 2 3 4 5 7 8 6
5、表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出你的一种选择方案
①②④③⑤⑥
16192111331418656
4. 下面这棵二叉树具有如下性质：除叶子结点外，每个结点的值都大于其左子树上的一切结点的值，并小于等于右子树上的一切结点的值。现把9个数1,2,3,…,8,9填入下图所示的二叉树的9个结点中，并使之具有上述性质。
1、 算法填空题
1. 下面的是实现在二叉排序树中插入一个关键字的值为kx的结点的算法，先对kx进行检索，若查找成功，则不插入，若失败，则插入相应位置，保持其二叉排序树的特性。试在算法中的空白处填上正确的内容，完成该算法typedef struct node{datatype key;
struct node *lchild,*rchild;}bsnode,*bstree;
void InsertBstree(bstree *t, datatype kx){bstree f, p=*t;While( P ){if(x==p→key) return; f=p;
if(kx p=(bsnode *)malloc(sizeof(bsnode));p→key= x ;p→lchild=NULL; p→rchild= null ;if(!(*t)) *t=p; else if(kx 2. 下面的算法是利用二分法检索的思想，在一个长度为n的有序表中插入一个元素x，并保持表的有序性。试在算法中的空白处填上正确的内容，完成该运算。#define maxsize 100typedef struct{ int data[maxsize+1];int len;}seqlist; void insert(seqlist r, int x) {int low=1,high=r.len,mid,i,find=0;While(low If (low>high) {for(i=r.len;i>=low;i--) r[i+1] = r[i] ;r[low]= x ;}} 2、 算法设计题 1. 请编写算法求一棵给定二叉树叶子结点的个数(采用二叉链表存储结构)。typedef int datatype;typedef struct node{datatype data; struct node *lchild,rchild;}bintnode; 2. 已知带头结点的单链表head中的结点按整数值递增排列，请设计算法讲值为x的结点插入表head中，使得表head仍然有序。 typedef int datatype;typedef struct link_node{datatype data; struct link_node *next;}node; 因篇幅问题不能全部显示，请点此查看更多更全内容