1252 数据机构（本） 复习题20220622

一、选择题。

1. 广义表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表头是________。 答案：a
2. 在一棵具有35个结点的完全二叉树中，该树的深度为(    )。 答案：6
3. 在一棵具有n个结点的二叉树的第i层上，最多具有(    )个结点。 答案： 2i-1
4. ________遍历一棵二叉排序树可得到一个有序序列。 答案：中序
5. 10.字符串 a1=“AEIJING”，a2=“AEI”，a3=“AEFANG”，a4=“AEFI”中最大的是（    ）。 答案：a1
6. 10个元素进行冒泡法排序，其中第5趟冒泡共需要进行________次元素间的比较。 答案：5
7. c语言中，字符串“E”存储时占_______个字节。 答案：2
8. n个元素进行冒泡法排序，第j趟冒泡要进行______次元素间的比较。 答案：n-j
9. n个元素进行冒泡法排序，通常需要进行________趟冒泡。 答案：n-1
10. 把数据存储到计算机中，并具体体现（    ）称为物理结构。 答案：数据元素间的逻辑关系
11. 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（   ）。 答案：物理结构
12. 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（    ）。 答案：存储结构
13. 采用分块查找时，若线性表中共有324个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（  ）个结点最佳。 答案：18
14. 采用分块查找时，数据的组织方式为（   ）。 答案：把数据分城若干块，块内数据不必有序，但块间必需有序，每块内最大（或最小）的数据组成索引表
15. 采用邻接表存储的图的广度优先搜索遍历算法类似于二叉树的（   ）。 答案：层次遍历
16. 采用邻接表存储的图的深度优先搜索遍历算法类似于二叉树的（    ）。 答案：先序遍历
17. 采用顺序查找法对长度为n（n为偶数）的线性表进行查找，采用从前向后的方向查找。在等概率条件下成功查找到前n/2个元素的平均查找长度为（   ）。 答案： (n+2)/4
18. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（   ）。 答案：(n+1)/2
19. 常对数组进行的两种基本操作是（     ）。 答案：查找和修改
20. 串的长度是指（     ）。 答案：串中所含字符的个数
21. 串函数StrCmp(“abA”,”aba”)的值为（     ）。 答案：-1
22. 串是（     ）。 答案：有限个字符的序列
23. 串是一种特殊的线性表，其特殊性体现在（   ）。 答案：数据元素是一个字符
24. 串与普通的线性表相比较，它的特殊性体现在（    ）。 答案：数据元素是一个字符
25. 从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（   ）。 答案：插入排序
26. 带头结点的链表为空的判断条件是（     ）（设头指针为head）。 答案：head->next==NULL
27. 待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为________。 答案：1，2，4，8，3，5，9