数据结构复习题

1、.-简答题比较两个概念的相同和异同1. 简述以下概念：数据，数据元素，数据类型，数据结构，逻辑结构，存储结构，线性结构，非线性结构。数据:是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据类型：是具有相同性质的计算机数据的集合及其在这个数据集合上的一组操作。逻辑结构：指的是数据之间的相互关系，即数据的组织形式。存储结构：数据对象在计算机中的存储表示，也称为物理结构。线性结构：线性结构的逻辑特征是：有且仅有一个开始结点和终端结点，并且所有结点都最多只有一

2、个直接前趋和一个直接后继。非线性结构：非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。2. 比较C语言与pascal语言的差异。C语言和Pascal语言是目前对计算机发展影响较深的两门计算机程序设计语言。两种语言各有特点：Pascal语言是一种结构式程序设计语言，最初是为系统地教授程序设计而发明的，语法严谨，特点是简明化和结构化，适合教学，科学计算等。C语言那么是国际上应用最广泛的计算机中级语言，具有语言简洁紧凑，使用方便灵活及运算符丰富等特点，语法限制不严格，程序设计自由度大，程序可移植性好。3. 试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。开始结点是指链表

3、中的第一个结点，也就是没有直接前趋的那个结点。链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。头结点是在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。4. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定

4、其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。假设线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，假设需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，假设链表的插入和删除主要发生在表的首尾两端，那么采用尾指针表示的单循环链表为宜。5. 为什么在单循环链表中设置尾指针比设置头指针更好 答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，那么开始结点和终

5、端结点的位置分别是rear-next-next 和 rear, 查找时间都是O(1)。假设用头指针来表示该链表，那么查找终端结点的时间为O(n)。6. 比较以下每队术语的区别空串和空格串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。答：空串是指不包含任何字符的串，它的长度为零。空格串是指包含一个或多个空格的串，空格也是字符。串常量是指在程序中只可引用但不可改变其值的串。串变量是可以在运行中改变其值的。主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。静态分配的顺序串是指串的存储空间是确定的，即串

6、值空间的大小是静态的，在编译时刻就被确定。动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，那么这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，假设有不相同的字符存在，那么此次位移就是无效位移(也就是从此位置开始的匹配失败)。串名和串值的区别串变量

7、的名字代表该串的首地址，即第一个字符的地址。串变量的值指的是该变量中存放的字符串。7.比较栈与队列的区别栈与队列的相同点：1.都是线性结构。2.插入操作都是限定在表尾进行。3.都可以通过顺序结构和链式结构实现。、4.插入与删除的时间复杂度都是O1，在空间复杂度上两者也一样。5.多链栈和多链队列的管理模式可以相同。栈与队列的不同点：1.删除数据元素的位置不同，栈的删除操作在表尾进行，队列的删除操作在表头进行。2.应用场景不同；常见栈的应用场景包括括号问题的求解，表达式的转换和求值，函数调用和递归实现，深度优先搜索遍历等；常见的队列的应用场景包括计算机系统中各种资源的管理，消息缓冲器的管理和广度优

8、先搜索遍历等。3.顺序栈能够实现多栈空间共享，而顺序队列不能。6.2 一棵度为2的有序树与一棵二叉树有何区别 答：一棵度为二的有序树与一棵二叉树的区别在于:有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。选择填空判断1. 一个深度为h的满k叉树有如下性质：第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。如果按层次顺序(同层自左至右)从1开始对全部结点编号，问：(1)各层的结点数目是多少 (2)编号为i的结点的双亲

9、结点(假设存在)的编号是多少(3)编号为i的结点的第j个孩子结点(假设存在)的编号是多少 (4)编号为i的结点的有右兄弟的条件是什么 其右兄弟的编号是多少 解：(1) 层号为h的结点数目为kh-1(2) 编号为i的结点的双亲结点的编号是：|_ (i-2)/k _|+1(不大于(i-2)/k的最大整数。也就是(i-2)与k整除的结果以下/表示整除。(3) 编号为i的结点的第j个孩子结点编号是：k*(i-1)+1+j; (4) 编号为i的结点有右兄弟的条件是(i-1)能被k整除右兄弟的编号是i+1. 6.6高度为h的完全二叉树至少有多少个结点至多有多少个结点 解：高度为h的完全二叉树至少有2h-1

10、个结点，至多有2h-1个结点(也就是满二叉树)。2. 在具有n个结点的k叉树(k=2)的k叉链表表示中，有多少个空指针 解：n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1;(1) 前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。(2) 中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。(3) 前序序列和后序序列相同的二叉树是：空二叉树或只有根的二叉树。(4) 前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。3. 在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助

11、答：分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。4. 高度为h的严格二叉树至少有多少个结点至多有多少个结点 答：所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。所以：高度为h的的严格二叉树至少有2h-1个结点；至多有2h-1个结点(即满二叉树)。5. DFS深度优先搜索遍历和BFS广度优先搜索遍历遍历各采用什么样的数据结构来暂存顶点当要求连通图的生成树的高度最小，应采用何种遍历 答：DFS遍历采用栈来暂存顶点。BFS采用队列来暂存顶点。当要求连通图的生成树的高度最小时，应采用BFS遍历。当候选轻边集中的轻边数始终等于1条时，其最小生成树是唯一的。假设关键字是

12、非负整数、快速排序、归并、堆和基数排序啊一个最快假设要求辅助空间为O(1)，那么应选择谁？假设要求排序是稳定的，且关键字是实数，那么应选择谁 答：假设关键字是非负整数，那么基数排序最快；假设要求辅助空间为O(1)那么应选堆排序；假设要求排序是稳定的，且关键字是实数，那么应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。恰好有n(n-1)/2条边的无向图称为无向完全图，恰有nn-1条边的有向图称为有向完全图。假设将图的每条边都赋上一个权，那么称这种带权图为网络。通常权是具有某种意义的数，比如，它们可以表示两个定点之间的距离，耗费等。假设图中的边的数目远远小于n2是即en2，此类图称作稀疏

13、图，这时用邻接矩阵表示节省存储空间；假设e接近于n2准确地说，无向图e接近于nn-1/2，有向图e接近于nn-1，此类图称作稠密图。深度优先搜索遍历类似于树的前序遍历；它的特点是尽可能先对纵深方向进行搜索，故称之为深度优先搜素。广度优先搜索遍历类似于树的按层次遍历；它的特点是尽可能先对横向进行搜索。把生成树各边的权值总和称为生成树的权，并把权最小的生成树称为G的最小生成树。交换排序的基本思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。起泡排序和快速排序属于两种交换排序。算法的时间复杂度是一个函数，它定性描述了该算法的运行时间。这是一个关于代表算法

14、输入值的HYPERLINK s:/baike.baidu /item/%E5%AD%97%E7%AC%A6%E4%B8%B2 t s:/baike.baidu /item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/_blank字符串的长度的函数。时间复杂度常用HYPERLINK s:/baike.baidu /item/%E5%A4%A7O%E7%AC%A6%E5%8F%B7 t s:/baike.baidu /item/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6/_blank大O符号表述，不包括

15、这个函数的低阶项和首项系数。时间复杂度是指执行算法所需要的计算工作量；而空间复杂度是指执行这个算法所需要的存空间。算法的复杂性表达在运行该算法时的计算机所需资源的多少上，计算机资源最重要的是时间和空间即寄存器资源，因此复杂度分为时间和空间复杂度。计算题栈P42页例如：9*3-1+2，属于中缀表达式。我们需要将它转换成后缀表达式：9 3 1 - * 2 +的形式求值。举个例子：“9+(3-1)*3+10/2应该是先化为后缀表达式： 9 3 1-3*+10/+从左到右遍历表达式的每个数字和符号，遇到数字就进栈，遇到符号就将栈顶的两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。解： 9 3

16、 1入栈遇到减号，1,3出栈3-1将结果重新入栈然后遇到3，进栈，遇到*，3和3-1出栈，变成3-1*3，将该结果再进栈，然后遇到的是加号，数据出栈，9+3-1*3，然后将该结果入栈，这里是15，直接将15入栈，同时下面数据遍历到10,2也入栈遍历继续，到/号，出栈栈顶两个数据元素：10/2，结果入栈，最后遍历+，栈顶两个数据元素出栈15+5 =20 ，为最终的结果。或解：画出图为： + + / 9 * 10 2 - 3 3 1 结果为9+(3-1)*3+10/2=20哈夫曼树p112页例题：假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：7，19,2，6,32,3,21,10。试为这8个字母设计哈夫曼编码。前中后序：二叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列