东北林业大学数据结构2003-2004

《东北林业大学数据结构2003-2004》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、东北林业大学2003－2004学年第二学期考试试题装订线课程名称：班级：学号□□□□□□□□姓名：考试科目：数据结构考试时间：120分钟试卷总分85分题号一二三四五平时成绩总分得分评卷教师得分一、单项选择题（在每个小题四个备选答案中选出一个正确答案，填在题末的括号中）（本大题共10小题，每小题2分，总计20分）1．设输入序列为a，b，c，d，借助一个栈得到的输出序列不可能是（）。A．a，b，c，dB．d，c，b，aC．a，c，d，bD．d，a，b，c答案（）2．任何一个无向连通图的最小生成树（）。A．只有一棵B．有一棵或多棵C．一定有多棵D．可能不存在答案（）3．若待

2、排序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方法是（）。A．归并排序B．直接插入排序C．直接选择排序D．快速排序答案（）4．有12个节点的平衡二叉树的最大深度是（）。A．4B．5C．6D．3答案（）5．对于序列为{12，13，11，18，60，15，7，18，25，100}，用筛选法建堆，必须从值为（）的结点开始。A．100B．12C．60D．15答案（）6．在一棵高度为H的满三叉树中，结点总数为（）。A．3H-1B．（3H–1）/2C．（3H-1）/3D．3H答案（）7．用二分法在有序表{3，4，10，13，33，42，46，63

3、，76，78，95，96，120}中查找95时，需要比较次数为（）。A．2B．3C．4D．5答案（）学院：信息学院教研室（学科）主任：王阿川第3页共3页东北林业大学2003－2004学年第二学期考试试题ACFG8．已知二叉树如图所示，此二叉树的顺序存储结构是（）。123454ACFG1234ACFGA．B.1234564ACFG12345ACFGC．D.答案（）9．某二叉树的前序遍历结点顺序为：ABCDEFG，中序遍历结点顺序为：CBDAFGE，则后续遍历结点的顺序为：（）。A．CDBGFEAB.CDGFEABC.CDBAGFED.CDBFAGE答案（）10．设树T的

4、度为4，其中度为1、2、3和4的结点的个数分别为4、2、1、1，则T中叶子结点的个数是（）。A．5B．6C．7D．8答案（）得分二、填空（本大题共10小题，每小题1分，总计10分）1．无向图中的极大连通子图称为该无向图的。2．在堆排序过程中，首先要将待排序的所有键值分放到一棵完全二叉树的各个结点中，然后反复调用“筛选”过程使该完全二叉树具有堆的特性，在建成堆的过程中，需要调用“筛选”过程次。3．对50个记录进行折半查找，最多比较次数和最少比较次数分别是。4．线性表L={a1，a2，......，an}用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移

5、动元素的个数是。5．设有一中缀表达式（（E-F）*G+A/（B-C））*D，其等价的后缀表达式是。6．设二维数组A[10..20，5..10]按行优先存储，每个元素占4个存储单元，A[10，5]的存储地址为1000，则A[15，10]的存储地址为。7．深度为K的完全二叉树至多和至少分别有个结点。8．在计算递归函数时，如不用递归过程，应借助的数据结构。9．查找表分为静态查找表和动态查找表两种，二叉排序树属于。10．一般树的遍历结果和它所对应的二叉树的遍历结果之间有一定的对应关系：一般树的前序遍历序列和它所对应二叉树的遍历序列一致，一般树的后序遍历序列和它所对应二叉树的遍

6、历序列一致。得分装订线课程名称：班级：学号□□□□□□□□姓名：三、解答下列问题（本大题共6小题，每小题5分，总计30分）1、已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)，哈希函数为：H(key)=keyMOD13,哈希表长为m=16，设每个记录的查找概率相等，学院：信息学院教研室（学科）主任：王阿川第3页共3页东北林业大学2003－2004学年第二学期考试试题用线性探测再散列处理冲突，即Hi=(H(key)+di)MODm。要求：（1）画出相应的哈希表；（2）分别求出在等概率情况下，查找成功的平均查找长度；2、一个空AVL树

7、内，依次插入关键字10，20，30，40，50，60分别画出10，20，30插入完和所有关键字都插入完的AVL树。3、给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树及其编码。4、下图是一个地区交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价，怎样选择能够沟通每个城市且总造价量省的n-1条公路，画出所有可能的方案。211662111531914645336185、对于给定的一组键值：70，73，69，23，93，18，11，68，分别画出利用快速排序方法对上述序列进行排序中的各趟的结果。得分四、算法设计题