东华理工大学数据结构(含C程序设计)考研真题试题2016年—2018年

数据结构c语言版试题大全(含答案)数据结构C语言版试题大全（含答案）第一章：基本概念与算法设计1.1 数据结构的定义与特点数据结构是指相互之间存在一种或多种特定关系的数据元素的集合，它包括了数据的存储、组织和管理方式。

数据结构的特点包括以下几个方面：- 数据元素之间存在某种关系，构成逻辑结构- 对数据元素的操作对应于对其逻辑结构的操作- 数据结构有存储结构，包括顺序存储结构和链式存储结构- 算法是对数据结构的操作步骤的描述和实现1.2 算法的基本概念算法是解决特定问题或完成特定任务的一系列操作步骤。

算法的基本概念包括以下几个方面：- 有穷性：算法必须能在有限步骤内完成- 确定性：算法的每一步骤必须有确定的含义和结果- 可行性：算法的每一步骤必须可行，能够通过执行有限次数实现- 输入：算法接受的输入数据是原始问题的实例- 输出：算法产生的输出数据与输入有明确的关系1.3 算法的描述方法算法可以用自然语言、伪代码或流程图来描述。

常用的伪代码描述方法包括结构化语言和算法描述语言，结构化语言包括顺序结构、分支结构和循环结构。

第二章：线性结构2.1 线性表的定义与基本操作线性表是n个数据元素的有限序列，其中相邻元素之间存在唯一的前驱和后继关系。

线性表的基本操作包括插入、删除、查找和修改等。

2.2 数组与广义表数组是指具有相同数据类型的一组数据元素的集合，可以通过下标访问元素。

广义表是线性表的推广，其中元素可以是基本数据类型或另一个广义表。

第三章：树与二叉树3.1 树的定义与基本术语树是n（n≥0）个结点的一个有限集合，其中满足以下条件：- 有且仅有一个特定的称为根的结点- 其余结点可分为m（m≥0）个互不相交的有限集合，每个集合本身又是一棵树3.2 二叉树的定义与性质二叉树是指每个结点最多有两个子结点的树结构。

二叉树的性质包括以下几个方面：- 深度为k的二叉树最多有2^k-1个结点- 一棵二叉树的第i层最多有2^(i-1)个结点- 在二叉树的第i层上至多有2^(n-i+1)-1个结点（n为树的深度）第四章：图4.1 图的基本概念与术语图是由顶点的有穷非空集合和边的有穷集合组成的。

注意：答案请做在答题纸上，做在试卷上无效
第 1 页，共 2 页 东华理工大学2016年硕士生入学考试初试试题
科目代码： 811 ; 科目名称：《数据结构（含C 程序设计）》；（A 卷） 适用专业（领域）名称：077500、081200计算机科学与技术
一、编写程序题：（共5小题，每小题12分，共60分）
1. 某百货公司进行促销活动，对于购物价格x≥5000元的8折，5000>x≥3000元的
8.5折，3000>x≥1000的9折，否则没有折扣。

编写函数，计算对购物x 元的折后价。

2. 计算1+(1×2)+(1×2×3)+…+(1×2×3×…×n)。

3. 已知一个班1门课的成绩，计算高于平均分的学生人数所占的百分数。

4. 输入一行字符，统计出26个大小写英文字母的个数。

5. 从键盘输入一串字符，除了空格，逐个把这些字符写入磁盘文件中，直到用户输入一个‘@’为止。

二、综合过程题：（共9小题，每小题10分，共90分）
1.设结点的类型如下：
typedef struct node
{ char data;
struct node *next;
}linklist;
编写建立带头结点的单链表的函数,结点值从键盘输入，当输入为‘#’时结束。

2.已知顺序栈的结构定义如下，编写出栈的函数。

typedef struct
{ int d[100];
int top;
}sqstack;
3.已知二叉树如下图，写出其前、中、后续的遍历结果。

数据结构课程设计论文题目：基于线性表下的查找与排序姓名：赖德发学院：理学院专业：信息与计算科学班级：1123202学号：2011203202022014年1月17日一、实验环境（1）硬件：学生每人一台计算机。

（2）软件：Windows操作系统，Visual C++6.0。

二、实验内容基于线性表下的查找与排序。

三、实验原理1.基于线性表的查找法概述集合结构是数据对象之间关系松散的一种数据结构，对其进行查找是根据给定的关键字，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。

查找的方法分为比较式查找法和计算式查找法，其中比较式查找法可分为基于线性表的查找法和基于树的查找法；而计算式查找法也称为Hash(哈希)查找法。

基于线性表的查找法是将集合的数据对象组织成为线性表形式进行查找，即用给定的关键字与线性表中各元素的关键字逐个比较，直到成功或失败。

线性表的存储结构通常是顺序存储结构，也可使用链式存储结构。

查找时可在表的一端设置一个“监视哨”，存放要查找元素的关键字，从表的另一端开始查找，若在“监视哨”找到要查找元素的关键字，返回失败信息，否则返回关键字的位序。

基于线性表的查找技术有着非常广泛的应用。

2.基于线性表的排序法概述排序是计算机程序设计中的一种重要操作，在数值计算或数据处理过程中，都会直接或间接用到数据的排序问题。

排序的功能是将一个数据元素（或称记录）的无序序列，按数据元素的关键字大小排列成一个递增或递减有序的记录序列。

由于待排序的记录数量不同，使得排序过程中涉及的存储器也不同，因此可将排序方法分为内排序和外排序。

内排序包括插入、交换、选择和归并等几类排序。

2.1基于插入类的排序概述插入类排序的基本思想是假定记录序列中前面的一部分记录已经有序，把后面的一个记录插入已排序的有序子序列中去，使得插入这个记录后得到的依然是有序序列，从而逐步扩大有序的子序列的长度，直到所有记录都有序为止。

东华理工大学2015 —2016学年第 一 学期考试模拟试卷 A一、 填空题（50分）1、数据结构是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。

（2分）2、数据结构的类型通常分为： 集合、线性结构、树形结构、图状结构或网状结构 ；从逻辑上可以把它们分成： 线性结构和非线性结构 。

3、数据的 逻辑结构 只抽象反映数据元素的 逻辑关系 ；数据的 存储（物理）结构 是数据的逻辑结构 在计算机存储器中的实现 。

4、算法分析的目的是分析算法的 效率以求改进 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。

A5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。

6、线性结构中元素之间的关系存在 一对一 关系，树形结构中元素之间的关系存在 一对多 关系，图形结构中元素之间的关系存在 多对多 关系。

7、试写出以下算法的时间复杂度i=s=0while (s<n) {i++;s += i;}7、试写出以下算法的时间复杂度i = 1 while( i <= n) )(n Oi = i*2O(log2n)8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象， S是D上的关系集，P是对D的基本操作集。

9、写出抽象数据类型线性表的定义ADT List{数据对象：D={ai | ai ∈Elemset, i=1,2,…,n,n≥0}数据关系：R={< ai-1 , ai> | ai-1 , ai ∈D, i=2,…,n}基本操作：InitList(&L) //构造一个空的线性表LDestroyList(&L) //消毁线性表LListLength(L) //返回L中数据元素的个数ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除L中的第i个元素，并用e 返回ListTraverse(L,visit()) //依次对L的每个元素调用函数visit()…………} ADT List10、指出线性表顺序存储、链式存储结构的优缺点。

数据结构(本)(网教)202301-模拟卷注：找到所考试题直接看该试题所有题目和答案即可。

查找按键：Ctrl+F超越高度一、单选题(共10题，20分)1、设循环队列中数组的下标范围是l~n,其头尾指针分别尾f、r,则队列中元素的个数为().A、r-fB、r-f+1C、(r-f+1)modnD、(r-f+n)modn正确答案：D2、以下哪一个不是队列的基本运算？A、从队尾插入一个新元素B、从队列中删除第i个元素C、判断一个队列是否为空D、读取队头元素的值正确答案：B3、有一个有序表｛1,3,9,12,32,41,62,75,77,86,95,100),当二分查找值为86的关键字时,需要比较的次数是()。

A、2B、3C、4D、5正确答案：C4、栈S最多能容纳4个元索。

现有6个元索按A、B、C、D、E、F的顺序进栈,问下列哪一个序列是可能的出栈序列？Λ.E、D、C、B、A、FB.B、C、E、F、A、DC.C、B、E、D、A、FD.A、D、F、E、B、C正确答案：C5、n个顶点的无向连通图至少有()条边。

A、n-1B、nC、n+1D、2n正确答案：A6、设有IOOOO个无序元索,希望用较快速度挑选出其中前15个最大元素,采用()方法最好.A、直接插入排序B、堆排序C、快速排序D、归并排序正确答案：B7、已知一棵二叉排序树,通过()可以得到结点的有序序列。

A、前序遍历B、中序遍历C、后序遍历D、线索化正确答案：B8、S="A;/document/Mary.doc",则的字符定位的位置为().A、2B、3C、12D、11正确答案：B9、假设有60行70列的二维数组a[b∙∙60,1…70]以列序为主序顺序存储,其基地址为10000,每个元索占2个存储单元,那么第32行第58列的元素a[32,58]的存储地址为()。

(无第。

行第0列元素)A、16902B、16904C、14454D、答案A,B,C均不对正确答案：A10、具有36个结点的完全二叉树的深度为()。

专用考试纸 请勿浪费 第 1 页 共 4 页一、单项选择题（20分，每题2分）1.数据管理技术的发展经历了多个理阶段，其中数据独立性最高的是 （ A ）阶段。

A)数据库系统 B)文件系统 C)人工管理 D)数据项管理 2.（ B ）属于信息世界的模型，是现实世界到机器世界的一个中间层 次。

A)数据模型 B)概念模型 C)E-R 图 D)关系模型 3.层次模型不能直接表示实体间的（ C ）。

A)1﹕1关系 B)1：n 关系 C)m ﹕n 关系 D)1﹕1和1：n 关系 4. 关系模型中，候选码（ C ）。

A)可由多个任意属性组成 B)至多由一个属性组成C)可由一个或多个其值能唯一标识该关系模式中任何元组的属性组成 D)以上说法都不正确5. 设关系R 和S 的属性个数分别是3和4，元组个数分别是100和300，关系T 是R 和S 的广义笛卡尔积，则T 的属性个数和元组个数分别是（ D ）。

A)4，300 B)4，400 C)7，400 D)7，300006. 设关系R=(A ，B ，C)，与SQL 语句Select Distinct A From R Where B=17等价的关系代数表达式是（A ）。

A)ΠA (σB=17(R)) B)σB=17(ΠA (R)) C)σB=17(ΠA ，C (R)) D)ΠA ，C (σB=17(R))7．有关系模式 R （S ，T ，C ，D ，G ），根据语义有如下函数依赖集： F={(S ，C) →T ，C →D ，(S ，C)→G ，T →C}。

关系模式 R 的候选码（C ） 。

A)只有 1 个，为（S ，C ） B)只有 1 个，为（S ，T ）C)有 2 个，为（S ，C ）和（S ，T ） D)有 2 个，为（S ，C ）和（T ） 8．在数据库恢复时，对尚未做完的事务执行（ C ）处理。

A ）REDOB ）ABORTC ）UNDOD ）ROLLBACK9．数据库物理设计完成后，进入数据库实施阶段，下列各项中不属于实施阶段的工作是（ D ）。