数据结构复习题库.docxVIP

数据结构复习题库填空题1.1绪论1、数据中指输入到计算机中并能被计算机程序处理的符号的总称。2、数据对象是具有相同性质的数据元素的集合，它是数据的子集。3、数据结构：带结构的数据元素的集合；是指数据以及相互之间的联系，主要描述数据及其关系在计算机内如何表示、存取和处理。 4、数据的逻辑结构是指数据元素之间逻辑关系的整体，它与数据的存储结构无关，是独立于计算机的。数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。5、数据结构在计算机意义下，包含三个方面的内容：（1）数据元素之间的逻辑关系；是指数据及其相互之间的关系,它是根据人们解决实际问题的需要和问题本身所含数据之间的内在联系而抽象出来的 ；（2）数据的存储方式；（3）数据的运算。6、数据的逻辑结构可归结为以下四类: 线性结构、树形结构、图状结构、集合结构7、数据的存储方式可归结为以下四类: 1）顺序存储 2）链接存储 3）索引存储 4）散列存储。8、抽象数据类型(Abstract Data Type 简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。抽象数据类型可以定义一个完整的数据结构。算法9、算法的五个重要特性是指(1)有穷性、(2)确定性：(3)可行性、(4)输入、(5)输出；其中有穷性是指：执行有限步后能够在有限时间内(合理)结束；确定性是指：每一步都应确切地、无二义性地定义；(3)可行性：每条指令可以执行且有正确的结果。10、评价一个算法的好坏主要依据：1正确性 2、可读性 3、健壮性 4、高效率与低存储量需求 。11、算法效率的衡量方法有：事后统计法 和事前分析估算法 ；事前估算法主要考虑：（1）算法选用的策略、（2）、问题的规模 。12、算法时间复杂度是算法中基本运算重复执行次数多少的量度。记作O(n)，空间复杂度作为实现算法所需的辅助存储空间的大小，记作S(n)=O(f(n))。1.2线性表1、线性表是具有相同特性的数据元素的一个有限序列。其特征有三：所有元素类型相同、线性表是由有限个数据元素组织、线性表中的数据元素与位置有关的，这一点表明线性表不同于集合，线性表中的每一个元素都有一个对应的序号，线性表中元素可以重复出现。2、线性结构特点：有“头”元素有“尾”元素，中间的元素有“前驱”元素和“后继”元素。3、线性表的顺序表示是指：用一组地址连续的存储单元依次存放线性表中的数据元素。4、对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为O（1），在表尾插入元素的时间复杂度为O（n）。5、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为____（38，56，25，60，42，74） 。 a 0 1 2 3 4 5 6 7 8? 60 56 42 38? 74 25? 4 3 7 6 2 0 1?datanext4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__ HL→next =NULL； _和_ HL=HL→next___。1.3栈和队列1、栈又称堆栈：是一个受限的线性表，其限制是仅允许在表的一端进行插入与删除。通常把对栈进行操作的一端称为栈顶，另一端称为栈底。向栈顶插入一个新元素称为入栈或称进栈，从栈顶删除一个元素，称为出栈或退栈。2、?队列的插入操作是在队列的队尾进行，删除操作是在队列的队首进行。3、?当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是top==0_。4、后缀表达式运算规则：运算符在式中出现的顺序恰为表达式的运算顺序，每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。5、中缀表达式a*(b+c)-d/f 的后缀表达式是： abc+*df/- 。6、当堆栈采用顺序存储结构时，栈顶元素的值可用S.stack [S.top] 表示；当堆栈采用链接存储结构时，栈顶元素的值可用HS→data表示。1.4稀疏矩阵与广义表1、稀疏矩阵的三元组表示法是指用非零元素所在的行、列以及值组成的三元组来表示一个非零元素2、广义表A= (a,(b,c),((d,e,()),f)),则它的深度为 4 ，它的长度为 3 。1.5树1.6图1.7查找1、静态查找表是仅作查询和检索的查找表，静态查找表正常有以下几种形式：顺序查找表、有序查找表 、静态查找树表、索引顺序表 2、动态查找表主要是指：若将“查询”结果为不在查找表中的元素插入查找表；或者，从查找表中删除其“查询”结果为在查找表中的数据元素。1.8排序1、当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用 ___快速 _____排序；当待排序的记录数较大，存储空间允