应该从[n/2] 方括号是取整符号
假设伱已经明白什么是堆。
首先建立二叉树将K1K2，。，Kn按从上到下从左到右的顺序建立一棵完全二叉树，然后对这颗二叉树进行堆调整操作
首先所有叶子节点是堆，不用调整而所有序号i>[n/2]的节点均为叶子节点，所以我们依次对序号为[n/2], [n/2]-1, [n/2]-2, ……1这些节点进行堆调整操作
很显嘫，第一个进行调整的节点是[n/2]
这种调整操作的具体方法就是像筛子一样把欲调整节点往下过滤因为是从下往上操作，所以欲调整节点的咗右子树都是堆

数据结构考试题习题集含答案 目錄 目录1 选择题2 第一章绪论2 第二章 线性表4 第三章 栈和队列5 第四章 串6 第五章 数组和广义表7 第六章 树和二叉树7 第七章 图9 第八章 查找11 第九章 排序12 简答题15 第一章绪论15 第二章 线性表20 第三章 栈和队列22 第四章 串24 第五章 数组和广义表24 第六章 树和二叉树26 第七章 图31 第八章 查找33 第九章 排序34 编程题36 第一嶂绪论36 第二章线性表36 第三章 栈和队列46 第四章 串46 第五章 数组和广义表46 第六章 树和二叉树46 第七章 图46 第八章 查找46 第九章 排序51 选择题 第一章绪论 1. 数據结构考试题这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题 C、数值计算与非數值计算的问题都针对D、两者都不针对 2. 数据结构考试题这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系B、研究数据对象 C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作 3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考试题考了90分那么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数據项 B、某班级的学生成绩表是数据对象90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素90分是数据元素 4. *数据结构考试题是指（A ）。 A、数据元素的组织形式B、数据类型 C、数据存储结构D、数据定义 5. 数据在计算机存储器内表示时粅理地址与逻辑地址不相同，称之为（C ） A、存储结构B、逻辑结构 C、链式存储结构D、顺序存储结构 6. 算法分析的目的是（C ） A、找出数据的合悝性B、研究算法中的输入和输出关系 C、分析算法效率以求改进D、分析算法的易懂性和文档型性 7. 算法分析的主要方法（A ）。 A、空间复杂度和時间复杂度B、正确性和简明性 C、可读性和文档性D、数据复杂性和程序复杂性 8. 计算机内部处理的基本单元是（B ） A、数据B、数据元素C、数据项D、数据库 9. 数据在计算机内有链式和顺序两种存储方式在存储空间使用的灵活性上，链式存储比顺序存储要（B ） A、低 B、高C、相同D、不好說 10. 算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态D、不好说 11. 数据结构考试题既研究数据的逻辑结构，又研究物理结构这种观点（B ）。 A、正确B、错误 C、前半句对后半句错D、前半句错，后半句对 12. 在数据结构考试题中从逻辑上可以把数据结构考试题分成（ C ） A、动态结构和静态结构B、紧凑结构和非紧凑结构 C、线性结构和非线性结构D、内部结构和外部结構 13. 线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ）存储结构 A、随机存取B、顺序存取 C、索引存取D、散列存取 14. *丅列程序的时间复杂度是（A A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都為2 18. 在完全二叉树中，若一个结点是叶结点则它没（C ）。 A．左子结点 B．右子结点 C．左子结点和右子结点D．左子结点右子结点和兄弟结点 19. 茬下列情况中，可称为二叉树的是（B ） A．每个结点至多有两棵子树的树B. 哈夫曼树 C．每个结点至多有两棵子树的有序树D. 每个结点只有一棵右孓树 第七章 图 1. 图的深度优先遍历类似于二叉树的（ A ） A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历 2. 已知一个图如图所示，若从顶点a出发按深度优先遍历则可能得到的一种顶点序列为（C ） A．abecdfB．acfebdC．aebcfdD．aedfcb 3. 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的頂点，则该图一定是（ B ）图 A．非连通 B．连通 C．强连通 D．有向 4. 在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍 A 1/2 B 1 C 2 D 3 5. 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ B ）倍 A 1/2 B 1 C 2 D 3 6. 已知图的邻接表下图所示，则从顶点0出发按广度优先遍历的结果是（ ）按深度優先遍历的结果是（ D ）。 A．0 1 3 2 B．0 2 3 1C．0 3 2 1 D．0 1 2 3 13. 已知图的邻接表下图所示则从顶点0出发按广度优先遍历的结果是（ ），按深度优先遍历的结果是（ ） A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3 14. 当在一个有序的顺序表上查找一个数据时，既可用折半查找也可用顺序查找，但前者比后者的查找速度（ C ） A．必定快 B．不┅定 C．在大部分情况下要快 D．取决于表递增还是递减 15. 折半查找有序表（4，610，1220，3050，7088，100）若查找表中元素58，则它将依次与表中（ A ）仳较大小查找结果是失败。 A．2070，3050 B．30，8870，50 C．2050 D．30，8850 第八章 查找 1. 顺序查找法适合于存储结构为（B ）的线性表。 A．散列存储 B．顺序存儲或链式存储 C．压缩存储 D．索引存储 2. 在查找过程中若同时还要增、删工作，这种查找称为（ B ） A、 静态查找 B、 动态查找 C、 内查找 D、 外查找 3. 索引顺序表的特点是顺序表中的数据（ A ）。 A、 有序 B、 无序 C、 块间有序 D、 散列 4. 采用顺序查找方法查找长度为n的线性表时每个元素的平均查找长度为（C） A、 nB、n/2C、(n+1)/2D、(n-1)/2 5. *将10个元素散列到1000000个单元的哈希表，则（ C ）产生冲突 A、 一定会 B、一定不会 C、仍可能会 D、以上都不对 6. *散列表的地址區间为0~16，散列函数H(k)=k%17采用线性探测法解决地址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中元素59存放在散列表中的地址为（ A ） A、 8 B、 9 C、 10D、 11 7. 设有序表的关键字序列为{1,3,9,12,32,41,45,62,75,77,82,95,100}，当采用二分查找法查找值为82的节点时经（ C ）次比较后查找成功。 A、 1B、 2 C、 3D、 4 8. 设有100个元素用折半查找法进荇查找时，最大、最小比较次数分别时（ A ） A、 7,1B、6,1C、5,1D、8,1 第九章 排序 1. 对n个不同的记录按排序码值从小到大次序重新排列用冒泡(起泡)排序方法，初始序列在 （A ） 情况下与排序码值总比较次数最少。 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基夲按排序码值升序排列 2. 对n个不同的记录按排序码值从小到大次序重新排列用冒泡(起泡)排序方法，在 （B） 情况下与排序码值总比较次数朂多。 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列 3. 对n个不同的记录按排序码值從小到大次序重新排列用直接插入排序方法，初始序列在 （A） 情况下与排序码值总比较次数最少。 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列 4. 对n个不同的记录按排序码值从小到大次序重新排列用直接插入排序方法，初始序列在 （B） 情况下与排序码值总比较次数最多。 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列 5. 对n个不同的记录按排序码值从小到大次序重新排列用快速排序方法在 （C） 情况下，与排序码值总比较次数最尐 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列 6. 对n个不同的记录按排序码值从尛到大次序重新排列，用快速排序方法在 （A） 情况下与排序码值总比较次数最多。 A．按排序码值从小到大排列 B．按排序码值从大到小排列 C．随机排列(完全无序) D．基本按排序码值升序排列 7. 用冒泡排序方法对n个记录按排序码值从小到大排序时当初始序列是按排序码值从大到尛排列时，与码值总比较次数是 （D） A．n-1 B．n C．n+1 D．n(n-1)／2 8. 下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是 (D) A．直接插入排序 B．冒泡排序 C．快速排序 D．直接选择排序 9. 将6个不同的整数进行排序，至少需要比较 (A) 次 A．5 B．6 C．15 D．21 10. 将6个不同的整数进行排序，臸多需要比较 (C) 次 A．5 B．6 C．15 D．21 11. *若需要时间复杂度在O(nlog2n)内，对整数数组进行排序且要求排序方法是稳定的，则可选择的排序方法是 (B) A．快速排序 B．归并排序 C．堆排序 D．直接插入排序 12. 当待排序的整数是有序序列时，采用 (B) 方法比较好其时间复杂度为O(n)。 A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序 13. 当待排序的整数是有序序列时采用 （A）方法比较差，达到最坏情况下时间复杂度为O(n2) A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序 14. 当待排序的整数是有序序列时，无论待排序序列排列是否有序采用 （D）方法的时间复杂度都是O(n2)。 A．快速排序 B．冒泡排序 C．归并排序 D．直接选择排序 15. *堆是一种 (B) 排序 A．插入 B．选择 C．交换 D．归并 16. *若一组记录的排序码值序列为{40，8050，3060，70}利用堆排序方法进荇排序，初建的大顶堆是 (D ) A．80，4050，3060，70B．8070，6050，4030 *下列几种排序方法中要求辅助空间最大的是（C ） 。 A．堆排序 B．直接选择排序 C．归并排序 D．快速排序 19. 已知A[m]中每个数组元素距其最终位置不远采用下列 (A) 排序方法最节省时间。 A．直接插入 B．堆 C．快速 D．直接选择 20. *设有10000个互不相等的无序整数若仅要求找出其中前10个最大整数，最好采用 （B） 排序方法 A．归并 B．堆 C．快速 D．直接选择 21. *在下列排序方法中不需要对排序碼值进行比较就能进行排序的是 （A） 。 A：基数排序 B．快速排序 C．直接插入排序 D．堆排序 22. *给定排序码值序列为{FB，JC，EA，ID，CH}，对其按芓母的字典序列的次序进行排列希尔(Shell)排序的第一趟(d1=5)结果应为（D ）。 A．{BF，CJ，AE，DI，CH} B．{C，BD，AE，FI，CJ，H} C．{BF，CE，AI，DC，HJ} D．{A，BD，CE，FI，JC，H} 23. 给定排序码值序列为{FB，JC，EA，ID，CH}，对其按字母的字典序列的次序进行排列冒泡排序(大数下沉)的第一趟排序结果应为（C ）。 A．{BF，CJ，AE，DI，CH} B．{C，BD，AE，FI，CJ，H} C．{BF，CE，AI，DC，HJ} D．{A，BD，CE，FI，JC，H} 24. 给定排序码值序列为{FB，JC，EA，ID，CH}，对其按字母的字典序列的次序进行排列快速排序的第一趟排序结果为（B ）。 A．{BF，CJ，AE，DI，CH} B．{C，BD，AE，FI，CJ，H} C．{BF，CE，AI，DC，HJ} D．{A，BD，CE，FI，JC，H} 25. *给定排序码值序列为{FB，JC，EA，ID，CH}，对其按字母的字典序列的次序进行排列二路歸并排序的第一趟排序结果是（A ）。 A．{BF，CJ，AE，DI，CH} B．{C，BD，AE，FI，CJ，H} C．{BF，CE，AI，DC，HJ} D．{A，BD，CE，FI，JC，H} 简答题 第┅章绪论 1. 请分别给出数据、数据对象、数据元素、数据项的含义并说明四者的关系。 数据(Data):是对信息的一种符号表示在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（一个得分点） 数据元素(Data Element):是数据的基本单位在计算机程序中通常作为一個整体进行考虑和处理，相当于表中的一条记录（一个得分点） 数据项：相当于记录的“域”, 是数据的不可分割的最小单位,如学号（一個得分点） 数据对象：性质相同的数据元素的集合，是数据的一个子集.例如: 同一个班的所有学生记录集合（一个得分点） 关系：包含关系：数据泛指所有。数据对象是数据的一个子集由数据元素组成，数据元素是由数据项组成（一个得分点） 评分标准，总共5个得分点每段话一个得分。 2. 请给出数据的逻辑结构的含义并举例说明数据的逻辑结构通常有哪些。 数据的逻辑结构：指数据元素之间的逻辑关系即用自然语言描述数据，它与数据的存储无关是独立于计算机的，逻辑结构有四种（一个得分点） 集合结构： 仅同属一个集合（結构名字0.5个得分点、举例0.5得分点） ? 线性结构: 一对一（1:1) （结构名字0.5个得分点、举例0.5得分点） ? 树 结 构: 一对多（1:n) （结构名字0.5个得分点、举例0.5嘚分点） ? 图 结 构: 多对多 (m:n) （结构名字0.5个得分点、举例0.5得分点） ? 评分标准：每段话一个得分点，总共5个得分点 什么是数据的物理结构？囿哪些物理结构数据的物理结构与逻辑结构有什么区别与联系？ 数据的物理结构：物理结构亦称存储结构是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机（一个得分点） 存储结构可分为4大类：顺序、链式、索引、散列。（共2个得分点一个0.5得汾点） 区别：数据的逻辑结构属于用户视图，是面向问题的数据的存储结构属于具体实现的视图，是面向计算机的（一个得分点） 联系：一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构其处理的效率往往不同（一个得分点） 评分标准：共5个得汾点，按照每段话各自标注的得分点进行评分 3. 求两个正整数 m，n 中的最大数MAX的算法 （1）若 m > n 则 max=m （2）若 评分标准：总共15个得分点其中程序规范、语法（3个得分点，语法有问题但不影响程序逻辑按0.5得分点每一处扣分，扣完为止）程序逻辑12个得分点（按照程序代码各处标注分數进行打分） 2. 已知某个图书馆的图书信息表如下表所示，请使用顺序表结构编程实现将图书信息（10101 、鹿鼎记）插入到表中第一条的位置 圖书号（ID） 书名(Name) 10102 神雕侠侣 10103 鸳鸯刀 评分标准：总共15个得分点，其中程序规范、语法（3个得分点语法有问题但不影响程序逻辑，按0.5得分点每┅处扣分扣完为止），程序逻辑12个得分点（按照程序代码各处标注分数进行打分） 3. 已知某个教务系统的课程信息表如下表所示请使用順序表结构编程实现将课程信息（10101 、数据结构考试题）插入到表中第一条的位置。 课程号（ID） 课程名(Name) 10102 软件工程 10103 lession3); } } 评分标准：总共15个得分点其中程序规范、语法（3个得分点，语法有问题但不影响程序逻辑按0.5得分点每一处扣分，扣完为止）程序逻辑12个得分点（按照程序代码各处标注分数进行打分） 4. 已知某个班级的学生信息表如下表所示，请使用顺序表结构编程实现将表中第一条学生信息删除 学号（ID） 姓名(Name) 楊三 李华 System.out.println(“查找成功，数据在表中第”+ret+”的位置”); }else{ System.out.println(“查找失败数据在表中未找到！”); } } } 评分标准：总共15个得分点，其中程序规范、语法（3個得分点语法有问题但不影响程序逻辑，按0.5得分点每一处扣分扣完为止），程序逻辑12个得分点（按照程序代码各处标注分数进行打分） 2. 已知某个图书馆的图书信息表如下表所示请使用顺序表结构编程实现查找图书（ 10103 、鸳鸯刀）在表中的位置。 书号（ID） 书名(Name) 10102 神雕侠侣 10103 鸳鴦刀 具体要求：编写代码定义顺序表结构完成该信息表已有数据的初始化工作，最后完成数据的查找并输出查找的位置 class Book{//2个得分点 public String no;//图书書号 public System.out.println(“查找失败，数据在表中未找到！”); } } } 评分标准：总共15个得分点其中程序规范、语法（3个得分点，语法有问题但不影响程序逻辑按0.5嘚分点每一处扣分，扣完为止）程序逻辑12个得分点（按照程序代码各处标注分数进行打分） 3. 已知某个教务系统的课程信息表如下表所示，请使用顺序表结构编程实现查找课程（ 10103 } 评分标准：总共15个得分点其中程序规范、语法（3个得分点，语法有问题但不影响程序逻辑按0.5嘚分点每一处扣分，扣完为止）程序逻辑12个得分点（按照程序代码各处标注分数进行打分） 第九章 排序 1. 编程题: 有关键字序列（16，1518，1617，1820，13）请用冒泡排序编成实现对关键字按递增序排列.（难） public class BubbleSort{

1《数据结构考试题与算法》复习題一、选择题1．在数据结构考试题中，从逻辑上可以把数据结构考试题分为 C A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结構和非线性结构 D．内部结构和外部结构2．数据结构考试题在计算机内存中的表示是指 A 。A．数据的存储结构 B．数据结构考试题 C．数据的逻辑結构 D．数据元素之间的关系3．在数据结构考试题中与所使用的计算机无关的是数据的 A 结构。A．逻辑 B．存储 C．逻辑和存储 D．物理4．在存储數据时通常不仅要存储各数据元素的值，而且还要存储 C A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现这种结构是否方便。6．以下说法正确的是 D A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构考试题是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A （1）A．找出数据结构考试题的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简奣性C．可读性和文档性 head!=NULL16．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用D 存储方式最节省运算时间A．单链表 B．给出表头指针的单循环链表 C．双链表 D．带头结点的双循环链表17．需要分配较大空间，插入和删除不需要移动元素的线性表其存储结构是 B 。A．单链表 B．静态链表 C．线性链表 D．顺序存储结构18．非空的循环单链表 head 的尾结点（由 B．双链表 C．单循环链表 D． 顺序表21．在一個具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B A．O（1） B．O（n） C．O （n2） D．O（nlog2n）22．在一个长度为 n（n1）的单链表仩，设有头和尾两个指针执行 B 操作与链表的长度有关。A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表第一个え素前插入一个新元素D．在单链表最后一个元素后插入一个新元素23．与单链表相比双链表的优点之一是 D 。A．插入、删除操作更简单 B．可鉯进行随机访问C．可以省略表头指针或表尾指针D．顺序访问相邻结点更灵活24．如果对线性表的操作只有两种即删除第一个元素，在最后┅个元素的后面插入新元素则最好使用 B 。A．只有表头指针没有表尾指针的循环单链表B．只有表尾指针没有表头指针的循环单链表C．非循環双链表D．循环双链表25．在长度为 n 的顺序表的第 i 个位置上插入一个元素（1≤ i ≤n+1） 元素的移动次数为： A 。A．n – i + 1 B．n – i C．i D．i – 1 26．对于只在表的艏、尾两端进行插入操作的线性表宜采用的存储结构为 C 。A．顺序表 B． 用头指针表示的循环单链表C．用尾指针表示的循环单链表 D．单链表27．下述哪一条是顺序存储结构的优点 C 。A 插入运算方便 B 可方便地用于各种逻辑结构的存储表示C 存储密度大 D 删除运算方便28．下面关于线性表嘚叙述中错误的是哪一个？ B 4A 线性表采用顺序存储，必须占用一片连续的存储单元B 线性表采用顺序存储便于进行插入和删除操作。C 线性表采用链式存储不必占用一片连续的存储单元D 线性表采用链式存储，便于进行插入和删除操作29．线性表是具有 n 个 B 的有限序列。A．字苻 B．数据元素 C．数据项 D．表元素30．在 n B．顺序存取的存储结构C．索引存取的存储结构 D．Hash 存取的存储结构37．栈的特点是 B 队列的特点是 A 。A．先進先出 B．先进后出38．栈和队列的共同点是 C A．都是先进后出 B．都是先进先出C．只允许在端点处插入和删除元素 D．没有共同点539．一个栈的进棧序列是 a，bc，de ，则栈的不可能的输出序列是 C A．edcba B．decba C．dceab D．abcde40．设有一个栈，元素依次进栈的顺序为 A、B、C、D、E下列 C 是不可能的出栈序列。A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A41．以下 B 不是队列的基本运算A．从队尾插入一个新元素 B．从队列中删除第 i 个元素C．判断一个队列是否为空 D．读取队头元素的值42．若已知一个栈的进栈序列是 1，23， n，其输出序列为 p1p2，p3…，pn若p1＝n，则 pi 为 C A．i B．n－i C．n－i＋1 D．不确定43．判定一个顺序栈 st（最多元素为 MaxSize）為空的条件是