2023年南昌理工学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年南昌理工学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、n个结点的完全有向图含有边的数目（　　）。 A.n*n B.n(n+1) C.n/2 D.n*(n-1) 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、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 5、下列关于AOE网的叙述中，不正确的是（　　）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成 6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（　　）个不同的码字。 A.107 B.108 C.214 D.215 9、有关二叉树下列说法正确的是（　　）。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（　　）。 A.每次分区后，先处理较短的部分 B.每次分区后，先处理较长的部分 C.与算法每次分区后的处理顺序无关 D.以上三者都不对 二、填空题 11、阅读下列程序，指出其功能，并写出空格处应填上的语句。 12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 13、建立索引文件的目的是______。 14、外排序的基本操作过程是______和______。 15、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。 16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。 17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 18、模式串P=‘abaabcac’的next函数值序列为______。 三、判断题 19、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 20、倒排序文件的优点是维护简单。（　　） 21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（　　） 22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（　　） 24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（　　） 25、抽象数据类型与计算机内部表示和实现无关。（　　） 26、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（　　） 27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（　　） 28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（　　） 四、简答题 29、将下列由三棵树组成的森林转换为二