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

2022年西华师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、算法的计算量的大小称为计算的（）。A.效率B.复杂性C.现实性D.难度4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。7、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。13、数据结构中评价算法的两个重要指标是______。14、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______15、文件由______组成；记录由______组成。16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（）22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）26、顺序存储结构的主要缺点是不利于插入或删除操作。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）四、简答题29、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。30、下面程序段的时间复杂度是什么？31、假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如图所示。图5存储映像示意图设str1和str2分别指向两个单词所在单链表的头结点，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指的两个链表共同后缀的起始位置（如图中字符i所在结点的位置p）。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度。五、算法设计题32、给定n×m矩阵A[a..b，c..d]，并设A[i，j]≤A[i+1，j]（a≤i≤b-1，c≤j≤d）。设计一算法判定x的值是否在A中，要求时间复杂度为O（m+n）。33、已知指针p指向带表头的中根次序线索二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设线索二叉树的结点结构、表头结点结构和空树结构分别为（LTAG，LLINK，INFO，RLlNK，RTAG），且规定线索树的最左下结点的LLINK域和最右下结点的RLINKt域指向表头。34、有二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由大到小的结点值递减序列，简述处理方法思路，用非递归形式写出算法。35、请运用快速排序思想，设计递归算法实现求n（n>1）个不同元素集合中的第f（1≤i≤n）小元素。

参考答案一、选择题1、【答案】D2、【答案】A3、【答案】B4、【答案】C5、【答案】A6、【答案】D7、【答案】D8、【答案】B9、【答案】C10、【答案】C二、填空题11、【答案】n（n-1）/212、【答案】480+8=488；480-32=44813、【答案】算法的时间复杂度和空间复杂度14、【答案】py->next=px->next；px->next=py15、【答案】记录；数据项16、【答案】9174；878817、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。18、【答案】【解析】最大的分支结点是最后一个叶子结点的父结点。三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】√27、【答案】√28、【答案】√四、简答题29、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。30、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。31、答：算法的基本设计思想：①分别求出str1和str2所指的两个链表的长度m和n。②将两个链表以表尾对齐，令指针p、q分别指向str1和str2的头结点，若m＞n，则使p指向链表中的第m－n＋1个结点；若m＜n，则使q指向链表中的第n－m＋1个结点，即使指针p和q所指的结点到表尾的长度相等。