10设有一棵深度为5的完全二叉树 ， 第5层上 。

8、有3个结点 ， 该树共有_个结点 。
（根所在结点为第1层） 1120个元素进行冒泡法排序 ， 通常需要进行19趟冒泡 ,其中第10趟冒泡共需要进行 次元素间的比较 。
12 一棵二叉树中每一个非叶结点的度数都为2 ， 共有10个非叶结点 ， 则该树共有 _ 个结点 。
13一棵有19个结点的二叉树,采用链式结构存储,该树结构中有 _ 个指针 域为空 。
14. 序列3,1,7,18,6,9,13,12经一趟归并排序的结果为。
15中序遍历一棵 树可得到一个有序序列 。
16 一棵有16个叶结点的哈夫曼树 ， 则该树共有_个非叶结点 。
17二叉排序树插入操作中,新插入的结点总是以树的 结点被插入的 18遍历二叉排序树可得到一个 。

9、有序序列 。
19. 广义表的 a , d,a ,b , h , e , i ,j,k 深度是。
20. 广义表 f , h , a ,b, d, c , d , e , i ,j,k的长度是。
21. 序列4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用归并排序算法升序,经一趟归并后,序列的结果 _ _ 。
22. 广义表的 h ,c ， g, a , a ,b , d , e , i ,j,k深度是 _ 。
23. 字符串a1teijing, a2 tef , a3 teifang, a4“tefi最小的 是。
24设有串p1”ABADF”,P2”ABAFD” 。

10、 ， P3”ABADFA”P4”ABAF”, 四个串中最 小的是。
三、综合题 1设查找表为 序号1234567891011序列4121819375565778586117 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示）（2）说明成功查找到元素86需要经过多少次比较（3）求在等概率条件下 ， 成功查找的平均比较次数2.（1）设有数据集合50 ， 39 ， 17 ， 83 ， 111 ， 14 ， 65 ， 13 ， 91 ， 102 ， 49 ， 依次取 集合中各数据构造一棵二叉排序树 。
2 一组记录的关键字序列为（6 ， 9 ， 7 ， 4 ， 5 ， 8） ， 利用堆排序（堆顶元 素 是最小元素）的方法建立初始堆 。
要求用完全二叉树表示3. 。

11、1 一组记录的关键字序列为（26 ， 59 ， 36 ， 18 ， 20 ， 25） ， 给出利用堆排序（堆顶 元素是最小元素）的方法建立的初始堆（要求以完全二叉树描述 ） 。
2 对关键字序列26,59,36,18,20,64采用快速排序 ， 给出以第一个关键字为分割 元素 ， 经过一次划分后的结果 。
4. 1 如下表为一个长度为10的有序表 ， 给出按折半查找对该表进行查找的判定树 2 按折半查找对该表进行查找 ， 求在等概率情况下查找成功的平均比较次数 。
为了成功查找72 ,给出元素的比较次数 。
序号12345678910序列2349391825607284555951 以1 ， 2 ， 3， 6 ， 7 ， 8作为叶结点的权 ， 构造一棵哈夫曼树 2 。

12、 给出具有相应权重值的叶结点的哈夫曼编码 。
四、程序填空题1以下函数在a0到an-1中 ， 用折半查找算法查找关键字等于k的记录 ， 查找成功返回该记录的下标 ， 失败时返回-1 ， 完成程序中的空格typedef struct int key;
NODE;
int Binary_SearchNODE a , int n, int k int low, mid, high;
low0;
highn-1;
while1 mid2 ifamid.keyk return 3;
else if 4 lowmid1;
else 5;
return -1 1.1 lowhigh 2 lowhigh/2 3 mid;
4 ami 。

【数据结构|数据结构(本)期末综合练习】13、d.keyk 5 highmid-1;
2.设线性表以不带头结点的单向链表存储 ， 链表头指针为head,以下程序的功能是 输出链表中各结点中的数据域data 。
完成程序中空格部分 。
define NULL 0void mainNODE *head ,*p ;
phead;
/*p为工作指针*/ do printf“dn”, _1_;
_2_ ;
while_3_;
2 （1）p-data （2）pp-next （3）pNULL3.以下程序是前序遍历二叉树的递归算法的程序 ， 完成程序中空格部分（树结构中左、 右指针域分别为left和right ， 数据域data为字符型 ， BT指向根结点） 。
void In 。

14、order struct BTreeNode *BT ifBTNULL 1;
2;
InorderBT right;
利用上述程序对右图进行前序遍历 ， 结果是3;
3. （1） printf“c”,BT-data （2）InorderBT-left （3）a b d f e c4.以下程序是后序遍历二叉树的递归算法的程序 ， 完成程序中空格部分（树结构中左、 右指针域分别为left和right ， 数据域data为字符型 ， BT指向根结点） 。
完成程序中 空格部分 。
void Inorder struct BTreeNode *BT if BTNULL InorderBT-left;
_1_ _2_ 4 （ 。

15、1） InorderBT-right （2） printf“c”,BT-data 5. 顺序查找算法如下, 完成程序中空格部分 。
int search NODE a ,int n , int k/* 在a0,a1an-1,中查找关键字等于k的记录 ， 查找成功返回记录的下标 ， 失败时返回 -1*/ int i0;
while i n ai.key _1_ _2_ if _3 return i;
else return -1;

声明：本文是由网友投稿，文中所阐述的观点不代表本网的立场。

来源：(未知)

【傻大方】网址：/a/2020/1125/00122566.html

标题：数据结构|数据结构(本)期末综合练习( 二 )