MOOC 数据结构-河南城建学院 中国大学慕课答案

MOOC数据结构-河南城建学院中国大学慕课答案数据结构的研究内容随堂测验1、问题：1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。选项：A、数据元素B、计算方法C、逻辑存储D、数据映像正确答案:【计算方法】2、问题：2.研究数据结构就是研究（）选项：A、数据的逻辑结构B、数据的存储结构C、数据的逻辑结构和存储结构D、数据的逻辑结构、存储结构及其基本操作正确答案:【数据的逻辑结构、存储结构及其基本操作】3、问题：3.具有线性结构的数据结构是（）。选项：A、图B、树C、广义表D、栈正确答案:【栈】4、问题：4.记录是数据处理的最小单位。选项：A、正确B、错误正确答案:【错误】5、填空题：5.数据结构被形式地定义为（D,R），其中D是（）的有限集合，R是D上的关系有限集合。正确答案:【数据元素】基本概念和术语随堂测验1、问题：1.组成数据的基本单位是（）选项：A、数据项B、数据类型C、数据元素D、数据变量正确答案:【数据元素】2、问题：2.数据结构中，与所使用的计算机无关的是数据的（）结构。选项：A、存储B、物理C、逻辑D、物理和存储正确答案:【逻辑】3、问题：3.所谓数据的逻辑结构指的是数据之间的逻辑关系。选项：A、正确B、错误正确答案:【错误】4、问题：4.逻辑结构与数据元素本身的内容和形式无关。选项：A、正确B、错误正确答案:【正确】5、问题：5.数据的物理结构是指数据在计算机内的实际存储形式。()选项：A、正确B、错误正确答案:【正确】抽象数据类型的表示与实现随堂测验1、问题：1.数据结构的抽象操作的定义与具体实现有关。选项：A、正确B、错误正确答案:【错误】2、问题：2.在顺序存储结构中，有时也存储数据结构中元素之间的关系。选项：A、正确B、错误正确答案:【错误】3、问题：3.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。选项：A、正确B、错误正确答案:【正确】4、问题：4.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。选项：A、正确B、错误正确答案:【错误】5、填空题：5.在有n个选手参加的单循环赛中，总共将进行（）场比赛。正确答案:【n(n-1)/2】算法和算法分析随堂测验1、问题：1.下面（）不是算法所必须具备的特性。选项：A、有穷性B、确切性C、高效性D、可行性正确答案:【高效性】2、问题：2.算法指的是（）。选项：A、对特定问题求解步骤的一种描述，是指令的有限序列。B、计算机程序C、解决问题的计算方法D、数据处理正确答案:【对特定问题求解步骤的一种描述，是指令的有限序列。】3、问题：3.算法分析的两个主要方面是：（）选项：A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性正确答案:【空间复杂性和时间复杂性】4、问题：4.算法的时间复杂度与（）有关。选项：A、问题规模B、计算机硬件性能C、编译程序质量D、程序设计语言正确答案:【问题规模】5、问题：5.算法的优劣与算法描述语言无关，但与所用计算机有关。()选项：A、正确B、错误正确答案:【错误】绪论单元作业绪论单元测验1、问题：与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。选项：A、存储结构B、存储实现C、逻辑结构D、运算实现正确答案:【逻辑结构】2、问题：通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。选项：A、数据具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等正确答案:【不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致】3、问题：以下说法正确的是（）。选项：A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构正确答案:【一些表面上很不相同的数据可以有相同的逻辑结构】4、问题：算法的时间复杂度取决于（）。选项：A、问题的规模B、待处理数据的初态C、计算机的配置D、A和B正确答案:【A和B】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、问题：试分析下面程序段的时间复杂度。for(i=0;in;i++)for(j=0;jm;j++)a[i][j]=0;选项：A、O(m)B、O(n)C、O(m*n)D、O(m+n)正确答案:【O(m*n)】11、问题：算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。选项：A、正确B、错误正确答案:【错误】12、问题：每种数据结构都具备三个基本操作：插入、删除和查找。选项：A、正确B、错误正确答案:【错误】13、问题：逻辑结构与数据元素本身的内容和形式无关。选项：A、正确B、错误正确答案:【正确】14、问题：基于某种逻辑结构之上的基本操作，其实现是唯一的。选项：A、正确B、错误正确答案:【错误】15、问题：所谓数据的逻辑结构指的是数据之间的逻辑关系。选项：A、正确B、错误正确答案:【错误】16、填空题：（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。正确答案:【数据元素】17、填空题：在一般情况下，一个算法的时间复杂度是（）的函数。正确答案:【问题规模】18、填空题：下面程序段的时间复杂度是（）x=90;y=100;while(y0)if(x100){x=x-10;y--;}elsex++;正确答案:【O(1)】19、填空题：数据的存储结构主要有顺序存储结构和链式存储结构两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素和（）。正确答案:【数据元素之间的关系】20、填空题：顺序存储结构中数据元素之间的逻辑关系是由存储位置表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。正确答案:【指针】线性表的定义和特点随堂测验1、问题：1.线性表是具有n个（）的有限序列（n≠0)选项：A、表元素B、字符C、数据元素D、数据项正确答案:【数据元素】2、问题：2.线性表的逻辑顺序和存储顺序总是一致的。选项：A、正确B、错误正确答案:【错误】3、问题：3.集合与线性表的区别在于是否按关键字排序。选项：A、正确B、错误正确答案:【错误】4、问题：4.线性表的特点是每个元素都有一个前驱和一个后继。选项：A、正确B、错误正确答案:【错误】5、问题：5.线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。选项：A、正确B、错误正确答案:【错误】线性表的类型定义随堂测验1、问题：1.以下关于线性表的说法不正确的是（）。选项：A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。正确答案:【线性表中的每个结点都有且只有一个直接前趋和直接后继。】2、问题：2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。选项：A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序正确答案:【访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）】3、问题：3.线性表就是顺序存储的表。选项：A、正确B、错误正确答案:【错误】4、问题：4.取线性表的第i个元素的时间同i的大小有关。选项：A、正确B、错误正确答案:【错误】5、问题：5.链接存储的特点是利用指针来表示数据元素之间的逻辑关系选项：A、正确B、错误正确答案:【正确】线性表的顺序表示和实现随堂测验1、问题：1.顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。选项：A、110B、108C、100D、120正确答案:【108】2、问题：2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。选项：A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B、在第i个结点后插入一个新结点（1≤i≤n）C、删除第i个结点（1≤i≤n）D、将n个结点从小到大排序正确答案:【访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）】3、问题：3.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。选项：A、64B、63C、63.5D、7正确答案:【63.5】4、问题：4.顺序存储方式只能用于存储线性结构。选项：A、正确B、错误正确答案:【错误】5、问题：5.顺序存储的线性表可以随机存取。选项：A、正确B、错误正确答案:【正确】线性表的链式表示和实现随堂测验1、问题：1.在一个单链表中，若删除p所指向结点的后续结点，则执行（）。选项：A、p-next=p-next-next;B、p=p-next;p-next=p-next-next;C、p=p-next;D、p=p-next-next;正确答案:【p-next=p-next-next;】2、问题：2.循环链表的主要优点是（）。选项：A、不再需要头指针B、已知某结点位置后能容易找到其直接前驱C、在进行插入、删除运算时能保证链表不断开D、在表中任一结点出发都能扫描整个链表正确答案:【在表中任一结点出发都能扫描整个链表】3、问题：3.用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。选项：A、正确B、错误正确答案:【正确】4、问题：4.所谓静态链表就是一直不发生变化的链表。选项：A、正确B、错误正确答案:【错误】5、问题：5.在具有头结点的单链表中，头指针指向链表的第一个数据结点（的存储位置）。选项：A、正确B、错误正确答案:【正确】顺序表和链表的比较随堂测验1、问题：1.在以下的叙述中，正确的是（）。选项：A、线性表的顺序存储结构优于链表存储结构ꢀB、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C、线性表的链表存储结构适用于频繁插入/删除数据元素的情况D、线性表的链表存储结构优于顺序存储结构正确答案:【线性表的链表存储结构适用于频繁插入/删除数据元素的情况】2、问题：2.线性表Ｌ在（）情况下适用于使用链式结构实现。选项：A、需经常修改Ｌ中的结点值B、需不断对Ｌ进行删除插入C、Ｌ中含有大量的结点D、Ｌ中结点结构复杂正确答案:【需不断对Ｌ进行删除插入】3、问题：3.为了很方便的插入和删除数据，可以使用双向链表存放数据。选项：A、正确B、错误正确答案:【正确】4、问题：4.顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。选项：A、正确B、错误正确答案:【错误】5、问题：5.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。选项：A、正确B、错误正确答案:【正确】线性表的应用随堂测验1、问题：3.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。选项：A、nB、2n-1C、2nD、n-1正确答案:【n】2、问题：4.创建一个包括n个结点的有序单链表的时间复杂度是（）。选项：A、O(1)B、O(n)C、O(n2)D、O(nlog2n)正确答案:【O(n2)】3、问题：5.链接存储的存储结构所占存储空间（）。选项：A、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B、只有一部分，存放结点值C、只有一部分，存储表示结点间关系的指针D、分两部分，一部分存放结点值，另一部分存放结点所占单元数正确答案:【分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针】4、问题：1.对任何数据结构链式存储结构一定优于顺序存储结构。选项：A、正确B、错误正确答案:【错误】5、问题：2.取线性表的第i个元素的时间同i的大小有关。选项：A、正确B、错误正确答案:【错误】线性表单元作业线性表单元测验1、问题：线性表采用链接存储时，其地址（）。选项：A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续与否均可以正确答案:【连续与否均可以】2、问题：单循环链表的主要优点是（）。选项：A、不再需要头指针了B、从表中任一结点出发都能扫描到整个链表C、已知某个结点的位置后，能够容易找到它的直接前趋D、在进行插入、删除操作时，能更好地保证链表不断开正确答案:【从表中任一结点出发都能扫描到整个链表】3、问题：链表不具有的特点是（）。选项：A、可随机访问任一元素B、插入、删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比正确答案:【可随机访问任一元素】4、问题：若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。选项：A、顺序表B、单链表C、双链表D、单循环链表正确答案:【顺序表】5、问题：若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。选项：A、单链表B、带头指针的单循环链表C、双链表D、带尾指针的单循环链表正确答案:【带尾指针的单循环链表】6、问题：在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。选项：A、n-iB、n-i+1C、n-i-1D、i正确答案:【n-i+1】7、问题：在双向链表存储结构中，删除p所指的结点时须修改指针（）。选项：A、p-next-prior=p-prior;p-prior-next=p-next;B、p-next=p-next-next;p-next-prior=p;C、p-prior-next=p;p-prior=p-prior-prior;D、p-prior=p-next-next;p-next=p-prior-prior;正确答案:【p-next-prior=p-prior;p-prior-next=p-next;】8、问题：使用双链表存储线性表，其优点是可以（）。选项：A、提高查找速度B、更方便数据的插入和删除C、节约存储空间D、很快回收存储空间正确答案:【更方便数据的插入和删除】9、问题：在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。选项：A、基地址B、结点大小C、向量大小D、基地址和结点大小正确答案:【基地址和结点大小】10、问题：在（）运算中，使用顺序表比链表好。选项：A、插入B、删除C、根据序号查找D、根据元素值查找正确答案:【根据序号查找】11、问题：链表中的头结点仅起到标识的作用。选项：A、正确B、错误正确答案:【错误】12、问题：顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。选项：A、正确B、错误正确答案:【错误】13、问题：取线性表的第i个元素的时间同i的大小有关。选项：A、正确B、错误正确答案:【错误】14、问题：设p，q是指针，若p=q，则*p=*q选项：A、正确B、错误正确答案:【错误】15、问题：在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。选项：A、正确B、错误正确答案:【错误】16、填空题：一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）。正确答案:【Ο(1)】17、填空题：顺序表中逻辑上相邻的元素的物理位置（）。正确答案:【相邻】18、填空题：当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用（）存储结构。正确答案:【顺序】19、填空题：线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。正确答案:【（n-1）/2】20、填空题：根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成（）和多重链表。正确答案:【单链表】栈和队列的定义和特点随堂测验1、问题：1．在栈中，下列说法正确的是（）。选项：A、每次插入总是在栈顶，每次删除也总是在栈顶。B、每次插入总是在栈顶，每次删除总是在栈底。C、每次插入总是在栈底，每次删除总是在栈顶。D、在栈底，每次删除也总是在栈底。正确答案:【每次插入总是在栈顶，每次删除也总是在栈顶。】2、问题：2．在队列中，下列说法正确的是（）。选项：A、每次插入总是在队尾，每次删除总是在队头。B、每次插入总是在队尾，每次删除也总是在队尾。C、每次插入总是在队头，每次删除也总是在队头。D、每次插入总是在队头，每次删除总是在队尾。正确答案:【每次插入总是在队尾，每次删除总是在队头。】3、问题：3．队列操作的原则是（）。选项：A、后进先出B、只能进行插入C、先进先出D、只能进行删除正确答案:【先进先出】4、问题：4．栈和队列都是受限的线性结构。选项：A、正确B、错误正确答案:【正确】5、问题：5．可以使用栈处理进制转换问题。选项：A、正确B、错误正确答案:【正确】栈的表示和操作的实现随堂测验1、问题：1.一个顺序栈S，其栈顶指针为top，则将元素e入栈的操作是（）。选项：A、*S-top=e;S-top++;B、S-top++;*S-top=e;C、*S-top=eD、S-top=e;正确答案:【*S-top=e;S-top++;】2、问题：2.判定一个顺序栈S（栈空间大小为n）为空的条件是（）。选项：A、S-top==0B、S-top!=0C、S-top==nD、S-top!=n正确答案:【S-top==0】3、问题：3.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。选项：A、iB、n-iC、n-i+1D、不确定正确答案:【n-i+1】4、问题：4.链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。选项：A、x=top-data;top=top-link；B、top=top-link;x=top-link；C、x=top;top=top-link；D、x=top-link；正确答案:【x=top-data;top=top-link；】5、问题：5.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ꢀ）。选项：A、2B、3C、4D、6正确答案:【3】栈与递归随堂测验1、问题：1.设计一个判别表达式中括号是否配对的算法，采用（）数据结构最佳。选项：A、顺序表B、链表C、栈D、队列正确答案:【栈】2、问题：2.将递归算法转换成对应的非递归算法时，通常需要使用（）来保存中间结果。选项：A、队列B、链表C、树D、栈正确答案:【栈】3、问题：3.设有一个递归算法如下intfact(intn){//n大于等于0if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。选项：A、n+1B、n-1C、nD、n+2正确答案:【n+1】4、问题：4.一个递归算法必须包括（ꢀ）。选项：A、递归部分B、终止条件和递归部分C、迭代部分D、终止条件和迭代部分正确答案:【终止条件和递归部分】5、问题：5.任何一个递归过程都可以转换成非递归过程。选项：A、正确B、错误正确答案:【正确】队列的表示和操作的实现随堂测验1、问题：1.判断一个循环队列Q（最多n个元素）为满的条件是（）选项：A、Q-rear==Q-frontB、Q-rear==Q-front+1C、Q-front==(Q-rear+1)%nD、Q-front==(Q-rear-1)%n正确答案:【Q-front==(Q-rear+1)%n】2、问题：2.依次在初始为空的队列中插入元素a,b,c,d以后，紧接着做了两次删除操作，此时的队头元素是（）。选项：A、aB、bC、cD、d正确答案:【c】3、问题：3.在一个链队列中，假定front和rear分别为队头指针和队尾指针，删除一个结点的操作是（）。选项：A、front=front-nextB、rear=rear-nextC、rear-next=frontD、front-next=rear正确答案:【front=front-next】4、问题：4.队和栈的主要区别是（）。选项：A、逻辑结构不同B、存储结构不同C、所包含的运算个数不同D、限定插入和删除的位置不同正确答案:【限定插入和删除的位置不同】5、问题：5.循环队列存储在数组A[0..m]中，则入队时的操作为（ꢀ）。选项：A、rear=rear+1B、rear=(rear+1)%(m-1)C、rear=(rear+1)%mD、rear=(rear+1)%(m+1)正确答案:【rear=(rear+1)%(m+1)】栈和队列单元作业栈和队列单元测验1、问题：若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。选项：A、5，4，3，2，1B、2，1，5，4，3C、4，3，1，2，5D、2，3，5，4，1正确答案:【4，3，1，2，5】2、问题：若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。选项：A、iB、n-iC、n-i+1D、不确定正确答案:【n-i+1】3、问题：数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。选项：A、r-fB、(n+f-r)%nC、n+r-fD、（n+r-f)%n正确答案:【（n+r-f)%n】4、问题：链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。选项：A、x=top-data;top=top-link；B、top=top-link;x=top-link；C、x=top;top=top-link；D、x=top-link；正确答案:【x=top-data;top=top-link；】5、问题：设有一个递归算法如下intfact(intn){//n大于等于0if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。选项：A、n+1B、n-1C、nD、n+2正确答案:【n+1】6、问题：栈在（）中有所应用。选项：A、递归调用B、函数调用C、表达式求值D、前三个选项都有正确答案:【前三个选项都有】7、问题：为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。选项：A、队列B、栈C、线性表D、有序表正确答案:【队列】8、问题：设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（ꢀ）。选项：A、2B、3C、4D、6正确答案:【3】9、问题：用链接方式存储的队列，在进行删除运算时（ꢀ）。选项：A、仅修改头指针B、仅修改尾指针C、头、尾指针都要修改D、头、尾指针可能都要修改正确答案:【头、尾指针可能都要修改】10、问题：最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ꢀ）。选项：A、(rear+1)%n==frontB、rear==frontC、rear+1==frontD、(rear-l)%n==front正确答案:【rear==front】11、问题：两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。选项：A、正确B、错误正确答案:【正确】12、问题：队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。选项：A、正确B、错误正确答案:【错误】13、问题：通常使用队列来处理函数或过程的调用。选项：A、正确B、错误正确答案:【错误】14、问题：栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。选项：A、正确B、错误正确答案:【正确】15、问题：栈和队列都是受限的线性结构。选项：A、正确B、错误正确答案:【正确】16、填空题：在具有n个元素的循环队列中，队满时具有（）个元素。正确答案:【n-1】17、填空题：设循环队列的容量为70，现经过一系列的入队和出队操作后，front为20，rear为11，则队列中元素的个数为（）。正确答案:【61】18、填空题：为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（）分别设在这片内存空间的两端，这样只有当两个栈的栈顶在栈空间的某一位置相遇时才产生上溢。正确答案:【栈底】19、填空题：判定一个顺序栈S（栈空间大小为n）为空的条件是（）。正确答案:【S->top==0；S.top==0】20、填空题：循环队列的引入，目的是为了克服（）。正确答案:【假溢出时大量移动数据元素】串的定义随堂测验1、问题：1.串与普通的线性表相比较，它的特殊性体现在（）选项：A、顺序的存储结构B、链式存储结构C、数据元素是一个字符D、数据元素任意正确答案:【数据元素是一个字符】2、问题：2.空串和空格串（）。选项：A、相同B、不相同C、可能相同D、无法确定正确答案:【不相同】3、问题：3.与线性表相比，串的操作的特点是（）选项：A、算法的时间复杂度较高B、通常以串整体作为操作对象C、需要更多的辅助空间D、涉及移动的元素更多正确答案:【通常以串整体作为操作对象】4、问题：4.串下面关于串的的叙述中，（）是不正确的？选项：A、串是字符的有限序列B、空串是由空格构成的串C、模式匹配是串的一种重要运算D、串既可以采用顺序存储，也可以采用链式存储正确答案:【空串是由空格构成的串】5、问题：5.下面的说法中，只有（）是正确的。选项：A、字符串的长度是指串中包含的字母的个数B、字符串的长度是指串中包含的不同字符的个数C、若T包含在S中，则T一定是S的一个子串D、一个字符串不能说是其自身的一个子串正确答案:【字符串的长度是指串中包含的不同字符的个数】串的类型定义、存储结构及其运算随堂测验1、问题：1.设有两个串S1和S2，求串S2在S1中首次出现位置的运算称作（）。选项：A、连接B、求子串C、模式匹配D、判断子串正确答案:【模式匹配】2、问题：3.设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’BeijingNanjing’，SUBSTR(S,4,5)=（）。选项：A、‘ijing’B、‘jing’C、‘ingNa’D、‘ingN’正确答案:【‘jing’】3、问题：4.字符串采用结点大小为1的链表作为其存储结构，是指（）。选项：A、链表的长度为1B、链表中只存放1个字符C、链表的每个链结点的数据域中不仅只存放了一个字符D、链表的每个链结点的数据域中只存放了一个字符正确答案:【链表的每个链结点的数据域中只存放了一个字符】4、问题：2.两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同。选项：A、正确B、错误正确答案:【正确】5、问题：5.KMP算法的最大特点是指示主串的指针不需要回溯。选项：A、正确B、错误正确答案:【正确】数组随堂测验1、问题：1.数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是()。选项：A、1175B、1180C、1205D、1210正确答案:【1175】2、问题：2.二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（）的起始地址相同。设每个字符占一个字节。选项：A、A[8,5]B、A[3,10]C、A[5,8]D、A[0,9]正确答案:【A[3,10]】3、问题：3.数组不能作为任何二叉树的存储结构。选项：A、正确B、错误正确答案:【错误】4、问题：4.从逻辑结构上看，n维数组的每个元素均属于n个向量。选项：A、正确B、错误正确答案:【正确】5、问题：5.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。选项：A、正确B、错误正确答案:【错误】广义表随堂测验1、问题：1.广义表((a,b,c,d))的表头是（）。选项：A、aB、()C、(a,b,c,d)D、(b,c,d)正确答案:【(a,b,c,d)】2、问题：2.设广义表L=((a,b,c))，则L的长度和深度分别为（）。选项：A、1和1B、1和3C、1和2D、2和3正确答案:【1和2】3、问题：4.对特殊矩阵采用压缩存储的目的主要是为了（ꢀꢀꢀ）选项：A、表达变得简单B、对矩阵元素的存取变得简单C、去掉矩阵中的多余元素D、减少不必要的存储空间正确答案:【减少不必要的存储空间】4、问题：3.广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。选项：A、正确B、错误正确答案:【错误】5、填空题：5.当广义表中的每个元素都是原子时，广义表便成了（）。正确答案:【线性表】树和二叉树的定义随堂测验1、问题：1.如果结点A有3个兄弟，B是A的双亲，则结点B的度是（ꢀꢀ）选项：A、1B、2C、3D、4正确答案:【4】2、问题：2.设二叉树有n个结点，则其深度为（）。选项：A、n-1B、nC、1D、不能确定正确答案:【不能确定】3、问题：3.由3个结点可以构造出多少种不同的二叉树？（）选项：A、2B、3C、4D、5正确答案:【5】4、问题：4.二叉树是度为2的树。选项：A、正确B、错误正确答案:【错误】5、填空题：5.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。正确答案:【12】树和二叉树的抽象数据类型定义随堂测验1、问题：1.假定一个三叉树的结点数为50，则它的最小高度是（）选项：A、3B、4C、5D、6正确答案:【4】2、问题：2.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。选项：A、正确B、错误正确答案:【错误】3、问题：3.度小于等于2的有序树即为二叉树。选项：A、正确B、错误正确答案:【错误】4、问题：5.树的子树是有序的。选项：A、正确B、错误正确答案:【错误】5、填空题：4.由3个结点可以构造出（）种不同的二叉树正确答案:【5】二叉树的性质和存储结构随堂测验1、问题：4.一个具有1025个结点的二叉树的高h为（）。选项：A、11B、10C、11至1025之间D、10至1024之间正确答案:【11至1025之间】2、问题：1.完全二叉树的某结点若无左孩子，则它必是叶结点。选项：A、正确B、错误正确答案:【正确】3、问题：2.对任一满二叉树，其分枝数B＝2(n0-1)。（其中，n0为终端结点数）选项：A、正确B、错误正确答案:【正确】4、问题：5.二叉树是树的特殊形式。选项：A、正确B、错误正确答案:【错误】5、填空题：3.具有100个结点的完全二叉树的叶子结点数为（）正确答案:【50】遍历二叉树和线索二叉树随堂测验1、问题：1.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用（）遍历方法最合适。选项：A、前序B、中序C、后序D、按层次正确答案:【后序】2、问题：2.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用（）遍历实现编号。选项：A、先序B、中序C、后序D、从根开始按层次遍历正确答案:【后序】3、问题：3.一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（）。选项：A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树正确答案:【只有一个叶子结点】4、问题：4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为（）。选项：A、X的双亲B、X的左子树中最右结点C、X的左子树中最右叶结点D、X的右子树中最左的结点正确答案:【X的左子树中最右结点】5、问题：5.引入二叉线索树的目的是（）。选项：A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一正确答案:【加快查找结点的前驱或后继的速度】树和森林随堂测验1、问题：1.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。选项：A、n?1B、nC、n+1D、n+2正确答案:【n+1】2、问题：2.在下列存储形式中，（）不是树的存储形式？选项：A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法正确答案:【顺序存储表示法】3、问题：3.利用二叉链表存储树，则根结点的右指针是（）。选项：A、指向最左孩子B、指向最右孩子C、空D、非空正确答案:【空】4、问题：4.把一棵树转换为二叉树后，这棵二叉树的形态是（）。选项：A、唯一的B、有多种C、有多种，但根结点都没有左孩子D、有多种，但根结点都没有右孩子正确答案:【唯一的】5、问题：5.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（）个。选项：A、n?1B、nC、n+1D、n+2正确答案:【n+1】哈夫曼树及其应用随堂测验1、问题：1.设哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。选项：A、99B、100C、101D、102正确答案:【100】2、问题：2.n（n≥2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是（）。选项：A、该树一定是一棵完全二叉树B、树中一定没有度为1的结点C、树中两个权值最小的结点一定是兄弟结点D、树中任一非叶结点的权值一定不小于下一层任一结点的权值正确答案:【该树一定是一棵完全二叉树】3、问题：3.已给出如图所示哈夫曼树，那么电文CDAA的编码是()。选项：A、110100B、11011100C、010110111D、11111100正确答案:【11011100】4、问题：4.上一题图中所示二叉树，A,B,C,D分别带权值为7，5，2，4则该树的带权路径长度为（）。选项：A、46B、36C、35D、都不是正确答案:【35】5、填空题：5.由n个权值构成的哈夫曼树共有（）个结点。正确答案:【2n-1】树和二叉树单元作业树和二叉树单元测验1、问题：已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()选项：A、-A+B*C/DEB、-A+B*CD/EC、-+*ABC/DED、-+A*BC/DE正确答案:【-+A*BC/DE】2、问题：设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）选项：A、5B、6C、7D、8正确答案:【8】3、问题：设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）选项：A、m-nB、m-n-1C、n+1D、条件不足，无法确定正确答案:【m-n】4、问题：若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）选项：A、9B、11C、15D、不确定正确答案:【11】5、问题：一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。选项：A、250B、500C、254D、以上答案都不对正确答案:【以上答案都不对】6、问题：有n个叶子的哈夫曼树的结点总数为（）。选项：A、2nB、2n+1C、2n-1D、不确定正确答案:【2n-1】7、问题：一个具有1025个结点的二叉树的高h为（）选项：A、11B、10C、11至1025之间D、10至1024之间正确答案:【11至1025之间】8、问题：在下列存储形式中，哪一个不是树的存储形式？（）选项：A、双亲表示法B、孩子链表表示法C、孩子兄弟表示法D、顺序存储表示法正确答案:【顺序存储表示法】9、问题：某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。选项：A、空或只有一个结点B、任一结点无左子树C、高度等于其结点数D、任一结点无右子树正确答案:【高度等于其结点数】10、问题：引入二叉线索树的目的是（A）选项：A、加快查找结点的前驱或后继的速度B、为了能在二叉树中方便的进行插入与删除C、为了能方便的找到双亲D、使二叉树的遍历结果唯一正确答案:【加快查找结点的前驱或后继的速度】11、问题：完全二叉树一定存在度为1的结点选项：A、正确B、错误正确答案:【错误】12、问题：二叉树的遍历只是为了在应用中找到一种线性次序。选项：A、正确B、错误正确答案:【正确】13、问题：采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。选项：A、正确B、错误正确答案:【正确】14、问题：当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。选项：A、正确B、错误正确答案:【错误】15、问题：用链表存储包含n个结点的二叉树时，结点的2n个指针区域中有n+1个空指针。选项：A、正确B、错误正确答案:【正确】16、填空题：具有256个结点的完全二叉树的深度为（）正确答案:【9】17、填空题：假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是（）。正确答案:【n】18、填空题：已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（）正确答案:【99】19、填空题：在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）（填相同或不相同）正确答案:【相同】20、填空题：若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为（）正确答案:【X的左子树中最右结点】图的定义和基本术语随堂测试1、问题：1.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。选项：A、1/2B、1C、2D、4正确答案:【2】2、问题：2.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。选项：A、1/2B、1C、2D、4正确答案:【1】3、问题：3.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1íV2,E1íE2则称（）。选项：A、G1是G2的子图B、G2是G1的子图C、G1是G2的连通分量D、G2是G1的连通分量正确答案:【G1是G2的子图】4、问题：4.图的连通分量是无向图的极小连通子图。选项：A、正确B、错误正确答案:【错误】5、填空题：5.设无向图G中顶点数为n，则图G至少有（）条边。正确答案:【0】图的类型定义随堂测验1、问题：1.设无向图的顶点个数为n，则该图最多有（）条边。选项：A、n-1B、n(n-1)/2C、n(n+1)/2D、0正确答案:【n(n-1)/2】2、问题：2.树中的结点和图中的顶点就是指数据结构中的数据元素。选项：A、正确B、错误正确答案:【正确】3、问题：3.连通分量指的是有向图中的极大连通子图。选项：A、正确B、错误正确答案:【错误】4、填空题：4.G是一个非连通无向图，共有28条边，则该图至少有______个顶点。正确答案:【9】5、填空题：5.有n个顶点的有向图，至少需要量______条弧才能保证是连通的。正确答案:【n-1】图的存储结构随堂测验1、问题：1.n个顶点的连通图用邻接距阵表示时，该距阵至少有（）个非零元素。选项：A、nB、2(n-1)C、n/2D、n*n正确答案:【2(n-1)】2、问题：2.已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应（）。选项：A、将邻接矩阵的第i行删除B、将邻接矩阵的第i行元素全部置为0C、将邻接矩阵的第i列删除D、将邻接矩阵的第i列元素全部置为0正确答案:【将邻接矩阵的第i行元素全部置为0】3、问题：3.无向图的邻接矩阵是一个（）。选项：A、对称矩阵B、零矩阵C、上三角矩阵D、对角矩阵正确答案:【对称矩阵】4、问题：4.用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。选项：A、正确B、错误正确答案:【正确】5、问题：5.已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是求第j列的所有元素之和。选项：A、正确B、错误正确答案:【正确】图的遍历随堂测验1、问题：1.用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。选项：A、栈B、队列C、树D、堆正确答案:【队列】2、问题：2.深度优先遍历类似于二叉树的（）。选项：A、先序遍历B、中序遍历C、后序遍历D、层次遍历正确答案:【先序遍历】3、问题：3.下列关于图遍历的说法不正确的是（）。选项：A、连通图的深度优先搜索是一个递归过程B、图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C、非连通图不能用深度优先搜索法D、图的遍历要求每一顶点仅被访问一次正确答案:【非连通图不能用深度优先搜索法】4、问题：4.对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。选项：A、正确B、错误正确答案:【错误】5、问题：5.广度遍历生成树描述了从起点到各顶点的最短路径。选项：A、正确B、错误正确答案:【错误】图的应用随堂测验1、问题：1.已知一个有向图的边集为{a,b,a,c,a,d,b,d,b,e,d,e}，则由该图产生的一种可能的拓扑序列为()选项：A、a,b,c,d,eB、a,b,d,e,bC、a,c,b,e,dD、a,c,d,b,e正确答案:【a,b,c,d,e】2、问题：2.下面（ꢀ）算法适合构造一个稀疏图G的最小生成树。选项：A、Prim算法B、Kruskal算法C、Floyd算法D、Dijkstra算法正确答案:【Kruskal算法】3、问题：3.在n个结点的无向图中，若边数n-1，则该图必是连通图。选项：A、正确B、错误正确答案:【错误】4、问题：4.关键路径是事件结点网络中从源点到汇点的最长路径。选项：A、正确B、错误正确答案:【正确】5、问题：5.在AOE网中一定只有一条关键路径。选项：A、正确B、错误正确答案:【错误】图单元作业图单元测验1、问题：n个结点的完全有向图含有边的数目（ꢀ）。选项：A、n*nB、n（n＋１）C、n／2D、n*（n－l）正确答案:【n*（n－l）】2、问题：用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为()。选项：A、5B、6C、8D、9正确答案:【5】3、问题：下列哪一种图的邻接矩阵是对称矩阵？（）选项：A、有向图B、无向图C、AOV网D、AOE网正确答案:【无向图】4、问题：无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。选项：A、a,b,e,c,d,fB、a,c,f,e,b,dC、a,e,b,c,f,dD、a,e,d,f,c,b正确答案:【a,e,d,f,c,b】5、问题：关键路径是事件结点网络中（）。选项：A、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长回路D、最短回路正确答案:【从源点到汇点的最长路径】6、问题：要连通具有n个顶点的有向图，至少需要（）条边。选项：A、n-1B、nC、n+1D、2n正确答案:【n】7、问题：图中有关路径的定义是（）。选项：A、由顶点和相邻顶点序偶构成的边所形成的序列B、由不同顶点所形成的序列C、由不同边所形成的序列D、上述定义都不是正确答案:【由顶点和相邻顶点序偶构成的边所形成的序列】8、问题：下面结构中最适于表示稀疏无向图的是（）。选项：A、邻接矩阵B、逆邻接表C、邻接多重表D、十字链表正确答案:【邻接多重表】9、问题：下面哪一方法可以判断出一个有向图是否有环（回路）：（）选项：A、求最小生成树B、拓扑排序C、求最短路径D、求关键路径正确答案:【拓扑排序】10、问题：下列关于AOE网的叙述中，不正确的是（）。选项：A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，那么整个工程将会提前完成C、所有的关键活动提前完成，那么整个工程将会提前完成D、某些关键活动提前完成，那么整个工程将会提前完成正确答案:【任何一个关键活动提前完成，那么整个工程将会提前完成】11、问题：用邻接矩阵表示图进行深度优先遍历时，通常是采用队列来实现算法的。选项：A、正确B、错误正确答案:【错误】12、问题：n个顶点的连通图，至少有n-1条边。选项：A、正确B、错误正确答案:【正确】13、问题：有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。选项：A、正确B、错误正确答案:【错误】14、问题：若连通图G中的一条边e是所以边中权值最小的边，则图G必存在着一最小生成棵包含边e的最小生成树。选项：A、正确B、错误正确答案:【正确】15、问题：任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。选项：A、正确B、错误正确答案:【错误】16、填空题：有向图G的强连通分量是指（）。正确答案:【极大强连通子图】17、填空题：一个连通图的（）是一个极小连通子图正确答案:【生成树】18、填空题：求图的最小生成树有两种算法，（）算法适合于求稀疏图的最小生成树。正确答案:【kruskal（克鲁斯卡尔）】19、填空题：对于一个具有n个顶点e条边的无向图的邻接表的表示，邻接表的边结点个数为（）。正确答案:【2*e】20、填空题：G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。正确答案:【9】查找的基本概念随堂测验1、问题：1.静态查找与动态查找的根本区别在于（）。选项：A、它们的逻辑结构不一样B、施加在其上的操作不同C、所包含的数据元素的类型不一样D、存储实现不一样正确答案:【施加在其上的操作不同】2、问题：2.最快的查找方法是快速查找。选项：A、正确B、错误正确答案:【错误】3、问题：3.如果在一个待排序的序列中,存在2个相等的数,在排序后这2个数的相对位置保持不变,那么该排序算法是稳定的。选项：A、正确B、错误正确答案:【正确】线性表的查找随堂测验1、问题：1.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。选项：A、(n-1)/2B、n/2C、(n+1)/2D、n正确答案:【(n+1)/2】2、问题：2.适用于折半查找的表的存储方式及元素排列要求为（）。选项：A、链接方式存储，元素无序B、链接方式存储，元素无序C、顺序方式存储，元素无序D、顺序方式存储，元素有序正确答案:【顺序方式存储，元素有序】3、问题：3.折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。选项：A、20，70，30，50B、30，88，70，50C、20，50D、30，88，50正确答案:【20，70，30，50】4、问题：4.如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。选项：A、顺序查找B、折半查找C、分块查找D、哈希查找正确答案:【分块查找】5、问题：5.对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。选项：A、3B、4C、5D、6正确答案:【4】树表的查找随堂测验1、问题：1.分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。选项：A、（100，80，90，60，120，110，130）B、（100，120，110，130，80，60，90）C、（100，60，80，90，120，110，130）D、(100，80，60，90，120，130，110)正确答案:【（100，60，80，90，120，110，130）】2、问题：2.折半搜索与二叉排序树的时间性能（）。选项：A、相同B、完全不同C、有时不相同D、数量级都是O(log2n)正确答案:【有时不相同】3、问题：3.任一查找树（二叉分类树）的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.选项：A、正确B、错误正确答案:【错误】4、问题：4.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。选项：A、正确B、错误正确答案:【错误】5、问题：5.对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。选项：A、正确B、错误正确答案:【错误】散列表的查找随堂测验1、问题：1.下面关于哈希查找的说法，正确的是（）。选项：A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定D、哈希表的平均查找长度有时也和记录总数有关正确答案:【不存在特别好与坏的哈希函数，要视情况而定】2、问题：2.下面关于哈希查找的说法，不正确的是（）。选项：A、采用链地址法处理冲突时，查找一个元素的时间是相同的B、采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的C、用链地址法处理冲突，不会引起二次聚集现象D、用链地址法处理冲突，适合表长不确定的情况正确答案:【采用链地址法处理冲突时，查找一个元素的时间是相同的】3、问题：3.设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。选项：A、8B、3C、5D、9正确答案:【9】4、问题：4.采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字()。选项：A、不一定都是同义词B、一定都是同义词C、一定都不是同义词D、都相同正确答案:【不一定都是同义词】5、问题：5.将10个元素散列到100000个单元的哈希表中，则（）产生冲突。选项：A、一定会B、一定不会C、仍可能会D、不能判断正确答案:【仍可能会】查找单元作业查找单元测验1、问题：若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。选项：A、(n-1)/2B、n/2C、(n+1)/2D、n正确答案:【(n+1)/2】2、问题：用二分（对半）查找表的元素的速度比用顺序法()。选项：A、必然快B、必然慢C、相等D、不能确定正确答案:【不能确定】3、问题：下面关于二分查找的叙述正确的是()。选项：A、表必须有序，表可以顺序方式存储，也可以链表方式存储B、表必须有序且表中数据必须是整型，实型或字符型C、表必须有序，而且只能从小到大排列D、表必须有序，且表只能以顺序方式存储正确答案:【表必须有序，且表只能以顺序方式存储】4、问题：如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用()查找法。选项：A、分块查找B、顺序查找C、折半查找D、哈希查找正确答案:【分块查找】5、问题：设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。选项：A、8B、3C、5D、9正确答案:【9】6、问题：设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13，散列地址为1的链中有（）个记录。选项：A、1B、2C、3D、4正确答案:【4】7、问题：下面关于哈希(Hash，杂凑)查找的说法正确的是()。选项：A、哈希函数构造的越复杂越好，因为这样随机性好，冲突小B、除留余数法是所有哈希函数中最好的C、不存在特别好与坏的哈希函数，要视情况而定D、若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可正确答案:【不存在特别好与坏的哈希函数，要视情况而定】8、问题：列表的地址区间为0-17,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（）。选项：A、8B、9C、10D、11正确答案:【11】9、问题：分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()。选项：A、（100，80，90，60，120，110，130）B、（100，120，110，130，80，60，90）C、（100，60，80，90，120，110，130）D、(100，80，60，90，120，130，110)正确答案:【（100，60，80，90，120，110，130）】10、问题：二叉查找树的查找效率与二叉树的()有关。选项：A、高度B、结点的多少C、形状D、结点的位置正确答案:【形状】11、问题：负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。选项：A、正确B、错误正确答案:【正确】12、问题：任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。选项：A、正确B、错误正确答案:【错误】13、问题：在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。选项：A、正确B、错误正确答案:【错误】14、问题：Hash表的平均查找长度与处理冲突的方法无关。选项：A、正确B、错误正确答案:【错误】15、问题：在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。选项：A、正确B、错误正确答案:【正确】16、填空题：顺序查找n个元素的顺序表，当使用监视哨时，若查找失败，则比较关键字的次数为。正确答案:【n+1】17、填空题：在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____。正确答案:【4】18、填空题：对于具有144个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为________。正确答案:【14】19、填空题：动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。正确答案:【插入、删除】20、填空题：在哈希函数H（key）=key%p中，p值最好取__________。正确答案:【小于等于表长（不大于表长）的最大素数（质数）】基本概念和排序方法概述随堂测验1、问题：1.如果某种排序算法是不稳定的，则该排序方法没有实际应用价值。选项：A、正确B、错误正确答案:【错误】2、问题：2.当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。选项：A、正确B、错误正确答案:【正确】3、问题：3.待排序记录序列中，存在多个具有相同关键字的记录，若经过排序，这些记录的相对次序保持不变，则称为稳定排序。选项：A、正确B、错误正确答案:【正确】4、问题：4.内部排序要求数据一定要以顺序方式存储。选项：A、正确B、错误正确答案:【错误】5、问题：5.在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。选项：A、正确B、错误正确答案:【错误】插入排序随堂测验1、问题：1.从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。选项：A、归并排序B、冒泡排序C、插入排序D、选择排序正确答案:【插入排序】2、问题：2.对5个不同的数据元素进行直接插入排序，最多需要进行（）次比较？选项：A、8B、10C、15D、25正确答案:【10】3、问题：3.若待排序对象序列在排序前已按其排序码递增顺序排列，则采用（）方法比较次数最少。选项：A、直接插入排序B、快速排序C、归并排序D、选择排序正确答案:【直接插入排序】4、问题：4.对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是()。选项：A、1B、4C、3D、2正确答案:【2】5、问题：5.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。选项：A、正确B、错误正确答案:【错误】交换排序随堂测验1、问题：1.对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。选项：A、从小到大排列好的B、从大到小排列好的C、元素无序D、元素基本有序正确答案:【从大到小排列好的】2、问题：2.对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。选项：A、n+1B、nC、n-1D、n(n-1)/2正确答案:【n(n-1)/2】3、问题：3.快速排序在下列（）情况下最易发挥其长处。选项：A、被排序的数据中含有多个相同排序码B、被排序的数据已基本有序C、被排序的数据完全无序D、被排序的数据中的最大值和最小值相差悬殊正确答案:【被排序的数据完全无序】4、问题：4.若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。选项：A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，79正确答案:【40，38，46，56，79，84】5、问题：5.对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（）。选项：A、1,3,5,7,9B、9,7,5,3,1C、5,3,1,7,9D、5,7,9,1,3正确答案:【5,7,9,1,3】选择排序随堂测验1、问题：1.下列关键字序列中，（）是堆。选项：A、16，72，31，23，94，53B、94，23，31，72，16，53C、16，53，23，94，31，72D、16，23，53，31，94，72正确答案:【16，23，53，31，94，72】2、问题：2.堆的形状是一棵（）。选项：A、二叉排序树B、满二叉树C、完全二叉树D、平衡二叉树正确答案:【完全二叉树】3、问题：3.若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。选项：A、79，46，56，38，40，84B、84，79，56，38，40，46C、84，79，56，46，40，38D、84，56，79，40，46，38正确答案:【84，79，56，38，40，46】4、问题：4.堆排序所需的时间与待排序的记录个数无关。选项：A、正确B、错误正确答案:【错误】5、问题：5.设有键值序列（k1,k2,…,kn），当in/2时，任何一个子序列（ki,ki+1,…,kn）一定是堆。选项：A、正确B、错误正确答案:【正确】归并排序随堂测验1、问题：1.下述几种排序方法中，要求内存最大的是（）。选项：A、希尔排序B、快速排序C、归并排序D、堆排序正确答案:【归并排序】2、问题：2.下述几种排序方法中，（）是稳定的排序方法。选项：A、希尔排序B、快速排序C、归并排序D、堆排序正确答案:【归并排序】3、问题：3.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做（）排序。选项：A、直接插入排序B、二路归并排序C、堆排序D、希尔排序正确答案:【二路归并排序】4、问题：4.若对n个元素进行归并排序，则进行归并的趟数为（）。选项：A、nB、n-1C、n/2D、log2n正确答案:【log2n】5、问题：5.归并排序一种典型的分而治之思想的算法应用。选项：A、正确B、错误正确答案:【正确】客观题试卷1、问题：算法指的是（）。选项：A、对特定问题求解步骤的一种描述，是指令的有限序列。B、计算机程序C、解决问题的计算方法D、数据处理正确答案:【对特定问题求解步骤的一种描述，是指令的有限序列。】2、问题：假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。选项：A、树B、图C、线性表D、集合正确答案:【图】3、问题：在数据结构中，从逻辑上可以把数据结构分成（）。选项：A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构正确答案:【线性结构和非线性结构】4、问题：顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。选项：A、110B、108C、100D、120正确答案:【108】5、问题：在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。选项：A、n-iB、n-i+1C、n-i-1D、I正确答案:【n-i+1】6、问题：线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。选项：A、必须是连续的B、部分地址必须是连续的C、一