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

2022年河北工程大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。A.5B.6C.8D.92、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点标识表结点中首结B.点的位置C.方便运算的实现说明单链表是线性表的链式存D.储4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，，cd，e，a，则根结点的孩子结点（）。A．只有e．有Be、b．有Ce、c．无法确定D8、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有（）个叶子。A.logn（nB.－1）/2C.logn+1（D.n＋1）/22210、下面关于B和B+树的叙述中，不正确的是（）A.B树和B+树都是平衡的多叉树树和B+树都可用于文件的索引B.B结构C.B树和B+树都能有效地支持顺序检索D.B树和B+树都能有效地支持随机检索二、填空题11、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。注：(1)图的顶点号从0开始计。(2)indegree是有n个分量的一维数组，放顶点的入度，(3)函数crein用于计算顶点入度。(4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。15、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。16、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排文件的目的是为了多关键字查找。（）21、一个广义表可以为其他广义表所共享。（）22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）26、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）四、简答题29、对于具有n个叶结点且