数据结构考试题库含答案.doc

1、数据构造考试题库含答案数据构造习题集含答案 目录 目录 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 第六章 树和二叉树

2、 46 第七章 图 46 第八章 查找 46 第九章 排序 51 选择题 第一章绪论 1.数据构造这门学科是针对什么问题而产生的？A A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据构造这门学科的研究内容下面选项最准确的是D A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据构造考了90分，那么下面关于数据对象、数据元素、数据项描绘正确的选项是C A、某班级的学生成绩表是数据元素，9

3、0分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4._数据构造是指A 。A、数据元素的组织形式 B、数据类型 C、数据存储构造 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不一样，称之为C 。A、存储构造 B、逻辑构造 C、链式存储构造 D、顺序存储构造 6.算法分析p 的目的是C A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析p 算法效率以求改良 D、分析p 算法的易懂性和文档型性 7.算法分析p 的主要方法A 。A、空间复杂度和时间复杂

4、度 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

5、 A、动态构造和静态构造 B、紧凑构造和非紧凑构造 C、线性构造和非线性构造 D、内部构造和外部构造 13.线性表的顺序存储构造是一种( )的存储构造，线性表的链式存储构造是一种 A 存储构造。A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14._以下程序的时间复杂度是A for (i=1; i0)个结点的完全二叉树的深度为(C )。  .log2(n)ù   . log2(n)û   . log2(n)  +1    

6、60;.log2(n)+1ù  16.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为D 个。  A.4 B.5 C.6 D.7 17.有关二叉树以下说法正确的选项是B   A二叉树的度为2                    B一棵二叉树的度可以小于2    &#

7、160;                       C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 18.在完全二叉树中，假设一个结点是叶结点，那么它没C 。  A左子结点     B右子结点    C左子结点和右子结点 D左子结点，右子结点和兄弟结点 19.在以下情

8、况中，可称为二叉树的是B     A每个结点至多有两棵子树的树 B. 哈夫曼树    C每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树       第七章 图 1.图的深度优先遍历类似于二叉树的 A 。A先序遍历 B中序遍历 C后序遍历 D层次遍历 2.一个图如下图，假设从顶点a出发按深度优先遍历，那么可能得到的一种顶点序列为C Aabecdf Bacfebd Caebcfd Daedfcb 3.假设从无向图的任意一个顶点出发进展一

9、次深度优先搜索可以访问图中所有的顶点，那么该图一定是 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.一个有N个顶点的有向图最多有 B 条边。A N B N(N-1) C N(n-1)/2 D 2N 7.具有4个顶点的无向完全图有 A 条边。A 6 B 12 C 18 D 20 8.具有6个顶点的无向图至少有 A 条边才能确保是一个连通图。A 5 B 6 C 7 D 8 9.对于一个具有N个顶点的

10、无向图，假设采用邻接矩阵表示，那么该矩阵大小是D A N B (N-1)2 C N-1 D N_N 10.一个具有N个顶点的无向图中，要连通全部顶点至少要 C 条边 A N B N+1 C N-1 D N/2 11._图的邻接矩阵如下图，那么从顶点0出发按深度优先遍历的结果是 C 。A0 2 4 3 1 5 6 B0 1 3 6 5 4 2 C0 1 3 4 2 5 6 D0 3 6 1 5 4 2 12.图的邻接表以下图所示，那么从顶点0出发按广度优先遍历的结果是 ，按深度优先遍历的结果是 D 。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3 13.图的邻接表以下图所

11、示，那么从顶点0出发按广度优先遍历的结果是 ，按深度优先遍历的结果是 。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3 14.当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度 C 。A必定快 B不一定 C在大局部情况下要快 D取决于表递增还是递减 15.折半查找有序表4，6，10，12，20，30，50，70，88，100。假设查找表中元素58，那么它将依次与表中 A 比拟大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50 第八章 查找 1.顺序查找法合适于存储构造为B

12、的线性表。A散列存储 B顺序存储或链式存储 C压缩存储 D索引存储 2.在查找过程中，假设同时还要增、删工作，这种查找称为 B 。A、 静态查找 B、 动态查找 C、 内查找 D、 外查找 3.索引顺序表的特点是顺序表中的数据 A 。A、 有序 B、 无序 C、 块间有序 D、 散列 4.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为CA、 n B、n/2 C、(n+1)/2 D、(n-1)/2 5._将10个元素散列到1000000个单元的哈希表，那么 C 产生冲突。A、 一定会 B、一定不会 C、仍可能会 D、以上都不对 6._散列表的地址区间为016，散列函数H(k)=

13、k17，采用线性探测法解决地址冲突，将关键字26、25、72、38、1、18、59依次存储到散列表中。元素59存放在散列表中的地址为 A A、 8 B、 9 C、 10 D、 11 7.设有序表的关键字序列为1,3,9,12,32,41,45,62,75,77,82,95,100，当采用二分查找法查找值为82的节点时，经 C 次比拟后查找成功。A、 1 B、 2 C、 3 D、 4 8.设有100个元素，用折半查找法进展查找时，最大、最小比拟次数分别时 A A、 7,1 B、6,1 C、5,1 D、8,1 第九章 排序 1.对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法

14、，初始序列在 A 情况下，与排序码值总比拟次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序) D根本按排序码值升序排列 2.对n个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，在 B情况下，与排序码值总比拟次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序) D根本按排序码值升序排列 3.对n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，初始序列在 A情况下，与排序码值总比拟次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序) D根本按排序码值升序排列 4.对

15、n个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，初始序列在 B情况下，与排序码值总比拟次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序) D根本按排序码值升序排列 5.对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法在 C情况下，与排序码值总比拟次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序) D根本按排序码值升序排列 6.对n个不同的记录按排序码值从小到大次序重新排列，用快速排序方法，在 A情况下与排序码值总比拟次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无

16、序) D根本按排序码值升序排列 7.用冒泡排序方法对n个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比拟次数是 D。An-1 Bn Cn+1 Dn(n-1)2 8.以下排序方法中，与排序码值总比拟次数与待排序记录的初始序列排列状态无关的是 (D) 。A直接插入排序 B冒泡排序 C快速排序 D直接选择排序 9.将6个不同的整数进展排序，至少需要比拟 (A) 次。A5 B6 C15 D21 10.将6个不同的整数进展排序，至多需要比拟 (C) 次。A5 B6 C15 D21 11._假设需要时间复杂度在O(nlog2n)内，对整数数组进展排序，且要求排序方法是稳定的

17、，那么可选择的排序方法是 (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._假设一组

18、记录的排序码值序列为40，80，50，30，60，70，利用堆排序方法进展排序，初建的大顶堆是 (D ) 。A80，40，50，30，60，70 B80，70，60，50，40，30 C80，70，50，40，30，60 D80，60，70，30，40，50 17.假设一组记录的排序码值序列为50，80，30，40，70，60利用快速排序方法，以第一个记录为基准，得到一趟快速排序的结果为B 。A30，40，50，60，70，80 B40，30，50，80，70，60 C50，30，40，70，60，80 D40，50，30，70，60，80 18._以下几种排序方法中要求辅助空间最大的是C 。

19、A堆排序 B直接选择排序 C归并排序 D快速排序 19.Am中每个数组元素距其最终位置不远，采用以下 (A) 排序方法最节省时间。A直接插入 B堆 C快速 D直接选择 20._设有10000个互不相等的无序整数，假设仅要求找出其中前10个最大整数，最好采用 B排序方法。A归并 B堆 C快速 D直接选择 21._在以下排序方法中不需要对排序码值进展比拟就能进展排序的是 A。A：基数排序 B快速排序 C直接插入排序 D堆排序 22._给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进展排列，希尔(Shell)排序的第一趟(d1=5)结果应为D 。AB，F，C，J

20、，A，E，D，I，C，H BC，B，D，A，E，F，I，C，J，H CB，F，C，E，A，I，D，C，H，J DA，B，D，C，E，F，I，J，C，H 23.给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进展排列，冒泡排序(大数下沉)的第一趟排序结果应为C 。AB，F，C，J，A，E，D，I，C，H BC，B，D，A，E，F，I，C，J，H CB，F，C，E，A，I，D，C，H，J DA，B，D，C，E，F，I，J，C，H 24.给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进展排列，快速排序的第一趟排序结果为B 。A

21、B，F，C，J，A，E，D，I，C，H BC，B，D，A，E，F，I，C，J，H CB，F，C，E，A，I，D，C，H，J DA，B，D，C，E，F，I，J，C，H 25._给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进展排列，二路归并排序的第一趟排序结果是A 。AB，F，C，J，A，E，D，I，C，H BC，B，D，A，E，F，I，C，J，H CB，F，C，E，A，I，D，C，H，J DA，B，D，C，E，F，I，J，C，H 简答题 第一章绪论 1.请分别给出数据、数据对象、数据元素、数据项的含义，并说明四者的关系。数据(Data):是对信息的一种符号

22、表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。一个得分点数据元素(Data Element):是数据的根本单位，在计算机程序中通常作为一个整体进展考虑和处理，相当于表中的一条记录。一个得分点数据项：相当于记录的“域”, 是数据的不可分割的最小单位,如学号一个得分点数据对象：性质一样的数据元素的集合，是数据的一个子集.例如: 同一个班的所有学生记录集合。一个得分点关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，数据元素是由数据项组成。一个得分点评分标准，总共5个得分点，每段话一个得分。2.请给出数据的逻辑构造的含义，并举例说明数据的逻辑构造

23、通常有哪些。数据的逻辑构造：指数据元素之间的逻辑关系。即用自然语言描绘数据，它与数据的存储无关，是独立于计算机的，逻辑构造有四种。一个得分点集合构造：仅同属一个集合构造名字0.5个得分点、举例0.5得分点 线性构造: 一对一1:1) 构造名字0.5个得分点、举例0.5得分点 树 结 构: 一对多1:n) 构造名字0.5个得分点、举例0.5得分点 图 结 构: 多对多 (m:n) 构造名字0.5个得分点、举例0.5得分点 评分标准：每段话一个得分点，总共5个得分点。什么是数据的物理构造？有哪些物理构造？数据的物理构造与逻辑构造有什么区别与联络？ 数据的物理构造：物理构造亦称存储构造，是数据的逻辑

24、构造在计算机存储器内的表示或映像。它依赖于计算机。一个得分点存储构造可分为4大类：顺序、链式、索引、散列。共2个得分点，一个0.5得分点区别：数据的逻辑构造属于用户视图，是面向问题的，数据的存储构造属于详细实现的视图，是面向计算机的。一个得分点联络：一种数据的逻辑构造可以用多种存储构造来存储，而采用不同的存储构造其处理的效率往往不同。一个得分点评分标准：共5个得分点，按照每段话各自标注的得分点进展评分。3.求两个正整数 m，n 中的最大数MA_的算法 1假设 m > n 那么 ma_=m 2假设 m this.curlen+1| this.curlen>=this.length)

25、return false; /从第i个位置开场顺序表所有结点均后移一个位置1个得分点int n = this.curlen; for(;n>=i;n-) datan = datan-1; /插入新结点stu1个得分点datan = stu; this.curlen+;1个得分点return true; public static void main(String args) /初始化数据2个得分点LineList lst=new LineList; Student stu1 = new Student(“120_02“,“李华“); Student stu2 = new Student(

26、“120_03“,“王丽“); lst.data0= stu1; lst.data1= stu2; /进展插入操作1个得分点Student stu3 = new Student(“120_01“,“杨三“); lst.insert(1, stu3); 评分标准：总共15个得分点，其中程序标准、语法3个得分点，语法有问题但不影响程序逻辑，按0.5得分点每一处扣分，扣完为止，程序逻辑12个得分点按照程序代码各处标注分数进展打分2.某个图书馆的图书信息表如下表所示，请使用顺序表构造编程实现将图书信息01 、鹿鼎记插入到表中第一条的位置。图书号ID书名(Name) 02 神雕侠侣 03 鸳鸯刀 详细要

27、求：编写代码定义顺序表构造，完成该信息表已有数据的初始化工作，最后完成数据的插入。class Book/两个得分点 public String no; /图书编号 public String name; /图书名称 public Book(String no, String name) this.no=no; =name; public class LineList /LineList为线性表名 int length = 35; /表长度1个得分点Book data = new Booklength; / 顺序表数组1个得分点 int curlen = 0; /实际表长1个得

28、分点/插入方法 public boolean insert(int i,Book book) /插入位置正确与否判断1个得分点if(i this.curlen+1| this.curlen>=this.length) return false; /从第i个位置开场顺序表所有结点均后移一个位置1个得分点int n = this.curlen; for(;n>=i;n-) datan = datan-1; /插入新结点book1个得分点datan = book; this.curlen+;1个得分点return true; public static void main(String

29、args) /初始化数据2个得分点LineList lst=new LineList; Book book1 = new Book(“02“,“神雕侠侣“); Book book2 = new Book(“03“,“鸳鸯刀“); lst.data0= book1; lst.data1= book2; /进展插入操作1个得分点Book book3 = new Book(“01“,“鹿鼎记“); lst.insert(1, book3); 评分标准：总共15个得分点，其中程序标准、语法3个得分点，语法有问题但不影响程序逻辑，按0.5得分点每一处扣分，扣完为止，程序逻辑12个得分点按照程序代码各处标

30、注分数进展打分3.某个教务系统的课程信息表如下表所示，请使用顺序表构造编程实现将课程信息01 、数据构造插入到表中第一条的位置。课程号ID课程名(Name) 02 软件工程 03 UML 详细要求：编写代码定义顺序表构造，完成该信息表已有数据的初始化工作，最后完成数据的插入。class Lession/两个得分点 public String no; /课程编号 public String name; /课程名称 public Lession(String no, String name) this.no=no; =name; public class LineList /Li

31、neList为线性表名 int length = 35; /表长度1个得分点Lession data = new Lessionlength; / 顺序表数组1个得分点 int curlen = 0; /实际表长1个得分点/插入方法 public boolean insert(int i,Lession lession) /插入位置正确与否判断1个得分点if(i this.curlen+1| this.curlen>=this.length) return false; /从第i个位置开场顺序表所有结点均后移一个位置1个得分点int n = this.curlen; for(;n>

32、=i;n-) datan = datan-1; /插入新结点lession1个得分点datan = lession; this.curlen+;1个得分点return true; public static void main(String args) /初始化数据2个得分点LineList lst=new LineList; Lession lession1 = new Lession(“02“,“软件工程“); Lession lession2 = new Lession(“03“,“UML“); lst.data0= lession1; lst.data1= lession2; /进展插

33、入操作1个得分点Lession lession3 = new Lession(“01“,“数据构造“); lst.insert(1, lession3); 评分标准：总共15个得分点，其中程序标准、语法3个得分点，语法有问题但不影响程序逻辑，按0.5得分点每一处扣分，扣完为止，程序逻辑12个得分点按照程序代码各处标注分数进展打分4.某个班级的学生信息表如下表所示，请使用顺序表构造编程实现将表中第一条学生信息删除。学号ID姓名(Name) 120_01 杨三 120_02 李华 详细要求：编写代码定义顺序表构造，完成该信息表已有数据的初始化工作，最后完成数据的删除。class Student/2

34、个得分点 public String no; /学生学号 public String name; /学生姓名 public Student(String no, String name) this.no=no; =name; public class LineList /LineList为线性表名 int length = 35; /表长度1个得分点Student data = new Studentlength; / 顺序表数组1个得分点 int curlen = 0; /实际表长1个得分点/删除方法 public Student delete(int i) /删除位置正确

35、与否判断1个得分点if(ithis.curlen) System.out.println(“删除位置有误！“); return null; /保存删除前第i个数据元素这行代码可有可无，不计分Student stu = this.datai-1; /从第i+1个位置开场依次向前移一个位置1个得分点for(int n = i;nthis.curlen) System.out.println(“删除位置有误！“); return null; /保存删除前第i个数据元素这行代码可有可无，不计分Book book = this.datai-1; /从第i+1个位置开场依次向前移一个位置1个得分点for(

36、int n = i;nthis.curlen) System.out.println(“删除位置有误！“); return null; /保存删除前第i个数据元素这行代码可有可无，不计分Lession lession = this.datai-1; /从第i+1个位置开场依次向前移一个位置1个得分点for(int n = i;n0)/判断输出结果1个得分点 System.out.println(“查找成功，数据在表中第”+ret+”的位置”); else System.out.println(“查找失败，数据在表中未找到！”); 评分标准：总共15个得分点，其中程序标准、语法3个得分点，语法有

37、问题但不影响程序逻辑，按0.5得分点每一处扣分，扣完为止，程序逻辑12个得分点按照程序代码各处标注分数进展打分2.某个图书馆的图书信息表如下表所示，请使用顺序表构造编程实现查找图书 03 、鸳鸯刀在表中的位置。书号ID书名(Name) 02 神雕侠侣 03 鸳鸯刀 详细要求：编写代码定义顺序表构造，完成该信息表已有数据的初始化工作，最后完成数据的查找并输出查找的位置。class Book/2个得分点 public String no; /图书书号 public String name; /图书书名 public Book(String no, String name) this.no=no;

38、=name; public class LineList /LineList为线性表名 int length = 35; /表长度1个得分点Book data = new Booklength; / 顺序表数组1个得分点 int curlen = 0; /实际表长1个得分点/查找方法 public int locate(Book book) /循环依次查找 for (int i=0; i0)/判断输出结果1个得分点 System.out.println(“查找成功，数据在表中第”+ret+”的位置”); else System.out.println(“查找失败，数据在表中未

39、找到！”); 评分标准：总共15个得分点，其中程序标准、语法3个得分点，语法有问题但不影响程序逻辑，按0.5得分点每一处扣分，扣完为止，程序逻辑12个得分点按照程序代码各处标注分数进展打分3.某个教务系统的课程信息表如下表所示，请使用顺序表构造编程实现查找课程 03 、数据机构在表中的位置。书号ID书名(Name) 02 dos操作系统 03 数据构造 详细要求：编写代码定义顺序表构造，完成该信息表已有数据的初始化工作，最后完成数据的查找并输出查找的位置。class Lession/2个得分点 public String no; /课程书号 public String name; /课程书名 public Lession(String no, String name) this.no=no; =name; public class LineList /LineList为线性表名 int length = 35; /表长度1个得分点Lession data = new Lessionlength; / 顺序表数组1个得分点 int curlen = 0; /实际表长1个得分点/查找方法 publi