复习题数据结

1、WOR格式专业资料整理1.数据的（A.存储结构）包括集合、线性、树和图B.逻辑结构4种基本类型C.基本运算D.算法描述2.对一个长度为 A. n-in的顺序表，在第B. n-i+1i个元素 1< i < n+1）之前插入一个新元素时需向右移动（ （）个元素。C. n-i-1D. i3下面程序的时间复杂度为（）。For(i=0;i<m;i+)For(j=0;j <n ;j+)Aij=i*j；A.O(m2)B.O(n2)C.O(n*m)D.O(n+m)4长度为n的线性表采用顺序存储结构，在其第 i个位置插入一个新元素的算法时间复杂度为（）。A. O（0）5.数据结构就是研究

2、（B. 0(1)C. 0(n)D. 0(n2)）。A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其数据在运算上的实现6下面关于算法的说法，错误的是（）。A.算法最终必须由计算机程序实现B.为解决某问题的算法和为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上三种说法都错误7线性表L= （a1, a2, ?an,）下列说法正确的是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少要有一个元素C.表中所有元素的排列顺序必须是由小到大或由大到小8.卜面关于线性表叙述错误的是（D.除第一个和最后一个元素外，其

3、余每个元素都有且仅有一个直接前驱和一个直线八日接后继）。A.B.线性表采用顺序存储，必须占用一段地址连续的单元线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链式存储，不必占用一段地址连续的单元D.线性表采用链式存储，便于进行插入和删除操作9用链表表示线性表的优点是（）A.便于随机存取B. 存储空间比顺序存储方式少C.便于插入和删除D.数据元素的存储顺序与逻辑顺序相同10若某线性表中最常用的操作是取第个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。A.单链表B.双链表C.单向循环D.顺序表B.由元素进入队列的先后顺序决定()11. 若队列采用顺序存储结构，元素的排列顺序A

4、.与元素值的大小有关C. 与队头指针和队尾指针的取值有关D. 与作为顺序存储结构的数组大小有关12.三个元素按A,B,C的顺序入栈，下列哪一个是不合法的出栈序列？（昭八、A.ABCB.CABC.ACBD.BAC13假定一个顺序循环队列存储于长度为n的一维数组中，其队头和队尾指针分别用front和rear表示，则判断队满的条件是（）A.( rear+1 ) %n=frontB. front+1=rearC. rear= (front-1 ) %nD. rear= (front+1 ) %n14假定一个顺序循环队列的队头和队尾指针分别用front和rear表示，则判队空的条件是（）。A.( fro

5、nt+1 ) %n=rearB. front=rear+1C. front=015.深度为5 （假设空树的深度为0）的二叉树至多有（2的n次方-1）结点。A. 64B. 32C.31D.63D. front=rear16 一个具有n个顶点的无向完全图的边数为（A. n(n+1)/2B. n(n-1)/2C.n(n-1)D.n(n+1)B.对栈不作任何判别D.判别栈元素的类型18.线性表采用链式存储时，其地址（）。A.必须连续B.部分地址必须连续C.必须连续D.连续与否均可17如果以链表作为栈的存储结构，则出栈操作时A.必须判别栈是否满C.必须判别栈是否空19. 一棵完全二叉树上有15个结点，其

6、深度是不超过（）的最大整数。A. 2B. 3C. 4D.AC 项都不对）存20. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 储方式最节省运算时间。A.单链表B.双链表C.带头结点的双循环链表D.容量足够大的顺序表21. 二叉树中第5层上的结点个数最多为A.8B.1522. 深度为5的二叉树至多有（A. 64B. 32_2的k-1次方-1C.16）结点C. 31D. 63D.32#23.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1,则编号为49的结点的左孩子的编号为()。(P124)A.98B.99C.50D.

7、4824.已知广义表的表头为A,表尾为（B,C）,则此广义表为（)A. (A,(B,C)B.(A,B,C)C.(A),B,C)D.(A,B,C)#25.在目标串 T0?n-1：=” xwxxyxy 中”，对模式串 p0?m-1=:xy进行子串定位操作的结果A.0B.2C.3D.526. 如果二叉树的前序遍历结果是12345，后序遍历结果是 24531，那么该二叉树的中序遍历结果是（c） ?A.23145B.32154C.21435D.无法确定27. 已知一棵二叉树的先序遍历结果是ABC则以下哪个序列是不可能的中序遍历结果：（）A. ABCB. BACC. CBAD. CAB29.树最适合于用来

8、表示。A.有序数据元素B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据30.下面的函数PreOrderPrintLeaves（BinTreeBT）按前序遍历的顺序打印出二叉树BT的所有叶子结点。则下列哪条表达式应被填在空中？voidPreOrderPrintLeaves（BinTreeBT）if（BT）if（）printf（"%d",BT->Data）;PreOrderPrintLeaves(BT->Left);PreOrderPrintLeaves(BT->Right);B. !BT->RightC . !BT->L

9、eft31. 对二叉排序树进行什么遍历可以得到从小到大的排A.前序遍历B.后序遍历C.中序遍历32. 已知 8 个数据元素为(34, 76, 45, 18, 26, 54, 92, 65) 最后两层上的结点总数为：A. BT->Data!=OD. !(BT->Left&&BT->Right)序序列？D.层次遍历，按照依次插入结点的方法生成一棵二叉排序树后,33. 由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树,A. 23B. 37C. 4434. 设一段文本中包含字符 码后，文本所占字节数为：A. 40B. 36C. 25该树的带权路径长度为:D.

10、46a,b,c,d,eD. 1235. 线性表、堆栈、队列的主要区别是什么？ A.线性表用指针，堆栈和队列用数组C.线性表和队列都可以用循环链表实现，但堆栈不能 是顺序表中第一个元素的存储地址是A. 100B. 105C. 10836设一个堆栈的入栈顺序是是：A. 1B. 3 C. 5 37、带头结点的单链表A. h=NULL;B38. 线性表1、,其出现频率相应为3,2,5,1,1。则经过哈夫曼编B.堆栈和队列都是插入、删除受到约束的线性表D.堆栈和队列都不是线性结构，而线性表100,每个元素的长度为D. 1102、3、4、5。若第一个出栈的元素是D. 1或者5h为空的判定条件是：.h-&g

11、t;next=NULL;C.L在什么情况下适用于使用链式结构实现？A.需不断对L进行删除插入B.需经常修改L中的结点值40. 对于一个具有NN个结点的单链表，在给定值为A. O(1)B. O(N/2)C. O(N)41. 数组A1.5,1.6每个元素占5个单元，存单元中，则元素 A5,5的地址为：A. 1120B. 1125C. 11402,则第5个元素的地址是()。4,则最后一个出栈的元素必定h->next=h;D.(1分)C. L中含有大量的结点h!=NULL;D. L中结点结构复杂xx的结点后插入一个新结点的时间复杂度为D. O(NA2)将其按行优先次序存储在起始地址为D. 114

12、542. 将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层(设根为第多是：A. 311B. 823C. 184744具有65个结点的完全二叉树其深度为(根的深度为A. 845下面(A. Prim算法46.堆是一种(A.插入1000的连续的内1层)有100个叶结点，则该完全二叉树的结点个数最D.无法确定1)：B. 7C. 6D. 5)算法适合构造一个稠密图G的最小生成树。B.

13、Kruskal 算法C. Floyd 算法)排序。B.选择C.交换时间复杂度和空间复杂度。1. 一个算法的好坏取决于该算法的2.克鲁斯卡尔算法的时间复杂度为O (eloge)最小生成树。D.Dijkstra 算法D.归并,适合求稀疏图3. 设单链表的结点结构为（data , *next ），已知指针p指向单链表中X结点，指针q指向y的新结点，若将结点y插入到结点x之后，则需要执行以下两条语句_ q >next=p >next和p >next=q4. 图的遍历方式有广度优先遍历和深度优先遍历两种。5. 在有序表（12,24,36,48,602,84）中二分查找关键字72时所需进

14、行的关键字比较次数为。26. 已知广义表 A=（a,b,c）,（d,e,f）, 则运算 head（head（tail（ A） ）=d7. 由带权为3,9,6,2,5 的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_55&一个哈夫曼（Huffman）树有19个结点，则其叶结点的个数是109. 静态查找表与动态查找表的根本区别在于施加在其上的操作不一样01 0可以看出，该图共有 3顶点。如果是无向图，则共有10 110. 从邻接矩阵A=< 1 0 011. 无向完全图具有 n（n条边。12. 广义表 A（ a,b,c ），（ d,e,f ）的表尾为 。13. 对于给定的n个元素，可

15、以构造出的逻辑结构有（集合）、（线性结构）、（树结构）、（图结构）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

16、），Pop（S），Pop（S）。18、一棵二叉树有67个结点，这些结点的度要么是 0,要么是2。这棵二叉树中度数为 2的结点有33个。19. 一棵深度为6的满二叉树有31个分支结点和32个叶子。20. 克鲁斯卡尔算法的时间复杂度为（ O（eloge），适合求（稀疏图）的最小生成树。21. 两个字符串相等的充分必要条件是（长度相等，并且各个对应位置上的字符都相等）。22写出模式串p= “ abaabcac的” next函数值序列为（01122312）23、设有一稀疏图 G,则G采用（邻接表）存储结构较省空间。24. 在对一组记录（54, 38, 96, 23, 15, 72, 60, 45, 8

17、3）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置至少需比较（3）次。25在有n个结点的二叉链表中，空链域的个数为_n + 1_。1. 已知二叉树的前序ABCDEFGHI和中序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）建立一个排

18、序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度6设关键字的输入次序为45, 24, 53, 45, 12, 24, 90。画出生成的二叉排序树的存储结构图，并求它的长度。5分)。7 画出下列广义表(),a,(b,c),(),d),(e)8试画出具有3个结点的二叉树所有不同形态(1)每个顶点的入/出度;(2)邻接矩阵；(3)邻接表；(4)逆邻接表。10对于所示的有向带权图9已知如图所示的有向图，请给出该图的：(1) 作为AOE写出从源点A到汇点G的所有路径并指出哪一条路径是关键路径(2) 将该图作为 AOE网，试写出C的最早发生时间及活动FC的最晚开始时间。(3) 写出A点到各顶点的最短路径。11已知图6.32所示的有向图，请给出: 每个顶点的入度和出度； 邻接矩阵； 邻接表； 逆邻接表。图6.33 无向网图6.32有向图12已知如图6.33所示的无向网，请给出：(1) 邻接矩阵；(2) 写出深度优先搜索顺序和广度度优先搜索顺序