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

831 华南理工大学 2011 年攻读硕士学位研究生入学考试试卷 （请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回） 科目名称：计算机专业综合(数据结构、操作系统) 适用专业：计算机技术(专业学位) 本卷满分：150 分 共 页 数据结构部分 一、选择题（每小题2分，共20分） 1．采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。 2 A 、O(n ) B 、O (nlogn) C、O(n) D 、O (log n) 2 2 2 ．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A 、希尔排序 B 、汽包排序 C、插入排序 D 、选择排序 3 ．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历 序列是（ ）。 A 、acbed B 、decab C、deabc D 、cedba 4. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 ( ) 。 2 2 A. n B. (n-1) C. n-1 D. n 5. 数组A 中，每个元素A 的长度为3个字节，行下标i从1到8，列下标j 从1到10， 从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]起始 地址为 （）。 A 、SA+141 B 、SA+180 C、SA+222 D 、SA+225 6. 设有两个串p和q, 求q在p 中首次出现的位置的运算称作 （）。 A 、连接 B 、模式匹配 C、求子串 D 、求串长 7. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（ ）。 A 、先序遍历 B 、中序遍历 C、后序遍历 D 、按层遍历 8. 将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编 号，根结点的编号为1。编号为47 的结点X 的双亲的编号为( ) 。 A 、24 B 、25 C、23 D 、无法确定 9．设n,m为一颗二叉树上的两个结点，在中序遍历时，n在m前的条件是（ ）。 A 、n在m右方 B 、n是m祖先 C、n在m左方 D 、n是m子孙 10．快速排序方法在( )情况下最不利于发挥其长处。 A 、要排序的数据量太大 B 、要排序的数据中含有多个相同值 C、要排序的数据已经基本有序 D 、要排序的数据个数为基数 二、简答题（共25分） 第 1 页 1、（7分）任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子 结点有（m-1）个度数为2，其余度数为1。 2 、（6分）请画出在图中所示的3阶B-树中依次插入关键字值55和69 以后B-树 的状态。 3、（6分）已知一表为(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec),按表中 顺序依次插入初始为空的二叉排序树，(1)在右边画出建立的二叉排序树。(2) 求出在等概率情况下查找成功的平均查找长度。 4 、 (6 分) 有n 个不同的