2022年长春工业大学计算机科学与技术专业《数据结构与算法》科目期末试精品.pdf

2022年长春工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入选择B.希尔二路C.归并D.2、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、线性表的顺序存储结构是一种（）。A.随机存取的存储结构顺序存取的存储结B.构C.索引存取的存储结构存取的存储结D.Hash构4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0．Bi＝5，j＝0．i＝C5，j＝2．i＝D6，j＝27、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（）。8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、下面关于B和B+树的叙述中，不正确的是（）A.B树和B+树都是平衡的多叉树树和B+树都可用于文件的索引B.B结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。13、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______14、索引顺序文件既可以顺序存取，也可以______存取。15、VSAM系统是由______、______、______构成的。16、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为，l2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、在链队列中，即使不设置尾指针也能进行入队操作。（）22、广义表（（（a，b，c），d，e，f））的长度是4。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）26、在任何情况下，归并排序都比简单插入排序快。（）27、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）28、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）四、简答题29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’（1）计算模式p的nextval函数值。（2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。30、写出下列排序算法的基本思想，并写出对序列（23，12，35，4