数据结构2009年试题

学生姓名__________ 学号_________________院系___________ 班级___________

-------------------------------密------------------------------封----------------------------线---------------------------------

烟台大学20 10 ～20 11 学年第 二 学期

数据结构 试卷B

（考试时间为120分钟）

题号 得分 阅卷人 一 二 三 四 五 合分人 总分 （注：第三大题答案请写在后面的空白答题纸上） 一、单项选择题(每小题2分，共20分)

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )

A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i (1≤i≤n+1)个位置上删除一个元素，元素的移动次数为( ) A.n-i+1

学生姓名__________ 学号_________________院系___________ 班级___________

-------------------------------密------------------------------封----------------------------线---------------------------------

烟台大学20 10 ～20 11 学年第 二 学期

数据结构 试卷B

（考试时间为120分钟）

题号 得分 阅卷人 一 二 三 四 五 合分人 总分 （注：第三大题答案请写在后面的空白答题纸上） 一、单项选择题(每小题2分，共20分)

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )

A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构 2.在长度为n的顺序表的第i (1≤i≤n+1)个位置上删除一个元素，元素的移动次数为( ) A.n-i+1

目 录

第一章．概述 ................................................................................................................................................ 1

1．1 本章重点 ...................................................................................................................................... 1 1．2 本章难点 ...................................................................................................................................... 1 1．3 本章习题 ...................................................................

院、系领导 审批并签名

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

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

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

考试大纲 教育部考试中心

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

目 录

I. 考查目标

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

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

试题示例

Ⅰ.考查目标

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

Ⅱ.考试形式和试卷结构

一、试卷满分及考试时间

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

- 1 -

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

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

Ⅲ.考查范围

数据结构

【考查目标】

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

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

一、选择题

第一二章

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

数据结构试题B卷

一、单选题（每小题2分，共8分）

1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。

A n B n/2 C (n+1)/2 D (n-1)/2

2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ ）进行。

A 栈顶 B 栈底 C 任意位置 D 指定位置

4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）

A 24 B 71 C 48 D 53 二、填空题（每空1分，共32

数据结构试题库

一、 单项选择题

1．下列程序段所代表的算法的时间复杂度为（ D ）。

x=n; y=0;

while (x>=(y+1)*(y+1)) y++;

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)

2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除

元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（ B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2

3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为

（ C ）。

(A)HS->next=s; (B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;

4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设

队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（ A ）。

void AddQueue(struct link