2022年数据结构模拟试题 .pdf

2002 年数据结构模拟试题（一）一、单项选择题（本大题共14 小题，每小题1 分，共 14 分）1. 下面程序的时间复杂性为：( )。for (i = 1; i = n ; i +) for ( j = 1 ; j next = p next next B.p = p next next C.p = p next D.p next = p next next 5. 非空的循环单链表head 的尾结点（由指针p 所指）满足 ( )。A.p next=NULL B.p next =head C.p = NULL D.P = head 6. 对于一个具有N 个顶点的图， 如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )。A.(N-1)(N-1) B.N N C.(N+1) (N+1) D.不确定7. 在一个具有N 个顶点的无向完全图中，包含的边的总数是( )。A.N(N-1)/2 B.N(N-1) C.N(N+1) D. N(N+1)/2 8. 对于一个具有N 个结点和E 条边的无向图， 若采用邻接表表示，则表头向量的大小是( )。A. N B. N+1 C. N-E D. N-1 9. 判断一个有向图是否存在回路的方法中，除了可以利用拓扑排序方法外，还可以利用的方法是 ( )。A求最短路径的方法B求关键路径的方法C深度优先遍历的方法D广度优先遍历的方法10. 一个具有N 个顶点的有向图最多有( )条边。A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/2 11. 下面的查找方式中，可以对无序表进行查找的是( )。A.顺序查找B.二分查找C.二叉排序树D.B- 树上的查找12. 散列表的目的是( )。A.插入B.删除C.快速查找D.排序13. 长度为 n 的线性表，若各个结点的查找的概率相同，则在查找成功的情况下，其平均查找 长度为 ( )。A.n B.n(n+1)/2 C.(n-1)/2 D.(n+1)/2 14. 用二分查找方法查找长度为n 的线性表时，每个元素的平均查找长度为( )。A.O(n) B.O(log2n) C.O(n) D.O(1) 二、判断题（本大题共10 小题，每小题2 分，共 20 分）1. 顺序存储的数组是一个随机存取结构。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 2. 将一个对角阵按照行优先或者对角线的顺序压缩到一个向量中时，对应的存储结构是一种随机的存取结构。3. 纯表中的成分可以进行递归和共享。4. 从树的根结点到树中其余结点均存在一条惟一的路径。5. 在一棵有序树中，如果 k1 和 k2 是兄弟， 且 k1 在 k2 左边， 则 k1 的任何一个子孙都在k2任何一个子孙的左边的。6. 一棵深度为k 且有 2k-1 个结点的二叉树叫做满二叉树。7. 满二叉树一定是完全二叉树，并且完全二叉树也一定是满二叉树。8. 完全图中具有最多的边数，且在图中，每个顶点之间均有边相连。9. 若 V（G）中有两个不同的顶点和是连通的，则G 就称为是连通图。10. 任何图的连通分量只有一个。三、填空题（本大题共10 小题，每小题3 分，共 30 分）1. 数据的存储结构可用如下四种基本的存储方法得到：（1）( )(2)( ) （3）( ) （4）( )。2. 评价一个算法的时间性能时，主要标准是( )。3. 数据的逻辑结构是从( )上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是( )存储结构是 ( )，它是依赖于计算机语言的；数据的运算是定义在数据的 ( )结构上的。4. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为( )，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为 ( )。5. 向栈中压入元素的操作是( )。对栈进行出栈时的操作是()。6. 在具有 n 个存储单元的队列中，队满时队中共有( )个元素。7.假设有一个顺序栈A，其中元素a1,a2,a3,a4,a5,a6依次进栈，如果已知六个元素出栈的顺序是 a2,a3,a4,a6,a5,a1, 则此栈容量至少应该为( )。8. 对于长度为n 的顺序表，插入或删除元素的时间复杂性为（） 。9. 向顺序表中第i 个元素之前插入一个新元素时，首先从( )，开始向后的所有元素均要()一个位置，接着把新元素写入()上，最后使线性表的长度( )。10. 从顺序表中删除第i 个元素时， 首先把第i 个元素赋给 ()带回，接着从开始向后的所有元素均 ()一个位置，最后使线性表的长度()。四、问答题（本大题共4 小题，每小题6 分，共 24 分）1. 什么是数据结构？请简单介绍一下数据结构包含的主要内容。2. 什么是线性表？线性表的逻辑特征是什么？3. 什么是递归？如何设计递归算法？4. 什么是循环队列？循环队列有什么优点？五、设计题（本大题共1 小题，共12 分）1. 设 A 是一个 m n 维的稀疏矩阵， 请编写一个算法实现：将 A 用三元组表表示，其中三元组表的第一行的三列存放A 的行数、列数以及非零元素的个数。(假设 A 中存放的元素都属于整型数 ) 参考答案及评分标准一、单项选择题1. C 2. B 3. A 4. A 5. B 6. B 7. A 8. A 9. C 10. B 11. A 12. C 13. D 14. B 二、判断题1. 对 2. 对 3. 错 4. 对 5. 对 6. 错 7.错 8. 对 9. 错 10. 错名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 三、填空题1 .顺序存储方法 ,链接存储方法 ,索引存储方法,散列存储方法2.算法时间复杂度的数量级，即算法的渐近时间复杂度3.逻辑关系 ,具体总是抽象出来的数学模型,用计算机语言的实现,逻辑4.0,空5.先移动栈顶指针，后存入元素,先取出元素，后移动栈顶指针，6 .n-1 7.3 8.O（n）9 .第 I 个元素 ,后移 ,第 I 个位置 ,增 1 10.变参或函数名,第 I+1 个元素 ,前移 ,减 1 四、问答题1.数据结构就是指数据之间的相互关系，即数据的组织形式，一般来说，数据结构包含以下三个方面的内容：数据元素之间的逻辑关系，也称为数据的逻辑结构；数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；数据的运算，即对数据施加的操作。2.线性表是由n(n=0) 个数据元素（结点）a1,a2, ，an 组成的有限序列。其中数据元素的个数 n 定义为表的长度。线性表的逻辑特征是：对于非空的线性表，有且仅有一个开始结点a1 它没有直接前趋，而仅有一个直接后继a2,有且仅有一个终端结点an,它没有直接后继，而仅有一个直接前趋an-1其余的内部结点ai(2 i n-1)均有且仅有一个直接前趋ai-1 和一个直接后继ai+1。3.所谓递归就是指：若在一个函数、过程或者数据结构定义的内部又直接（或者间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。递归算法的设计一般有两步：（1）将规模较大的原问题分解为一个或者多个规模更小的，但具有类似于原问题特性的子问题，即较大的问题递归的用较小的问题来描述，解原问题的方法同样可以用来解决这些子问题。 （2）确定一个或者多个无须分解、可直接求解的最小子问题。则在第一步称为递归步骤，第二步中所述的最小子问题称为递归的终止条件。在递归步骤的分解中，应该使子问题相对于原问题而言更接近于递归终止条件，从而保证经过有限次递归步骤之后，子问题的规模减至最小，达到递归终止条件而结束递归。4.如果我们将存储队列的向量想象成一个首尾相接的圆环，则我们称这种向量为循环向量，存储在其中的队列就称为循环队列。在循环队列中， 对其进行出队和入队的操作时，头指针和尾指针仍和在顺序队列中一样要加1， 只是在循环队列中， 当头尾指针指向向量的上界时，其加 1 的操作的结果是指向向量的下界0，这样在循环队列中，出队元素的空间可以被重新利用，这样，除非队列元素的个数真的大于向量空间，否则，使用循环队列不会产生上溢，于是就克服了循环队列中的假上溢现象。所以， 人们在使用时一般都选择使用循环队列，而不是采用顺序队列。五、设计题1.此项换算法相对较简单，在 B 中所有的数据类型都是整型，不需要额外设置，只需要对A进行逐行扫描，将非零元素对应的行号、列号以及此非零元素的值都存放到B 中对应的位置即可名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - - - - - - - 2002年数据结构模拟试题（二）一、单项选择题（本大题共14 小题，每小题1 分，共 14 分）1. 下面的程序在执行时，S语句共被执行了( )次。i = 1 ; while (i =n for ( j = i ; jnext B.r = r next C.f = f next D.f = r next 8. 向一个栈顶指针为top 的链栈中插入一个s 所指结点时，其操作步骤是( )。A.top next = s B.s next = top ; top = s; C.s next =top next; top next = s; D.s next =top ; top = top next 9. 在一个具有n 个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以top 作为栈顶指针，则作退栈操作时，top 的变化是 ( )。A.top =top -1 ; B.top = top +1 ; C.top 不变D.top 不确定10. 在一个具有n 个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以top 作为栈顶指针，则作退栈操作时，top 的变化是 ( )。A.top =top -1 ; B.top = top +1 ; C.top 不变D.top 不确定11. 在有向图中，所有顶点的入度之和是所有顶点的出度之和的( )倍。A.2 B.1 C.0.5 D. 不确定12. 具有 N 个顶点的无向图至少应该有( )个边才能保证此图是一个连通图。A.N B.N-1 C.N+1 D.2N 13. 假设一个连通图G 有 N 个顶点，则此图的任何一条路径的长度不可能超过( )。A.N B.2N C.2N-1 D.N-1 14. 在无向图中，所有顶点的度数之和是所有边树的( )倍。A.2 B.1 C.0.5 D. 不确定二、判断题（本大题共10 小题，每小题2 分，共 20 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 6 页 - - - - - - - - - 1. 直接插入排序是一种就地排序，它需要的辅助空间是O（n）. 2. 插入排序方法是稳定的。3. 在冒泡排序法中，如果按照轻气泡向上的原则进行排序，则排序的终止条件是：待排序的无序区中所有的气泡均满足轻者在上，重者在下。4. 若已知一个数组的起始存储地址和维数以及每维的上、下界，且已知每个数组元素所占有的单元数，则不管按照行优先还是列优先，元素aij 的存储地址是一样的。5. C = ( ( x , ( a , b ) ) , y ) 是一个长度为3 的广义表。6. 对一个空表作求表头和表尾的运算后得到的表头和表尾均是空表。7. 对非空的广义表的表头和表尾总是一个广义表。8. 在完全二叉树中，一个结点若没有左孩子，则它一定没有右孩子。9. 将一个森林或者一棵树转换成一棵二叉树后，得到的二叉树不惟一。10. 将一棵树转换成一棵二叉树之后，二叉树的根结点的右子树必定为空。三、填空题（本大题共10 小题，每小题3 分，共 30 分）1. 在顺序表中， 插入或者删除一个元素，需要平均移动 ()个元素， 具体移动的元素个数与()有关。2. 顺序表中逻辑上相邻的元素的物理位置()紧邻。单链表中逻辑上相邻的元素的物理位置()紧邻。3. 在单链表中，除了首元结点外，任一结点的存储位置由()指示。4. 在线性表中，若结构是一个非空集，则第一个节点称为()，且此节点 ()前趋节点，其余各个结点有且仅有()，最后一个结点称为()，它()后继节点， 其余各个结点有且仅有1 个后继节点。5. 数据类型是 ()，按照 “ 值” 是否可分，将数据类型分为两类()和()。6. 一个算法应该具有()、()、()、 ()、()五个特征。7. 一个算法的时间复杂性是指该算法包含的()的多少，它是一个算法运行时间的()，一个算法的空间复杂性是指该算法在运行过程中临时占用的()的大小。8. 从一个顺序存储的循环队列中删除一个元素时，应该()。9. 实际上，链栈就是运算受限的()，它的插入和删除仅限制在()() 位置上进行，由于只能在()进行操作，所以链栈没有必要附加头结点。10. 在队列中进行入队和出队操作时，必须按照下面的规律：入队时()，出队时 ()。四、问答题（本大题共4 小题，每小题6 分，共 24 分）1. 一般来说，一个问题往往有多种不同的算法，我们如何评价这些算法的好坏并能从中得到较好的算法呢？2. 在单链表中设置头结点的作用（或者说其优点）是什么？3. 请简述静态存储方式和动态存储方式的区别。4. 请简述串在什么情况下是匹配成功，什么情况下匹配失败。五、设计题（本大题共1 小题，共12 分）1. 已知有一关键字序列为37 ，42，17，99，12，9，24，52，11，30，如果我们采用冒泡法进行排序（按照升序排列），请给出每一趟排序的结果。参考答案及评分标准一、单项选择题1. A 2. A 3. D 4. B 5. C 6. A7. C 8. B 9. A 10. B 11. B12. B 13. D 14. A 二、判断题1. 错 2. 错 3. 对 4. 对 5. 对 6. 对 7. 错 8. 对 9. 错 10. 对名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 三、填空题1.约表长的一半,该元素在线性表中的位置2.必须 ,不必3.其直接前趋结点的链域的值4.开始节点 ,没有 ,1,终端结点 ,没有5.一个值的集合以及在这些值上定义的一组操作的总称,原子类型 ,结构类型6.有穷性 ,确定性 ,可行性 ,输入 ,输出7 .简单操作次数,相对量度 ,存储空间8 .先移动队首指针，后取出元素9 .单链表 ,表头 ,链表头部10.将新元素插入到rear 所指的位置，然后rear 加 1,删除 front 所指的元素，然后将front 加并返回被删除元素, 四、问答题1.对于同一个问题，我们往往可以编写出多种不同的算法来求解，我们在选用时，首先要保证算法的 “ 正确性 ” ，然后再从以下三个方面考虑：执行算法所需要的时间，当然我们要尽量选用耗时少的算法；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等。尽管我们希望所选用的算法占用存储空间小，运行时间短， 其他性能也好， 但往往一个算法不能同时满足这些要求，在选用时要根据实际情况来选择。2.头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理； （2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就一样了。3.静态存储方式中，串值空间的大小是静态的，它在编译时就已经确定，在对进行操作时存储空间的大小是不能改变的，而在动态存储方式中，可以根据实际需要动态的分配和释放字符数组空间，即存储空间的大小是根据实际情况发生变化的。4.对于目标串中的合法位置i（0 i n-m）,依次将目标串中的子串Ti.i+m-1 与模式串P0.m-1进行比较，如果二者相等，则称为从位置i 开始匹配成功。如果二者之中有一个元素不对应相等，则称匹配失败。五、设计题1.冒泡排序法的过程为：从下向上扫描数组，将Ri+1与 Ri进行比较，若Ri+1Ri ，则将二者进行交换(即“ 轻 ” 者在上 )，否则继续扫描，这样每扫描一趟，就将本数组中最 “ 轻” 的元素 “ 浮” 到上面即若i 趟扫描的结果就是此趟扫描前无序区中最“ 轻 ” 的元素 “ 浮”到 Ri中。按照上述规则，我们得到如下结果：初始： 37，42，17，99，12，9，24，52， 11，30 第 1 趟： 9， 37，42，17， 99，12，11，24， 52，30 第 2 趟： 9， 11，37，42，17，99，12，24， 30，52 第 3 趟： 9， 11，12，37，42，17，99，24， 30，52 第 4 趟： 9， 11，12，17，37，42，24，99， 30，52 第 5 趟： 9， 11，12，17，24，37，42，30， 99，52 第 6 趟： 9， 11，12，17，24，30，37，42， 52，99 第 7 趟： 9， 11，12，17，24，30，37，42， 52，99 因为第 7 趟扫描时没有数据之间的交换，所以扫描结束。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -