Question

《数据结构》考试复习希望各位高手帮忙解答, 马上要考试了,.急急急!!!!

一． 填空题
1. 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点_____________ 后续结点，其余每个结点有且只有1个后续结点。
2. 在树形结构中，根结点没有___________ 结点，其余每个结点有且只有___________ 个前驱结点；叶子结点没有___________ 结点，其余每个结点的后续结点数可以 ______________个前驱结点。
3. 数据的存储结构可用四种基本的存储方法表示，它是____________。
4. 数据的运算最常用的有5种，它们分别是______、________、_________、_______、__________。
5. 一个算法的效率可分为___________效率和_________________效率。
6. 在顺序表中插入或删除一个元素，需要平均移动____________ 元素，具体移动元素个数与线性表中结点的集合是_____________ 的，结点间的关系是_________ 的。
7. _______________ 有关。
8. 向一个长度为n 的向量中第i个元素（1≤i≤n+1）之前插入一个元素时，需向后移动___________ 元素。
9. 向一个长度为n的向量中删除第i个元素（1≤i≤n）时，需向前移动________个元素。
10． 由3个结点所构成的二叉树有_____________ 种形态。
11．一棵深度为6的满二叉树有___________ 个叶子。
12． 设一棵完全二叉树有700个结点，则此共有_________ 个叶子结点。
13． 在数据的存放无规律而言的线性表进行检索的最佳方法是____________。
14．线性有序表(a1,a2,a3,…a256)是从小到大排列的，对一个给定的值K，用二分法检索表中与K相等的元素，在查找不成功的情况下，最多需要检索____________次，设有100个结点，用二分法查找时，最大比较次数是____________。
15．假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为__________ ；比较四次查找成功的结点数为__________。
16．折半查找有序表(4,6,12,20,28,38,50,70,88,100)，若查找表中元素20,它将第一次与表中元素_________比较大小。
17．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是____________。
18．哈希表存储的基本思想是由_____________决定数据的存储地址。
19.一个算法的效率可分为___________效率和_________________效率。
20.在顺序表中插入或删除一个元素，需要平均移动____________ 元素，具体移动元素个数与_______________ 有关。
21.在顺序表中访问任意一结点的时间复杂度均为______________ ，因此，顺序表也称为_______________ 的数据结构。
22.顺序表中逻辑上相邻的元素的物理位置__________相邻。单链表中逻辑上相邻的元素的物理位置_____________相邻。
23.在单链表中，除了首元素结点外，任一结点的存储位置由___________ 指示。
24.在n个结点的单链表中要删除已知*P，需找到它的____________ ，其时间复杂度为_________。
25.向量、栈和队列都是____________ 结构，可以在向量的_________ 位置插入和删除元素；对于栈只能在_______________插入和删除元素；对于队列只能在_________ 插入和_______ 删除元素。
26． 在一个循环队列中，队首指针指向队首元素的________ 位置。
27．在具有n个单元的循环队列中，队满时共有_____________ 个元素。
28． 向栈中压入元素的操作是先_______________ ，后_______________。
29.抽象数据类型包括（ ）和（ ）两个部分
30.一个完全二叉数有200个结点，则度为1的结点有（ ）个
31. 29条边的无向连通图最多有（ ）个顶点，最少有（ ）顶点
32.设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2、度为0的结点，则该二叉树中所含结点至少有（ ）个

Answer 1

1.没有
2. 前驱 1 后继 多
3. 顺序存储 链表存储 索引存储 散列存储
4. 数据的运算最常用的有5种，插入， 删除，
5. 时间复杂度 空间复杂度
6. n*(n-1)/2 ？
7. ??????????
8.n-i+1
9.n-i
10．5
11．32
12.350 (n0+n1+n2=700 n=n2+1 n1只能去0 或1 所以，700=2n0- 1+n1 所以 n1=1 n0=350)

13．快速排序
14．线性有序表(a1,a2,a3,…a256)是从小到大排列的，对一个给定的值K，用二分法检索表中与K相等的元素，在查找不成功的情况下，最多需要检索____________次，设有100个结点，用二分法查找时，最大比较次数是____________。
15．假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为__________ ；比较四次查找成功的结点数为__________。
16．28
17．散列查找 （即哈希表的查找 只和负载因子有关）
18．哈希函数
19.时间 空间
20. (n-1)/2 插入位置
21.O(1) 随机存取
22一定 不一定
23.前驱结点的指针
24.前驱结点 O(n)
25.线性 任意 栈顶 队尾 队头
26． 下一个
27．n-1
28． *S.top=data top++
29.数据元素的表示 数据元素的关系
30. 1
31. 28 8 （ n 个顶点 无向连通图 至少 n-1条边 之多 n*(n-1)/2
）
32. 2^(h+1) -1
(h=0-------->n=1=2^0=2^h h=1-------->n=3= 2^1 +2^0=2^h +2^(h-1)
h=2-------->n=7=2^2+ 2^1 +2^0=2^h +2^(h-1) +2^(h-2)
-----------
n=0+1+2+--------+2^h=2^(h+1) -1 等比公式