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

2022年湖南人文科技学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.402、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、以下与数据的存储结构无关的术语是（）。A.循环队列B.链表C.哈希表D.栈4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝28、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、数据结构中评价算法的两个重要指标是______。14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排序文件的优点是维护简单。（）21、一个广义表可以为其他广义表所共享。（）22、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）23、对于有n个结点的二叉树，其高度为log2n。（）24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）25、顺序存储结构的主要缺点是不利于插入或删除操作。（）26、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、已知n阶下三角矩阵A（即当i＜j时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B中确定元素aij的存放位置的公式。30、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）。31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)（1）画出这六大城市的交通网络图。（2）画出该图的邻接表表示法。（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。五、算法设计题32、以顺序存储结构表示串，设计算法。求串s中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。33、已知一棵二叉树的前序遍历序列和中序遍历序列分别存于两个一维数组中，试编写算法建立该二叉树的二叉链表。34、对给定关键字序号j（1<j<n），要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时间和最少的空间）。例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。35、设稀疏矩阵Mm×n中有t个非零元素，用三元组顺序表的方式存储。请设计一个算法，计算矩阵M的转置矩阵N，要求转置算法的时间复杂度为O（n+t）。

参考答案一、选择题1、【答案】B2、【答案】A3、【答案】D4、【答案】B5、【答案】D6、【答案】D7、【答案】C8、【答案】B9、【答案】D10、【答案】A二、填空题11、【答案】n；n+112、【答案】2(n-1)13、【答案】算法的时间复杂度和空间复杂度14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2)①T[k]；toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i]；fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}，ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u，v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。15、【答案】分配和释放存储空间；重组；对插入的记录@16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。18、【答案】23；100CH三、判断题19、【答案】√20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】√25、【答案】√26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：2阶下三角矩阵元素A[i][j]（1≤i，j≤n，i≥j）。第1列有n个元素，第j列有n-j+1个元素，第1列到第j-1列是梯形，元素数为（n+（n-j+2）（j-1）/2，而aij在第j列上的位置是为i-j+1。所以n阶下三角矩阵A按列存储，其元素aij在一维数组B中的存储位置k与i和j的关系为：30、答：森林转换为二叉树分以下三步：连线（将兄弟结点相连，各树的根看作兄弟）。切线（保留最左边子女为独生子女，将其他子女分支切掉）。旋转（以最左边树的根为轴，顺时针向下旋转45度）。所以由上面三棵树转换得到的二叉树如图所示：31、答：(1)这六大城市的交通网络图如图所示：