结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。（N） 9．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的(N)。
10．一个有向图的邻接表和逆邻接表中表结点的个数一定相等（Y） ①（101，88，46，70，34，39，45，58，66，10）是堆（Y）； ② 将一棵树转换成二叉树后，根结点没有左子树（N）；
③ 用二叉树的前序遍历和中序遍历可以导出树的后序遍历（Y）；
④ 即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同(N)；
⑤ 哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离很较近（Y）。 11、表示一个有1000个顶点、1000条边的有向图的邻接矩阵有1000000个矩阵元素，是否稀疏矩阵 是
12.（ N）串长度是指串中不同字符的个数。
13.（ N）数组可以看成是线性结构的一种推广，因此可以对它进行插入、删除等运算。 14.（ Y）在顺序表中取出第i个元素所花费的时间与i成正比。 15. ( Y)在栈满的情况下不能作进栈的运算，否则产生“上溢”。
16.（ Y二路归并排序的核心操作是将两个有序序列归并为一个有序序列。
17.（ N ）对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。
18.（ Y）一个有向图的邻接表和逆邻接表中的结点个数一定相等。
19（ Y）在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的个数有关，而且与每一块中的元素个数有关。
12（ N）叉排序树或者是一棵空树，或者 是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值小于其右孩子的值。 21（ N）执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。
三、填空题
1. 在带有头结点的单链表L中，第一个元素结点的指针是___L->next________。
2. 在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句： s->next=p; s->prior=p->prior; p->prior=s; _s->prior->next_______________=s;
3. 设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___top==0__________，栈为满的条件是________top==maxsize_____________。 4. 具有100个结点的完全二叉树的深度为______7__________________。
5. 有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的____出度_______________。
6．r指向单链表的最后一个结点，要在最后一个结点之后插入e所指的结点，需执行的三条语句是r->next=s; r=s；r—>next=NULL。
7在单链表中，指针p所指结点为最后一个结点的条件是p->next==null
8设一个链栈的栈顶指针是ls，栈中结点格式为info;link;栈空的条件是 ls==null。如果栈不为空，则退栈操作为p=ls； ls=ls->link；free(p)。
9已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有12个叶子结点。
10．图有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 双亲表示法。
11．n个顶点的连通图的生成树有n-1条边。
12．一个有向图G中若有弧
13．设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序 方法对其进行排序(按递增顺序)：冒泡最省时间，快速最费时间。
14。下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。 typedef struct pnode }int key；
struct node *left，*right； }
void searchinsert(int x;pnode t) /*t为二叉排序树根结点的指针*/ {if (t==null)
{p=malloc(size); p->key=x;p->left=null; p->right=null;t=p; } else
if (x
20．G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是连通图。
21．如果一个有向图中没有环，则该图的全部结点可以排成一个拓扑序列。 22．深度为8(根的层次号为1)的满二叉树有8 个叶子结点。
23．将一棵有100个结点的完全二叉树按层编号，则编号为49的结Ⅸ，其双亲PARENT(X) 的编号为 24 。
24．设有一个链队，结点结构为data;next；front为队头指针，rear为队尾指针，当执行入队操作时需执行下列语句：malloc(p);p->data=x;p->next=null;rear->next=p;rear=p; 25.在散列法中，元素个数 越多，发生冲突的可能性越大。
26．在带有头结点的单链表L中，第一个元素结点的指针是 L->next。 27．在顺序文件中，存取第i个记录，必须先存取 第I-1号元素。
28．设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是 top==0，栈为满的条件是 top==maxsize
29．具有64个结点的完全二叉树的深度为 7
30．有向图G用邻接矩阵A[1..N,1..N]存储，其第I列的所有元素之和等于顶点I的入度。
31．在双循环链表中，若要在指针P所指结点前插人指针S所指的结点，则需执行下列语句 s->next=p;s->prior=p->prior;p->prior=s;s->prior->next=p;
32．对于下图所示二叉树；按前序遍历所得到的结点序列A，B，D，E，H，C，F．
33．分别采用堆排序、快速排序、冒泡排序和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是冒泡排序 ，最费时间的是快速算法
34. 对于下面的二叉树，按中序遍历所得到的结点序列为_______________。 35. 对下图所示的网，执行prim算法可得到最小生成树，试在下表的空白处填上适当的内容，以说明该算法的执行过程。
1
1 5
5 3
4 2
2
顶点 1 4
3 （2，3） 4 （2，3） 4 4 （U，V） （2，1） 代价 ∞ （U，V） 代价 （U，V） （3，1） 1 代价 U {2} V {1，3，4} {1，3} {1} （2，4） 2 {2，4} {2，4，3} （U，V） {2，4，3，1} 代价
36、设广义表L＝(（），（）) 则head(L)是 () ；tail(L)是 (())；L的长度是 2 ；深度是 2
37、在n个记录的有序顺序表中进行折半查找，最大的比较次数是logn 。
在如图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_S->NEXT->NEXT=P->NEXT_和_P->NEXT=S__。
38．串S=″I am a worker″的长度是_14_______。
假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为__55____。
39．在n个结点的线索二叉链表中，有___n+1_个线索指针。
40．对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为_48,44,52,63,80,91___。
二、应用题
1． 已知二叉树的后跟序列和中根序列如下，构造出该二叉树。
后根序列：ABCDEFG 中根序列：ACBGEDF
2． 有一组关键码序列{8，9，5，3，7，2，1}，分别采用冒泡排序、快速排序、直接选择
排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中请选择各种排序第一趟排序的结果。 冒泡排序：E 快速排序：A 直接选择排序：B 直接插入排序：C 二路归并：F
A．{1，2，5，3，7，8，9} B．{1，9，5，3，7，2，8} C．{9，8，5，3，7，2，1} D．{9，5，3，7，2，1，8} E．{8，5，3，7，2，1，9} F．{8，9，3，5，2，7，1} 3． 设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，
<6，5>，<5，4>，<6，4>}，请写出图G中顶点的所有拓扑序列。 4． 设图G=（V，E），V={1，2，3，4，5，6}，E={<1，2>，<1，3>，<2，5>，<3，6>，
<6，5>，<5，4>，<6，4>}，请画出其邻接表，并说明每个顶点的入度和出度。 5． 对如下所示的二叉树，画出其顺序存储结构。
6． 已知图G的邻接表如图所示，画出图G的所有连通分量。
现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，在下面
的选项中选择一个编号，说明这5个结点的哈夫曼编码。（2）
（1） （2） （3） （4）
A：1，B：001，C：010，D：011，E：000 A：000，B：001，C：010，D：011，E：1 A：001，B：011，C：010，D：000，E：1 A：000，B：1，C：010，D：011，E： 001
7． 已知一表为{23，45，24，6，57，45，35}，按表中顺序依次插入初始为空的二叉排序
树，要求画出建立的二叉排序树。
设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求其查找成功时的平均查找长度。 答：二叉排序树: (3分)
=2.5 (2分)
平均查找长度= (1+2×2+3×2+4) * 1/6
8． 对如下所示的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修路的
代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。 9． 设有n个元素的有序表为A，K为一个给定的值，填空完成二分查找算法： binsrch(a,n,k) int a[],k;
{ int low,hig,mid; low=0; hig=n;
while(low<=hig)
{ mid=(low+hig)/2; if(k
if(a[mid]==k)
printf(\ else
printf(\}
10．已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：
#define MaxNum 50//图的最大顶点数
#define INFINITY INT_MAX //INT_MAX为最大整数，表示∞
typedef struct{
char vexs[MaxNum];//字符类型的顶点表
int edges[MaxNum][MaxMum];//权值为整型的邻接矩阵
int n,e;//图中当前的顶点数和边数