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