数据结构习题课1(绪论、线性表).ppt
习题课,第一章绪论第二章线性表授课教师：任国威,第一章绪论数据结构的基本概念：数据、数据元素、数据项、数据对象、数据结构、数据的逻辑结构、数据的物理结构、数据类型（原子型和结构型）、抽象数据类型（ADT）。算法的五个基本特征：算法的四个基本要求：算法用以下形式的函数描述：数据类型函数名（函数参数表）/算法说明语句序列/函数名,华中理工2001、02年考题、一个算法具有（）等特点A、可行性B、至少有一个输入量C、确定性D、健壮性、一个数据结构在计算机中的_称为存储结构、一个算法具有个特性：_有零个或多个输入、有一个或多个输出。,A、C,映像,确定性、可行性、有穷性,北航考题、数据的逻辑结构是指数据的个数据项之间的逻辑关系（判断题，分）、算法的计算量的大小称为计算的（）A、效率B、复杂度C、现实性D、难度哈工大考题、在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（）A、逻辑结构B、顺序存储结构C、链式存储结构 D、以上都对,错：指数据元素间的逻辑关系,B,B,、数据结构与数据类型有什么区别？（分）、抽象数据类型（分）、算法的时间复杂度（分）,数据结构是相互之间存在一种或多种特定关系的数据元素的集合，一般包括三方面内容：数据的逻辑结构、存储结构和数据的运算。而数据类型是一个值的集合和定义在这个值集上的一组操作的总称,指一个数学模型及定义在该模型上的一组操作,从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作的重复执行的次数作为算法的时间度量，也就是算法的时间复杂度。,练习测验、数据对象就是一组数据元素的集合（）、（）不是算法的基本特征。（武汉大学）A、正确性B、长度有限C、在规定时间内完成D、确定性、数据结构是一门研究非数值计算的程序设计问题中计算机的_,以及它们之间的_和操作等的学科。（南京理工大学2002年考题）A、操作对象，结构B、操作对象，关系C、逻辑存储，运算D、数据映象，算法,错：相同性质,、下面关于算法的说法错误的是（）南理A、算法最终必须由计算机程序实现B、为解决模问题的算法同为该问题编写的程序含义是相同的C、算法的可行性是指指令不能有二义性D、以上几个都是错误的,算法的确定性是指指令不能有二义性,试求出下面程序的时间复杂度,Int time(int n)count=0;x=2;while(xn/2)x*=2;count+;return(count)/time 练习册p91.9题,第二章线性表熟练掌握线性表的基本操作，尤其是链表，回去做练习册13页2.、2.2、2.72.a 编写程序，建立并显示一个有10个数据元素的顺序线性表。,线性表基本语法：定义顺序表（静态表）typedef struct ElemType int*elem;int length;int listsize;SqList;SqList L;：定义链表（链表）typedef struct LNode ElemType data;Struct LNode*next;LNode,*LinkList;LinkList L;/L是LinkList类型的变量,讲解：设计有效算法解决与线性表相关的应用问题是线性表学习的难点。下面通过约瑟夫（josephus）环问题来说明线性表的应用。约瑟夫（josephus）环问题为n个人围成一圈，从第s人开始报数，报到m的人出列，从下一个人再从新报数，报到m的人出列，如此下去，直到所有人出列。（详见ky-p12-josephus.c）解决思想：分单链表和顺序表、把n个人看成一环、设当前有p个人，下一出列的人为s=(s+m-1)%p、将出列的人删除。,设计一个时间复杂度为O(n)，空间复杂度不超过O(2)的算法，该算法将数组S0:n-1中所有元素依次循环右移k个位置-北航02年考题(ky-p14-rightrotation.c)解题重点：本题难在要求空间复杂度，只能申请两个辅助变量所以要考虑两种情况：、设k和n的最大公约数为m，则需要比较m趟。,0|1|2|3|4|5|6|7|8|9,0|1|2|3|4|5|6|7,K=4,练习：已知数组A1.n的元素类型为int。设计算法将其调整为左右两部分，左边左右元素为奇数，右边为偶数，要求时间复杂度为O(n)东南大学,Adjust(intA1.n)int I=1,j=n;while(IAj;,设计一个正整数序列组成的有序单链表(递增排序且允许有相等的数据元素),编写算法:1、确定单链表中比x大的数有几个（相同的数只算一次）详见ky-p16-countnum.c、将单链表中比x小的偶数删除(作业自作）、将比正整数x大的偶数从单链表里删除（作业自作）（东北大学2001）讲解：本题考学生单链表的操作，第一个算法已经给出，后两个请同学们自行完成。注意单链表生成的时候最后插入的节点最靠近表头，也就是输入链表数据时是递减，生成的链表数据就是递增的。,
