2022年上海师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年上海师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（　　）。 A.60 B.66 C.18000 D.33 2、无向图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，f B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b 3、算法的计算量的大小称为计算的（　　）。 A.效率 B.复杂性 C.现实性 D.难度 4、在用邻接表表示图时，拓扑排序算法时间复杂度为（　　）。 A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n) 5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（　　）。 A.543612 B.453126 C.346521 D.234156 6、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 7、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（　　）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（　　）。 A.直接插入排序 B.起泡排序 C.简单选择排序 D.快速排序 二、填空题 11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。 12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。 13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。 14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。 15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。 17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85的地址为______。 18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 三、判断题 19、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 20、文件系统采用索引结构是为了节省存储空间。（　　） 21、广义表（（（a，b，c），d，e，f））的长度是4。（　　） 22、串是一种数据对象和操作都特殊的线性表。（　　） 23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（　　） 24、树形结构中元素之间存在一对多的关系。（　　） 25、归并排序辅助存储为O（1）。（　　） 26、在待排数据基本有序的情况下，快速排序效果最好。（　　） 27、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（　　） 28、无环有向图才能进行拓扑排序。（　　） 四、简答题 29、写出下列排序算法的基本思想，并写出对序列（23，12，35，47， 16，25，36，19，21，16）进行排序时每一趟的结果。 30、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’ （1）计算模式p的nextv