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

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