当前位置:文档之家› 江西师大数据结构第01章_概论

江西师大数据结构第01章_概论

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语(P3) 1.数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2.数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2.数据元素是数据的基本单位 3.数据对象相同性质的数据元素的集合 4.数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. (1)数据的逻辑结构指数据元素之间固有的逻辑关系. (2)数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释:数据结构、二元组 2、根据数据元素之间关系的不同,数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型,它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i=0)个具有相同性质的数据元素a1,a2,a3……,an组成的有穷序列 //顺序表结构 #define MAXSIZE 100 typedef int DataType; Typedef struct{ DataType items[MAXSIZE]; Int length; }Sqlist,*LinkList; //初始化链表 void InitList(LinkList *L){ (*L)=(LinkList)malloc(sizeof(LNode)); if(!L){ cout<<”初始化失败!”; return;

《数据结构(c语言版)》知识点概括

数据结构知识点概括 第一章概论 数据就就是指能够被计算机识别、存储与加工处理得信息得载体。 数据元素就是数据得基本单位,可以由若干个数据项组成。数据项就是具有独立含义得最小标识单位。 数据结构得定义: ·逻辑结构:从逻辑结构上描述数据,独立于计算机.·线性结构:一对一关系。 ·线性结构:多对多关系。 ·存储结构:就是逻辑结构用计算机语言得实现。·顺序存储结构:如数组。 ·链式存储结构:如链表。 ·索引存储结构:·稠密索引:每个结点都有索引项。 ·稀疏索引:每组结点都有索引项. ·散列存储结构:如散列表。 ·数据运算。 ·对数据得操作。定义在逻辑结构上,每种逻辑结构都有一个运算集合。 ·常用得有:检索、插入、删除、更新、排序。 数据类型:就是一个值得集合以及在这些值上定义得一组操作得总称. ·结构类型:由用户借助于描述机制定义,就是导出类型。 抽象数据类型ADT:·就是抽象数据得组织与与之得操作。相当于在概念层上描述问题. ·优点就是将数据与操作封装在一起实现了信息隐藏. 程序设计得实质就是对实际问题选择一种好得数据结构,设计一个好得算法.算法取决于数据结构。 算法就是一个良定义得计算过程,以一个或多个值输入,并以一个或多个值输出.评价算法得好坏得因素:·算法就是正确得; ·执行算法得时间; ·执行算法得存储空间(主要就是辅助存储空间); ·算法易于理解、编码、调试。 时间复杂度:就是某个算法得时间耗费,它就是该算法所求解问题规模n得函数. 渐近时间复杂度:就是指当问题规模趋向无穷大时,该算法时间复杂度得数量级。 评价一个算法得时间性能时,主要标准就就是算法得渐近时间复杂度。 算法中语句得频度不仅与问题规模有关,还与输入实例中各元素得取值相关。 时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。 空间复杂度:就是某个算法得空间耗费,它就是该算法所求解问题规模n得函数。 算法得时间复杂度与空间复杂度合称算法复杂度。 第二章线性表 线性表就是由n≥0个数据元素组成得有限序列. n=0就是空表;非空表,只能有一个开始结点,有且只能有一个终端结点。 线性表上定义得基本运算: ·构造空表:Initlist(L) ·求表长:Listlength(L) ·取结点:GetNode(L,i) ·查找:LocateNode(L,x) ·插入:InsertList(L,x,i) ·删除:Delete(L,i) 顺序表就是按线性表得逻辑结构次序依次存放在一组地址连续得存储单元中。在存储单元中得各元素得物理位置与 逻辑结构中各结点相邻关系就是一致得。地址计算:LOCa(i)=LOCa(1)+(i-1)*d;(首地址为1) 在顺序表中实现得基本运算: ·插入:平均移动结点次数为n/2;平均时间复杂度均为O(n)。 ·删除:平均移动结点次数为(n-1)/2;平均时间复杂度均为O(n)。 线性表得链式存储结构中结点得逻辑次序与物理次序不一定相同,为了能正确表示结点间得逻辑关系,在存储每个结点值得同时,还存储了其后继结点得地址信息(即指针或链)。这两部分信息组成链表中得结点结构。 一个单链表由头指针得名字来命名。 单链表运算: ·建立单链表·头插法:s—〉next=head;head=s;生成得顺序与输入顺序相反。平均时间复杂度均为O(n)。 ·尾插法:head=rear=null;if(head=null)head=s;else r—>next=s;r=s; 平均时间复杂度均为O(n) ·加头结点得算法:对开始结点得操作无需特殊处理,统一了空表与非空表。 ·查找·按序号:与查找位置有关,平均时间复杂度均为O(n). ·按值:与输入实例有关,平均时间复杂度均为O(n)。 ·插入运算:p=GetNode(L,i-1);s—〉next=p—〉next;p->next=s;平均时间复杂度均为O(n)

数据结构第1章作业

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的()。 A.效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于() A.问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是(1),它必须具备(2)这三个特性。 (1) A.计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A.可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4.一个算法应该是()。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C. 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]对换;

第一章数据结构概论习题

第一章概论习题 一、选择题 1.数据结构是具有【B 】的数据元素的集合。 A.相同性质B.相互关系C.相同运算D.数据项2.在计算机的存储结构中,逻辑上相邻的结点存储在物理位置上也相邻的连续存储单元里,称之为【 B 】。 A.逻辑结构B.顺序存储结构C.链式存储结构D.散列存储结构3.语句for(i=1;i<=n;i++) x++;的时间复杂度为【B 】。 A.O(1) B.O(n) C.O(n2) D.O(n3) 4.下面不属于数据的存储结构的是【D 】。 A.散列存储B.链式存储C.索引存储D.压缩存储5.数据结构研究的是数据的【 A 】及它们之间的相互关系。 A.存储结构和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑6.下面程序段的时间复杂度是【D 】。 for(i=0;i<2*n;i++) for(j=1;j<3*n;j++) A[i][j]=0; A.O(n) B.O(5n) C.O(6n2) D.O(n2) 7.数据的逻辑结构有两大类,分别是【 B 】。 A.顺序存储结构和链式存储结构B.线性结构和非线性结构 C.压缩结构和非压缩结构D.有序结构和无序结构 8.以下与数据的存储结构无关的术语是【D 】。 A.循环队列B.链表C.哈希表D.栈 9.算法分析的两个主要方面是【A 】。 A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 10.下面程序段的时间复杂度是【D 】。 S=0; for(i=0;i

数据结构复习要点(整理版).docx

第一章数据结构概述 基本概念与术语 1.数据:数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序所处理的符号的总称。 2. 数据元素:数据元素是数据的基本单位,是数据这个集合中的个体,也称之为元素,结点,顶点记录。 (补充:一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 ) 3.数据对象:数据对象是具有相同性质的数据元素的集合,是数据的一个子集。(有时候也 叫做属性。) 4.数据结构:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 (1)数据的逻辑结构:数据的逻辑结构是指数据元素之间存在的固有逻辑关系,常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关,是独立于计算机的。 依据数据元素之间的关系,可以把数据的逻辑结构分成以下几种: 1. 集合:数据中的数据元素之间除了“同属于一个集合“的关系以外,没有其他关系。 2. 线性结构:结构中的数据元素之间存在“一对一“的关系。若结构为非空集合,则除了第一个元素之外,和最后一个元素之外,其他每个元素都只有一个直接前驱和一个直接后继。 3. 树形结构:结构中的数据元素之间存在“一对多“的关系。若数据为非空集,则除了第一个元素 (根)之外,其它每个数据元素都只有一个直接前驱,以及多个或零个直接后继。 4. 图状结构:结构中的数据元素存在“多对多”的关系。若结构为非空集,折每个数据可有多个(或零个)直接后继。 (2)数据的存储结构:数据元素及其关系在计算机内的表示称为数据的存储结构。想要计算机处理数据,就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构: 1. 顺序存储结构:把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中,借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 2. 链式存储结构:借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5. 时间复杂度分析:1.常量阶:算法的时间复杂度与问题规模n 无关系T(n)=O(1) 2. 线性阶:算法的时间复杂度与问题规模 n 成线性关系T(n)=O(n) 3. 平方阶和立方阶:一般为循环的嵌套,循环体最后条件为i++ 时间复杂度的大小比较: O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )

数据结构基础知识

数据结构基础知识 标准化文件发布号:(9312-EUATWW-MWUB-WUNN-INNUL-DQQTY-

复习提纲 第一章数据结构概述 基本概念与术语(P3) 1.数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2.数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2.数据元素是数据的基本单位 3.数据对象相同性质的数据元素的集合 4.数据结构三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. (1)数据的逻辑结构指数据元素之间固有的逻辑关系. (2)数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释:数据结构、二元组 2、根据数据元素之间关系的不同,数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型,它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i

数据结构练习题 第一章 概论

第一章概论 一、名词解释 1.数据表示 2.数据处理 3.数据 4.数据元素 5.逻辑关系 6.逻辑结构 7.结构 8.运算 9.基本运算 10.存储结构 11.顺序存储结构 12.链式存储结构 13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分 17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构 二、填空题 1.计算机专业人员必须完成的两项基本任务是:_数据表示__和__数据处理__。 2.数据在计算机存储器中的存在形式称为_机内表示_。 3.概括地说,数据结构课程的主要内容包括: 数据的_逻辑结构__、定义在_逻辑结构上的基本运算__、数据的_存储结构和运算__的实现。此外,该课程还要考虑各种结构和实现方法的_评价和选择_。 4.由一种_逻辑性_结构和一组_基本运算_构成的整体是实际问题的一种数学模型,这种数学模型的建立、选择和实现是数据结构的核心问题。 5.存储结构是逻辑结构的_存储_实现。 6.数据表示任务是逐步完成的,即数据表示形式的变化过程是_机外表示_->_逻辑结构_->_存储结构__。 7.数据处理任务也是逐步完成的,即转化过程是_处理要求_->_基本运算和运算_->_算法。 8.从数据结构的观点看,通常所说的"数据"应分成三个不同的层次,即_数据_、_数据元素_和_数据项_。 9.根据需要,数据元素又被称为_元素_、_结点_、_顶点_或_记录_。 10.在有些场合下,数据项又称为_字段_或_域_,它是数据的不可分割的最小标识单位。 11.从某种意义上说,数据、数据元素和数据项实际反映了数据组织的三个层次,数据 可由若干个_数据元素_构成,数据元素可由若干个_数据项_构成。 12.根据数据元素之间关系的不同特性,通常有_集合_、_线性结构_、_树形结构__、_图状结构_四类基本逻辑结构,它们反映了四类基本的数据组织形式。 13.根据操作的效果,可将运算分成以下两种基本类型: ①__加工_型运算,其操作改变了原逻辑结构的“值”,如结点个数、某些结点的内容等; ②__引用_型运算,其操作不改变原逻辑结构,只从中提取某些信息作为运算的结果。 14.将以某种逻辑结构S为操作对象的运算称为“_定义在S上的运算_”,简称“_S上运算_”。 15.一般地,可能存在同一逻辑结构S上的两个运算A和B,A的实现需要或可以利用B,而B 的实现不需要利用A。在这种情况下,称A可以“_归纳_”为B。 16.存储实现的基本目标是建立数据的_机内表示_。 17.一般地,一个存储结构包括_存储结点__、_数据元素之间关联方式的表示_、_附加设施_三个主要部分。 18.通常,存储结点之间可以有_顺序存储方式_、_链式存储方式_、_索引存储方式_、_散列存储方式_四种关联方式,称为四种基本存储方式。 19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑 结构S中数据元素之间的逻辑关系。由此得到的存储结构,称为_给定逻辑结构S的存储实现__或_存储映象_。 20.一个运算的实现是指一个完成该运算功能的_程序_。运算实现的核心是处 理步骤的规定,即_算法设计_。 21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同,可将算法分 为:__运行终止的程序可执行部分_、_伪语言算法_、_非形式算法_三类。

数据结构C语言版第1章练习题

第一章概论练习题 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。 2. 数据结构被形式地定义为(D, R),其中D是的有限集合,R是D上的有限集合。 3. 数据结构包括数据的、数据的和数据的这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类,它们分别是和。 5. 线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。 6.在线性结构中,第一个结点前驱结点,其余每个结点有且只有 1个前驱结点;最后一个结点后续结点,其余每个结点有且只有1个后续结点。 7. 在树形结构中,树根结点没有结点,其余每个结点有且只有个前驱结点;叶子结点没有结点,其余每个结点的后续结点数可以。 8. 在图形结构中,每个结点的前驱结点数和后续结点数可以。 9.数据的存储结构可用四种基本的存储方法表示,它们分别是。 10. 数据的运算最常用的有5种,它们分别是。 11. 一个算法的效率可分为效率和效率。 二、单项选择题 ()1. 非线性结构是数据元素之间存在一种: A)一对多关系 B)多对多关系 C)多对一关系 D)一对一关系 ()2. 数据结构中,与所使用的计算机无关的是数据的结构; A) 存储 B) 物理 C) 逻辑 D) 物理和存储 ()3. 算法分析的目的是: A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性 ()4. 算法分析的两个主要方面是: A) 空间复杂性和时间复杂性 B) 正确性和简明性 C) 可读性和文档性 D) 数据复杂性和程序复杂性 ()5. 计算机算法指的是: A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法 ()6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性 三、简答题 1.数据结构和数据类型两个概念之间有区别吗? 2. 简述线性结构与非线性结构的不同点。

智慧树全套答案计算机文化基础江西师范大学版课后作业答案.docx

智慧树全套答案计算机文化基础江西师范 大学版课后作业答案 问:目前显微断口的分析工作大都是用()来完成的。 答:表面形貌衬度 问:企业分层管理中的人数是有价值和绩效产生的人。() 答:错误 问:扫描电镜中的透镜有些是聚光镜,有些是成像物镜。 答:错 问:9. 建筑施工企业安全生产管理工作中,()是清除隐患、防止事故、改善劳动条件的重要手段。 答:安全检查制度 问:扫描电镜不用电磁透镜放大成像,也不用电子束成像,而是利用电子束在样品表面扫描时激发出来的各种物理信号来调制成像。 答:对 问:流的传递方式是 答:串行的 问:阿里巴巴的企业宗旨是(): 答:为中小企业服务 问:基于横、纵坐标的曲线作图来源于()。

答:D 问:欧洲经济共同体是1958年1月1日成立的。 答:对 问:《公孙九娘》是一个喜剧故事 答:错误 问:海流发电站主要是利用的海流的动能。 答:对 问:关于人工流产的正确答案是: 答:在孕后10周内做人工流产一般是吸宫术或刮宫术两次体温在37摄氏度以上者暂缓做流产手术 问:在下列的软件中:①WPS Office 2003;②Windows 2000;③UNIX;④Auto CAD; ⑤Oracle;⑥Photoshop;⑦Linux。属于应用 答:D 问:波斯波利斯的皇宫从大流士一世建到大流士()世。 答:三 问:社会主义市场经济的正式确认在中国共产党的第几次代表大会上?() 答:B 问:医学伦理学是医学与伦理学相互交叉的边缘学科。 答:对 问:流行病学的研究对象是 答:人群 问:医学是医学技术与医学人文的结合。 答:对

问:1.下列药用植物学中以叶入药的有()。 答:艾 菘蓝 枇杷 罗布麻 紫苏 问:已知X服从均数为μ,标准差为σ的正态分布,则P(X≥1.645)为: 答:5% 问:有哪两种缝纽扣的方法? 答:平行缝十字缝 问:中国政府有哪些营养体统?() 答:监督系统信息传输系统 问:个体户减少的原因有哪些?() 答:市容工作的干扰超市连锁店的冲击 问:心痛三项化验检查包括 答:肌红蛋白肌钙蛋白肌酸激酶同工酶 问:抽象形象没有具体的形象表现,追求块与面的传达。() 答:对

数据结构第一章

8576 顺序线性表的基本操作 时间限制:1000MS 内存限制:1000K 提交次数:1714 通过次数:300 题型: 编程题语言: 无限制 Description 编写算法,创建初始化容量为LIST_INIT_SIZE的顺序表T,并实现插入、删除、遍历操作。本题目给出部分代码,请补全内容。 #include #include #define OK 1 #define ERROR 0 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemTypeint typedefstruct { int *elem; int length; intlistsize; }SqList; intInitList_Sq(SqList&L) { // 算法2.3,构造一个空的线性表L,该线性表预定义大小为LIST_INIT_SIZE // 请补全代码 } intLoad_Sq(SqList&L) { // 输出顺序表中的所有元素 inti; if(_________________________) printf("The List is empty!"); // 请填空 else { printf("The List is: ");

for(_________________________) printf("%d ",_________________________); // 请填空 } printf("\n"); return OK; } intListInsert_Sq(SqList&L,inti,int e) { // 算法2.4,在顺序线性表L中第i个位置之前插入新的元素e // i的合法值为1≤i≤L.length +1 // 请补全代码 } intListDelete_Sq(SqList&L,inti, int&e) { // 算法2.5,在顺序线性表L中删除第i个位置的元素,并用e返回其值 // i的合法值为1≤i≤L.length // 请补全代码 } int main() { SqList T; int a, i; ElemType e, x; if(_________________________) // 判断顺序表是否创建成功 { printf("A Sequence List Has Created.\n"); } while(1) { printf("1:Insert element\n2:Delete element\n3:Load all elements\n0:Exit\nPlease choose:\n"); scanf("%d",&a); switch(a) { case 1: scanf("%d%d",&i,&x); if(_________________________) printf("Insert Error!\n"); // 判断i值是否合法,请填空 elseprintf("The Element %d is Successfully Inserted!\n", x);

数据结构第一章 概述习题↓

第一章绪论 1、简述下列术语:数据、数据元素、数据对象、数据结构、数据存储、存储结构、数据类型和抽象数据类型。 2、数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么? 3、什么是算法? 算法的5个特性是什么? 试根据这些特性解释算法与程序的区别。 4、什么叫算法的时间复杂度?怎样表示算法的时间复杂度? 5、两个数据结构的逻辑结构和存储结构都相同,但是它们的运算集合中有一个运算的定义不一样,它们是否可以认作是同一个数据结构?为什么? 6、试画出与下列程序段等价的框图 (1)product = 1; i = 1; while(i <= n){ product * = i ; i++; } (2)i = 0; do{ i++; }while ((i!=n)&&(a[i])!=x); 7、已知如下程序段 for(i=n;n>=1;n--) {语句1} { x++; {语句2} for(j=n;j<=i;j--)FOR j:=n {语句3} y++; {语句4} }; 求语句1到语句4的频度。 8、按增长率从小到大的顺序排列下列各组函数:

2100,(3/2)n,(2/3)n,(4/3)n,n,n3/2,n2/3,n!,n n,log2n,n/log2n,log2(log2n),n log2n 9、试写一算法,自大至小依次顺序读入的三个整数X,Y,Z的值。 10、假设有A,B,C,D,E五个高等院校进行田径对抗赛,各院校的单项成绩均已存入计算机,并构成一张表,表中每行的形式为: 项目名称性别校名成绩得分 编写算法,处理上述表格,以统计各院校的男、女总分和团体总分,并输出。 11、设求解同一个问题有三种算法,三种算法各自的时间复杂度分别为O(n2),O(2n)和O(nlg n),哪种算法最可取?为什么? 12、设n为已在算法前边定义的整数类型,并已知n为正整数,分析下列各算法中语句的执行次数,并给出各算法的时间复杂度T(n)。 (1) int i = 1, k = 0; while (i < n-1) { k = k + 10 * i; i = i + 1; } (2) int i = 1, k = 0; do { k = k + 10 * i; i = i + 1; }while (i != n); (3) int i = 1, j = 1; while (i <= n && j <= n) { i = i + 1; j = j + 1; } (4) int x = n; /* n > 1 */ int y = 0; while(x >= (y+1)*(y+1)) y++;

江西师范大学江西未来的另一个211(精)

江西师范大学 江西师范大学位于具有深厚历史文化底蕴、素有“物华天宝、人杰地灵”美誉的江西省会城市南昌,学校缘起于庐山白鹿洞书院,肇基于1940年创建的国立中正大学,1949年更名为国立南昌大学,1953年改为江西师范学院,1983年更名为江西师范大学,是江西省本科办学历史最为悠久的普通高等院校。2003年,江西金融职工大学(江西银行学校整建制并入。学校现有瑶湖、青山湖和共青城三个校区,占地面积4500余亩,建筑面积140余万平方米,馆藏纸质文献304余万册,电子图书100余万册。瑶湖校区不设围墙,四周以一条5公里长的瑶河环抱,具有突出的生态人文特色。 70年来,学校先后七次迁址,六易其名,四度调整,砥砺出“静思笃行、持中秉正”的校训,孕育了“严谨、勤奋、求是、创新”的优良校风,形成了“以人为本、面向社会”的办学思想和“以生为本、全面发展”的育人思想。新世纪以来,学校发扬“百折不挠、艰苦创业”的办学传统,坚持“质量立校、人才兴校、创新强校、文化铸校、和谐荣校”的办学理念,弘扬“爱国荣校、民主和谐、求真务实、开放创新”的师大精神,现已发展成为一所融文学、历史学、哲学、经济学、管理学、法学、理学、工学、教育学等九大学科门类于一体,师范与非师范并举,对江西的政治、经济、文化和社会发展有较大影响、被省政府确定为优先发展的省属重点师范大学。 学校是博士学位授予权单位和全国第一批学士、硕士学位授予权单位,设有23个专业学院,1个独立学院(科技学院,现有全日制本专科生4万余人,博士、硕士研究生4500余人,成人高等学历教育学生1万余人;有2个博士后流动站,1个博士后科研工作站、3个博士学位授权一级学科点、20个博士学位授权二级学科点、19个硕士学位授权一级学科点、124个硕士学位授权二级学科点、11个硕士专业学位授予点、68个本科专业;有2个教育部重点实验室,1个国家人文素质教育基地,6个省级重点实验室,2个省级工程技术研究中心,1个省级大学科技园,5个省级人文社会科学重点研究基地,3个江西省产学研合作示范培育基地,10个省级软件科学(高校工程、实验示范技术中心。

数据结构 第一章 概述习题

第一章概述习题 一、单选题 1、研究数据结构就是研究( D )。 A、数据的逻辑结构 B、数据的存储结构 C、数据的逻辑结构和存储结构 D、数据的逻辑结构、存储结构及其数据在运算上的实现 2、以下说法正确的是(C )。 A、数据元素是数据的最小单位 B、数据项是数据的基本单位 C、数据结构是带有结构的各数据项的集合 D、一些表面上很不相同的数据可以有相同的逻辑结构. 3、在数据结构中,数据的逻辑结构可以分成(C )。 A. 内部结构和外部结构 B. 紧凑结构和非紧揍结构 C. 线性结构和非线性结构 D. 动态结构和静态结构 4、数据元素及其关系在计算机存储器内的表示,称为数据的(D )。 A. 线性结构 B. 非线性结构 C. 逻辑结构 D. 存储结构 5、计算机算法必须具备输入、输出、( B )等5个特性。 A 可行性、可移植性和可扩展性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、安全性和稳定性 6、下面关于算法的叙述中错误的是( A )。 A. 一个算法应有一个或多个输入。 B. 算法最终必须由计算机程序实现 C. 为解决某问题的算法同为该问题编写的程序含义是相同的 D. 算法中的每条指令都必须有明确的含义 7、若一个算法的时间复杂度用T(n)表示,其中n的含义是(C )。 A. 循环层数 B. 语句条数 C. 问题规模 D. 函数数量 8、下面说法正确的是(A)。 A. 健壮的算法不会因非法的数据输入而出现莫名其妙的状态 B. 程序一定是算法 C. 算法的时间复杂度只依赖于问题的规模 D. 算法的优劣与算法描述语言无关,但与所用计算机有关 9、下面程序段的时间复杂性的数量级为(C ) for (i=1;i<=n;i++)

数据结构第一章

1.1 程序设计的实质是数据表示和数据处理。 1.2数据要能被计算机加工处理,首先必须能够存储在机器中,成为能被机器直接操作的对象。数据在计算机存储器中的这种存在形式称为机内表示。将数据从机外表示转化为机内表示,这项任务称为数据表示。 1.3用适当的可执行语句编制程序,以便让计算机去执行对数据机内表示的各种操作,从而实现处理要求,即得到所需的结果,这项工作称为数据处理。 1.4 软件工程学认为:软件系统的生存期可分为软件计划、需求分析、软件设计、软件编码、软件测试和软件维护等六个阶段。程序设计包括前五个阶段(程序设计包括数据表示和数据处理两个方面)。 1.5数据结构课程集中讨论以设计阶段为核心、同时涉及编码阶段和分析阶段的一个小范围内的若干基本问题。概括的说,其主要内容包括:数据的逻辑结构、定义在逻辑结构上的基本运算、数据的存储结构和运算的实现。其中,数据的逻辑结构是数据的组织形式,基本运算规定了数据的基本操作方式。由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型,这种数学模型的建立、选择和实现是数据结构的核心问题。 1.6 数据表示任务是逐步完成的,即数据表示形式的变化过程是:机外表示——》逻辑结构——》存储结构。 数据处理任务也是逐步完成的,即有转化过程:处理需求——》基本运算和运算——》算法。 数据表示与数据处理是密切相关的,数据处理方式总是与数据的相应的表示形式相联系,反之亦然。 2.1从数据结构的观点看,数据就分成三个不同的层次,即数据、数据元素和数据项。凡能被计算机存储、加工的对象通称为数据;数据元素是数据的基本单位,在程序中作为一个整体而加以考虑和处理,即数据元素被当作运算的基本单位,并且通常具有完整确定的实际意义,又被称为元素、结点、顶点或记录;数据元素又是数据项组成的,但数据项通常不具有完整确定的实际意义,或不当作一个整体对待,又称为字段或域,它是数据的不可分割的最小标识单位。 2.2从数据结构的观点看,重要的是数据元素之间的逻辑关系。所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。四类基本逻辑结构:集合、线性结构、树形结构和图状结构。1)逻辑结构与数据元素本身的形式、内容无关 2)逻辑结构与数据元素的相对的相对位置无关 3)逻辑结构与所含结点个数无关 2.3运算是指在任何逻辑结构上施加的操作,即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象,以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。根据操作的效果将运算分成两种基本类型: 1)加工型运算,其操作改变了原逻辑结构的“值” 2)引用型运算,其操作不改变原逻辑结构,只从中提取某些信息作为运算的结果 2.4假如A是S上的一些运算的集合,B是A的一个子集,使得A中每一运算都可以“归约”为B中一个或多个运算,而B中任一运算不可归约为别的运算,则称B中运算为(相对于A的)基本运算。 2.5对某些逻辑结构S和在S上的基本运算集B,由S和B构成的整体(S,B)往往在大量不同种类的实际问题的求解中反复出现,在此将这样的整体称为一个“数据结构”;线性表、队列、栈等都是数据结构,这三个数据结构有相同的逻辑结构但有不同的基本运算集。 3.1存储实现的基本目标是建立数据的机内表示,存储实现建立的机内表示应遵循选定的逻

第1章数据结构概论自测题及答案

第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为(D, R),其中D是数据元素的有限集合,R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类,它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 6.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有1个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有1个后续结点。 7. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有1个前驱结点;叶子结点没有后续结点,其余每个结点的后续结点数可以任意多个。 8. 在图形结构中,每个结点的前驱结点数和后续结点数可以任意多个。 9.数据的存储结构可用四种基本的存储方法表示,它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种,它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 二、单项选择题 (B)1. 非线性结构是数据元素之间存在一种: A)一对多关系B)多对多关系C)多对一关系D)一对一关系 ( C )2. 数据结构中,与所使用的计算机无关的是数据的结构; A) 存储B) 物理C) 逻辑D) 物理和存储 (C)3. 算法分析的目的是: A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 (A)4. 算法分析的两个主要方面是: A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 ( C )5. 计算机算法指的是: A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 (B)6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性

江西师范大学软件工程领域工程硕士培养方案-江西师范大学计算机

专业型硕士(工程硕士·软件工程领域)培养方案 一、培养目标 面向软件行业及相关工程部门,培养基础扎实、素质全面、工程实践能力强并具有一定创新能力的应用型、复合型高层次工程技术和软件工程管理人才。具体要求为: (一)拥护党的基本路线和方针政策,热爱祖国,遵纪守法,具有良好的职业道德和敬业精神,具有科学严谨和求真务实的学习态度和工作作风,身心健康。 (二)掌握软件工程领域坚实的基础理论和宽广的专业知识,具有独立从事软件分析、设计、开发、维护等工作的能力以及工程项目的组织与管理能力,了解软件工程领域的技术现状和发展趋势,能够运用先进方法和现代化技术手段解决软件工程问题。 (三)掌握一门外国语,具备良好的阅读、理解和撰写外语资料的能力和进行国际化交流的能力。 二、招生对象 一般为具有国民教育序列大学本科学历(或本科同等学力)人员,具体报考条件以学校正式颁发的招生简章为准。 三、学习方式及年限 采用全日制学习方式,学习年限一般为3年,最长不超过5年。优秀

研究生可申请提前毕业。 四、主要研究方向 软件项目管理、智能信息处理、互联网应用软件、电子商务与电子政务、数据挖掘及应用、农村信息化工程、嵌入式软件、智能教育软件、信息管理与信息系统等。 五、课程设置及教学计划 工程硕士采用课程学习、工程实践和学位论文相结合的培养方式。课程设置应体现厚基础理论、重实际应用、博前沿知识的原则,以实际应用为导向,以职业需求为目标,以综合素养和应用知识与能力的提高为核心,并与软件工程领域任职资格认证紧密衔接。课程设置分为通识课程、专业基础和专业课、专业选修课程和工程实践等4个模块。课程学习实行学分制,总学分不低于41学分。 (一)通识课程(11学分) 1、英语(4学分) 2、自然辩证法(2学分) 3、知识产权(1学分) 4、信息检索(1学分) 5、工程数学(3学分) (二)专业基础与专业课程(10学分) 1、高级软件工程(2学分) 2、现代数据库技术(2学分)

数据结构第1章习题解答..

第1章习题解答 1.1什么是数据结构?一个数据结构结构的二元组定义形式是什么样的?举例解释其含义。 [解答] 概括地说,数据结构是互相有关联的数据元素的集合。也就是说,数据结构是由某个数据元素的集合和该集合中的数据元素之间的关系组成的,因此数据结构可以用一个二元组来表示。例如,B=(D,R),其中D是某一数据元素的集合,R是D上的关系的有限集。R所表示的是集合D的数据元素之间的逻辑关系,它表示的可能是数据元素之间客观存在的某种联系,也可能是为了处理问题的需要而人为组织的数据元素之间的某种关系,因此,称之为数据的逻辑结构。例如,一个农历节气表,就构成了一个数据结构,其数据元素是一年的农历二十四节气,数据元素之间的关系是节气的时间先后关系。又如,一个某年级学生的成绩排序表,也是一个数据结构,其数据元素是包含成绩项的该年级的学生记录,数据元素之间的关系是学生之间的成绩高低关系。为了在计算机中进行数据处理,必须把从实际问题中抽象出来的数据的逻辑结构映象到计算机的存储器中,即要把抽象出来的数据元素集合D 和数据元素之间的关系存储到计算机的存储器中,称之为数据的物理结构或存储结构,它是数据的逻辑结构在计算机中的表示。 1.2假设R是集合M上的一个关系,R的定义是什么?对实际问题而言,其含义是什么? [解答] 如果R是对集合M自身的笛卡尔积所取的一个子集,那么我们就说“R是集合M上的一个关系”。对实际问题而言,它表示的是集合M中元素的某种相关性。例如,对于参加一个羽毛球比赛的运动员集合,可以用一个二元关系表示出各场比赛的胜负关系。对于一组课程的集合,可以用一个二元关系表示出各门课程之间的先修和后续关系等等。 1.3设有集合M={d1,d2,d3,d4,d5}上的一个关 R={(d1,d2),(d2,d4),(d4,d5),(d2,d5),(d1,d4),(d1,d5),(d3,d5),(d1,d3)},试说明关系R具有什么样的性质。 [解答] 从二元关系的基本性质容易验证,该关系R是反自反的、反对称的、传递的关系。 因为关系R中没有(d i,d i)这样的元素,所以它是反自反的。 因为关系R中没有(元素d i,d j)和(d j,d i)同时存在的情况,所以它是反对称的。 关系R 的传递性表现在: 有元素(d1,d2),(d2,d4),同时有元素(d1,d4), 有元素(d1,d2),(d2,d5),同时有元素(d1,d5), 有元素(d1,d3),(d3,d5),同时有元素(d1,d5), 有元素(d1,d4),(d4,d5),同时有元素(d1,d5), 有元素(d2,d4),(d4,d5),同时有元素(d2,d5)。 1.4什么是线性结构?什么是非线性结构?举例说明。 [解答]

相关主题
文本预览
相关文档 最新文档