2022年长春理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年长春理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（　　）。 A.head（tail（LS）） B.tail（head（LS）） C.head（tail（head（tail（LS）））） D.head（tail（tail（head（LS）））） 2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 3、单链表中，增加一个头结点是为了（　　）。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储 4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（　　）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 6、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（　　）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 9、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（　　）。 A.每次分区后，先处理较短的部分 B.每次分区后，先处理较长的部分 C.与算法每次分区后的处理顺序无关 D.以上三者都不对 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 13、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild 域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。 15、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。 16、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。 三、判断题 19、直接访问文件也能顺序访问，只是一般效率不高。（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（　　） 22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 24、