资源描述：
《复习题数据结 新 优质文档.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、优质文档数据结构题库1.一个算法的好坏取决于该算法的时间复杂度和空间复杂度。2.克鲁斯卡尔算法的时间复杂度为O（eloge），适合求稀疏图的最小生成树。3.设单链表的结点结构为（data，*next），已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句_q—>next=p—>next和p—>next=q4.图的遍历方式有广度优先遍历和深度优先遍历两种。5.在有序表（12,24,36,48,602,84）中二分查找关键字72时所需进行的关键字比较次数为。26.已知广义表A=
2、((a,b,c),(d,e,f)),则运算head(head(tail（A）)))=d7.由带权为3,9,6,2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_558．一个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是109.静态查找表与动态查找表的根本区别在于施加在其上的操作不一样01010110010.从邻接矩阵A=可以看出，该图共有3顶点。如果是无向图，则共有2条边11.无向完全图具有n(n-1)/2条边。11优质文档12.广义表A（（a,b,c），（d,e,f））的表尾为__________。13
3、.对于给定的n个元素，可以构造出的逻辑结构有（集合）、（线性结构）、（树结构）、（图结构）4种。14线性结构中的元素之间存在（一对一）关系，树形结构中元素之间存在（一对多）关系，图形结构中的元素之间存在（多对多）关系。15队列的插入操作是在队列的（队尾）进行，删除操作是在队列的（队头）进行。16堆栈的逻辑特点是（先进后出），队列的逻辑特点是（先进先出）。17堆栈操作设输入元素的顺序为1,2,3,4,5，要在栈的输出端得到43521，则应进行栈的基本运算表示应为：Push（S,1），Push(S,2)，Push(S,3)，P
4、ush(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函数值序列为（01122312）11优质
5、文档23、设有一稀疏图G，则G采用（邻接表）存储结构较省空间。24．在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（3）次。25在有n个结点的二叉链表中，空链域的个数为__n＋1__。1.已知二叉树的前序ABCDEFGHIJ和中序CDBFEAIHGJ，试构造出相应的二叉树。2.已知一棵二叉树的后序遍历序列为EICBGAHDF，中序遍历序列为ECIFBAGDH，请画出这棵二叉树，3已知某二叉树，写出前序遍历、中序遍历和后序遍历
6、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分）。911优质文档已知如图所示的有向图，请给
7、出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。10对于所示的有向带权图。（1）作为AOE，写出从源点A到汇点G的所有路径并指出哪一条路径是关键路径。（2）将该图作为AOE网，试写出C的最早发生时间及活动FC的最晚开始时间。（3）写出A点到各顶点的最短路径。11已知图6.32所示的有向图，请给出：①每个顶点的入度和出度；②邻接矩阵；③邻接表；④逆邻接表。 图6.32有向图11优质文档图6.33无向网12已知如图6.33所示的无向网，请给出：(1)邻接矩阵；(2)写出深度优先搜索顺序和广度度
8、优先搜索顺序（至少5个）(3)画出最小生成树13假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。①试为这8个字母设计赫夫曼编码。②它的带权路径长度WPL。14已知模式串t=‘abcaabbabcab’写出用K
