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

2022年河北地质大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入选择B.希尔二路C.归并D.3、线性表的顺序存储结构是一种（）。A.随机存取的存储结构顺序存取的存储结B.构C.索引存取的存储结构存取的存储结D.Hash构4、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.45、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、已知字符串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Ⅲ、Ⅳ、Ⅴ8、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log（n+1）+12C.log（n+1）2D.log（n-l）29、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、属于不稳定排序的有______。12、在哈希函数H（key）=key%p中，p值最好取______。13、文件由______组成；记录由______组成。14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。15、索引顺序文件既可以顺序存取，也可以______存取。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。18、模式串P=‘abaabcac’的next函数值序列为______。三、判断题19、倒排序文件的优点是维护简单。（）20、倒排文件是对次关键字建立索引。（）21、数组不适合作为任何二叉树的存储结构。（）22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）23、若从二叉树的任一结点出发，到根的路径上所经过的结点序列按其关键字有序，则该二叉树一定是哈夫曼树。（）24、深度为k的二叉树中结点总数小于等于2k-1。（）25、排序算法中的比较次数与初始元素序列的排列无关。（）26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序?对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：（1）画出描述折半查找过程的判定树。（2）若查找元素54，需依次与哪些元素比较?（3）若查找元素90，需依次与哪些元素比较?（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构，且邻接点都按序号从