[数据结构与算法(严蔚敏 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. 试分析下列各个算法的时间复杂度

相关文章
|
11月前
|
存储 C语言 C++
【c语言】运算符汇总(万字解析)
今天博主跟大家分享了c语言中各种操作符的功能、使用方法以及优先级和结合性,并且与大家深入探讨了表达式求值的两个重要规则--算数转换和整形提升。学习这些知识对我们的C语言和C++学习都有着极大的帮助。
556 2
|
11月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
326 4
|
9月前
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
10月前
|
存储 网络协议 编译器
【C语言】深入解析C语言结构体:定义、声明与高级应用实践
通过根据需求合理选择结构体定义和声明的放置位置,并灵活结合动态内存分配、内存优化和数据结构设计,可以显著提高代码的可维护性和运行效率。在实际开发中,建议遵循以下原则: - **模块化设计**:尽可能封装实现细节,减少模块间的耦合。 - **内存管理**:明确动态分配与释放的责任,防止资源泄漏。 - **优化顺序**:合理排列结构体成员以减少内存占用。
721 14
|
10月前
|
存储 编译器 C语言
【C语言】数据类型全解析:编程效率提升的秘诀
在C语言中,合理选择和使用数据类型是编程的关键。通过深入理解基本数据类型和派生数据类型,掌握类型限定符和扩展技巧,可以编写出高效、稳定、可维护的代码。无论是在普通应用还是嵌入式系统中,数据类型的合理使用都能显著提升程序的性能和可靠性。
427 8
|
10月前
|
存储 算法 C语言
【C语言】深入浅出:C语言链表的全面解析
链表是一种重要的基础数据结构,适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现,以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
2955 6
|
10月前
|
存储 网络协议 算法
【C语言】进制转换无难事:二进制、十进制、八进制与十六进制的全解析与实例
进制转换是计算机编程中常见的操作。在C语言中,了解如何在不同进制之间转换数据对于处理和显示数据非常重要。本文将详细介绍如何在二进制、十进制、八进制和十六进制之间进行转换。
959 5
|
10月前
|
C语言 开发者
【C语言】断言函数 -《深入解析C语言调试利器 !》
断言(assert)是一种调试工具,用于在程序运行时检查某些条件是否成立。如果条件不成立,断言会触发错误,并通常会终止程序的执行。断言有助于在开发和测试阶段捕捉逻辑错误。
203 5
|
10月前
|
安全 搜索推荐 Unix
【C语言】《回调函数》详细解析
回调函数是指一个通过函数指针调用的函数。它允许将一个函数作为参数传递给另一个函数,并在特定事件发生时执行。这种技术使得编程更加灵活,可以动态决定在何时调用哪个函数。
571 1
|
11月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
277 1

热门文章

最新文章

推荐镜像

更多
  • DNS