华东理工大学网络学院《数据结构》------ch6树和二叉树、ch8查找班级学号姓名成绩一、名词解释（每个2分，共10分）1.结点的度2.哈夫曼树3.线索化4.二叉树5.冲突答：1结点的度：结点的子树的个数。2哈夫曼树：带权路径长度WPL最小的二叉树称为哈夫曼树或者最优二叉树。3线索化：对二叉树以某种次序进行遍历并且加以线索的过程。4二叉树：满足条件（1）每个结点的度都不大于2；（2）每个结点的孩子结点次序不能任意颠倒；这样的树形结构称为二叉树。5冲突：不同的关键字可能得到同一个哈希地址，这种现象称为冲突。二、填空题（每空1分，共20分）1.由树转换为二叉树，其根节点的右子树总是为空。2.深度为6（根层次为1）的二叉树至多有26–1个结点。3.含17个结点的二叉树的深度是5（设根结点的深度为1）。4.一棵高度为h的满二叉树共有2h-1个终端结点。5.已知一棵完全二叉树的第5层有3个结点，其叶子结点数是9。6.对线性表进行二分查找时，要求线性表必须以.顺序方式存储，且结点按关键字有序排列。7.哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的方法8.在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法。9.在分块查找方法中，首先查找索引（表），然后再查找相应的块。10.由树转换成的二叉树里，一个结点N的左孩子是N在原树里对应结点的最左子结点，而N的右孩子是它在原树里对应结点的最邻近的右兄弟。11.在哈希存储中，装填因子α的值越大，则发生冲突的可能性就越大；α的值越小，则发生冲突的可能性就越小。12.N个结点的二叉树采用二叉链表存放，共有空链域个数为n+1。13.树是结点的有限集合，它有0个或1个根结点，记为T。其余的结点分成为m（m≥0）个互不相交的集合T1，T2，…，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1≤i≤m）。一个结点的子树个数为该结点的度。三、判断正误（对的用”T”表示，错误的用”F”表示。每小题1分，共10分）1.(T)具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。2.(F)用一维数组存储二叉树时，总是以前序遍历存储节点。3.(T)判断线索二叉树中某结点p有左孩子的条件是p->ltag=0。4.(T）深度为K的完全二叉树至少有2K-1个结点。5.(F)折半查找适用于有序表，包括有序的顺序表和有序的链表。6.(F）哈夫曼树中没有度为1的结点，所以必为满二叉树。7.(F)哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。8.(T）若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。9.(F）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值；若它的右子树非空，则根结点的值大于其右孩子的值。10.(F)索引顺序表的特点是块间可无序，但块内一定要有序。四、单项选择题（每小题2分，共20分）1.对包含n个元素的哈希表进行查找，平均查找长度为：DAO(log2n)BO(n)CO(nlog2n)D不直接依赖于n2.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：CA48B49C50D513．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：CA3B2C4D54.设一哈希表表长M为100，用除留余数法构造哈希函数，即H（K）=KMODP（P<=M）,为使函数具有较好性能，P应选CA100B99C97D895.由3个结点所构成的树有B种形态。Ａ1Ｂ2Ｃ3Ｄ46.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：AA98B99C50D487.平衡二叉排序树具有的特点是左子树与右子树的高度差的绝对值不超过D。A–1B1C0D18.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：CA2B3C4D59.如果二叉树中某结点p->rtag=1，则在对该二叉树按照某种次序进行线索化时，该指针域指向该结点的D。A左孩子B右孩子C遍历前驱D遍历后继10.设有100个元素，用折半查找法进行查找时，最大比较次数为C次。A5B6C7D8五、简答题（每小题5分，共10分）1.在哈希表中，发...
