数据结构考试题库含答案

《数据结构考试题库含答案》由会员分享，可在线阅读，更多相关《数据结构考试题库含答案（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第七章 图46第八章 查找46第九章 排序51选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的？（A ）A、针对非

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

3、元素，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.数据在计算机内有

4、链式和顺序两种存储方式，在存储空间使用的灵活性上， 链式存储比顺序存储要（B ） 。A、低 B、高C、相同D、不好说10. 算法的时间复杂度取决于（ C ）A 、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说11. 数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ） 。A、正确B、错误C、前半句对，后半句错D、前半句错，后半句对12. 在数据结构中，从逻辑上可以把数据结构分成（ C ）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构13. 线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是

5、一 种（ A ）存储结构。A、随机存取B、顺序存取C、索引存取D、散列存取14. *下列程序的时间复杂度是（A ）for (i=1; i0)个结点的完全二叉树的深度为(C )。 .log2(n) . log2(n) . log2(n) +1 .log2(n)+1 16. 在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为（D ）个。 A. 4 B. 5 C.6 D.717. 有关二叉树下列说法正确的是（B ） A二叉树的度为 2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为 2D二叉树中任何一个结点的度都

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

7、搜索可以访问图中所有 的顶点，则该图一定是（ B ）图。A非连通 B连通 C强连通 D有向4.在一个图中，所有顶点的度数之和等于所有边数的（ C ）倍。A 1/2 B 1 C 2 D 35.在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ B ） 倍。A 1/2 B 1 C 2 D 36.一个有 N 个顶点的有向图最多有（ B ）条边。A N B N(N-1) C N(n-1)/2 D 2N7.具有 4 个顶点的无向完全图有（ A ）条边。A 6 B 12 C 18 D 208.具有 6 个顶点的无向图至少有（ A ）条边才能确保是一个连通图。A 5 B 6 C 7 D 89.对于一

8、个具有 N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵大小是 （D ）A N B (N-1)2 C N-1 D N*N10. 一个具有 N 个顶点的无向图中，要连通全部顶点至少要（ C ）条边A N B N+1 C N-1 D N/211. *已知图的邻接矩阵如图所示，则从顶点 0 出发按深度优先遍历的结果是（ C ） 。0100011101100001011010110011001000110010011011110A0 2 4 3 1 5 6B0 1 3 6 5 4 2C0 1 3 4 2 5 6D0 3 6 1 5 4 212. 已知图的邻接表下图所示，则从顶点 0 出发按广度优先遍历

9、的结果是（ ） ，按深度优先遍历的结果是（ D ） 。A0 1 3 2 B0 2 3 1C0 3 2 1 D0 1 2 313. 已知图的邻接表下图所示，则从顶点 0 出发按广度优先遍历的结果是（ ） ，按深度优先遍历的结果是（ ） 。A0 1 3 2 B0 2 3 1 C0 3 2 1 D0 1 2 314. 当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序 查找，但前者比后者的查找速度（ C ） 。 A必定快 B不一定 C在大部分情况下要快 D取决于表递增还是递减15. 折半查找有序表（4，6，10，12，20，30，50，70，88，100） 。若查找 表中元素 58，则

10、它将依次与表中（ 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、 nB、n/2C、(n+1)/2D、(n-

11、1)/25.*将 10 个元素散列到 1000000 个单元的哈希表，则（ C ）产生冲突。A、 一定会 B、一定不会 C、仍可能会 D、以上都不对6.*散列表的地址区间为 016，散列函数 H(k)=k%17，采用线性探测法解决 地址冲突，将关键字 26、25、72、38、1、18、59 依次存储到散列表中。 元素 59 存放在散列表中的地址为（ A ）A、 8 B、 9 C、 10D、 117.设有序表的关键字序列为1,3,9,12,32,41,45,62,75,77,82,95,100，当采用 二分查找法查找值为 82 的节点时，经（ C ）次比较后查找成功。A、 1B、 2 C、 3D

12、、 48.设有 100 个元素，用折半查找法进行查找时，最大、最小比较次数分别时 （ A ）A、 7,1 B、6,1C、5,1D、8,1第九章 排序1.对 n 个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方 法，初始序列在 （A ） 情况下，与排序码值总比较次数最少。A按排序码值从小到大排列 B按排序码值从大到小排列C随机排列(完全无序) D基本按排序码值升序排列2.对 n 个不同的记录按排序码值从小到大次序重新排列，用冒泡(起泡)排序方 法，在 （B） 情况下，与排序码值总比较次数最多。A按排序码值从小到大排列 B按排序码值从大到小排列C随机排列(完全无序) D基本按排序码

13、值升序排列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） 。An-1 Bn Cn+1 Dn(n-1)28. 下列排序方法中，与排序码值总比较次数与待排序记录的初始序列排列状 态无关的是