复习题数据结.docx

1。数据的（）包括集合、线性、树和图4种基本类型A. 存储结构B.逻辑结构C.基本运算D.算法描述2. 对一个长度为n的顺序表，在第i个元素（1iData ! = 0 B. !BT-Right C. !BT-Left D. ! (BTLeft & BTRight)31. 对二叉排序树进行什么遍历可以得到从小到大的排序序列？A.前序遍历B.后序遍历 C.中序遍历 D.层次遍历32. 已知8个数据元素为(34, 76, 45, 18, 26,54, 92, 65 )，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为：A. 1B. 2C. 3D. 433. 由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：A. 23 B. 37 C. 44 D. 4634. 设一段文本中包含字符a, b, c, d, e,其出现频率相应为3, 2, 5, 1, 1。则经过哈夫曼编码后，文本所占字节数为：A. 40 B. 36 C. 25 D. 1235 .线性表、堆栈、队列的主要区别是什么？A.线性表用指针，堆栈和队列用数组B.堆栈和队列都是插入、删除受到约束的线性表C.线性表和队列都可以用循环链表实现，但堆栈不能D.堆栈和队列都不是线性结构，而线性表是顺序表中第一个元素的存储地址是1,每个元素的长度为2,则第5个元素的地址是()。A. 1 B. 105 C. 108 D. 11036设一个堆栈的入栈顺序是1、2、3、4、5.若第一个出栈的元素是4,则最后一个出栈的元素必定是：A. 1 B. 3 C. 5 D. 1 或者 537、带头结点的单链表h为空的判定条件是：A. h = NULL; B. h-next = NULL; C. hnext = h;D. h != NULL;38. 线性表L在什么情况下适用于使用链式结构实现？( 1分)A.需不断对L进行删除插入8.需经常修改L中的结点值C. L中含有大量的结点D. L中结点结构复杂40。对于一个具有NN个结点的单链表，在给定值为xx的结点后插入一个新结点的时间复杂度为A. O(1) B. O (N/2) C. O(N) D. O(NA2)41. 数组A1.5,1.6 每个元素占5个单元，将其按行优先次序存储在起始地址为10的连续的内存单元中，则元素A5, 5的地址为：A. 1120 B. 1125 C. 1140 D. 114542 .将 32, 2, 15, 65, 28, 10 依次插入初始为空的二叉排序树。则该树的前序遍历结果是：A. 2, 10, 15, 28, 32, 65B. 32, 2, 10, 15, 28, 65C. 10, 28, 15, 2, 65, 32D. 32, 2, 15, 10, 28, 6543已知一棵完全二叉树的第9层(设根为第1层)有1个叶结点，则该完全二叉树的结点个数最多是：A. 311 B. 823 C. 1847 D.无法确定44具有65个结点的完全二叉树其深度为(根的深度为1)：A. 8 B.7 C.6 D.545下面()算法适合构造一个稠密图G的最小生成树。A. Prim算法B. Kruskal算法 C. Floyd算法D. Dijkstr算法46.堆是一种()排序.A.插入B.选择 C.交换D.归并1。一个算法的好坏取决于该算法的时间复杂度和空间复杂度。2。克鲁斯卡尔算法的时间复杂度为 O(eloge) ,适合求 的最小生成树。3. 设单链表的结点结构为(data * next),已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句一 q一next=p-nex和pnext =q4. 图的遍历方式有 广度优先遍历和深度优先遍历两种。5. 在有序表(12,24 36,48,602 84 )中二分查找关键字72时所需进行的关键字比较次数为。26. 已知广义表 A= (a,b,d , (d,e f)则运算 head(head (tail A ) ) = d7. 由带权为3, 9, 6, 2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为一558. 个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是109. 静态查找表与动态查找表的根本区别在于施加在其上的操作不一样厂010、10. 从邻接矩阵职0 1 可以看出，该图共有 _顶点.如果是无向图，则共有 条边 I已知二叉树的前序ABCDEFGHIJ 和中序CDBFEAIHGJ,试构造出相应的二叉树。已知一棵二叉树的后序遍历序列为EICBGAHDF ，中序遍历序列为ECIFBAGDH ，请画出这棵二叉树,3已知某二叉树，写出前序遍历、中序遍历和后序遍历4给定权值集合 15,03,1, 02, 06, 09,16 17,构造相应的哈夫曼树，并计算它的带权路径长度。5用序列( 46,88,45 39, 70, 58,101, 10, 66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度6设关键字的输入次序为45,24,53 45, 12,24, 90。画出生成的二叉排序树 0 011. 无向完全图具有n(n1)/2条边。12. 广义表 A( (a, b, c) , (d,e f)的表尾为。13. 对于给定的n个元素，可以构造出的逻辑结构有集合)、(线性结构)、(树结构)、(图结构)4种.14线性结构中的元素之间存在(一对一)关系，树形结构中元素之间存在(一对多)关系，图形结构中的元素之间存在(多对多)关系.15队列的插入操作是在队列的(队尾)进行，删除操作是在队列的(队头)进行。16堆栈的逻辑特点是(先进后出),队列的逻辑特点是(先进先出)。17堆栈操作设输入元素的顺序为1,2,3,4 5，要在栈的输出端得到43521,则应进行栈的基本运算表示应为：Push (S,1), Push(S, 2), Push(S, 3), Push(S, 4), Pop(S) , ( Pop(S) ), (Push(S, 5) ),Pop(S), Pop(S), Pop(S)。18、一棵二叉树有67个结点，这些结点的度要么是0,要么是2。这棵二叉树中度数为2的结点有33个.19、一棵深度为6的满二叉树有31个分支结点和32个叶子。20. 克鲁斯卡尔算法的时间复杂度为(O(eloge),适合求(稀疏图)的最小生成树。21。两个字符串相等的充分必要条件是(长度相等，并且各个对应位置上的字符都相等)。22写出模式串p= “abaabcaC的 next函数值序列为(0 1 1 2 2 3 1) 223、设有一稀疏图G,则G采用(邻接表)存储结构较省空间。24. 在对一组记录(54,38 96, 23, 15, 72,60,45 83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较(3)次。25在有n个结点的二叉链表中，空链域的个数为_n+1_。7画出下列广义表()，a ( b , c,) (), d) ,(e)的存储结构图，并求它的长度。8试画出具有3个结点的二叉树所有不同形态(5分).9已知如图所示的有向图，请给出该图的：/g.(1) 每个顶点的入/出度；/SK. X邻接矩阵；Jr邻接表；凡上(4)逆邻接表。10对于所示的有向带权图.(1) 作为AOE ,写出从源点A到汇点G的所有路径并指出哪一条路径是关键路径.(2) 将该图作为AOE网,试写出C的最早发生时间及活动FC的最晚开始时间。(3) 写出A点到各顶点的最短路径。11已知图6. 32所示的有向图，请给出: 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。图6. 32有向图图6.33无向网12已知如图6. 33所示的无向网，请给出：(1娜接矩阵；(2) 写出深度优先搜索顺序和广度度优先搜索顺序(至少5个)(3) 画出最小生成树13假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0。19, 0。02, 0。06, 0。32, 0. 03 0。21, 0。10。 试为这8个字母设计赫夫曼编码。 它的带权路径长度WPL。14已知模式串t= Cabcaabbabcab,写出用KMP法求得的每个字符对应的next和nextval函数值。15以二叉链表作为二叉树的存储结构，编写以下算法：(1)统计二叉树的叶结点个数.16请写出链式存储的线性表中，在第i个位置插入和删除数据元素x的实现算法。(请在关键部分给出注释。)插入：17尾插法建立单循环链表的函数