2022年南京工程学院计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年南京工程学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。A.head（tail（LS））（head（LS））B.tailC.head（tail（head（tail（LS））））（tail（tailD.head（head（LS））））2、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表仅有头B.指针的单循环链表双链C.表仅有尾指D.针的单循环链表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，V3B.V1，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7，V2，V5，D.V1V3，V4，V6，V75、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，，cd，e，a，则根结点的孩子结点（）。A．只有e．有Be、b．有Ce、c．无法确定D8、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log（n+1）+12C.log（n+1）2D.log（n-l）29、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBA不定C.CBEDFAD.10、下列二叉排序树中查找效率最高的是（）。A.平衡二叉树B.二叉查找树C.没有左子树的二叉排序树D.没有右子树的二叉排序树二、填空题11、属于不稳定排序的有______。12、无用单元是指______，例______13、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。15、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是______。（2）存放数组的第8列的所有元素至少需要的单元数______。（3）数组按列存储时，元素A[5，8]的起始地址是______。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。三、判断题19、倒排序文件的优点是维护简单。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、串是一种数据对象和操作都特殊的线性表。（）22、一个广义表可以为其他广义表所共享。（）23、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）25、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）27、平衡二叉