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

2022年河北科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。A.插入B.选择C.希尔D.二路归并3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、属于不稳定排序的有______。12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：13、文件由______组成；记录由______组成。14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。15、外排序的基本操作过程是______和______。16、设数组a[1..50，1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为______；若以列序为主序顺序存储，则元素a[45，68]的存储地址为______。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排序文件的优点是维护简单。（）21、一个广义表可以为其他广义表所共享。（）22、循环队列也存在空间溢出问题。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、排序算法中的比较次数与初始元素序列的排列无关。（）26、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、B-树中所有结点的平衡因子都为零。（）四、简答题29、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12，13，15，18，20，60（）排序的结果为：13，15，18，12，20，60（）排序的结果为：13，15，20，18，12，60（）排序的结果为：12，13，20，18，15，6030、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。31、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。五、算法设计题32、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。33、写一算法找出n个数的最大值和最小值，要求最坏条件下的元素比较次数为34、写出一个递归算法来实现字符串逆序存储。35、试为二叉树写出一个建立三叉链表的算法，并在此三叉链表中删去每一个元素值为x的结点，以及以它为根的子树，且释放相应存储空间。二叉树的三叉链表的描述为：

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】A4、【答案】A5、【答案】A6、【答案】C7、【答案】D8、【答案】D9、【答案】C10、【答案】A二、填空题11、【答案】希尔排序、简单选择排序、快速排序、堆排序等12、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。13、【答案】记录；数据项14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2)①T[k]；toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i]；fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}，ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u，v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。15、【答案】生成有序归并段（顺串）；归并16、【答案】9174；878817、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】√27、【答案】×28、【答案】√四、简答题29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。31、答：（1）由于装填因子为0.8，关键字有8个，所以表长为8/0.8=10