2022年海南热带海洋学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年海南热带海洋学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.332、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modMB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modMD．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（）的两趟排序后的结果。A.选择排序B.起泡排序C.插入排序D.堆排序二、填空题11、在哈希函数H（key）=key%p中，p值最好取______。12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。13、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。14、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。15、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶点号从0开始计。(2)indegree是有n个分量的一维数组，放顶点的入度，(3)函数crein用于计算顶点入度。(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。18、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排文件的目的是为了多关键字查找。（）21、数组不适合作为任何二叉树的存储结构。（）22、广义表（（（a，b，c），d，e，f））的长度是4。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）25、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）26、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54，需依次与哪些元素比较?（3）若查找元素90，需依次与哪些元素比较?（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。31、已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想。（2）描述算法的详细实现步骤。（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。五、算法设计题32、设计将数组A[n]中所有的偶数移到奇数之前的算法。要求不增加存储空间，且时间复杂性为O（n）。33、假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。（1） 下面所示的序列中哪些是合法的?A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIO（2） 通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。34、按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)35、叙述基数排序算法，并对下列整数序列图示其基数排序的全过程。（179，208，93，306，55，859，984，9，271，33）

参考答案一、选择题1、【答案】B2、【答案】A3、【答案】B4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】B9、【答案】D10、【答案】C二、填空题11、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数12、【答案】480+8=488；480-32=44813、【答案】（n-1）/214、【答案】逻辑结构；物理结构；操作（运算）；算法15、【答案】0；j；i；0；indegree[i]=0；[vex][i]；k==l；indegree[i]=0【解析】有向图用邻接矩阵表示时，顶点i的入度等于第i列的所有元素之和。拓扑排序过程：首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其他顶点的入度减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。16、【答案】模式匹配；模式串17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。18、【答案】（）；（（））；2；2三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】×23、【答案】√24、【答案】×25、【答案】√26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）判定树如图所示：（2） 若查找元素54，需依次和元素30、63、42、54比较，查找成功。（3） 若查找元素90，需依次和元素30、63、87、95比较，查找失败。（4）30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。（2）算法的详细实现步骤①count＝0，p和q指向链表表头结点的下一个结点。②