数据结构复习题

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第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=-