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

2023年南通理工学院数据科学与大数据技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、下列排序算法中，占用辅助空间最多的是（　　）。 A.归并排序 B.快速排序 C.希尔排序D.堆排序 3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（　　）存储方式最节省时间。 A.顺序表 B.双链表 C.带头结点的双循环链表 D.单循环链表 4、在下列表述中，正确的是（　　） A.含有一个或多个空格字符的串称为空格串 B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 5、下列关于AOE网的叙述中，不正确的是（　　）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成 6、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 7、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 9、有关二叉树下列说法正确的是（　　）。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（　　）。 A.（2，5，12，16）26（60，32，72） B.（5，16，2，12）28（60，32，72） C.（2，16，12，5）28（60，32，72） D.（5，16，2，12）28（32，60，72） 二、填空题 11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用a，b，d 三元组表示弧a，b及弧上的权d。E(G)为E(G)=｛0，5，100，0， 2，10，1，2，5，0，4，30，4，5，60，3，5，10，2， 3，50，4，3，20｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。 13、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 14、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。 17、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。 18、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（　　） 21、在链队列中，即使不设置尾指针也能进行入队操作。（　　） 22、数组不适合作为任何二叉树的存储结构。（　　） 23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么 从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（　　） 25、为了很方便地