北华大学计算机科学技术学院2012数据结构试题

1、北华大学计算机科学技术学院2012-2013学年第一学期 数据结构 课程期末考试试卷（3）题号一二三四总分得分评卷人核分：一、填空题（每小题2分，共14分）1.数据元素之间的关系有四种，包括集合、 线性结构 、树形结构和图状结构。2.二维数组A34采用行序为主方式存储，每个元素占2个存储单元，并且A10的存储地址是1000，则A22的地址是_1012_。3. 有一个长度为n的顺序表，若在第i个元素（0in-1）之后插入一个元素时，需向后移动_n-i-1_个元素。4.已知有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，若第i个结点有右孩子，则其右孩子结点的编号为_2n+1_

2、。5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为 N0N1 。6. 设有向图G中有n个顶点，并有e条有向边，所有的顶点入度数之和为d，则e和d的关系为_。7. _中序_遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。二、选择题（每题2分，共16分）1.下面算法的时间复杂度为_A_。for(i=0； im； i+) for(j=0； jt； j+) cij=0；for(i=0； im； i+) for(j=0； jt； j+) for(k=0； knext=0C. head-next=headD. head!=04.

3、设一棵完全二叉树中有65个结点，则该完全二叉树的深度为 B 。A. 8B. 7C. 6D. 5 5. 如果在表示树的孩子兄弟链中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中叶的个数_。A. 有7个 B. 有6个 C. 有5个 D. 不能确定6. 设有向图G中的有向边的集合E=，则不是该图的一个拓扑序列的为_。A. 1,2,4,6,5,3 B. 1,4,6,5,2,3 C. 1,4,2,6,5,3 D.1,4,6,2,3,57. 设无向图G中的边的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发进行深度优先遍

4、历可以得到的一种顶点序列为 。A. aedfcbB. acfebdC. aebcfdD. aedfbc8.如右侧图所示的一棵二叉排序树其成功的平均查找长度为_。A. 21/6 B. 15/6 C. 18/7 D. 28/7三、应用题（14题每题6分，56题每题8分，共40分）1.一个输入序列是123，请写出栈的一个输出序列和队列的输出序列。并总结栈和队列区别。 90302050408070大题得分1题得分2题得分2.假设字符a,b,c,d,e,f,g的使用频率分别是0.18,0.13,0.12,0.08,0.11,0.16,0.26 (1)画出赫夫曼树，要求左子树为权值最小的结点 (2)写出a

5、,b,c,d,e,f,g的赫夫曼编码，要求左子树编码为0，并写出accee的编码。3. 已知一个二叉树的中序和后序遍历序列分别为CDBAEGF和DCBGFEA，请画出此二叉树，并写出其先序序列。4.已知关键字序列49 38 65 97 76 13 27，写出执行快速排序算法（以第一个关键字为枢轴元素）前三趟升序排序的关键字序列的状态。3题得分4题得分5.已知AOV网如下，按关键路径算法: （1）找出其关键路径。 （2）计算：Ve (F)、Vl (F)（3）设弧称为活动a, 计算：e (a)和l(a)（4）完成此工程最少需要多少天。6. 假设有一批关键字序列18,75,60,23, 30,33,

6、46,20，给定哈希函数H(k)=k % 13，存贮区的内存地址从0到15，则计算每个关键字存储序号，并画出该哈希表。 四、算法设计（每小题10分，共30分）1. 已知顺序表的存储结构如下，请在空格上填写适当的语句，完成对顺序表L作一趟Shell排序插入算法，假定原顺序表L中元素按升序排序。typedef struct int *elem, length, listsize; SqList； void ShellInsert(SqList &L, int dk) for(i=dk+1;i0<(L.r0.key,L.rj.key); ) = L.rj; L.rj+dk = ; EAFDHCG

7、B335647449108865题得分6题得分大题得分1题得分2题得分2.线性表的单链表存储结构如下，请在空格上填写适当的语句，完成单链表的删除算法。typedef struct LNode Status ListDelete_L(LinkList ,ElemType &e) ElemType data; / 在带头结点的单链线性表L中删除第i个元素struct LNode *next; / 并由e返回其值 Lnode,*LinkList; p=L;j=0; while (p-next&jnext)|ji-1) return ERROR; q=p-next; ; ; ; return OK; /ListInsert_L3根据下面给出的二叉树树的存储结构，请用类C语言编写二叉排序树的插入算法,其中查找算法原型为Status SearchBST(BiTree &T,KeyType key,BiTree f，BiTree &p)。typedef struct Bi