精品飞行学院计算机科学与技术专业《数据结构与算法》科目期末试卷精品.pdf

2022年中国民用航空飞行学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入选择B.希尔二路C.归并D.2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、连续存储设计时，存储单元的地址（）。A.一定连续一定不B.连续C.不一定连续D.部分连续，部分不连续4、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储5、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ．仅BⅠ、Ⅱ、Ⅲ．C仅Ⅱ、Ⅲ、Ⅳ．仅DⅢ、Ⅳ、Ⅴ8、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。A.1B.4C.3D.2二、填空题11、若用n表示图中顶点数目，则有______条边的无向图成为完全图。12、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是该函数的程序段，请将未完成的部分填入，使之完整。②执行程序，f（6，4）=______。13、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。15、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。17、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为，l2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。三、判断题19、倒排序文件的优点是维护简单。（）20、倒排文件的目的是为了多关键字查找。（）21、稀疏矩阵压缩存储后，必会失去随机存取功能。（）22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）26、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易