当前位置: 首页 > news >正文

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

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

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

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

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

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

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

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

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

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. 试分析下列各个算法的时间复杂度

  • 在这里插入图片描述
    • 在这里插入图片描述
  • 在这里插入图片描述
    • 在这里插入图片描述
  • 在这里插入图片描述
    • 在这里插入图片描述
  • 在这里插入图片描述
    • 在这里插入图片描述
  • 在这里插入图片描述
    • 在这里插入图片描述
  • 在这里插入图片描述
    • 在这里插入图片描述

相关文章:

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

1. 简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 数据 数据是客观事物的符号表示,是所有能输人到计算机中并被计算机程序处理的符号的总称。数据是信息的载体,能够被计算机识别、存储和加工 数据元素…...

JS_countup.js 的简单使用,数字滚动效果

countup.js countup.js 是一个轻量级,无依赖的JavaScript类,通过简单的设置就可以达到数字滚动的效果 官网:https://inorganik.github.io/countUp.js/ 源码 var CountUpfunction(target,startVal,endVal,decimals,duration,options){var …...

【C++知识点】STL 容器总结

✍个人博客:https://blog.csdn.net/Newin2020?spm1011.2415.3001.5343 📚专栏地址:C/C知识点 📣专栏定位:整理一下 C 相关的知识点,供大家学习参考~ ❤️如果有收获的话,欢迎点赞👍…...

C++---背包模型---装箱问题(每日一道算法2023.3.9)

注意事项: 本题是"动态规划—01背包"的扩展题,dp和优化思路不多赘述。 题目: 有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。 要求 n 个物品中,任取若…...

if-else if与switch的练习1:输入两个数,输出两个数的加减乘除的值

1.if-else if的练习 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" content"widthdevice…...

【教程】你现在还不知道微软的New Bing?你out了,快点进来看

哈喽啊&#xff0c;大家好&#xff0c;好久不见&#xff0c;我是木易巷&#xff01; 不禁感叹&#xff0c;AI人工智能时代真的已经来临&#xff01; 目前&#xff0c;谷歌和微软就各自面向大众的产品发布了重大公告。谷歌推出了一款名为Bard实验性对话式 AI 服务&#xff0c;而…...

https流程

ssl加密协议包含以下4个步骤 1、服务器去第三方机构注册生成证书&#xff0c;第三方机构非对称加密生成公钥私钥&#xff0c;给服务器一个私钥&#xff0c;证书包含了公钥。 2、客户端向服务器索要证书 3、客户端向第三方机构验证证书 4、客户端对称加密生成密钥&#xff0c;在…...

python魔法方法

Python中的魔法方法&#xff08;也称为特殊方法或双下划线方法&#xff09;是在类定义中使用的一些特殊的函数,可以使用dir方法查询。它们以双下划线开头和结尾&#xff0c;例如__init__和__str__。这些方法被Python解释器用于执行特定的操作&#xff0c;例如实例化对象、字符串…...

软件测试员如何进行产品测试?

一般来讲&#xff0c;当软件成为一个成功的产品后&#xff0c;产品测试工作就会复杂很多。比如拥有的用户量大&#xff0c;迭代频繁&#xff0c;测试的周期短&#xff0c;重复性强。面对紧张复杂的产品测试工作&#xff0c;软件测试员应怎样完成这一系列的测试工作呢&#xff1…...

计算机网络基础知识点【1】

文章目录计算机网络第一章 计算机网络参考模型1.计算机网络为什么需要分层&#xff1f;1.1 分层思想1.2 分层好处2.OSI七层模型2.1 OSI七层模型总结2.2 OSI七层工作原理2.3 数据封装与解封装2.4 计算机网络常用协议3.TCP/IP参考模型3.1 什么是TCP/IP协议3.2 TCP/IP协议族的组成…...

c++ 中标准库类型 string 详解

&#x1f441;‍&#x1f5e8;&#x1f441;‍&#x1f5e8; 前言 标准库类型string 表示可变长的字符序列&#xff0c;使用string 类型必须首先包含string 头文件。string 定义在命名空间std 中。 定义和初始化 string 对象 首先说明如何初始化对象是由类本身决定的&#xff0…...

Html新增属性之拖拽(drag)

元素在拖放过程中触发的事件 HTML5中&#xff0c;只要将元素的 draggable 属性设置为 true 就可以实现拖放功能&#xff0c;在拖放过程中&#xff0c;触发了多个事件&#xff0c;如下&#xff1a; dragstart:事件主体是被拖放元素&#xff0c;在开始拖放被拖放元素时触发。dra…...

C/C++开发,无可避免的多线程(篇二).thread与其支持库

一、原子类型与原子操作 1.1 原子类型与操作介绍 在前一篇博文中&#xff0c;多线程交互示例代码中&#xff0c;给出了一个原子类型定义&#xff1a; // 原子数据类型 atomic_llong total {0}; 那么什么事原子数据类型呢&#xff0c;和c的基础数据类型有什么不同呢&#xff1a…...

mysql数据库之表级锁

表级锁&#xff0c;每次操作锁住整张表。锁定粒度大&#xff0c;发生所冲突的概率最高&#xff0c;并发度最低。应用在myisam、innodb、bdb等存储引擎中。 一、表级锁分类。 1、表锁 2、元数据锁&#xff08;meta data lock&#xff0c;MDL&#xff09; 3、意向锁 二、表锁…...

Python - Pandas - 数据分析(2)

Pandas数据分析2前言常用的21种统计方法describe()&#xff1a;numeric_only&#xff1a;偏度skewness&#xff1a;功能&#xff1a;含义&#xff1a;计算公式&#xff1a;演示&#xff1a;峰度值&#xff1a;用途&#xff1a;数值&#xff1a;计算公式&#xff1a;演示&#x…...

我的十年编程路 2019年篇

随着2018年&#xff0c;三星天津研究院的裁撤&#xff0c;我选择了到广州的三星研究院工作&#xff0c;与最心爱的她开始一起生活。 这一年的开始&#xff0c;我注册了博客园。和2014年类似&#xff0c;在刚注册不久&#xff0c;我写了一篇题为《全新开始&#xff0c;全心出发…...

(蓝桥真题)剪格子(搜索+剪枝)

样例1输入&#xff1a; 3 3 10 1 52 20 30 1 1 2 3 样例1输出&#xff1a; 3 样例2输入&#xff1a; 4 3 1 1 1 1 1 30 80 2 1 1 1 100 样例2输出&#xff1a; 10 分析&#xff1a;这道题目我们直接从(1,1)点开始进行dfs搜索即可&#xff0c;但是需要注意一点的是我们搜…...

Kalman Filter in SLAM (3) ——Extended Kalman Filter (EKF, 扩展卡尔曼滤波)

文章目录1. 线性系统的 Kalman Filter 回顾2. Extended Kalman Filter 之 DR_CAN讲解笔记2.1. 非线性系统2.2. 非线性系统线性化2.2.1. 状态方程f(xk)f(x_k)f(xk​)在上一次的最优估计状态x^k−1\hat{x}_{k-1}x^k−1​处线性化2.2.2. 观测方程h(xk)h(x_k)h(xk​)在这一次的预测…...

关于vertical-align的几问

vertical-align属性可以给我讲解一下吗&#xff1f; 当使用table-cell布局或inline元素时&#xff0c;可以使用CSS的vertical-align属性控制元素的垂直对齐方式。该属性可应用于元素本身以及其父元素&#xff08;例如&#xff0c;td、th、tr和table&#xff09;。 以下是vertic…...

【拜占庭将军问题】这一计谋,可以让诸葛丞相兴复汉室

我们都知道&#xff0c;诸葛亮第一次北伐是最可能成功的&#xff0c;魏国没有防备&#xff0c;还策反了陇西&#xff0c;陇西有大量的马匹可以装备蜀国骑兵&#xff0c;可惜街亭一丢&#xff0c;那边就守不住了 当时我不在&#xff0c;只能作诗一首~ 如果穿越过去&#xff0c;…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

C# SqlSugar:依赖注入与仓储模式实践

C# SqlSugar&#xff1a;依赖注入与仓储模式实践 在 C# 的应用开发中&#xff0c;数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护&#xff0c;许多开发者会选择成熟的 ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;SqlSugar 就是其中备受…...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

提升移动端网页调试效率:WebDebugX 与常见工具组合实践

在日常移动端开发中&#xff0c;网页调试始终是一个高频但又极具挑战的环节。尤其在面对 iOS 与 Android 的混合技术栈、各种设备差异化行为时&#xff0c;开发者迫切需要一套高效、可靠且跨平台的调试方案。过去&#xff0c;我们或多或少使用过 Chrome DevTools、Remote Debug…...