数据结构考研题目

《数据结构》实验题目

实验一 客房管理（链表）

? 实验目的：熟练掌握单循环链表操作的基本算法实现。

? 实现功能：以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。 ? 实验机时：8 ? 设计要求：

(1)定义客房链表结点结构类型，以Hotel和*HLink命名，数据域：客房名称roomN、标准价格Price、入住价格PriceL(默认值=标准价格*80%)、床位数Beds、入住状态State(空闲、入住、预订，默认值为空闲)，指针域：*next；

(2)实现创建客房基本情况链表函数void Build(HLink &H)，输入客房名称、标准价格、床位数，将入住价格、入住状态修改为默认值，建议用文件操作来输入数据；

(3)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state；

(4)实现输出客房基本情况函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；

(5)函数void Add(HLink &H)，将该链表中未入住的客房入住价格均加价20%；

(6)函数void upBed(

数据结构笔试题题目

一、 选择题

1. 下面哪种排序法对123456798在空间和时间上最优( )

A. 快速排序 B. 冒泡排序 C. 插入排序 D. 堆排序

2. 2.就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是（ ） A．堆排序〈 快速排序〈归并排序 B．堆排序〈 归并排序〈 快速排序 C．堆排序〉 归并排序 〉快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对

3. 3.一株二叉树的以某种遍历方式的序列为A、B、C、D、E、F、G，.若该二叉树的根结

点为E,则它的一种可能的前序遍历为____ ,相应的后序遍历为____

A. ECBADFG, BDCAFGE C. ECBADGF, EACBDGF

B. ECBADFG, EFACDBG D. EACBDGF, BDCAFGE

（常见题型，给出树的前序遍历和中序遍历，中序和后续遍历，推出二叉树） 4. 关于图和树，下面说法正确的是________

A. 树和图都允许有环

B. 图的深度遍历和广度遍历结果可能一样 C. 二叉树是每个节点都有两个孩子节点的树

D. 二叉树的前序遍历和后序遍历结果肯定不一样

5. 完成在双循

? ? ? ? ? ? ? ? ? ? ? ?

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

n（n>20）的阶乘 【问题描述】

大数运算——计算n的阶乘（n>=20）。 【基本要求】

（1）数据的表示和存储；

（1.1） 累积运算的中间结果和最终的计算结果的数据类型要求是整型——这是问题本身的要求；

（1.2） 试设计合适的存储结构，要求每个元素或结点最多存储数据的3位数值。

（2）数据的操作及其实现：

基于设计的存储结构实现乘法操作，要求从键盘上输入n值，在屏幕上显示最终计算结果。 【测试数据】

（1）n＝20，n！＝2432902008176640000

（2）n＝30，n！＝265252859812191058636308480000000 #include \#include #include using namespace std; template class Chain;

template class ChainNode {

friend Chain;

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[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

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[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

[注]：编写程序可选用任一种高语言，算法描述可采用类语言，必要时加上注释 一、 回答下列问题：[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

问题说明

部分题目或答案有问题，现将已经发现的公布如下，同学在作这些模拟题的时候应着重做题方法的理解，遇到问题以教材或课件为准，不确定的地方可找同学商量或问我

（1）试卷1第一套填空题第1题，试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致，以教材或课件为准，实际上front指向的是队头元素，rear指向当前尚未被占用的第一个队列空间，队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材

（2）试卷1第一套应用题第5题，不声明邻接点顺序时默认编号最小的邻接点为第一邻接点，该图的深度优先遍历序列为123465,答案错。此外，当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定，如试卷1第二套填空题第8题

（3）试卷1第五套应用题第4题，两种方法处理冲突的方法下所求ASL值相等都为7/6

（4）试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件，大顶堆满足 ki>=k2i && ki>=k2i+1 （5）试卷1第一套填空题第9题模式匹配的BF算法以书中答案为准，两者区别在于，教材中存储字符串的数组的0号单元不存放有效字符，而试卷答案认为0号单元也放数组

（6）试卷1第二套填空题第7题给定初始序列

数据结构作业

班级： 学号： 姓名： 教师：

第一章：概述

一．单项选择。

1、数据结构是一门研究数值计算得程序设计问题中计算机的 以及它们之间的 和运算等的学科。

(1)A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 （2）A．结构 B关系 C运算 D算法 2、数据结构被形式地定义为（K，R），其中K是 的有限集，R是K上的 有限集。 （1）A.算法 B.数据元素 C.数据操作 D.逻辑结构 （2）A.操作 B.映像 C.存储 D.关系

3、 线性结构的顺序存储结构是一种 的存储结构，线性表的链式存储结构式一种 的存储结构。

A．随机存取 B.顺序存取 C.索引存取 D.散列存取

4、计算机算法指的是 ，它必须必备输入，输出和 等5个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可执行性、可移值性和可扩充性 B.

数据结构作业

班级： 学号： 姓名： 教师：

第一章：概述

一．单项选择。

1、数据结构是一门研究数值计算得程序设计问题中计算机的 以及它们之间的 和运算等的学科。

(1)A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 （2）A．结构 B关系 C运算 D算法 2、数据结构被形式地定义为（K，R），其中K是 的有限集，R是K上的 有限集。 （1）A.算法 B.数据元素 C.数据操作 D.逻辑结构 （2）A.操作 B.映像 C.存储 D.关系

3、 线性结构的顺序存储结构是一种 的存储结构，线性表的链式存储结构式一种 的存储结构。

A．随机存取 B.顺序存取 C.索引存取 D.散列存取

4、计算机算法指的是 ，它必须必备输入，输出和 等5个特性。 （1）A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2）A.可执行性、可移值性和可扩充性 B.

《数据结构》上机实验题目 （共8次，每次上机4小时）

第一阶段（线性部分）

《数据结构》第1上机题 （线性表练习） 1．编程实现书P19 ADT List 基本操作12个：

（1） 用顺序存储结构实现； （2）用链式存储结构实现； 2．编程实现顺序表和单链表的就地逆置（习题集P18 2.21 2.22）。

《数据结构》第2上机题 （线性表练习）

1．分别用顺序结构和单链表结构编程实现下列功能：假设以两个元素依值递增有序排列的线性表A和B 分别表示两个集合，现要求在A的空间上构成一个新线性表C，其元素为A和B元素的交集，且表C中的元素也是依值递增有序排列（习题集P18 2.25 2.26）；

2．设有一个双向循环链表，每个结点中除有pre，data和next三个域外，还增设了一个访问频度域freq。在链表被起作用前，频度域freq的值均初始化为零，而当对链表进行一次LOCATE(L,x)的操作之后，被访问的结点（即元素值等于x的节点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编程实现之（习题集P19 2.38）。

《数据结构》 第3