第3章数据结构答案

1、第 3 章数据结构、选择题1. _ 图形结构是数据元素之间存在一种 _B _A 一对多关系B 多对多关系C 多对一关系D 一对一关系2. 算法分析的目的是 CC 程序设计语言的类型或版本A 找出数据结构的合理性D 算法设计者的水平C 分析算法的效率以求改进B 研究算法中的输入和输出的关系D 分析算法的易懂性和文档性3. 算法的时间复杂度与 _A_A 问题规模有关。B 计算机硬件性能4. 有下面的算法段：for (i=0; i<n; i+) k+;其时间复杂度为 _B_。A.O(1)B. qn)C .qiog 2n)D .C(n2)5.计算机算法必须具备输入、输出和A、计算方法B、排序方法

2、C、解决问题的有限运算步骤D 、程序设计法C。6.B是数据的基本单位A、数据结构B 、数据元素C 、数据项D 、数据类型7. 下面，对非空线性表特点的论述， _C 是正确的A. 所有结点有且只有一个直接前驱B?所有结点有且只有一个直接后继C?每个结点至多只有一个直接前驱，至多只有一个直接后继D.结点间是按照 1 对多的邻接关系来维系其逻辑关系的8. _ 在顺序表中，只要知道 D , 就可以在相同的时间内求出任一结点的存储地址。A、开始结点B、终端结点C、向量大小D、基地址和结点大小9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是_C,A、开始结点B 、终端结点C 、内部结点D 、

3、所有结点10.顺序表中逻辑上相邻的结点的物理位置为A 。A、一定相邻B、不必相邻C 、按某种规律排列D 、不要求11.一个向量第一个元素的存储地址是100 ，每个元素的长度为 2, 则第 5 个元素的地址是 _ B _ 。A 110B 108C 100D 12012.链表不具有的特点是A 。A、可以随机访问任何一个元素B、插入和删除元素不需要移动元素C、不必事先估计存储空间D、所需的存储空间和链表长度无关13.数据结构反映了数据元素之间的结构关系。链表是一种_DA 顺序存储线性表B 非顺序存储非线性表C 顺序存储非线性表D 非顺序存储线性表14. 链接存储的存储结构所占存储空间AA 分两部分，

4、一部分存放结点值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点值C 只有一部分，存储表示结点间关系的指针D 分两部分，一部分存放结点值，另一部分存放结点所占单元数15. 线性表 L 在 _ B _ 情况下适用于使用链式结构实现。A 需经常修改 L 中的结点值欢迎下载2B 需不断对 L 进行删除插入C L 中含有大量的结点欢迎下载3D L 中结点结构复杂16. _线性链表不具有的特点是AA 随机访问B 不必事先估计所需存储空间大小C 插入与删除时不必移动元素D 所需空间与线性表长度成正比17. 在长度为 n 的顺序表中，往其第 i 个元素（ K i < n）之前插入一个新的元素

5、时，需要往后移动 _ B个元素A.n-iB. n-i+1C. n-i-1D. i18.在长度为 n 的顺序表中，删除第i 个元素（ 1 <i <n）时，需要往前移动A个元素。A.n-iB. n-i+1C. n-i-1D. i19. 往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动_ B个结点。A. nB. n/2C. n+1D. （n+1 ）/220. 带表头结点的单链表 Lk_h 为空的判定条件是A. Lk_h = NULLB.Lk_h->Next = NULLC. Lk_h->Next = Lk_hD. Lk_h != NULL21. 在一个单链表中

6、，已知 qtr 所指结点是 ptr 所指结点的直接前驱。现要在 qtr所指结点和 ptr 所指结点之间插入一个rtr 所指的结点，要执行的操作应该是_C _ 。A.rtr->Next = ptr->Next;ptr->Next = rtr;B.ptr->Next = rtr->Next;C.qtr->Next = rtr; rtr->Next = ptr;D.ptr->Next = rtr; rtr->Next = qtr->Next;22.在单链表中，如果指针 ptr 所指结点不是链表的尾结点，那么在ptr 之后插入由指针 qtr

7、所指结点的操作应该是_ B _ 。欢迎下载4A. qtr->Next = ptr ;B. qtr->Next = ptr->Next ;ptr->Next = qtr ;ptr->Next = qtr ;C. qtr->Next =D. ptr->Next = qtr ;ptr->Next ; ptr = qtr ;qtr->Next = ptr ;23. 栈与一般线性表的区别在于 _B _ 。A、数据元素的类型不同B 、运算是否受限制C、数据元素的个数D、逻辑结构不同24. 栈的插入和删除操作在 _A_ 进行。A、栈顶B、栈底C、任意位置

8、D、指定位置25. 一个顺序栈一旦被声明，其占用空间大小A 。A、已固定B、可以变化C、不能固定D、动态变化26. 设有一个顺序栈 S, 元素 s1， s2， s3， s4 , s5, s6 依次进栈，如果 6个元素的出栈顺序为s2， s3， s4， s6， s5， si，则顺序栈的容量至少应为BA2B3C4D527. 若让元素 1，2，3 依次进栈，则出栈次序不可能出现_C _ 种情况。A3， 2， 1B2， 1， 3C3， 1， 2D1， 3， 228. 一个栈的入栈序列是 abcde ，则栈不可能的输出序列是 _ C _ 。A、edcba B 、decba C 、dceab D 、abc

9、de29. 队列的插入操作是在 _ B _ 进行的。A、队首B、队尾C、队前D、队后30. 队列的删除操作是在 _A_ 进行的。A、队首B、队尾C、队前D、队后31. 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数欢迎下载5据。该缓冲区的逻辑结构应该是_A_ 。A.队列B.栈C.线性表D.有序表32. 下列关于线性表、栈和队列的叙述，错误的是_A_。A. 线性表是给定的 n （n 必须大于零）个元素组成的序列。B. 线性表允许在表的任何位置进行插入和删除操作。C. 栈只允许在一端进行插入和删除操作。D.

10、队列允许在一端进行插入，在令一端进行删除。33. 一个队列的入队序列是 1,2,3,4 ，则队列的确定输出序列 _B _A. 4,3,2,1B. 1,2,3,4C. 1,4,3,2D.3,2,4,134. 若用一个大小为 6 的数组来实现循环队列 ，且当前 rear 和 front 的值分别为0 和 3.当从队列中删除一个元素,再加入两个元素后 ，rear 和 front 的值分别为_B _A.1 和 5B.2 和 4C.4 和 2D.5 和 135. 最大容量为 n 的循环队列，队尾指针是 rear ，队头是 front , 则队空的条件是 _ B_ 。A. (rear+1)%n=front

11、B. rear=frontC. rear+1=fr ontD. (rear-l)% n=front36. 循环队列存储在数组A0.m 中，则入队时的操作为_ D _ 。A.rear=rear+1B. rear=(rea 叶 1)%(m-1)B. rear=(rea 叶 1)%mD. rear=(rea 叶 1)%(m+1)37. 数组 Qn 用来表示一个循环队列， f 为当前队列头元素的前一位置， r 为队尾元素的位置，假定队列中元素的个数小于 n,计算队列中元素的公式为_D_A r f; B ( n+ f r) % n;C n + r f;D ( n + r f) % n38. 一个长度为

12、50 的循环队列中，队头指针（front ）等于 41，队尾指针（ rer ）欢迎下载6等于 20，则队列中有 _D _ 个元素欢迎下载7A41B20C21D2939. _二维数组 M, 行下标 i 的范围从 0 到 4，列下标 j 的范围从 0 到 5,M 按行存储时元素 M35 的起始地址与 M按列存储时元素B _ 的起始地址相同。A、M24 B 、M34C、M35D、M4440. 数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到10，从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的单元数是A、 80B、 100C、240 D 、2

13、7041. 有一个二维数组 mn ，按行存储，假设 00 存放位置在 644 （ 10 进制），22 存放位置在 676（ 10 进制），每个元素占一个空间，则45 在_C_ 位A 692 B 626 C 709 D 72442. 数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到10，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为 _ C _ 。A、SA+141 B 、SA+144C、SA+222D、SA+22543. 在具有 100 个结点的树中，其边的数目为 _C,A101B100C99D9844.按照树的定义

14、，具有3 个结点的树有 A种形态。A、2B、3C、4D 、545.按照二叉树的定义，具有3 个结点的二叉树有_D_ 种形态。A、2B 、3C、4D、546. 下面说法中， _D_ 是正确的。A、度为 2 的树是二叉树B、度为 2 的有序树是二叉树C、 子树有严格左、右之分的树是二叉树D 子树有左、右之分、且度不超过2 的树是二叉树欢迎下载847. 下面的说法中， _C_ 是正确的。A、二叉树的度为2B、二叉树中任意一个结点的度都为2C、任何二叉树中结点度可以小于2 D 、任何二叉树中至少有一个结点的度为 248. 若一棵二叉树有10 个度为 2 的结点，则该二叉树的叶结点的个数_ B。A9B、

15、11C、12D、不确定49. 具有 10 个叶结点的二叉树中有A 个度为 2 的结点。A9B、11C、12D、不确定50. 若一棵满二叉树有2047 个结点，则该二叉树中叶结点的个数为_ B。A 512 B 、 1024 C 、 2048 D 、 409651. 具有 65 个结点的完全二叉树的高度为_ B _ 。A8B7C6D552. 深度为 5 的二叉树至多有_ B _ 个结点。A16B 、 31C 、 15D 、 3053. 在一棵树的左孩子 -右兄弟表示法 中，一个 结点的右孩 子是该结点的A _ 结点。A、兄弟B 、父子C、祖先D 、子孙54. 在一棵树的双亲表示中，每个数据元素包含

16、_B_ 个域A1B 、2C 、3D 、455.对二叉树的结点从1 开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可 采用C_ 次序的遍历实现编号。A.先序B.中序 C. 后序 D.从根开始按层次遍历欢迎下载956. _ 某二叉树中序序列为 A,B,C,D,E,F,G ，后序序列为 B,D,C,A,F,G,E 则前序序列是 _B _A. E,G,F,A,C,D,BB .E,A,C,B,D,G,F C.E,A,G,C,F,B,D D. 上面的都不对57.二叉树的先序遍历和中序遍历如先序遍历： EFHIGJK 中序遍历下：CHFI

17、EJKG 。该二叉树根的右子树的根是D 、 H58.把一棵树转换为二叉树后，这棵二叉树的形态是_AA 唯一的B 有多种，但根结点都没有左孩子C 有多种D 有多种，但根结点都没有右孩子59.在一个图中，所有顶点的度数之和等于所有边的数目的_C_ 倍A、 1/2 B60. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_ B _ 倍。A、1/2 B 、1 C、2 D 、461. 一个具有 n 个顶点的无向图最多有A 条边A、nx(n 1) /2B、nX( n 1)C、nX(n+1 ) /2D、nX n62. 一个具有 n 个顶点的有向图最多有_ B _ 条边。A、nX( n 1) /2

18、 B 、nX( n 1)C、nX( n+1 ) /2 D 、nX n63. 一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个_A A 、对称矩阵B 、对角矩阵C、三角矩阵D 、稀疏矩阵64.具有 n 个顶点、 e 条边的无向图采用邻接矩阵存储方法。则邻接矩阵的大小为D 。欢迎下载10A n B 、(n-1) x(n+1 )C、(n+1) x(n+1 )D 、nx n65. 通常把查找过程中对关键字需要执行的 C作为衡量一个查找算法效率 优劣的标准。A BST B 、WPL C 、ASL D 、BFS66. 在表长是 N 的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数 _C_

19、。A N B 、1 C、N+1 D 、N-167.一个顺序存储结构的线性表有 255 个记录，采用线性查找法（也称顺序查找法）查找该表，在等概率条件下的平均查找长度为A 。A 128 B 127 C 126 D 25568. _在表长为 n 的链表中进行线性查找，它的平均查找长度为_B,A ASL=nB ASL=(n+l)/2C ASL= n / 2D ASLlog2(n+l)-l69.线性表必，须才是能进B行二分查找。A、用数组存储的线性表B、用数组存储的有序表C、用链表存储的线性表D、用链表存储的有序表70. 有一个顺序表为 1，3,9， 12，32，41，45，62，75，77,82，9

20、5，100，当折半查找值为82 的结点时 ,A次比较后查找成功A 4B2C1D 871. 链表适用于A 查找A顺序 B二分法C 顺序、，也能二分法D 随机72. 折半查找有序表（ 4， 6，12，20，28，38，50，70，88，100），若查找表中元素 20，它将依次与表中元素A 比较大小。A 28 ，6，12，20 B 38,12,20 C 20 D 38,70,88,100欢迎下载1173. 折半查找有序表（ 4， 6，10，12，20，30，50，70，88，100 ）。若查找表中元素 58，则它将依次与表中A比较大小，查找结果是失败。A 20 ，70，30，50 B 30 ，88，

21、70，50 C 20 ，50 D 30 ， 88，5074. 对 22 个记录的有序表作折半查找，当查找失败时，至少需要比较 _C_ 次关键字。A3B4C5D675. 散列查找是由键值 B确定散列表中的位置，并进行存储或查找A、本身B、散列函数值C、相反数D、平方76. 设某散列表长度为100 ，散列函数 H(k)k%p, 贝 U P 通常情况下最好选择_C_A、 91B、 93 C、 97D、 9977. 哈希表的地址区间为 0-17 ，哈希函数为 H(k)=k mod 17 。采用线性探测法处理冲突，并将关键字序列 26,25,72,38,8,18,59 依次存储到哈希表中。那么，元素 5

22、9 存放在哈希表中的地址是 _D_ 。A.8B.9C.10D.1178. 给定 n=8 ，对数组 R 中的 8 个元素做升序排列，数组R 中的关键字为： ( 8，3,2，1，7，4，6，5) ，则简单选择排序过程中第二趟排序结束后关键字的顺序是AA1,2,3,8,7,4,6,5 B 1,3,2,8,7,4,6,5 C 1,2,3,4,5,6,8,7 D 1,2,3,4,5,6,7,879. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做A 排序。A、插入B 、交换 C、选择 D 、归并80. 有关键字序列 20，6， 15 ，7，3，作升序排列，则线性插入排序过程中

23、第 三趟排序结束后关键字的顺序是 C_ 。欢迎下载12A 20， 6， 15， 7， 3B 6， 20， 15， 7， 3欢迎下载13C 6,15,20,7,3D 6,7,15,20,381.在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是_ C _A 顺序查找B 折半查找C 散列查找D 线性查找82?在 n 个结点的顺序表中，算法的时间复杂度是 O （1 ）的操作是 _ A A 访问第 i 个结点 （1 < i 菊 n 和求第 i 个结点的直接前驱 （2< i W?nB 在第 i 个结点后插入一个新结点（1 < i W）C 删除第 i 个结点（ 1< i

24、引D 将 n 个结点从小到大排序83.数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素的方法以及它们之间的A和运算等的学科。A、结构B 关系 C、运算 D、算法84. _算法的计算量的大小称为计算的B 。A、效率 B、复杂性C、现实性D、难度85. 以下数据结构中， A 是非线性数据结构A、树 B、字符串 C、队 D、栈86. 线性表元素之间的关系是 A 。A、一对一B、一对多 C、多对多D、无关系87. 下列四种 基本的逻辑结 构中，结构结点间不 存在任何逻辑联系的是A 。A、集合B 线性结构C 、树形结构D、图形结构88. _D _ 不是线性表的特性。A、除第一个元素之外，每个元素都有前驱B、除最后一个元素外，每个元素都有后继C、 线性表是数据的有限序列D 线性表的长度为n, 且 n0欢迎下载1489、 下列关于线性表存储结构的叙述中正确的是_D _ 。A、链表中的元素一定存放在不连续的存储空间里B、链