《数据结构概论》+A卷

1、+A卷数据结构概论+A 卷编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构概论 +A 卷的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为数据结构概论+A 卷的全部内容。福建师范大学试卷纸第1 页共5 页+A 卷第 PAGE 第4页共 5 页福建师范大学试卷纸数据结构概论期末考核试题一、单项选择题 (230分）1。下列

2、编码中属前缀码的是（B )A。1,01,000，001B。1,01,011，010C。0，10，110,11D.0,1，00,112SQa，b,c，d,e，f依次进栈，一个元素Q6b,d，c,f，e，a,S至少应当是( C ）A。6B.4C。3D.23.在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复度是(B）A。O（1)B.O(n）C.O(nlogn）4。要表示省，市，区，街道的有关数据及其关系，选择（B)比较合适A.线性结构B.树结构C。图结构D。集合结构5.链栈与顺序栈相比，比较明显的优点是( D)A。插入操作更加方便B.删除操作更加方便C。不会出现下溢的情况D.不

3、会出现上溢的情况6。二叉树中第5层上的结点个数最多为( CA。8B。15C.16D.327.在表长为的链表中进行线性查找，查找成功时,它的平均查找长度为( B）A.ASL=nB.ASL=（n+1）/2C.ASL= n +1D。ASLlog2(n+1）18。对 22 个记录的有序表进行折半查找， 当查找失败时， 至少需要比较( B）次关键字。A。3B.4C。5D。69。已知图的邻接表如下所示,根据算法，则从顶点 0 出发按广度优先遍历的结序列是（ A）A. 0 3 2 1B. 0 1 2 3C。 0 1 3 2D。0 3 1 2（90,1,2，3）10.对于哈希函数H(key)=key%13，被

4、称为同义词的关键字是（D)A.35和41B.23 和39C.15和44D.25 和5111。图的深度优先遍历类似于二叉树的(A）A。先序遍历B.中序遍历C.后序遍历D.层次遍历12。下述几种排序方法中，稳定的排序算法是( BA.直接插入排序B.快速排序C。堆排序D。希尔排序依次取出元素与已排序序列（初始时为空）中的元素进行比较 ,将其放入已序序列的正确位置上的方法，称为（ C）A。希尔排序B.冒泡排序C。插入排序D。选择排序14。二叉树是非线性数据结构，所以 （ C)A.它不能用顺序存储结构存储B。它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储D。顺序存储结构和链式存储结都不

5、能使用15.有8个结点的无向图最多有( B)条边A。14B.28C.56D.112二、填空题（115分）当问题的规模n趋向无穷大时，算法执行时间T（n）的数量级被称为算法的 时间复杂度。aM(M为最大空间个数)Q的存储空间,front(指向第一个存放数据的位置）,rear 为队尾指针（指向最后一个存放数据位置的下一个），Q队列的队满条件是_front= =(rear+1)m_。BEFCGDHFEBGCHD，则它的后序序列必是_FEGHDCB。SX分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA的操作序列为 SSXSXX， 则由“a*b+c/d”得到“abcd/+的操作序列为_S

6、XSSXXSSXSSXXX.32106，则度为3的结点个数是2。在数据的存放无规律而言的线性表中进行检索的最佳方法是_顺序查找。n 个顶点 e 条边的图采用邻接矩阵存储 ,深度优先遍历算法的时间复杂度为 O(n2）；若采用邻接表存储时，该算法的时间复杂度为O（n+e)。在堆排序和快速排序中，若初始记录接近正序或反序，则选用堆排序 ;若初始记录基本无序，则最好选用快速排序。若要求一个稠密图G的最小生成树，最好用普里姆算法来求解。6 32个叶子。 63 个 分 支 结 点 和在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是_哈希表 。有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶

7、点i的出度 。三、解答题（840分)1。 用普里姆(prim)算法从右图中的顶点 1 构造的每一步。116252119146932611654182. 假设通信电文使用的字符集为 a,b，c,d,e，f，g，若这些字符在电文中出现的频度分别为：3，35，13，15，20，5 和 9以及哈夫曼编码，并比较他们的编码长度。3. 25，47,36,21，90,84,62,78，15，32。写出用（小根）序的每一趟的结果。4。 已知一棵树的前序序列为： abefcgdhijk，后序序列为： efbgcijkhda。画出这棵树。5.已知闭散列表的长度为 10（ 散列地址空间为 0.。9)， 散列函数为 H（K)=K%8，采用线性重新散列技术解决冲突，将下列一组数据 25，17，39， 47，83，55,99，34依次插入到散列表中，请画出散列表。四、算法阅读、设计(5分)1 algo,并回答问题:（5分）void algo(Queue *Q)Stack S； InitStack（S）；while (!QueueEmpty（Q)） Push(S, DeQueue(Q）)；while （！ StackEmpty（S） nQueue(Q,Pop（&S)）；（1)假设队列 q 中的元素为(2,4，5,7，8)，其中“2