雨课堂学堂在线学堂云《数据结构与算法（大连民族大学）》单元测试考核答案

数据结构与算法第1题算法的描述方法通常有____、____、____、____等,其中,____被称为算法语言。第2题算法具有五个特性,分别是____、____、____、____和____。第3题算法分析的目的是(),算法分析的两个主要方面是()。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性第4题顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中的数据元素之间的逻辑关系是由()表示的。A线性结构B非线性结构C存储位置D指针第6题对于一个具有n个结点的单链表,在p所指结点后插入一个结点的是时间复杂度为____,在给定值为x的结点后,在链表最后插入新结点的时间复杂度为____。第7题在一个长度为n的顺序表中删除第i个元素【】时,需向前移动____个元素。第8题设r指向单循环链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是（____）；r->next=s;r=s;。第9题在单链表中，指针p所指结点为最后一个结点的条件是（____）。第10题在单链表中,若p和s是两个指针,且满足p->next与s相同,则语句p->next=s->next作用是____s所指向结点。第11题设head指向单链表的表头,p指向单链表的表尾结点,则执行p->next=head后,该单链表构成____。第12题从一个具有n个结点的单链表中查找值等于x的结点时,在查找成功的情况下,需要平均比较()个结点。ABnCD第13题链表是一种采用()存储结构存储的线性表。A顺序B链式C星式D网状第14题线性表采用链式地址时,其地址()。A必须是连续的B一定是不连续的C连续与否均可以D部分地址必须是连续的第三章作业第3题设栈S和队列Q的初始状态为空,元素e1、e2、e3、e4、e5、e6依次入栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e2、e4、e3、e6、e5、e1,则栈S的容量至少应该是()。A6B4C3D2第4题栈和队列的主要区别在于()。A它们的逻辑结构不一样B它们的存储结构不一样C所包含的运算不一样D插入、删除运算的限定不一样第5题在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区,该缓冲区应该是一个()结构。A栈B队列C数组D线性表第6题一个队列的入队顺序是1,2,3,4,则队列的输出顺序是()。A4321B1234C1432D3241第7题允许对队列实施的操作有()。A对队列中的元素排序B取出最近进队的元素C在队头元素之前插入元素D删除队头元素第8题循环队列存储在数组A[0..m]中,则入队时的操作为()。Arear=rear+1Brear=(rear+1)%(m-1)Crear=(rear+1)%mDrear=(rear+1)%(m+1)第9题数组q[]存储一个循环队列,first和last分别是首尾指针。如果使元素x出队操作的语句为“first=(first+1)%m,x=q[];”。那么元素x进队的语句是()。Alast=(last+1)%m,q[last]=x;Bx=q[last],last=(last+1)%m;Cq[last+1]=x;Dq[(last+1)%m]=x;第10题对于链队列,在进行删除操作时,有()。A仅修改头指针B仅修改尾指针C头、尾指针都要修改D头、尾指针可能都要修改第11题在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后,栈顶元素是()。A6B7C5D2第12题铁路进行列车调度时,常把站台设计成栈结构,若进站的六辆列车顺序为:1,2,3,4,5,6,不能产生的出栈序列是()。A435612B325641C123456D135426第四章作业第1题两个串相等的充分必要条件是()。A两个字符串存储形式相同B两个字符串的长度相等且对应位置上的字符也相等C两个字符串中对应位置上的字符相等D两个字符串的长度相等第2题设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x串和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len()返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是()。ABCDEFBBCDEFGCBCPQRSTDBCDEFEF第3题一个的对称矩阵按行优先或列优先进行压缩存储,则其存储容量为()。ABCD第4题二维数组A中,每个元素A的长度为3个字节,行下标i从0到7,列下标j从0到9,从首地址SA开始连续存放在存储器内,该数组按列序存放时,元素A[4][7]的起始地址为()。ASA+141BSA+180CSA+222DSA+225第五章作业第1题若一棵二叉树有9个度为2的结点,5个度为1的结点,则叶子结点的个数为()。A9B15C10D不确定第2题如果结点A有3个兄弟,而且B是A的双亲,则B的度是()。A2B3C4D5第3题如下图所示的4棵二叉树，（）是平衡二叉树。ABCD第4题如图所示二叉树的中序遍历序列是()。AabcdgefBdfebagcCdbaefcgDdefbagc第5题下面哪种说法是正确的()。A一个二叉树可由其先序序列和中序序列唯一确定。B一个二叉树可由其先序序列唯一确定。C一个二叉树可由其中序序列唯一确定。D一个二叉树可由其后序序列唯一确定。第6题有一棵树如图所示,回答下面的问题:⑴这棵树的根结点是____;⑵这棵树的叶子结点____;⑶结点k3的度是____;⑷这棵树的是____;⑸这棵树的深度是____;⑹结点k3的孩子是____;⑺结点k3的父结点是____。第7题对任何二叉树,若度为2的结点数为n2,则叶子数n0=____。第8题设树T的度为4,其中度为1、2、3和4的结点个数分别是4、2、1和1,则T中叶子结点的个数是____。第9题已知二叉树中叶子结点数为40,仅有一个孩子的结点数为20,则总结点数____。第10题设有30个值,用它们构造一棵哈夫曼树,则该哈夫曼树中共有____个结点。第七章查找第1题关于折半查找,以下说法正确的是()。A静态查找表B动态查找表C静态查找表与动态查找表D两种表都不适合第2题解决哈希查找方法中出现的冲突问题常采用的方法是()。A数字分析法、除留余数法、平方取中法B数字分析法、除留余数法、线性探测法C数字分析法、线性探测法、再哈希法D线性探测法、再哈希法、链地址法第3题有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当折半查找值为82的结点时,()次比较后查找成功。A1B2C4D8第4题设哈希表长m=14,哈希函数。表中已有4个结点:addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7如用二次探测再散列处理冲突,关键字为49的结点的地址是()。A8B3C5D9第5题采用顺序查找方法查找长度为n的线性表时,查找成功时的平均查找长度为().AnBCD第6题顺序查找法适合于存储结构为()的线性表。A哈希表存储B顺序存储或链式存储C压缩存储D索引存储第7题哈希表的平均查找长度()。A与处理冲突方法有关而与表的长度无关B与处理冲突方法无关而与表的长度有关C与处理冲突方法有关而与表的长度有关D与处理冲突方法无关而与表的长度无关第8题对于查找表的查找过程中,若被查找的数据元素不存在,则把该数据元素插入到集合中。这种方式主要适合于()。A静态查找表B动态查找表C静态查找表与动态查找表D两种表都不适合第9题查找成功情况下,顺序查找法的平均查找长度为____;折半查找法的平均查找长度为____;哈希表查找法采用链接法处理冲突时的平均查找长度为____。第15题采用二分查找方法查找长度为n的线性表时,查找成功时的平均查找长度为()。ABCD第六章作业第5题根据图的存储结构进行某种次序的遍历,得到的顶点序列是____的。第6题遍历图的过程实质上是____。以邻接表为存储结构,图的广度优先遍历时间复杂度为____,图的深度优先遍历时间复杂度为____,两者不同之处在于____,反映在采用的辅助数据结构上的差别(深度优先遍历采用栈存储访问过的顶点,广度优先遍历采用队列存储访问过的顶点)。第7题已知一个有向图用邻接矩阵存储,计算第i个结点的入度的方法是____。第8题在无向图G的邻接矩阵A中,若A[i][j]等于1,则A[j][i]等于____。第9题n个顶点的连通图至少____条边。第10题在图的邻接表存储结构上执行广度优先遍历类似于二叉树的____。第11题在图的邻接表存储结构上执行深度优先遍历类似于二叉树的____。第12题对于一个有向图,若一个顶点的入度为k1,出度为k2,则对应逆邻接表中该顶点单链表中的结点数为()。Ak1Bk2Ck1-k2Dk1+k2第13题用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印出相应的顶点,则输出的顶点序列是()。A逆拓朴有序的B拓朴有序的C无序的第14题判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用()。A求关键路径的方法B求最短路径的Dijkstra方法C宽度优先遍历算法D深度优先遍历算法第八章作业第1题设要将序列(Q,H,C,Y,P,A,M,S,R,D,F,X)中的关键字按升序排列,则()是增量为4的希尔排序一趟扫描的结果。A(F,H,C,D,P,A,M,Q,R,S,Y,X)B(P,A,C,S,Q,D,F,X,R,H,M,Y)C(A,D,C,R,F,Q,M,S,Y,P,H,X)D(H,C,Q,P,A,M,S,R,D,F,X,Y)第2题下述几种排序方法中,平均查找长度最小的是()。A插入排序B选择排序C快速排序D希尔排序第3题设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好选用()排序法。A起泡排序B快速排序C堆排序D基数排序第4题在堆排序,快速排序和归并排序中,若只从存储空间考虑,则应首先选取____方法,其次选取____方法,最后选取____方法;若只从排序结果的稳定性考虑,则应选取____方法;若只从平均情况下排序最快考虑,则应选取____方法;若只从最坏情况下排序最快并且要节省内存考虑,则应选取____方法。第5题对n个元素的序列进行起泡排序时，最少的比较次数是（____）。第6题在插入排序和选择排序中,若初始数据基本正序,则选用____;若初始数据基本反序,则选用____。第7题在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是____,需要内存容量最多的是____。第8题用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是()。A32,40,21,46,69,94,90,80B94,32,40,90,80,46,21,69C21,32,46,40,80,69,90,94D90,69,80,46,21,32,94,40第9题下述几种排序