mooc数据结构与算法_5章节答案(mooc完整答案)

点击查看答案

第二章 线性表

第二章 线性表

1、数据算法01、结构数据在计算机存储器内表示时，章节物理地址与逻辑地址相同并且是答案答案连续的，称之为___。完整
A、数据算法A) 存储结构
B、结构B) 逻辑结构
C、章节C) 顺序存储结构
D、答案答案D) 链式存储结构

2、完整02、数据算法一个向量第一个元素的结构存储地址是100，每个元素的章节长度为2，则第5个元素的答案答案地址是 。
A、完整A) 110
B、B) 108
C、C) 100
D、D) 120

3、03、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是___。
A、A) 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)
B、B) 在第i个结点后插入一个新结点(1≤i≤n)
C、C) 删除第i个结点(1≤i≤n)
D、D) 将n个结点从小到大排序

4、04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 _ 个元素。
A、A) 8
B、B) 63.5
C、C) 63
D、D) 7

5、05、链式存储的存储结构所占存储空间___。
A、A) 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B、B) 只有一部分，存放结点值
C、C) 只有一部分，存储表示结点间关系的指针
D、D) 分两部分，一部分存放结点值，另一部分存放结点所占单元数

6、06、线性表若采用链式存储结构时，要求内存中可用存储单元的地址___。
A、A) 必须是连续的
B、B) 部分地址必须是连续的
C、C) 一定是不连续的
D、D) 连续或不连续都可以

7、07、线性表L在 情况下适用于使用链式结构实现。
A、A) 需经常修改L中的结点值
B、B) 需不断对L进行删除插入
C、C) L中含有大量的结点
D、D) L中结点结构复杂

8、08、在单向链表的指针p所指结点后插入结点*s(*p不是尾结点)，则应执行___操作。
A、A) s->next=p; p->next=s;
B、B) s-next=p->next; p->next=s;
C、C) s-next=p->next; p=s;
D、D) p->next=s; s->next=p;

9、09、下列关于线性表的叙述中，不正确的是___。
A、A) 线性表是n个结点的有穷序列
B、B) 线性表可以为空表
C、C) 线性表的每一个结点有且仅有一个前趋和一个后继
D、D) 线性表结点间的逻辑关系是1:1的联系

10、10、下面程序的功能是___。 void delete(Linklist *L) { p=L; while (p->next!=NULL) { m=p->next->data; q=p; while (q->next!=NULL) { if (q->next->data==m) { r=q->next; q->next=r->next; free(r); } q=q->next; } p=p->next; }
A、A) 在单链表中删除重复结点
B、B) 在单链表中删除第m个结点
C、C) 在单链表中的第m个位置插入结点
D、D) 在单链表中统计结点的数目并保存到m中

11、链表的每个结点中都恰好包含一个指针。

12、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

13、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

14、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

15、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。

16、对任何数据结构链式存储结构一定优于顺序存储结构。

17、取线性表的第i个元素的时间同i的大小有关。

18、循环链表不是线性表。

19、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高

20、链表中的头结点仅起到标识的作用。

中国大学数据结构与算法_5

随着时代的发展，计算机科学和技术越来越受到人们的重视，数据结构与算法作为计算机科学和技术的重要组成部分，对于我们来说更是必不可少的。在中国大学中，数据结构与算法是每一个计算机专业学生都必须掌握的知识之一。在前面的几篇文章中，我们已经深入了解了线性表、栈、队列、树等数据结构的基本概念和应用。在本篇文章中，我们将继续探讨更多的数据结构和算法知识。

哈希表

哈希表是一种基于哈希函数实现的数据结构，它能够在平均情况下以常数时间复杂度进行插入、删除和查找操作。哈希表的思想就是通过哈希函数将数据映射到数组中的某个位置，然后在该位置上进行操作。

哈希表的实现方法有多种，其中最简单的方法就是直接使用数组。我们可以将数据存储在一个固定大小的数组中，并定义一个哈希函数，将数据的关键字转化为数组下标，然后将数据存储在对应的位置上。当两个或多个数据映射到同一个位置上时，我们需要使用冲突解决方法来解决冲突。

哈希表的主要优点是能够提供快速的查找和插入操作，但其缺点是对于存储空间的利用率较低，在处理大规模数据时可能需要较大的存储空间。同时，哈希表的性能也会受到哈希函数的影响，因此选择一种合适的哈希函数非常重要。

堆

堆是一种基于完全二叉树的数据结构，它有两种类型：最大堆和最小堆。在最大堆中，父节点的关键字大于或等于其子节点的关键字；在最小堆中，父节点的关键字小于或等于其子节点的关键字。

堆的主要操作包括插入和删除。在插入操作中，我们需要先将新的元素插入到堆的最后一个位置，然后通过堆的性质将其向上调整，以维护堆的性质。在删除操作中，我们通常会删除堆的根节点，然后将堆的最后一个节点移动到根节点的位置，并通过堆的性质将其向下调整，以维护堆的性质。

堆的主要用途是在优先队列中进行插入和删除操作。优先队列是一种支持插入和弹出操作的队列，其中每个元素都有一个优先级。在优先队列中，元素的弹出顺序是按照其优先级进行排序的。

排序算法

排序算法是数据结构和算法中非常重要的一部分，它们能够将一个无序的数据集合转化为一个有序的数据序列。在计算机科学和技术中，排序算法是非常基础的知识之一，在日常开发中也经常被使用到。

常用的排序算法有多种，其中一些比较常见的包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数组，比较相邻的元素并交换它们的位置，直到遍历完整个数组。其基本思想是通过相邻元素的比较和交换，将较大的元素逐步向数组的右端移动。

选择排序

选择排序是一种简单直观的排序算法，它的主要思想是每次找到未排序部分中的最小元素，将其放置到已排序部分的末尾。

插入排序

插入排序是一种简单直观的排序算法，它的主要思想是将未排序部分中的元素逐个按照大小插入到已排序部分中的合适位置。

快速排序

快速排序是一种常用的排序算法，它使用分治法的思想，将一个数组分成两个较小的子数组，然后递归地对这两个子数组进行排序。其主要思想是通过选定一个基准值，将数组分成两个部分，然后对这两个部分递归地进行快速排序，最终得到有序的数组。

归并排序

归并排序是一种基于分治法的排序算法，它的主要思想是将一个数组分成两个较小的子数组，然后递归地对这两个子数组进行排序，最终将它们合并成一个有序的数组。

总结

数据结构和算法是计算机科学和技术的重要组成部分，对于每一个计算机专业的学生来说，掌握数据结构和算法知识是非常重要的。在本篇文章中，我们探讨了哈希表、堆和排序算法等重要的数据结构和算法知识，希望这些知识对大家有所帮助。

在学习数据结构和算法时，重点是理解其基本原理和应用场景，而不是死记硬背。只有通过实践和应用，才能真正掌握这些知识并将其应用到实际开发中。