正在进行安全检测...

发布时间:2024-04-19 11:31:21   来源:文档文库   
字号:
安徽大学2005-2006学年第1学期数据结构》期末考试试卷(B卷)-------------------------------------------------------------------08.设有数组A[i,j],数组的每个元素长度为5字节,i的值为05j的值为06,数组从内存首地址AB开始顺序存放,当用以列为主序存放时,元素A[55]的存储首地址为(A.AB+180B.AB+175C.AB+200D.AB+20509.有六个元素654321的顺序进栈,问下列哪一个不是合法的出栈序列(A.543612B.453126年级专业姓名学号座位号C.346521D.234156总分阅卷人10.从具有n个结点的二叉排序树中查找一个元素时,在最坏情况下的时间复杂度为(A0(nB0(1C0(lognDO(n²二、填空题(每空1分,共20分)1.对于双向链表,在两个结点之间插入一个新结点时需要修改的指针共有____个。3.K个叶子结点的哈夫曼树,其结点的总数为4.对于17个元素的有序表A[1]-A[17]作二分查找,在查找其等于A[10]的元素时需比较_____.5.树的三种存储结构是、孩子表示法和孩子兄弟表示法。6.对二叉排序树进行遍历,就可以得到排好序的顶点序列。7.数据结构是相互之间存在一种或多种特定关系的数据元素的集合。根据数据元素之间关系的不同特性,通常可分为四类基本结构:集合、线性结构和图状结构。8.已知一个无向图的邻接表如下图所示:则从顶点Vo出发进行深度优先搜索遍历得到的顶点序列为_____________和广度优先搜索得到的顶点序列为_______________.0V02^31V14^62V23V34V4ABCD5V56V656634351^2^30^20^一、单项选择(在备选答案中选出一个正确答案,并将其号码填在题后的括号内。每题2分,共20分)01如果待排序序列中两个数据元素具有相同的值,在排序2.已知完全二叉树的第10层有10个叶子结点,则整个二叉树的结点数最多为_______个。前后它们的相互位置发生颠倒,则称该排序算法是不稳定的。)就是不稳定的排序方法。A.起泡排序B.归并排序C.Shell排序D.直接插入排序02.下面关于二分查找的叙述正确的是(A.链接方式存储,元素无序B.链接方式存储,元素有序C.顺序方式存储,元素无序D.顺序方式存储,元素有序03.若已知一棵二叉树的前序序列是BEFCGDH中序序列是FEBGCHD则他的后序序列是(AEFGHBCDBFEGHDCBCFEGBHDCDEFBGCHD04一棵完全二叉树上有1001个结点,其中叶子结点的个数是(A250B500D505D.以上答案都不对05.有一个具有n个顶点的连通图生成的最小生成树中,具有(条边。AnBn-1Cn+1D2n-106.下面的二叉树中,不是平衡二叉树。07.若串S1=ABCDEFG’,S2=’9898’,S3=’###’,S4=’012345’,执行concat(replace(S1,substr(S1,length(S2,length(S3,S3,substr(S4,index(S2,8,length(S2其结果为AABC###G0123’BABCD###2345’CABC###G1234’DABCD###1234’----------------------------------------线----------------------------------------1^第二题,8小题图9.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。6页,第1学生答题注意:勿超黑线两端;注意字迹工整。6页,第2
三、分析计算题(第16分,2,3,4每题8分,510,40分)3.某赋权有向图如下图所示:用迪杰斯特拉(Dijkstra)算法思想,求源点A到各其余顶点的最短路径及路径长度1B3A2C3D31.试以数据集{257913}为权值构造一棵哈夫曼树,并计算其带权路径长度.112FE1G5(第三大题第3题图)4.记录的关键字集合K={2393956812624833},给定的增量序列D={421},请写出对K按“SHELL方法”排序时各趟排序结束时的结果。6页,第3学生答题注意:勿超黑线两端;注意字迹工整。6页,第42.对于如下的连通图,请给出从顶点Vo出发,利用普里姆(Prim)算法求出它的最小生成树的过程中得到的顶点集和边集及最小生成树的权,并画出所得到的最小生成树。A6714B4DC22653F10E3(第三大题第2题图)

本文来源:https://www.2haoxitong.net/k/doc/bb9145bc6b0203d8ce2f0066f5335a8102d266fd.html

《正在进行安全检测....doc》
将本文的Word文档下载到电脑,方便收藏和打印
推荐度:
点击下载文档

文档为doc格式