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

2023年黄淮学院计算机应用技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（　　）存储方式最节省运算时间。 A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表 4、在用邻接表表示图时，拓扑排序算法时间复杂度为（　　）。 A.O(n) B.O(n+e) C.O(n*n) D.O(n*n*n) 5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。 A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都可能要修改 D.队头、队尾指针都要修改 6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（　　）。 A．3，5，12，8，28，20，15，22，19 B．3，5，12，19，20，15，22，8，28 C．3，8，12，5，20，15，22，28，19 D．3，12，5，8，28，20，15，22，19 7、已知字符串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 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（　　）个不同的码字。 A.107 B.108 C.214 D.215 9、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（　　）。 A.选择排序法 B.插入排序法 C.快速排序法 D.堆排序法 二、填空题 11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。 12、在有n个顶点的有向图中，每个顶点的度最大可达______。 13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。 14、文件可按其记录的类型不同而分成两类，即______和______文件。 15、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。 16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。 17、阅读下列程序说明和程序，填充程序中的______。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 三、判断题 19、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 20、倒排文件的目的是为了多关键字查找。（　　） 21、数组不适合作为任何二叉树的存储结构。（　　） 22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元