二叉排序树构造过程_二叉树排序算法原理

数据结构精品课程 　　一、判断题：（10 分） 　　  正确在括号内打√，错误打× 　　 (  ) 1.在单链表中，头结点是必不可少的。 　　（  ）2．如果一个二叉树中没有度为1的结点，则必为满二叉树。 　　 (  ) 3. 循环链表的结点结构与单链表的结点结构完全相同，只是结点间的连接方式不同。 　　 (  ) 4. 顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 　　 (  ) 5. 在一个大根堆中，最小素不一定在最后。 　　 (  ) 6. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 　　（  ）7. 在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。 　　（  ）8. 内部排序是指排序过程在内存中进行的排序。 　　（  ）9. 拓扑排序是指结点的值是有序排列。 　　 (  )10. AOE网所表示的工程至少所需的时间等于从源点到汇点的最长路径的长度。 　　  　　二、选择题(30分, 每题1.5分) 　　1．有一个含头结点的单链表，头指针为head,  则判断其是否为空的条件为：________________ 　　   A． head=NIL     B. head^.next=NIL      C.  head^.next=head    D. head<>NIL 　　或 A． head==NULL  B. Head->next==NULL  C.  head->next==head  D. Head!=NULL 　　2．非空的循环单链表head的尾指针p满足______________。 　　   A.  p^.next=NIL      B.  p=NIL         C.  p^.next=head      D.  p=head 　　或 A.  p->next=NULL    B.  p==NULL     C.  P->next==head     D.  p==head 　　3．链表不具有的特点是        。 　　   A、可随机访问任一个素                        B、插入删除不需要移动素 　　   C、不必事先估计存储空间                        D、所需空间与线性表的长度成正比 　　4．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用        存储方式最节省运算时间。 　　   A、单链表              B、双链表            C、单循环链表     D、带头结点的双循环链表 　　5．若线性表最常用的操作是存取第i个素及其前驱的值，则采用        存储方式节省时间。 　　   A、单链表              B、双链表            C、单循环链表            D、顺序表 　　6．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能的是        。 　　    A、 A，B，C，D                                    B、D，C，B，A 　　C、 A，C，D，B                                    D、D，A，B，C 　　7．一个队列的入队序列是1，2，3，4，则队列的输出序列是        。 　　   A、4，3，2，1              B、1，2，3，4     C、1，4，3，2     D、3，2，4，1 　　8．设循环队列中数组的下标范围是1~n，其头尾指针分别为f，r，若队列中素个数为        。 　　   A、r-f                    B 、r-f+1             C、（r-f+1）mod n    D、（r-f+n）mod n 　　9．串是        。 　　   A、不少于一个字母的序列                        B、任意个字母的序列 　　   C、不少于一个字符的序列                        D、有限个字符的序列 　　10．数组A[1..5,1..6]的每个素占5个单，将其按行优先次序存储在起始地址为1000的连续内存单中，则A[5，5]的地址是        。 　　   A、1140          B、1145         C、1120         D、1125 　　11．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为        。 　　   A、98              B、99            C、50            D、48 　　12．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号， 则可采用        实现编号。 　　  A、先序遍历            B、中序遍历         C、后序遍历        D、从根开始进行层次遍历 　　13．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是        的二叉树。 　　  A、空或只有一个结点                          B、高度等于其结点数 　　  C、任一结点无左孩子                          D、任一结点无右孩子 　　14．在有n个叶子结点的哈夫曼树中，其结点总数为        。 　　  A、不确定 B、2n     C、2n+1        D、2n-1 　　15．一个有n个顶点的无向图最多有        条边。 　　  A、n          B、n（n-1）         C、n（n-1）/2             D、2n 　　16．任何一个无向连通图的最小生成树        。 　　  A、只有一棵            B、有一棵或多棵         C、一定有多棵            D、可能不存在 　　17．一组记录的关键字为（46，79，56，38，40，84），利用快速排序的方法，以第一个记录为基准得到的一次划分结果为        。 　　  A、38，40，46，56，79，84 　　  B、40，38，46，79，56，84 　　  C、40，38，46，56，79，84 　　  D、40，38，46，84，56，79 　　18．已知数据表A中每个素距其最终位置不远，则采用        排序算法最节省时间。 　　    A、堆排序            B、插入排序         C、快速排序               D、直接选择排序 　　19．下列排序算法中，        算法可能会出现下面情况：初始数据有序时，花费时间反而最多。 　　    A、堆排序            B、冒泡排序         C、快速排序        D、SHELL 排序 　　20．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为        的结点开始。 　　   A、100            B、60            C、12            D、15 　　  　　三、填空题（40分） 　　1.         在顺序表（即顺序存储结构的线性表）中插入一个素，需要平均移动       个素. 　　2.         快速排序的最坏情况，其待排序的初始排列是                           . 　　3.  为防止在图中走回，应设立                             . 　　4. 一个栈的输入序列为123，写出不可能是栈的输出序列                  。 　　5. N个结点的二叉树,采用二叉链表存放,空链域的个数为             . 　　6. 要在一个单链表中p所指结点之后插入s所指结点时,  　　   应执行                    和                       的操作. 　　 7.Dijkstra算法是按                   的次序产生一点到其余各顶点最短路径的算法. 　　8.在N个结点完全二叉树中，其深度是                       . 　　9.对二叉排序树进行          遍历, 可得到结点的有序排列. 　　10．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P〈=M〉, 　　  　　为使函数具有较好性能，P应选                      　　  　　11．单链表与多重链表的区别是                   　　12．深度为6（根层次为1）的二叉树至多有                个结点。 　　13．已知二维数组A[0..20][0..10]采用行序为主方式存储，每个素占4个存储单,并且A[0][0]的存储地址是1016, 则A[10][5]的存储地址是             　　14．循环单链表La中，指针P所指结点为表尾结点的条件是              　　15．在查找方法中，平均查找长度与结点个数无关的查找方法是               。 　　16．队列的特性是                  　　17．具有3个结点的二叉树有           种 　　18．已知一棵二叉树的前序序列为ABDFCE，中序序列为DFBACE，后序序列为           　　  　　19．已知一个图的邻接矩阵表示，要删除所有从第i个结点出发的边，在邻接矩阵运算是 　　  　　                         　　  　　四、构造题：（30 分） 　　1．已知关键字序列为：（75, 33, 52, 41, 12, 88, 66, 27）哈希表长为10，哈希函数为： 　　H(k)=K MOD 7, 解决冲突用线性探测再散列法，构造哈希表，求等概率下查找成功的平均查找长度。 　　  　　  2．已知无向图如图1所示， 　　    （1）给出图的邻接表。 　　    （2）从A开始，给出一棵广度优先生成树。 　　
　　  　　  3．给定叶结点权值：（1，3，5，6，7，8），构造哈夫曼树，并计算其带权路径长度。 　　  4．从空树开始，逐个读入并插入下列关键字，构造一棵二叉排序树： 　　      （24，88，42，97，22，15，7，13）。 　　  5．对长度为8的有序表，给出折半查找的判定树，给出等概率情况下的平均查找长度。 　　
　　  6．已知一棵树如图2所示，要求将该树转化为二叉树。 　　  　　  　　  　　  　　  　　  　　  　　  　　  　　五、算法设计题(40分) 　　[算法题可用类PASCAL或类C语言,每题20分] 　　  　　1．  已知一棵二叉树采用二叉链表存放，写一算法，要求统计出二叉树中叶子结点个数并输出二叉树中非终端结点（输出无顺序要求）。 　　2．编写算法，判断带头结点的双循环链表L是否对称。 　　对称是指：设各素值a1,a2,…,an, 则有ai=an-i+1   　　即指：a1= an，a2= an-1  。。。。。。 　　    结点结构为 　　prior 　　data 　　next