第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 2. 算法的时间复杂度取决于（） 3.计算机算法指的是（），它必须具备（）这三个特性。 4．一个算法应该是（）。 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 13．以下哪个数据结构不是多型数据类型（） A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 15. 下列数据中，（）是非线性数据结构。 A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题
数据结构试卷 一、单项选择题（本大题 共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1 . 下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C. 链队列 D.栈 2 . 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3 . 已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear 指向 队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4 . 递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C. 队列 D. 线性表 5 . 设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）A.求子串 B.串联接 C.串匹配D.求串长 6 . 对于广义表A，若head(A)等于tail(A)，则表A为（） A.() B.(()) C.((),()) D.((),(), ()) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一 定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度 为l的结点个数是3，度为2 的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3 个程序段，第一程序段的执行次数为错误！未找到引用源。，第二个程序段执 行次数为4n，第三个程序段的执行次数 为0.06错误！未找到引用源。，则该算法的时间复 杂度为（）。 A．O（n）B ．O（错误！未找到引用源。） C ．O（错误！未找到引用源。）D．O （错误！未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={
第二题：电梯模拟 1、需求分析： 模拟某校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为地下层、第一层、第二层、……第八层，其中第一层是大楼的进出层，即是电梯的“本垒层”，电梯“空闲”时，将来到该层候命。 乘客可随机地进出于任何层。对每个人来说，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。 模拟时钟从0开始，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位（简记为t），比如：有人进出时，电梯每隔40t测试一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；如果电梯在某层静止时间超过300t，则驶回1层侯命。 而题目的最终要求输出时： 按时序显示系统状态的变化过程，即发生的全部人和电梯的动作序列。 2、设计 2．1设计思想： （1）数据结构设计 本题中的电梯的变化，是一个动态变化的过程，要在动态过程中实现 正常跳转，首先要确定各种跳转的状态，因而这里我使用枚举类型来 表示电梯的各种状态的： enum {up,down,stop,home}State(home); 同时初始化最初状态为电梯在本垒层。而在电梯的运行过程中对于乘 客来说，显然有一个进入电梯与出电梯的队列，因而在这里我是用的 链表来实现这个过程的，同时用结构体来保存该乘客的信息： typedef struct passage { int now;//乘客当前所在的位置 int dis;//乘客的目地地 int wait;//最长的等待的时间 int waitnow;//已经等待的时间 struct passage *next; }Passage; 虽然电梯中的状态是由枚举类型来实现的，但是在整个程序的运行过 程中，我还是为电梯设置了一个结构体类型，以便保存更多的信息： typedef struct lift { int count_C;//计数电梯已到达的层数 int count_A;//系统的总时间计数器记得必须初始化为0 int flag_in[High];//九个楼层有无请求的标志哪个楼层如果有请 求该标志置1 int num;//等待队列中的人数记得要进行初始化为0 int people;//电梯中人数
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 一.填空题 1. _集合__、线性结构、__树形结构____ 、图形结构 2.p->next!=NULL 3.时间复杂度和空间复杂度 4.随机存取 5..队尾 6. n-1 二、单选题、 1-5DAACC 6-10DBDDB 11-15DCABD 三，简答题 1、 2、数据是对客观事物的描述形式和编码形式的统称，是算法和程序的处理对象和计算结构。数据元素又称数据结点，简称结点，通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。多数情况下，一个结点包含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识结点的域称为关键字域。 算法：有穷规则的集合，而规则规定了解决某一特定问题的运算序列。 有穷性：必须在执行有穷步后终止。 确定性：每一步必须具有确定的定义，不能含糊不清，不带二义性。 可行性：所有运算都可以精确地实现。 输出数据：必须有输出数据，包括输出某种动作或控制信号。 输入数据：作为执行前的初始量。不是必须。 算法有两种表现形式：描述形式和程序形式。 计算时间复杂的的方法： ?支配性语句度量法：在一段程序中，往往有一条语句执行次数最多，话费时间也就是最多，其他语句执行次数的和将不超过这套语句执行次数的常数倍，那么就称这条语句在话费时间上是起支配性作用的典型语句，于是可选这条语句的执行次数作为度量这段程序花费时间的阶。 ? 四、应用题 1、 2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点， 它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的 升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这 两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL WPL=∑Wi*Li (i=1到n) WPL=(2+4)*3+(6+8+10)*2 =66 第一章 1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。 2、数据结构的形式定义：二元组Data_Structure=(D,S) 其中，D 是数据元素的有限集，S 是D 上关系的有限集。 3、数据元素之间关系的映像：１、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。 2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。 任何一个算法的设计取决于数据(逻辑)结构，其实现取决于物理结构。 4、 算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特性：有穷性、确定性、可行性、输入、输出 5、 算法的评价——衡量算法优劣的标准 正确性(correctness):满足具体问题的需求 可读性(readability)：易读、易理解 健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理 效率与低存储量:执行时间短、存储空间小 作业的答案：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 第二章 1、线性表是一种最简单的线性结构。 线性结构 是一个数据元素的有序（次序）关系 特点：存在唯一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继 2、线性表类型的实现——顺序映像 定义：用一组地址连续的存储单元依次存放线性表中的数据元素。 ? 以“存储位置相邻”表示有序对 淮海工学院计算机工程学院实验报告书 课程名：数据结构 题目：线性数据实验 班级：G计算机141 学号：2014150230 姓名：韩坚 一、目的与要求 1）掌握线性表的顺序存储结构和链式存储结构； 2）熟练掌握顺序表和链表基本算法的实现； 3）掌握利用线性表数据结构解决实际问题的方法和基本技巧； 4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）； 5）按时提交实验报告。 实验环境 计算机、C语言程序设计环境 实验学时 2学时，必做实验。 二、实验内容或题目 一、顺序表的基本操作实现实验 要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）： 1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内； 2）打印（遍历）该线性表（依次打印出表中元素值）； 3）在线性表中查找第i个元素，并返回其值； 4）在线性表中第i个元素之前插入一已知元素； 5）在线性表中删除第i个元素； 6）求线性表中所有元素值（整数）之和； 二、链表（带头结点）基本操作实验 要求：数据元素类型ElemType取字符型char。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）： 1）创建任意字符型有序（递增排序）单循环链表（即链表的字符元素随机在键盘上输入），长度限定在15之内； 2）打印（遍历）该链表（依次打印出表中元素值）； 3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE； 4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE； 5）在链表中按照有序方式插入一已知字符元素； 6）在线性表中删除第i个结点； 7）计算链表的长度。 三、实验步骤与源程序 一、顺序表的源程序 #include "stdafx.h" #include "stdio.h" 银行自动取款系统 一、目的 根据所学知识，编写指定题目的C语言程序，并规范地完成课程设计报告。通过课程设计，加深对《C语言程序设计》课程所学知识的理解，熟练掌握和巩固C语言的基本知识和语法规范，包括：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；库函数应用（时间函数、绘图函数以及文件的读写操作函数等）；复杂任务功能分解方法（自顶向下逐步求精、模块化设计、信息隐藏等）。 学会编制结构清晰、风格良好、数据结构适当的C语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。 二需求分析 根据任务书里的“课程设计的基本要求”及给定的“课程设计的主要内容”。编写的银行自动提款模拟系统由使用者担当银行卡使用者自行输入卡号模拟银行卡使用系统进行各项操作，该系统有简便、稳定等特点。 该系统开始时有使用者自行初始化各项数据，包括卡的数量，一天内可操作次数上相及“银行卡”的卡号和余额，使用者可根据不同情况对系统的各项内容进行初始化，方便、快捷。 当使用者输入错误数据及操作次数达到上限时系统会自动退出或者给出相应的恢复提示使用者重新操作，直到输入正确，系统不会出现异常、突然崩溃，稳定。 1、所实现的功能： ①.系统能够让使用者自行输入卡的数量及每天操作次数上限，然后初始化卡的卡号和卡上所拥有的余额； ②.初始化信息后，可以开始使用系统进行存取款，输入卡号，如果卡号为负责退出程序、卡号不存在则提示重新输入直到输入正确为止，如果此卡的操作次数已达上限则同样退出程序； ③.输入正确后可以输入想要存取款数目，当数目为正是存款，负数为取款； ④.正确存取款后，系统会自行输出操作、卡上余额和剩下操作次数到屏幕，然后返回选择菜单，使用者可以再进行选择进行操作。 2、测试预测 ①.进行测试，每个编写的函数逐个进行调试直到都能够正常运行； ②.在进行存取款操作都，所对应卡的操作次数应加一，余额能够进行相应的改变； ③.程序的各项运作结果与预想的与一样。 三概要设计 程序的主要功能函数包括如下几个部分： 习题练习第一章绪论 1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]) { int j,k,r; int x; for(r=0;r<=n;r++) 1) n+2 { for (j=0;j<=n;j++) 2) (n+1)*(n+2) { x=0; 3) (n+1)2 for(k=1；k<=n;k++) 4) (n+1)3 x+=a[r][k]*[k][j]; 5) n* (n+1)2 c[r][j]=x; 6) (n+1)2 } } } 计算时间每条语句的频度和该算法的时间复杂度 2．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 4．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1 （2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 6．连续存储设计时，存储单元的地址（ A ）。【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 7. 数据元素是数据的最小单位。( F ) 【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】 第二章线性表 1．线性表是具有n个（ C ）的有限序列（n>0）。【清华大学 1998 一、 4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信 息项 班级：：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验容 定义一个包含学生信息（学号，，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表 L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; 班级：姓名：学号： 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义； 2、掌握线性表的基本操作，如建立、查找、插入和删除等。 二、实验内容 定义一个包含学生信息（学号，姓名，成绩）的顺序表和链表（二选一），使其具有如下功能： (1) 根据指定学生个数，逐个输入学生信息； (2) 逐个显示学生表中所有学生的相关信息； (3) 根据姓名进行查找，返回此学生的学号和成绩； (4) 根据指定的位置可返回相应的学生信息（学号，姓名，成绩）； (5) 给定一个学生信息，插入到表中指定的位置； (6) 删除指定位置的学生记录； (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include typedef int Status; // 定义函数返回值类型 typedef struct { char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 1.1 请说明算法具有哪些特性，各是什么含义？ 算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束. 1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类 型和抽象数据类型。 数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。是数据的一个子集。数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。抽象数据类型（abstract data type，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。1.3设n为正整数。试确定下列各程序段中前置以记号@的语句频度： (1) x=n; y=0; //n为不小于1的常数 while (x>=(y+1)*(y+1)) { @ y++; } n1/2向下取整 (2) i=1; j=0; while (i+j<=n) { @ if (i>j) j++; else i++; } n 注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。 1.4请说明下列算法的时间复杂度。 (1) void sf1 (int n) { int i, x=0; for(i=1; i xxx 实验报告 一、实验目的 1.熟悉上机环境，进一步掌握语言的结构特点。 2.掌握线性表的顺序存储结构的定义及实现。 3.掌握线性表的链式存储结构——单链表的定义及实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i 个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、程序主要语句及作用 1)程序1的主要代码(附简要注释) #include en>=MAXSIZE) { printf("the list is overflow\n"); return ERROR; } else if((i<1)||(i>(*L).len+1)) { printf("position is not corrent.\n"); return ERROR; } else{ for(j=(*L).len-1;j>=i-1;j--) ec[j+1]=(*L).vec[j]; ec[i]=x; len++; 部分的时间都用在了编程上，主要是因为C语言掌握的问题，C语言基础不好特别是对于C语言中链表的一些定义和基本操作不够熟练，导致在编程过程中还要不断的拿着c语言的教材查找，所以今后还要对C语言多练习，多动手，多思考。 2.数据结构有很强的逻辑性，因此我认为如果在上机之前先把逻辑搞清楚很重要，不管是对算法的设计还是对程序的调试都有很大帮助。 3.经过一次上机实践，我认为实践课很重要，上理论课只是纸上谈兵，只是被动地接受，而实践课上能将学过的知识利用起来，同时还有一些东西只能是自己上机实践才能慢慢探索出的。 所以我在做试验的时候特别费劲，特别吃力，这也是事出有因的。通过自我反省，总结不足之处后，我还是脚踏实地去查找资料，包括请教老师，上网搜索数据库线性表操作的优秀代码，经过不断的验证，修改和深入的研究，最终使得自己的程序得以运行，实现了实验的最终目的和要求。 Problem A : Hardwood Species From:POJ, 2418 Description Hardwoods are the botanical group of trees that have broad leaves, produce a fruit or nut, and generally go dormant in the winter. America's temperate climates produce forests with hundreds of hardwood species -- trees that share certain biological characteristics. Although oak, maple and cherry all are types of hardwood trees, for example, they are different species. Together, all the hardwood species represent 40 percent of the trees in the United States. On the other hand, softwoods, or conifers, from the Latin word meaning "cone-bearing," have needles. Widely available US softwoods include cedar, fir, hemlock, pine, redwood, spruce and cypress. In a home, the softwoods are used primarily as structural lumber such as 2x4s and 2x6s, with some limited decorative applications. Using satellite imaging technology, the Department of Natural Resources has compiled an inventory of every tree standing on a particular day. You are to compute the total fraction of the tree population represented by each species. Input Input to your program consists of a list of the species of every tree observed by the satellite; one tree per line. No species name exceeds 30 characters. There are no more than 10,000 species and no more than 1,000,000 trees. Output Print the name of each species represented in the population, in alphabetical order, followed by the percentage of the population it represents, to 4 decimal places. Sample Input Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood 一、简答题 1、链表：链表就是一串存储数据的链式结构。链式的优点在于，每个数据之间都是相 关联的。 2、线性结构： 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。 3、树与二叉树 二叉树是每个结点最多有两个子树的有序树； 树是由n（n>=1）个有限节点组成一个具有层次关系的集合。 树和二叉树的2个主要差别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。 4、堆 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 5、二叉排序树 二叉排序数的（递归）定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。 二、应用题 1、树与二叉树 ①前中后序遍历序列 一、已知前序、中序遍历，求后序遍历 例：前序遍历: GDAFEMHZ中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。 同理，遍历的右子树的第一个节点就是右子树的根节点。 ②树与二叉树的转换 树转换为二叉树： 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。 （3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。 （9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。（14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n）。（19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。数据结构实验报告及心得体会
数据结构(1)
数据结构期末复习资料[1]
数据结构实验1报告 G计算机141-韩坚
数据结构分析报告
数据结构1
数据结构实验一实验报告
数据结构实验一 实验报告
十套数据结构试题及答案[1-5] (1)
数据结构1
《数据结构》实验报告1
专题一 数据结构
数据结构复习资料(亲自整理)
数据结构单元1练习参考答案
相关主题
文本预览