2022年上海海事大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。A.快速排序B.堆排序归C.并排序D.直接插入排序2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、链表不具有的特点是（）。A.插入、删除不需要移动元素可随机B.访问任一元素C.不必事先估计存储空间所需空D.间与线性长度成正比4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0．Ci＝5，j＝2．Di＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树．所有叶B结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。A.（2，5，12，16）26（60，32，72）B.（5，16，2，12）28（60，32，72）C.（2，16，12，5）28（60，32，72）D.（5，16，2，12）28（32，60，72）二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。13、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。三、判断题19、倒排序文件的优点是维护简单。（）20、文件系统采用索引结构是为了节省存储空间。（）21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）22、串是一种数据对象和操作都特殊的线性表。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）26、在任何情况下，归并排序都比简单插入排序快。（）27、若一