数据结构复习

数据结构笔试复习⼀选择题1．下述哪⼀条是顺序存储结构的优点？（）A．存储密度⼤ B．插⼊运算⽅便 C．删除运算⽅便 D．可⽅便地⽤于各种逻辑结构的存储表⽰2.数据结构在计算机内存中的表⽰是指( ）。

A. 数据的物理结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系3．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元。

B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作。

C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元。

D．线性表采⽤链接存储，便于插⼊和删除操作。

4.若线性表最常⽤的操作是存取第i个元素及其前驱的值，则采⽤( ）存储⽅式节省时间。

A. 单链表B. 双向链表C. 循环链表D. 顺序表5．线性表是具有n 个（）的有限序列（n>0）。

A．表元素 B．字符 C．数据元素 D．数据项 E．信息项6．若某线性表最常⽤的操作是存取任⼀指定序号的元素和在最后进⾏插⼊和删除运算，则利⽤（）存储⽅式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表7．某线性表中最常⽤的操作是在最后⼀个元素之后插⼊⼀个元素和删除第⼀个元素，则采⽤（）存储⽅式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表8．设⼀个链表最常⽤的操作是在末尾插⼊结点和删除尾结点，则选⽤( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表9．若某表最常⽤的操作是在最后⼀个结点之后插⼊⼀个结点或删除最后⼀个结点。

则采⽤（）存储⽅式最节省运算时间。

A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表10. 链表不具有的特点是（）A．插⼊、删除不需要移动元素 B．可随机访问任⼀元素C．不必事先估计存储空间 D．所需空间与线性长度成正⽐11、3个结点可构成_____棵不同形态的⼆叉树。

数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。

（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。

（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。

（）5．如果两个串含有相同的字符，则这两个串相等。

（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。

（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

（）9．一个广义表的表尾总是一个广义表。

（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。

（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。

（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。

（）13．直接选择排序是一种稳定的排序方法。

（）14．闭散列法通常比开散列法时间效率更高。

（）15．有n个结点的不同的二叉树有n!棵。

（）16．直接选择排序是一种不稳定的排序方法。

（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。

（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。

（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。

（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

一、单选题（共20题，40分）1、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

（2.0）A、 8B、 63.5C、 63D、 7正确答案： B2、在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是（）。

（2.0）A、 O(1)B、 O(n)C、O(n²)D、 O(log₂n)正确答案： B3、根据一组关键字(56, 42, 50, 64, 48)依次插入结点生成一棵AVL树，当插入到值为0的结点时需要进行旋转调整。

（2.0）A、 42B、 50C、 64D、 48正确答案： B4、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。

（2.0）A、 nB、 n+1C、 (n-1)/2D、 (n+1)/2正确答案： D5、在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。

（2.0）A、 n-iB、 n-i+lC、 n-i-1D、 i正确答案： A6、稀疏矩阵一般的压缩存储方法有两种，即（）。

（2.0）A、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表正确答案： C7、以下关于线性表的说法不正确的是______。

（2.0）A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

正确答案： C8、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

（2.0）A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序正确答案： A9、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相同，则该二叉树一定满足（）。

《数据结构》复习题一．选择题：1．数据结构是研究数据的( ) 以及它们之间的相互关系A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构2. 组成数据的基本单位是（）A.数据项B.数据类型C. 数据元素D. 数据变量3. 如果某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，元素之间的关系为R={<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>},则该数据结构是一种（）A.线性结构B. 树结构C. 图结构D. 链表结构4. 线性表的链接实现有利于( ) 运算A.插入B.读表元C.查找D.定位5. 设一数列的输入顺序为1，2，3，4，5，6通过栈操作不可能排成的输出序列为（）A. 3，2，5，6，4，1B. 1，5，4，6，2，3C. 2，4，3，5，1，6D. 4，5，3，6，2，16. 设字符串S1=‘ABCDEFG’，S2=‘PQRST’则运算S=Concat(Sub(S1,2,Length(S2)),Sub(S1,Length(S2),2))后结果为（）A.‘BCQR’B.‘BCDEF’C.‘BCDEFG’D.‘BCDEFEF’7. 设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则修改指针的操作为（）A. p→next= p→next→nextB. p= p→nextC. p= p→next→nextD. p→next = p8. 线性表采用链式存储时，其地址（）A. 必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续与否均可以9. 在内部排序时，排序不稳定的有（）A.插入排序B. 冒泡排序C. 快速排序D.归并排序10. 设有1000个元素，用折半法查找时，最小比较次数为（）A.0B. 1C.10D. 50011. 将一个元素进入队列的时间复杂度是（）n)A. O (1)B. O (n)C. O (n2)D. O (log212. 在一个具有n个结点的单链表中查找其值等x的结点，在查找成功的情况下，需要比较（）个元素结点A. n/2B. nC. (n+1)/2D. (n-1)/213. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）个元素A. n-iB. n-i+1C. n-i-1D. i14. 总共3层的完全二叉树，其结点数至少有（）A.3B. 4C.7D.815. 队列操作的原则是（）A. 先进先出B.后进先出C. 只能进行插入D. 只能进行删除16. 若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（）存储方式最节省时间A.单链表B. 双向链表C. 音循环链表D. 顺序表17. 栈和队列都是（）A. 顺序存储的线性结构B. 限制存取点的线性结构C. 链接存储的线性结构D. 限制存取点的非线性结构18. 与线性表的链接存储相符的特性是（）A.插入和删除操作灵活B. 需要连续存储空间C. 便于随机访问D. 存储密度大19.若进队序列为1,2,3,则出队序列是（）A.3，2，1B. 1，3，2C. 1，2，3D. 3，2，120. 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）A. p= NULLB. p→next= NULLC. p=hD. p→next= h3. 在双向循环链表中,在指针P所指的结点之后插入指针f所指的结点,其操作为。

《数据结构》课程复习资料一、填空题: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.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运算时，可能发生栈的下溢。

A—熟练掌握B—理解C—了解第一章：绪论1. 基本概念：包括数据的逻辑结构、数据的存储结构和数据的相关运算。

C四类数据组织结构：集合、线性表、树形、图状结构C数据的存储方式：顺序存储和链式存储。

B2.算法和分析算法的特征、时间复杂度的分析和常见的时间复杂度增长率排序、空间复杂度B本章重点：分析算法时间复杂度例1. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的D例2. 以下那一个术语与数据的存储结构无关？（）A．栈 B. 哈希表 C. 线索树 D. 双向链表A．例3.．求下段程序的时间复杂度：void mergesort(int i, int j){int m;if(i!=j){m=(i+j)/2;mergesort(i,m);mergesort(m+1,j);merge(i,j,m);}}其中mergesort()用于对数组a[n]归并排序，调用方式为mergesort(0,n-1);，merge()用于两个有序子序列的合并，是非递归函数，时间复杂度为。

解：分析得到的时间复杂度的递归关系：为merge（）所需的时间，设为cn（c为常量）。

因此令，有有第二章：线性表1.线性表的基本运算：….. C2.线性表的顺序存储（利用静态数组或动态内存分配）。

相应的表示与操作 A3.线性表的链式存储。

相应的表示与操作。

包括循环链表、双向链表。

A4.顺序存储与链式存储的比较：基于时间的考虑--分别适用于静态的和动态的操作：比如静态查找和插入删除）；基于空间的考虑-- ……. B这也适用于后面用两种方式存储的其他数据结构。

★本章重点：很熟悉顺序表，单链表、双链表，循环链表的基本操作；并学会在各种链表上进行一些算法设计（与基本操作类似的操作或组合），请仔细复习。

例4．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。

数据结构复习题及答案数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。

2.线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。

3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。

4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。

5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。

6.查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。

7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。

一、填空题1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。

算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。

2.数据的基本单元是__数据元素__，数据的最小单元是__数据项_。

3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。

4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。

5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。

6.算法机能的阐发和怀抱，能够从算法的工夫庞大度和空间庞大度来评判算法的好坏。

7.数据的逻辑布局包孕调集布局、线性布局、树形布局和图型布局四品种型。

8.数据布局在计较机中的表示称为数据的物理布局，它能够采用__按次存储___或__链式存储_两种存储方法。

9.线性表有两种存储布局，划分为按次存储和链式存储。

数据结构复习题及标准答案————————————————————————————————作者：————————————————————————————————日期：一、选择题。

(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。

A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。

A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。

A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。

A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。

A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。

A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。

A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。

A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。

A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。

A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。

第一章数据结构概述基本概念与术语1．数据:数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。

2。

数据元素:数据元素是数据的基本单位,是数据这个集合中的个体,也称之为元素，结点，顶点记录。

（补充:一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

）3．数据对象:数据对象是具有相同性质的数据元素的集合，是数据的一个子集。

（有时候也叫做属性。

)4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

（1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。

数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关,是独立于计算机的。

依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种：1.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系.2.线性结构:结构中的数据元素之间存在“一对一“的关系。

若结构为非空集合，则除了第一个元素之外，和最后一个元素之外,其他每个元素都只有一个直接前驱和一个直接后继。

3。

树形结构：结构中的数据元素之间存在“一对多“的关系.若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱,以及多个或零个直接后继。

4.图状结构:结构中的数据元素存在“多对多"的关系.若结构为非空集，折每个数据可有多个（或零个）直接后继.(2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。

想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。

逻辑结构可以映射为以下两种存储结构：1.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系.2.链式存储结构：借助指针表达数据元素之间的逻辑关系。

不要求逻辑上相邻的数据元素物理位置上也相邻。

考试说明考试内容：一、绪论数据结构的基本概念和分类、数据结构的逻辑结构、存储结构、算法、数据结构的选择和评价二、线性表线性表的类型定义、线性表的顺序表示和实现、线性表的链式表示和实现三、栈和队列栈和队列的结构特性、两种存储结构上实现栈和队列的基本操作、栈和队列在程序设计中的应用六、树和二叉树树、二叉树的定义、性质和存储结构、二叉树的遍历和线索化、二叉树和森林转换、最优树和哈夫曼编码。

七、图图的定义和术语、图的存储结构、图的遍历、最小生成树、拓扑排序、最短路径问题。

九、内部排序插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程、时间复杂度分析及其应用。

试题类型及分值：选择题30分15题应用题40分5题算法设计题30分3题1.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D. 易读性、稳定性、安全性答案：CB2. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)答案 C3．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构答案 C4．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈答案 D5．连续存储设计时，存储单元的地址（）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续答案 A6．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

《数据结构》复习资料《数据结构》复习资料1⼀、选择题1. ⼀棵⼆叉树中第６层上最多有（）个结点。

A. ２B. 31C. 32D. 642. 顺序表中数据元素的存取⽅式为（）。

A. 随机存取B. 顺序存取C. 索引存取D. 连续存取3. 设有⽆向图G=(V,E)，其中顶点集合V={a,b,c,d,e,f}，边集合E={(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)}。

对G进⾏深度优先遍历，正确的遍历序列是（）。

A. a,b,e,c,d,fB. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b4. 在待排元素序列基本有序的前提下，效率最⾼的排序⽅法是（）。

A. 插⼊B. 选择C. 快速D. 归并5. 设表中含100个数据元素，⽤折半查找法进⾏查找，则所需最⼤⽐较次数为（）。

A. 50B. 25C. 10D. 76. 设哈希表地址范围为0~19，哈希函数H(key)=key%17，使⽤⼆次探测再散列法处理冲突。

若表中已存放有关键字值为6、22、38、55的记录，则再放⼊关键字值为72的记录时，其存放地址应为（）。

A. 2B. 3C. 4E. 8F. 以上都不对7. 设对下图从顶点a出发进⾏深度优先遍历，则（）是可能得到的遍历序列。

A. acfgdebB. abcdefgC. acdgbefD. abefgcd8. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序⽅法是（）。

A. 快速排序B. 堆排序C. 归并排序D. 直接插⼊排序9. 设有⼀组关键字值（46,79,56,38,40,84），则⽤堆排序的⽅法建⽴的初始堆为（）。

A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,3810. 设⼴义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。

】一、单选题：1、下列说法中，不正确的是（D）。

A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2. 算法的时间复杂度取决于（A）A．问题的规模 B. 待处理数据的初态 C. A和B3.数据的逻辑结构可分为（C ）两类。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性表是具有n个（C）的有限序列（n>0）A．表元素 B．字符 C．数据元素 D．数据项5.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表6．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5.下述哪一条是顺序存储结构的优点（ D）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2、非空的循环单链表L的尾结点（由p所指向）满足（C ）。

A.p->next= =NULLB.p= =NULLC.p->next= =LD.p= =L2. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ）。

A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL3、已知一个栈的进栈序列是1，2，3…，n，其输出序列的第一个元素是i，则第j个出栈元素是（D ）。

A.iB.n-iC.j-i+1D.不确定3、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（C ）。

A.edcbaB.decbaC.dceabD.abcde4、若串s='software'，其子串的个数是（ D ）。

《数据结构》复习资料一单选题 (共48题，总分值0分 )1. 设用链表作为栈的存储结构，则退栈操作（0 分）A. 必须判别栈是否为满B. 必须判别栈是否为空C. 判别栈元素的类型D. 对栈不作任何判别2. 下面关于m阶B树说法正确的是（）。

①每个结点至少有两棵非空子树；②树中每个结点至多有m-1个关键字；③所有叶子在同一层上；④当插入一个数据项引起B树结点分裂后，树长高一层。

（0 分）A. ①②③B. ②③C. ②③④D. ③3. 下列关于文件的说法，错误的是（）。

（0 分）A. 选择文件的组织方式时应考虑外存的性质和容量B. 不定长文件指的是总长度可变的文件C. 对文件的操作主要是维护和检索D. 文件的存储结构指的是文件在外存上的组织方式4. 设无向图的顶点个数为n，则该图最多有（）条边。

（0 分）A. n-1B. n(n-1)/2C. n(n+1)/2D. n25. 设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（）。

（0 分）A. bB. cC. (c)D. (c,d,e)6. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

（0 分）A. 688B. 678C. 692D. 6967. 设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（0 分）A. nB. eC. 2nD. 2e8. 广义表(a,(b,(),c))的深度为（）。

（0 分）A. 1B. 2C. 3D. 49. 设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（）。

（0 分）A. 4条B. 5条C. 6条D. 无法确定10. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（0 分）A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，311. 具有n个顶点的有向强连通图最少有（）条弧。

一、填空：1．顺序存储结构的特点是（），链接存储结构的特点是（）。

【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。

2.算法在发生非法操作时可以作出处理的特性称为（健壮性）。

【解答】健壮性3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶(O(1) )、对数阶(O(log2n) )、线性阶(O （n）)、平方阶(O(n2) )和指数阶(O（2n）)。

【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。

n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n!5．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（c ）。

A O(0) B O(1) C O(n) D O(n2)【解答】C6．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（n-i+1 ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（n-i ）个元素。

【解答】n-i+1，n-i7．在单链表中，除了头结点以外，任一结点的存储位置由（其前趋结点的指针域）指示。

【解答】其前趋结点的指针域8．当线性表采用顺序存储结构时，其主要特点是（逻辑结构中相邻的结点在存储结构中仍相邻）。

【解答】逻辑结构中相邻的结点在存储结构中仍相邻9 栈通常采用的两种存储结构是（顺序存储结构和链接存储结构）；其判定栈空的条件分别是（栈顶指针top=-1和top=NULL），判定栈满的条件分别是（栈顶指针top等于数组的长度和内存无可用空间）。

【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top= -1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间10（栈）可作为实现递归函数调用的一种数据结构。

一、在数据结构中，从逻辑上可以把数据结构的的分类。

P101、分类：线性结构：K中每个结点最多只有一个前驱和一个后继。

没有前驱的结点称为开始结点，没有后继的结点称为终端结点。

树形结构：K中每个结点最多只有一个前驱，但可以有多个后继的结构。

复杂结构：K 中结点的前驱、后继结点的个数都不作限制的结构。

2、特殊的还有集合结构：当R为空集时，K中结点间没有约束关系。

3、各种逻辑结构具有以下包含关系：集合结构⊆线性结构⊆树形结构⊆复杂结构二、数据结构主要研究对象P13研究的是结点之间的逻辑结构、储存结构和各种行为的具体表现。

三、算法的特点P171、定义：算法是由有穷规则构成的为解决某一问题的运算序列（方法或过程）。

2、算法特点有三个：有穷性：一个算法必须在执行了有穷步之后结束确定性：算法的每一步必须有确切的定义可行性：算法是可行的，意味着算法中的每个动作，原则上都是能够由机器或人准确完成的。

3、算法的正确性：如果一个算法以一组满足初始条件的输入开始，那么该算法的执行一定终止，并且终止时得到满足要求的（输出）结果。

4、算法设计的方法：贪心法、分治法、回溯法、动态规划法、分枝界限法。

四、线性表概念P29，顺序表存储特点，链表的类型及存储特点。

单链表的插入、删除、查找操作算法描述1、线性表：线性表简称表，是零个或多个元素的有穷序列。

通常表示为：K= (k0,k1,.......k n-1) , K中所含元素的个数称为表的长度。

线性表可采用顺序储存和链式储存。

2、顺序表存储特点：将线性表中的元素一个接一个地存储在一片相邻的存储区域中。

3、链表的类型有及存储特点：（1）单链表：用一组可以是不连续的存储单元，存储线性表的各个元素，每个元素存储了自身的信息，还存储了其后继的信息（即后继元素的存储位置）。

数据域指针域（2）双链表：llink info rlink其中，llink域指向其前驱结点，称为左指针域；rlink域指向其后继结点，称为右指针域；info域存放结点本身的信息，特点是找到结点的前驱和后继。

《数据结构》复习内容一．单选题1．链栈与顺序栈相比，有一个比较明显的优点是BA.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便2．从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为AA.选择排序B.插入排序C.快速排序D.冒泡排序3．若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个BA.一般矩阵B.对称矩阵C.对角矩阵D.稀疏矩阵4．一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为CA.n*nB.n*n/2C.(n+1)*n/2D.(n+1)*(n+1)/25．当栈中的元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为BA.n-1B.nC.n+1D.n/26．在单链表中，增加头结点的目的是CA.使单链表至少有一结点B.标志表中首结点位置C.方便运算的实现D.说明单链表是线性表的链式存储实现8．在一个图中，所有顶点的度数之和等于所有边数的倍。

CA.1/2B.1C.2D.47．下列排序方法中，排序趟数与序列的原始状态有关的方法是DA.选择排序B.希尔排序C.堆排序D.冒泡排序8．在一棵具有五层的满二叉数中，结点总数为AA.31B.32C.33D.169．线性表是AA.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，不能为空12．下列排序算法中，排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。

CA.选择B.冒泡C.归并D.堆13．二维数组a的每个元素是由6个字符组成的串，行下标的范围从0到8，列下标的范围从1到10，则存放a至少需要个字节。

DA.90B.180C.270D.54014．对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为CA.A[1],A[2],A[3],A[4]B.A[1],A[14],A[7],A[4]C.A[7],A[3],A[5],A[4]D.A[7],A[5],A[3],A[4]15．以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n>0 ），空链域的个数为CA.2n-1B.n-1C.n+1D.2n+116．向顺序栈中压入元素时AA.先移动栈顶指针，后存人元素B.先存人元素，后移动后移动栈顶指针C.谁先谁后无关紧要D.同时进行17．下列存储形式中，哪一个不是树的存储形式DA.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法18．对n个记录的文件进行堆排序，最坏情况下的执行时间为A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)19用链表表示线性表的优点是CA.便于随机存取B.花费的存储空间比顺序表少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同20．下列有关线性表的叙述中，正确的是AA.线性表中的元素之间是线性关系B.线性表中至少有一个元素C.线性表中任何一个元素有且仅有一个直接前驱D.线性表中任何一个元素有且仅有一个直接后继21．线性表的顺序存储结构中，一般情况下，在第i（1≤i≤n）个元素之前插入一个元素时，需向后移动（）个元素。

数据结构复习资料一、单项选择题：1、以下说法正确的是（B ）。

A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构2、在数据结构中，从逻辑上可以把数据结构分成（C ）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．以上三个选项都是不是3、以下数据结构中，（A ）是非线性数据结构A．树B．字符串C．队D．栈4. 对于int *pa[5]的描述，（ D ）是正确的。

A．pa是一个指向数组的指针，所指向的数组是5个int型元素B．pa是一个指向某数组中的第5个元素的指针，该元素是int型变量C．pa[5]表示某个数组的第5个元素的值D．pa是一个具有5个元素的指针数组，每个元素是一个int型指针5、在int a[][3]={{1},{3,2},{4,5,6},{0}}中，a[2][2]的值是( C )。

A.3B. 2C.6D.41. 栈和队列的共同特点是( A )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( D ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 算法分析的目的是：（ C ）A．找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性4. 算法分析的两个主要方面是：（ A ）A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性5. 计算机算法指的是：（ C ）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法6．循环链表的主要优点是( B ) 。

A.不在需要头指针了B.已知某个结点的位置后，能够容易找到他的直接前趋C.在进行插入、删除运算时，能更好的保证链表不断开D.从表中的任意结点出发都能扫描到整个链表7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ B ）。

一、填空题1、栈的特点是先进后出(或后进先出)，队列的特点是先进先出。

2、顺序表中逻辑上相邻的元素物理位置也相邻，单链表中逻辑上相邻的元素物理位置不相邻。

3、算法的5个重要特性是__________、__________、_________、___________、___________。

4、线性表、栈、队列都是线性结构，可以在线性表的任何位置插入和删除元素，对于栈只能在栈顶位置插入和删除元素，对于队列只能在队尾位置插入和只能在队头删除元素。

5、下面树的先序、中序、后续遍历的结果依次为_________、___________、__________6、当数据量特别大需借助外部存储器对数据进行排序时，则这种排序称为外部排序。

7、在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则应首先选取堆排序方法；若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序的速度来考虑，则应选取快速排序方法。

二、选择题1、算法分析的两个主要方面是（）。

A. 时间复杂度和空间复杂度B. 正确性和简明性C. 可读性和文档性D. 健壮性和科学性2、对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间。

A. 顺序表B. 带头结点的双循环链表C. 单链表D. 带尾结点的单循环链表5、循环队列在进行删除运算时（）A. 仅修改头指针B. 修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改6、栈和队列的共同点是（）。

A．都是先进后出B．都是先进先出C．只允许在端点处插入和删除元素D．没有共同点7、树最适合用来表示（）A．有序数据元素 B. 无序数据元素C．元素之间具有分支层次关系的数据 D. 元素之间无联系的数据8、如果结点A有3个兄弟，而且B是A的双亲，则B的度是（）A. 4B. 5C. 1D. 39、有关二叉树下列说法正确的是（）A. 二叉树的度为2B. 一棵二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为210、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A. 250B. 500C. 505D. 以上答案都不对11、静态查找表与动态查找表二者的根本差别在于（B）A. 它们的逻辑结构不一样B. 施加在其上的操作不同C. 所包含的数据元素的类型不一样D. 存储实现不一样12、顺序查找法适合于存储结构为（B）的线性表。