2023年四川师范大学软件工程专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年四川师范大学软件工程专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 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.Hash存取的存储结构 4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛V1，V2，V1，V3，V1，V4，V2，V5，V3，V5， V3，V6，V4，V6，V5，V7，V6，V7｝，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、已知关键字序列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、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。 8、有关二叉树下列说法正确的是（　　）。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 9、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 10、下列二叉排序树中查找效率最高的是（　　）。 A.平衡二叉树 B.二叉查找树 C.没有左子树的二叉排序树 D.没有右子树的二叉排序树 二、填空题 11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m， n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2， 3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整。 ②执行程序，f（6，4）=______。 12、阅读下列程序，指出其功能，并写出空格处应填上的语句。 13、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。 14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。 15、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需要执行以下语句：______ 16、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B 中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始） 17、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 18、阅读下列程序说明和程序，填充程序中的______。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 三、判断题 19、哈希表与哈希文件的唯一区别是哈希文