《数据结构》考试复习希望各位高手帮忙解答,马上要考试了,.一．填空题1.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点；最后一个结点后续结点,其

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 等比公式