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

《数据结构(c语言版)复习资料new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、不逼自己一把，怎么知道你有多优秀。数据结构复习资料一、填空题1.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科2.数据结构被形式地定义为（DR）其中D是数据元素的有限集合R是D上的关系有限集合3.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容4.数据结构按逻辑结构可分为两大类它们分别是线性结构和非线性结构5.线性结构中元素之间存在一对一关系树形结构中元素之间存在一对多关系图形结构中元素之间存在多对多关系6．在线性结构中第一个结点没有前驱结点其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点其余每个结点有

2、且只有1个后续结点7.在树形结构中树根结点没有前驱结点其余每个结点有且只有1个前驱结点；叶子结点没有后续结点其余每个结点的后续结点数可以任意多个8.在图形结构中每个结点的前驱结点数和后续结点数可以任意多个9．数据的存储结构可用四种基本的存储方法表示它们分别是顺序、链式、索引和散列10.数据的运算最常用的有5种它们分别是插入、删除、修改、查找、排序11.一个算法的效率可分为时间效率和空间效率12.在顺序表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与表长和该元素在表中的位置有关13.线性表中结点的集合是有限的结点间的关系是一对一的14.向一个长度为n的向量的第i个

3、元素(1≤i≤n+1)之前插入一个元素时需向后移动n-i+1个元素15.向一个长度为n的向量中删除第i个元素(1≤i≤n)时需向前移动n-i个元素16.在顺序表中访问任意一结点的时间复杂度均为O(1)因此顺序表也称为随机存取的数据结构17.顺序表中逻辑上相邻的元素的物理位置必定相邻单链表中逻辑上相邻的元素的物理位置不一定相邻18．在单链表中除了首元结点外任一结点的存储位置由其直接前驱结点的链域的值指示19．在n个结点的单链表中要删除已知结点*p需找到它的前驱结点的地址其时间复杂度为O（n）20.向量、栈和队列都是线性结构可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删

4、除元素；对于队列只能在队尾插入和队首删除元素21.栈是一种特殊的线性表允许插入和删除运算的一端称为栈顶不允许插入和删除运算的一端称为栈底22.队列是被限定为只能在表的一端进行插入运算在表的另一端进行删除运算的线性表23.不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串24.子串的定位运算称为串的模式匹配；被匹配的主串称为目标串子串称为模式25.假设有二维数组A6×8每个元素用相邻的6个字节存储存储器按字节编址已知A的起始存储位置（基地址）为1000则数组A的体积（存储量）为288B；末尾元素A57的第一个字节地址为1282；若按行存储时元素

5、A14的第一个字节地址为(8+4)×6+1000=1072；若按列存储时元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝127626．由３个结点所构成的二叉树有5种形态27.一棵深度为6的满二叉树有n1+n2=0+n2=n0-1=31个分支结点和26-1=32个叶子注：满二叉树没有度为1的结点所以分支结点数就是二度结点数28．一棵具有２５７个结点的完全二叉树它的深度为9（注：用?log2(n)?+1=?8.xx?+1=929．设一棵完全二叉树有700个结点则共有350个叶子结点　　答：最快方法：用叶子数＝[n/2]＝35030．设一棵完全二叉树具有1000个结点则此完

6、全二叉树有500个叶子结点有499个度为2的结点有1个结点只有非空左子树有0个结点只有非空右子树答：最快方法：用叶子数＝[n/2]＝500n2=n0-1=499另外最后一结点为2i属于左叶子右叶子是空的所以有1个非空左子树完全二叉树的特点决定不可能有左空右不空的情况所以非空右子树数＝0.31．在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）32.线性有序表（a1a2a3...a256)是从小到大排列的对一个给定的值k用二分法检索表中与k相等的元素在查找不成功的情况下最多需要检索8次设有100个结点用二分法查找时最大比较次数是733.假设在有序线性表a[20

7、]上进行折半查找则比较一次查找成功的结点数为1；比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7解：显然平均查找长度＝O（log2n）<5次（25）但具体是多少次则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）因为这是在假设n＝2m-1的情况下推导出来的公式应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74；ASL＝74/20=3.7！！！34．折半查找有序表（4612202838507