mooc数据结构_52期末答案(mooc完整答案)
77 min readmooc数据结构_52期末答案(mooc完整答案)
1.2 什么是数据算法（3节共22:41）随堂测验
1、下列函数中，结构哪个函数具有最快的期末增长速度：
A、
B、答案答案
C、完整
D、数据
2、结构下面一段代码的期末时间复杂度是？if ( A > B ) { for ( i=0; i<N; i++ ) for ( j=N*N; j>i; j-- ) A += B; } else { for ( i=0; i<N*2; i++ ) for ( j=N*2; j>i; j-- ) A += B; }
A、
B、答案答案
C、完整
D、数据
第二讲 线性结构（2:19:00）[何钦铭]
2.1 线性表及其实现(6小节共45:04)随堂测验
1、结构对于线性表，期末在顺序存储结构和链式存储结构中查找第k个元素，答案答案其时间复杂性分别是完整多少？
A、都是O(1)
B、都是O(k)
C、O(1)和O(k)
D、O(k)和O(1)
2、在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是： for (___________ ) PtrL->Data[j-1]=PtrL->Data[j]; 其中空缺部分的内容应该是
A、j = i; j< = PtrL->Last; j++
B、j =PtrL->Last; j>= i; j--
C、j = i-1; j< = PtrL->Last; j++
D、j =PtrL->Last; j>= i-1; j--
3、下列函数试图求链式存储的线性表的表长，是否正确？ int Length ( List *PtrL ) { List *p = PtrL; int j = 0; while ( p ) { p++; j++; } return j; }
2.2 堆栈(4小节共39:51)随堂测验
1、借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：
A、2
B、3
C、4
D、5
2、设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：
A、3
B、n-2
C、n-3
D、任何元素均可能
3、若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？ （1）4->2->3 (2) 1->2->4
A、只能是（1）
B、只能是（2）
C、（1）和（2）都有可能
D、（1）和（2）都不可能
4、如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。
A、PPPOOPOPOO
B、POOPPPOPOO
C、POPPOPPOOO
D、PPOPPOOOPO
2.3 队列(2小节共15:45)随堂测验
1、在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：
A、f->next=s; f=s;
B、r->next=s; r=s;
C、s->next=r; r=s;
D、s->next=f; f=s;
2、现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？
A、4
B、5
C、6
D、7
学习通数据结构_52
数据结构是计算机科学中的一门基础学科，它研究的是数据在计算机中的存储、组织和管理方式。数据结构的研究涉及到各种各样的算法和数据类型，例如数组、链表、堆栈、队列、树、图等等，这些数据类型和算法可以高效地处理大量的数据，让计算机能够更加智能地运行。
数据结构的基本概念
在学习数据结构的过程中，我们需要掌握一些基本的概念，例如数据元素、数据对象、数据结构、存储结构和算法等等。
- 数据元素：是数据的基本单位，它可以是一个字符、一个数字或者一个对象。
- 数据对象：是具有相同性质的数据元素的集合，例如一个班级中所有学生的信息。
- 数据结构：是指数据对象及其之间的关系，它是数据元素在计算机中的组织形式。
- 存储结构：是指数据结构在计算机内存中的表示形式，例如数组、链表等等。
- 算法：是指解决某个问题的具体步骤，它是通过对数据结构进行操作而得到的结果。
常用的数据结构
在实际的开发过程中，我们会经常用到一些常用的数据结构，例如数组、链表、堆栈、队列、树、图等等。
数组
数组是一种线性数据结构，它由一组连续的内存空间组成，每个元素都可以通过下标来访问。
<code>int arr[10];for (int i = 0; i < 10; i++) { arr[i] = i;}for (int i = 0; i < 10; i++) { cout << arr[i] << \ \}</code>链表
链表是一种非线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
<code>struct Node { int data; Node* next;};Node* head = nullptr;for (int i = 0; i < 10; i++) { Node* node = new Node(); node->data = i; node->next = head; head = node;}Node* cur = head;while (cur) { cout << cur->data << \ \ cur = cur->next;}</code>堆栈
堆栈是一种后进先出（LIFO）的数据结构，它只能在一端进行插入和删除操作。
<code>stack<int> s;for (int i = 0; i < 10; i++) { s.push(i);}while (!s.empty()) { cout << s.top() << \ \ s.pop();}</code>队列
队列是一种先进先出（FIFO）的数据结构，它支持在队尾插入元素，在队头删除元素。
<code>queue<int> q;for (int i = 0; i < 10; i++) { q.push(i);}while (!q.empty()) { cout << q.front() << \ \ q.pop();}</code>树
树是一种非线性数据结构，它由一组节点和一组边组成，每个节点可以有多个子节点。
<code>struct TreeNode { int val; TreeNode* left; TreeNode* right;};TreeNode* buildTree(vector<int>& nums, int l, int r) { if (l > r) { return nullptr; } int mid = (l + r) / 2; TreeNode* root = new TreeNode(); root->val = nums[mid]; root->left = buildTree(nums, l, mid - 1); root->right = buildTree(nums, mid + 1, r); return root;}vector<int> nums = { 1, 2, 3, 4, 5};TreeNode* root = buildTree(nums, 0, nums.size() - 1);</code>图
图是一种复杂的非线性数据结构，它由一组节点和一组边组成，每个节点可以有多个相邻节点。
<code>struct Graph { int n; vector<vector<int>> adj; Graph(int n) { this->n = n; adj.resize(n); } void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); }};Graph g(5);g.addEdge(0, 1);g.addEdge(1, 2);g.addEdge(2, 3);g.addEdge(3, 4);</code>数据结构的应用
数据结构是计算机科学中的重要基础学科，它在实际的软件开发中有着广泛的应用。
搜索和排序算法
搜索和排序是计算机科学中最基本的问题之一，它们的解决方法都离不开数据结构。
二分查找
二分查找是一种高效的搜索算法，它利用了有序数组的特性，可以快速地找到一个元素。
<code>int binarySearch(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return -1;}vector<int> nums = { 1, 2, 3, 4, 5};int index = binarySearch(nums, 3);</code>快速排序
快速排序是一种高效的排序算法，它利用了分治思想，可以将一个数组快速地排序。
<code>void quickSort(vector<int>& nums, int l, int r) { if (l >= r) { return; } int i = l, j = r, pivot = nums[(l + r) / 2]; while (i <= j) { while (nums[i] < pivot) { i++; } while (nums[j] > pivot) { j--; } if (i <= j) { swap(nums[i], nums[j]); i++; j--; } } quickSort(nums, l, j); quickSort(nums, i, r);}vector<int> nums = { 3, 2, 1, 4, 5};quickSort(nums, 0, nums.size() - 1);</code>数据处理和计算机图形学
在数据处理和计算机图形学中，也会用到很多数据结构，例如哈希表、树状数组、线段树、二叉堆和并查集等等。
哈希表
哈希表是一种高效的数据结构，它可以快速地将一个键映射到一个值。
<code>unordered_map<string, int> umap;umap[\apple\ = 1;umap[\banana\ = 2;umap[\orange\ = 3;int value = umap[\banana\</code>线段树
线段树是一种高效的数据结构，它可以快速地查询一个区间的值，并且支持修改操作。
<code>const int MAXN = 100005;int a[MAXN], s[MAXN * 4];void build(int i, int l, int r) { if (l == r) { s[i] = a[l]; } else { int mid = (l + r) / 2; build(i * 2, l, mid); build(i * 2 + 1, mid + 1, r); s[i] = s[i * 2] + s[i * 2 + 1]; }}int query(int i, int l, int r, int x, int y) { if (x <= l && r <= y) { return s[i]; } else { int mid = (l + r) / 2, res = 0; if (x <= mid) { res += query(i * 2, l, mid, x, y); } if (y > mid) { res += query(i * 2 + 1, mid + 1, r, x, y); } return res; }}</code>并查集
并查集是一种高效的数据结构，它用于维护一些不相交的集合，并支持合并和查询操作。
<code>const int MAXN = 100005;int p[MAXN];void init(int n) { for (int i = 0; i < n; i++) { p[i] = i; }}int find(int x) { if (p[x] != x) { p[x] = find(p[x]); } return p[x];}void merge(int x, int y) { p[find(x)] = find(y);}bool same(int x, int y) { return find(x) == find(y);}</code>总结
数据结构是计算机科学中的一门基础学科，它研究的是数据在计算机中的存储、组织和管理方式。数据结构的研究涉及到各种各样的算法和数据类型，例如数组、链表、堆栈、队列、树、图等等，这些数据类型和算法可以高效地处理大量的数据，让计算机能够更加智能地运行。
在实际的开发过程中，我们会经常用到一些常用的数据结构，例如数组、链表、堆栈、队列、树、图等等。同时，数据结构也被广泛地应用于搜索和排序算法、数据处理和计算机图形学等领域。
因此，掌握数据结构是每一个程序员必须要掌握的基本技能之一，它可以让我们更好地理解计算机科学的基础知识，并且更加高效地解决实际问题。
中国大学数据结构_52
数据结构是计算机科学中非常重要的一个领域，是计算机科学必修的一门课程，也是许多专业方向的基础知识。
数据结构的定义
数据结构是指数据对象以及数据对象中各个元素之间的关系，二者统称为数据结构。
数据结构的分类
数据结构可以分为线性结构和非线性结构两大类。
线性结构
线性结构是指数据元素之间存在一对一的关系，即每个数据元素只有一个直接前驱和直接后继。常见的线性结构有线性表、栈、队列等。
线性表
线性表是一种线性结构，它是由同类型数据元素组成的有限序列。
顺序存储结构
顺序存储结构是指用一段地址连续的存储单元存储线性表中的元素，线性表中的元素在物理上也是相邻的。
链式存储结构
链式存储结构是指用一组任意的存储单元存储线性表中的元素，线性表中的元素在物理上可以不相邻，但是逻辑上仍然是相邻的。
栈
栈是一种特殊的线性表，它是只能在表尾进行插入和删除操作的线性表。栈的特点是后进先出，即最后插入的元素最先被删除。
顺序存储结构
顺序存储结构的栈称为顺序栈，它是用一段地址连续的存储单元存储栈中的元素。
链式存储结构
链式存储结构的栈称为链式栈，它是用一组任意的存储单元存储栈中的元素。
队列
队列是一种特殊的线性表，它是只能在表头进行删除操作，在表尾进行插入操作的线性表。队列的特点是先进先出，即最先插入的元素最先被删除。
顺序存储结构
顺序存储结构的队列称为顺序队列，它是用一段地址连续的存储单元存储队列中的元素。
链式存储结构
链式存储结构的队列称为链式队列，它是用一组任意的存储单元存储队列中的元素。
非线性结构
非线性结构是指数据元素之间存在多对多的关系，即每个数据元素可能有多个直接前驱或直接后继。常见的非线性结构有树、图等。
树
树是一种非线性结构，它是由n（n>=1）个结点组成的有限集合。当n=1时，该树被称为单节点树。当n>1时，树由一个根结点和n-1个子树构成，每个子树又是一棵树。树的结点包含数据元素和若干指向其子结点的指针。
二叉树
二叉树是一种特殊的树，它的每个结点最多只有两个子结点，分别称为左子结点和右子结点。二叉树具有以下性质：
- 每个结点最多有两个子结点
- 左子结点的值小于其父结点的值
- 右子结点的值大于其父结点的值
线索化二叉树
线索化二叉树是在二叉树的基础上，将二叉树中的空指针指向该结点在某种遍历序列下的前驱或后继结点，形成一个有指向的线性结构，从而方便遍历二叉树。线索化二叉树分为前序线索二叉树、中序线索二叉树和后序线索二叉树。
图
图是一种非线性结构，它是由顶点集合和边集合组成的有限集合。
有向图
有向图是指图中的边是有方向的，从一个顶点到另一个顶点的边有起点和终点之分。
无向图
无向图是指图中的边是无方向的，从一个顶点到另一个顶点的边没有起点和终点之分。
数据结构的应用
数据结构是计算机科学中应用最广泛的一门课程之一，它在许多领域都有着广泛的应用。
算法设计与分析
算法是指解决特定问题的步骤序列。数据结构是算法设计和分析的基础，不同的数据结构适合不同的算法。
数据库
数据库是指存储、管理和检索数据的软件系统。数据结构在数据库中的应用包括索引、散列表、排序等。
操作系统
操作系统是计算机系统中与硬件和应用系统之间的接口，它需要管理系统资源，包括内存、进程等。数据结构在操作系统中的应用包括文件系统、内存管理、调度器等。
人工智能
人工智能是计算机科学中的一个重要分支，它需要处理复杂的逻辑关系。数据结构在人工智能中的应用包括搜索、图论、机器学习等。
结语
数据结构是计算机科学中的一门重要课程，掌握好数据结构对于学习和工作都有着很大的帮助。希望本文对您有所帮助。
