河北大学数据结构期末考试题.doc

河北大学课程考核试卷(2005—2006学年第1学期考核科目数据结构课程类别选修考核方式闭卷卷别_A_一、选择题(每题2分,共20分(1、如果线性表中最常用的操作是存取第i个元素及其前驱结点的值,则采用存储方式节省时间。A单链表B双链表C单循环链表D顺序表(2、在一个链队列中,若f,r分别为队首、队尾指针,则插入s所指结点的操作为Af->next=s;f=s;Br->next=s;r=s;Cs->next=r;r=s;Ds->next=f;f=s;(3、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树定满足A所有的结点均无左孩子B所有的结点均无右孩子C只有一个叶子结点D是任意一棵二叉树(4、设F是一个森林,B是由F变换得到的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有个。An-+1Dn+2(5、有10个结点的无向图至少有条边才能确保其是连通图A8B9C10D11A—1(6、二叉排序树中,键值最小的结点一定A左指针为空B右指针为空C左右指针均为空D左右指针均非空(7、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。A1/2B1C2D4(8、设高度为h的二叉树上只有度为0和2的结点,则此二叉树中所包含的结点数至少为A2*hB2*h-1C2*h+1Dh+1(9、一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有个结点。A2k-1-1B2k-1+1C2k-1D2k+1(10、一组记录的排序码为(46,79,56,38,40,84,则利用堆排序的方法建立的初始堆为A79,46,56,38,40,80B84,79,56,38,40,46C84,79,56,46,40,38D84,56,79,40,46,38二、判断题(每题1分,共10分(1、顺序存储方式只能用于线性结构,不能用于非线性结构。(2、若一个结点是某二叉树子树的中序遍历序列中的第一个结点,则它必是该子树的后序遍历序列中的第一个结点。(3、求最小生成树的Prim算法在边较少、结点较多时效率较高。(4、折半查找只能在有序的顺序表上进行而不能在有序链表上进行。(5、快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。(6、在一个有向图的邻接表中,若某结点的链表为空,则该顶点的度一定为零。(7、插入排序、选择排序和冒泡排序不都是稳定的排序算法。(8、在二叉树排序中删除一个结点,接着又将该结点插入到该二叉排序树中去,该二叉树不会发生变化。(9、在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点相应的指针域置空即可。(10、由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树。三、简答题(每题6分,共36分1、试描述头指针、头结点、第一个结点的区别,并说明头指针和头结点的作用。2、已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF,求其对应的二叉树。3、已知如下所示长