文档介绍：数据结构复****资料一、。(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合。、数据的存储结构和数据的运算这三个方面的内容。,它们分别是线性结构和非线性结构。,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。,每个结点的前驱结点数和后续结点数可以任意多个。,它们分别是顺序、链式、索引和散列。,它们分别是插入、删除、修改、查找、排序。。,需要平均移动表中一半元素,具体移动的元素个数与表长和该元素在表中的位置有关。,结点间的关系是一对一的。(1≤i≤n+1)之前插入一个元素时,需向后移动n-i+1个元素。(1≤i≤n)时,需向前移动n-i个元素。(1),因此,顺序表也称为随机存取的数据结构。。单链表中逻辑上相邻的元素的物理位置不一定相邻。,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值指示。*p,需找到它的前驱结点的地址,其时间复杂度为O(n)。、栈和队列都是线性结构,可以在向量的任何位置插入和删除元素;对于栈只能在栈顶插入和删除元素;对于队列只能在队尾插入和队首删除元素。,允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。,在表的另一端进行删除运算的线性表。(长度为0)的串称为空串;由一个或多个空格(仅由空格符)组成的串称为空白串。;被匹配的主串称为目标串,子串称为模式。×8,每个元素用相邻的6个字节存储,存储器按字节编址。已知A的起始存储位置(基地址)为1000,则数组A的体积(存储量)为288B;末尾元素A57的第一个字节地址为1282;若按行存储时,元素A14的第一个字节地址为(8+4)×6+1000=1072;若按列存储时,元素A47的第一个字节地址为(6×7+4)×6+1000)=1276。。+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子。注:满二叉树没有度为1的结点,所以分支结点数就是二度结点数。,它的深度为9。(注:用ëlog2(n)û+1=ëû+1=,则共有350个叶子结点。答:最快方法:用叶子数=[n/2]=,则此完全二叉树有500个叶子结点,有499个度为2的结点,有1个结点只有非空左子树,有0个结点只有非空右子树。答:最快方法:用叶子数=[n/2]=500,n2=n0-1=499。另外,最后一结点为2i属于左叶子,右叶子是空的,所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况,所以非空右子树数=(线性查找)。(a1,a2,a3,…,a256)是从小到大排列的,对一个给定的值k,用二分法检索表中与k相等的元素,在查找不成功的情况下,最多需要检索8次。设有100个结点,用二分法查找时,最大比较次数是7。[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为2;比较四次查找成功的结点数为8;。解:显然,平均查找长度=O(log2n)<5次(25)。但具体是多少次,则不应当按照公式来计算(即(21×log221)/20=!)。因为这是在假设n=2m-1的情况下推导出来的公式。应