数据结构习题课1(绪论、线性表).pptVIP

习题课１ 第一章　绪论 　第二章　线性表 授课教师：任国威 第一章　绪论 数据结构的基本概念：数据、数据元素、数据项、数据对象、数据结构、数据的逻辑结构、数据的物理结构、数据类型（原子型和结构型）、抽象数据类型（ADT） 。 算法的五个基本特征： 算法的四个基本要求： 算法用以下形式的函数描述：数据类型　函数名　（函数参数表）｛//算法说明语句序列｝//函数名 华中理工2001、02年考题 １、一个算法具有（　　）等特点A、可行性　B、至少有一个输入量C、确定性　D、健壮性 ２、一个数据结构在计算机中的________称为存储结构 ３、一个算法具有５个特性： _____________________有零个或多个输入、有一个或多个输出。 北航考题 １、数据的逻辑结构是指数据的个数据项之间的逻辑关系（判断题，１分） ２、算法的计算量的大小称为计算的（　　）A、效率　B、复杂度　C、现实性　D、难度 哈工大考题 １、在计算机的存储器中表示时，物理地址和逻辑地址相同并且是连续的，称之为（　　）A、逻辑结构 　B、顺序存储结构C、链式存储结构　 D、以上都对 ２、数据结构与数据类型有什么区别？（３分） ３、抽象数据类型（３分） ４、算法的时间复杂度（３分） 练习测验 １、数据对象就是一组数据元素的集合（　） ２、（　）不是算法的基本特征。（武汉大学）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 练习册p9　1.9题 第二章　线性表 熟练掌握线性表的基本操作，尤其是链表，回去做练习册13页2.１、2.2、2.7 2.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)的算法，该算法将数组S[0:n-1]中所有元素依次循环右移k个位置----北航02年考题 　　　　　　　　　　　(ky-p14-rightrotation.c) 解题重点：本题难在要求空间复杂度，只能申请两个辅助变量．所以要考虑两种情况：１、设k和n的最大公约数为m，则需要比较m趟。 练习：已知数组A[1..n]的元素类型为int。设计算法将其调整为左右两部分，左边左右元素为奇数，右边为偶数，要求时间复杂度为O(n)—东南大学 设计一个正整数序列组成的有序单链表(递增排序且允许有相等的数据元素),编写算法:1、确定单链表中比x大的数有几个（相同的数只算一次）详见ky-p16-countnum.c ２、将单链表中比x小的偶数删除(作业自作）３、将比正整数x大的偶数从单链表里删除（作业自作） （东北大学2001） 讲解：本题考学生单链表的操作，第一个算法已经给出，后两个请同学们自行完成。注