数据结构理论

知识点： 性质1 非空二叉树上叶结点数等于双分支结点数加1。即：n0=n2+1。 性质2 非空二叉树上第i层上至多有2i-1个结点（i≥1）。

1、给定广义表求深度。 对于带头结点的广义表g，广义表深度的递归定义是它等于所有子表中表的最大深度加1。 int GLDepth(GLNode *g) //求广义表g的深度 { GLNode *g1; int maxd=0，dep; if (g->tag==0) return 0; //为原子时返回0 （第一种情况） g1=g->val.sublist; //g1指向第一个元素 if (g1==NULL) return 1; //为空表时返回1 （第二种情况） while (g1!=NULL) //遍历表中的每一个元素（第三种情况） { if (g1->tag==1) //元素为子表的情况 { dep=GLDepth(g1); //递归调用求出子表的深度 if (dep>maxd) //maxd为同层子表深度的最大值 maxd=dep; } g1=g1->link; //使g1指向下一个元素 } return(maxd+1); //返回表的深度 }

2、已知一棵二叉树的前序、中序序列或中序、后序序列获取相关信息 （哪些是左子树的结点、哪些是右子树的结点）。

3、图的邻接矩阵和度的关系（注意区分有向图、无向图）。 有向图：邻接矩阵数组第i行非零非无穷元素的个数是顶点i的出/入度 无向图： (1).邻接矩阵数组第i行非零非无穷元素的个数是顶点i的度 (2).无向图的邻接矩阵数组是一个对称矩阵

4、顺序栈的四要素。课本P80 (1).栈空条件：top=-1 (2).栈满条件：top=Maxsize-1 (3).进栈e操作：top++，将e放在top处 (4).出栈e操作：先从top出取出e，再top--

5、线索二叉树空指针如何处理。 (1).空指针需要被处理为指向树的前驱或后继节点的线索 (2).所有原本为空的右指针改为指向该节点在中序序列中的后继结点，所有原本为空的左指针改为指向该节点的中序序列的前驱结点。

1、考点：时间复杂度

image-ed57dd32

2、单链表的插入、删除。 插入操作语句： s->next = p->next; p->next = s;

删除操作语句： p->next = p->next->next;

3、给定循环队列的容量为20（序号从0到19），经过一系列的入队和出队运算后，有（1）front=9，rear=15; （2）front=15，rear=9；求两种情况循环队列中各有元素多少个。

第一种：L=（20＋15－9）% 20=6 第二种：L=（20＋9－15）% 20=14

4、已知二维数组A9×6,采用按行优先顺序存放，每个元素占2个存储单元，并 且第一个元素的存储地址为Loc(a1,1)=8，请求出Loc(a6,5)元素的存储地址。 Loc(a6,5)=Loc(a1,1)+[(6-1)*6+(5-1)]*2=8+(30+4)*2=76。

5、Prim算法和Kruskal算法构造最小生成树的过程。 课本P280 P284 Prim：找权最小的节点，在依次找其相邻节点中较小的权值，不能有回路 Kruskal：把所有权值进行排序，按权值排序顺序连接，不能有回路

6、考查知识点：哈夫曼树的构造（写最终构造的结果） 课本P232 找两个最小的值合并为一个值,把值加入集合中，再找两个最小的值..直到找完

1、已知一组关键字为: {25，18，46，2，53，39，32，4，74，67，60，11} （1）按表中的元素顺序依次插入到一棵初始为空的二叉排序树中，画出该二叉排序树。 （2）求在等概率的情况下查找成功的平均查找长度和查找不成功的平均查找长度。 （1）

image-183ffbd4

（2）

image-a377755a

Asl成功=sum(层数x每层节点数)/总结点数 Asl不成功=sum[(层数-1)x(每层的外部节点数)]/总外部节点数 （课本P327）

2、设初始排序表中有10个元素，其关键字序列为（6，8，7，9，0，1，3，2，4，5），请使用快速排序写出每趟排序的结果。（课本P380） 第一趟排序结果：{5 4 2 3 0 1 } 6 {9 7 8} 第二趟排序结果：{1 4 2 3 0} 5 6 {9 7 8} 第三趟排序结果：{0} 1 {2 3 4 } 5 6 {9 7 8} 第四趟排序结果：{0} 1 2 {3 4 } 5 6 {9 7 8} 第五趟排序结果：{0} 1 2 3 {4} 5 6 {9 7 8} 第六趟排序结果：{0} 1 2 3 {4} 5 6 {8 7} 9 第七趟排序结果：{0} 1 2 3 {4} 5 6 {7} 8 9