一. 填空题
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的结点,则该二叉树中所含结点至少有( )个