计算机基础知识——数据结构与算法（二）（山东省大数据职称考试）

  大数据分析应用-初级

第一部分 基础知识

       一、大数据法律法规、政策文件、相关标准

       二、计算机基础知识

       三、信息化基础知识

       四、密码学

       五、大数据安全

       六、数据库系统

       七、数据仓库.

第二部分 专业知识

       一、大数据技术与应用

       二、大数据分析模型

       三、数据科学

---

大数据相关标准

• 大数据分析应用-初级
• 前言
• 一、线性表的概念
• 二、堆栈、队列、跳表和散列的描述方法与应用
• 练习题目

---

前言

数据结构与算法

2、掌握线性表的概念，掌握堆栈、队列、跳表和散列的描述方法与应用。

---

一、线性表的概念

概念

线性表是由 n（n≥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）是一种只能在一端进行插入和删除操作的特殊线性表，允许操作的一端称为栈顶，另一端称为栈底。遵循后进先出（LIFO，Last 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）也是一种特殊的线性表，它只允许在一端进行插入操作（队尾），在另一端进行删除操作（队头），遵循先进先出（FIFO，First 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 + b，a、b 为常数）、除留余数法（Hash(key) = key % p，p 通常为小于散列表长度的质数）等。
• 解决冲突的方法：
  • 开放定址法：发生冲突时，按照一定的探测序列去寻找下一个空闲的存储单元，比如线性探测（Hi = (Hash(key) + i) % m，m 为散列表长度，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

解析：线性表是由 n（n≥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 % p（p 通常为小于散列表长度的质数）比较常用；平方取中法是将关键字平方后，取中间几位作为散列地址；折叠法是将关键字分割成位数相同的几部分，然后取它们的叠加和作为散列地址。

5.跳表的组成部分包括（ ）
A. 多层有序链表
B. 头节点
C. 索引节点
D. 数据节点

答案：ABC

解析：跳表由多层有序链表组成，最底层的链表包含了所有的元素。有头节点用于方便操作，并且通过索引节点构建索引层来加速查找过程，跳表中的节点没有专门区分数据节点和其他节点的说法，节点既包含数据也包含索引相关的指针。

三、判断题

1.线性表中的元素必须是数字。（ ）
答案：错误

解析：线性表中的元素可以是任何相同类型的数据，如字符、字符串、结构体等，不一定是数字。

2.栈和队列都是线性表的特殊形式。（ ）
答案：正确

解析：栈和队列都是在基本线性表的基础上，对插入和删除操作进行了限制而形成的特殊线性表。栈限制在一端进行插入和删除操作，队列限制在两端分别进行插入和删除操作。

3.散列函数计算出来的地址一定不会冲突。（ ）
答案：错误

解析：散列函数可能会产生冲突，因为关键字的集合通常比散列表的地址空间大得多，不同的关键字可能通过散列函数映射到相同的地址。

4.跳表在最坏情况下的查找时间复杂度和链表一样。（ ）
答案：正确

解析：在最坏情况下，跳表的索引层没有起到作用，就相当于在底层的链表进行查找，时间复杂度和普通链表一样，为。

5.顺序队列不存在队列满的情况。（ ）
答案：错误

解析：顺序队列有容量限制，当队尾指针到达数组末尾，即使队头前面还有空闲空间，也会出现队满的假溢出情况，不过可以通过循环队列来解决这个问题。