1、第 1 页 （共 25 页） 数据结构 课程习题集 第 1 页 （共 25 页） 一、 . 选择题 . 1. 算法的计算量的大小称为计算的（ ）。 A效率 B. 复杂性 C. 现实性 D. 难度 .2. 算法的时间复杂度取决于（ ） . A问题的规模 B. 待处理数据的初态 C. A 和 B D. 难 确定 .3. 下面关于算法说法错误的是（ ） A算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是 指指令不能有二义性 D. 以上几个都是错误的 .4从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线
2、性结构、非线性结构 D初等结构、构造型结构 .5以下数据结构中，哪一个是线性结构（ ）？ A广义表 B. 二叉树 C. 稀疏矩阵 D. 串 .6下述哪一条是顺序存储结构的优点？（ ） A存储密度大 B插入运算方便 第 2 页 （共 25 页） C删除运算方便 D可方便地用于各种逻辑结构的存储表示 .7下面关于线性表的叙述中，错误的是哪一个？（ ） A线性表采用顺序存储，必须占用一片连续的存储单元。 B线性表采用顺序存储，便于进行插入和删除操作。 C线性表采用链接存储，不必占用一片连续的存储单元。 D线性表采用链接存储，便于插入和删除操作。 .8若某线性表最常用的操作是存取任 一 指定序号的元素
3、和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A顺序表 B双链表 C带头结点的双循环链表 D单循环链表 .9设一个链表最常用的操作是在末尾 插入结点和删除尾结点，则选用 ( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 .10. 链表不具有的特点是（ ） . A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比 .11. 设一个栈的输入序列是 1， 2， 3， 4， 5,则下列序列中，是栈的合法输出序列的是（ ）。 A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4
4、3 1 2 5 D. 3 2 1 5 4 .12. 某堆栈的输入序列为 a, b， c ， d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a， c， b， d B. b, c， d， a C. c, d， b, a D. d, c， a， b 第 3 页 （共 25 页） .13. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 .14. 用不带头结点的单链表存储队列时 ,其队头指针指向队头结点 ,其队尾指针指向队尾结点，则在进行删除操作时 ( )。 A仅修改队头指针 B. 仅修改队
5、尾指针 C. 队头、队尾指针都要修改 D. 队头 ,队尾指针都可能要修改 .15下面关于串的的叙述中，哪一个是不正确的？（ ） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储 .16 串是一种特殊的线性表，其特殊性体现在 ( ) A可以顺序存储 B数据元素是一个字符 C可以链接存储 D数据元素可以是多个字符 .17关于空串与空格串，下面说法正确的是 ( )。 A空串与空格串是相同的 B空串与空格串长度是相同的 C空格串中存放的都是空格 D空串中存放的都是 NULL . 18图中有关路径的定义是（ ）。 A由顶点和相邻顶点序
6、偶构成的边所形成的序列 B由不同顶点所形成的序列 第 4 页 （共 25 页） C由不同边所形成的序列 D上述定 义都不是 .19设无向图的顶点个数为 n，则该图最多有（ ）条边。 A n-1 B n(n-1)/2 C n(n+1)/2 D 0 E n2 .20 一个 n 个顶点的连通无向图，其边的个数至少为（ ）。 A n-1 B n C n+1 D nlogn； .21某内排序方法的稳定性是指 ( )。 A该排序算法不允许有相同的关键字记录 B该排序算法允许有相同的关键字记录 C平均时间为 0（ n log n）的 排序方法 D以上都不对 .22如果只想得到 1000 个元素组成的序列中第
7、 5 个最小元素之前的部分排序的序列，用（ ）方法最快。 A起泡排序 B快速排列 C Shell 排序 D堆排序 E简单选择排序 .23排序趟数与序列的原始状态有关的排序方法是 ( )排序法。 A插入 B. 选择 C. 冒泡 D. 都不是 .24下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。 ( ) A选择排序法 B. 插入排序法 C. 快速 排序法 D. 都不是 .25对序列 15， 9， 7， 8， 20， -1， 4进行排序，进行一趟后数据的排列变为 4， 9， -1，8， 20， 7， 15；则采用的是（ ）排序。 第 5 页 （共 25 页） A. 选择 B. 快
8、速 C. 希尔 D. 冒泡 .26. 设树 T 的度为 4，其中度为 1， 2， 3 和 4 的结点个数分别为 4， 2， 1， 1 则 T 中的叶子数为（ ） A 5 B 6 C 7 D 8 .27 一棵完全 二叉树上有 1001 个结点，其中叶子结点的个数是 （ ） A 250 B 500 C 254 D 505 E以上答案都不对 .28. 有关二叉树下列说法正确的是（ ） . A二叉树的度为 2 B一棵二叉树的度可以小于 2 C二叉树中至少有一个结点的度为 2 D二叉树中任何一个结点的 度都为 2 .29二叉树的第 I 层上最多含有结点数为（ ） . A 2I B 2I-1-1 C 2I
9、-1 D 2I -1 .30对于有 n 个结点的二叉树 , 其高度为（ ） . A nlog2n B log2n C log2n|+1 D不确定 .31对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用 ( )次序的遍历实现编号。 A先序 B. 中序 C. 后序 D. 从根开始按层次遍历 .32. 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为 ( ) A（ N+1） /2 B. N/2 C. N D. （ 1+N） *N /2 第 6 页 （共 25 页） .33. 对线
10、性表进行二分查找时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储 ,且数据元素有序 C.以链接方式存储 D.以链接方式存储 ,且数据元素有序 .34当在一个有序的顺序存储表上查找一个数据 时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度 ( ). A必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 .35. 具有 12 个关键字的有序表，折半查找的平均查找长度（ ） . A. 3.1 B. 4 C. 2.5 D. 5 .36. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) A顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法
11、查找 二、填空题 .1. 对于长度为 255 的表，采 用分块查找，每块的最佳长度为 _。 .2. 顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为 _ _次；当使用监视哨时，若查找失败，则比较关键字的次数为 _ _。 .3 在有序表 A1.12中，采用二分查找算法查等于 A12的元素，所比较的元素下标依次为 _。 .4. 在一棵二叉树中，第 5 层上的结点数最多为 个。 .5.、 n(n0)个结点构成的二叉树，叶结点最多有 个 ， 最少有 个 。 若二叉树有 m 个叶结点，则 度为 2 的结点有 个 。 .6二叉树中某一结点左子树的深度减去右子树的深度称为该结点的 _。 第
12、 7 页 （共 25 页） .7. 假定一棵二叉树的结点数为 18，则它的最小深度为 ，最大深度为 ； .8. 在一棵二叉树中，度为零的结点的个数为 n 0，度为 2 的结点的个数为 n 2，则有n0= 。 .9. 现有按中序遍历二叉树的结果为 abc，问有 _种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是 _。 .10若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键 字的 _和记录的 _。 .11直接插入排序用监视哨的作用是 _。 .12. 不受待排序初始序列的影响，时间复杂度为 O(N2)的排序算法是 _，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上
13、的排序算法是 _。 .13.判断一个无向图是一棵树的条件是 _。 .14具有 10 个顶点的无向图，边的总数最多为 _。 .15若用 n 表示图中顶点数目，则有 _条边的无向图成为完全图。 .16空格串是指 _ _，其长度等于 _ _。 .17设 T和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为 _ _，又称 P 为 _ _。 .18串的两种最基本的存储方式是 _ _、 _ _；两个串相等的充分必要条件是 _ _。 .19. 已知链队列的头尾指针分别是 f 和 r，则将值 x 入队的操作序列是 _。 .20.向栈中压入元素的操作是 _。 .21.在具有 n 个单元的循环队列中
14、，队满时共有 _个元素。 .22用 S 表示入栈操作， X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈第 8 页 （共 25 页） 顺序，相应的 S 和 X 的操作串为 _。 .23. 单链表是 _的链接存储表示。 .24. 在双链表中，每个结点有两个指针域，一个指向 _，另一个指向 _。 .25链接存储的特点是利用 _来表示数据元素之间的逻辑关系。 .26.顺序存储结构是通过 _表示元素之间的关系的 ;链式存储结构是通过 _表示元素之间的关系的。 .27线性表 L=（ a1,a2, ,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的
15、个数是 _。 .28根据线性表的链式存 储结构中每一个结点包含的指针个数，将线性链表分成 _和 _；而又根据指针的连接方式，链表又可分成 _和 _。 .29数据的物理结构包括 的表示和 的表示。 .30抽象数据类型的定义仅取决于它的一组 _ _，而与 _ _无关，即不论其内部结构如何变化，只要它的 _ _不变，都不影响其外部使用。 .31数据结构中评价算法的两个重要指标是 .32. 数据结构是研讨数据的 _ 和 _ ，以及它 们之间的相互关系，并对与这种结构定义相应的 ，设计出相应的 _。 .三 程序填空题 1 已知单链表 H 为一个用带头结点的链表表示的线性表，如下算法是 将其倒置 。 请在
16、下划线处填上正确的语句。 第 9 页 （共 25 页） template void Line_ListLink： Reverse ( ) Line_ListNode *p， *head=new Line_ListNode( )； while(_) p=first； first=first link； p link=_ ； head link=p； first=head link； delete _ ； 2 在顺序表中随机存取的数据，很容易在顺序表中实现 按序号查找 元素。代码如下所示 ，请在下划线处填上正确的语句。 template bool Line_ListSqu： Find(_ ， T DataType temp; for(i = 1; _ ; i+) flag = 0; for(j = 0; _ ; j+) if(_ )
