数据结构期末复习题

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

1、一、单选题 1. 从物理上可以把数据结构分为（B ）两大类。 A. 动态结构、静态结构 B. 顺序结构、链式结构 C. 线性结构、非线性结构 D. 初等结构、构造型结构 2. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间 复杂度为（C ）(1in+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 3. 链表不具有的特点是（B） 。 A. 插入、删除不需要移动元素 B. 可随机访问任一元素 C. 不必事先估计存储空间 D. 所需空间与线性长度成正比 4. 下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A

2、. 选择 B. 起泡 C. 归并 D. 堆 5. 在下列排序算法中，哪一个算法的时间复杂度与初始排序无关（D ） 。 A. 插入排序 B. 起泡排序 C. 快速排序 D. 选择排序 6. 一个栈的输入序列为 1,2,3,n，若输出序列的第一个元素是 i，则第 j 个输出元素是 （D） 。 A. i-j-1 B. i-j C. j-i+1 D. 不确定 7. 输入序列为 ABC，可以变为 BCA 时，经过的栈操作为（D ） 。 A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push

3、,pop D. push,push,pop,push,pop,pop 8. 有六个元素 6 5 4 3 2 1 的顺序进栈，下列（ C ）不是合法的出栈序列。 A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 9. 串的长度是指（B ） 。 A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 10. 设二维数组 A1. m,1. n（即 m 行 n 列）按行存储在数组 B1. m*n中，则二维数组元 素 Ai,j在一维数组 B 中的下标为( A) 。 A.（i

4、-1）*n+j B.（i-1）*n+j-1 C. i*（j-1） D. j*m+i-1 11. 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是 （B ） 。 A. 9 B. 11 C.15 D. 不确定 12. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac ，它的前序遍历是（ D ） 。 A. acbed B. decab C. deabc D. cedba 13. 下面几个符号串编码集合中，不是前缀编码的是（ B） 。 A. 0,10,110,1111 B. 11,10,001,101,0001 C. 00,010,011

5、0,1000 D. b,c,aa,ac,aba,abb,abc 14. 一个 n 个顶点的连通无向图，其边的个数至少为（ A ） 。 A. n-1 B. n C. n+1 D. nlogn； 15. 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是 （D ） 。 A. G 中有弧 B. G 中有一条从 Vi 到 Vj 的路径 C. G 中没有弧 D. G 中有一条从 Vj 到 Vi 的路径16. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（ C ） 。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 17.

6、下面关于二分查找的叙述正确的是（D ） 。 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 18. 对线性表进行二分查找时，要求线性表必须（ B ） 。 A. 以顺序方式存储 B. 以顺序方式存储，且数据元素有序 C. 以链接方式存储 D. 以链接方式存储，且数据元素有序 19. 下面关于哈希(Hash ，杂凑)查找的说法正确的是（ C） 。 A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B. 除留余数法是所有哈希函数中最好的 C. 不存在

7、特别好与坏的哈希函数，要视情况而定 D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即 可 20. 设哈希表长为 14，哈希函数是 H(key)=key Mod 11，表中已有数据的关键字为 15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决 冲突，则放入的位置是（ D ） 。 A. 8 B. 3 C. 5 D. 9 二、判断题 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （X ） 2. 内排序要求数据一定要以顺序方式存储。 （X ） 3. 若输入序列为 1，2，3，4，5，6，用栈可以输出序列 1，

8、5，4，6，2，3。 （X）3,2 4. 循环队列通常用指针来实现队列的头尾相接。 （X ）圆圈形 5. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （V） 6. 在待排数据基本有序的情况下，快速排序效果最好。 （ X） 7. 中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。 （ V） 8. 在 n 个结点的无向图中，若边数大于 n-1 ，则该图必是连通图。 （ X ） 9. 归并排序在任何情况下都比所有简单排序速度快。 （ X） 10. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。 （V ） 11. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 （V ） 12.

9、 深度为 K 的二叉树中结点总数 2k-1 。 （ ）2K-1 13. 折半查找法的查找速度一定比顺序查找法快 。 （X ） 14. 稀疏矩阵压缩存储后，必会失去随机存取功能。 （X ） 15. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 （V ） 16. 不同的求最小生成树的方法最后得到的生成树是相同的。 （ V ） 17. 采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的 所在位置置空，因为这会影响以后的查找。 （ V ）三、简答题 1. 数据元素之间的关系在计算机中有几种表示方法？ 各有什么特点？ 表示关系有两种不同方法，相应得到两类存储结构： （1）顺

10、序存储方式。数据元素顺序存放，每个存储结点只含一个 元素。存储位置反映数据元素间的逻辑关系。存储密度大，但有些 操作（如插入、删除）效率较差。 （2）链式存储方式。每个存储结点除包含数据元素信息外还包含 一组（至少一个）指针。指针反映数据元素间的逻辑关系。这种方 式不要求存储空间连续，便于动态操作（如插入、删除等） ，但存储 空间开销大（用于指针） ，另外不能折半查找等。 （3）索引存储方式。除数据元素存储在一地址连续的内存空间外， 尚需建立一个索引表，索引表中索引指示存储结点的存储位置（下 标）或存储区间端点（下标） ，兼有静态和动态特性。 （4）散列存储方式。通过散列函数和解决冲突的方法，

11、将关键字 散列在连续的有限的地址空间内，并将散列函数的值解释成关键字 所在元素的存储地址，这种存储方式称为散列存储。其特点是存取 速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。 2. 试述头结点，首元结点，头指针这三个概念的区别。 答：首元结点是指链表中存储线性表中第一个数据元素 a1 的结 点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其 作用是为了对链表进行操作时，可以对空表、非空表的情况以 及对首元结点进行统一处理。头指针是指向链表中第一个结点 （或为头结点或为首元结点）的指针。若链表中附设头结点， 则不管线性表

12、是否为空表，头指针均不为空。否则表示空表的 链表的头指针为空。这三个概念对单链表、双向链表和循环链 表均适用。是否设置头结点，是不同的存储结构表示同一逻辑 结构的问题。头结点 head data link头指针 首元结点 简而言之， 头指针是指向链表中第一个结点（或为头结点或为首元结点） 的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只 放空表标志和表长等信息（内放头指针？那还得另配一个头指 针！） 首元素结点是指链表中存储线性表中第一个数据元素 a1 的结点。 3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处。数据类型是程序设计语言中的一个概念，它是一个值的集

13、合 和操作的集合，如C 语言中的整型、实型、字符型及其上的加、减等操作。实际 上数据类翌是厂家提供给用的已实现了的基本数据结构。抽象数据类型(ADT)指一个数学模型及定义在该模型上的 一组操作。 “抽象”的意义在于数据类型的数学抽象特性。抽象 敛据类型的定义仅取决于它的逻辑特性而与其在计算机内部 如何表示和实现无关。无论其内部结构如何变化，只要它的数 学特性不变就不影响它的外部使用。抽象数据类型和数据类型实质上是一个概念。此外，抽象 数据类型的范围更广，它已不再局限于机器已定义和实现的鼓 据类型，还包括用户在设计软件系统时自行定义的敛据类型。 使用抽象数据类型定义的软件模块含定义、表示和实现三

14、部 分封装在一起对用户透明(提供接口)，而不必了解实现细节。 4. 如果输入序列为 1 2 3 4 5 6，试问能否通过栈结构得到以下两个序列：4 3 5 6 1 2 和 1 3 5 4 2 6；请说明为什么不能或如何才能得到。 输入序列为 123456，不能得出 435612，其理由是，输出序列最 后两元素是 12，前面 4 个元素（4356）得到后，栈中元素剩 12，且 2 在栈顶，不可能栈底元素 1 在栈顶元素 2 之前出栈。得到 135426 的过程如下：1 入栈并出栈，得到部分输出序 列 1；然后 2 和 3 入栈，3 出栈，部分输出序列变为：13；接着 4 和 5 入栈，5，4 和

15、 2 依次出栈，部分输出序列变为 13542； 最后 6 入栈并退栈，得最终结果 1354265. 简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的头指针与尾指 针的值。 typedef struct node elemtype elemcqm; /m 为队列最大可能的容量。int front ,rear; /front 和 rear 分别为队头和队尾指针。 cqnode; cqnode cq; (1) 初始状态 cq.front=cq.rear=0; (2) 队列空 cq.front=cq.rear; (3) 队列满 (cq.rear+1)%m=cq.front; 四、应用题 1. 已知记录