[数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)

简介: [数据结构与算法(严蔚敏 C语言第二版)]第1章 绪论(课后习题+答案解析)

1. 简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

  • 数据
  • 数据是客观事物的符号表示,是所有能输人到计算机中并被计算机程序处理的符号的总称。数据是信息的载体,能够被计算机识别、存储和加工
  • 数据元素
  • 是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
  • 数据项
  • 是组成数据元素的、有独立含义的、不可分割的最小单位。
  • 数据对象
  • 是性质相同的数据元素的集合,是数据的一个子集。
  • 数据结构
  • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带“结构”的数据元素的集合,“结构”是指数据元素之间存在的关系。
  • 逻辑结构
  • 数据元素之间的逻辑关系,数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的,是从具体问题抽象出来的数学模型
  • 存储结构
  • 数据元素及其关系在计算机内存中的表示(又称映像、存储方式),数据对象在计算机中的存储表示称为数据的存储结构,也称为物理结构。存储结构既要存储各数据元素的数据,又要存储数据元素之间的逻辑关系
  • 抽象数据类型
  • 抽象数据类型是指一个数学模型以及定义在此数学模型上得一组操作的总称,不考虑计算机内的具体存储结构和运算的具体实现算法

2. 试举一个数据结构的例子,叙述其逻辑结构和存储结构两个层次的含义及相互关系。

  • 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。
  • 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。
  • 即相同的逻辑结构,可以对应不同的存储结构。

3. 简述逻辑结构的四种基本关系并画出它们的关系图。

  • 集合结构:数据元素之间除了“属于同一个集合”的关系外,别无其他关系
  • 线性结构:数据元素之间存在一对一的关系
  • 树结构:数据元素之间存在一对多的关系
  • 图结构或网状结构:数据元素之间存在多对多的关系

4. 存储结构由哪两种基本的存储方法实现?

  1. 顺序存储结构
  • 顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系,通常借助程序设计语言的数组类型来描述
  • 顺序存储结构要求所有的元素依次存放在一片连续的存储空间中
  1. 链式存储结构
  • 用一组任意的存储单元存储数据元素,数据元素之间的逻辑关系使用指针来表示
  • 链式存储结构通常借助于程序设计语言的指针类型来描述

5. 选择题

  • (1)在数据结构中,从逻辑上可以把数据结构分成()。
  • A.动态结构和静态结构
  • B.紧凑结构和非紧凑结构
  • C.线性结构和非线性结构
  • D.内部结构和外部结构
  • 答案:C
  • 解析:
  • 在数据结构中,从逻辑上可以把数据结构分成线性结构和非线性结构
  • 图、树、集合等结构为非线性结构
  • (2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()
  • A.存储结构
  • B.存储实现
  • C.逻辑结构
  • D.运算实现
  • 答案:C
  • 解析:
  • 逻辑结构表示的是数据元素之间的逻辑关系,数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的,是从具体问题抽象出来的数学模型
  • 运算实现与数据元素的形式、内容和个数有关,数据元素形式、内容和个数不同运算实现可能有所不同
  • 存储结构和存储实现是数据元素在计算机内存中的表示和实现,与数据元素本身的形式、内容、相对位置、个数相关
  • (3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着().
  • A. 数据具有同一特点
  • B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致
  • C.每个数据元素都一样
  • D.数据元素所包含的数据项的个数要相等
  • 答案:C
  • 解析
  • 同一逻辑结构中的所有数据元素具有相同的特性,每个数据元素的数据项的个数相同且类型一致。数据元素数据项的内容可不同
  • (4)以下说法正确的是()。
  • A.数据元素是数据的最小单位
  • B.数据项是数据的基本单位
  • C.数据结构是带有结构的各数据项的集合
  • D.一些表面上很不相同的数据可以有相同的逻辑结构
  • 答案:D
  • 解析:
  • 数据项是组成数据元素的、有独立含义的、不可分割的最小单位。
  • 数据的基本单位是数据元素
  • 数据结构为数据元素及数据元素之间关系的集合
  • (5)算法的时间复杂度取决于()。
  • A.问题的规模
  • B.待处理数据的初态
  • C.计算机的配置
  • D.A和 B
  • 答案:D
  • 解析:
  • 算法的时间复杂度取决于问题的规模和待处理数据的初态,问题的规模越大时间复杂度越大,数据的初态不同算法所需的时间不同
  • (6)以下数据结构中,()是非线性数据结构。
  • A.树
  • B.字符串
  • C.队列
  • D.栈
  • 答案:A
  • 解析:
  • 字符串、队列、栈均为线性表中的一种,树结构为非线性结构

6. 试分析下列各个算法的时间复杂度

相关文章
|
5月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
290 77
|
5月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
5月前
|
存储 C语言
【C语言程序设计——函数】递归求斐波那契数列的前n项(头歌实践教学平台习题)【合集】
本关任务是编写递归函数求斐波那契数列的前n项。主要内容包括: 1. **递归的概念**:递归是一种函数直接或间接调用自身的编程技巧,通过“俄罗斯套娃”的方式解决问题。 2. **边界条件的确定**:边界条件是递归停止的条件,确保递归不会无限进行。例如,计算阶乘时,当n为0或1时返回1。 3. **循环控制与跳转语句**:介绍`for`、`while`循环及`break`、`continue`语句的使用方法。 编程要求是在右侧编辑器Begin--End之间补充代码,测试输入分别为3和5,预期输出为斐波那契数列的前几项。通关代码已给出,需确保正确实现递归逻辑并处理好边界条件,以避免栈溢出或结果
287 16
|
5月前
|
算法 C语言
【C语言程序设计——循环程序设计】求解最大公约数(头歌实践教学平台习题)【合集】
采用欧几里得算法(EuclideanAlgorithm)求解两个正整数的最大公约数。的最大公约数,然后检查最大公约数是否大于1。如果是,就返回1,表示。根据提示,在右侧编辑器Begin--End之间的区域内补充必要的代码。作为新的参数传递进去。这个递归过程会不断进行,直到。有除1以外的公约数;变为0,此时就找到了最大公约数。开始你的任务吧,祝你成功!是否为0,如果是,那么。就是最大公约数,直接返回。
170 18
|
5月前
|
Serverless C语言
【C语言程序设计——循环程序设计】利用循环求数值 x 的平方根(头歌实践教学平台习题)【合集】
根据提示在右侧编辑器Begin--End之间的区域内补充必要的代码,求解出数值x的平方根;运用迭代公式,编写一个循环程序,求解出数值x的平方根。注意:不能直接用平方根公式/函数求解本题!开始你的任务吧,祝你成功!​ 相关知识 求平方根的迭代公式 绝对值函数fabs() 循环语句 一、求平方根的迭代公式 1.原理 在C语言中,求一个数的平方根可以使用牛顿迭代法。对于方程(为要求平方根的数),设是的第n次近似值,牛顿迭代公式为。 其基本思想是从一个初始近似值开始,通过不断迭代这个公式,使得越来越接近。
126 18
|
5月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
99 15
|
5月前
|
C语言
【C语言程序设计——循环程序设计】统计海军鸣放礼炮声数量(头歌实践教学平台习题)【合集】
有A、B、C三艘军舰同时开始鸣放礼炮各21响。已知A舰每隔5秒1次,B舰每隔6秒放1次,C舰每隔7秒放1次。编程计算观众总共听到几次礼炮声。根据提示,在右侧编辑器Begin--End之间的区域内补充必要的代码。开始你的任务吧,祝你成功!
130 13
|
5月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
136 10
|
5月前
|
存储 编译器 C语言
【C语言程序设计——函数】分数数列求和2(头歌实践教学平台习题)【合集】
函数首部:按照 C 语言语法,函数的定义首部表明这是一个自定义函数,函数名为fun,它接收一个整型参数n,用于指定要求阶乘的那个数,并且函数的返回值类型为float(在实际中如果阶乘结果数值较大,用float可能会有精度损失,也可以考虑使用double等更合适的数据类型,这里以float为例)。例如:// 函数体代码将放在这里函数体内部变量定义:在函数体中,首先需要定义一些变量来辅助完成阶乘的计算。比如需要定义一个变量(通常为float或double类型,这里假设用float。
144 3
|
5月前
|
存储 算法 安全
【C语言程序设计——函数】分数数列求和1(头歌实践教学平台习题)【合集】
if 语句是最基础的形式,当条件为真时执行其内部的语句块;switch 语句则适用于针对一个表达式的多个固定值进行判断,根据表达式的值与各个 case 后的常量值匹配情况,执行相应 case 分支下的语句,直到遇到 break 语句跳出 switch 结构,若没有匹配值则执行 default 分支(可选)。例如,在判断一个数是否大于 10 的场景中,条件表达式为 “num> 10”,这里的 “num” 是程序中的变量,通过比较其值与 10 的大小关系来确定条件的真假。常量的值必须是唯一的,且在同一个。
136 2