1 / 10
文档名称:

数据结构(c语言版)复习资料.doc

格式:doc   大小:116KB   页数:10页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

数据结构(c语言版)复习资料.doc

上传人:蓝天 2021/10/15 文件大小:116 KB

下载得到文件列表

数据结构(c语言版)复习资料.doc

文档介绍

文档介绍:数据结构复****资料
一、填空题
数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学
科。
数据结构被形式地定义为(D,R),其中D是 数据元素 的有限集合,R是D上的 关系 有限集合。
数据结构包括数据的 逻辑结构 、数据的存储结构 和数据的 运算 这三个方面的内容。
数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构 。
线性结构中元素之间存在二对二关系,树形结构中元素之间存在二关系,图形结构中元素之间存在多对多关系。
在线性结构中,第一个结点 没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点 没有 后续结 点,其余每个结点有且只有1个后续结点。
在树形结构中,树根结点没有前驱 结点,其余每个结点有且只有 1 个前驱结点;叶子结点没有 后续 结点,
其余每个结点的后续结点数可以任意多个 。
在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个 。
数据的存储结构可用四种基本的存储方法表示,它们分别是顺序、链式、索引和散列。
数据的运算最常用的有5种,它们分别是插入、删除、修改、查找、排序。
一个算法的效率可分为时间 效率和空间效率。
在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与表长和该元素在表中的位置 有关。
线性表中结点的集合是有限 的,结点间的关系是 一对一 的。
向一个长度为n的向量的第i个元素(IWiWn+l)之前插入一个元素时,需向后移动n-i+1个元素。
向一个长度为n的向量中删除第i个元素(IWiWn)时,需向前移动n-i个元素。
在顺序表中访问任意一结点的时间复杂度均为0(1),因此,顺序表也称为随机存取 的数据结构。
顺序表中逻辑上相邻的元素的物理位置二蟾相邻。。
在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值 指示。
在n个结点的单链表中要删除已知结点*p,需找到它的前驱结点的地址,其时间复杂度为O (n)。
向量、栈和队列都是 线性 结构,可以在向量的 任何 位置插入和删除元素;对于栈只能在 栈顶 插入和 删除元素;对于队列只能在队尾 插入和队首删除元素。
栈是一种特殊的线性表,允许插入和删除运算的一端称为栈顶 。不允许插入和删除运算的一端称为―栈 底
是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。
不包含任何字符(长度为0)的串 称为空串; 由一个或多个空格(仅由空格符)组成的串 称为空白串。
子串的定位运算称为串的模式匹配;被匹配的主串 称为目标串,子串称曹模式。
假设有二维数组A6x8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,
则数组A的体积(存储量)为 288B ;末尾元素A”的第一个字节地址为 1282 ;若按行存储时,元素缶,的
第一个字节地址为(8+4)X6+1000=1072 :若按列存储时,元素A&的第一个字节地址为(6X7+4)X6+1000)=
1276
由3个结点所构成的二叉树有_ 种形态。
一棵深度为6的满二叉树有m+n,=0+ 11,= 11“-1=31个分支结点和2心=32个叶子。

最近更新