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

2023年温州理工学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下述文件中适合于磁带存储的是（　　）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（　　）排序法。 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、动态存储管理系统中，通常可有（　　）种不同的分配策略。 A.1 B.2 C.3 D.4 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（　　）个叶子。 A.log2n B.（n－1）/2 C.log2n+1 D.（n＋1）/2 9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（　　）个不同的码字。 A.107 B.108 C.214 D.215 10、下列二叉排序树中查找效率最高的是（　　）。 A.平衡二叉树 B.二叉查找树 C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 二、填空题 11、属于不稳定排序的有______。 12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。 （2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 15、索引顺序文件既可以顺序存取，也可以______存取。 16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。 17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。 三、判断题 19、文件系统采用索引结构是为了节省存储空间。（　　） 20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　） 21、稀疏矩阵压缩存储后，必会失去随机存取功能。（　　） 22、一个广义表可以为其他广义表所共享。（　　） 23、深度为k的二叉树中结点总数小于等于2k-1。（　　） 24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（　　） 26、顺序存储结构的主要缺点是不利于插入或删除操作。（　　） 27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（　　） 28、B-树中所有结点的平衡因子都为零。（　　） 四、简答题 29、已知n阶下三角矩阵A（即当i＜j时，有aij=0），按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中，请写出从第一列开始采用列序为主序分配方式时在B 中确定元素aij的存放位置的公式。 30、请写出应填入下列叙述中（　　）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一