loading石家庄学院
2014-2015学年二学期数据结构期末考试试卷(B卷)
班级:___________学号:___________姓名:___________得分:___________
题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 成绩 复核 题目部分，(卷面共有162题,202分,各大题标有题量和总分) 一、判断正误(100小题,共100分)
1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 2．所谓静态链表就是一直不发生变化的链表。( ) 3．顺序存储方式只能用于存储线性结构。( ) 4．线性表只能用顺序存储结构实现。( ) 5．循环链表不是线性表. ( )
6．顺序存储结构属于静志结构．链式结构属于动态结构。（ ）
7．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( ) 8．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( )
9．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（ ）
10．在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存储结构。（ ）
11．集合与线性表的区别在于是否按关键字排序。( )
12．栈和队列都是线性表，只是在插入和删除时受到了一些限制。（ ） 13．循环队列也存在空间溢出问题。（ ）
14．若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。 （ ）15．任何一个递归过程都可以转换成非递归过程。（ ） 16．栈和队列都是限制存取点的线性结构。( ) 17．有n个数顺序(依次)进栈，出栈序列有种，即：。 （ ）
18．设模式串的长度为m，目标串的长度为n；当n≈m且处理只匹配一次的模式时，朴素的匹配(即子串定位函数)算法所花的时间代价也可能会更为节省。 ( )
19．设有两个串P和Q，其中Q是P的子串，把Q在P中首次出现的位置作为子串Q在P中的位置算祛称为模式匹配。( )
20．KMP算注的最大特点是指示主串的指针不需回溯。( )
21．子串定位函数的时问复杂度在最坏情况下为0（n×m）因此子串定位函数没有实际使用的价值。( )
22．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ） 23．对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。（ ） 24．所谓取广义表的表尾就是返回广义表中最后一个元素。（ ）
25．一个稀疏矩阵采用三元组形式表示。若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成的转置运算。( ) 26．一个广义表可以为其它广义表所共享。（ ）
27．一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（ ）
28．数组是同类型值的集合。（ ）
29．线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。( )
30．二维以上的数组其实是一种特殊的广义表。（ ） 31．广义表是线性表的推广，是类线性数据结构。( )
32．广义表是由零或多个原予或子表所组成的有限序列，所以广义表可能为空表。( ) 33．一般来说，若深度为k 的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为-1，余下的n - +1个结点在第k层的任一位置上。( ) 34．前序遍历森林和前序遍历与该森林对应的二叉树其结果不同。( ) 35．二叉树是度为2的有序树。（ ）
36．二叉树的遍历结果不是唯一的. （ ）
37．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ） 38．后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。（ ） 39．度为二的树就是二叉树。（ ）
40．二叉树中除叶结点外，任一结点x,其左子树根结点的值小于该结点（x）的值，其右子树根结点的值大于等于该结点（x）的值，因此，二叉树一定是二叉排序树 41．若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。( )
42．将一棵树转换成二叉树后，根结点没有左子树。( )
43．中序遍历二叉链存储的二叉树时，一般要用堆栈；中序遍历检索二叉树时，也必须使用堆栈。 ( ） 44． 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。( ） 45．一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。（ ）
46．二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。（ ）
47．由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ） 48．(101，88，46，70，34，39，45，58，66，10)是堆。( )
49．后序遍历森林和中序遍历与该森林相对应的二叉树其结果不同。( ) 50．二叉树的遍历只是为了在应用中找到一种线性次序。（ ） 51．哈夫曼树无左右子树之分。( )
52．在n个结点的无向图中，若边数>n-1，则该图必是连通图。( ) 53．任何AOV网拓扑排序的结果都是唯一的。 ( )
54．有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。( )
55．用邻接矩阵表示图时，矩阵元素的个数与边的条数有关。( ) 56．m阶B-树具有K个子树的非叶子结点含有K—1个关键字。 ( )
57．虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的，( )
58．二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。( )
59．二叉排序树的查找和折半查找时间的性能相同。( )
60．无论是顺序表还是树表，其结点在表中的位置与关键字之间存在着唯一的对应关系：因此进行查找时，总是实施一系列的和关键字的比较操作来体现。
61．折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( )
62．如果某种排序算法是不稳定的．则该方法没有实际应用价值。( )
63．快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。（ ） 64．在快速排序算法中，不可以用队列替代栈。（ ）
65．在完成外排序过程中，每个记录的I/O次数必定相等。( ) 66．交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆序时，进行交换，冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算法的最坏时间复杂性是O（n*n），而快速排序算法的最坏时间复杂性是O（nlog2n）；所以快速排序比冒泡排序效率更高。（ ）
67．堆是满二叉树。（ ）
68．外部排序与外部设备的特性无关。（ ）
69．对于n个记录的集合进行快速排序，在最坏情况下所需要的时间是。（ ） 70．减少初始并段的数量，可使外排序的时间缩短。（ ）
71．当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。（ ）
72．堆肯定是一棵平衡二叉树。（ ）
73．快速排序，堆排序和希尔排序是时间性能较好的排序方法，也是稳定的排序方法。 74．对一个堆，按二叉树层次进行遍历可以得一个有序序列。（ ）
75．当待排序的元素很大叫，为了交换元素的位置，移动元素要占用较多的时间，这是影响时闸复杂度的主要因素。（ ）
76．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（ ）
77．归并排序在任何情况下都比所有简单排序速度快。（ ） 78．文件中每个记录最多只有一个后继记录和一个前驱记录，而文件的第一个记录只有后继
而没有前驱，最后一个记录只有前驱却没有后继；因此，文件可看成是一种线性结构。（ ）
79．索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。（ ） 80．在磁带上的顺序文件中扎入新的记录时，必须复制整个文件。（ ） 81．数据元素是数据的最小单位。( )
82．数据结构的抽象操作的定义与具体实现有关。( )
83．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 84．在9阶B-树中，除叶子以外的任意结点的分支数介于5和9之间。（ ） 85．虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。( ) 86．完全二叉树肯定是平衡二叉树。（ ）
87．二叉排序树删除一个结点后，仍是二叉排序树。（ ） 88．B-树中所有结点的平衡因子都为零。 ( ) 89．在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。( ) 90．若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。（ ）
91．带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（ ） 92．完全二叉树就是满二叉树。（ ） 93．直接选择排序稳定。（ ）
94．线性表的逻辑顺序与物理顺序总是一致的（ ）。
95．关键活动不按期完成就会影响整个工程的完成时间。（ ）
96．n个结点的有向图，若它有n(n－1)条边，则它一定是强连通的。（ ） 97．任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（ ）
98．任何一个关键活动延迟，那么整个工程将会延迟。（ ） 99． 在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（０，１）之间。（ ）100．对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。（ ）
二、多项选择题(40小题,共80分) 1．下面的叙述不正确的是
A、线性表在链式存储时，查找第i个元素的时间同i的值成正比 B、线性表在链式存储时，查找第i个元素的时间同i的值无关 C、线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D、线性表在顺序存储时，查找第i个元素的时间同i的值无关 2．便于插入和删除操作的是
A、静态链表 B、单链表 C、顺序表 D、双链表 E、循环链表 3．线性表的顺序存储结构是一种（ ）的存储结构，线性表的链式链式存储结构是一种（ ）的存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、HASH存取 4．一个输入序列abcd经过一个栈到达输出序列，并且一旦离开输出序列后就不能再返回到输入序列，则下面（ ）为正确的输出序列。
A、 bcad B、cbda C、dabc D、acbd E、dcba
5．依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列是以下哪些序列？ A、{d ，e，c，f，b，g，a} B、 {f，e，g，d，a，c，b} C、 {e，f，d，g，b，c，a} D、 {c，d，b，e，f，a，g}
6．已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有 A、 dacb B、 cadb C、 dbca D、 bdac E、 以上答案都不对 7．循环队列是
A、顺序存储结构 B、不会产生下溢 C、不会产生上溢 D、队满时rear==front E、不会产生假溢 8．两个串相等必有
A、串长度相等 B、串中各位置字符任意 C、串中各位置字符均对应相等 D、串长度不等 E、串长度任意 9．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ ），nextval数组的值为 A、0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B、0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C、0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D、0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E、0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F、0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1
10．二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（ ）内的正确答案。 （1）存放A至少需要（ ）个字节；
（2）A的第8列和第5行共占（ ）个字节；
（3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（ ）的起始地址一致。
供选择的答案：
（1）A、 90 B、 180 C、 240 D、 270 E. 540 （2）A、 108 B、 114 C、 54 D、 60 E. 150 （3）A、 A[8,5] B、 A[3,10] C、 A[5,8] D、 A[0,9] 11．对广义表来说，下述哪些是正确的
A、广义表是一种多层次的结构 B、 广义表是一种非线性结构 C、广义表是种共享结构 D、广义表是一种递归表 E、广义表是一种单链表结构
12．有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是（ ① ）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（ ② ） 和（ ③ ）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（ ④ ）和（ ⑤ ）。 ①-⑤:
A、28 B、44 C、76 D、92 E.108 F.116 G.132 H.176 I.184 J.188
13．有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情况
而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的答案：
①-④：
A．12 B、 66 C、 72 D、 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤：
A、行与列的上界相同 B、 行与列的下界相同
C、 行与列的上、下界都相同 D、 行的元素个数与列的元素个数相同 14．下面（ ）属于特殊矩阵。
A、对角矩阵 B、上三角矩阵 C、下三角矩阵 D、稀疏矩阵 E、对称矩阵 15．给定无向图G如图所示，下列哪些是由顶点1出发的深度优先搜索序列 A、1243 B、 1234 C、 1342 D、 1324 E、 1423
16．下面哪一个方法可以判断出一个有向图中是否有环(回路)?
A、深度优先遍历 B、拓扑排序 C、求最短路径 D、求关键路径 17．图的应用算法有
A、克鲁斯卡尔算法 B、哈夫曼算法 C、迪杰斯特拉算法 D、欧几里得算法 E、拓扑排序算法
18．如下图所示，给出由7个顶点组成的无向图。从顶点1出发，对它进行深度优先遍历得到的顶点序列是____(1)______;而进行广度优先遍历得到的序列是____(2)_______。