2022年温州理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，f，B.ac，f,e，b，dC.a，e，b，c，f,d，eD.a，d，f，c，b2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.403、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。A.单链表B.双向链表单C.循环链表顺D.序表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180．B500，450，200，180C．180，500，200，450．D180，200，500，4507、已知关键字序列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，198、一个具有1025个结点的二叉树的高h为（）。A.11B.10至1025C.11之间至D.101024之间9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFA不定D.10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。15、数据结构中评价算法的两个重要指标是______。16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1）存放该数组至少需要的单元数是______。（2）存放数组的第8列的所有元素至少需要的单元数______。（3）数组按列存储时，元素A[5，8]的起始地址是______。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、倒排序文件的优点是维护简单。（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（）