2022年同济大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。A.5B.6C.8D.92、将线性表的数据元素进行扩充，允许带结构的线性表是（）。A.串树B.广义C.表栈D.3、以下数据结构中，（）是非线性数据结构。A.树字符串B.队C.栈D.4、下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成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，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7，D.V1V2，V5，V3，V4，V6，V76、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只B有Ⅱ．CⅠ和Ⅱ．DⅠ和Ⅲ7、已知关键字序列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，198、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。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、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。A.(n-1)/2B.n/2C.(n+1)/2D.n二、填空题11、属于不稳定排序的有______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、文件可按其记录的类型不同而分成两类，即______和______文件。14、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。15、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。三、判断题19、对磁带机而言，ISAM是一种方便的文件组织方法（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）22、串是一种数据对象和操作都特殊的线性表。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、排序算法中的比较次数与初始元素序列的排列无关。（）26、为了很方便地插入和删除数据，可以使用双向链表存放数据。（）27、无环有向图才能进行拓扑排序。（）28、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）四、简答题29、s