数据结构年度模拟试题(doc 6页).doc

2002年数据结构模拟试题（一）一、单项选择题（本大题共14小题，每小题1分，共14分）1. 下面程序的时间复杂性为：( )。for (i = 1; i = n ; i +)for ( j = 1 ; j next = p next next B.p = p next nextC.p = p next D.p next = p next next5. 非空的循环单链表head 的尾结点（由指针p所指）满足( )。A.p next=NULL B.p next =headC.p = NULL D.P = head6. 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是 ( )。A.(N-1)(N-1) B.NN 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)/28. 对于一个具有N个结点和E条边的无向图，若采用邻接表表示，则表头向量的大小是( )。A. N B. N+1 C. N-E D. N-19. 判断一个有向图是否存在 回路的方法中，除了可以利用拓扑排序方法外，还可以利用的 方法是( )。A求最短路径的方法 B求关键路径的方法C深度优先遍历的方法 D广度优先遍历的方法10. 一个具有N个顶点的有向图最多有( )条边。A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/211. 下面的查找方式中，可以对无序表进行查找的是( )。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)/214. 用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。A.O(n) B.O(log2n) C.O(n) D.O(1)二、判断题（本大题共10小题，每小题2分，共20分）1. 顺序存储的数组是一个随机存取结构。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是一个mn维的稀疏矩阵，请编写一个算法实现：将A用三元组表表示，其中三元组表的第一行的三列存放A的行数、列数以及非零元素的个数。(假设A中存放的元素都属于整型数)参考答案及评分标准一、单项选择题1. C 2. B 3. A 4. A 5. B 6. B 7. A 8. A 9. C 10. B 11. A12. C 13. D 14. B二、判断题1. 对 2. 对 3. 错 4. 对 5. 对6. 错 7.错 8. 对 9. 错 10. 错三、填空题1 .顺序存储方法,链接存储方法,索引存储方法,散列存储方法2.算法时间复杂度的数量级，即算法的渐近时间复杂度3.逻辑关系,具体总是抽象出来的数学模型,用计算机语言的实现,逻辑4.0,空5.先移动栈顶指针，后存入元素,先取出元素，后移动栈顶指针，6 .n-17.38.O（n）9 .第I个元素,后移,第I个位置,增110.变参或函数名,第I+1个元素,前移,减1四、问答题1.数据结构就是指数据之间的相互关系，即数据的组织形式，一般来说，数据结构包含以下三个方面的内容：数据元素之间的逻辑关系，也称为数据的逻辑结构；数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；数据的运算，即对数据施加的操作。2.线性表是由n(n=0)个数据元素（结点）a1,a2,，an组成的有限序列。其中数据元素的个数n定义为表的长度。线性表的逻辑特征是：对于非空的线性表，有且仅有一个开始结点a1它没有直接前趋，而仅有一个直接后继a2,有且仅有一个终端结点 an,它没有直接后继，而仅有一个直接前趋an-1,其余的内部结点ai(2in-1)均有且仅有一个直接前趋ai-1和一个直接后继ai+1。3.所谓递归就是指：若在一个函数、过程或者数据结构定义的内部又直接（或者间接）出现有定义本身的应用，则称它们是递归的，或者是递归定义的。递归算法的设计一般有两步：（1）将规模较大的原问题分解为一个或者多个规模更小的，但具有类似于原问题特性的子问题，即较大的问题递归的用较小的问题来描述，解原问题的方法同样可以用来解决这些子问题。（2）确定一个或者多个无须分解、可直接求解的最小子问题。则在第一步称为递归步骤，第二步中所述的最小子问题称为递归的终止条件。在递归步骤的分解中，应该使子问题相对于原问题而言更接近于递归终止条件，从而保证经过有限次递归步骤之后，子问题的规模减至最小，达到递归终止条件而结束递归。4.如果我们将存储队列的向量想象成一个首尾相接的圆环，则我们称这种向量为循环向量，存储在其中的队列就称为循环队列。在循环队列中，对其进行出队和入队的操作时，头指针和尾指针仍和在顺序队列中一样要加1，只是在循环队列中，当头尾指针指向向量的上界时，其加1的操作的结果是指向向量的下界0，这样在循环队列中，出队元素的空间可以被重新利用，这样，除非队列元素的个数真的大于向量空间，否则，使用循环队列不会产生上溢，于是就克服了循环队列中的假上溢现象。所以，人们在使用时一般都选择使用循环队列，而不是采用顺序队列。五、设计题1.此项换算法相对较简单，在B中所有的数据类型都是整型，不需要额外设置，只需要对A进行逐行扫描，将非零元素对应的行号、列号以及此非零元素的值都存放到B中对应的位置即可2002年数据结构模拟试题（二）一、单项选择题（本大题共14小题，每小题1分，共14分）1. 下面的程序在执行时，S语句共被执行了( )次。i = 1 ;while (i=n for ( j = i ; jnextB.r = r nextC.f = f nextD.f = r next8. 向一个栈顶指针为top的链栈中插入一个s 所指结点时，其操作步骤是( )。A.top next = sB.s next = top ; top = s;C.s next =top next; top next = s;D.s next =top ; top = top next9. 在一个具有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.2B.1C.0.5D.不确定12. 具有N个顶点的无向图至少应该有( )个边才能保证此图是一个连通图。A.NB.N-1C.N+1D.2N13. 假设一个连通图G有N个顶点，则此图的任何一条路径的长度不可能超过( )。A.NB.2NC.2N-1D.N-114. 在无向图中，所有顶点的度数之和是所有边树的( )倍。A.2B.1C.0.5D.不确定二、判断题（本大题共10小题，每小题2分，共20分）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. 对三、填空题1.约表长的一半,该元素在线性表中的位置2.必须,不必3.其直接前趋结点的链域的值4.开始节点,没有,1,终端结点,没有5.一个值的集合以及在这些值上定义的一组操作的总称,原子类型,结构类型6.有穷性,确定性,可行性,输入,输出7 .简单操作次数,相对量度,存储空间8 .先移动队首指针，后取出元素9 .单链表,表头,链表头部10.将新元素插入到rear所指的位置，然后rear加1,删除front所指的元素，然后将front加并返回被删除元素,四、问答题1.对于同一个问题，我们往往可以编写出多种不同的算法来求解，我们在选用时，首先要保证算法的“正确性”，然后再从以下三个方面考虑：执行算法所需要的时间，当然我们要尽量选用耗时少的算法；执行算法所耗费的存储空间，其中主要考虑辅助存储空间；算法应易于理解，易于编码，易于调试等。尽管我们希望所选用的算法占用存储空间小，运行时间短，其他性能也好，但往往一个算法不能同时满足这些要求，在选用时要根据实际情况来选择。2.头结点就是在单链表的开始结点之前附加的一个结点，设置头结点的优点有两个：（1）由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其他位置上一样，无须进行其他特殊处理；（2）无论链表是否为空，其头指针是指向头结点的非空指针（空表中头结点的