搜索
命题人：张凤君专业主任（签字）：日期：2012年12月6日印数：使用专业计算机科学与技术（师、工）、软件工程、网络工程使用年级2011级班级学号姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————第1页共5页北华大学计算机科学技术学院2012-2013学年第一学期《数据结构》课程期末考试试卷（3）题号一二三四总分得分评卷人核分：一、填空题（每小题2分，共14分）1.数据元素之间的关系有四种，包括集合、线性结构、树形结构和图状结构。2.二维数组A[3][4]采用行序为主方式存储，每个元素占2个存储单元，并且A[1][0]的存储地址是1000，则A[2][2]的地址是__1012___________。3.有一个长度为n的顺序表，若在第i个元素（0≤i≤n-1）之后插入一个元素时，需向后移动______n-i-1__个元素。4.已知有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，若第i个结点有右孩子，则其右孩子结点的编号为__2n+1_________。5.设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为N0—N1。6.设有向图G中有n个顶点，并有e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。7.__中序________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。二、选择题（每题2分，共16分）1.下面算法的时间复杂度为__A_______。for(i=0；im；i++)for(j=0；jt；j++)c[i][j]=0；for(i=0；im；i++)for(j=0；jt；j++)for(k=0；kn；k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；A.O(m*n*t)B.O(m+n+t)C.O(m+n*t)D.O(m*t+n)大题得分大题得分命题人：张凤君专业主任（签字）：日期：2012年12月6日印数：使用专业计算机科学与技术（师、工）、软件工程、网络工程使用年级2011级班级学号姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————第2页共5页2.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是C。A.n-iB.n-1-iC.n+1-iD.不能确定3.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是B。A.head==0B.head-next==0C.head-next==headD.head!=04.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为B。A.8B.7C.6D.55.如果在表示树的孩子兄弟链中有6个空的左指针域，7个空的右指针域，5个结点左、右指针域都为空，则该树中叶的个数________。A.有7个B.有6个C.有5个D.不能确定6.设有向图G中的有向边的集合E={1，2，2，3，1，4，4，5，5，3，4，6，6，5}，则不是该图的一个拓扑序列的为____________。A.1,2,4,6,5,3B.1,4,6,5,2,3C.1,4,2,6,5,3D.1,4,6,2,3,57.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为。A.aedfcbB.acfebdC.aebcfdD.aedfbc8.如右侧图所示的一棵二叉排序树其成功的平均查找长度为________。A.21/6B.15/6C.18/7D.28/7三、应用题（1~4题每题6分，5~6题每题8分，共40分）1.一个输入序列是123，请写出栈的一个输出序列和队列的输出序列。并总结栈和队列区别。大题得分1题得分90302050408070命题人：张凤君专业主任（签字）：日期：2012年12月6日印数：使用专业计算机科学与技术（师、工）、软件工程、网络工程使用年级2011级班级学号姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————第3页共5页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,b,c,d,e,f,g的赫夫曼编码，要求左子树编码为0，并写出accee的编码。3.已知一个二叉树的中序和后序遍历序列分别为CDBAEGF和DCBGFEA，请画出此二叉树，并写出其先序序列。4.已知关键字序列{49386597761327}，写出执行快速排序算法（以第一个关键字为枢轴元素）前三趟升序排序的关键字序列的状态。2题得分3题得分4题得分命题人：张凤君专业主任（签字）：日期：2012年12月6日印数：使用专业计算机科学与技术（师、工）、软件工程、网络工程使用年级2011级班级学号姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————第4页共5页5.已知AOV网如下，按关键路径算法:（1）找出其关键路径。（2）计算：Ve(F)、Vl(F)（3）设D,E弧称为活动a,计算：e(a)和l(a)（4）完成此工程最少需要多少天。6.假设有一批关键字序列18,75,60,23,30,33,46,20，给定哈希函数H(k)=k%13，存贮区的内存地址从0到15，则计算每个关键字存储序号，并画出该哈希表。四、算法设计（每小题10分，共30分）1.已知顺序表的存储结构如下，请在空格上填写适当的语句，完成对顺序表L作一趟Shell排序插入算法，假定原顺序表L中元素按升序排序。typedefstruct{int*elem,length,listsize;}SqList；voidShellInsert(SqList&L,intdk){for(i=dk+1;i=L.length;)if(LT(L.r[i].key,L.r[i-dk].key)){;for(j=i-dk;j0&<(L.r[0].key,L.r[j].key);)=L.r[j];L.r[j+dk]=;}}6题得分大题得分5题得分1题得分EAFDHCGB33564744910886命题人：张凤君专业主任（签字）：日期：2012年12月6日印数：使用专业计算机科学与技术（师、工）、软件工程、网络工程使用年级2011级班级学号姓名考试地点————————¤—————¤———————————装订线————————¤———————¤——————第5页共5页2.线性表的单链表存储结构如下，请在空格上填写适当的语句，完成单链表的删除算法。typedefstructLNodeStatusListDelete_L(LinkList,ElemType&e){ElemTypedata;{//在带头结点的单链线性表L中删除第i个元素structLNode*next;//并由e返回其值}Lnode,*LinkList;p=L;j=0;while(p-next&&ji-1){;++j;}if((!(p-next)||ji-1))returnERROR;q=p-next;;;;returnOK;}//ListInsert_L3．根据下面给出的二叉树树的存储结构，请用类C语言编写二叉排序树的插入算法,其中查找算法原型为StatusSearchBST(BiTree&T,KeyTypekey,BiTreef，BiTree&p)。typedefstructBiTNode{TElemTypedata;structBiTNode*lchild，*rchild;}BiTNode,*BiTree;StatusInsertBST(BiTree&T,ElemTypee)3题得分2题得分