数据结构模拟试题

《数据结构模拟试题》由会员分享，可在线阅读，更多相关《数据结构模拟试题（7页珍藏版）》请在金锄头文库上搜索。

1、 2002 年数据结构模拟试题（一）一、单项选择题（本大题共 14 小题，每小题 1 分，共 14 分） 1. 下面程序的时间复杂性为：( )。 for (i = 1; i 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

2、-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)/2 8. 对于一个具有 N 个结点和 E 条边的无向图，若采用邻接表表示，则表头向量的大小是( )。A. N B. N+1 C. N-E D. N-1 9. 判断一个有向图是否存在 回路的方法中，除了可以利用拓扑排序方法外，还可以利用 的 方法是( )。 A求最短路径的方法 B求关键路径的方法 C深度优先遍历的方法 D广度优先遍历的方法 10. 一个具有 N 个顶点的有向图最多有(

3、)条边。 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(

4、n) D.O(1)二、判断题（本大题共 10 小题，每小题 2 分，共 20 分） 1. 顺序存储的数组是一个随机存取结构。 2. 将一个对角阵按照行优先或者对角线的顺序压缩到一个向量中时，对应的存储结构是一 种随机的存取结构。 3. 纯表中的成分可以进行递归和共享。 4. 从树的根结点到树中其余结点均存在一条惟一的路径。 5. 在一棵有序树中，如果 k1 和 k2 是兄弟，且 k1 在 k2 左边，则 k1 的任何一个子孙都在 k2 任何一个子孙的左边的。 6. 一棵深度为 k 且有 2k-1 个结点的二叉树叫做满二叉树。 7. 满二叉树一定是完全二叉树，并且完全二叉树也一定是满二叉树。 8

5、. 完全图中具有最多的边数，且在图中，每个顶点之间均有边相连。 9. 若 V（G）中有两个不同的顶点和是连通的，则 G 就称为是连通图。 10. 任何图的连通分量只有一个。 三、填空题（本大题共 10 小题，每小题 3 分，共 30 分） 1. 数据的存储结构可用如下四种基本的存储方法得到：（1）( )(2)( )（3）( ) （4）( )。 2. 评价一个算法的时间性能时，主要标准是( )。 3. 数据的逻辑结构是从( )上描述数据，它与数据的存储无关，是独立于计算机的。因此， 数据的逻辑结构可以看作是( )存储结构是( )，它是依赖于计算机语言的；数据的运算是定 义在数据的( )结构上的。

6、 4. 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列 的初始化时均应该设置为( )，当对队列进行插入和删除的操作后，如果头指针和尾指针相 等时，队列为( )。 5. 向栈中压入元素的操作是( )。对栈进行出栈时的操作是()。 6. 在具有 n 个存储单元的队列中，队满时队中共有( )个元素。 7.假设有一个顺序栈 A，其中元素 a1,a2,a3,a4,a5,a6 依次进栈，如果已知六个元素出栈的顺 序是 a2,a3,a4,a6,a5,a1,则此栈容量至少应该为( )。 8. 对于长度为 n 的顺序表，插入或删除元素的时间复杂性为（ ） 。 9. 向顺序表中第 i

7、 个元素之前插入一个新元素时，首先从( )，开始向后的所有元素均要() 一个位置，接着把新元素写入()上，最后使线性表的长度( )。 10. 从顺序表中删除第 i 个元素时，首先把第 i 个元素赋给()带回，接着从开始向后的所有 元素均()一个位置，最后使线性表的长度()。 四、问答题（本大题共 4 小题，每小题 6 分，共 24 分） 1. 什么是数据结构？请简单介绍一下数据结构包含的主要内容。 2. 什么是线性表？线性表的逻辑特征是什么？ 3. 什么是递归？如何设计递归算法？ 4. 什么是循环队列？循环队列有什么优点？ 五、设计题（本大题共 1 小题，共 12 分） 1. 设 A 是一个

8、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. A 12. C 13. D 14. B二、判断题 1. 对 2. 对 3. 错 4. 对 5. 对 6. 错 7.错 8. 对 9. 错 10. 错 三、填空题 1 .顺序存储方法,链接存储方法,索引存储方法,散列存储方法 2.算法时间复杂度的数量级，即算法的渐近时间复杂度 3

9、.逻辑关系,具体总是抽象出来的数学模型,用计算机语言的实现,逻辑 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,，a

10、n 组成的有限序列。其中数据元素的 个数 n 定义为表的长度。 线性表的逻辑特征是：对于非空的线性表，有且仅有一个开始结点 a1 它没有直接前趋，而 仅有一个直接后继 a2,有且仅有一个终端结点 an,它没有直接后继，而仅有一个直接前趋 an-1,其余的内部结点 ai(2in-1)均有且仅有一个直接前趋 ai-1 和一个直接后继 ai+1。 3.所谓递归就是指：若在一个函数、过程或者数据结构定义的内部又直接（或者间接）出 现有定义本身的应用，则称它们是递归的，或者是递归定义的。递归算法的设计一般有两 步：（1）将规模较大的原问题分解为一个或者多个规模更小的，但具有类似于原问题特性 的子问题，即

11、较大的问题递归的用较小的问题来描述，解原问题的方法同样可以用来解决 这些子问题。 （2）确定一个或者多个无须分解、可直接求解的最小子问题。则在第一步称 为递归步骤，第二步中所述的最小子问题称为递归的终止条件。在递归步骤的分解中，应 该使子问题相对于原问题而言更接近于递归终止条件，从而保证经过有限次递归步骤之后， 子问题的规模减至最小，达到递归终止条件而结束递归。 4.如果我们将存储队列的向量想象成一个首尾相接的圆环，则我们称这种向量为循环向量， 存储在其中的队列就称为循环队列。在循环队列中，对其进行出队和入队的操作时，头指 针和尾指针仍和在顺序队列中一样要加 1，只是在循环队列中，当头尾指针指

12、向向量的上 界时，其加 1 的操作的结果是指向向量的下界 0，这样在循环队列中，出队元素的空间可 以被重新利用，这样，除非队列元素的个数真的大于向量空间，否则，使用循环队列不会 产生上溢，于是就克服了循环队列中的假上溢现象。所以，人们在使用时一般都选择使用 循环队列，而不是采用顺序队列。 五、设计题 1.此项换算法相对较简单，在 B 中所有的数据类型都是整型，不需要额外设置，只需要对 A 进行逐行扫描，将非零元素对应的行号、列号以及此非零元素的值都存放到 B 中对应的 位置即可2002 年数据结构模拟试题（二）一、单项选择题（本大题共 14 小题，每小题 1 分，共 14 分） 1. 下面的程

13、序在执行时，S 语句共被执行了( )次。 i = 1 ;while (i=n for ( j = i ; jnextB.r = r nextC.f = f next D.f = r next 8. 向一个栈顶指针为 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 next 9. 在一个具有 n 个单元的顺序栈中，假设栈底是存储地址的低端，现在我们以 top 作为栈 顶指针，则作退栈操

14、作时，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.1 C.0.5 D.不确定 12. 具有 N 个顶点的无向图至少应该有( )个边才能保证此图是一个连通图。 A.NB.N-1 C.N+1

15、D.2N 13. 假设一个连通图 G 有 N 个顶点，则此图的任何一条路径的长度不可能超过( )。 A.NB.2N C.2N-1 D.N-1 14. 在无向图中，所有顶点的度数之和是所有边树的( )倍。 A.2B.1 C.0.5 D.不确定 二、判断题（本大题共 10 小题，每小题 2 分，共 20 分） 1. 直接插入排序是一种就地排序，它需要的辅助空间是 O（n）. 2. 插入排序方法是稳定的。 3. 在冒泡排序法中，如果按照轻气泡向上的原则进行排序，则排序的终止条件是：待排序 的无序区中所有的气泡均满足轻者在上，重者在下。 4. 若已知一个数组的起始存储地址和维数以及每维的上、下界，且已知每个数组元素所占 有的单元数，则不管按照行优先还是列优先，元素 aij 的存储地址是一样的。 5. C = ( ( x , ( a , b ) ) ,