没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构导论自考的复习大摘要
数据结构导论自考的复习大摘要
5星 · 超过95%的资源 需积分: 50 30 下载量 161 浏览量
更新于2023-03-03
评论
收藏 6.08MB DOC 举报
《数据结构导论》是一门较难的课程,特别是对于广大的自考学生,这份资料帮助自考生在考试前复习用。
资源详情
资源评论
资源推荐
数据结构导论复习大摘要
第一章 概论
1.数据:凡能被计算机存储、加工处理的对象。
2.数据元素:是数据的基本单位,在程序中作为一个整体而加以考虑和处理
3.数据项:又叫字段或域,它是数据的不可分割的最小标识单位。
4.逻辑结构需要注意的几点:
① 逻辑结构与数据元素本身的内容无关
② 逻辑结构与数据元素相对位置无关
③ 逻辑结构与所有结点的个数无关
5.数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。
6.四类基本逻辑结构(集合、线性结构、树形结构和图形结构)的不同特点?
答:集合中任何两个结点之间都没有逻辑关系,组织形式松散;
线性结构中结点按逻辑关系依次排列形成一条“锁链”;
树形结构具有分支、层次特性,其形态有点像自然界中的树;
图状结构最复杂,其中的各个结点按逻辑关系互相缠绕,任何两个结点都可以领接。
7.运算是在逻辑结构层次上对处理功能的抽象
8.基本运算的含义?
答:假如 是 S 上的一些运算的集合, 是 的一个子集,使得 中每一运算都可以
“归约”为 中的一个或多个运算,而 中任一运算不可归约为别的运算,则称 中运算
为基本运算
9.数据结构是指由一个逻辑结构 S 和 S 上的一个基本运算集 构成的整体(S ,
)。
10.数据结构涉及数据表示和数据处理两个方面
11.存储结构的含义和四种基本存储方式的基本思想?
答:存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。
一个存储结构应包含三个主要的部分:存储结点、机内表示和附加设施。
存储结构包括四种存储方式,顺序存储方式、链式存储方式、索引存储方式和散列存
储方式。
12.运算实现与运算的联系与区别?
答:运算指的是数据在逻辑结构 S 上的某种操作,运算只描述处理功能,不包括处理步
骤和方法;而运算实现是指一个完成该运算功能的程序,运算实现的核心是处理步骤的规
定,即算法设计。
13.算法的概念和分类?
答:算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序,使得给
定类型的任何问题能在有限时间内被机械地求解。
算法的类型有:运行终止的程序可执行部分、伪语言算法和非形式算法(根据描述算
法语言不同)
14.算法在给定输入下的计算量的含义和估算的方法?
答:算法在给定输入下的计算量是指根据该类问题的特点合理地选择一种或几种操作作
为“标准操作”,确定每个算法在给定输入下共执行多少次标准操作,并将此次数规定为该
算法在给定输入下的计算量。 估算的方法有:最坏时间复杂度和平均时间复杂度。
15.最坏情况时间复杂性和平均时间复杂性的概念?
答:最坏情况时间复杂性也称为最坏时间复杂度,是指以算法在所有输入下的计算量的
第 1 页 共 20 页
最大值作为算法的计算量;平均情况时间复杂性也称为平均时间复杂度,是指以算法在所
有输入下的计算量的加权平均值作为算法的计算量;
16.空间复杂性指的是一个算法除输入数据占存储空间之外所需要的附加存储空间的大小。
17.算法的性质:正确性、易读性、健壮性和高效率。
第二章 线性表
1.线性结构:是 n(n≥0)个结点的有穷序列。
2.线性结构的基本特征:若至少含有一个结点,则除起始结点没有直接前趋外,其他
结点
有且仅有一个直接前趋;除终端节点没有直接后继外,其他结点有且仅有一个直接后
继。
3.线性表的逻辑结构是线性结构
4.线性表的六种基本运算的功能?
答:⑴初始化 INITIATE(L),功能是建立一个空表
⑵ 求表长 LENGTH(L),功能是返回线性表 L 的长度
⑶ 读表元 GET(L,i),功能是返回线性表 L 的第 i 个结点
⑷ 定位(按值查找)LOCATE(L,X),功能是返回找到的结点集合中序号的最小值,
否则返回值为 0(说明没有找到)
⑸ 插入 INSERT(L,X,i),功能是在线性表 L 的地 i 个位置上增加一个值为 X
的新结点(整个表长+1)
⑹ 删除 DELETE(L,i),功能是撤销线性表 L 的第 i 个位置结点(整个表长-1)
5.顺序表表示法的基本思想、特点
答:基本思想是:按照顺序存储方式,顺序表的一个存储结点存储线性表的一个结点
的内容,即数据元素,所有存储结点按相应数据元素建的逻辑关系决定的次序依次排
列。
特点:逻辑结构中相邻的结点在存储结构中仍相邻。
6.区别顺序表的容量与线性表的表长?
答:顺序表的容量是指定义顺序表时的 maxsize 的值,而线性表的表长是指其中包含
的结点个数。
7.顺序表中 ai 的地址计算:ai 的地址=b+(i-1)*l,b 是首地址,l 是每个结点占的空
间
7.掌握顺序表上实现插入、删除和定位运算的三个算法 P18-20
8.单链表表示法的基本思想——用指针表示结点间逻辑关系
9.单链表的结点形式:
答:由数据域和指针域两部分组成;这两部分各自的作用分别是数据域是用于存储线
性表的一个数据元素的,指针域是用于存放一个指针的,该指针指向本结点所含数据
元素的直接后继所在的结点。
10.头指针和头结点的作用?
答:头指针是一个指向链表开始结点的指针,单链表由头指针唯一确定;头结点是
我们人为地在链表的开始结点之前附加的一个结点,有了头结点之后,头指针指向头
结点,不论链表是否为空,头指针总是非空的,而且头指针的设置使得对链表的第一
位置上的操作和在其他位置上的操作一致。
11.单链表上实现插入、删除和定位三种运算的三个算法:P26-28
12 . 插 入 算 法 中 所 包 含 的 指 针 操 作 :
s=malloc(size);s→data=x;s→next=p→next;p→next=s;
第 2 页 共 20 页
删除算法中所包含的指针操作:q=p→next;p→next=q→next;free(q);
13.Malloc(size)的作用:
① 生成一个结点
② 形式一条指针
14.循环链表的组织方法:将单链表中的尾结点的 NULL 改成指向头结点的指针,就
形成了循环链表。循环链表优点:可以从表中任一结点出发都可以向后扫描整表。
15.双链表的结点形式:
刻画双链表结构的对称性的语句:p→prior→next== p→next→prior;
16.顺序表的主要优点和主要缺点:
优点:①无需为表示结点间的逻辑关系而增加额外的存储空间
② 可以方便地随机存取表中的任意结点
缺点:①插入和删除运算不方便
② 分配内存空间采用静态分配方式
17.链表的主要优点:
① 插入和删除运算方便,只需要修改指针,不需要移动结点
② 分配内存空间采用动态分配方式
18.字符串:以字符为数据元素,以线性结构为逻辑结构的数据。
19.串的逻辑结构(是线性结构)和串的特点(是由 0 个或多个字符组成的有穷序
列)
20.串的基本运算的功能:判等 EQUAL(S,T)的功能是两个串的长度要相等,而且对应
位置的字符都要相同。
21.串的顺序存储方法(紧缩格式和非紧缩格式)和链接存储方法
第三章 栈、队列和数组
1.栈的基本运算及由此而决定的栈的基本特点
栈是一种只允许在栈顶进行插入、删除的特殊线性表;其基本特点是采用“后进先出”操
作;
2.栈的基本运算:①初始化 InitStack(S)②进栈 Push(S,X)③退栈 Pop(S)
④ 读栈顶元素 TOP(S)⑤判断栈空 Empty(S)
3.顺序栈 “上溢”、“下溢”的概念
“上溢”:顺序栈在进行进栈时,超过了顺序栈的最大的容量
“下溢”:顺序栈在进行退栈时,栈中的元素少于 0 个元素
4.进栈和退栈运算在顺序栈上的实现算法:P44
5.顺序栈上的简单算法(初始化,判栈空,取栈顶元素)
6.链栈的结点形式及其描述:
Data 用来存放该结点的数据元素
Next 用来存放指向下一个数据元素
7.链栈上实现进栈和退栈的算法 P46
8.链栈上的简单算法(初始化,判栈空,取栈顶元素)
9. 队列的基本运算及由此决定的队列的特点
队列是一种只允许在对头进行插入在队尾进行删除的特殊线性表;其基本特点是采
用“先进先出”操作;
10.顺序队上的“假溢出”及其解决方法:顺序队在进行多次入队、出队后,顺序队已经
第 3 页 共 20 页
满了,但顺序队中的大部分空间是空的;
解决方法:将顺序队改成循环队
11.循环队队满、队空的条件:
判断循环栈满的条件:((sq→rear+1)%maxsize)==sq→front
判断循环栈空的条件:sq→rear== sq→front
12.链队的结点形式及其链队的组织方法:
13.在链队上实现入队、出队的算法 P56-57
14.数组的逻辑结构是线性结构的推广
15.二维数组的基本运算是读与写
16.二维数组: ,其中 a[0][0]是首地址,k 是每
个数据元素存储单元。
17.稀疏矩阵的三元组表示法:A=(i,j,aij)
A=((1,2,3),(1,6,1),(3,1,5),(3,2,-1),( 4,5,4),( 5,1,-
3))
第四章 树
1.树的定义:是 n(n>0)个结点的有穷集合,满足:
① 有且仅有一个称为根的结点
② 其余结点分为 m(m≥0)个互不相交的非空集合 T1,T2…… Tm,这些集合中
的每一个都是一棵树,称为根的子树。
2.树形结构的有关术语及其含义
① 根结点
② 双亲结点和孩子结点
③ 兄弟结点和堂兄弟结点
④ 子孙结点和祖先结点
⑤ 树的层次、树的高度和树的度
3.二叉树的逻辑结构、特点和五种基本形态
(1):二叉树是 n(n≥0)个结点的有穷集合,满足:
① 有且仅有一个称为根的结点
② 其余结点分为 2 个互不相交的集合 T1,T2,T1 是左子树,T2 是右子树,且
T1,T2 也都是一棵二叉树。
(2)特点:①二叉树是棵有序树
② 二叉树的度≤2
(3)五种基本形态
4.二叉树的基本运算和性质
第 4 页 共 20 页
剩余19页未读,继续阅读
nhqfhg
- 粉丝: 6
- 资源: 14
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
- MW全能培训汽轮机调节保安系统PPT教学课件.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2