下载文档原格式
数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。
A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。
A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。
A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。
例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。
2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。
3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。
例如构成一个数据元素的字段、域、属性等都可称之为_数据项。
4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。
5、数据的逻辑结构是指数据之间的逻辑关系。
逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。
因此逻辑结构可以看作是从具体问题抽象出来的数学模型。
6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。
存储结构是逻辑结构在计算机里的实现，也称之为映像。
7、数据的运算是指对数据施加的操作。
它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。
常用的有：查找、排序、插人、删除、更新等操作。
8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。
9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。
《数据结构》课程复习资料一、填空题:1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。
2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。
3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。
4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。
5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
8.在快速排序、堆排序、归并排序中，_________排序是稳定的。
9.在有n个叶子结点的哈夫曼树中，总结点数是_______。
10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定_______。
11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。
12.在有n个结点的无向图中，其边数最多为_______。
13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。
14.对矩阵采用压缩存储是为了___ ____。
15.带头结点的双循环链表L为空表的条件是_______。
16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。
17.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。
二、填空题1. 线性表是一种典型的___线性______结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。
3. 顺序表中逻辑上相邻的元素的物理位置__相邻______。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需向__前___移一个位置，移动过程是从_前____向_后____依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过__物理存储位置_____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过__链域的指针值_____决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向___前趋____结点，另一个指向____后继___结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___顺序__存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用__链接___存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置__一定_____相邻，单链表中逻辑上相邻的元素，物理位置___不一定____相邻。
9. 线性表、栈和队列都是__线性_____结构，可以在线性表的___任何___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在___队头____位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为__单链表_______和__双链表_____；而根据指针的联接方式，链表又可分为__循环链表______和__非循环链表______。
11. 在单链表中设置头结点的作用是__使空表和非空表统一______。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为_o(1)_____，在给定值为x的结点后插入一个新结点的时间复杂度为__o(n)_____。
13. 对于一个栈作进栈运算时，应先判别栈是否为__栈满_____，作退栈运算时，应先判别栈是否为_栈空______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为___m____。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
一、填空题1．数据的最小单位是（ C ）。
A. 数据项B. 数据类型C.数据元素D.数据变量2.算法指的是（ D ）。
A．计算机程序 B．解决问题的计算方法C．排序算法 D．解决问题的有限运算序列3．下面关于线性表的叙述错误的是（C ）。
A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D. 线性表采用顺序存储便于插入和删除操作的实现5．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。
A. 2m-1B. 2mC. 2m+1D. 4m6．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。
A. R-FB. F-RC. (R-F+M)％MD. (F-R+M)％M7．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。
A. BADCB. BCDAC. CDABD. CBDA8．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。
A. n(n-1)/2B. n(n-1)C. n2D. n2-19. 满二叉树_______二叉树。
A. 一定是完全B．不一定是完全C．不是D．不是完全10．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。
A. 9B. 10C. 11D. 1211．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
A. n-1B. nC. n+1D. 2n-112．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
A. 2，3，5，8，6B. 3，2，5，8，6C. 3，2，5，6，8D. 2，3，6，5，813.栈和队列的共同特点是( A )。
数据结构填空练习题1.通常从四个方面评价算法的质量：______ _________ 、______ 、_____ 和。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2 ，其数量级表示为_______ 。
3.假定一棵树的广义表表示为A( C，D( E，F，G)，H( I ，J))，则树中所含的结点数为________ 个，树的深度为________ ，树的度为。
4.后缀算式9 2 3 +- 10 2 / - 的值为____ 。
中缀算式( 3+4X) -2Y/3 对应的后缀算式为___________________________ 。
5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，n 个结点的二叉树共有个指针域，其中有_______ 个指针域是存放了地址，有____________ 个指针是空指针。
6.对于一个具有n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有____ 个和______ 个。
7.AOV 网是一种_______________ 的图。
8.在一个具有n 个顶点的无向完全图中，包含有条边，在一个具有n 个顶点的有向完全图中，包含有_____ 条边。
9.假定一个线性表为(12,23,74,55,63,40) ，若按Key % 4 条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为__________ 、_________________ 、 ___________________ 和_______________________ 。
10.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度11.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_______ ，整个堆排序过程的时间复杂度为_____ 。
12.在快速排序、堆排序、归并排序中，______ 排序是稳定的。
第一章绪论一．选择题1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。
①A．算法B．数据元素C．数据操作D．逻辑结构②A．操作B．映象C．存储D．关系2．算法分析的目的是①，算法分析的两个主要方面是②。
①A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性②A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为A．逻辑结构B．顺序存储结构C．链表存储结构D．以上都不对4．数据结构中，在逻辑上可以把数据结构分成：( ）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（）。
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示6．数据结构研究的内容是（）。
A．数据的逻辑结构B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面7．链式存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数8．计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1）A. 计算方法 B.排序方法C. 解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性9．以下关于数据的逻辑结构的叙述中正确的是（）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构10．算法分析的主要任务是（）。
数据结构练习（二）答案一、填空题：1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为（1）4，树的深度为（2）4 ，树中叶子结点的个数为（3）8。
2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间关系的表达式（4）n=2h-1,m=n+1-2h-1 n=2m-1 。
3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。
一棵深度为k的完全二叉树中最少有2k-1（6）个结点，最多有（7）2k-1个结点。
4．具有n个结点的二叉树，当它是一棵(8)完全二叉树时具有最小高度（9）log2n」+1，当它为一棵单支树时具有高度(10) n 。
5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。
6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。
7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。
8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。
9．已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。
10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。
11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。
度为k的树中第i层最多有___k i-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+k h-1____个结点。
第1章绪论一、判断题1.数据的逻辑结构与数据元素本身的内容和形式无关。
（√）2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（√）3.数据元素是数据的最小单位。
（×）4.数据的逻辑结构和数据的存储结构是相同的。
（×）5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
（×）6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）7.数据的存储结构是数据的逻辑结构的存储映象。
（√）8.数据的物理结构是指数据在计算机内实际的存储形式。
（√）9.数据的逻辑结构是依赖于计算机的。
（×）10.算法是对解题方法和步骤的描述。
（√）二、填空题1.数据有逻辑结构和存储结构两种结构。
2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。
3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
4.树形结构和图形结构合称为非线性结构。
5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。
6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。
7.数据的存储结构又叫物理结构。
8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。
9.线性结构中的元素之间存在一对一的关系。
10.树形结构中的元素之间存在一对多的关系。
11.图形结构的元素之间存在多对多的关系。
12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算） 3个方面的内容。
13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。
14.算法是一个有穷指令的集合。
15.算法效率的度量可以分为事先估算法和事后统计法。
16.一个算法的时间复杂度是算法输入规模的函数。
17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。
18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）。
数据结构复习题库一、填空题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、线性表是具有相同特性的数据元素的一个有限序列。
《数据结构》程序填空复习题说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。
不能放弃其他容的复习，切记！！！一、线性表1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。
#define NULL 0void main( ){NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾结点*/head= （1）;a.next=&b;b.next=&c;c.next=&d;（2）; /*以上结束建表过程*/p=head; /*p为工作指针，准备输出链表*/do{printf(“%d\n”, （3）);（4）;}while( （5）);}答案：（1）&a（2）d next=NULL（3）p->data（4）p=p->next（5）p!=NULL2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点，struct node{ int data;struct node *next;};typedefstruct node NODEint delete(NODE *head,int i){NODE *p,*q;int j;q=head;j=0;while((q!=NULL)&&( ___(1)_____)){___(2)_____;j++;}if(q==NULL)return(0);p= ___(3)_____;___(4)_____=p->next;free(___(5)_____);return(1);}答案：（1）j<i-1（2）q=q->next（3）q->next（4）q->next（5）p3.将新元素插入到线性表中的第i位，MAX是数组的个数，a[0]用以存放线性表长度，b存放待插入的元素值，i存放插入的位置，n存放线性表长度{int a[MAX];int i,j,b,n;scanf(“%d%d%d”,&b,&i,&n);for(j=1;j<=n;j++)scanf(“%d”,&a[j]);a[0]=n;for(j=n; （1）;j- -)（2）;（3）;（4）;for(j=1;j<=a[0];j++)printf(“%5d\n”,a[j]);}答案：（1）j>=i（2）a[j+1]=a[j]（3）a[i]=b（4）a[0]=n+14.用头插法建立带头结点且有n个结点的单向链表的算法NODE *create(n){NODE *head,*p,*q;int ip=(NODE *)malloc(sizeof(NODE));（1）;（2）;（3）;for(i=1;i<=n;i++){p=(NODE *)malloc(sizeof(NODE));p->data=i;if(i==1)（4）;else{（5）;（6）;}}return(head);}答案：（1）head=p（2）p->next=NULL（3）q=p（4）p->next=NULL（5）p->next=q->next（6）q->next=p一、栈1. 以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针struct node{ ElemType data;struct node *next;};struct node *top ;void Push(ElemType x){struct node *p;p=(struct node*)malloc(___(1)_____);p->data=x;___(2)_____;}答案：（1）sizeof (struct node)（2）p->next=top（3）top=p二、队列1. 以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针struct node{ ElemType data;struct node *next;};struct node *front，*rear;void InQueue(ElemType x){struct node *p;p= (struct node*) ___(1)_____;p->data=x;p->next=NULL;___(2)_____;rear= ___(3)_____;}答案：（1）malloc(sizeof (struct node))（2）rear->next=p（3）p2. 以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返回，front、rear分别是链队列的队头、队尾指针struct node{ ElemType data;struct node *next;};struct node *front，*rear;ElemType OutQueue(){ElemType x;if(___(1)_____) {printf("队列下溢错误！\n");exit(1);}else {struct node *p=front->next;x=p->data;front->next= ___(2)_____;if(p->next==NULL) rear=front;free(p);___(3)_____;}}答案：（1）front= =rear（2）p->next（3）return(x)三、树1.以下程序是先序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右指针域分别为left和right，数据域data为字符型，BT指向根结点）。
数据结构（树与图部分）练习题数据结构(树与图部分)练习题⼀、填空题1.不考虑顺序的3个结点可构成种不同形态的树，种不同形态的⼆叉树。
2.已知某棵完全⼆叉树的第4层有5个结点，则该完全⼆叉树叶⼦结点的总数为：。
3.已知⼀棵完全⼆叉树的第5层有3个结点，其叶⼦结点数是。
4.⼀棵具有110个结点的完全⼆叉树，若i＝54，则结点i的双亲编号是；结点i的左孩⼦结点的编号是，结点i的右孩⼦结点的编号是。
5.⼀棵具有48个结点的完全⼆叉树，若i＝20，则结点i的双亲编号是______；结点i的左孩⼦结点编号是______，右孩⼦结点编号是______。
6.在有n个叶⼦结点的Huffman树中，总的结点数是：______。
7.图是⼀种⾮线性数据结构，它由两个集合V(G)和E(G)组成，V(G)是______的⾮空有限集合，E(G)是______的有限集合。
8.遍历图的基本⽅法有优先搜索和优先搜索两种⽅法。
9.图的遍历基本⽅法中是⼀个递归过程。
10.n个顶点的有向图最多有条弧；n个顶点的⽆向图最多有条边。
11.在⼆叉树的⼆叉链表中，判断某指针p所指结点是叶⼦结点的条件是。
12.在⽆向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于。
⼆、单项选择题1.树型结构的特点是：任意⼀个结点：（）A、可以有多个直接前趋B、可以有多个直接后继C、⾄少有1个前趋D、只有⼀个后继2.如下图所⽰的4棵⼆叉树中，（）不是完全⼆叉树。
3.深度为5的⼆叉树⾄多有（）个结点。
A、16B、32C、31D、104.64个结点的完全⼆叉树的深度为：（）。
A、8B、7C、6D、55.将⼀棵有100个结点的完全⼆叉树从根这⼀层开始，每⼀层从左到右依次对结点进⾏编号，根结点编号为1，则编号为49的结点的左孩⼦的编号为：（）。
A、98B、99C、50D、486.在⼀个⽆向图中，所有顶点的度之和等于边数的（）倍。
A、1/2B、1C、2D、47.设有13个值，⽤它们组成⼀棵Huffman树，则该Huffman树中共有( )个结点。
数据结构填空练习题数据结构填空练习题一1. 通常从四个方面评价算法的质量：_________、_________、_________和________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
4. 后缀算式9 2 3 +- 10 2 / -的值为__________。
中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。
在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。
7. AOV网是一种___________________的图。
8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。
1. 正确性易读性强壮性高效率2. O(n)3. 9 3 34. -1 3 4 X * + 2 Y *3 / - 5. 2 n n-1 n+1 6. e 2e7. 有向无回路 8. n(n-1)/2 n(n-1)9. （12，40）（）（74）（23,55，63） 10.增加111.O(log2n) O(nlog2n)12.归并二1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是______________。
2. 在图的邻接表中用顺序存储结构存储表头结点的优点是________________。
3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。
5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。
7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。
8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。
9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
}答案1. top1+1=top22. 可以随机访问到任一个顶点的简单链表3. i(i+1)/2+j-14. FILO，FIFO5. ABDECF，DBEAFC，DEBFCA6. 8，647. 出度，入度8. ki<=k2i && ki<=k2i+19. n-i，r[j+1]=r[j]10. mid=(low+high)/2，r[mid].key>k三1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。
2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。
3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。
4. 一个算法的效率可分为__________________效率和__________________效率。
5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。
6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。
7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。
8. 下面程序段的时间复杂度是__________________。
第8题9题10题 11题9. 下面程序段的时间复杂度是__________________。
10. 下面程序段的时间复杂度是__________________。
11. 下面程序段的时间复杂度是__________________。
12. 衡量算法正确性的标准通常是____________________________________。
13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
答案1.线性结构，非线性结构2.集合，线性，树，图3. 一对一，一对多或多对多4. 时间，空间5. 前趋，一，后继，多6. 有多个7. 一对一，一对多，多对多12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。
13. 事后统计，事前估计四1. 线性表是一种典型的_________结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
3. 顺序表中逻辑上相邻的元素的物理位置________。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。
相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9. 线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。
11. 在单链表中设置头结点的作用是________。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。
13. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。
为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, p ush后，输出序列是_________。
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。
答案1．线性2．n-i+1 3．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致 12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇14．2、3 15．O(1)五1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
