长沙有家具网站建设的吗,免费wordpress 主题,织梦搭建商城网站,掌门一对一辅导官网大数据分析应用-初级
第一部分 基础知识 一、大数据法律法规、政策文件、相关标准 二、计算机基础知识 三、信息化基础知识 四、密码学 五、大数据安全 六、数据库系统 七、数据仓库.
第二部分 专业知识 一、大数据技术与应用 二、大数据分析模型 三、数据科学 大数据相关标准… 大数据分析应用-初级
第一部分 基础知识 一、大数据法律法规、政策文件、相关标准 二、计算机基础知识 三、信息化基础知识 四、密码学 五、大数据安全 六、数据库系统 七、数据仓库.
第二部分 专业知识 一、大数据技术与应用 二、大数据分析模型 三、数据科学 大数据相关标准
大数据分析应用-初级前言一、线性表的概念二、堆栈、队列、跳表和散列的描述方法与应用练习题目 前言
数据结构与算法
2、掌握线性表的概念掌握堆栈、队列、跳表和散列的描述方法与应用。 一、线性表的概念 概念 线性表是由 nn≥0个相同类型的数据元素组成的有限序列。它是一种最基本、最简单的数据结构数据元素之间存在着一对一的线性关系。当 n 0 时线性表为空表。 描述方法 顺序存储结构顺序表用一组连续的存储单元依次存储线性表中的各个元素可以通过数组来实现。例如在 C 语言中可以定义如下结构体来表示顺序表 #define MAXSIZE 100 // 定义最大长度
typedef struct {int data[MAXSIZE]; // 存储元素的数组int length; // 线性表当前长度
} SqList; 链式存储结构链表通过节点来存储元素每个节点包含数据域和指针域指针域指向下一个节点节点之间通过指针链接形成线性表。以单链表为例C 语言代码如下 typedef struct LNode {int data; // 数据域struct LNode *next; // 指针域指向下一个节点
} LNode, *LinkList; 顺序表应用比如学生成绩管理系统将每个学生的成绩依次存储在顺序表中方便按照学号等顺序进行查找、修改成绩等操作。链表应用在操作系统中进程调度队列可以用链表来实现每个节点代表一个进程便于动态地插入新进程和移除已完成的进程。 二、堆栈、队列、跳表和散列的描述方法与应用 堆栈 概念 堆栈Stack是一种只能在一端进行插入和删除操作的特殊线性表允许操作的一端称为栈顶另一端称为栈底。遵循后进先出LIFOLast In First Out的原则。 描述方法 顺序栈同样基于数组实现利用一个指针通常称为栈顶指针来指示栈顶元素的位置。以下是简单的 C 语言顺序栈结构体定义 #define MAXSIZE 50 // 栈的最大容量
typedef struct {int data[MAXSIZE];int top; // 栈顶指针初始化为 -1
} SqStack;链栈采用链表结构栈顶作为链表的表头入栈和出栈操作都在表头进行。用 C 语言表示链栈节点的结构体如下 typedef struct StackNode {int data;struct StackNode *next;
} StackNode, *LinkStack;应用 函数调用栈在程序运行时当一个函数调用另一个函数时会将当前函数的执行上下文如局部变量、返回地址等压入栈中被调用函数执行完毕后再从栈顶弹出相应的执行上下文恢复到原函数继续执行实现了函数调用的嵌套管理。表达式求值例如对算术表达式 “3 4 * 2” 求值时可以利用栈来辅助实现运算符和操作数的处理根据运算符优先级将操作数和运算符依次入栈、出栈进行计算。 队列 概念 队列Queue也是一种特殊的线性表它只允许在一端进行插入操作队尾在另一端进行删除操作队头遵循先进先出FIFOFirst In First Out的原则。 描述方法 顺序队列使用数组来存储队列元素通过两个指针分别指示队头和队尾的位置。不过顺序队列存在假溢出问题实际应用中常采用循环队列来解决。循环队列的 C 语言结构体示例如下 #define MAXSIZE 100 // 队列最大容量
typedef struct {int data[MAXSIZE];int front; // 队头指针int rear; // 队尾指针
} SqQueue;链队列由一个带头节点的单链表实现队头指针指向头节点队尾指针指向链表的最后一个节点。其节点结构体和队的结构体定义大致如下 typedef struct QNode {int data;struct QNode *next;
} QNode, *QueuePtr;typedef struct {QueuePtr front; // 队头指针QueuePtr rear; // 队尾指针
} LinkQueue;应用 操作系统中的作业排队在多道程序设计环境下多个作业等待 CPU 处理时会按照提交的先后顺序排成队列先提交的作业先进入 CPU 执行体现了先进先出的特点。打印机任务队列当多个文档需要打印时它们会按照发送打印请求的先后顺序在队列中排队打印机依次从队列头取出任务进行打印。 跳表 概念 跳表Skip List是一种基于有序链表改进的数据结构通过增加多级索引来提高查找效率它以概率的方式来构建索引层使得查找、插入和删除操作的平均时间复杂度可以达到 其中 n 是元素个数。 描述方法 跳表由多层有序链表组成最底层的链表包含了所有的元素每一层链表都是下一层链表的一个子集并且元素间隔逐渐变大高层的索引链表能够快速跳过一些节点加速查找过程。例如一个简单的跳表节点结构体在 C 语言中可以这样定义 typedef struct SkipListNode {int key;int value;struct SkipListNode *forward[1]; // 指针数组用于指向不同层的下一个节点
} SkipListNode;typedef struct SkipList {SkipListNode *header; // 头节点int level; // 跳表当前层数
} SkipList;应用 数据库索引在一些数据库系统中对于频繁进行查找操作的数据表可以采用跳表来构建索引加快数据查询速度比如在内存数据库中查找特定键值对应的记录时跳表能高效地定位到目标记录。分布式系统中的数据查找在分布式缓存等场景下需要快速查找某个键对应的缓存值跳表可作为一种有效的存储结构来提高查找性能。 散列 概念 散列Hash又称哈希是通过散列函数将数据元素的关键字映射为散列表中的一个地址根据这个地址来存储和查找元素理想情况下可以实现 的时间复杂度来进行插入、查找和删除操作但可能存在冲突情况不同关键字通过散列函数得到相同的地址需要解决冲突。 描述方法 散列函数的选择常见的散列函数有直接定址法例如Hash(key) a * key ba、b 为常数、除留余数法Hash(key) key % pp 通常为小于散列表长度的质数等。解决冲突的方法 开放定址法发生冲突时按照一定的探测序列去寻找下一个空闲的存储单元比如线性探测Hi (Hash(key) i) % mm 为散列表长度i 依次递增、二次探测等。链地址法将散列到同一地址的所有元素构成一个链表存储在散列表对应的槽位中。例如用 C 语言实现链地址法的散列表节点和散列表结构体可以如下 typedef struct HashNode {int key;int value;struct HashNode *next;
} HashNode;typedef struct HashTable {HashNode **table; // 指针数组每个元素指向一个链表头节点int size; // 散列表大小
} HashTable;应用 编译器中的符号表管理在编译程序时对于程序中定义的变量名、函数名等符号通过散列函数将它们映射到符号表中的地址进行存储方便后续在编译过程中快速查找符号对应的属性如变量类型、作用域等。缓存系统中的键值存储像网页缓存以网页的 URL 作为关键字经过散列后存储对应的网页内容在缓存中下次访问相同 URL 时能快速通过散列地址找到缓存内容提高访问效率。 练习题目
一、单选题
1.线性表是 A. 一个有限序列可以为空 B. 一个无限序列不能为空 C. 一个有限序列不能为空 D. 一个无限序列可以为空
答案A
解析线性表是由 nn≥0个相同类型的数据元素组成的有限序列。当 n 0 时线性表为空表所以线性表是一个有限序列可以为空。
2.栈的操作原则是 A. 先进先出 B. 后进先出 C. 只能删除 D. 只能插入
答案B
解析栈是一种只能在一端进行插入和删除操作的特殊线性表遵循后进先出LIFO的原则。就像往一个桶里放东西最后放进去的东西会最先被拿出来。
3.队列操作的原则是 A. 先进先出 B. 后进先出 C. 只能删除 D. 只能插入
答案A
解析队列只允许在一端进行插入操作队尾在另一端进行删除操作队头遵循先进先出FIFO的原则。例如排队买票先排队的人先买到票离开。
4.散列存储中处理冲突的方法有 A. 仅开放定址法 B. 仅链地址法 C. 开放定址法和链地址法 D. 重新散列法
答案C
解析在散列存储中开放定址法是发生冲突时按照一定的探测序列去寻找下一个空闲的存储单元链地址法是将散列到同一地址的所有元素构成一个链表存储在散列表对应的槽位中。这两种都是常见的处理冲突的方法。
5.跳表的平均查找时间复杂度是
答案B
解析跳表通过增加多级索引来提高查找效率以概率的方式来构建索引层使得查找、插入和删除操作的平均时间复杂度可以达到O(logn)其中 n 是元素个数。
二、多选题
1.线性表的存储结构可以是 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储
答案AB
解析线性表主要有两种存储结构顺序存储结构顺序表和链式存储结构链表。顺序存储是用一组连续的存储单元依次存储线性表中的各个元素链式存储是通过节点来存储元素每个节点包含数据域和指针域指针域指向下一个节点节点之间通过指针链接形成线性表。
2.以下属于栈的应用的是 A. 函数调用栈 B. 表达式求值 C. 作业排队 D. 网页缓存
答案AB
解析在程序运行时函数调用栈用于管理函数调用的嵌套表达式求值可以利用栈来辅助实现运算符和操作数的处理。作业排队是队列的应用网页缓存主要是散列的应用。
3.队列的存储结构可以是 A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储
答案AB
解析队列可以用顺序存储结构如顺序队列、循环队列和链式存储结构链队列来实现索引存储和散列存储不是队列常见的存储实现方式用于体现队列的特性。
4.散列函数的常见构造方法有 A. 直接定址法 B. 除留余数法 C. 平方取中法 D. 折叠法
答案ABCD
解析直接定址法是一种简单的散列函数构造方法如Hash(key) a * key b除留余数法Hash(key) key % pp 通常为小于散列表长度的质数比较常用平方取中法是将关键字平方后取中间几位作为散列地址折叠法是将关键字分割成位数相同的几部分然后取它们的叠加和作为散列地址。
5.跳表的组成部分包括 A. 多层有序链表 B. 头节点 C. 索引节点 D. 数据节点
答案ABC
解析跳表由多层有序链表组成最底层的链表包含了所有的元素。有头节点用于方便操作并且通过索引节点构建索引层来加速查找过程跳表中的节点没有专门区分数据节点和其他节点的说法节点既包含数据也包含索引相关的指针。
三、判断题
1.线性表中的元素必须是数字。 答案错误
解析线性表中的元素可以是任何相同类型的数据如字符、字符串、结构体等不一定是数字。
2.栈和队列都是线性表的特殊形式。 答案正确
解析栈和队列都是在基本线性表的基础上对插入和删除操作进行了限制而形成的特殊线性表。栈限制在一端进行插入和删除操作队列限制在两端分别进行插入和删除操作。
3.散列函数计算出来的地址一定不会冲突。 答案错误
解析散列函数可能会产生冲突因为关键字的集合通常比散列表的地址空间大得多不同的关键字可能通过散列函数映射到相同的地址。
4.跳表在最坏情况下的查找时间复杂度和链表一样。 答案正确
解析在最坏情况下跳表的索引层没有起到作用就相当于在底层的链表进行查找时间复杂度和普通链表一样为。
5.顺序队列不存在队列满的情况。 答案错误
解析顺序队列有容量限制当队尾指针到达数组末尾即使队头前面还有空闲空间也会出现队满的假溢出情况不过可以通过循环队列来解决这个问题。
