2022年北京石油化工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年北京石油化工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、将线性表的数据元素进行扩充，允许带结构的线性表是（　　）。 A.串 B.树 C.广义表 D.栈 2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（　　）。 A.a，b，e，c，d，f B.a，c，f,e，b，d C.a，e，b，c，f, d D.a，e，d，f，c，b 3、以下与数据的存储结构无关的术语是（　　）。 A.循环队列 B.链表 C.哈希表 D.栈 4、动态存储管理系统中，通常可有（　　）种不同的分配策略。 A.1 B.2 C.3 D.4 5、已知有向图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 6、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序 A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ 7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（　　）。 8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（　　）。 A.在树T中，X是其双亲的第一个孩子 B.在树T中，X一定无右兄弟 C.在树T中，X一定是叶结点 D.在树T中，X一定有左兄弟 10、就平均性能而言，目前最好的内排序方法是（　　）排序法。 A.起泡 B.希尔插入 C.交换 D.快速 二、填空题 11、阅读下列程序，指出其功能，并写出空格处应填上的语句。 12、在有n个顶点的有向图中，每个顶点的度最大可达______。 13、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。 14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 15、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。 （2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。 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、已知一循环队列的存储空间为[m..n]，其中nm，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。 三、判断题 19、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、循环队列也存在空间溢出问题。（　　） 22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　） 23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（　　） 24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（　　） 25、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（　　） 26、顺序存储方式的优点是存储密度大，且插入、删除运算效率