admin 管理员组

文章数量: 887006

华南理工大学计算机考研试题,《2016年华南理工大学31计算机专业综合考研试题》.doc...

《2016年华南理工大学31计算机专业综合考研试题》.doc

831

华南理工大学 2011 年攻读硕士学位研究生入学考试试卷

(请在答题纸上做答，试卷上做答无效，试后本卷必须与答题纸一同交回)

科目名称：计算机专业综合(数据结构、操作系统) 适用专业：计算机技术(专业学位)本卷满分：150 分共 页

数据结构部分

一、选择题(每小题2分，共20分)

1． 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。

A、O(n2) B、O(nlog2n) C、O(n) D、O (log2n) 2．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。

A、希尔排序 B、汽包排序C、插入排序D、选择排序

3．已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历 序列是( )。

A、acbedB、decabC、deabcD、cedba

4. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是

()。A.nB. (n-1)2C. n-1D. n2数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10， 从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]起始

地址为( )。

A、SA+141B、SA+180C、SA+222D、SA+225

设有两个串p和q, 求q在p中首次出现的位置的运算称作( )。 A、连接 B、模式匹配 C、求子串 D、求串长

采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )。 A、先序遍历 B、中序遍历 C、后序遍历 D、按层遍历

将含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、(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 个不同的英文单词，它们的长度相等，均为 m, 若 n ＞＞50,m＜ 5,试问采用什么排序方法时间复杂度最佳？为什么？

三、算法设计(30分)

1、(10分)假设二叉树采用链接存储结构进行存储，root指向根结点，p所指结 点为任一给定的结点，编写一个求出从根结点到p所指结点之间路径的函数。

2、(10分)假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B,

要求B也采用三元组表示。

3、(10分)假设有一个链表，其结点包含3个域：pre,data和next,其中data为

数据域，next为指针域，其值为后续结点的地址，pre也为指针域，其初始值 为空(NULL)，编写一个函数将此链表改为循环双链表。

操作系统部分一、名字解释(每个5) 1、用户认证

2、死锁二、试说明用户级线程和核心级线程的区别。(10分)

第2 页三、假定在公交车上有两种角色的进程：司机和售票员。其职责分别为：公交车到站

后，停车，售票员打开车门，等待乘客上车或下车，然后关门。司机在关门后将公交 车开到下一个车站。请使用up和down操作描述司机和售票员的行为。(15分)

四、某磁盘每个磁道有10个扇区。假定磁头通过一个扇区需要耗费3ms，如果是读数 据的话，还要另外花费6ms去处理数据。回答以下问题：(12 分) 1、假定一个磁道上所有的扇区均按照其扇区号一个接一个顺序存放。如果磁盘读进

程要顺序读取一个磁道上的所有扇区的数据，则会花费多长时间？

2、 试设计一种有效的扇区存放策略，使得顺序读取一个磁道上的所有扇区所花费的

时间最少，并计算顺序读取一个磁道上的所有扇区所花费的时间。

五、某操作系统采用页式内存管理策略，其页的大小是1k字节。假定某进程的地址空

间如下图所示。整个内存的大小是10k字节，页框0和1用于操作系统。进程的前三页 装在页框2，4和8。(1

本文标签： 华南理工大学计算机考研试题 《2016年华南理工大学31计算机专业综合考研试题》doc

版权声明：本文标题：华南理工大学计算机考研试题,《2016年华南理工大学31计算机专业综合考研试题》.doc... 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732362024h1535487.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。