数据结构考试题库含答案_资格考试-教师资格考试.pdf

《数据结构考试题库含答案_资格考试-教师资格考试.pdf》由会员分享，可在线阅读，更多相关《数据结构考试题库含答案_资格考试-教师资格考试.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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 第六章 树和二叉树.46 第七章 图.

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

3、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、正确

4、性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分

5、是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 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.在数据结构中，从逻辑上可以把数据结构分

6、成（C ）A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种()的存储结构，线性表的链式存储结构是一种（A ）存储结构。A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A）for(i=1;i=n;+i)for(j=1;j=n;+j)c ij=0;A、O(n2)B、O(n)C、O(2n)D、O(2n2)15.*下列程序的空间复杂度是（A）for(i=1;i=n;+i)for(j=1;j=m;+j)c ij=0;A、O(m*n)B、O(m+n)C、O(m-n)D、O(m/n)六

7、章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成

8、绩表 16.*求下列程序段的时间复杂度(B )for(i=1;i=n;i+)for(j=1;j=n;j+)x=x+1;A、O(n2)B、O(n)C、O(1)D、O(0)第二章 线性表 1.关于线性表的说法不正确的是？（D）A、存在唯一的一个被称为“第一个”的数据元素（开始结点）B、存在唯一的一个被称为“最后一个”的数据元素（终端结点）C、除第一个之外，集合中的每个数据元素均只有一个前驱 D、除第一个之外，集合中的每个数据元素均只有一个后继 2.关于顺序表的说法不正确的是？（D）A、逻辑关系上相邻的两个元素在物理存储位置上也相邻 B、可以随机存取表中任一元素，方便快捷 C、在线性表中插入某一元素

9、时，往往需要移动大量元素 D、在线性表中删除某一元素时，无需移动大量元素 3.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用什么存储结构？（A）A、顺序表 B、单链表 C、循环链表 D、双链表 4.在一个长度为 n 的顺序表中第 i 个元素（1=i0)个结点的完全二叉树的深度为(C )。.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 一

10、棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 2 18.在完全二叉树中，若一个结点是叶结点，则它没（C）。A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点 19.在下列情况中，可称为二叉树的是（B ）A每个结点至多有两棵子树的树 B.哈夫曼树 C每个结点至多有两棵子树的有序树 D.每个结点只有一棵右子树 第七章 图 1.图的深度优先遍历类似于二叉树的（A ）。A先序遍历 B中序遍历 C后序遍历 D层次遍历 2.已知一个图如图所示，若从顶点 a 出发按深度优先遍历，则可能得到的一种顶点序列为（C）Aabecdf Bacfe

11、bd Caebcfd Daedfcb 3.若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（B ）图。A非连通 B连通 C强连通 D有向 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分

12、那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 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 个顶点的无向

13、图至少有（A）条边才能确保是一个连通图。A 5 B 6 C 7 D 8 9.对于一个具有 N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是（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 ）。0100011101100001011010110011001000110010011011110 A0 2 4 3 1 5 6 B0 1 3 6 5 4 2 C0 1 3 4 2 5 6 D0 3 6

14、 1 5 4 2 12.已知图的邻接表下图所示，则从顶点 0 出发按广度优先遍历的结果是（），按深度优先遍历的结果是（D ）。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 3 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对

15、象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 13.已知图的邻接表下图所示，则从顶点 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，2

16、0，30，50，70，88，100）。若查找表中元素 58，则它将依次与表中（A ）比较大小，查找结果是失败。A20，70，30，50 B30，88，70，50 C20，50 D30，88，50 第八章 查找 1.顺序查找法适合于存储结构为（B）的线性表。A散列存储 B顺序存储或链式存储 C压缩存储 D索引存储 2.在查找过程中，若同时还要增、删工作，这种查找称为（B ）。A、静态查找 B、动态查找 C、内查找 D、外查找 3.索引顺序表的特点是顺序表中的数据（A ）。A、有序 B、无序 C、块间有序 D、散列 4.采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为（C）A、

17、n B、n/2 C、(n+1)/2 D、(n-1)/2 5.*将 10 个元素散列到 1000000 个单元的哈希表，则（C ）产生冲突。A、一定会 B、一定不会 C、仍可能会 D、以上都不对 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记

18、录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 6.*散列表的地址区间为 016，散列函数 H(k)=k%17，采用线性探测法解决地址冲突，将关键字 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 ）次比较

19、后查找成功。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 个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，初始序列在 （A）情况下，与排序码值总比较次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序)D基本按排序码值升序排列 2.对 n 个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方法，在 （B）情况下，与排序码值总比较次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随

20、机排列(完全无序)D基本按排序码值升序排列 3.对n 个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，初始序列在 （A）情况下，与排序码值总比较次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序)D基本按排序码值升序排列 4.对n 个不同的记录按排序码值从小到大次序重新排列，用直接插入排序方法，初始序列在 （B）情况下，与排序码值总比较次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序)D基本按排序码值升序排列 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和

21、广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 5.对 n 个不同的记录按排序码值从小到大次序重新排列，用快速排序方法在 （C）情况下，与排序码

22、值总比较次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序)D基本按排序码值升序排列 6.对 n 个不同的记录按排序码值从小到大次序重新排列，用快速排序方法，在 （A）情况下与排序码值总比较次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列 C随机排列(完全无序)D基本按排序码值升序排列 7.用冒泡排序方法对 n 个记录按排序码值从小到大排序时，当初始序列是按排序码值从大到小排列时，与码值总比较次数是 （D）。An-1 Bn Cn+1 Dn(n-1)2 8.下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状态无关的是 (D)。A直接插入排

23、序 B冒泡排序 C快速排序 D直接选择排序 9.将 6 个不同的整数进行排序，至少需要比较 (A)次。A5 B6 C15 D21 10.将 6 个不同的整数进行排序，至多需要比较 (C)次。A5 B6 C15 D21 11.*若需要时间复杂度在O(nlog2n)内，对整数数组进行排序，且要求排序方法是稳定的，则可选择的排序方法是 (B)。A快速排序 B归并排序 C堆排序 D直接插入排序 12.当待排序的整数是有序序列时，采用 (B)方法比较好，其时间复杂度为O(n)。A快速排序 B冒泡排序 C归并排序 D直接选择排序 13.当待排序的整数是有序序列时，采用 （A）方法比较差，达到最坏情况下时间

24、复杂度为 O(n2)。A快速排序 B冒泡排序 C归并排序 D直接选择排序 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩

25、表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 14.当待排序的整数是有序序列时，无论待排序序列排列是否有序，采用 （D）方法的时间复杂度都是 O(n2)。A快速排序 B冒泡排序 C归并排序 D直接选择排序 15.*堆是一种 (B)排序。A插入 B选择 C交换 D归并 16.*若一组记录的排序码值序列为 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.若一组记录的排序码值

26、序列为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）。A堆排序 B直接选择排序 C归并排序 D快速排序 19.已知 Am中每个数组元素距其最终位置不远，采用下列 (A)排序方法最节省时间。A直接插入 B堆 C快速 D直接选择 20.*设有 10000 个互不相等的无序整数，若仅要求找出其中前 10 个最大整数，最好采用 （B）排序方法。

27、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，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 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序

28、编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 DA，B，D，C，E，F，I，J，C，H 23.给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列的次序进行排列，冒泡

29、排序(大数下沉)的第一趟排序结果应为（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）。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 25.*给定排序码值序列为F，B，J，C，E，A，I，D，C，H，对其按字母的字典序列

30、的次序进行排列，二路归并排序的第一趟排序结果是（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):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（一个得分点）数据元素(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，相当于表中的一条记录。（一个得分点）六章树和二叉树第七章

31、图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 数据项：相当

32、于记录的“域”,是数据的不可分割的最小单位,如学号（一个得分点）数据对象：性质相同的数据元素的集合，是数据的一个子集.例如:同一个班的所有学生记录集合。（一个得分点）关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，数据元素是由数据项组成。（一个得分点）评分标准，总共 5 个得分点，每段话一个得分。2.请给出数据的逻辑结构的含义，并举例说明数据的逻辑结构通常有哪些。数据的逻辑结构：指数据元素之间的逻辑关系。即用自然语言描述数据，它与数据的存储无关，是独立于计算机的，逻辑结构有四种。（一个得分点）集合结构：仅同属一个集合（结构名字 0.5 个得分点、举例 0.5 得分点）线

33、性结构:一对一（1:1)（结构名字 0.5 个得分点、举例 0.5 得分点）树 结 构:一对多（1:n)（结构名字 0.5 个得分点、举例 0.5 得分点）六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对

34、象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 图 结 构:多对多 (m:n)（结构名字 0.5 个得分点、举例 0.5 得分点）评分标准：每段话一个得分点，总共 5 个得分点。什么是数据的物理结构？有哪些物理结构？数据的物理结构与逻辑结构有什么区别与联系？数据的物理结构：物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。（一个得分点）存储结构可分为 4 大类：顺序、链式、索引、散列。（共 2 个得分点，一个 0.5 得分点）区别：数据的逻辑

35、结构属于用户视图，是面向问题的，数据的存储结构属于具体实现的视图，是面向计算机的。（一个得分点）联系：一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构其处理的效率往往不同。（一个得分点）评分标准：共 5 个得分点，按照每段话各自标注的得分点进行评分。3.求两个正整数 m，n 中的最大数 MAX 的算法 （1）若 m n 则 max=m （2）若 m=n 则 max=n 请根据上述算法解释一下算法的组成要素有哪些，分别是什么。算法由操作、控制结构、数据结构 3 要素组成 操作包含：算术运算、关系比较、逻辑运算、数据传送（输入、输出、赋值）（一个得分点）例子中有关系比较和赋值计算的

36、操作。（一个得分点）控制结构包含：顺序结构、选择结构、循环结构（一个得分点）例子中有选择结构（一个得分点）数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。（一个得分点）本例是数值问题，涉及到两个正整数，因此使用基本的整数类型就可以解决问题。（一六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不

37、针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 个得分点）评分标准：本题共 6 个得分点，每段话一个得分点。4.简述算法的基本性质 1）输入：0 个或多个输入 2）输出：1 个或多个输出 3）有穷性：算法必须在有限步内结束 4）确定性：组成算法的操作必须清晰无二义性 5）可行性：组成算法的操作必须能够在计算机上实现 评分标准，本题共 5 个得分点，每个要

38、点一分。5.简述算法的设计要求 1、正确性（correctness）2、可读性（readability）3、健壮性（robustness）4、通用性（generality）5、效率与存储的要求（执行算法所耗费的存储空间、执行算法所耗费的时间）评分标准，本题共 5 个得分点，每个要点一分。6.评价算法好坏的 3 条主要标准 1）算法实现所耗费的时间。2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间。3）算法应易于理解、易于编码、易于调试等。评分标准，本题共 3 个得分点，每个要点一分。7.请简述数据结构所研究的三种基本结构，以及数据元素间的关系。线性结构：数据元素之间一对一的关系。（2 分

39、）树形结构：数据元素之间一对多的关系。（1.5 分）图形结构：数据元素之间多对多的关系。（1.5 分）8.请问算法的分析和评价的两个标准，以及各自作用。时间复杂度：评估算法运行所需时间。（1.5+1 分）空间复杂度：评估算法运行时所需最大存储空间。（1.5+1 分）六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学

40、科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 9.请说出三种逻辑数据结构，以及他们的特点。（5 分）（1）线性结构：数据元素只有一个前驱数据元素和一个后继数据元素。（2 分）（2）树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素。（1.5 分）（3）图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素。（1.5 分）10.评价

41、算法的主要标准是什么？（1）算法实现所耗费的时间（2 分）（2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间。（2 分）（3）算法应易于理解、易于编码、易于调试。（1 分）11.请说出三种逻辑数据结构，并分别画图表示它们。（a,2 分，b,c 各 1.5 分）12.算法的基本性质有哪些？并简述每个特性。(5 分)（1）有穷性.（1 分）（2）确定性.（1 分）（3）可行性.（1 分）（4）输入性.（1 分）（5）输出性.（1 分）13.通常从那几个方面来评价算法的质量?(5 分)通常从四个方面评价算法的质量：正确性、可读性、健壮性和高效性。（少一个扣 1 分）六章树和二叉树第七章图第八章

42、查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 14.请描述线性数据

43、结构的两种存储方式，并说出其各有什么特点。顺序存储：连续存储，易于定位，不易于插入和删除。（1+1.5 分）链式存储：非连续存储，不易于定位，易于插入和删除。（1+1.5 分）15.请问算法的分析和评价的两种方法，它们关注点各有什么不同？（简单）空间效率：关注算法对内存的占用度。（1+1.5 分）时间效率：关注算法的运算速度。（1+1.5 分）第二章 线性表 1.请问如果要插入一个数据到一个线性表中，顺序表和链表哪个的效率高？为什么？链表的效率高（2 分），因为顺序表要移动插入位置后的每一个元素的位置给新数据腾位置（1.5 分）。链表只需要将前一个数据的指针指向新数据并将新数据的指针指向后一个

44、数据即可（1.5 分）。2.线性表有哪些特点？1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素；（2 分）2）第一个数据元素没有前驱数据元素；（1.5 分）3）最后一个数据元素没有后继数据元素。（1.5 分）3.顺序存储结构的优缺点有哪些?(中等)顺序存储结构的优点:（2.5 分）存储空间连续 逻辑相邻，物理相邻 可随机存取任一元素 缺点:（2.5 分）插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章

45、树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是数据对象分是数据项某班级的学生成绩表 4.单链式存储结构的优缺点有哪些?(中等)单链式存储结构的优点:（2.5 分）不需预先分配空间，空间利用充分

46、 插入、删除操作简单,无需移动大量的元素 表容量易于扩充 缺点:（2.5 分）每个数据元素，除存储本身信息外，还需空间存储其直接后继的信息 逻辑相邻，物理不一定相邻 不可随机存取任一元素,只能从链表头依次查找.5.有顺序表 A=(a0,a1,a2,.a8,a9,a19)，要在 a8,a9 之间插入一个元素 a20，请描述其操作(思想)步骤。(中等)插入思想或步骤：根据顺序表的存储特点，要在表中某位置 10 插入一新数据元素,则要进行如下两步操作：（1）、从位置 10 到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第 10 个位置。（2 分）（2）、将新结点插入到空

47、余位置 10 处。2 分）（3）表长度加 1.（1 分）6.有顺序表 A=(a0,a1,a2,.a8,a9,a19)，要删除一个元素 a9，请描述其操作(思想)步骤。(中等)（1）然后将从位置 11 到表尾的所有数据元素依次向前移一个存储位置。（3 分）（2）表长度减 1.（2 分）7.请描述在顺序表中第 i个位置插入新的数据 x 操作过程。根据顺序表的存储特点，要在表中某位置 i 插入一新数据元素，则要进行如下两步操作：（1）从位置 i 到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第 i 个位置；（2 分）（2）将新数据 x 插入到空余位置 i 处。（2 分）

48、（3）表长度加 1.（1 分）六章树和二叉树第七章图第八章查找第九章排序简答题第一章绪论第二章线性表第三章栈和队列第四章串第五章数组和广义表第六章树和二叉树第七章图第八章查找第九章排序编程题第一章绪论第二章线性表第三章栈和队列第四章针对什么问题而产生的针对非数值计算的程序设计问题针对数值计算的程序设计问题数值计算与非数值计算的问题都针对两者都不针对数据结构这门学科的研究内容下面选项最准确的是研究数据对象和数据之间的关系研究数据对象记录其中数据结构考了分那么下面关于数据对象数据元素数据项描述正确的是某班级的学生成绩表是数据元素分是数据项某班级的学生成绩表是数据对象分是数据元素某班级的学生成绩表是

49、数据对象分是数据项某班级的学生成绩表 8.请描述在顺序表中删除第 i个位置的数据的过程。（1）然后将从位置 i 到表尾的所有数据元素依次向前移一个存储位置。（3 分）（2）表长度减 1.（2 分）9.请描述在一个单链表中插入一个数据 q 的插入过程。（1）找到将插入数据位置的前一个结点 p;（1 分）（2）q 的 next 值等于 p 的 next 值;（2 分）（3）p 的 next 值等于 q；（2 分）10.请描述从一个单链表中删除一个数据的删除过程。（1）找到将被删除数据的前一个结点 p;（2 分）（2）p 的 next 指针指向被删除数据的后一个结点；（2 分）（3）将被删除数据原来

50、的 next 指针指向 null;（1 分）第三章 栈和队列 1.请简述线性表、栈和队列三者之间的联系。（简单）（1）线性表、栈和队列都属于线性结构。（2 分）（2）栈和队列都是特殊的线性表，并且都有顺序存储、链式存储两种存储方式。（1 分）（3）栈是一种先进后出的线性表，队列是一种先进先出的线性表（2 分）2.在计算机进行运算时，需要把十进制转换为二进制。请问答：这种数制转换可以借助于哪种数据结构实现、及原因。答:栈。（2 分）原因：（3 分）在进行数值转换时，其实质是求余的过程，并且余数的倒序序列正是所求结果。栈是一种先进后出的线性结构，能够满足这种操作。3.有一字符序列 abcde 依次