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

2022年淮阴工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、下列关于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、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.log2nB.（n－1）/2C.log2n+1D.（n＋1）/210、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、在哈希函数H（key）=key%p中，p值最好取______。12、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。13、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有______检索和______检索。14、文件可按其记录的类型不同而分成两类，即______和______文件。15、索引顺序文件既可以顺序存取，也可以______存取。16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。三、判断题19、直接访问文件也能顺序访问，只是一般效率不高。（）20、倒排文件的目的是为了多关键字查找。（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）22、一个广义表可以为其他广义表所共享。（）23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）24、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（）25、抽象数据类型与计算机内部表示和实现无关。（）26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、下面程序段的时间复杂度是什么？30、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12，13，15，18，20，60（）排序的结果为：13，15，18，12，20，60（）排序的结果为：13，15，20，18，12，60（）排序的结果为：12，13，20，18，15，6031、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)（1）画出这六大城市的交通网络图。（2）画出该图的邻接表表示法。（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。五、算法设计题32、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。33、对给定关键字序号j（1<j<n），要求在无序记录A[1..n]中找到关键字从小到大排在第j位上的记录，写一个算法利用快速排序的划分思想实现上述查找（要求用最少的时间和最少的空间）。例如：给定无序关键字{7，5，1，6，2，8，9，3}，当j=4时，找到的关键字应是5。34、假定用两个一维数组L[N]和R[N]作为有N个结点1，2，…，N的二叉树的存储结构。L[i]和R[i]分别指示结点i的左儿子和右儿子，L[i]=0（R[i]=0）表示i的左（右）儿子为空。试写一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点u是否为结点V的后代的算法。35、假设在二叉链表的结点中增设两个域：parent域指示其双亲结点：flag域（取值为0~2）区分在遍历过程中到达该结点时应继续向左、向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。

参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】C5、【答案】B6、【答案】C7、【答案】D8、【答案】B9、【答案】D10、【答案】A二、填空题11、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数12、【答案】（1）L->next=NULL//置空链表，然后将原链表结点逐个插入到有序表中（1） p!=NULL//当链表尚未到尾，p为工作指针（2） q!=NULL//查P结点在链表中的插入位置，这时q是工作指针（4）p->next=r->next//将P结点链入链表中（5）r->next=p//r是q的前驱，u是下个待插入结点的指针13、【答案】关键字；记录号；记录号；顺序；直接14、【答案】操作系统文件；数据库15、【答案】随机16、【答案】0；n+1；top[1]+1=top[2]17、【答案】3318、【答案】【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】×25、【答案】√26、【答案】√27、【答案】√28、【答案】×四、简答题29、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。30、答：①快速排序②起泡排序③直接插入排序④堆排序31、答：(1)