数据结构复习题
一、填空题
1.  数据结构是一门研究非数值计算的程序设计问题中计算机的  操作对象    以及它们之间的  关系    和运算等的学科。
2. 数据结构被形式地定义为（D, R），其中D是   数据元素    的有限集合，R是D上的   关系  有限集合。
3. 数据结构包括数据的 逻辑结构  、数据的 存储结构  和数据的  运算  这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是  线性结构   和  非线性结构   。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多二叉树的深度为k关系，图形结构中元素之间存在多对多关系。
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）；还有一种时间复杂度为O(1)的巧妙删除方法，即把p的后继结点中数据拷贝到p结点中，然后删除p的后继结点，删除语句应该是q=p->next; p->next=q->next;free(q);。
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  个叶子结点。
解：最快方法：最后一个叶子编号为700，其父节点编号为[n/2]＝350，且其父节点为最后一个非叶子结点。
30． 设一棵完全二叉树具有1000个结点，则此完全二叉树有 500  个叶子结点，有  499  个度为2的结点，有  1  个结点只有非空左子树，有  0    个结点只有非空右子树。
解：方法同上：最后一个非叶子编号为[n/2]＝500，所以叶子结点数n0=500, n2=n0-1=499。 另外，最后一个结点为2i属于左叶子，右叶子是空的，所以有1个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数＝0. 也可根据编号为50
0的左右儿子结点应该为1000和1001，而显然1001不存在。
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. 散列法存储的基本思想是由  关键字的值    决定数据的存储地址。
37．数据的逻辑结构可分为集合结构、_线性结构_、__树形结构__和__图形结构_等4种。
38．从长度为n的采用顺序存储结构的线性表中删除第i个元素(1≤i≤n),需要移动
  n-i 个元素, 在第i个元素前面插入一个元素，需要移动 n-i+1 个元素。
39．顺序存储的栈，做入栈运算时，应先判断栈是否为 满 ，做出栈运算时，应先判断栈是否为  空  。
40．已知一个栈的进栈先后次序为abcd，判断下面两个序列能否是其出栈序列：
(1)dbca  不能         (2)cbda  能   (注：填“能”或者“不能”)
41．长度为0的字符串称为_空串_。设正文串长度为n，模式串长度为m，则简单模式匹配算法的时间复杂度为__O(n*m)_。
42．设广义表L=(()，()) ，则GetHead(L)是 () ；GetTail(L)是  (()) ；L的长度是 2  ；L的深度是  2 。
43．由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_55_。
44．完全二叉树的第7层有8个结点，则此完全二叉树的叶子结点数为_36_。768个结点的完全二叉树有_384_个叶子结点？19个结点的哈夫曼树有_10_个叶子结点？
45．n个顶点的无向连通图，用邻接矩阵存储时，该矩阵至少有 2n-2 个非零元素。
46．希尔排序的增量序列有多种选择，但不管哪种选择，最后一个增量必须为__1__。
47．假设以S和X分别表示入栈和出栈操作，则对输入序列a，b，c，d，e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为_bceda_。
48. 组成串的数据元素只能是_字符_。
49．n个结点的完全二叉树，编号最大的非叶结点是_[n/2]_号结点，编号最小的叶结点是_[n/2]+1_号结点。
50．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 99 。
51. 在一棵二叉树中，度为0的结点个数为N0,则度为2的节点个数为 N0-1 。
52. 叶子权值(5，6，17，8，19)所构造的哈夫曼树带权路径长度为  121  。
53. 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。
54.在n个元素的线性表中顺序查，若查成功，则关键字的比较次数最多为 n_次；使用监视哨时，若查失败，则关键字的比较次数为 n+1 次。
55.折半搜索只适合用于__有序的顺序存储表__。
56.结点关键字转换为该结点存储单元地址的函数H称为_哈希函数_或叫_散列函数_。
57.在一棵k叉树中，度为i(0<=i<=k)的结点的个数为Ni,则有N0 =。
解：所有结点数记为n，结合树中分支数比结点数少一个，以及每一个分支被计入顶点的度1次，则有
            n  =N0+N1+…+Nk
            n-1=  1*N1+2*N2+…k*Nk //所有结点度数的和
    两式相减即得。
58.设一棵完全二叉树叶子结点数为k,最后一层结点数为偶数时，则该二叉树的高度为    ；最后一层结点数为奇数时，则该二叉树的高度为    。
解：根据完全二叉树性质，结点数为n的完全二叉树，其深度为【或者+1】，所以只要推算出二叉树结点即可。

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