数据结构期末复习

练习一1第 16 题要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为()。A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构答案:C2第 17 题关于矩阵的三元组表表示，以下叙述正确的是()。A.转置运算时只需把每个三元组的行、列下标互换即可。B.存储时只需要各非零元素的三元组信息，不需要其它信息。C.适合于对称矩阵的压缩存储。D.访问元素时不能随机存取。答案:D3第 24 题对长度为 10 的顺序表进行查找，若查找前面 5 个元素的概率相同，均为 1/8，查找后面 5个元素的概率相同，均为 3/40，则查找任一元素的平均查找长度为()。A.5.5B.5C.39/8D.19/4答案:C4第 25 题若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表B.仅有头指针的单循环链表C.双链表D.仅有尾指针的单循环链表答案:D5第 27 题将数组称为随机存储结构是因为()。A.数组元素是随机的B.随时可以对数组元素进行访问C.对数组的任一元素的存取时间是相等的D.数组的存储结构是不定的答案:C6第 28 题在下列排序方法中，空间复杂性为 O(log2n)的方法为()。A.直接选择排序B.归并排序C.堆排序D.快速排序答案:D7第 30 题对 n 个顶点和 e 条边的有向图，以邻接矩阵存储，则求图中某顶点入度的时间复杂度为()。A)O(n)B)O(e)C)O(n+e)D)O(n2)A.AB.BC.CD.D答案:A8第 31 题图的广度遍历必须借助()作为辅助空间。A.栈B.队列C.查找表D.数组答案:B9第 39 题基数排序中的“基数”可以是()。A.10B.8C.16D.以上都可以答案:D10第 40 题n 个记录直接插入排序时所需的记录最少比较次数是()。A.n-1B.nC.n(n-1)/2D.n(n+1)/2答案:A11第 41 题下图所示二叉树对应的森林中有()棵树。A.1B.2C.3D.不确定答案:C12第 42 题对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为()。A.求顶点的邻接点B.求顶点的度C.深度优先遍历D.广度优先遍历答案:B13第 52 题二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序()。A.可能改变B.一定会改变C.一定不改变D.可能变也可能不变答案:C14第 53 题下列叙述错误的是()。A.多维数组是向量的推广。B.多维数组是非线性结构。C.如果将二维数组看成由若干个行向量组成的一维数组，则为线性结构。D.对矩阵进行压缩存储的目的是为了数据加密。答案:D15第 54 题以下关于算法叙述不正确的是()。A.时间和空间性能往往是一对矛盾B.常常可牺牲空间性能换取时间性能C.常常可牺牲时间性能换取空间性能D.时间和空间性能并不会矛盾答案:D16第 55 题由同一关键字集合构造的各棵二叉排序树()。A.形态和平均查找长度都不一定相同B.形态不一定相同，但平均查找长度相同C.形态和平均查找长度都相同D.形态相同，但平均查找长度不一定相同答案:A17第 56 题算法的时间复杂度取决于()。A.问题的规模B.数据的初始状态C.A 和 BD.以上都不是答案:C18第 57 题对二叉排序树进行()，可以得到各结点键值的递增序列。A.先根遍历B.中根遍历C.层次遍历D.后根遍历答案:B19第 58 题串是()。A.一些符号构成的序列B.有限个字母构成的序列C.一个以上的字符构成的序列D.有限个字符构成的序列答案:D20第 59 题以下广义表关系正确的是()。A.线性表再入表 纯表递归表B.线性表纯表递归表再入表C.纯表线性表再入表递归表D.线性表纯表 再入表递归表答案:D21第 63 题以下叙述错误的是()。A.数据的三个层次是数据、数据元素、数据项B.数据类型是指相同性质的计算机数据的集合C.每种逻辑结构都有一个运算的集合D.储存结构中不仅要储存数据的内容，还要把数据间的关系表示出来。答案:B22第 64 题若只在线性表的首、尾两端进行插入操作，宜采用的存储结构为()。A.顺序表B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表答案:C23第 65 题栈操作的原则是()。A.先进先出B.后进先出C.栈底删除D.以上都不是答案:B24第 66 题若下图表示某广义表，则它是一种()。A.线性表B.纯表C.再入表D.递归表答案:D25第 67 题导致队列下溢的操作是()。A.队满时执行出队B.队满时执行入队C.队空时执行出队D.队空时执行入队答案:C27第 69 题关键字比较次数与数据的初始状态无关的排序算法是()。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案:A28第 70 题对 n 个元素进行冒泡排序，最好情况下的只需进行()对相邻元素之间的比较。A.nB.n-1C.n+1D.n/2答案:B29第 71 题对 n 个顶点的有向图，若所有顶点的出度之和为 s，则所有顶点的入度之和为()。A.sB.s-1C.s+1D.n答案:A30第 72 题与邻接表表示相比，邻接矩阵表示更适合()。A.无向图B.有向图C.稠密图D.稀疏图答案:C31第 89 题多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为()。A.数组的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案:A32第 90 题高度为 n、结点数也为 n 的二叉树，共有()棵。A）nB）2n-1C）n-1D）2n-1A.AB.BC.CD.D答案:D33第 91 题单链表中增加头结点的目的是为了()。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储答案:C34第 92 题对 n 个结点的二叉树，按()遍历顺序对结点编号（号码为 1n）时，任一结点的编号等于其左子树中结点的最大编号加 1，又等于其右子树中结点的最小编号减 1。A.前根B.中根C.后根D.层次答案:B35第 93 题算法分析是指()。A.分析算法的正确性B.分析算法的可读性C.分析算法的健壮性D.分析算法的时空性能答案:D36第 94 题栈和队列的共同特点是()。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点答案:C37第 95 题下列关于串的叙述中，正确的是()。A.一个串的字符个数即该串的长度B.一个串的长度至少是 1C.空串是由空格字符组成的串D.两个串若长度相同，则它们相等答案:A38第 96 题希尔排序的增量序列必须是()。A.递增的B.随机的C.递减的D.任意的答案:C39第 97 题在不完全排序的情况下，就可以找出前几个最大值的方法是()。A.快速排序B.直接插入排序C.堆排序D.归并排序答案:C40第 98 题若要在 O(1)的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点答案:B41第 99 题在 n 个顶点和 e 条边的无向图的邻接表中，边结点的个数为()。A.nB.n*eC.eD.2*e答案:D42第 100 题若一个图中包含有 k 个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用()次深度优先搜索遍历的算法。A.1B.kC.k-1D.k+1答案:B43第 22 题连通图的 BFS 生成树一般比 DFS 生成树的高度小。答案:正确44第 23 题利用栈可将递归程序转化成非递归程序。答案:正确45第 29 题每一种逻辑结构只能对应一种存储结构。答案:错误46第 32 题用线性探测法解决突出时，同义词在散列表中是相邻的。47第 33 题链表中逻辑上相邻的元素在物理位置上不一定相邻。答案:正确48第 34 题稀疏矩阵就是矩阵的元素很少。答案:错误49第 35 题堆排序是一种巧妙的树型选择排序。答案:正确50第 36 题图 G 的生成树 T 是 G 的子图。答案:正确51第 37 题二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变。答案:错误52第 43 题若二叉树中没有度为 1 的结点，则为满二叉树。答案:错误53第 44 题空串并不是由空白字符组成的串。答案:正确54第 45 题在顺序表中按值查找运算的复杂性为 O(1)。答案:错误55第 46 题如果根结点的左子树和右子树高度差不超过 1，则该二叉树是平衡二叉树。答案:错误56第 47 题排序的目的是为了方便以后的查找。答案:正确57第 48 题基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。答案:错误58第 49 题如果网络中有多条边的权相同，则其最小生成树就不会是唯一的。答案:错误59第 50 题在栈的应用中，栈顶指针总是指向真正的栈顶。答案:错误60第 73 题线索二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。答案:错误61第 74 题数据的逻辑结构和运算集组成问题的数学模型，与计算机无关。答案:正确62第 75 题单链表中的头结点就是单链表的第一个结点。答案:错误63第 76 题一维数组是一种顺序表。答案:正确64第 77 题直接插入排序是稳定的，而 Shell 排序就是调用若干趟直接插入排序，故也是稳定的。答案:错误65第 78 题二叉排序树上，以根到任一结点的路径为界，则：路径左边结点路径结点路径右边结点。答案:错误66第 79 题不是所有的有向图都可以进行拓扑排序，而能拓扑排序时，结果不一定唯一。答案:正确67第 80 题稀疏矩阵压缩存储后会丧失随机存取特性。答案:正确68第 101 题当问题具有先进先出特点时，就需要用到栈。答案:错误69第 102 题算法的时间复杂性越高，则计算机速度提高后，得到的收益就越大。答案:错误70第 103 题顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。答案:错误71第 104 题n 个结点的有向图，若它有 n(n1) 条边，则它一定是强连通的。答案:正确72第 105 题二路归并排序的核心操作是把两个有序序列合并为一个有序序列。答案:正确73第 1 题树的三种常用存储结构是：孩子链表表示法、_和_。答案:双亲链表、孩子兄弟链表74第 2 题线索二叉树中，线索的含义是_。答案:某种遍历的前趋或后继信息75第 3 题运算定义在逻辑结构上，算法定义在_结构上；运算指出“做什么” ，算法指出_。答案:储存；怎么做76第 4 题下面程序段的时间复杂性为_。y=1;while(yn)y=y*3;答案:O(log3n)77第 5 题下面程序段的时间复杂性为_。for(i=0;in;i+)for(j=0;j10;j+)Aij=0；答案:O(n)78第 6 题若 I 和 O 分别表示入栈和出栈，对元素 a、b、c 、d、e 依次执行 IIOIOIIOOO，则栈的容量至少为_。答案:379第 7 题顺序栈在进行_运算时，可能发生栈的上溢，在进行_运算时，