2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A

2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A

一、选择题

　　1、下列说法不正确的是(　　)。

　　A.图的遍历是从给定的源点出发每个顶点仅被访问一次

　　B.遍历的基本方法有两种：深度遍历和广度遍历

　　C.图的深度遍历不适用于有向图

　　D.图的深度遍历是一个递归过程

　　2、下列排序算法中，占用辅助空间最多的是(　　)。

　　A.归并排序 B.快速排序 C.希尔排序D.堆排序

　　3、线性表的顺序存储结构是一种(　　)。

　　A.随机存取的存储结构 B.顺序存取的存储结构

　　C.索引存取的存储结构 D.Hash存取的存储结构

　　4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E={，，，，， ，，，｝，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

　　5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时(　　)。

　　A.仅修改队头指针

　　B.仅修改队尾指针

　　C.队头、队尾指针都可能要修改

　　D.队头、队尾指针都要修改

　　6、下列关于无向连通图特性的叙述中，正确的是(　　)。

　　Ⅰ.所有的顶点的度之和为偶数 Ⅱ.边数大于顶点个数减1 Ⅲ.至少有一个顶点的度为1

　　A.只有Ⅰ B.只有Ⅱ C.Ⅰ和Ⅱ D.Ⅰ和Ⅲ

　　7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是(　　)。

　　Ⅰ.简单选择排序Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排 Ⅴ.二路归并排序

　　A.仅Ⅰ、Ⅲ、Ⅳ B.仅Ⅰ、Ⅱ、Ⅲ C.仅Ⅱ、Ⅲ、Ⅳ D.仅Ⅲ、Ⅳ、Ⅴ

　　8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到(　　)个不同的码字。

　　A.107 B.108 C.214 D.215

　　9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有(　　)个叶子。

　　A.log2n B.(n-1)/2 C.log2n+1 D.(n+1)/2

　　10、下面关于B和B+树的叙述中，不正确的是(　　)

　　A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构

　　C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索

二、填空题

　　11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 。

　　12、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用 三元组表示弧及弧上的权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、在单链表L中，指针P所指结点有后继结点的条件是 。

　　14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为 ，在给定值为x的结点后插入一个新结点的时间复杂度为 。

　　15、数据结构中评价算法的两个重要指标是 。

　　16、当两个栈共享一存储区时，栈利用一维数组stack(1，n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为 ，栈2空时， top[2]为 ，栈满时为 。

　　17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。

　　18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为 ，又称P为 。

三、判断题

　　19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。(　　)

　　20、直接访问文件也能顺序访问，只是一般效率不高。(　　)

　　21、一个广义表可以为其他广义表所共享。(　　)

　　22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。(　　)

　　23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。(　　)

　　24、深度为k的二叉树中结点总数小于等于2k-1。(　　)

　　25、为了很方便地插入和删除数据，可以使用双向链表存放数据。　(　　)

　　26、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(　　)

　　27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。(　　)

　　28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。(　　)

四、简答题

　　29、阅读下面的算法，说明算法实现的功能。

　　30、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。

　　31、设有6个有序表A、B、C、D、E、F，分别含有10、35、40、50、60 和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将 6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

　　(1) 给出完整的合并过程，并求出最坏情况下比较的总次数。

　　(2) 根据你的合并过程，描述n(n≥2)个不等长升序表的合并策略，并说明理由。

五、算法设计题

　　32、在一个循环链队中只有尾指针(记为rear，结点结构为数据域data，指针域next)，请给出这种队列的入队和出队操作的实现过程。

　　33、编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于x的数据元素。要求你的算法的时间复杂度为O(log2(x+m))，其中，2为排序树中所含结点数，m为输出的关键字个数。

　　34、给定n×m矩阵A[a..b，c..d]，并设

　　A[i，j]≤A[i+1，j](a≤i≤b-1，c≤j≤d)。设计一算法判定x的值是否在A 中，要求时间复杂度为O(m+n)。

　　35、设排序二叉树中结点的结构为下述三个域构成： Data：给出结点数据的值;left：给出本结点的左儿子结点的地址; right：给出本结点的右儿子结点的地址。设data域为正整数，该二叉树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data 域之值小于等于x的结点全部删除掉。