青岛大学2005年硕士研究生入学考试试题

学科代码： 407 科目名称： 数据结构 （共4页） 请考生写明题号，将答案全部答在答题纸上，答在试卷上无效

一．单项选择题（本大题共10道小道小题，每小题3分，共30分）

1. 算法的时间复杂度取决于 【 】

A. 问题的规模 B. 待处理数据的初始状态

C. 软件和硬件的组合 D. 操作系统

2. 向一个栈顶指针为top的链栈中插入一个s结点，则执行 【 】

A. top->next=s; B. s->next=top->next; top->next=s;

C. s->next=top; top=s; D. s->next=top; top=top->next;

3. 广义表（（a））的表头是 【 】

A. a B. (a) C. () D. ((a))

4. 由带权为8、2、5、7的叶子结点构造一棵哈夫曼树，该树的带权路径长度为 【 】

A. 37 B. 32 C. 46 D. 43

5. 采用邻接表存储的图，其BFS算法类似于二叉树的 【 】

A. 中序遍历 B. 先序遍历 C. 后序遍历 D. 按层遍历

6. 在非空m阶B_树上，除根结点之外的所有其他非终端结点 【 】

A. 至少有 m/2 棵子树 B. 至多有 m/2 棵子树

C. 至少有 m/2 棵子树 D. 至多有 m/2 棵子树

7. 对线性表进行顺序查找时，要求线性表的存储结构为 【 】

A. 散列存储 B. 顺序存储或者链式存储

C. 压缩存储 D. 索引存储

8. 在关键字“基本有序”的情况下，最佳排序算法为 【 】

A. 快速排序 B. 冒泡排序 C. 直接插入排序 D. 基数排序

9. 折半查找法和二叉排序树的时间性能 【 】

A. 与处理数据量有关 B. 相同 C. 不相同 D. 不确定

10. 串是一种特殊的线性表，其特殊性体现在 【 】

A. 可以顺序存储 B. 数据元素是一个字符

C. 可以链接存储 D. 数据元素可以是多个字符

二、填空题（本大题共10小题，每小题2分，共20分）

1. 在具有n个单元的循环队列中，队满时共有____________个元素。

2. 单链表中设置头结点的目的是____________。

3. 消除递归_____________需要使用栈。

4. 在具有n(n≥1)个结点的k叉树中，有_____________个空指针。

5. 深度为5的二叉树至多有_________个结点。

6. 一个连通图的__________是一个极小连通子图。

7. 对稀疏图进行DFS遍历时，应该采用___________作为其存储结构。

8. 在哈希表中，装填因子α越大，则_______________________。