河北大学数据结构期末考试真题A

1、河 北 大 学 课 程 考 核 试 卷（ 2005 2006 学年第 1 学期）考核科目 数据结构 课程类别 选修 考核方式 闭卷 卷别_A_一二三四五六七八九十十一总分得分评卷人一、选择题（每题2分，共20分）（ ）1、如果线性表中最常用的操作是存取第 i个元素及其前驱结点的值，则采用 存储方式节省时间。A）单链表B）双链表C）单循环链表D）顺序表（ ）2、在一个链队列中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为 A）f->next=s;f=s; B） r->next=s;r=s; C）s->next=r;r=s; D） s->next=f;f=s;（

2、）3、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树定满足 A）所有的结点均无左孩子 B）所有的结点均无右孩子C）只有一个叶子结点 D）是任意一棵二叉树（ ）4、设F是一个森林，B是由F变换得到的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有 个。A）n-1 B）n C）n1 D）n2（ ）5、有10个结点的无向图至少有 条边才能确保其是连通图A）8 B）9 C）10 D）11A1（ ）6、二叉排序树中，键值最小的结点一定 A）左指针为空 B）右指针为空 C）左右指针均为空 D）左右指针均非空（ ）7、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍

3、。 A）1/2 B）1 C）2 D）4（ ）8、设高度为h的二叉树上只有度为0和2的结点，则此二叉树中所包含的结点数至少为 A）2*h B）2*h-1 C）2*h+1 D）h+1 （ ）9、一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有 个结点。A）2k-1-1B）2k-1+1C）2k-1D）2k+1（ ）10、一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为 ） 79,46,56,38,40,80） 84,79,56,38,40,46） 84,79,56,46,40,38） 84,56,79,40,46,38得分评卷人二、判断

4、题（每题1分，共10分）（ ）1、顺序存储方式只能用于线性结构，不能用于非线性结构。（ ）2、若一个结点是某二叉树子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。（ ）3、求最小生成树的Prim算法在边较少、结点较多时效率较高。（ ）4、折半查找只能在有序的顺序表上进行而不能在有序链表上进行。（ ）5、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。（ ）6、在一个有向图的邻接表中，若某结点的链表为空，则该顶点的度一定为零。（ ）7、插入排序、选择排序和冒泡排序不都是稳定的排序算法。A2（ ）8、在二叉树排序中删除一个结点，接着又将该结点插入到该二叉

5、排序树中去，该二叉树不会发生变化。（ ）9、在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点相应的指针域置空即可。（ ）10、由二叉树的后序序列和中序序列可以唯一地确定一棵二叉树。得分评卷人三、简答题（每题6分，共36分）1、试描述头指针、头结点、第一个结点的区别，并说明头指针和头结点的作用。2、已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，求其对应的二叉树。3、已知如下所示长度为12的查找表：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec；试按表中元素的顺序依次插入到一棵初

6、始为空的二叉排序树。画出插入完成后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。4、对下面连通图，画出其邻接矩阵，并用Prim算法构造其最小生成树。14213abcdhgfe2221125、设AOE网如下图所示，求：列出各个事件的最早、最迟发生时间；找出该AOE网中的关键路径，并回答完成该工程需要的最短时间。V1V2V4V3V5V6V7V8V9V10a1=5a2=6a3=3a4=6a5=3a6=3a7=10a8=5a9=1a12=5a10=4a11=4a13=2a14=2A36、应用直接插入排序算法，对关键值序列25，84，68，47，35，27， 21， 15，24从小到大排列。试写出每趟排序的结果。得分评卷人四、算法设计题（共34分）【要求】定义主要数据的存储类型；对算法中的主要操作步骤加以注释。1、已知带头结点的单链表L中的结点是按整数值递增排列的，试写一算法，将值为x 的结点插入到表L中，使得L仍然有序。（10分）2、假设二叉排序树T的各个元素的值均不相同，设计一个算法按值递减的