2011秋算法与数据结构试卷A

石家庄铁道大学2011-2012学年第1学期2010级本科期末考试试卷（A）课程名称：算法与数据结构 仟课教师考试时间：分钟学号：姓名：班级：考试性质（学生填写）：正常考试（）缓考（）补考（）重修（）提前修读（）题号一二三四五六七总分满分206020100得分阅卷人、单项选择题（每小题2分，共20分）数据结构从逻辑上分为（）。B.内部结构和外部结构DB.内部结构和外部结构D.线性结构和非线性结构B.都是后进先出D.没有共同点C.紧凑结构和非紧凑结构栈和队列的共同点是（）。A.都是先进后出C.只允许在端点处插入和删除元素在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s,则执行（）。A.s—link=pTlink；p—link=s； B.p—link=s；s—link=q；C.p—link=s—link；s—link=p； D.q—link=s；s—link=p；在数组A8x10中，行列下标从0开始，每一个数组元素占用3个字节存储，所有数据元素相继存放在一个地址连续的存储空间中，则存放该数组至少需要的字节数是（）。A.240 B.100 C.80D.270中缀表达式A*（B+C）/（D-E+F）的后缀表达式为（ ）。A.A*B+C/D-E+F B.AB*C+D/E-F+C.ABC+*DE-F+/ D.ABCDEF*+/-+将一棵有100个结点的完全二叉树从根开始，每层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶子结点的编号为（）。A.48 B.49C.50 D.51已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该（ ）。A.将邻接矩阵的第i行删除 B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除 D.将邻接矩阵的第i列元素全部置为0对线性表进行折半搜索时，要求线性表必须( )。A.以数组的方式存储且结点按关键码有序排列 B.以数组方式存储C.以链接的方式存储且结点按关键码有序排列 D.以链接方式存储如果某二叉树的先根次序遍历结果为stuwv,中序遍历为uwtvs，那么该二叉树的后序为()。A.uwvts B.vwutsC.wuvtsD.wutsv不可能生成图所1-1示的二叉排序树的关键字序列为( )。A.42135B.45213C.45123D.42531)图1-1二、简答题(共60分)设一组关键字为(7,15,20,31,48,53,64,19,82,91),Hash函数H(key)=keyMOD11,Hash表表长m=11，用线性探测法解决冲突，试构造Hash表。(10分)并：(1)给出构造过程(2)求出平均查找长度ASL某子系统在通信联络中只可能出现8种字符，其出现的概率分别为0.06,0.28.0.07,0.08,0.14,0.23,0.03,0.11。(10分)请：(1)画出赫夫曼树设计赫夫曼编码计算其带权路径长度WPL已知一个图的顶点集V和边集G如下：V={0,1,2,3,4,5,6,7,8,9}；E={(0,1),(0, 4), (1,2),(1,7),(2,8),(3, 4),(3,8), (5,6), (5,8),(5,9),(6,7), (7, 8),(8,9)}。(12分)请：(1)画出此图给出此图的邻接表写出从顶点0出发的深度优先搜索遍历的顶点序列写出从顶点0出发的广度优先搜索遍历的顶点序列如图2-1所示(8分)请：(1)给出图2-1所示的二叉树的中序遍历序列给出图2-1所示的二叉树的后序遍历序列画出与图2-1所示的二叉树对应的森林>4G 图1/^已知有一个数据表为{30,18,20,15,38,12,44,53,46,18*,26,86},请给出进行2路归并排序的过程中每一趟排序后的数据表变化。（说明：从小到大排序）（8分）已知长度为10的表（xal,wan,wil,zol,yo,xul,yum,wam,wim,zr）,按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，请画出每插入一个结点完成后的平衡二叉排序树，若做了某种旋转，给出旋转类型。（12分）三、算法分析与设计（每小题10分，共20分）说明：用类C语言编写算法；对算法中使用