2022年华南农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docx

2022年华南农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 2、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（　　）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 3、单链表中，增加一个头结点是为了（　　）。 A.使单链表至少有一个结点 B.标识表结点中首结点的位置 C.方便运算的实现 D.说明单链表是线性表的链式存储 4、动态存储管理系统中，通常可有（　　）种不同的分配策略。 A.1 B.2 C.3 D.4 5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 6、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。 7、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。 A．500，200，450，180 B．500，450，200，180 C．180，500，200，450 D．180，200，500，450 8、在下述结论中，正确的有（　　）。 ①只有一个结点的二叉树的度为0。 ②二叉树的度为2。 ③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A.①②③ B.⑦③④ C.②④ D.①④ 9、有关二叉树下列说法正确的是（　　）。 A.二叉树的度为2 B.一棵二叉树的度可以小于2 C.二叉树中至少有一个结点的度为2 D.二叉树中任何一个结点的度都为2 10、就平均性能而言，目前最好的内排序方法是（　　）排序法。 A.起泡 B.希尔插入 C.交换 D.快速 二、填空题 11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 12、阅读下列程序，指出其功能，并写出空格处应填上的语句。 13、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。 14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 15、VSAM系统是由______、______、______构成的。 16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。 17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。 18、模式串P=‘abaabcac’的next函数值序列为______。 三、判断题 19、直接访问文件也能顺序访问，只是一般效率不高。（　　） 20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　） 21、数组不适合作为任何二叉树的存储结构。（　　） 22、稀疏矩阵压缩存储后，必会失去随机存取功能。（　　） 23、任何二叉树的后序线索树进行后序遍历时都必须用栈。（　　） 24、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　） 25、排序算法中的比较次数与初始元素序列的排列无关。（　　） 26、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（　　） 27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（　　） 28、平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（　　） 四、简答题 29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。 30、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’ （1）计算模式p的nextval函数值。 （2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 31、二叉树的带权路径