2023年上海海事大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(含答案)

2023期末试卷A〔有答案〕一、选择题1、假设需在O〔nlog2n〕的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是〔 〕。A.快速排序B.堆排序C. 归并排序D. 直接插入排序2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，由于哈希函数是一对一的关系，则选择好的〔 〕方法是哈希文件的关键。哈希函数除余法中的质数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＝0C ．i＝5，j＝2D ．i＝6，j＝27、以下表达中，不符合m阶B树定义要求的是〔 〕。A．根结点最多有m棵子树B ．全部叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接反，则该二叉树肯定满足〔 〕。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，以下结论正确的选项是〔 〕。在树T中，X是其双亲的第一个孩子在树T中，X肯定无右兄弟在T中，X肯定是叶结点在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至少为 。6、有N个结存放在向量A[：N结点为 。17、设10阶对称矩A承受压缩存储方式〔以行为主序存储：a11=1〕，a85的地址为 。18、在挨次存储的二叉树中，编号为i和j的两个结点处在同一层的条件是 。三、推断题。〔 〕20、文件系统承受索引构造是为了节约存储空间。〔 〕21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴实的匹配〔即子串定位函数〕算法所花的时间代价可能会更为节约。〔 〕22、串是一种数据对象和操作都特别的线性表。〔 〕23、深度为k的二叉树中结点总数小于等于2k-1。〔 〕24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。〔 〕25、为提高排序速度，进展外排序时，必需选用最快的内排序算法。〔 〕排序快。〔 〕27、假设一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。〔 〕28、对大小均为n的有序表和无序表分别进展挨次查找，在等概率查找的状况下，对于查找成功，它们的平均查找长度是一样的，而对于查找失败，它们的平均查找长度是不同的。〔 〕四、简答题29、阅读下面的算法，说明算法实现的功能。ij30n阶下三角矩阵A〔即当i＜j时，有aij

=0〕，依据压缩存储的思想，可以将其ij主对角线以下全部元素〔包括主对角线上元素〕依次存放于一维数组B中，请写出从第一列开头承受列序为主序安排方式时B中确定元素a的存放位置的公式。ij316个顶点〔顶点编号0～5〕的有向G，其邻接矩阵A为上三角矩阵，按行为主序〔行优先〕保存在如下的一维数组中。要求：画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。五、算法设计题32、试将以下递归过程改写为非递归过程。233、编写递归算法，从大到小输出给定二叉排序树中全部关踺字不小于x的数据元素。为〔log〔x+〕〕，其中，2排序结m2为输出的关键字个数。34、写出一趟快速排序算法。35、请运用快速排序思想，设计递归算法实现n〔n>1〕个不同元素集合中的第f〔1≤i小元素。参考答案一、选择题1、【答案】C2、【答案】D3、【答案】B4、【答案】B5、【答案】A6、【答案】C7、【答案】D8、【答案】C9、【答案】D10、【答案】B二、填空题11、【答案】〔n+1〕/212、【答案】n；n+113、【答案】O〔1〕；O〔n〕14、【答案】【解析】m【解析】mB-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少16、【答案】【解析】最大的分支结点是最终一个叶子结点的父结点。17、【答案】3318、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。三、推断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：本算法功能是将两个无头结点的循环链表合并为一个循环链head1最终一个结点的链域指向head2，head2最终一个结点的链域指向head1，head1为结果循环链表的指针。30、答：2阶下三角矩阵A[i][j]〔1≤i，j≤n，i≥j〕30、答：2阶下三角矩阵A[i][j]〔1≤i，j≤n，i≥j〕1列有n个元素，第jn-j+11列到第j-1列是梯形，元素数为〔n+〔n-j+2〕〔j-1〕/2，而aj列ij上的位置是为i-j+1。所以n阶下三角矩A按列存储，其元素a在一维数B中的存储ki和j的关系为：ij可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1个，由此可以画出压缩存储数组中的元