2012年华南理工大学考研试题 831计算机专业综合(数据结构、操作系统).pdfVIP

831 华南理工大学 2012 年攻读硕士学位研究生入学考试试卷 （请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回） 科目名称：计算机专业综合(数据结构、操作系统) 适用专业：计算机技术(专硕) 本卷满分：150 分 共 4 页 数据结构部分 一、 选择题（每小题 2 分，共 20 分） 1. 设数组 a[1..10,5..15]的元素以行为主序存放，每个元素占用 4 个存储单元，则 数组元素 a[i,j] (1≤i≤10,5≤j ≤15)的地址计算公式为______________ 。 A ．a-204+2i+j B. a-204+40i+4j C ．a-84+i+j D. a-64+44i+4j 2. 给定一个有 n 个元素的线性表。若采用顺序存储结构，则在等概率前提 下，向其插入一个元素需要移动的元素个数平均为______________ 。 A ．n+1 B. n/2 C ．(n+1)/2 D. n 3. 采用邻接表表示一有向图，若图中某顶点的入度和出度分别为 d1 和 d2， 则该顶点对应的单链表的节点数为______________ 。 A ．d1 B. d2 C ．d1-d2 D. d1+d2 4. 设有 100 个节点，用二分法查找时，最大比较次数是______________ 。 A ．25 B. 50 C ．10 D. 7 5. 若长度为 n 的线性表采用顺序存数结构，在其第i 个位置插入一个新元素 算法的时间复杂度是______________ 。 A ． O(log 2 2n) B.O(1) C ．O(n) D. O (n ) 6. 一棵 124 个叶结点的完全二叉树最多有__________个结点。 A ．247 B. 248 C ．249 D. 250 7. 将上万个一组无序并且不相等的正整数序列，存放于顺序存储结构中， 采用__________方法能够最快地查找出其中最大的正整数。 A ．快速排序 B. 插入排序 C ．选择排序 D. 归并排序 8. 前序遍历序列和中序遍历序列相同的二叉树为__________ 。 A ．根节点无左子树的二叉树 B ．根节点无右子树的二叉树 C ．只有根节点的二叉树或非叶子节点只有左子树的二叉树 D ．只有根节点的二叉树或非叶子节点只有右子树的二叉树 9. 判断“链式队列为空”的条件是__________ （front 为头指针,rear 为尾指 针）。 A ．front==NULL B. rear==NULL C ．front==rear D. front!=rear 第 1 页 10. 判断一个表达式中左右括号是否匹配，采用__________实现较为方便。 A ．线性表的顺序存储 B. 队列 C ．线性表的链式存储 D. 栈 二、 判断题（每题 1.5 分，共 15 分） 1.用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储 空间大小只与图中节点个数有关，而与图的边数无关。（ ） 2.负载因子（填充因子）是散列法的一个重要参数，