复习提纲_6月＿测绘工程
以下为《复习提纲_6月＿测绘工程》的无排版文字预览，完整内容请下载
数据结构 复习提纲
测绘工程（2021年6月）
考试题型：
四种： 选择题、填空题、简答题、算法阅读题
第一章 概论
1．数据结构的四种基本逻辑结构形式_集合_、线性结构、树形结构和图或网状结构。各种结构中的结点的前驱与后继是什么情况？各种结构的开始结点和终端结点有什么不同？
2. 两种基本的存储结构是顺序存储结构、链式存储结构。两种结构有什么异同？它们的优缺点分别是什么？
数据的储存结构主要有：顺序存储结构和链式存储结构。
主要区别
一、存储单元的连续性不同
链式存储结在构计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
顺序存储结构在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素。
二、优缺点不同
空间上
顺序比链式节约空间。是因为链式结构每一个节点都有一个指针存储域。
存储操作上：
顺序支持随机存取，方便操作
插入和删除上：
链式的要比顺序的方便（因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）
3. 数据结构一般有查找、删除、插入、修改四大类基本操作。两种基本的存储结构分别适用于哪些操作？
链式存储适用于在较频繁地插入、删除、更新元素时，而顺序存储结构适用于频繁查询时使用。
4．什么是算法？算法的5个重要特性：_______。怎么样是“好的算法”？
5. 什么是时间复杂度？比较理想的时间复杂度曲线是怎样的？O(n2)与O(nlogn)，哪种更好？
第二章 线性结构 （线性表）
1．线性结构的四大基本特征(4个唯一)是：______________
2．三种常见的线性结构：队列、栈、线性表。它们的定义、特点以及相关术语，以及基本操作都有哪些？
3．在一个单某某中，若q所指结点是p所指结点的前驱结点。若在q与p之间插入一个s所指的结点，则必须执行两条核心语句以修改指针，这两条语句依次是：s->next = p ;q->next = s。如果是删除p或q所指结点，核心语句序列是q->next = p->next;free(p)。
4．队列需设置front和rear指针，分别指向什么位置？栈需设置base和top指针，分别指向什么位置？
队头元素的位置和队尾元素的下一位置。指向首地址或基地址，top指针永远指向空，即指向栈顶元素的下一位置
5. 三种常见的线性结构，如何判定空表、满表？
栈：空：s.top=0,满：s.top>=s.size
顺序存储的队列：空：Q.front==Q.rear,满：Q.rear==Q.maxSize
1、单某某
（不带头结点）空：head==NULL? ? ? ? ?(带头结点）空：head->next==NULL
2、循环链表
空：head->next==head
3、双向链表
空：p->prior==p? ?p->next==p
二、栈与队列
1、栈
空：S->top==S->base
满：S->top-S->base>=S->stacksize
2、队列
普通队列：
空：q->front==q->rear==NULL
满：q->rear==MAXSIZE-1
循环队列：
由于入队时尾指针追着头指针，出队时头指针追着尾指针，因此如果一般情况处理的话q->front==q->rear无法区分满还是空，因此需要浪费一个存储空间来区分空满
空：q->front==q->rear
满：q->front=(q->rear+1)%MAXSIZE
6． 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 则每个顶点的度最大是多少？
解：对无向图，最大为n-1；对有向图，最大可为2(n-1)，因为每个顶点到其余n-1顶点都可有一条入边和出边。
6．如何由输入的边信息画邻接表、邻接矩阵？如何分别在两种存储结构上进行DFS、BFS遍历？
7．DFS的实现用到栈，BFS的实现用到队列。
8．DFS类似树的先根遍历，BFS类似树的层次遍历。
18．例：在邻接矩阵M[n][n]上求顶点k的入度。
解：入度＝矩阵相应列中1的个数。
int in(int M[n][n],int n,int k) {
int i,j=0;
for(i=0;i请点击下方选择您需要的文档下载。
- 二级公共基础知识复习资料
- 建筑力学学习心得
- 硕士研究生入学考试自命题科目 考试大纲
- 18.太空生活趣事多教学设计
- 数据结构ch01第1章绪论
- 数据结构讨论题无答案
- 1案例精讲10 第一节 审计理论研究的意义与原则
- 队形队列常规口令
- 课程设计指导书-数据结构-计算机级
- 计算机二级公共基础考点 1
- 小学美术静物素描教案
- 企业云盘-FM脚本
- 分布式存储-LoongStore文件系统运维手册
- 《数据结构(c语言版)》知识点概括
- 《地球的圈层结构》教案
- 《数据结构》考试大纲
- 柱锥台球的结构特征(1)教案
- 教学设计教材内容
- 06015 贴合鼓技术协议
以上为《复习提纲_6月＿测绘工程》的无排版文字预览，完整内容请下载
复习提纲_6月＿测绘工程由用户“呵呀呵哇”分享发布，转载请注明出处