期末总结术语 第1篇
[i]取值 ;i>=0，如元素为1,2,3，，i=0,1,2
若带头结点，空表条件为L->next==NULL（L为头指针指向头结点永不为空）
若不带头结点，空表条件为L==NULL
栈空： //首xxx指针相同
栈满： //xxx首等于最大容量即为满
链栈一定是没有头结点，所以栈空的条件为：S==NULL
队空： //首xxx指针相同
//xxx指针指向的为最后一个元素的下一个地址(永远为空)，所以+1
队满：()%MAXSIZE==
队空：
由于串、数组、广义表的存储结构不是重点在这里就不再列出其存储结构
栈和队列除了链栈都有头xxx指针
期末总结术语 第2篇
1.满二叉树(最完美最满的状态) 完全二叉树(编号是连续的即最右面缺而且是最后一层缺)
完全二叉树度为1的结点个数为0或1
当前结点编号为i，它的左孩子编号为2i，右孩子为2i+1（从1开始时）
2.二叉树常用性质
3.二叉树遍历
4.二叉树线索化目的是加快查找结点的前驱或后继的速度。实质上就是遍历一次二叉树，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点
5.哈夫曼树即带权路径最短树，也称最优树。
树的带权路径长度=树根到各叶子结点的路径(树根到该结点要走几步)乘对应权值；通常记作 WPL=∑wi×li
6.哈夫曼编码是最优前缀编码(任一个编码都不是其他编码的前缀，便于通信减少数据传输)
哈夫曼树没有度为1的结点，且不一定是完全二叉树
7.树的存储结构有三种:双亲表示法、孩子表示法、孩子兄弟表示法,其中孩子兄弟表示法是最常用的表示法,任意一棵树都能通过孩子兄弟表示法转换为二叉树进行存储。
8.含有n个节点的二叉树共有(2n)!/(n!*(n+1)!) (常考3个节点共5种)
9.二叉树的高度是最大层次数(根节点为第一层)
10.树和二叉树均可以为空(注意树可为空是在xxx教材中可空，有的地方规定不能为空)
11.树的先序对应二叉树的先序，树的后序对应二叉树的中序(这里的二叉树一般指经孩子兄弟法转换的树)
12.哈弗曼树属于二叉树有左右子树之分
1.
答：n0= n2+1 n1=0或n1=1 n0+n1+n2=1001
**2.**注意题目说的是存储树，而树的存储结构中，孩子兄弟表示法又称二叉链表表示法
3.在一颗度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是______82_。
答：任何树中，分支数(度数之和)比节点数少1
题目中，分支数为20*4+10*3+1*2+10*1=122，所以有123个节点
度为0的节点为123-20-10-1-10=82
也可用公式n0=1*n2+2*n3+3*n4+1=1+2*10+3*20+1=82
**4.**设哈夫曼树中有199 个结点,则该哈夫曼树中有_100__个叶子结点
答：哈弗曼树没有度为1的结点,n0=n2+1,n0+n2=199,所以n0=100
**5.**一棵高度为4的完全二叉树至少有______8_个结点
答：前三层是满二叉树，最后一层只有一个即1+2+4+1=8
6.
后是左右根，所以C是根，根据中序(左根右)得到DEBA均是C左子根
根据后序的DABE得到E是DABE的根，再由中序的DEBA得到D是E的左字根，BA是E的右子根
后序是左右根是AB，而中序是左根右是BA，正好相反则当没有左时正好是右根和根右，即B是根A是右
7.一颗高度为h的完全二叉树至少有_____2h-1__个结点
答：最少的情况就是前h-1层是满的，第h层只有一个。
即2h-1-1(前h-1层)+1(第h层)
8.有n个结点，高度为n的二叉树的数目为_____2n-1__
答：结点数和高度相同，那么每层都只有一个结点。对于除根节点以外的结点都可能是左子树或右子树，即有两种可能，n-1个2相乘即为2n-1
9.二叉树遍历
注意中序先访问C的左而不是先访问W的左
10.树与森林之间的转换（左孩子右兄弟）
11.只要LTag为1表明线索为真即它肯定没左子树，为0表示一定有左子树
期末总结术语 第3篇
1.线性表的查找（静态查找表）
2.折半查找的判定树：把中间位置的值作为树根，左边和右边的记录作为根的左子树和右子树
判定树的中序遍历(左根右)得到的是有序的序列(判定树左子树比根节点小，右子树比根节点大)
3.加入监视哨(存待查元素) 免去每一步查找都要判断是否查找完的情况，只要读到监视哨就说明没查到
4.树表的查找（动态(可插入删除)查找表）
5.二叉排序树的删除：缺右补左，缺左补右，不缺左(左子树)中(中序)后(最后一个)
6.平衡调整：当插入一个结点破坏了平衡性就要调整
LL、LR等是对不平衡状态的描述
若是LL和RR型就把画圈的中间的那个掂起来（想想有重量，另外俩即自己落下去了）
若是LR和RL型就把画圈的最下面那个掂起来（另外俩也落到它两边）
若新插入结点在最小不平衡根节点的左(L)孩子的左(L)子树上即为LL型调整
若新插入结点在最小不平衡根节点的右®孩子的右左(L)子树上即为RL型调整
树（B树） m阶B-树，阶数其实就是树的度数 适合外存文件系统索引
树的查找 (类似于二叉树的查找，但是可以有三个或多个方向)
如查找关键字42。首先在根结点查找，因为42>30，则沿着根结点中指针p[1](下标从0开始)往右下走;因为39<42<45,则沿着子树根结点中指针p[1]往下走，在下层结点中查找关键字42成功，查找结束。
树是B-树的变型树，更适合做文件系统的索引。
10.散列表：根据给定的关键字计算关键字在表中的地址
负载(装载因子)：表中结点/表的空间，所以表越满越容易发生冲突
冲突：不相等的关键字计算出了相同的地址
同义词：发生冲突的两个关键字
11.散列表的构造方法
12.处理冲突的方法
1.折半查找求判定树
答：先找中间的值，(1+20)/2=10，所以1-9为10的左子树(比根小)，11-20为10的右子树。
比较时先和10比较，若比10小，则比较1-9，那先和谁比较呢，1-9中的中间值为(1+9)/2=5，所以先和5比较(即5和10相连)。如果还比5小，那就要和1-4比了，同样1-4先和谁比呢，1-4的中间值(1+4)/2=2，所以先和2比较(即2和5相连比5小在左边)，其他依次类推
查找为4的有1、3、6、8、11、13、16、19(依次和10,15,18,19比较所以4次)
2.用顺序表和单链表表示的有序表均可使用折半查找方法来提高查找速度。 （错）
答：单链表无法使用折半查找必须是顺序存储，因为要取中间值
3.二叉排序树序列判定
答：二叉排序树序列可理解为一个元素与二叉排序树比较的记录构成的序列。A中91后面是24说明待查元素X比91小所以后面是24，而24后面是94，说明X比24大，但是24前面已经比较过91了(说明已经肯定比91小了)，现在后面又来了个94显然是错的
4.
答：装填因子越大就越满越可能发生冲突。冲突少减少不必要的查找。
不能完全避免聚集(不是同义词却抢相同地址)只能减少但可避免二次聚集
个元素的表做顺序查找时,若查找每个元素的概率相同，则平均查找长度为_______(n+1)/2______
答：总查找次数为1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2
6.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用 （C）
A.顺序查找 B.折半查找 C.分块查找 D.哈希查找
答：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块， 就可以在该块内进行插入和删除运算。由于块内是无序的，故插入和删除比较容易，无需进行大量移动。如果线性表既要快速查找又经常动态变化，则可采用分块查找。严版P198
7.对22个记录的有序表作折半查找，当查找失败时，至少需要比较 ( 4 ) 次关键字。
答：4层的满二叉树有24-1=15个结点，5层的有31。题目是22个结点，所以是前4层是满二叉树，第五层不是满的，因此最少4次，最多5次。
8.下面关于 B- 和 B+ 树的叙述中，不正确的是（ C）。
A． B- 树和 B+ 树都是平衡的多叉树 B． B- 树和 B+ 树都可用于文件的索引结构
C． B- 树和 B+ 树都能有效地支持顺序检索 D． B- 树和 B+ 树都能有效地支持随机检索
答：B+树支持顺序(从最小的关键字叶子起从左到右)，而B-树因为其叶子结点互相没连接只支持从根节点起随机检索
9.假定对有序表: (3， 4，5，7，24，30，42，54，63，72，87，95) 进行折半查找, ①画出描述折半查找过程的判定树; ②若查找元素90，需依次与哪些元素比较? ③假定每个元素的查找概率相等，求查找成功时的平均查找长度。
答：1️⃣ 画判定树一般先画出坐标的判定树，再根据坐标填值即可，注意取下界及low和high的变化
2️⃣ 需要与30、63、87、95比较
3️⃣ 前3层：1+2*2+4*3=17 第四层：5*4=20
ASL=（17+20）/ 12 = 即总查找次数除总个数
10.设哈希函数 H(K) =3 K mod 11 ，哈希地址空间为 0～ 10 ，对关键字序列（ 32， 13 ，49， 24 ， 38， 21 ， 4， 12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度 ASLsucc 和 ASLunsucc 。 ① 线性探测法； ② 链地址法。
答：1️⃣ 散列地址就是若算的关键字为空就放里面，不为空就往后找
ASLsucc = （ 1+1+1+2+1+2+1+2 ） /8=11/8
ASLunsucc =（ 1+2+1+8+7+6+5+4+3+2+1 ） /11=40/11
因为最多成功查8个元素，所以查找成功时分母为8，分子就是每个元素查找的次数之和
而查找失败时可能计算得到的地址有11种，即分母为11，而关键字为空的查一次就知道失败了(要是有也不会为空)，若不为空要往后找直到找到第一个空元素(说明确实没有这个元素不然该放到这个空着的位置了)
2️⃣ 链地址就是要是地址被占了放后面挂着就行
ASLsucc = （ 1*5+2*3 ） /8=11/8 第一列查一次就知道了xxx要查两次
ASLunsucc =（ 1+2+1+2+3+1+3+1+3+1+1 ） /11=19/11
失败的情况：查一次若为空说明肯定不存在，若不为空继续向下查直到为空说明到底了查找失败(比如第二行需要查两次，第一次查到为4，第二次查到了空，记住不是查一次就行)
总结：查找成功看位置，查找失败就找空
11.适宜于对动态查找表进行高效率查找的组织结构是 （C）
A.有序表 B. 分块有序表 C. 三叉排序表 D. 线性
答：如果线性表既要快速查找又要经常动态变化，则可采用分块查找。而这里说的是动态查找表，分块查找属于静态查找表。动态即要进行修改。有序表和线性不适合修改操作