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

2022年湖南理工学院南湖学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图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，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.403、线性表的顺序存储结构是一种（）。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、下列二叉排序树中查找效率最高的是（）。A.平衡二叉树B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。13、索引顺序文件既可以顺序存取，也可以______存取。14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。15、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。16、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。17、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、倒排文件的目的是为了多关键字查找。（）21、循环队列也存在空间溢出问题。（）22、数组不适合作为任何二叉树的存储结构。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）四、简答题29、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：30、下面程序段的时间复杂度是什么？31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。(2)以顶点V1为出发点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法（注：已知树中的结点数）。33、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。34、输入一个字符串，内有数字和非数字字符，如：ak123x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[0]，456放入a[1]，……。编程统计其共有多少个整数，并输出这些数。35、编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：它们已用val域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由right（down）域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

参考答案一、选择题1、【答案】D2、【答案】B3、【答案】A4、【答案】C5、【答案】B6、【答案】A7、【答案】D8、【答案】B9、【答案】B10、【答案】A二、填空题11、【答案】（n+1）/212、【答案】起泡；快速13、【答案】随机14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）15、【答案】逻辑结构；物理结构；操作（运算）；算法16、【答案】’xyxyxywwy’17、【答案】（）；（（））；2；218、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。三、判断题19、【答案】×20、【答案】√21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次数如表1-1所示。执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5对，f（5）=55，执行过程中，输出结果为：30、答：赋值语句一共被执行了m