2022年长安大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年长安大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.332、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串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、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟9、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。15、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。16、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。18、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。三、判断题19、倒排文件是对次关键字建立索引。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、数组不适合作为任何二叉树的存储结构。（）22、广义表（（（a，b，c），d，e，f））的长度是4。（）23、对于有n个结点的二叉树，其高度为log2n。（）24、一般来说，若深度为k的n个结点的二叉树只有最小路径长度，那么从根结点到第k-1层具有的最多结点数为2k-1-1，余下的n-2k-1+1个结点在第k层的任一位置上。（）25、数据元素是数据的最小单位。（）26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。(2)以顶点V1为出发点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。33、令G=(V，E)为一个有向无环图，编写一个给图G中每一个顶点赋以一个整数序号的算法，并满足以下条件：若从顶点i至顶点j有一条弧，则应使i<j。34、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。35、已知一棵高度为K具有n个结点的二叉树，按顺序方式存储。（1）编写用前序遍历树中每个结点的非递归算法。（2）编写将树中最大序号叶结点的祖先结点全部打印输出的算法。

参考答案一、选择题1、【答案】B2、【答案】D3、【答案】D4、【答案】B5、【答案】B6、【答案】C7、【答案】A8、【答案】D9、【答案】A10、【答案】C二、填空题11、【答案】n；n+112、【答案】480+8=488；480-32=44813、【答案】2；4；3【解析】二分法查找元素次数列表查找100是找到115就停止了。14、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。15、【答案】分配和释放存储空间；重组；对插入的记录@16、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。17、【答案】O（m+n）18、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。三、判断题19、【答案】√20、【答案】×21、【答案】×22、【答案】×23、【答案】×24、【答案】√25、【答案】×26、【答案】√27、【答案】×28、【答案】√四、简答题29、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的