华中科技大学数据结构试题及答案.pdf

华中科技大学数据结构试题及答案--第1页 数据结构试题及答案 一．是非题（每题1分共10分） 1. 线性表的链式存储结构优于顺序存储结构。 F 2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操 作。F 3 ． 字符串是数据对象特定的线性表。T 4 ．在单链表P 指针所指结点之后插入S 结点的操作是：P-next= S ; S- next = P-next; F 5 ． 一个无向图的连通分量是其极大的连通子图。T 6 ． 邻接表可以表示有向图，也可以表示无向图。T 7 ．假设B 是一棵树，B′是对应的二叉树。则B 的后根遍历相当于B′ 的中序遍历。 T 8． 通常，二叉树的第i 层上有2i-1个结点。F 9 ． 对于一棵m 阶的B-树,树中每个结点至多有m 个关键字。除根 之外的所有非终端结点至少有ém/2ù 个关键字。F 10．对于任何待排序序列来说，快速排序均快于起泡排序。F 二．选择题（每题2分共28分） 1．在下列排序方法中，（c ）方法平均时间复杂度为0(nlogn) ，最坏 情况下时间复杂度为0(n2) ；（d ）方法所有情况下时间复杂度均为 0(nlogn) 。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n 个结点的二叉树的二叉链表表示中，空指针数为（ b ）。 华中科技大学数据结构试题及答案--第1页 华中科技大学数据结构试题及答案--第2页 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中，（a ）可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树 4. 下列查找方法中，（a ）适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查 找 5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查 找完毕，可采用（ a ）方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中，（c ）具有先进先出特性，（b ）具有先进 后出特性。 a ．线性表 b ．栈 c ．队列 d ．广义表 7 ．具有m 个结点的二叉排序树，其最大深度为（ f ），最小深度为 （b ）。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 8 ． 已知 一 组 待 排 序 的记 录 关 键 字 初 始 排 列 如 下 ： 56,34,58,26,79,52,64,37,28,84,57。 下列选择中（ c ）是快速排序一趟排序的结果。 （b ）是希尔排序（初始步长为4 ）一趟排序的结果。 （d ）是基数排序一趟排序的结果。 （a ）是初始堆