2023年唐山师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷B（有答案）.docxVIP

2023年唐山师范学院计算机科学与技术专业《数据结构与算法》科目期末试卷B（有答案） 一、选择题 1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（　　）。 A.60 B.66 C.18000 D.33 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，V7 B.V1，V3，V2，V6，V4，V5，V7 C.V1，V3，V5，V2，V6，V7 D.V1，V2，V5，V3，V4，V6，V7 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，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。 A．只有e B．有e、b C．有e、c D．无法确定 7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 9、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（　　）。 A.（38，40，46，56，79，84） B.（40，38，46，79，56，84） C.（40，38，46，56，79，84） D.（40，38，46，84，56，79） 二、填空题 11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。 12、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。 13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。 14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。 （2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 15、外排序的基本操作过程是______和______。 16、阅读下列程序说明和程序，填充程序中的______。 【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为： （1）把根结点放入堆栈。 （2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 （3）重复（2）直到堆栈为空时为止。 17、设广义表L=（（），（）），则head（L）是______； tail（L）是______；L的长度是______；深度是______。 18、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。 三、判断题 19、倒排文件的目的是为了多关键字查找。（　　） 20、倒排文件是对次关键字建立索引