华南理工大学数据结构2008考研试题研究生入学考试试题考研真题
● 摘要
818
华南理工大学
2008年攻读硕士学位研究生入学考试试卷
（请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回） 科目名称：数据结构
适用专业：软件工程 共 4 页
一、 选择题. (30分)
1. 一个算法必须满足的条件不包括以下选项中的:
(A) 终止性 (B) 由正确步骤组成 (C) 无歧义性 (D) 正确性
2. 选择当n 变大时所对应的增长率最有效率的算法:
(A) 2n2 (B) 30 log n (C) 5n (D) 2n
3. 下面说法不对的是 :
(A) 3个节点的二叉树有5种不同形状.
(B) 在一个非空二叉树中，空子树的个数等于这个树的节点数.
(C) 非空完全二叉树中，叶子结点只可能出现在最下两层
(D) 一个非空满二叉树中叶子的个数比内部节点个数多1.
4. 一个基于磁盘请求的程序运行时间最有效的节省方法是:
(A) 减少递归调用次数. (B) 将磁盘访问次数最小化
(C) 改进基本操作. (D) 减少主存使用.
5. 树的索引方法能克服哈希方法的哪个缺点?
(A) 不能处理范围查询. (B) 不能处理大数据集合.
(C) 不能处理更新. (D) 以上都不是.
6. 有一个占4字节的指针和一个需要12字节的数据元素，当数组在什么状态下链
表实现比基于数组的实现要求的空间更少:
(A) 少于一半满. (B) 少于2/3满.
(C) 少于1/3满. (D) 少于3/4满.
7. 给定数组 A[m][n]. 若A [0][0]位于644(10) ，A [2][2]存储在676(10), 且每个元素占
一个空间. “(10)”为十进制表示. 那么元素A [3][3](10) 的位置是:
(A) 692 (B) 695 (C) 650 (D) 708
8. 堆排序的时间复杂性为：（n 为元素的个数）。
（A ）O(n) (B) O(log n) (C) O(n log n) (D) O(n2)
9. 在链表中进行以下哪类操作比在顺序表中进行操作效率高。
第 1 页