数据结构研究生试题

思凯学习俱乐部

第九章 集合

一、 选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2

4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学

目录

I 考查目标 ......................................................................................... 2 II 考试形式和试卷结构 ................................................................... 2 III 考查内容 ..................................................................................... 2 IV. 题型示例及参考答案 ................................................................. 3

1

全国硕士研究生入学统一考试

数据结构考试大纲

I 考查目标

全国硕士研究生入学统一考试模式识别与智能系统、计算机技术、软件工程、农业信息化硕士专业学位《数据结构》考试是为江苏大学招收以上硕士生设置的具有选拔性质的考试科目。其目的是科学、公平、有效地测试考生是否具备攻读模式识别与智能系统、计算机技术、软件工程、农业信息化专

Houjiuming

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分

- 1 -

计算机组成原理 45分 操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

2009年全国硕士研究生入学统一考试

Ⅲ.考查范围

数据结构

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分 计算机组成原理 45分

- 1 -

操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

Ⅲ.考查范围

数据结构

【考查目标】

1.理解数据结构的基本概念；掌握数据的逻辑结构

Houjiuming

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考 计算机学科专业基础综合

考试大纲 教育部考试中心

中国学位与研究生教育学会工科工作委员会

目 录

I. 考查目标

II. 考试形式和试卷结构考查范围 III. 考查范围

数据结构 计算机组成原理 操作系统 计算机网络 IV.

试题示例

Ⅰ.考查目标

计算机学科专业基础综合考试涵盖数据机构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。要求考生比较系统地掌握上述专业基础课程的概念、基本原理和方法，能够运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

本试卷满分为150分，考试时间为180分钟 二、答题方式 答题方式为闭卷、笔试 三、试卷内容结构 数据结构 45分

- 1 -

计算机组成原理 45分 操作系统 35分 计算机网络 25分 四、试卷题型结构

单项选择题 80分（40小题，每小题2分） 综合应用题 70分

2009年全国硕士研究生入学统一考试

Ⅲ.考查范围

数据结构

第一章 绪论

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。

● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.

● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

您所在位置：数据结构网络教学平台>>> 试卷汇粹>>数据结构试题汇总

一、选择题

第一二章

1．数据结构是一门研究计算机中____对象及其关系的学科。 （1）数值运算 （2）非数值运算 （3）集合 （4）非集合

2．数据结构的定义为(K，R)，其中K是____的集合。 （1）算法 （2）数据元素 （3）数据操作 （4）逻辑结构 3．算法分析的目的是____。 （1） 找出数据结构的合理性 （2） 研究算法中输入和输出的关系 （3） 分析算法的效率以求改进

（4） 分析算法的易懂性和文档性

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行___。 （1）s->link=p;p->next=s;

（2）s->link=p->link;p->link=s; （3）s->link=p->link;p=s;

（4）p->link=s;s->link=p;

5．在循环链表中first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是____。

（1）current->link=NULL (2)first->link=current

（3）first=current (

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[20分] 1、 算法的定义和性质

2、 为什么说数组与广义表是线性表的推广？ 3、 什么是结构化程序设计？

4、 哈希方法的基本思想

5、 给出一不稳定排序方法名称与实例

二、 构造结果：[24分]

（1） 确定x:=x+1语句在下面程序段中的频率，要求写出分析过程。 for i:=1 to n do

for j:=1 to I do

for k:=1 to j do x:=x+1

（2） 画出对长度为8的有序表进行折半查找的判定树，并求其在等概率时查找成功的平均查找长度。

（3） 已知一棵二叉树如右图，给出对这棵二叉树进行前序、中序、后序遍历的结果序列．

（4） 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为{2，3，5，7，11，4，13，15}，试为这8个字母设计哈夫曼编码．

（5） 在地址空间为0~15的散列区中，对以下关键字序列构G造哈希表，关键字序列为（Jan,Feb,Mar, Apr,May,Jun,Jul Aug,Sep,Oct,Nov,Dec），H(x)=[i/2] ，其中i

院、系领导 审批并签名

A / B卷 广州大学 2009-2010 学年第 二 学期考试卷

课程 数据结构 考试形式（开卷/闭卷，考试/考查）学院

系 专业 班级 学号 姓名_ 题次 分数 评分 一 10 二 20 三 10 四 30 五 30 六 七 八 九 十 总分 评卷人 100 一、单项选择题（10分，每小题1分）

1、 输出一个二维数组b[m][n]中所有元素值的时间复杂度为（ ）。

A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

2、在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2

B. n/2

C. n

D. n+1

3、 设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p

所指结点之后插入指针s所指结点，则应执行下列哪一个操作？

A. p->rLink = s; s->lLink = p