郑州大学远程教育学院数据结构试题及答案

郑州大学现代远程教育《数据结构》课程（本科）学习指导书郭纯一编课程内容与基本要求“数据结构”在计算机科学中是一门综合性的专业基础课。

本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。

本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。

课程学习进度与指导章节课程内容学时分配学习指导（均以课件学习为主）第一章绪论4学时重点掌握基本概念和时间复杂度的计算方法第二章*线性表10学时重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的2种方法第三章栈和队列8学时重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用第四章串2学时重点掌握串的术语、串操作结果和不同存储结构的特点第七章*树和二叉树10学时重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和Huffman编码的构造方法第八章图8学时重点掌握图的术语、存储、遍历算法及应用；掌握最小生成树的2种构造方法及特点、会求拓扑排序序列和单源最短路径第九章*查找8学时重点掌握各种动态查找表的构造过程、性能分析、插入/删除方法；掌握静态查找表的顺序、折半和分块查找及ASL求法第十章*排序8学时掌握关于排序的术语及分类方法；重点掌握插入排序、交换排序、选择排序等内排序方法及其性能分析方法第一章绪论一、章节学习目标与要求1、理解数据抽象和信息隐蔽原则2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序二、本章重点、难点重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。

习题1一、单项选择题1.数据结构是指（）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（）。

A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。

for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)5.算法分析的目的是（1），算法分析的两个主要方面是（2）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2） A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。

（1） A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。

A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。

A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。

A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。

A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是______________和_________________。

2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。

数据结构考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。

A. 结构中元素的个数B. 结构中元素之间是否有一对一的对应关系C. 结构中元素之间是否有层次关系D. 结构中元素之间是否有顺序关系答案：C2. 链式存储结构相比于顺序存储结构的优势在于（）。

A. 节省存储空间B. 可以方便地进行插入和删除操作C. 可以随机访问任意元素D. 可以存储在非连续的存储单元中答案：B3. 下列关于栈的描述，正确的是（）。

A. 栈是一种先进先出（FIFO）的数据结构B. 栈是一种后进先出（LIFO）的数据结构C. 栈可以实现递归算法D. 栈只能进行单一方向的插入和删除操作答案：B4. 在二叉树中，度为2的节点称为（）。

A. 叶子节点B. 内部节点C. 分支节点D. 根节点答案：B5. 哈希表解决冲突的常用方法不包括（）。

A. 分离链接法B. 开放寻址法C. 链地址法D. 二分查找法答案：D6. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C7. 在图的遍历中，深度优先搜索（DFS）使用的是（）。

A. 队列C. 链表D. 数组答案：B8. 以下哪种排序算法是不稳定的（）。

A. 冒泡排序B. 快速排序C. 归并排序D. 插入排序答案：B9. 一个具有n个顶点的无向图，其边的最大数量是（）。

A. nB. n(n-1)/2C. n^2答案：B10. 以下哪个算法不是动态规划算法（）。

A. 斐波那契数列B. 最长公共子序列C. 快速排序D. 0/1背包问题答案：C二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度为O(n^2)，表示该算法的执行时间随着输入数据规模的增加而______。

答案：呈二次方增长2. 一个长度为n的数组，使用二分查找算法查找一个元素的平均时间复杂度为O(____)。

数据结构（Java版）_郑州大学中国大学mooc课后章节答案期末考试题库2023年1.对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列一定相同。

参考答案:错误2.在链队列中，即使不设置尾指针，也能进行入队操作。

参考答案:正确3.循环顺序队列和循环链队列都存在空间一处问题。

参考答案:错误4.直接选择排序的时间复杂度与关键字的初始排列无关。

参考答案:正确5.一个循环链表可以由给定的头指针或尾指针来唯一标识。

参考答案:正确6.所谓随机存取，就是通过首地址和元素的序号可以在O(1)的时间内找到指定的元素。

参考答案:正确7.快速排序在最坏情况下的时间复杂度是O(【图片】)。

参考答案:正确8.哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（）参考答案:正确9.在队列中存取数据元素的原则是（）。

参考答案:先进先出10.将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（）。

参考答案:142311.完全二叉树的存储结构通常采用顺序存储结构（）。

参考答案:正确12.在中序线索二叉树中，每一非空的线索均指向其祖先结点（）参考答案:正确13.二叉树中序线索化后，不存在空指针域（）参考答案:错误14.二叉树的层次遍历需要栈结构的支持。

参考答案:错误15.下列关于AOE网的叙述中，不正确的是（）参考答案:任何一个关键活动提前完成，那么整个工程将会提前完成16.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）参考答案:只有一个叶子结点17.引入二叉线索树的目的是（）参考答案:加快查找结点的前驱或后继的速度18.单源最短路径算法的时间复杂度为（）参考答案:O()19.对6个不同的数据元素进行直接插入排序，最多需要进行（）次关键字的比较。

参考答案:1520.完全二叉树中，若一个结点没有左孩子，则它必是树叶（）。

参考答案:正确21.已知循环队列存储在一维数组A[0【图片】n]中，且队列非空时front和rear分别指向队首元素和队尾元素。

数据结构考试题目及答案pdf一、单项选择题（每题2分，共10分）1. 在数据结构中，线性结构和非线性结构的主要区别在于（）。

A. 数据元素之间是否有逻辑关系B. 是否有且仅有一个根节点C. 是否有多个根节点D. 数据元素之间是否有顺序关系答案：A2. 链表中每个节点包含数据元素和（）。

A. 一个指针B. 多个指针C. 一个数据域D. 一个数据域和一个指针答案：D3. 在二叉树的遍历中，先序遍历的顺序是（）。

A. 根-左-右B. 左-根-右C. 右-根-左D. 根-右-左答案：A4. 哈希表解决冲突的方法不包括（）。

A. 开放寻址法B. 链地址法C. 线性探测法D. 二分查找法答案：D5. 堆是一种特殊的完全二叉树，其特点是（）。

A. 每个节点的值都大于其子节点的值B. 每个节点的值都小于其子节点的值C. 每个节点的值都大于或等于其子节点的值D. 每个节点的值都小于或等于其子节点的值答案：C二、填空题（每题2分，共10分）1. 在顺序表中，插入一个元素的平均时间复杂度为 O(n) 。

2. 栈是一种特殊的线性表，其特点是后进先出（LIFO），即后进的元素先出栈。

3. 快速排序的时间复杂度在最坏情况下为 O(n^2) 。

4. 广义表的表示形式为 (a, b, c) ，其中a、b、c可以是数据元素或子表。

5. 在图的遍历中，深度优先搜索（DFS）使用的是栈数据结构。

三、简答题（每题10分，共20分）1. 请简述二叉搜索树和平衡二叉树的区别。

答：二叉搜索树是一种特殊的二叉树，其中每个节点的左子树只包含小于该节点的值，右子树只包含大于该节点的值。

平衡二叉树除了满足二叉搜索树的性质外，还要求每个节点的左子树和右子树的高度差不超过1，以保持树的平衡，从而提高查找效率。

2. 什么是图的连通分量？请举例说明。

答：图的连通分量是指图中的最大的连通子图。

如果一个图不是连通的，那么它将被划分为若干个连通分量，每个连通分量内部的顶点都是相互连通的，但不同分量之间没有直接的边相连。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

郑州大学远程教育学院招生入学考试试卷及答案郑州大学远程教育学院招生入学考试试卷一、选择题(每小题1分，共60分)下列各题A)、B)、C)、D)四个选项中，只有一个选项是正确的，请将正确选项涂写在答题卡相应位置上，答在试卷上不得分。

1．世界上不同型号的计算机，就其工作原理而论，一般认为都基于的冯·诺依曼提出的原理。

（A）二进制数（B）布尔代数（C）开关电路（D）存储程序和控制2．下列一组数据中，最大的数是：(A)(227)8（B）(1FF)16 (C)(1010001)2（D）(789)103．第一台电子计算机ENIAC问世的10年间，称为电子管计算机时代。

其主要的硬件电路为：(A)电子管（B）晶体管 (C)集成电路（D）大规模集成电路4．计算机辅助教学的英文意义为：(A)CAD (B)CAM (C)CAT (D)CAI5．MPU的含义是：（A）多媒体计算机的简称（B）控制器的简称（C）微处理器的简称（D）中央处理器的简称6．UPS是：(A)控制器 (B)存储器 (C)不间断电源 (D)运算器7．在表示存储器的容量时，M的准确含义是：(A)1000K （B）1024K (C)1000 (D)10248．直接用计算机能够识别的二进制编码编写的语言是：（A）BASIC (B)C (C)汇编语言 (D)机器语言9．计算机只懂机器语言，而人类只熟悉高级语言，故人机通信必须借助一种中间者，此中间者就是：（A）编译程序（B）编辑程序（C）连接程序（D）装入程序10．下列语句中，正确的是：（A）1KB=1024X1024bytes （B）1KB=1024MB （C）1MB=1024X1024bytes （D）1MB=1024bytes11．图标是W1ndows的重要元素之一，对图标的描述错误的是：(A)图标可以表示被组合在一起的多个程序(B)图标既可以代表程序也可以代表文档(C)图标可能是仍然在运行但窗口被最小化的程序(D)图标只能代表某个应用程序12．Windows是一个多任务操作系统，这是指：(A)Windows可以供多个用户同时使用 (B) Windows可以运行很多种应用程序(C) Windows可以同时运行多个应用程序 (D) Windows可以同时管理多种资源13．在Windows桌面上，不能打开资源管理器的操作是：(A)先用鼠标右键单击"我的电脑"图标，然后从弹出的菜单中选取"资源管理器"(B)先用鼠标右键单击"开始"按钮，然后从弹出的菜单中选取"资源管理器"。

《数据结构》考试大纲数据结构是计算机专业的主干课、专业基础课，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。

通过教学要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，并为后续课程的学习打下良好的理论基础和实践基础。

为了检验学生学习效果，特编写此考试大纲，具体内容如下：总成绩评定办法：采用百分制，包括理论部分、实验部分、平时成绩三部分。

总成绩比例：理论成绩70%+上机成绩20%+平时成绩10%。

总成绩不及格者需要补考或重修。

1)理论成绩：为期末闭卷考试成绩，试卷由担当这门课授课任务的所有老师参与命题，考试结束后依据相同的评分标准密封改卷；2)上机成绩：主要指上机实训期间对每次实验内容的完成情况，该考核由各任课老师完成；3)平时成绩：主要包括考勤和课堂表现，该考核由各任课老师完成。

现将期末考试所要求掌握的知识点以及考试注意事项整理如下：一、考试知识点（按100分制命题）第1章数据结构概论1.了解数据、数据元素、抽象数据类型、数据结构、数据的逻辑结构与存储结构等概念。

2.了解算法的定义、特性、算法的时间复杂度、算法的空间复杂度、递归算法等概念。

第2章线性表1.掌握线性表的基本概念及其两种存储结构（顺序存储、链式存储）。

2.掌握顺序表的各种操作（插入、删除等）实现及算法复杂度。

3.掌握单链表的各种操作（插入、删除等）实现及算法复杂度。

4.了解带头结点的单链表的头结点的作用。

5.了解循环单链表、循环双链表等概念及其特点。

6.了解双链表的概念及其实现（重点是插入、删除操作的实现）。

7.掌握顺序表和链表的特点，对比他们的优缺点。

第3章串本章不考第4章桟和队列1.了解栈、队列的基本概念。

2.熟练掌握两种栈（顺序栈、链式栈）的入桟、出栈操作，并能利用栈解决实际问题。

数据结构考试试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么类型的数据结构来实现？A. 栈B. 队列C. 数组D. 链表答案：C2. 下列选项中，哪一个不是二叉树的性质？A. 任意节点的左子树和右子树的深度可能不同B. 任意节点的左子树和右子树的深度相同C. 任意节点的左子树和右子树的节点数可能不同D. 任意节点的左子树和右子树的节点数相同答案：B3. 哈希表的冲突解决方法不包括以下哪种？A. 开放定址法B. 链地址法C. 线性探测法D. 排序法答案：D4. 以下哪种排序算法的时间复杂度最低？A. 冒泡排序B. 快速排序C. 插入排序D. 归并排序答案：B5. 在图的遍历算法中，深度优先搜索（DFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：B6. 以下哪种数据结构可以有效地实现稀疏矩阵的存储？A. 顺序存储B. 链表C. 散列D. 邻接矩阵答案：C7. 在二叉搜索树中，插入一个新节点后，树的平衡因子可能为：A. -2B. 0C. 2D. 3答案：A8. 堆数据结构中，父节点的值总是大于其子节点的值，这种堆被称为：A. 最小堆B. 最大堆C. 完全二叉树D. 满二叉树答案：B9. 以下哪个算法不是动态查找表的算法？A. 直接查找B. 二分查找C. 斐波那契查找D. 哈希查找答案：A10. 在图的遍历算法中，广度优先搜索（BFS）使用的栈是：A. 系统栈B. 显式栈C. 隐式栈D. 以上都不是答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种______结构，遵循后进先出（LIFO）的原则。

答案：线性2. 一个具有n个顶点的无向图的边数最多为______。

答案：n*(n-1)/23. 快速排序算法的时间复杂度在最坏情况下为______。

答案：O(n^2)4. 在哈希表中，如果一个关键字的哈希地址已经被占用，则需要进行______。

数据结构考试题及答案详解一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用哪种数据结构实现？A. 链表B. 数组C. 栈D. 队列答案：B2. 下列哪个是二叉树的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 排序算法D. 查找算法答案：A3. 哈希表解决冲突最常用的方法是？A. 链接法B. 线性探测法C. 二次探测法D. 所有选项都是答案：D4. 栈的后进先出（LIFO）特性决定了它不能用于实现哪些数据结构？A. 队列B. 堆C. 树D. 图答案：A5. 快速排序算法的时间复杂度在最坏情况下是？A. O(n log n)B. O(n^2)C. O(n)D. O(1)答案：B二、简答题（每题10分，共30分）1. 什么是递归？请给出一个递归函数的例子。

答案：递归是一种在函数内部调用自身的编程技术。

递归函数通常有两个条件：一个基本情况（base case），用于停止递归调用；一个递归情况（recursive case），用于进行递归调用。

例如，计算阶乘的递归函数如下：```cint factorial(int n) {if (n == 0) return 1; // 基本情况return n * factorial(n - 1); // 递归情况}```2. 什么是图的深度优先搜索（DFS）？请简述其基本思想。

答案：深度优先搜索是一种遍历图的算法，它从一个顶点开始，沿着一条路径尽可能深地搜索，直到无法继续为止，然后回溯并沿着另一条路径继续搜索。

基本思想是使用一个栈来记录已访问的顶点，以避免重复访问。

3. 什么是平衡二叉搜索树？请列举至少两种常见的平衡二叉搜索树。

答案：平衡二叉搜索树是一种特殊的二叉搜索树，它保持树的高度尽可能低，以保证操作的效率。

常见的平衡二叉搜索树有AVL树和红黑树。

AVL树通过旋转操作保持平衡，红黑树通过颜色和旋转操作来保持平衡。

三、计算题（每题25分，共50分）1. 给定一个数组A，包含n个元素，请计算其归并排序的时间复杂度，并给出排序过程的一个示例。

数据结构考试试题及答案一、选择题（每题2分，共60分）1. 数据结构是指（）。

A. 用来存储和组织数据的方式和方法B. 构建数据的逻辑关系C. 存储和处理数据的工具和技术D. 对数据进行操作和管理的过程2. 下列哪种数据结构是线性结构（）。

A. 树B. 图C. 队列D. 堆3. 下列哪种数据结构是非线性结构（）。

A. 栈B. 队列C. 数组D. 树4. 栈是一种（）。

A. 先进先出的数据结构B. 先进后出的数据结构C. 后进先出的数据结构D. 后进后出的数据结构5. 在二叉树中，每个节点最多有几个孩子节点（）。

A. 0B. 1C. 2D. 36. 下列哪种排序算法的时间复杂度最好（）。

A. 冒泡排序B. 插入排序C. 快速排序D. 归并排序7. 哈希表的查找时间复杂度是（）。

A. O(1)B. O(logn)C. O(n)D. O(nlogn)8. 链表的插入和删除操作时间复杂度是（）。

A. O(1)B. O(logn)C. O(n)D. O(nlogn)9. 广度优先搜索算法一般使用（）数据结构来实现。

A. 栈B. 队列C. 堆D. 树10. 什么是递归（）。

A. 函数调用自身的过程B. 通过循环完成的过程C. 一种数据结构D. 没有调用其他函数的过程二、填空题（每题2分，共20分）1. 数据结构中，线性表是由一系列 _______________ 元素构成的数据结构。

2. 在树结构中，每个节点可以有 _______________ 个子节点。

3. 在图结构中，节点之间的关系可以用 _______________ 来表示。

4. _______________ 是一种递归定义的数据结构，它由若干个节点组成，每个节点都有零个或多个子节点。

5. 在堆排序中，堆是一种 _______________ 数据结构。

6. _______________ 是一种常用的搜索算法，常用于解决最短路径问题。

7. 在散列表中，使用 _______________ 来解决冲突问题。

2022年郑州大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.402、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)3、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.2341566、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列关于无向连通图特性的叙述中，正确的是（）。

Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。

n个结点的正则二叉树中有（）个叶子。

A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/29、一个具有1025个结点的二叉树的高h为（）。

A.11B.10C.11至1025之间D.10至1024之间10、下面关于B和B+树的叙述中，不正确的是（）A.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索二、填空题11、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。

数据结构考试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构和非线性结构的区别在于（）。

A. 结构中元素的个数B. 结构中元素之间是否有一对一的对应关系C. 结构中元素之间是否有层次关系D. 结构中元素之间是否是线性排列答案：C2. 一个栈的入栈序列为1，2，3，4，5，那么可能的出栈序列为（）。

A. 54321B. 12345C. 34521D. 54123答案：C3. 在二叉树中，度为2的结点数为n，度为1的结点数为m，度为0的结点数为p，则m和p之间的关系是（）。

A. m = n + 1B. p = n + 1C. m = n - 1D. p = n - 1答案：A4. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别在于（）。

A. 是否使用链表B. 是否使用数组C. 是否使用循环探测D. 是否使用二次探测5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是（）。

A. O(n), O(n^2), O(nlogn)B. O(nlogn), O(n^2), O(nlogn)C. O(n), O(nlogn), O(n^2)D. O(n^2), O(nlogn), O(n)答案：B6. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 是否使用栈B. 是否使用队列C. 是否使用递归D. 是否使用图的邻接表表示7. 一个长度为n的有序数组，使用二分查找法查找一个元素的最好、最坏和平均时间复杂度分别是（）。

A. O(1), O(n), O(n)B. O(logn), O(n), O(logn)C. O(n), O(1), O(logn)D. O(1), O(logn), O(n)答案：B8. 在下列排序算法中，时间复杂度为O(n)的是（）。

A. 冒泡排序B. 快速排序C. 归并排序D. 桶排序答案：D9. 一个图的邻接矩阵表示中，若该图是无向图，则矩阵一定是（）。

郑州大学现代远程教育《计算机网络》课程学习指导书林予松编课程内容与基本要求课程内容：计算机网络是计算机专业的一个重要的基础学科，是一门交叉学科，包含计算机应用、数据通信原理等多方面的内容，同时也是交换机与路由器配置、综合布线技术、网络安全和管理等学科的前导课程。

基本要求：通过系统介绍计算机网络的发展，理解计算机体系结构、物理层、数据链路层、网络层、运输层、应用层、网络安全、因特网上的音频/视频服务、无线网络和下一代因特网等内容，使学生掌握计算机网络系统的基本原理、基本技能和基本分析方法。

课程学习进度与指导第一章概述章节学习目标与要求1、了解计算机网络发展的过程以及因特网的标准化工作，掌握计算机网络的相关概念、功能。

2、理解两种通信方式：客户服务器方式（C/S方式）和对等方式（P2P方式）的特点和区别。

3、掌握三种交换方式：电路交换、报文交换和分组交换的原理及特点，并会进行简单计算。

4、了解计算机网络在我国的发展，熟悉计算机网络的类别。

5、熟练掌握计算机网络的性能指标：速率、带宽、吞吐量、时延、时延带宽积、往返时间RTT以及利用率，并会利用公式进行相关计算。

6、理解计算机网络五层协议体系结构参考模型，掌握计算机网络协议的相关概念。

二、本章重点、难点1. 计算机网络的重要作用；2. 客户服务器方式(C/S方式)以及对等方式(P2P方式)的特点与区别；3. 因特网核心部分中的三种交换方式：电路交换、报文交换和分组交换的特点和各自的优缺点；4. 为什么要对网络进行分层；5. TCP/IP五层协议体系中各层的特点及功能；6. 实体、协议、服务和服务访问点等重要概念。

三、章节练习1. 计算机网络向用户可以提供那些服务？2. 简述因特网标准制定的几个阶段。

3. 计算机网络有哪些常用的性能指标？4. 客户服务器方式与对等通信方式的主要区别是什么？有没有相同的地方？5. 试从多个方面比较电路交换、报文交换和分组交换的主要优缺点。

0812数据结构判断题找不到的就选“错误”
已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n,则pi为＿＿＿＿＿＿＿＿。

D. n-i+1
一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。

B. {40，38，46，56，79，84}
对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。

C. O(nlogn)
在进行递归函数调用时，处理参数和返回地址需要使用一种称为＿＿＿＿＿＿＿＿的数据结构。

C. 栈
在待排序的元素序列基本有序时，效率最高的排序方法是（）。

A. 直接插入排序
高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。

B. 12
按照二叉树的定义，具有3个结点的二叉树有＿＿＿＿＿＿＿＿种形态。

C. 5
下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。

D. nlogn+5000n
设有两个串s1和s2，求s2在s1中首次出现的位置的操作是＿＿＿＿＿＿＿＿。

D. 模式匹配
空格串的长度为＿＿＿＿＿＿＿＿。

C. 串中空格的个数
用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。

设m，n是一棵二叉树上的两个结点，中序遍历时，n在m之前的条件是＿＿＿＿＿＿＿＿。

C. 散列地址
在下列排序方法中，在待排序的数据有序时, 花费时间反而最多的是＿＿＿＿＿＿＿。

数据结构》第01章在线测试A BC D为正整数。

确定下面程序段的时间复杂度：1;i＜＝A BC D为正整数。

确定下面程序段的时间复杂度：0; while(iA BC D、下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。

A BC D为正整数，下列程序段的时间复杂度是＿＿＿＿＿＿＿＿。

for(i＝1,xA BC DF、可扩充性2、根据元素之间关系的不同特性，通常可有下列基本结构＿＿＿＿＿＿＿＿。

ABCDA、集合B、线性结构C、树结构D、图结构3、下列说法中，不正确的是＿＿＿＿＿＿＿＿。

ABDA、数据是数据元素的基本单位B、数据元素是数据中不可分割的最小标识单位C、数据元素可由若干个数据项组成D、数据项可由若干个数据元素组成4、数据结构的三要素是指＿＿＿＿＿＿＿＿。

ABCA、数据元素B、逻辑结构C、物理结构D、顺序结构E、链式结构5、数据结构被形式化的定义为(D,S), 其中D、S分别是＿＿＿＿＿＿＿＿的有限集合。

ADA、数据元素B、数据操作C、数据存储D、数据关系第三题、判断题（每题1分，5道题共5分）1、数据元素是数据的不可分割的最小单位。

正确错误、数据的物理结构是指数据和关系在计算机内的实际存储形式。

正确错误、在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。

正确错误、数据对象是一组数据元素的集合。

正确错误、算法是解决某一问题的有限运算序列。

正确错误《数据结构》第02章在线测试A BC D、顺序表中第一个元素的起始存储地址为，则第五个元素的起始地址是＿＿＿＿＿＿＿。

A BC D、单链表是一种＿＿＿＿＿＿＿＿的存储结构。

A BC D、有头结点的单链表（为头指针）是空表的条件是＿＿＿＿＿＿＿A BC D、顺序表是线性表的一种＿＿＿＿＿＿＿的存储结构。

A、顺序存取B、随机存取C、索引存取D、第二题、多项选择题（每题2分，5道题共10分）1、单链表是用一组任意的存储单元来存储线性表的元素，这些存储单元之间＿＿＿＿＿＿＿＿A、可以是连续的B、可以是不连续的C、必须是连续的D、必须是不连续的2、单链表的特点是＿＿＿＿＿＿＿＿。