若将和此序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于(或不小于)其左右孩子结点的值。 由此，若序列{Kl，K2，…，Kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
（课本P227）二叉排序树又称二元查找树（Binary Search Tree），或者是一棵空树，或者是具有下列性质的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）它的左、右子树也分别为二叉排序树。
3、快速分类法的基本思想是什么?
（课本P273）快速排序是对起泡排序的一种改进。它的基本思想是，通过一趟
排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？
1 7 2 5 3 8 6 4 4 5 1 3 5 2 4 3
下一条边应在（5，1），（5，6），（4，6），（4，3）中选取，根据MST性质应该选取（4，6）。
5、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？ 正确
6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。 0000，0001，001，01，1
7、对于一个队列，若入队的顺序为a,b,c, 则所有可能的出队序列是什么？ a,b,c
8、已知一个图如下，试画出其逆邻接链表。
1 2 3 4
注意：课本P164，逆邻接表是为了便于确定顶点的入度。
9、若一个栈的输入序列是1,2,3??，n, 其输出序列为p1,p2,??pn, 若 p1=n，则pi为多少？ Pi= n-i+1
10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？ 正确
11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。 5种
12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？
a c b e f d
不行，不行
根据深度优先和广度优先遍历的规则
13、栈的存储方式有哪两种？ 顺序存储结构和链式存储结构
14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中： 单链表和单循环链表的结点结构为 date next 双向链表的结点结构为
prior date next
1.单链表不行，因为单链表没有办法得到其前驱； 2. 单循环链表可以，假设链表的元素大于等于2：
struct Node {
Node * next; int data; };
循环链表 Node * list; Node *pnode = p;
while(pnode->next != p) {
pnode = pnode->next; }
//找到其前驱了
int tmp = pnode->data; pnode->data = p->data; p->data->tmp;
3.双向链表可以，假设链表的元素大于等于2，且p不为链表头。 struct Node { Node * next; Node * pre; int data; }
双向链表list; Node *pnode = p; if(p->pre != NULL) {
int tmp = p->data;
p->data = p->pre->data; p->pre->data = tmp; }
15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
（1）根据哈夫曼编码的规则画树。（课本P146） （2）（具体计算方法见课本P146）该哈夫曼树的带权路径长度：253
16、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。 （期中试题）顺序存储
17、内存中一片连续空间（不妨假设地址从1到m）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。 （期中试题）
18、设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。 （期中试题）
19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。
从上到下，从左到右依次为：5，1，9，4，6，2，7，3，8
20、 试证明：若借助栈由输入序列1,2,?,n得到输出序列为P1,P2,?,Pn（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 如果i i进栈,i出栈,j进栈,j出栈,k进栈,k出栈.此时具有最小值的排在最前面pi位置,具有中间值的排在其后pj位置,具有最大值的排在pk位置,有pi < pj < pk, 不可能出现pj < pk < pi的情形; i进栈,i出栈,j进栈,k进栈,k出栈,j出栈.此时具有最小值的排在最前面pi位置,具有最大值的排在pj位置,具有中间值的排在最后pk位置,有pi < pk < pj , 不可能出现pj< pk < pi的情形; i进栈,j进栈,j出栈,i出栈,k进栈,k出栈.此时具有中间值的排在最前面pi位置,具有最小值的排在其后pj位置,有pj < pi < pk, 不可能出现pj < pk < pi的情形; i进栈,j进栈,j出栈,k进栈,k出栈,i出栈.此时具有中间值的排在最前面pi 位置,具有最大值的排在其后pj位置,具有最小值的排在pk位置,有pk < pi < pj, 也不可能出现pj < pk < pi的情形; i进栈,j进栈,k进栈,k出栈,j出栈,i出栈.此时具有最大值的排在最前面pi 位置,具有中间值的排在其后pj位置,具有最小值的排在pk位置,有pk < pj < pi, 也不可能出现pj < pk < pi的情形. 四 算法阅读 1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); } 该算法被调用后得到的输出结果为： （期中试题） 2、 void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ （期中试题） 3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) ListInsert(La,1,a[i]); （2）ListDelete(La,1,e); ListInsert(La,ListLength(La)+1,e); （3）ClearList(La); For (i=0;i<5;i++) ListInsert(La,i+1,a[i]); （期中试题） 4、int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; }