《数据结构》课程标准 英文名称：DataStructure 学分： 4 适用专业：嵌入式系统工程 一、课程性质 《数据结构》是嵌入式系统工程专业的一门专业基础必修课程。本课程面向Android软件工程师的岗位需求，针对JDK1.6，主要讲述集合、线性表、堆栈和队列、树和二叉树、查找和排序等基本数据结构和算法。本课程着重基本知识的掌握和基本技能的训练，为利用Java语言进一步开发基于Android的APP应用奠定基础。 二、课程理念 数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。精心选择的数据结构可以带来更高的运行或存储效率，数据结构往往同高兴的检索算法和索引技术有关。 将CDIO理念应用在数据结构课程中。CDIO是近年来国际工程教育改革的最新成果。CDIO代表构思（Conceive）、设计（Design）、实现（Implement）和运作（Operate），它以产品研发到产品运行的生命周期为载体，让学生以主动的、实践的、课程之间有机联系的方式学习工程。 1、课程地位理念 在许多类型的程序设计中，数据结构的选择是一个基本的设计考虑因素。许多大型的构造经验表明，系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了最优的数据结构。许多时候，确定了数据结构后，算法就容易得到了。有些时候事情也会反过来，我们根据特定算法来选择数据结构与之适应。不论哪种情况，选择合适的数据结构都是非常重要的。选择了数据结构，算法随之确定，是数据而不是算法是系统构造的关键因素。 2、课程学情理念 本课程开设在嵌入式系统工程专科第一学期，学生在学习本课程前已具备计算机基础、java基础等知识，本课程力图让学生学会在java语言环境下，运用面向对象的思想编写规范的代码，实现经典的数据结构和算法。熟悉常用的数据结构和算法，使学生初步具备一个优秀的软件开发人员所应有的基本能力。 3、课程内容理念 根据本课程的教学目标，确定了课程内容体系结构的五个组成部分：集合结构、线性表、堆栈和队列、树和二叉树、查找和排序。内容主要包括：绪论、集合结构的线性存储实现方法、集合结构的链式存储实现方法、线性表、有序线性表、堆栈、队列、树、二叉树、二叉树的遍历、顺序查找、折半查找、插入排序、选择排序等。 4、课程要求理念 《数据结构》是一门偏重理论的课程，有很强的理论性。在多年的教学研究和教学实践中，《数据结构》形成了独具特色的“七化”教学方法，即教学资源立体化、教师精讲主导化、学生学习团队化、教学过程流水化、程序项目核心化、知识技能点索引化、和java语言结合化。 5、课程考核理念 如何客观反映出学生对数据结构的理解、掌握、综合应用的实际情况，传统的闭卷考试有不完善的地方，应该对考核内容和形式进行适当的调整，过程评价与终结评价相结合，形成全方位、更加公正客观的评价体系。考核方法采用“N+2”成绩评定方式，采用“课堂考勤＋课堂笔记＋期末考试”的方式。 三、课程目标 （一）总目标
第一章作业 一、选择题 1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的 这种关系称为( )。 A. 规则 B. 结构 C. 集合 D. 运算 2.在Data_Structure=(D,S)中，D是( )的有限集合。 A. 数据元素 B. 算法 C. 数据操作 D.数据对象 3.计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。 A. 数据与数据 B. 数据元素与数据元素 C. 元素内数据项与数据项 D. 数据文件内记录与记录 4.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 5.链接存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 6.从逻辑上可将数据结构分为( )。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 7.以下选项属于线性结构的是( )。 A. 广义表 B. 二叉树 C. 串 D. 稀疏数组 8.以下选项属于非线性结构的是( )。 A. 广义表 B. 队列 C. 优先队列 D. 栈 9.以下属于逻辑结构的是( ) A. 顺序表 B. 散列表 C. 有序表 D. 单链表 10.一个完整的算法应该具有( )等特性。 A. 可执行性、可修改性和可维护性 B. 可行性、确定性和有穷性
C. 确定性、有穷性和可靠性 D. 正确性、可读性和有效性 11.若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。 A. 迭代 B. 递归 C. 先递归后迭代 D. 先迭代后递归 12.一个递归算法必须包括( ) A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部 分 13.算法的时间复杂度与( )有关。 A. 问题规模 B. 源程序长度 C. 计算机硬件运行速度 D. 编译后执行程序的 质量 二、指出下列各算法的功能并求出其时间复杂度。 (1) int Prime(int n){ int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根 while(i<=x){ if(n%i==0)break; i++; } if(i>x) return 1; else return 0; } (2) int sum1(int n){ int p=1,s=0; for(int i=1;i<=n;i++){ p*=i;s+=p;
Data Structure 2015 hash table散列表：存放记录的数组 topological sort拓扑排序：将一个DAG中所有顶点在不违反前置依赖条件规定的基础上排成线性序列的过程称为拓扑排序（44）worst case 最差情况：从一个n元一维数组中找出一个给定的K，如果数组的最后一个元素是K，运行时间会相当长，因为要检查所有n个元素，这是算法的最差情况（15） FIFO先进先出：队列元素只能从队尾插入，从队首删除（20）（P82）2014 growth rate增长率：算法的增长率是指当输入的值增长时，算法代价的增长速率（14） priority queue 优先队列：一些按照重要性或优先级来组织的对象成为优先队列（26） external sorting外排序：考虑到有一组记录因数量太大而无法存放到主存中的问题，由于记录必须驻留在外存中，因此这些排序方法称为外排序（32） connected component连通分量：无向图的最大连通子图称为连通分量（40） 2013 stack栈：是限定仅在一端进行插入或删除操作的线性表（19）priority queue 优先队列：一些按照重要性或优先级来组织的对象
成为优先队列（26） BFS广度优先搜索：在进一步深入访问其他顶点之前，检查起点的所有相邻顶点（42） collision (in hashing)冲突：对于一个散列函数h和两个关键码值k1和k2，如果h(k1) =β= h(k2) ，其中β是表中的一个槽，那么就说k1和k2对于β在散列函数h下有冲（35） Chapter 1 Data Structures and Algorithms 1.type类型：是指一组值的集合 2.data type数据类型：一个类型和定义在这个类型上的一组操作 3.abstract data type(ADT) 抽象数据类型：指数据结构作为一个 软件构件的实现 4.data structure数据结构：是ADT的实现 5.problem问题：一个需要完成的任务，即对应一组输入，就有一 组相应的输出 6.function函数：是输入和输出之间的一种映射关系 7.algorithm算法：是指解决问题的一种方法或者一个过程 8.algorithm算法是解决问题的步骤，它必须把每一次输入转化为 正确的输出；一个算法应该由一系列具体步骤组成，下一步应执行的步骤必须明确；一个算法必须由有限步组成；算法必须可以终止。 https://www.doczj.com/doc/fb16559863.html,puter program计算机程序：被认为是使用某种程序设计语言 对一个算法的具体实现
数据结构练习第四章串 一、选择题 1．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 A. “STRUCTURE” B.“DATA” C. “ASTRUCTUR” D. “DATASTRUCTURE” 2．字符串的长度是指（）。 A. 串中不同字符的个数 B. 串中不同字母的个数 C. 串中所含字符的个数 D. 串中不同数字的个数 3．两个字符串相等的充要条件是（）。 A. 两个字符串的长度相等 B. 两个字符串中对应位置上的字符相等 C. 同时具备(A)和(B)两个条件 D. 以上答案都不对 4．关于串的叙述中，正确的是（） A．空串是只含有零个字符的串 B.空串是只含有空格字符的串 C.空串是含有零个字符或含有空格字符的串 D.串是含有一个或多个字符的有穷序列 5．下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 6．设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作( ) A．求子串 B.判断是否相等 C．模型匹配 D.连接 7．若串S=’software’,其子串的数目是( )。 A．8 B．37 C．36 D．9 8．串的长度是指（） A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 9．串是一种特殊的线性表，其特殊性体现在( )。 A．数据元素是一个字符 B. 可以顺序存储 C. 数据元素可以是多个字符 D. 可以链接存储 10．下面关于串的的叙述中，哪一个是不正确的（B） A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算 D. 串既可以采用顺序存储，也可以采用链式存储 11．若串＝‘software’，其非平凡子串（非空且不同于串本身）的数目是（C）A. 8 B. 37 C. 35 D. 9 12．串是一种特殊的线性表，其特殊性体现在（B） A. 可以顺序存储 B. 数组元素是一个字符 C. 可以连续存储 D. 数据元素可以是多个字符 13. 下面关于串的的叙述中，哪一个是不正确的？（B）
计算机是由什么组成的？CPU是什么东西，工作原理又是什么？操作系统以及内存硬盘这些统统都要懂，连这些都不懂你好意思说自己是程序员吗。 一、基础介绍 1）操作系统 什么是操作系统？你所编写的程序在什么操作系统上运行？目前主要有Windows类、Unix类、Linux类操作系统。每种操作系统对编程的影响是不同的。 2）计算机、内存、硬盘 这些概念对编程来说也是最基础的，例如计算机分为PC机、小型机、大型机。在PC机上编程和小型机上编程是有差别的。程序设计语言安装时也要注意内存大小和硬盘大小。 3）目录、文件 这些是最基础的概念了！一定要掌握和理解。因为你编写的程序就是一种文件，而且要放置在指定目录下。 4）程序设计语言、程序、编辑、源程序、编译、可执行程序、运行这些概念也是最基础的。 不同的程序设计语言对编程具有很大的影响。目前主流的程序设计语言有Java、C#、C语言等。 二.程序的概念 程序是由序列组成的，告诉计算机如何完成一个具体的任务。 程序是软件开发人员genuine用户需求开发的、用程序设计语言描述
的适合计算机执行的指令（语句）序列。由于现在的计算机还不能理解人类的自然语言，所以还不能用自然语言编写计算机程序。 三.程序的内容 1）对数据的描述 在程序中要指定数据的类型和数据的组织形式，即数据结构（datastructure）。 2）对操作的描述 即操作步骤，也就是算法（algorithm）。著名计算机科学家沃思提出一个公式：数据结构+算法=程序。实际上，一个程序除了以上两个主要的要素外，还应当采用程序设计方法进行设计，并且用一种计算机语言来表示。
线性结构题 1.栈和队列的共同特点是( A )。 (A) 只允许在端点处插入和删除元素 (B) 都是先进后出 (C) 都是先进先出 (D) 没有共同点 2.以下数据结构中哪一个是非线性结构？( D ) (A) 队列(B) 栈(C) 线性表(D) 二叉树 3.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在( C )位置。脚注(10)表示用10进制表示。 (A) 688 (B) 678 (C) 692 (D) 696 4．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03， 07>，<03，08>，<03，09>}，则数据结构A是（ B ）。 (A) 线性结构 (B) 树型结构(C) 物理结构(D) 图型结构 5．下面程序的时间复杂为（ B ） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4) 6.下列程序段的时间复杂度为（ A ）。 i=0，s=0；while (s Data structure Course code：80077009 Course Name：Data structure Credits：4 Term：semester V Audience:undergraduate majored in software engineering Pre-requisites：C programming Course Director：Yuanhao、associated professor、master Course Descriptions: Data structures is a professional compulsory course for students of software engineering.The goals of this course is to develop a solid understanding of the most common data structures and algorithms. Students will: 1.learn data structures such as lists, arrays, stacks, queues, trees, and graphs, these are commonly used data structures in almost every computer program; study their implementations, and analyze their efficiency (both in time and space) 2.Demonstrate a familiarity with major algorithms like sorting, searching and graph algorithms. 3. Analyze the asymptotic performance of algorithms and the evaluation of algorithms. Mastering these basic data structures and algorithms will greatly enhance students’ ability to write elegant programs. This course is really helpful for the further study. Practical Training During the semester, students must complete 8 experiments listed in schedule. Course Evaluation Homework+lab:20%；Final exam:80% Textbook [1] Tanhaoqiang.《Data structure》.Beijing:Tsinghua university press.2005.third edition Reference [1] Xuxiaokai,Weirong.《Data structure》. Beijing: China Machine Press.1996.second edition Reference [2]Chenwenbo,Zhuqing.《Data structure 》.Beijing:Tsinghua university press.1996.third edition 1 1．数据的最小单位是（ A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ C ）。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC(B) BCDA (C) CDAB (D) CBDA 5．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（ C ）。 (A) 9 (B) 10 (C) 11(D) 12 6．下面程序的时间复杂为（B ） for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (A) O(n) (B) O(n2)(C) O(n3) (D) O(n4) 7．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（ C ）。 (A) q=p->next；p->data=q->data；p->next=q->next；free(q)； (B) q=p->next；q->data=p->data；p->next=q->next；free(q)； (C) q=p->next；p->next=q->next；free(q)； (D) q=p->next；p->data=q->data；free(q)； 8．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1)(D) O(n2) 9．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 10．设用链表作为栈的存储结构则退栈操作（ B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．函数substr(“DATASTRUCTURE”，5，9)的返回值为（ A ）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（ C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1(D) N0=2N1+l 13．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。 (A) 空或只有一个结点(B) 高度等于其结点数 (C) 任一结点无左孩子(D) 任一结点无右孩子 14. 深度为k的完全二叉树中最少有（ C ）个结点。 (A) 2k-1-1 (B) 2k-1(C) 2k-1+1(D) 2k-1 Data and Structure 1、Data Types and Data Structures. 1，数据类型和数据结构。 ?What is a data type? 什么是数据类型？[修改] ?The essence of a type is that it attempts to identify qualities common to a group of individuals or objects that distinguish it as an identifiable class or kind. 一个类型的精髓在于它试图找出共同的特质的个人或者物体识别为可识别的类别或种类的IT小 组。[修改] ?If we provide a set of possible data values and a set of operations that act on the values,we can think of the combination as a data type. 如果我们提供一个可能的数据值和一组操作集的价值观行事，我们可以认为，作为一种数据类型的组合。 ? A data structure is a data type whose values are composed of component elements that are related by some structure. 一个数据结构是一种数据类型，其是由某种结构的组成元素组成的相关值。[修改]?Since a data structure is a data type,it has a set of operations on its values. 由于数据结构是一种数据类型，它有其价值的操作。[修改] ?In addition,there may be operations that act on its component elements. 此外，可能有操作上的组成元素的行为。[修改] 2、Typical Data Structures-Stacks and Queues. 二，典型数据结构，栈和队列。 ?The data types arrays and records are native to many programming languages. 这些数据类型的数组和记录原产于许多编程语言。[修改] ?By using the pointer data type and dynamic memory allocation,many programming languages also provide the facilities for constructing linked structures. 通过使用指针数据类型和动态内存分配，许多编程语言也为构建与结构的设施。[修改]?Arrays,records,and linked structures provide the building blocks for implementing what we might call higher-level abstractions. 数组，记录和链接结构为实施我们可以称之为更高层次的抽象的基石。[修改] 我以一名大学生的人格尊严保证，在本场考试中，自觉遵守考试纪律，服从考试管理，决不作弊或帮助别人作弊！签名：学院专业学号级班 ··················密···················封·····················线·················· 命题人签字：系主任签字：审核院长签字：共印份数： 第1页共6页聊城大学计算机学院2012—2013学年第1学期期末考试2011级《数据结构》试题（闭卷B卷） 一、单项选择题（共15题，每题2分，共30分） 1.研究数据结构就是研究（D ）。 A．数据的逻辑结构B．数据的存储结构 C．数据的逻辑结构和存储结构D．数据的逻辑结构、存储结构及其基本操作 2.在数据结构中，从逻辑上可以把数据结构分为（C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 3.算法分析的两个主要方面是（A ）。 A．空间复杂度和时间复杂度B．正确性和简单性 C．可读性和文档性D．数据复杂性和程序复杂性 4.下面程序段的时间复杂度是（ C ）。 for(i=0；i Midterm data structure review 1．Concepts explaining (1)Data structure (2)Time complexity (3)Array implementation of list (4)Linked list (5)Queue (6)Stack (7)Binary tree (8)Algorithm (9)Depth of a tree (10)Height of a tree 2．Single choice (1) Which data structure is first in last out for data storage? ( B ) A. Queue B. Stack C. Character string D. Simple linear list (2) Which is dequeue time complexity in a queue as follows? ( A ) A. O(1) B. O(log2n) C. O(n) D. O(n2) (3) If a push ing sequence of a stack is 1,2,3…,100, and the output sequence is p1,p2,p3, …,pn and if p1=100, what p20 is then? ( C ) A. 40 B. 60 C. 81 D. uncertain (4) Which are the normal two storage structures of stack structure? ( A ) A Sequence storage structure and linked storage structure B Hash mode and index mode C Linked list storage structure and array D linear storage structure and nonlinear storage structure (5) The memory address of first element of a sequence queue is 200, the memory address of the second element is 204 and the length of every element is 4, what is the address of 6th element? ( B ) A.210 B. 220 C. 200 D. 230 (6) What is the condition to judge if a stack S (m elements at best) is empty? ( A ) A. S.top= =0 B. S.top= =-1 C. S.top!=m D. S.top= =m (7) What is the sameness between queue and stack? ( C ) A. First in first out all B. First in last out all C. Insertion and deletion only be done at the terminals D. No sameness at alldata structure
数据结构习题(附答案)
Data and Structure(数据结构)
考研 数据结构试题(含答案)
data structure 期中复习答案
相关主题
文本预览