数据结构期末复习资料剖析.doc

数据结构复习资料 ??????????????? ? 一、填空题 1. ?数据结构是一门研究非数值计算的程序设计问题中计算机的??操作对象 ???以及它们之间的???关系????和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是???数据元素 ???的有限集合，R是D上的???关系 ??有限集合。 3. 数据结构包括数据的??逻辑结构???、数据的?存储结构???和数据的???运算??这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是???线性结构 ??和???非线性结构 ???。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6． 在线性结构中，第一个结点??没有?前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点??没有????后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有?前驱 ?结点，其余每个结点有且只有???1???个前驱结点；叶子结点没有??后续 ???结点，其余每个结点的后续结点数可以任意多个 ??。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以??任意多个 ???。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 ?、 链式 、 索引 ?和 ?散列 ?。 10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。 11. 一个算法的效率可分为??时间????效率和???空间???效率。 12. 在顺序表中插入或删除一个元素，需要平均移动?表中一半元素，具体移动的元素个数与?表长和该元素在表中的位置??有关。 13. 线性表中结点的集合是?有限????的，结点间的关系是???一对一????的。 14. 向一个长度为n的向量的第i个元素(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. 向量、栈和队列都是??线性 ??结构，可以在向量的??任何?????位置插入和删除元素；对于栈只能在???栈顶???插入和删除元素；对于队列只能在???队尾????插入和???队首???删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为???栈顶????。不允许插入和删除运算的一端称为????栈底?????。 22. ????队列??是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. ??不包含任何字符（长度为0）的串??称为空串；????由一个或多个空格（仅由空格符）组成的串????称为空白串。 24. 子串的定位运算称为串的模式匹配；?被匹配的主串????称为目标串，??子串???称为模式。 25. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为????288 B ??；末尾元素A57的第一个字节地址为???1282 ????；若按行存储时，元素A14的第一个字节地址为??(8+4)×6+1000=1072 ???；若按列存储时，元素A47的第一个字节地址为??(6×7＋4)×6＋1000）＝1276 ????。 26． 由３个结点所构成的二叉树有???5??种形态。 27. ??一棵深度为6的满二叉树有?n1+n2=0+ n2= n0-1=31 ?个分支结点和?26-1?=32??个叶子。 注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。 28． 一棵具有２５７个结点的完全二叉树，它的深度为???9????。 （ 注：用??log2(n) ?+1= ??8.xx ?+1=9 29．设一棵完全二叉树有700个结点，则共有??350??个叶子结点。 答：最快方法：用叶子数＝[n/2]＝350 30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有?500??个叶子结点，有??499???个度为2的结点，有???1???个结点只有非空左子树，有??0????个结点只有非空右子树。 答：最快方法：用叶子数＝[n/2]＝500 ，n2=n0-1=499。 另外，最后