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