复习题数据结.doc

1.数据的（ ）包括集合、线性、树和图4种基本类型A存储结构 B逻辑结构C基本运算D算法描述2.对一个长度为n的顺序表，在第i个元素（1in+1）之前插入一个新元素时需向右移动（ ）个元素。An-iBn-i+1Cn-i-1Di3下面程序的时间复杂度为（ ）。For(i=0;im;i+) For(j=0;jData); PreOrderPrintLeaves( BT-Left ); PreOrderPrintLeaves( BT-Right ); ABT-Data != 0B!BT-RightC!BT-LeftD!(BT-Left & BT-Right)31.对二叉排序树进行什么遍历可以得到从小到大的排序序列？A前序遍历B后序遍历C中序遍历D层次遍历32.已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为：A1B2C3D433.由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：A23B37C44D4634.设一段文本中包含字符a, b, c, d, e，其出现频率相应为3, 2, 5, 1, 1。则经过哈夫曼编码后，文本所占字节数为：A40B36C25D1235.线性表、堆栈、队列的主要区别是什么？A线性表用指针，堆栈和队列用数组 B堆栈和队列都是插入、删除受到约束的线性表C线性表和队列都可以用循环链表实现，但堆栈不能 D堆栈和队列都不是线性结构，而线性表是顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A100B105C108D11036设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4，则最后一个出栈的元素必定是：A1 B3 C5 D1或者537、带头结点的单链表h为空的判定条件是：Ah = NULL; Bh-next = NULL; Ch-next = h;Dh != NULL;38.线性表L在什么情况下适用于使用链式结构实现？(1分)A需不断对L进行删除插入B需经常修改L中的结点值CL中含有大量的结点DL中结点结构复杂40.对于一个具有NN个结点的单链表，在给定值为xx的结点后插入一个新结点的时间复杂度为AO(1) BO(N/2)CO(N)DO(N2)41.数组A1.5,1.6每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为：A1120B1125C1140D114542.将 32, 2, 15, 65, 28, 10 依次插入初始为空的二叉排序树。则该树的前序遍历结果是：A2, 10, 15, 28, 32, 65B32, 2, 10, 15, 28, 65C10, 28, 15, 2, 65, 32D32, 2, 15, 10, 28, 6543已知一棵完全二叉树的第9层（设根为第1层）有100个叶结点，则该完全二叉树的结点个数最多是：A311B823C1847D无法确定44具有65个结点的完全二叉树其深度为（根的深度为1）：A8B7C6D545下面（）算法适合构造一个稠密图G的最小生成树。A Prim算法 BKruskal算法 CFloyd算法 DDijkstra算法46堆是一种（ ）排序。 插入 选择 交换 归并1.一个算法的好坏取决于该算法的时间复杂度和空间复杂度。2.克鲁斯卡尔算法的时间复杂度为 O（eloge） ，适合求 稀疏图 的最小生成树。3.设单链表的结点结构为（data，*next），已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句_ qnext=pnext和pnext =q 4.图的遍历方式有 广度优先遍历 和深度优先遍历两种。5.在有序表（12,24,36,48,602,84）中二分查找关键字72时所需进行的关键字比较次数为。26.已知广义表A=(a,b,c),(d,e,f),则运算head(head (tail（A）)= d7.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_558 一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是109.静态查找表与动态查找表的根本区别在于施加在其上的操作不一样0 1 010 11 0 0 10.从邻接矩阵A= 可以看出，该图共有 3 顶点。如果是无向图，则共有 2条边11.无向完全图具有 n(n-1)/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 2 ）23、设有一稀疏图G，则G采用 （邻接表）存储结构较省空间。24在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（ 3）次。25在有n个结点的二叉链表中，空链域的个数为_n1_。1.已知二叉树的前序ABCDEFGHIJ和中序CDBFEAIHGJ，试构造出相应的二叉树。2.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为ECIFBAGDH，请画出这棵二叉树，3已知某二叉树，写出前序遍历、中序遍历和后序遍历4给定权值集合15,03,14,02,06,09,16,17，构造相应的哈夫曼树，并计算它的带权路径长度。5用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度6设关键字的输入次序为45，24，53，45，12，24，90。画出生成的二叉排序树7画出下列广义表( ( ( ) ) , a , ( ( b , c ) , ( ) , d ) , ( ( ( e ) ) ) )的存储结构图，并求它的长度。8试画出具有3个结点的二叉树所有不同形态（5分）。9已知如图所示的有向图，请给出该图的:（1） 每个顶点的入/出度；（2） 邻接矩阵；（3） 邻接表；（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个字母设计赫夫