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
2、第八章 查找 .46第九章 排序 .51选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（A ）A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对 D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系 B、研究数据对象C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90 分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班
3、级的学生成绩表是数据对象，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、数据复杂性和程序复杂性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 .log2(n)+1 16. 在一棵三元树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1的结点数为 2 个，则度为 0 的结点数为（D ）个。 A. 4 B. 5
6、 C.6 D.717. 有关二叉树下列说法正确的是（B ） A二叉树的度为 2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的度都为 218. 在完全二叉树中，若一个结点是叶结点，则它没（C ） 。 A左子结点 B右子结点 C左子结点和右子结点 D左子结点，右子结点和兄弟结点19. 在下列情况中，可称为二叉树的是（B ） A每个结点至多有两棵子树的树 B. 哈夫曼树 C每个结点至多有两棵子树的有序树 D. 每个结点只有一棵右子树 第七章 图1. 图的深度优先遍历类似于二叉树的（ A ） 。A先序遍历 B中序遍历 C后序遍历 D层次遍历2. 已知一个图如
7、图所示，若从顶点 a 出发按深度优先遍历，则可能得到的一种顶点序列为（C ）Aabecdf Bacfebd Caebcfd Daedfcb3. 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ 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.
8、具有 4 个顶点的无向完全图有（ A ）条边。A 6 B 12 C 18 D 208. 具有 6 个顶点的无向图至少有（ A ）条边才能确保是一个连通图。A 5 B 6 C 7 D 89. 对于一个具有 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 ） 。 0101A0 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
