2023年浙大城市学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年浙大城市学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、将线性表的数据元素进行扩充，允许带结构的线性表是（　　）。 A.串 B.树 C.广义表 D.栈 2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（　　）。 A.j=r[j].next B.j=j+l C.j=j-next D.j=r[j]-next 3、以下数据结构中，（　　）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 4、已知串S=aaab，其next数组值为（　　）。 A.0123 B.1123 C.1231 D.1211 5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛V1，V2，V1，V3，V1，V4，V2，V5，V3，V5， V3，V6，V4，V6，V5，V7，V6，V7｝，G的拓扑序列是（　　）。 A.V1，V3，V4，V6，V2，V5，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7 6、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 7、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、就平均性能而言，目前最好的内排序方法是（　　）排序法。 A.起泡 B.希尔插入 C.交换 D.快速 二、填空题 11、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是______算法，最费时间的是______算法。 12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。 13、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 15、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。 16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 17、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。 18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85的地址为______。 三、判断题 19、倒排序文件的优点是维护简单。（　　） 20、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 22、二维以上的数组其实是一种特殊的广义表。（　　） 23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（　　） 24、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（　　） 25、在待排数据基本有序的情况下，快速排序效果最好。（　　） 26、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（　　） 27、无环有向图才能进行拓扑排序。（　　） 28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（　　） 四、简答题 29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0