数据结构复习题.docx
- 文档编号:11504154
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:64
- 大小:296.61KB
数据结构复习题.docx
《数据结构复习题.docx》由会员分享,可在线阅读,更多相关《数据结构复习题.docx(64页珍藏版)》请在冰点文库上搜索。
数据结构复习题
一.判断题(下列各题,正确的请在前面的括号内打√;错误的打×)
第1章
(√)
(1)数据的逻辑结构与数据元素本身的内容和形式无关。
(√)
(2)一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
(×)(3)数据元素是数据的最小单位。
(×)(4)数据项是数据的基本单位。
(×)(5)数据的逻辑结构和数据的存储结构是相同的。
(√)(6)数据的逻辑结构是各数据元素之间的逻辑关系,是用户按使用需要而建立的。
(√)(7)数据的物理结构是指数据在计算机内实际的存储形式。
(√)(8)从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。
(√)(9)数据的存储结构是数据的逻辑结构的存储映像。
(√)(10)算法是对解题方法和步骤的描述。
第2章
(×)
(1)链表的物理存储结构具有同链表一样的顺序。
(×)
(2)链表的每个结点都恰好包含一个指针域。
(√)(3)线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此属于同一数据对象。
(×)(4)链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。
(×)(5)顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
(√)(6)数组元素的存储位置是下标的线性函数。
(√)(7)在单链表中,元素的存储位置用指针联系,所以可以从头结点开始查找任何一个元素。
(×)(8)顺序存储线性表的插入和删除操作不需要付出很大的代价,因为平均每次移动仅一半的元素。
(×)(9)顺序存储方式的优点是存储密度大,插入、删除效率高。
(×)(10)在单链表中,要取得某个元素,只要知道该元素的指针即可,因此单链表是随机存取的存储结构。
第3章
(√)
(1)大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。
(×)
(2)快速排序在任何情况下都比其它排序方法速度快。
(√)(3)快速排序算法在每一趟排序中都能找到一个元素放在其最终位置上。
(×)(4)如果某种排序算法不稳定,则该排序方法就没有实际应用价值。
(√)(5)对n个记录的进行快速排序,所需要的平均时间是O(nlog2n)。
(×)(6)冒泡排序是不稳定的排序。
(√)(7)冒泡排序的时间复杂度是O(n2)。
(×)(8)堆排序所需的时间与待排序的记录个数无关。
(√)(9)对快速排序来说,初始序列为正序或反序都是最坏情况。
(√)(10)对于n个记录的集合进行归并排序,所需的平均时间为O(nlog2n)。
第4章
(√)
(1)栈是运算受限制的线性表。
(√)
(2)在栈空的情况下,不能作出栈操作,否则产生下溢出。
(×)(3)栈一定是顺序存储的线性结构。
(×)(4)空栈就是所有元素都为0的栈。
(×)(5)一个栈的输入序列为:
A,B,C,D,可以得到输出序列:
C,A,B,D。
(√)(6)一个栈的输入序列为:
A,B,C,D,通过入出栈操作可以输出序列:
A,B,C,D。
(×)(7)在C或C++语言中设顺序栈的长度为MAXLEN,则top=MAXLEN时表示队满。
(√)(8)链栈与顺序栈相比,其特点之一是通常不会出现栈满的情况。
(√)(9)在栈中插入或删除一个元素应遵守的“后进先出”的原则。
(√)(10)进位制的换算算法是栈的应用。
(√)(11)队列是限制在两端进行操作的线性表。
(√)(12)判断顺序队列为空的标准是头指针和尾指针均指向同一个结点。
(×)(13)在链队列做出队操作时,会改变front指针的值。
(√)(14)在循环队列中,若尾指针rear大于头指针front,其元素个数为rear-front。
(√)(15)队列是一种“先进先出”的线性表。
(×)(16)在循环链队列中无上溢出现象。
(×)(17)栈和队列都是顺序存储的线性结构。
(√)(18)栈和队列都是属于线性结构。
(×)(19)顺序队和循环队的队满和队空的判断条件是一样的。
(√)(20)在队列中插入或删除一个元素应遵守的”先进先出”的原则。
第5章
(×)
(1)串的长度是指串中不同字符的个数。
(×)
(2)串是n个字母的有限序列。
(√)(3)空串不等于空格串。
(×)(4)如果两个串含有相同的字符,则说明它们相等。
(×)(5)如果一个串中所有的字母均在另一个串中出现,则说明前者是后者的子串。
(√)(6)串的堆分配存储是一种动态存储结构。
(×)(7)“DT”是“DATA”的子串。
(×)(8)空串与空格串是相同的。
(×)(9)串中任意个字符组成的子序列称为该串的子串。
(√)(10)子串的定位运算称为模式匹配。
(√)(11)n维的多维数组可以视为n-1维数组元素组成的线性结构。
(√)(12)稀疏矩阵中非零元素的个数远小于矩阵元素的总数。
(ㄨ)(13)若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算。
(ㄨ)(14)在稀疏矩阵的三元组表表示法中,每个三元组表示矩阵中数据元素的行号、列号和值。
(ㄨ)(15)上三角矩阵主对角线以上(不包括主对角线中的元素),均为常数C。
(√)(16)对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。
(ㄨ)(17)任何矩阵都可以进行压缩存储。
(√)(18)在稀疏矩阵的三元组表表示法中,每个三元组表示矩阵中非零元素的行号、列号和值。
(√)(19)数组元素可以由若干个数据项组成。
(√)(20)稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。
第6章
(√)
(1)树结构中每个结点最多只有一个直接前驱。
(×)
(2)完全二叉树一定是满二查树。
(√)(3)由树转换成二叉树,其根结点的右子树一定为空。
(√)(4)在前序遍历二叉树的序列中,任何结点的子树的所有结点都是直接跟在该结点之后。
(×)(5)用一维数组来存储二叉树时,总是以前序遍历存储结点。
(×)(6)已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树,因为不知道根结点是哪一个。
(√)(7)二叉树的前序遍历中,任意一个结点均处于其子女结点的前面。
(√)(8)由二叉树的前序遍历序列和中序遍历序列,可以推导出后序遍历的序列。
(√)(9)不使用递归,也可以实现二叉树的前序、中序和后序遍历。
(√)(10)在完全二叉树中,若一个结点没有左孩子,则它必然是叶子结点。
第7章
(√)
(1)图可以没有边,但不能没有顶点。
(×)
(2)在无向图中,(V1,V2)与(V2,V1)是两条不同的边。
(×)(3)邻接表只能用于有向图的存储。
(√)(4)用邻接矩阵法存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关。
(√)(5)一个图的邻接矩阵表示是唯一的。
(×)(6)有向图不能进行广度优先遍历。
(√)(7)一个图的最小生成树是该图所有生成树中权最小的生成树。
(√)(8)存储无向图的邻接矩阵是对称的,因此只要存储邻接矩阵的上三角(或下三角)部分就可以了。
(×)(9)有向图的邻接矩阵一定是对称的。
(×)(10)一个图的深度优先遍历的序列是唯一的。
第8章
(√)
(1)二分查找法要求待查表的关键字值必须有序。
(√)
(2)哈希法是一种将关键字转换为存储地址的存储方法。
(×)(3)在二叉排序树中,根结点的值都小于孩子结点的值。
(×)(4)对有序表而言采用二分查找总比采用顺序查找法速度快。
(√)(5)二叉排序树是一种特殊的线性表。
(√)(6)散列存储法的基本思想是由关键字的值决定数据的存储地址。
(√)(7)哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。
(√)(8)一般说来用哈希函数得到的地址,冲突不可能避免,只能尽可能减少。
(×)(9)选择好的哈希函数就可以避免冲突的发生。
(×)(10)在二叉排序树上删除一个结点时,不必移动其它结点,只要将该结点的父结点的相应的指针域置空即可。
二.填空题
第1章
1.数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。
2.数据的存储结构形式包括:
顺序存储、链式存储、散列存储、索引存储。
3.数据结构按逻辑结构可分为两大类,它们分别是:
线性结构和非线性结构。
4.一个算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模n的函数。
5.数据结构有逻辑结构和存储结构两种结构。
6.数据的存储结构形式包括:
顺序存储、链式存储、散列存储、索引存储。
7.一个算法的效率可分为时间效率和空间效率。
8.数据元素是数据的基本单位。
9.数据结构主要研究数据的逻辑结构、存储结构和算法。
11.数据的逻辑结构是独立于计算机的。
12.数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系的有限集合。
13.树形结构结构中的元素之间存在一对多的关系。
14.若一个算法中的语句频度之和为T(n)=125n+3nlog2n,则算法的时间复杂度为O(nlog2n)。
15.数据结构主要研究数据的逻辑结构、存储结构和算法。
第2章
1.顺序表中逻辑上相邻的元素在物理位置上必须相连。
2.在单链表中要在已知结点*P之前插入一个新结点,需找到*P的直接前趋结点的地址,其查找的时间复杂度为O(n)。
3.线性表是n个结点的有限集合。
4.链表相对于顺序表的优点有插入、删除方便;缺点是存储密度小。
5.链表相对于顺序表的优点有插入、删除方便;缺点是存储密度小。
6.顺序表相对于链表的优点是:
节省存储和随机存取。
7.对于一个具有n个结点的单链表,在已知p所指结点后插入一个新结点的时间复杂度是O
(1)。
8.在链表中逻辑上相邻的元素的物理位置不必相连。
9.线性表中第一个结点没有直接前趋,称为开始结点。
10.在顺序表中访问任意一个结点的时间复杂度均为O
(1)。
11.在n个结点的单链表中要删除已知结点*P,其时间复杂度为O
(1)。
12.在单链表中需知道头指针才能遍历整个链表。
13.在一个单链表中,在指针p所指向的结点之后插入指针s所指向的结点时,应执行s->next=p->next和p->next=s操作。
14.在一个长度为n的顺序表中,如果要在第i个元素前插入一个元素,要后移n-i+1个元素。
15.在双向链表中,每个结点都有两个指针域,它们一个指向其前趋结点,另一个指向其后继结点。
第3章
1.根据被处理的数据在计算机中使用不同的存储设备,排序可分为:
内排序和外排序。
2.评价排序算法优劣的主要标准是时间复杂性和算法所需的附加空间。
3.插入排序、堆排序、归并排序中,排序是不稳定的有:
堆排序。
4.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较3次。
5.对n个关键字进行冒泡排序,其可能的最小比较次数为:
n-1次。
6.内排序是指整个排序过程,全部在计算机的内存中进行。
7.大多数排序算法都有两个基本的操作:
比较和移动。
8.在插入排序和选择排序中,若初始数据基本正序,则选用插入排序较好。
9.在排序前,关键字值相等的不同记录,排序后相对位置变化的排序方法,称为不稳定的排序方法。
10.若原始数据接近无序,则选用快速排序最好。
11.对于n个记录的集合进行归并排序,所需要的平均时间为:
O(log2n)。
12.在插入排序、归并排序、快速排序中,排序是不稳定的有:
快速排序。
13.对一组记录(54,35,96,21,12,72,60,44,80)进行直接选择排序时,第四次选择和交换后,未排序记录是54,72,60,96,80。
14.对于n个记录的集合进行,若对其进行快速排序,在最坏的情况下所需要的时间是O(n2)。
15.在最坏情况下,在第i趟直接插入排序中,要进行i-1次关键字的比较。
第4章
1.在栈中存取数据遵从的原则是:
后进先出。
2.在有n个元素的栈中,进栈操作的时间复杂度为O
(1)。
3.后进先出的线性表称为栈。
4.在顺序栈中,当top=MAXLEN-1时,表示栈满。
5.栈是输入、输出受限制的线性表。
6.在有n个元素的栈中,出栈操作的时间复杂度为O
(1)。
7.在栈结构中,允许插入、删除的一端称为栈顶。
8.顺序栈S存在数组S->data[0..MAXLEN-1]中,出栈操作时要执行的语句有:
S->top--。
9.在顺序栈中,当栈顶指针top=-1时,表示栈空。
10.向一个栈顶指针为top的链栈插入一个新结点*p时,应执行p->next=top;和top=p;操作。
11.同一栈的各元素的类型相同。
12.栈只能在栈顶插入和删除元素。
13.已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。
14.若进栈的次序是A、B、C、D、E,执行三次出栈操作以后,栈顶元素为B。
15.从一个栈删除元素时,首先取出栈顶元素,然后再移动栈顶指针。
16.在队列中存取数据应遵从的原则是先进先出。
17.设长度为n的链队列用单循环链表表示,若只设头指针,则入队操作的时间复杂度为
O(n)。
18.在队列中,允许插入的一端称为队尾。
19.设长度为n的链队列用单循环链表表示,若只设头指针,则出队操作的时间复杂度为
0
(1)。
20.设循环队列的头指针front指向队头元素,尾指针rear指向队尾元素后的一个空闲元素,队列的最大空间为MAXLEN,则队空的标志为front==rear。
21.队列在进行出队操作时,首先要判断队列是否为空。
22.设循环队列的头指针front指向队头元素,尾指针rear指向队尾元素后的一个空闲元素,队列的最大空间为MAXLEN,则队满标志为front==(rear+1)%MAXLEN。
23.在一个链队列中,若队头指针为front,队尾指针为rear,则判断该队列只有一个结点的条件为:
front==rear&&front<>NULL。
24.队列结构的元素个数是可变的。
25.设长度为n的链队列用单循环链表表示,若只设尾指针,则出队操作的时间复杂度为
0
(1)。
26.设长度为n的链队列用单循环链表表示,若只设尾指针,则入队操作的时间复杂度为
0
(1)。
27.链队列为空时,LQ->front->next=NULL。
28.设循环队列的头指针front指向队头元素,尾指针rear指向队尾元素后的一个空闲元素,队列的最大空间为MAXLEN,当rear 29.向一个循环队列中插入元素时,首先要移动队尾指针,然后再向指针所指位置写入新的元素。 30.队列Q经过InitQueue(Q);InQueue(Q,a);InQueue(Q,b);GetHead(Q,x)后,x的值是a。 第5章 1.长度为零的字符串称为空串。 2.在串的运算中,EqualStr(aaa,aabb)的值为<0。 3.串的顺序存储结构简称为顺序串。 4.串的链式存储结构简称为链式串。 5.求子串函数SubStr("Todayis30July,2005",13,4)的结果是: July。 6.设S="A: /document/",则len(s)=_20。 7.由零个或多个字符组成的有限序列称为字符串(或串)。 8.字符串按存储方式可以分为: 顺序存储、链接存储和堆分配存储。 9.设S=“A: /mydocument/”,则strlen(S)=23。 10.在空串和空格串中,长度不为0的是空格串。 11.串顺序存储紧凑格式的优点是: 空间利用率高,对串的字符处理效率低。 12.两个串相等是指两个串相长度等,且对应位置的字符都相同。 13.串顺序存储紧凑格式的缺点是对串的字符处理效率低。 14.模式匹配成功的起始位置称为: 有效位移。 15.所有模式匹配不成功的起始位置称为: 无效位移。 16.多维数组的顺序存储方式有行优先顺序存储和列优先顺序存储两种。 17.同一数组中各元素的长度相等。 18.在多维数组中,数据元素的存放地址可以直接通过地址计算公式算出,所以多维数组是一种随机存取结构。 19.在n维数组中的每一个元素最多可以有n个直接前驱。 20.输出二维数组A[m][n]中所有元素值的时间复杂度为O(m*n)。 数组元素a[0..2][0..3]的实际地址上2000,元素长度是4,则Loc[1,2]= 2024。 21.数组的三元组存储是对稀疏矩阵的压缩存储 22.稀疏矩阵的三元组有3列。 23.稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的行数。 阶对称矩阵,如果只存储下三角元素,只需要n(n-1)/2个存储单元。 25.稀疏矩阵A如下图所示,其非零元素存于三元组表中,三元组(4,1,5)按行优先顺序存储在三元组表的第6项。 26.稀疏疏矩阵的压缩存储方法通常有三元组表和十字链表两种。 27.n阶下三角矩阵,因为对角线的上方是同一个常数,需要n(n-1)/2+1个存储单元。 28.稀疏矩阵中有n个非零元素,则三元组有n行。 29.稀疏矩阵的三元组中第2列存储的是数组中非零元素所在的列数。 30.稀疏矩阵的三元组中,第3列存储的是稀疏数组中的非零元素。 第6章 1.在树中,一个结点所拥有的子树数称为该结点的度。 2.一棵含有n个结点的完全二叉树,它的高度是|log2n|+1。 (下取整) 3.度为零的结点为叶子结点(或叶结点)。 4.一棵深度为h的完全二叉树上的结点总数最少为2h-1个。 5.树内各结点度的最大值称为树的度。 6.一棵深度为h的完全二叉树上的结点总数最多为2h-1个。 7.树中结点的最大层次称为树的深度(或高度)。 8.三个结点可以组成2种不同形态的树。 9.由树转换成二叉树时,其根结点没有右子树。 10.有20个结点的完全二叉树,编号为10的结点的左儿子结点的编号是20。 11.在树中,一个结点的直接子结点的个数称为该结点的度。 12.由二叉树的后序和中序遍历序列,可以唯一确定一棵二叉树。 13.给定如下图所示的二叉树,其前序遍历序列为: ABEFHCG。 14.给定如下图所示的二叉树,其层次遍历序列为: ABCEFGH。 15.将一棵完全二叉树按层次编号,对于任意一个编号为i的结点,该结点右孩子的编号为: 2*i+1。 第7章 1.图有: _邻接矩阵_和邻接表等存储结构。 2.n个顶点e条边的图若采用邻接矩阵存储,深度优先遍历算法的时间复杂度为: O(n2)。 3.图的遍历有: 深度优先搜和_广度优先搜__等方法。 4.n个顶点e条边的图若采用邻接矩阵存储,则空间复杂度为: _O(n2)__。 5.图有: 邻接矩阵和邻接表等存储结构。 6.若图G中每条边都_无方向,则G为无向图。 7.在具有n个顶点的图的生成树中,含有n-1条边。 8.有向图的边也称为_弧___。 9.图的邻接矩阵表示法是表示__顶点____之间相邻关系的矩阵。 10.有向图G用邻接矩阵存储,其第i行的所有元素之和等于顶点i的__出度____。 11.图的深度优先遍历序列___不是_____唯一的。 12.设有一稀疏图G,则G采用_邻接表____存储比较节省空间。 13.从图中某一顶点出发,访遍图中其余顶点,且使每一顶点仅被访问一次,称这一过程为 图的遍历(或遍历)。 14.遍历图的两种基本方法是: 深度优先遍历和广度优先遍历。 15.有向图的邻接表表示适于求顶点的出度。 第8章 1.顺序查找法,表中元素可以任意存放。 2.散列表查找法的平均查找长度与元素个数n无关。 3.快速排序是对冒泡排序的一种改进。 4.在哈希函数H(key)=key%P中,P一般应取质数。 5.二分查找的存储结构仅适用于顺序存储结构,而且关键字有序的。 6.在分块查找方法中,首先查找索引,然后再查找相应的块。 7.二分查找法,表中元素必须按关键字有序存放。 8.在分块查找方法中,表中元素每块内的元素可以任意存放,块与块之间必须有序存放。 9.顺序查找、二分查找、分块查找都属于静态查找。 10.顺序查找法,其平均查找长度为: (n+1)/2。 11.理想情况下,在散列表中查找一个元素的时间复杂度为: O (1)。 12.散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 13.二叉排序树是一种动态查找表。 14.处理冲突的两类主要方法是开放定址法和拉链法(或链地址法)。 15.设有100个元素,用二分查找时,最少的比较次数是1次。 三.选择题 第1章 1.数据结构通常是研究数据的(A)及它们之间的相互联系。 A.存储结构和逻辑结构B.存储和抽象C.联系和抽象D.联系与逻辑 2.执行下列语句的时间复杂度为: (B)。 s=0; for(i=1;i<=n;i++) s=s+i; A.O (1)B.O(n)C.O(n2)D.O(n3) 3.数据结构中,在逻辑上可以把数据结构分成: (C)。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 4.某程序的时间复杂度为(3n+log2n+n2+15)其数量级表示为(B) A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n) 5.非线性结构的数据元素之间存在(B)。 A.一对多关系B.多对多关系C.多对一关系D.一对一关系 6.下列时间复杂度中最坏的是(D) A.O (1)B.O(n)C.O(log2n)D.O(n2) 7.以下任何两个结点之间都没有逻辑关系的是(D) A.图型结构B.线性结构C.树型结构D.集合 8.链接存储的存储结构所占存储空间(A)。 A.分两部分,一部分存放结点的值,另一部分存放表示结点间关系的指针 B.只有一部分,存放结点值 C.只有一部分,存储表示结点间关系的指针 D.分两部分,一部分存放结点值,另一部分存放结点所占单元素 9.一个存储结点存放一个(B) A.数据项B.数据元素C.数据结构D.数据类型 10.下列时间复杂度中最好的是(A) A.O (1)B.O(n)C.O(log2n)D.O(n2) 11.每一个存储结点不仅含有一个数
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)