下载文档原格式
11.线性表是A.一个有限序列，可以为空B.一个有限序列，不能为空C.一个无限序列，可以为空D.一个无限序列，可以为空正确答案是：【A】解析：线性表的定义如下：线性表是具有n（n≥0）个元素的一个有限序列，当n=0时称为空表。
2在n个结点的顺序表，算法的时间复杂度是O(1)的操作是A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.顺序查找与给定值x相等的元素正确答案是：【A】解析：顺序表可以按元素下标直接存和直接取，其时间复杂度为O(1)。
在第i个元素后面插入新元素和删除第i个元素的时间复杂度都是O(n)，顺序查找的时间复杂度也是O(n)。
3若长度为n的线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，需要移动表中数据元素的数目为A.iB.n+iC.n-i+1D.n-i-1正确答案是：【C】解析：在线性表的第i个位置插入一个新的数据元素之前，需要先将线性表的第i个数据元素至第n个数据元素依次后移1个位置，一共需要移动n-i+1个数据元素。
4将两个各有n1和n2个元素的有序表（递增）归并成一个有序表，仍保持其递增顺序，则最少的比较次数是A.B.C.D.正确答案是：【C】解析：由于将长度为n的单链表链接在长度为m的单链表之后的操作，需要把长度为m的单链表遍历一遍，找到最后的一个结点，所以时间复杂度为O （m）。
5已知L是带头结点的单链表，结点p既不是第一个结点，也不是最后一个结点，删除p结点的直接后继结点的语句序列是A.p=p→nextB.p→next=pC.p→next=p→next→nextD.p=p→next→next正确答案是：【C】解析：选项A是删除了当前p结点；选项B是把p结点之后的所有结点都丢失了，同时在p结点本身形成了一个环；选项C正确；选项D是把p和p的后继结点都删除了。
6设双向循环链表中结点的结构为（prior，data，next），且不带表头结点。
教与学|数据结构一C语言描述（教学大纲）一、课程基本信息二、课程描述和目标1•课程描述本课程是高等院校计算机类相关专业一门重要的学科基础课，也是本校计算机科学与技术、软件工程、网络工程、大数据与科学技术等专业的计算机大类平台必修课。
本课程主要讨论各种数据的抽象表示、实现方法、处理数据的算法设计以及对算法性能的分析。
它的先修课程是：高级语言程序设计，后继课程是：数据库原理、操作系统等。
本课程的教学依赖于其先修课程，又能为其后续课程及进一步的软件开发奠定良好的理论与实践基础。
2.课程目标结合专业人才培养方案，并基于新工科专业OBE理念，力求通过本课程的系统学习促进学生在知识、能力和素质三方面得到一定程度的提升。
课程目标1:能够清楚表述数据结构和算法的基本概念，并能判断计算机处理不同数据时所采用的组织方法、操作原理和实现方法。
课程目标2:能够针对具体问题，运用数据结构课程相关知识和批判思维，分析计算机处理对象的结构特征，选择合适的数据存储结构，设计高效的操作算法。
课程目标3:能够综合运用数据结构的基本原理和设计方法，研究复杂问题的特征，自主设计可行的求解方案，并能运用高级语言编写实现问题求解的应用程序，再验证其正确性。
三、课程目标对毕业要求的支撑关系四、教学内容、基本要求及学时分配本课程教学内容主要包括线性表、栈和队列、串与数组、树和图等主要数据结构的特点、在计算机内部的表示和实现原理与方法分析，以及查找和排序两种主要操作的各种实线性表的应用奋斗一我自己励志的故事栈的应用奉献-开源技术背后的故事10分钟矩阵的压缩存储节约-提升资源复用水平、降低资源消耗的相关故事10分钟哈夫曼树与哈夫曼编码（压创新-工匠精神，余立平冒着巨大的危险雕刻火药的10分钟缩技术）航天人的故事拓扑排序、关键路径分布式-跨地域信息沟通水平，是升社会安全的故事10分钟二叉排序树上的查找快速排序效率-有关提升计算资源利用率以及社会生产效率10分钟的故事协作一有关专业分工、各司其职的螺丝钉精神的故10分钟五、课程重难点六、课程要求及成绩评定1.教学环节及其组织形式本课程采用线上线下相结合的混合式教学模式实施教学，整个教学分课前、课中、课后三个环节进行组织教学活动。
第2章线性表练习题答案一、填空1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。
2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。
3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。
4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。
5．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
二、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。
答：错误。
链表中的结点可含多个指针域，分别存放多个指针。
例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。
（×）2. 链表的物理存储结构具有同链表一样的顺序。
错，链表的存储结构特点是无序，而链表的示意图有序。
（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
错，链表的结点不会移动，只是指针内容改变。
（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。
（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
错，正好说反了。
顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
错，前一半正确，但后一半说法错误，那是链式存储的优点。
顺序存储方式插入、删除运算效率较低，在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。
（×）7. 线性表在物理存储空间中也一定是连续的。
错，线性表有两种存储方式，顺序存储和链式存储。
数据结构作业答案单选题1、下列关于算法的基本特征，说法不正确的是（）。
能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。
算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。
算法的有穷性是指算法必须能在有限的时间内做完。
算法与提供情报无关。
[D] 教师批改：D2、算法的时间复杂度取决于（）。
问题的规模待处理的数据的初态问题的难度 A 和 B[D] 教师批改：D3、下列选项中，不是算法基本特征的是（）。
可行性有穷性确定性高效率[D] 教师批改：D4、通常一个好的算法应达到的目标中，不包括（）。
正确性可读性技巧性健壮性[C] 教师批改：C5、在一般的计算机系统中，基本的运算和操作不包括（）。
语法处理算术运算关系运算数据传输[A] 教师批改：A6、工程上常用的分治法是（）。
列举法归纳法减半递推技术回溯法[C] 教师批改：C多选题7、算法设计的要求包括（）。
正确性可读性健壮性唯一性[ABC] 教师批改：A，B，C8、算法的时间复杂度应该与（）无关。
所使用的计算机程序设计语言基本运算的执行次数程序编制者[ABD] 教师批改：A，B，D9、下列关于算法的描述中，不正确的有（）。
算法即是计算机程序算法是解决问题的计算方法算法是排序方法算法是解决问题的有限运算序列[ABC] 教师批改：A，B，C填空题16、所谓算法是指（）。
教师批改：解题方案的准确而完整的描述17、算法的基本特征有（）、（）、（）和（）教师批改：能行性、确定性、有穷性和拥有足够的情报。
18、一个算法通常由两种基本要素组成，它们是（）和（）。
教师批改：算法中对数据的运算和操作。
算法的控制结构。
19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。
教师批改：归纳法、递推、递归、减半递推技术。
20、算法的复杂度主要包括（）复杂度和（）复杂度。
教师批改：时间、空间综合题21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）：int mid ( int a, int b, int c){ int m ; m=a ;if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b ; else m=c ; } }else { if ( m<=c) { if (b>=c) m=c; else m=b ; } }return ( m ) ;}假设a，b，c中的每一个数为中数的概率相等（均为1/3）。
【数据结构】线性表顺序表详解和代码实例线性表(List)是零个或者多个数据元素的有限序列.⾸先它是⼀个序列.⾥⾯的元素是有顺序的,如果有多个元素,除开头和结尾以外的元素都有⼀个前驱和⼀个后继.⽽开头元素只有后继,结尾元素只有前驱.其次线性表是有限的，也就是⾥⾯的元素个数是有限的。
1ADT 线性表（List）2Data3线性表的数据对象集合为{a1, a2, a3, ......, an},每个元素类型为DataType。
4Operation5InitList(L); //初始化线性表6 IsEmptyList(L); //判断线性表是否为空7 ClearList(L); //清空线性表8 GetElemList(L, i, *e); //获取第i个位置的数据9 SearchList(L, e); //查找与数据e相等的元素10 InsertNodeList(L, i, e);//在第i个位置插⼊元素11 DeleteNodeList(L, i, *e);//删除第i个位置的元素，e获取删除元素12 GetLengthList(L); //获取线性表的长度13endADT关于线性表的基本操作就上⾯⼏种，还有⼏个例如线性表的排序，合并，逆序等等操作。
为了⽂章篇幅，就下次再介绍了。
线性表的顺序存储结构，就是指 ⽤⼀段地址连续的存储单元⼀次存储线性表的数据元素。
学过⾼级语⾔的朋友，相信对数组这玩意⼉都不会陌⽣吧。
数组就是⼀种顺序存储结构。
链式存储结构就是可以⽤⼀组任意的内存单元存储线性表中的元素。
与顺序存储不同的是，这组内存单元可以是连续的，也可以是不连续的。
这就意味着，元素可以存储在内存的任意位置。
正因为如此，在链式结构中，每个元素不仅要存它的信息，还需要存储它后继元素的存储地址。
我们把存储元素信息的域称为数据域，⽽把存储后继元素地址的域称为指针域。
由这两部分共同组成的数据元素ai，则可以称之为节点(Node)。
第一章习题答案2、××√3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽（3）数据对象、对象间的关系、一组处理数据的操作（4）指针类型（5）集合结构、线性结构、树形结构、图状结构（6）顺序存储、非顺序存储（7）一对一、一对多、多对多（8）一系列的操作（9）有限性、输入、可行性4、（1）A（2）C（3）C5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n）第二章习题答案1、（1）一半，插入、删除的位置（2）顺序和链式，显示，隐式（3）一定，不一定（4）头指针，头结点的指针域，其前驱的指针域2、（1）A（2）A：E、AB：H、L、I、E、AC：F、MD：L、J、A、G或J、A、G（3）D（4）D（5）C（6）A、C3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。
头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。
首元素结点：线性表中的第一个结点成为首元素结点。
4、算法如下：int Linser(SeqList *L,int X){ int i=0,k;if(L->last>=MAXSIZE-1){ printf(“表已满无法插入”)；return(0);}while(i<=L->last&&L->elem[i]<X)i++;for(k=L->last;k>=I;k--)L->elem[k+1]=L->elem[k];L->elem[i]=X;L->last++;return(1);}5、算法如下：#define OK 1#define ERROR 0Int LDel(Seqlist *L,int i,int k){ int j;if(i<1||(i+k)>(L->last+2)){ printf(“输入的i，k值不合法”);return ERROR;}if((i+k)==(L->last+2)){ L->last=i-2;ruturn OK;}else{for(j=i+k-1;j<=L->last;j++)elem[j-k]=elem[j];L->last=L->last-k;return OK;}}6、算法如下：#define OK 1#define ERROR 0Int Delet(LInkList L,int mink,int maxk){ Node *p,*q;p=L;while(p->next!=NULL)p=p->next;if(mink<maxk||(L->next->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”);return ERROR;}else{ p=L;while(p->next-data<=mink)p=p->next;while(q->data<maxk){ p->next=q->next;free(q);q=p->next;}return OK;}}9、算法如下：int Dele(Node *S){ Node *p;P=s->next;If(p= =s){printf(“只有一个结点，不删除”)；return 0;}else{if((p->next= =s){s->next=s;free(p);return 1;}Else{ while(p->next->next!=s)P=p->next;P->next=s;Free(p);return 1;}}}第三章习题答案2、（1）3、栈有顺序栈和链栈两种存储结构。
