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

2022年江苏师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、以下与数据的存储结构无关的术语是（）。A.循环队列B.链表C.哈希表D.栈4、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12115、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341566、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（）。A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modMB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modMD．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）7、已知关键字序列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、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.21510、下面关于B和B+树的叙述中，不正确的是（）A.B树和B+树都是平衡的多叉树B.B树和B+树都可用于文件的索引结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。12、属于不稳定排序的有______。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。15、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。17、模式串P=‘abaabcac’的next函数值序列为______。18、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。三、判断题19、倒排序文件的优点是维护简单。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、循环队列也存在空间溢出问题。（）22、数组不适合作为任何二叉树的存储结构。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、二叉树是一般树的特殊情形。（）25、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、阅读下面的算法，说明算法实现的功能。30、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。31、已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想。（2）描述算法的详细实现步骤。（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。五、算法设计题32、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。33、串以静态存储结构存储，结构如下所述，试实现串操作equal算法。34、给出以十字链表作存储结构，建立图的算法，输入(i，j，v)，其中i，j为顶点号，v为权值。35、已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O（m）。

参考答案一、选择题1、【答案】A2、【答案】D3、【答案】D4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】B10、【答案】C二、填空题11、【答案】n；n+112、【答案】希尔排序、简单选择排序、快速排序、堆排序等13、【答案】P->next!=NULL14、【答案】有穷性；确定性；可行性15、【答案】2；4；3【解析】二分法查找元素次数列表查找100是找到115就停止了。16、【答案】0；n+1；top[1]+1=top[2]17、【答案】0112231218、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】√26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。30、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：31、答：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。（2）算法的详细实现步骤①count＝0，p和q指向链表表头结