福州大学 学年第 学期考试 卷
课程名称 算法与数据结构 考试日期考生姓名 学号 专业或类别题号题分得分一30二48三22总分100累分人签名考生注意事项：1、本试卷共 8 页，请查看试卷中是否有缺页。 2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。教师注意事项：如果整门课程由一个教师评卷的，只需在累分人栏目签名，题首的评卷人栏目可不签名一、填空题（每小题3分，共30分）得分评卷人 1、在内存中分配了一个数组Elem Arrary[20][30][50]（行优先），已知Array[0][0][0]的起始存储地址是1024000(字节)，Elem类型的元素长度为8字节，求Arrary[5][7][9]的存储地址空间（起止地址）为_____________。2、对一棵完全3叉树，按照广度优先遍历顺序给结点从左向右依次连续编号，第一个结点编号为0。则编号为100 的结点的父结点编号是__________。3、下面术语______________与数据的存储结构无关（写出编号）。 (a) 顺序表 (b) 链表 (c) 队列 (d) 循环链表4、编号为1，2，3，4的四辆列车，顺序开进一个栈式结构的站台；问开出车站的顺序有 种可能。5、顺序存储的队列如果不采用循环方式，则会出现 问题。第 1 页 共 8 页
试卷答案网课刷课代刷完成flyingjgh4、算法是由若干条指令组成的有穷序列，具有以下4个特性：(a) 确定性、 (b)有限性、(c)有零个或多个输入、(d) 有一个或者多个输出。程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质 。（写出编号）7、40，27，32，15，14，20，25，11是一个堆，其中32的孩子为 。8、在具有n(n>=1)个结点的m叉树中，有 个指针是空的。499、对10个元素的序列（49,38,65,97,76,12,27,50,,80）按从小到大的顺序进行排序，选择排序的第3趟的结果为______________________________________。10、采用快速排序法进行排序时，如果 时，排序效率会大大降低。2、简答题（每小题8分，共48分）得分评卷人 1、散列表长度m=13，散列函数为h1(key) = key % m。处理冲突的方法为双重散列法，探查函数为： p(key，i）=（key %（m-2）+ i * h1（key））% m， i =1，…，m-1 依次将关键码{34, 96, 12, 8, 37, 35, 22 } 填入散列表。（1）请把关键码填写到下面散列表中相应的位置：0123456789101112（2）求出对散列表中现有元素等概率查找时查找成功的平均查找长度。第 2 页 共 8 页
试卷答案网课刷课代刷完成flyingjgh2、（1）对于连通的无向图，采用Dijkstra最短路径算法，在Dist数组中能否给出足够形成一棵支撑树的信息？ （2）是否能给出一棵最小支撑树？请证明你的结论或举反例说明。 （提示：Dist数组用来记录当前每个顶点所对应的最短特殊路径长度。）第 3 页 共 8 页
试卷答案网课刷课代刷完成flyingjgh
(3)--数据结构试卷2
