数据结构复习资料
一、填空题
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的体积（存储量）为288Bc语言二维数组表示方法；末尾元素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。另外，最后一结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0.
31．在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查（线性查）。
32.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查不成功的情况下，最多需要检索8次。设有100个结点，用二分法查时，最大比较次数是7。
33.假设在有序线性表a[20]上进行折半查，则比较一次查成功的结点数为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．折半查有序表（4，6，12，20，28，38，50，70，88，100），若查表中元素20，它将依次与表中元素28，6，12，20比较大小。
35.在各种查方法中，平均查长度与结点个数n无关的查方法是散列查。
36.散列法存储的基本思想是由关键字的值决定数据的存储地址。
二、判断正误（在正确的说法后面打勾，反之打叉）
（×）1.链表的每个结点中都恰好包含一个指针。
答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点
可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（×）2.链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
（×）3.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
错，链表的结点不会移动，只是指针内容改变。
（×）4.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。