数据结构复习题库.

重庆正大软件学院数据结构-复习题软件学院张红实第1章选择题1数据结构这门学科是针对什么问题而产生的？（）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对第1章选择题2数据结构这门学科的研究内容下面选项最准确的是（）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作第1章选择题3某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素第1章选择题4数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（）。A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构第1章选择题5算法分析的目的是（）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性第1章选择题6算法分析的主要方法（）。A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性第1章选择题7计算机内部处理的基本单元是（）A、数据B、数据元素C、数据项D、数据库第1章选择题8数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。A、低B、高C、相同D、不好说第1章选择题9算法的时间复杂度取决于（）A、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说第1章选择题10数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（）。A、正确B、错误C、前半句对，后半句错D、前半句错，后半句对第1章选择题11在数据结构中，从逻辑上可以把数据结构分成（）A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构第1章选择题12线性表的链式存储结构是一种()的存储结构A、随机存取B、顺序存取C、索引存取D、散列存取第1章选择题13线性表的链式存储结构是一种()的存储结构A、随机存取B、顺序存取C、索引存取D、散列存取第1章简答题1请分别给出数据、数据对象、数据元素、数据项的含义，并说明四者的关系数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并能被计算机程序处理的符号的总称。（一个得分点）数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理，相当于表中的一条记录。（一个得分点）数据项：相当于记录的“域”,是数据的不可分割的最小单位,如学号（一个得分点）数据对象：性质相同的数据元素的集合，是数据的一个子集.例如:同一个班的所有学生记录集合。（一个得分点）关系：包含关系：数据泛指所有。数据对象是数据的一个子集，由数据元素组成，数据元素是由数据项组成。（一个得分点）第1章简答题2请给出数据的逻辑结构的含义，并举例说明数据的逻辑结构通常有哪些。数据的逻辑结构：指数据元素之间的逻辑关系。即用自然语言描述数据，它与数据的存储无关，是独立于计算机的。第1章简答题3求两个正整数m，n中的最大数MAX的算法（1）若mn则max=m（2）若m=n则max=n请根据上述算法解释一下算法的组成要素有哪些，分别是什么。算法由操作、控制结构、数据结构3要素组成操作包含：算术运算、关系比较、逻辑运算、数据传送（输入、输出、赋值）（一个得分点）例子中有关系比较和赋值计算的操作。（一个得分点）控制结构包含：顺序结构、选择结构、循环结构（一个得分点）例子中有选择结构（一个得分点）数据结构：算法操作的对象是数据，数据间的逻辑关系、数据的存储方式及处理方式就是数据结构。（一个得分点）本例是数值问题，涉及到两个正整数，因此使用基本的整数类型就可以解决问题。（一个得分点）第1章简答题4简述算法的基本性质1）输入：0个或多个输入2）输出：1个或多个输出3）有穷性：算法必须在有限步内结束4）确定性：组成算法的操作必须清晰无二义性5）可行性：组成算法的操作必须能够在计算机上实现第1章简答题5简述算法的设计要求1、正确性（correctness）2、可读性（readability）3、健壮性（robustness）4、通用性（generality）5、效率与存储的要求（执行算法所耗费的存储空间、执行算法所耗费的时间）第1章简答题6评价算法好坏的3条主要标准1）算法实现所耗费的时间。2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间。3）算法应易于理解、易于编码、易于调试等。第1章简答题7请简述数据结构所研究的三种基本结构，以及数据元素间的关系。线性结构：数据元素之间一对一的关系。树形结构：数据元素之间一对多的关系。图形结构：数据元素之间多对多的关系。第1章简答题8请问算法的分析和评价的两个标准，以及各自作用。时间复杂度：评估算法运行所需时间空间复杂度：评估算法运行时所需最大存储空间第1章简答题9请说出三种逻辑数据结构，以及他们的特点。（1）线性结构：数据元素只有一个前驱数据元素和一个后继数据元素（2）树结构：每个数据元素只有一个前驱数据元素，可有零个或若干个后继数据元素（3）图结构：每个数据元素可有零个或若干个前驱数据元素，零个或若干个后继数据元素第1章简答题10评价算法的主要标准是什么？（1）算法实现所耗费的时间（2）算法实现所耗费的存储空间，其中主要考虑辅助存储空间（3）算法应易于理解、易于编码、易于调试第1章简答题11请说出三种逻辑数据结构，并分别画图表示它们。第1章简答题12算法的基本性质有哪些？并简述每个特性。（1）有穷性——（2）确定性——（3）可行性——（4）输入性——（5）输出性——第1章简答题13通常从那几个方面来评价算法的质量?通常从四个方面评价算法的质量：正确性、可读性、健壮性和高效性。第1章简答题14请描述线性数据结构的两种存储方式，并说出其各有什么特点。顺序存储：连续存储，易于定位，不易于插入和删除链式存储：非连续存储，不易于定位，易于插入和删除第1章简答题15请问算法的分析和评价的两种方法，它们关注点各有什么不同空间效率：关注算法对内存的占用度时间效率：关注算法的运算速度第2章选择题1关于线性表的说法不正确的是？（）A、存在唯一的一个被称为“第一个”的数据元素（开始结点）B、存在唯一的一个被称为“最后一个”的数据元素（终端结点）C、除第一个之外，集合中的每个数据元素均只有一个前驱D、除第一个之外，集合中的每个数据元素均只有一个后继第2章选择题2关于顺序表的说法不正确的是？（）A、逻辑关系上相邻的两个元素在物理存储位置上也相邻B、可以随机存取表中任一元素，方便快捷C、在线性表中插入某一元素时，往往需要移动大量元素D、在线性表中删除某一元素时，无需移动大量元素第2章选择题3当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用什么存储结构？（）A、顺序表B、单链表C、循环链表D、双链表第2章选择题4在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动多少个元素。（）A、n-1B、n-iC、n-i+1D、n-i-1第2章选择题5在单链表中设置头结点的作用是()。A、单链表定义而已B、指定表的起始位置C、为双向链表做准备D、为循环链表做准备第2章选择题6根据线性表链式存储结构中每一个结点包含的指针数，将线性链表分成（）A、单链表与循环链表B、单链表与十字链表C、单链表与双链表D、循环链表与多链表第2章选择题7链接存储的特点是利用什么来表示数据元素之间的逻辑关系（）A、引用B、串联C、挂接D、指派第2章选择题8已知指针p指向单链表L中的某结点，则删除其后继结点的语句是（）A、p=p.nextB、p=nullC、p.next=nullD、p.next=p.next.next第2章简答题1请问如果要插入一个数据到一个线性表中，顺序表和链表哪个的效率高？为什么？链表的效率高因为顺序表要移动插入位置后的每一个元素的位置给新数据腾位置链表只需要将前一个数据的指针指向新数据并将新数据的指针指向后一个数据即可第2章简答题2线性表有哪些特点？1）除第一个和最后一个数据元素外，每个数据元素只有一个前驱数据元素和一个后继数据元素2）第一个数据元素没有前驱数据元素3）最后一个数据元素没有后继数据元素第2章简答题3顺序存储结构的优缺点有哪些?顺序存储结构的优点:存储空间连续逻辑相邻，物理相邻可随机存取任一元素缺点:插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充第2章简答题4单链式存储结构的优缺点有哪些?单链式存储结构的优点:不需预先分配空间，空间利用充分插入、删除操作简单,无需移动大量的元素表容量易于扩充缺点:每个数据元素，除存储本身信息外，还需空间存储其直接后继的信息逻辑相邻，物理不一定相邻不可随机存取任一元素,只能从链表头依次查找.第2章简答题5有顺序表A=(a0,a1,a2,...a8,a9,…a19)，要在a8,a9之间插入一个元素a20，请描述其操作(思想)步骤。插入思想或步骤：根据顺序表的存储特点，要在表中某位置10插入一新数据元素,则要进行如下两步操作：（1）、从位置10到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第10个位置（2）、将新结点插入到空余位置10处。（3）表长度加1.第2章简答题6有顺序表A=(a0,a1,a2,...a8,a9,…a19)，要删除一个元素a9，请描述其操作(思想)步骤。（1）然后将从位置11到表尾的所有数据元素依次向前移一个存储位置（2）表长度减1.第2章简答题7请描述在顺序表中第i个位置插入新的数据x操作过程。根据顺序表的存储特点，要在表中某位置i插入一新数据元素，则要进行如下操作：（1）从位置i到表尾位置的所有数据元素均要从后至前依次向后移一个存储位置，为新插入结点腾出第i个位置（2）将新数据x插入到空余位置i处（3）表长度加1.第2章简答题8请描述在顺序表中删除第i个位置的数据的过程。（1）然后将从位置i+1到表尾的所有数据元素依次向前移一个存储位置（2）表长度减1.第2章简答题9请描述在一个单链表中插入一个数据q的插入过程。找到将插入数据位置的前一个结点p;q的next值等于p的next值;p的next值等于q第2章简答题10请描述从一个单链表中删除一个数据的删除过程。（1）找到将被删除数据的前一个结点p;（2）p的next指针指向被删除数据的后一个结点（3）将被删除数据原来的next指针指向null;第3章选择题1栈、队列通常采用两种存储结构，它们是()A、散列方式和索引方式B、顺序存储结构和链式存储结构C、链表存储结构和数组D、线性和非线性存储结构第3章选择题2一个栈入栈序列是a,b,c,d,则栈输出序列不可能是()A、d,c,b,aB、c,d,b,aC、d,c,a,bD、a,b,c,d第3章选择题3判断顺序栈（最多结点数为m）为栈满的条件是（）A、top==0B、top!=mC、top!=0D、top==m第3章选择题4栈存取数据原则（或栈特点）是（）A、后进后出B、后进先出C、先进先出D、随意进