复习题数据结.docx

1。数据的（）包括集合、线性、树和图4种基本类型
A. 存储结构B.逻辑结构C.基本运算D.算法描述
2. 对一个长度为n的顺序表，在第i个元素（1<i<n+1）之前插入一个新元素时需向右移动（）个元素。
A . n一iB. n一i+1C . n一i—1D . i
3下面程序的时间复杂度为（）。
For （ i=0; i〈m ; i++）
For（j=0 j〈n; j++）
A [i] [j]=i*j；
A。0 （m2）B. O（n2） C. O（n* m） D.O （n+m ）
4长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）。
A. 0（0）B. 0（1）C.0 （n）D. 0（n2）
5.数据结构就是研究（）。
A .数据的逻辑结构B .数据的存储结构
C .数据的逻辑结构和存储结构
D.数据的逻辑结构、存储结构及其数据在运算上的实现
6下面关于算法的说法，错误的是（）。
A. 算法最终必须由计算机程序实现
B. 为解决某问题的算法和为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上三种说法都错误
7线性表L=（a1,a2 , an,）下列说法正确的是（）.
A .每个元素都有一个直接前驱和一个直接后继
B. 线性表中至少要有一个元素
C. 表中所有元素的排列顺序必须是由小到大或由大到小
D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继
8.下面关于线性表叙述错误的是（）。
A. 线性表采用顺序存储，必须占用一段地址连续的单元
B. 线性表采用顺序存储，便于进行插入和删除操作
C. 线性表采用链式存储，不必占用一段地址连续的单元
D. 线性表采用链式存储，便于进行插入和删除操作
9用链表表示线性表的优点是（）
A.便于随机存取B.存储空间比顺序存储方式少
C.便于插入和删除D.数据元素的存储顺序与逻辑顺序相同
10若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省
时间。
A.单链表B.双链表C.单向循环D.顺序表
11。若队列采用顺序存储结构，元素的排列顺序（）
A.与元素值的大小有关B.由元素进入队列的先后顺序决定
C.与队头指针和队尾指针的取值有关D.与作为顺序存储结构的数组大小有关
12。三个元素按照A,B,C的顺序入栈，下列哪一个是不合法的出栈序列？（）
A. ABCB。 CABC。 ACBD 。 BAC
13假定一个顺序循环队列存储于长度为n的一维数组中，其队头和队尾指针分别用fron和 rear表示，则判断队满的条件是（）
A (rear+1)%n==front
B. front+1==rear

C. rear==（front-1 %nD. rear==（front+）%n
14假定一个顺序循环队列的队头和队尾指针分别用fron和 rear表示，则判队空的条件是（）.
A. （front+1 %n==rearB. front==rear+1
C. front==0D . front==rear
15。深度为5（假设空树的深度为0）的二叉树至多有（2的n次方-1 ）结点.
A. 64B. 32C. 31D. 63
16 一个具有n个顶点的无向完全图的边数为（）
A . n （ n+1 ） /2B. n（ n—1 ） /2C. n （ n-1）D . n（n+1）
17如果以链表作为栈的存储结构，则出栈操作时（c ）
A.必须判别栈是否满B.对栈不作任何判别
C.必须判别栈是否空D.判别栈元素的类型
18。 线性表采用链式存储时，其地址（）。
A.必须连续 B.部分地址必须连续
C.必须连续 D.连续与否均可
19。一棵完全二叉树上有15个结点，其深度是不超过（）的最大整数。
A. 2B. 3C. 4D.A~C 项都不对
20。 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间.
A.单链表B-双链表C.带头结点的双循环链表D.容量足够大的顺序表
21。二叉树中第5层上的结点个数最多为__2的k—1次方-1__
A.8B.15C.16D.32
22。深度为5的二叉树至多有（）结点。
A. 64B. 32 C. 31D. 63
#23.将一棵有1个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为（）（p124）
A.98Bo 99Co 50D。48
24.已知广义表的表头为A，表尾为（B，C）,则此广义表为（）
A.（A，（B，C））B.（A，B，C） C. （（A），B，C）D. （（ A，B,C））
#25.在目标串T[0.・.n—1]=" xwxxyxy中，对模式串p [ 0.・.m— 1 ] =” xy进行子串定位操作的结果
A.0Bo 2C.3D.5
26. 如果二叉树的前序遍历结果是12345,后序遍历结果是24531，那么该二叉树的中序遍历结果是（c ） ?
A.23145B. 32154C.21435。.无法确定
27。已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：（）
A. ABC B. BAC C. CBAD. CAB
29. 树最适合于用来表示。
A.有序数据元素 B.无序数据元素C.元素之间无联系的数据D.元素之间具有分支层次关系的数据
30. 下面的函数PreOrderPrintLeaves （ BinTree BT）按前序遍历的顺序打印出二叉树BT的所有叶子结点。则下列哪条表达式应被填在空中？
void PreOrderPrintLeaves （ BinTree BT ）
{ if （BT） {
if （ ） printf （” ％d”，BT-〉Data）;
PreOrderPrintLeaves( BT— Left);
PreOrderPrintLeaves( BT— Right );
)
)
A. BT->Data ! = 0 B. !BT-〉Right C. !BT->Left D. ! (BT—〉Left && BT—>Right)
31. 对二叉排序树进行什么遍历可以得到从小到大的排序序列？
A.前序遍历B.后序遍历 C.中序遍历 D.层次遍历
32. 已知8个数据元素为(34, 76, 45, 18, 26,54, 92, 65 )，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为：
A. 1B. 2C. 3D. 4
33. 由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：
A. 23 B. 37 C. 44 D. 46
34. 设一段文本中包含字符｛a, b, c, d, e｝,其出现频率相应为｛3, 2, 5, 1, 1｝。则经过哈夫曼编码后，文本所占字节数为：
A. 40 B. 36 C. 25 D. 12
35 .线性表、堆栈、队列的主要区别是什么？
A.线性表用指针，堆栈和队列用数组B.堆栈和队列都是插入、删除受到约束的线性表
C.线性表和队列都可以用循环链表实现，但堆栈不能D.堆栈和队列都不是线性结构，而线性表
是
顺序表中第一个元素的存储地址是1,每个元素的长度为2,则第5个元素的地址是()。
A. 1 B. 105 C. 108 D. 110
36设一个堆栈的入栈顺序是1、2、3、4、5.若第一个出栈的元素是4,则最后一个出栈的元素必定是：
A. 1 B. 3 C. 5 D. 1 或者 5
37、带头结点的单链表h为空的判定条件是：
A. h == NULL; B. h-〉next == NULL; C. h—〉next == 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. 数组A[1..5,1.6 ]每个元素占5个单元，将其按行优先次序存储在起始地址为10的连续的内存单元中，则元素A[5, 5]的地址为：
A. 1120 B. 1125 C. 1140 D. 1145
42 .将｛ 32, 2, 15, 65, 28, 10 ｝依次插入初始为空的二叉排序树。则该树的前序遍历结果是：
A. 2, 10, 15, 28, 32, 65B. 32, 2, 10, 15, 28, 65
C. 10, 28, 15, 2, 65, 32D. 32, 2, 15, 10, 28, 65
43已知一棵完全二叉树的第9层(设根为第1层)有1个叶结点，则该完全二叉树的结点个数最多是：
A. 311 B. 823 C. 1847 D.无法确定
44具有65个结点的完全二叉树其深度为(根的深度为1)：
A. 8 B.7 C.6 D.5
45下面()算法适合构造一个稠密图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和p—>next =q
4. 图的遍历方式有 广度优先遍历和深度优先遍历两种。
5. 在有序表(12,24 36,48,602 84 )中二分查找关键字72时所需进行的关键字比较次数为。2
6. 已知广义表 A= ((a,b,d , (d,e f))则运算 head(head (tail A )) )) = d
7. 由带权为3, 9, 6, 2,5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为一55
8. —个哈夫曼(Huffman)树有19个结点，则其叶结点的个数是10
9. 静态查找表与动态查找表的根本区别在于施加在其上的操作不一样
厂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 0」
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个结点的二叉链表中，空链域的个数为__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尾插法建立单循环链表的函数