数据结构查找习题及复习资料

1、静态查找表和动态查找表的区别是( )。

A.所包含的数据元素的类型不同B.施加其上的操作不同C.它们的逻辑结构相同D.以上都不对正确答案：B解析：B、若在查找的同时对表做修改操作(如插入和删除)，则相应的查找表称之为动态查找表。

若在查找中不涉及表的修改操作，则相应的查找表称之为静态查找表。

2、顺序查找法适合于存储结构为( )的线性表。

A.索引存储B.压缩存储C.顺序存储或者链式存储D.哈希存储正确答案：C解析：C、顺序查找可以从前向后或者从后向前挨次查找，既适合于顺序存储结构也适合于链式存储结构。

3、采用顺序查找方法查找长度为n 的顺序表时，在等概率时成功查找的平均查找长度为( )。

A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：D解析：D、顺序查找时，元素ai 需i 次比较，成功查找的平均查找长度=(1+2+ …+n)/n=(n+1)/2。

4、采用顺序查找方法查找长度为n 的顺序表时，在等概率时不成功查找的平均查找长度为( )。

A.(n-1)/2B.nC.n/2D.(n+1)/2正确答案：B解析：B、当查找的元素不在线性表中时，均需要n 次元素之间的比较。

5、适合于折半查找的数据组织方式是( )。

A.以链表存储的有序线性表B.以顺序表存储的有序线性表C.以链表存储的线性表D.以顺序表存储的线性表正确答案：B解析：B、折半查找的数据必须是有序的。

此外，折半查找中需要确定查找区间，这要求存储结构最好具有随机存取特性，而顺序表满足这个特性。

6、采用折半查找方法查找长度为n 的线性表，当n 很大时，在等概率时不成功查找的平均查找长度为( )。

n)A. O(nlog2B. O(n2)C. O(n)n)D. O(log2正确答案：D解析：D、采用折半查找时，若n 很大，对应的判定树可以看成是一棵满二叉树，失败节点(外部节点)集中在最下一层，落在每一个失败节点时比较的次都均为log n。

27、设有100 个元素的有序表，采用折半查找方法，在等概率时成功时最大的比较次数是( )。

数据结构复习题及答案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．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。

数据结构基础及深入及考试复习资料习题及实验参考答案见附录结论1、数据的逻辑结构是指数据元素之间的逻辑关系。

即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。

2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。

它依赖于计算机。

存储结构可分为4大类：顺序、链式、索引、散列3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。

它由基本的数据类型构成，并包括一组相关的服务（或称操作）。

它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。

4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。

5、在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和表态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构6、算法的时间复杂度取决于（ A ）A、问题的规模B、待处理数据的初态C、问题的规模和待处理数据的初态线性表1、线性表的存储结构包括顺序存储结构和链式存储结构两种。

2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。

A、(n-1)/2B、nC、n+1D、n-1E、n/2F、(n+1)/2G、(n-2)/23、“线性表的逻辑顺序与存储顺序总是一致的。

”这个结论是（ B ）A、正确的B、错误的C、不一定，与具体的结构有关4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ）A、必须是连续的B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以5、带头结点的单链表为空的判定条件是（ B ）A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL6、不带头结点的单链表head为空的判定条件是（ A ）A、head==NULLB、head->next==NULLC、head->next=headD、head!=NULL7、非空的循环单链表head的尾结点P满足（ C ）A、p->next==NULLB、p==NULLC、p->next==headD、p==head8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）A、O(1)B、O(n)C、O(n2)D、O(nlog2n)9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ）A、p->next=p->next->next;B、p=p->next;p->next=p->next->next;C、p->next=p->next;D、p= p->next->next;10、在一个单链表中，若在p所指结点之后插入s所指结点，则执行（ B ）A、s->next=p;p->next=s;B、s->next=p->next;p->next=s;C、s->next=p->next;p=s;D、p->next=s;s->next=p;11、在一个单链表中，已知q是p的前趋结点，若在q和p之间插入结点s，则执行（C ）A、s->next=p->next;p->next=s;B、p->next=s->next;s->next=p;C、q->next=s;s->next=p;D、p->next=s;s->next=q;12、在线性结构中，第一个结点没有前趋结点，其余每个结点有且只有 1 个前趋结点。

数据结构复习题及参考答案《数据结构》课程复习资料一、填空题: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个元素的存储位置是。

数据结构复习题及答案一、选择题1. 在数据结构中，以下哪种数据结构允许在任何位置进行插入和删除操作？A. 栈B. 队列C. 链表D. 数组答案：C2. 以下哪个选项是二叉搜索树的特性？A. 所有左子树的节点值小于根节点值B. 所有右子树的节点值大于根节点值C. 所有左子树的节点值大于根节点值D. 所有右子树的节点值小于根节点值答案：A3. 在图的遍历中，深度优先搜索（DFS）使用的是哪种数据结构？A. 栈B. 队列C. 链表D. 数组答案：A二、填空题1. 在一个有n个节点的完全二叉树中，如果节点按层次从上到下、从左到右编号为1, 2, 3, ..., n，则第i个节点的左孩子节点的编号为____。

答案：2i2. 哈希表解决冲突的一种方法是使用链地址法，其中每个哈希表项是一个____。

答案：链表3. 在图的表示方法中，邻接矩阵适合表示____图，邻接表适合表示____图。

答案：稠密；稀疏三、简答题1. 描述什么是递归，并给出一个简单的递归算法的例子。

答案：递归是一种在算法中调用自身的方法，用于解决可以分解为相似子问题的问题。

一个简单的递归算法例子是计算阶乘：n! = n * (n-1)!，其中基本情况是0! = 1。

2. 解释什么是图的广度优先搜索（BFS）算法，并说明其在哪些情况下适用。

答案：广度优先搜索（BFS）是一种遍历或搜索树或图的算法，它从根节点开始，逐层遍历节点。

BFS适用于寻找最短路径或在层次结构中按层次顺序访问节点的情况。

四、编程题1. 给定一个单链表，请编写一个函数来反转该链表。

答案：（此处省略具体代码实现，只提供解题思路）要反转一个单链表，可以创建一个新的链表头节点，然后遍历原链表，将每个节点的next指针指向前一个节点，直到链表末尾。

最后，将新链表的头节点设置为原链表的最后一个节点的前驱节点。

第9章查找一、单选题1.对一棵二叉搜索树按〔〕遍历，可得到结点值从小到大的排列序列。

A. 先序B. 中序C. 后序D. 层次2.从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为〔〕。

A. O(n)B. O(1)C. O(logn)D. O(n2)3.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为〔〕。

A. O(n)B. O(1)C. O(logn)D. O(n2)4.在二叉搜索树中插入一个结点的时间复杂度为〔〕。

A. O(1)B. O(n)C. O(logn)D. O(n2)5.分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是〔〕。

A．〔100，80，90，60，120，110，130〕B.〔100，120，110，130，80，60，90〕C.〔100，60，80，90，120，110，130〕D.〔100，80，60，90，120，130，110〕6.在一棵AVL树中，每个结点的平衡因子的取值X围是〔〕。

A. -1~1B. -2~2C. 1~2D. 0~17.根据一组关键字〔56，42，50，64，48〕依次插入结点生成一棵A VL树，当插入到值为〔〕的结点时需要进行旋转调整。

A. 42B. 50C. 64D. 488.深度为4的A VL树至少有〔〕个结点。

A．9 B.8C.7D.69.一棵深度为k的A VL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有〔〕个结点。

A.2k-1-1B.2k-1+1C.2k-1D.2k10.在A VL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作〔〕型调整以使其平衡。

A. LLB. LRC. RLD. RR二、判断题1.二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

2.二叉搜索树中每个结点的关键字值大于其左非空子树〔若存在的话〕所有结点的关键字值，且小于其右非空子树〔若存在的话〕所有结点的关键字值。

数据结构复习题(附答案)数据结构复习题(附答案)数据结构是计算机科学中非常重要的一门课程，其涉及到对数据的组织、存储和管理方法的研究。

在学习数据结构的过程中，我们通常需要进行大量的练习和复习以加深对各种数据结构和算法的理解。

本文将为大家提供一些数据结构的复习题，并附有详细的答案解析。

一、栈和队列1. 给定一个字符串，判断其中的括号序列是否合法。

例如，"{([])}"是合法的括号序列，而"{[)]}"则是非法的。

答案：使用栈的数据结构可以很方便地解决这个问题。

遍历字符串，遇到左括号就将其入栈，遇到右括号就判断对应的左括号是否与栈顶元素相匹配，如果匹配则将栈顶元素出栈，继续比较下一个字符。

最后，栈为空则表示括号序列合法。

2. 设计一个队列，实现队列的基本操作：入队、出队、获取队头元素和判断队列是否为空。

答案：可以使用一个数组来实现队列，使用两个指针front和rear分别指示队头和队尾的位置。

入队操作时，将元素添加到rear指向的位置，并将rear后移一位；出队操作时，将front后移一位；获取队头元素时，返回front指向的位置的元素；判断队列是否为空可以通过比较front和rear来确定。

3. 反转一个单链表。

答案：使用三个指针prev、curr和next来实现链表的反转。

初始时，将prev指向null，curr指向头节点，next指向curr的下一个节点。

然后，将curr的next指向prev，将prev指向curr，将curr指向next，再将next指向next的下一个节点。

重复这个操作，直到链表反转完成。

4. 判断一个单链表中是否存在环。

答案：使用快慢指针的方法可以判断一个单链表中是否存在环。

如果存在环，那么快指针最终会追上慢指针；如果不存在环，那么快指针最终会达到链表的末尾。

三、树和图5. 给定一个二叉树，编写一个算法来判断它是否是平衡二叉树。

答案：平衡二叉树的定义是指二叉树的每个节点的左子树和右子树的高度差不超过1。

第九章查找一、选择题1。

若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

A． (n—1)/2 B. n/2 C。

（n+1）/2 D。

n2. 下面关于二分查找的叙述正确的是（ )A。

表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B。

表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 用二分(对半）查找表的元素的速度比用顺序法（ )A．必然快 B. 必然慢 C. 相等 D. 不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度( ）A. 3。

1 B。

4 C. 2。

5 D. 55．当采用分块查找时,数据的组织方式为 ( ）A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序,但块间必须有序，每块内最大(或最小）的数据组成索引块C。

数据分成若干块，每块内数据有序，每块内最大(或最小）的数据组成索引块D. 数据分成若干块,每块（除最后一块外)中数据个数需相同6。

二叉查找树的查找效率与二叉树的( （1）)有关, 在（（2）)时其查找效率最低（1）: A。

高度 B。

结点的多少 C. 树型 D. 结点的位置(2）: A。

结点太多 B. 完全二叉树 C。

呈单枝树 D. 结点太复杂。

7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败，它们的平均查找长度是((1）） ,对于查找成功，他们的平均查找长度是（（2））供选择的答案：A。

相同的 B。

不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）A．(100,80， 90， 60， 120，110，130） B。

（100，120，110,130，80， 60, 90) C。

（100，60, 80， 90, 120，110，130） D。

第 1 章绪论课后习题讲解1. 填空(1)()是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素3()是数据的最小单位，()是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶ 从逻辑关系上讲，数据结构主要分为( )、( )、( )和( )。

【解答】集合，线性结构，树结构，图结构⑷ 数据的存储结构主要有( )和( )两种基本方法，不论哪种存储结构，都要存储两方面的内容：( ) 和( )。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸ 算法具有五个特性，分别是( )、( )、( )、( )、( )。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹ 算法的描述方法通常有( )、( )、( )和( )四种，其中，( )被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺ 在一般情况下，一个算法的时间复杂度是( )的函数。

【解答】问题规模⑻设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为( )，若为n*log25n，则表示成数量级的形式为( )。

【解答】0 (1)，O (nlog2n)【分析】用大0记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴ 顺序存储结构中数据元素之间的逻辑关系是由( )表示的，链接存储结构中的数据元素之间的逻辑关系是由( )表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置(即元素在数组中的下标)表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

数据结构复习题及答案数据结构习题一、名词解释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.线性表有两种存储布局，划分为按次存储和链式存储。

（完整版）数据结构复习题目及答案数据结构 -C 语言版》第一章绪论单项选择题1．在数据结构中，数据的基本单位是 ________2．数据结构中数据元素之间的逻辑关系被称为__ ___ 。

A. 数据的存储结构B. 数据的基本操作C. 程序的算法3．在数据结构中，与所使用计算机无关的是数据的________ ___。

A. 存储结构B. 逻辑和物理结构C. 逻辑结构4．在链式存储结构中，数据之间的关系是通过 _______ ___ 体现的。

A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针5．计算算法的时间复杂度是属于一种 ______ ___。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是A. n 2B. nlognC. nD. logn 7.设使用某算法对 n 个元素进行处理，所需的时间是T(n)=100nlog 2n+200n+2000，则该算法的渐近时间复杂度为 _____ ___。

A. 数据项B. 数据类型C. 数据元素D. 数据变量D. 数据的逻辑结构D. 物理结构A. O(1)B. O(n)C. O(200n)D. O(nlog2n)CDCBBDD第二章线性表单项选择题1 ?链表不具有的特点是 __________ 。

A.可随机访问任一元素B.插入和删除时不需要移动元素C.不必事先估计存储空间D.所需空间与线性表的长度正比2.设顺序表的每个元素占 8个存储单元。

第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为 ______________ 。

3 ?在线性链表存储结构下，插入操作算法_______________ B. p_>next = p_>n ext;D. p = p->n ext; p->n ext = p->n ext- >n ext;5 .将长度为n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 __________________ A. 0( n)B. 0(1)C. 0(m)D. 0(m+n)6 ?需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 ________A.单链表B.静态链表C.线性链表D.顺序存储方式ACCABB 填空题1 ?在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 ____ 结点。

数据结构复习--排序和查找现在正在学习查找和排序，为了节省时间提⾼效率，就正好边学习边整理知识点吧！知识点⼀：⼆分查找/折半查找1.⼆分查找的判定树（选择题）下列⼆叉树中，可能成为折半查找判定树（不含外部结点）的是： (4分)1.2.3.4.注：折半查找判定树是⼀棵⼆叉排序树，它的中序遍历结果是⼀个升序序列，可以在选项中的树上依次填上相应的元素。

虽然折半查找可以上取整也可以下取整但是⼀个查找判定树只能有⼀种取整⽅式。

如果升序序列是偶数个，那么终点应该偏左多右少。

在2选项中，由根节点左⼦树4个节点⽽右⼦树5个节点可以确定⽤的是向下取整策略，但是它的左⼦节点在左⼦树种对应的终点左边2个，右边个，明显是上取整策略，策略没有统⼀，所以是错的。

其他的选项类似分析。

2.⼆分查找法/折半查找法已知⼀个长度为16的顺序表L，其元素按关键字有序排列。

若采⽤⼆分查找法查找⼀个L中不存在的元素，则关键字的⽐较次数最多是： (2分)1. 72. 63. 54. 4 注：⼀次找到最边界的那⼀个树的情况下有最多次数 这个题中结点数16是个偶数：第⼀次（0+15）/2 7 第⼆次（8+15）/2 11第三次（12+15）/2 14 第四次（14+15）/2 14 第五次（15+15）/2 15（下取整的就向右计算求最多次数）第⼀次（0+15）/2 8 第⼆次（0+7）/2 4 第三次（0+3）/2 2 第四次（0+1)/2 0第五次（0+0）/2 0（下取整的话就向左求最多次数）若结点数是奇数15：第⼀次（0+14）/2 7 第⼆次（ 0+6）/2 3 第三次（0+2）/2 1第四次（0+0）/2 0第⼀次（0+14）/2 7 第⼆次（8+14）/2 11 第三次（12+14）/2 13第四次（14+14）/2 0这时候向左或者向右都是OK的（因为得到的数都是能够被2整除的）但是划重点了折半查找⼀个有序表中不存在的元素，若向下取整，则要最多⽐较[log2n]+1次，若向上取整，则要最多⽐较[log2(n+1)],其实就是求树的深度.（这⼀块⾃⼰的说法可能不够准确，希望⼤家看到有问题的可以指出来）结合实际，我们⽤[log2n]+1来算更简单并且计算[log2n]要取整数，因为可能会存在不是满⼆叉树的情况。

《数据结构》复习资料《数据结构》复习资料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)))的值为（）。

数据结构图,查找,内排序的练习及答案数据结构课后练习习题要求：此次练习不要求上交，只是帮助⼤家掌握知识点，便于复习。

第⼋章图⼀．单项选择题（20分）1. 带权有向图G ⽤邻接矩阵A 存储，则Vi 的⼊度等于A 中___D______A. 第i ⾏⾮∞的元素只和B. 第i 列⾮∞的元素之和C. 第i ⾏⾮∞且⾮0的元素之和D. 第i 列⾮∞且⾮0的元素个数2. ⽆向图的邻接矩阵是⼀个___A____A. 对称矩阵B. 零矩阵C. 上三⾓阵D. 对⾓矩阵3. 在⼀个⽆向图中，所有顶点的度之和等于边数的__C____倍A. 1/2B. 1C. 2D. 44. ⼀个有n 个顶点的⽆向图最多有___C____条边。

A. nB. n(n-1)C. n(n-1)/2D.2n5. 对于⼀个具有n 个顶点的⽆向图，若采⽤邻接矩阵表⽰，则该矩阵⼤⼩是__D_____A. nB. 2)1(?nC. n-1D. 2n6. ⼀个有向图G 的邻接表存储如右图所⽰，现按深度优先搜索遍历，从V1出发，所得到的顶点序列是___B_____。

A. 1，2，3，4，5B. 1，2，3，5，4C. 1，2，4，5，3D. 1，2，5，3，47. 对右图所⽰的⽆向图，从顶点V1开始进⾏深度优先遍历，可得到顶点访问序列__A______（提⽰：可先画出邻居表图再遍历）A. 1 2 4 3 5 7 6B. 1 2 4 3 5 6 7C. 1 2 4 5 6 3 7D. 1 2 3 4 5 6 78. 如果从⽆向图的任⼀顶点出发进⾏⼀次深度优先搜索即可访问所有顶点，则该图⼀定是__B_____A. 完全图B. 连通图C.有回路D. ⼀棵树9. 任何⼀个⽆向连通图___B___最⼩⽣成树（提⽰：注意最⼩⽣成树的定义，此题易错）A. 只有⼀棵B. ⼀棵或多棵C. ⼀定有多棵D.可能不存在11. 若图的邻接矩阵中主对⾓线上的元素全是0，其余元素全是1，则可以断定该图⼀定是_D_____。

一、单选题1、对于查找表(13,27,38,49,50 ,65,76,97)采用顺序查找，在等概率情况下查找成功的平均查找长度是（）。

A.4.5B.9C.4D.8正确答案：A2、在关键字序列（10,20,30,40,50）中采用折半查找20，依次与（）关键字进行了比较。

A.30,10,20B.20C.30,20D.40,20正确答案：A3、在关键字序列（8,12,20,25,33）中，采用二分查找25，关键字之间比较需要（）次。

A.2B.1C.3D.4正确答案：A4、对于长度为11的有序表，按折半查找，在等概率情况下查找成功时，其平均查找长度是（）。

A.3B.4C.1D.2正确答案：A5、对于长度为11的有序表，按折半查找，在查找失败时，待查找值域表中关键字比较的次数是（）。

A.3次或4次B.2次或3次C.4次或5次D.1次或2次正确答案：A6、对于长度为n的有序表，按折半查找，在等概率情况下查找成功平均时间复杂度是（）。

A.O(㏒n)B.O(n)C.O(1)D.O(n㏒n)正确答案：A7、索引顺序查找也叫分块查找，其查找过程分为是（）个步骤。

A.1B.3C.4D.2正确答案：D8、对于长度为n的关键字序列创建一颗二叉排序树，该树可能的最大高度是（）。

A.n+1B.n-1C.㏒nD.n正确答案：D9、对于关键字序列(30,25,40,35,45)，按序列次序创建一颗二叉排序树，在等概率情况下查找成功时，其平均查找长度是（）。

A.8/3B.11/5C.8D.11正确答案：B10、影响散列查找时间效率的主要因素（）。

A.仅与散列表中实际元素个数相关B.仅与散列表长相关C.与散列表长和散列表中实际元素个数均相关D.与散列表长和散列表中实际元素个数均不相关正确答案：C11、一组关键字序列为(27，17，9，19，16，43，53，8，63)，用哈希函数H(key)=key MOD 8和链地址法处理冲突，查找关键字43，与散列表中关键字进行了（）次比较。

《数据结构》复习题及参考答案数据结构复习题及参考答案1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的组织方式、存储方式、访问方式以及对数据进行操作的算法等。

数据结构的选择对于解决不同类型的问题非常重要。

2. 数据结构有哪些常见的分类？数据结构可以分为以下几类：(1) 线性结构：线性结构是一种有序排列的数据结构，其中数据元素之间存在着一对一的关系。

常见的线性结构有数组、链表、栈和队列等。

(2) 非线性结构：非线性结构是一种数据元素之间存在多对多关系的结构，常见的非线性结构有树和图等。

(3) 逻辑结构：逻辑结构是指数据元素之间的逻辑关系，主要包括集合结构、线性结构、树形结构和图形结构等。

(4) 物理结构：物理结构是指数据的逻辑结构在计算机存储中的表示方式，主要包括顺序存储结构和链式存储结构等。

3. 什么是算法？算法是解决特定问题的一系列步骤或操作的有限序列。

一个算法通常包括输入、输出、基本操作、控制结构和定义算法执行的约定等。

4. 数据结构和算法之间的关系是什么？数据结构是算法的基础，而算法又依赖于数据结构。

只有选择合适的数据结构，才能实现高效的算法。

同时，算法的设计也会对数据结构的选择产生影响。

5. 请解释什么是时间复杂度和空间复杂度？时间复杂度是衡量算法执行时间消耗的度量，表示算法的运行时间与问题规模之间的关系。

通常用大O符号来表示时间复杂度，如O(n)、O(nlogn)等。

空间复杂度是衡量算法执行所需存储空间的度量，表示算法所需的额外空间与问题规模之间的关系。

同样也使用大O符号来表示，如O(1)、O(n)等。

6. 请简要描述以下数据结构的特点及应用场景：(1) 数组：数组是一种连续存储数据元素的线性结构，具有随机访问性能。

适用于知道元素位置的查找和修改操作。

(2) 链表：链表是一种通过指针连接的数据结构，具有插入、删除元素方便的特点。

适用于频繁插入、删除操作以及不知道具体位置的查找操作。

数据结构复习题及参考答案（抽考其中50%）一、单选题(每小题1分)1．下列程序段的时间复杂度为（A ）。

for(i=0； i<m ； i++)for(j=0； j<t ； j++) c[i][j]=0；for(i=0； i<m ； i++)for(j=0； j<t ； j++)for(k=0； k<n ； k++)c[i][j]=c[i][j]+a[i][k]*b[k][j]；(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)2．下列程序段的时间复杂度为（A ）。

i=0，s=0；while (s<n) {s=s+i ；i++；}(A) O(n 1/2) (B) O(n 1/3) (C) O(n) (D) O(n 2)3．设顺序表中有n 个数据元素，则删除表中第i 个元素需要移动（A ）个元素。

(A) n-i (B) n+l-i (C) n-1-i (D) i4．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（D ）存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表(C) 双向链表 (D) 双向循环链表5．设F 是由1T 、2T 和3T 三棵树组成的森林，与F 对应的二叉树为B ，1T 、2T 和3T 的结点数分别为1n 、2n 和3n ，则二叉树B 的根结点的左子树的结点数为（A ）。

(A) 11n - (B) 21n - (C) 23n n + (D) 13n n +6．设指针q 指向单链表中结点A ，指针p 指向单链表中结点A 的后继结点B ，指针s 指向被插入的结点X ，则在结点A 和结点B 插入结点X 的操作序列为（B ）。

(A) s->next=p->next ；p->next=-s ； (B) q->next=s ； s->next=p ；(C) p->next=s->next ；s->next=p ； (D) p->next=s ；s->next=q ；7．利用直接插入排序法的思想建立一个有序线性表的时间复杂度为（C ）。