复习题数据结

1、复习题常用软件课程设计C. n-i-1D. iD.O（ n+m）i个位置插入一个新元素的算法时间复杂度为（C. O（n）D. O（n2）个元素）存储方式最节省1数据的（）包括集合、线性、树和图4种基本类型A 存储结构B 逻辑结构C.基本运算D 算法描述2.对一个长度为n的顺序表，在第i个元素（K i n+1）之前插入一个新元素时需向右移动A. n-iB. n-i+13下面程序的时间复杂度为（）。For（i=0;iData);PreOrderPri ntLeaves( BT-Left );A . BT-Data != 0B .!BT-Right C!BT-LeftD. !(BT-Left & B

2、T-Right)PreOrderPri ntLeaves( BT-Right);31. 对二叉排序树进行什么遍历可以得到从小到大的排序序列？A.前序遍历B.后序遍历C.中序遍历D.层次遍历32. 已知8个数据元素为(34, 76, 45, 18, 26, 54, 92, 65),按照依次插入结点的方法生成一棵 二叉排序树后，最后两层上的结点总数为：A. 1 B. 2C. 3D. 433. 由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：A. 23 B. 37 C. 44 D. 4634. 设一段文本中包含字符a, b, c, d, e，其出现频率相应为3, 2,

3、 5, 1, 1。则经过哈夫曼编码后，文本所占字节数为：A. 40 B. 36 C. 25 D. 1235. 线性表、堆栈、队列的主要区别是什么？A.线性表用指针，堆栈和队列用数组B .堆栈和队列都是插入、删除受到约束的线性表C.线性表和队列都可以用循环链表实现，但堆栈不能D.堆栈和队列都不是线性结构，而线性表是顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。A . 100B . 105 C. 108D. 11036设一个堆栈的入栈顺序是1、2、3、4、5。若第一个出栈的元素是4,则最后一个出栈的元素必定 是：A . 1B. 3 C. 5D. 1 或者 53

4、7、带头结点的单链表h为空的判定条件是：A . h = NULL; B . h- next = NULL;C . h- next = h;D . h != NULL;38. 线性表L在什么情况下适用于使用链式结构实现？(1分)A.需不断对L进行删除插入B .需经常修改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个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素

5、A5,5的地址为：A . 1120B. 1125C. 1140D. 114542.将 32, 2, 15, 65, 28, 10 依次插入初始为空的二叉排序树。则该树的前序遍历结果是:A . 2, 10, 15, 28, 32, 65C. 10, 28, 15, 2, 65, 32B. 32, 2, 10, 15, 28, 65D. 32, 2, 15, 10, 28, 6543已知一棵完全二叉树的第9层(设根为第1层)有100个叶结点，则该完全二叉树的结点个数最阜.是：B. 823C. 1847D.无法确定44具有65个结点的完全二叉树其深度为(根的深度为1)：A . 8 B . 7 C .

6、 6 D . 5复习题45下面()算法适合构造一个稠密图G的最小生成树。A. Prim 算法 B. Kruskal 算法 C. Floyd 算法 D. Dijkstra 算法46.堆是一种()排序。A.插入E.选择C.交换D.归并1 一个算法的好坏取决于该算法的 时间复杂度和空间复杂度。2. 克鲁斯卡尔算法的时间复杂度为 0(eloge ) ，适合求稀疏图的最小生成树。3. 设单链表的结点结构为(data, * next),已知指针p指向单链表中X结点，指针q指向y的新结点， 若将结点y插入到结点x之后，则需要执行以下两条语句 _ qnext=p next和p next =q4. 图的遍历方式

7、有 广度优先遍历 和深度优先遍历 两种。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. 静态查找表与动态查找表的根本区别在于施加在其上的操作不一样10.从邻接矩阵A=11.无向完全图具有1 0 、0 1可以看出，该图共有卫顶点。如果是无向图，则共有 2 条0 0 n(n -1

8、)/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, P

9、ush(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= “abaabca的 next函数值序列为(0 1 1 2 2 3 1 2 )23、设有一稀疏图G,则

10、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已知某二叉树，写出前序遍历、中序遍历和后序遍历4给定权值集合15,03,14,02,06,09,16,17，构造相应

11、的哈夫曼树，并计算它的带权路径长度。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 )的存储结构图，并求它的长度。5分）8试画出具有3个结点的二叉树所有不同形态(9已知如图所示的有向图，请给出该图的：(1) 每个顶点的入/出度；(2) 邻接矩阵；(3) 邻接表；(4) 逆邻接表。10对于所示的有向带权图。(1) 作为

12、AOE，写出从源点A到汇点G的所有路径并指出哪一条路径是关键路径。(2) 将该图作为 AOE网，试写出C的最早发生时间及活动 FC的最晚开始时间(3) 写出A点到各顶点的最短路径11已知图6.32所示的有向图，请给出: 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。图6.32 有向图图6.33 无向网12已知如图6.33所示的无向网，请给出：(1) 邻接矩阵;(2) 写出深度优先搜索顺序和广度度优先搜索顺序(至少5个)(3) 画出最小生成树0.07，0.19, 0.02, 0.06,13假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为 0.32，0.03，0.21，0.10。 试为这8个字母设计赫夫曼