第3章数据结构 答案

1、第3章 数据结构一、选择题1. 图形结构是数据元素之间存在一种_B_。    A 一对多关系   B  多对多关系  C  多对一关系   D  一对一关系  2.算法分析的目的是_C_。    A 找出数据结构的合理性  B  研究算法中的输入和输出的关系   C  分析算法的效率以求改进   D  分析算法的易懂性和文档性 3.算法的时间复杂度与_A_

2、有关。    A 问题规模   B  计算机硬件性能   C  程序设计语言的类型或版本   D  算法设计者的水平  4.有下面的算法段：for (i=0; i<n; i+) k+;其时间复杂度为 B 。AO(1) BO(n) CO(log2n) DO(n2)5.计算机算法必须具备输入、输出和_C_。A、计算方法 B、排序方法C、解决问题的有限运算步骤 D、程序设计法6._B_是数据的基本单位。A、数据结构 B、数据元素 C、数据项 D、数据类型7.下面，对

3、非空线性表特点的论述， _C_ 是正确的。A所有结点有且只有一个直接前驱B所有结点有且只有一个直接后继C每个结点至多只有一个直接前驱，至多只有一个直接后继D结点间是按照1对多的邻接关系来维系其逻辑关系的8.在顺序表中，只要知道_D_，就可以在相同的时间内求出任一结点的存储地址。A、开始结点 B、终端结点 C、向量大小 D、基地址和结点大小9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是_C_。A、开始结点 B、终端结点 C、内部结点 D、所有结点10.顺序表中逻辑上相邻的结点的物理位置为_A_。A、一定相邻 B、不必相邻 C、按某种规律排列 D、不要求11.一个向量第一个元素的存

4、储地址是100，每个元素的长度为2，则第5个元素的地址是_B_。    A 110   B  108  C  100  D  120  12.链表不具有的特点是_A_。A、可以随机访问任何一个元素 B、插入和删除元素不需要移动元素C、不必事先估计存储空间 D、所需的存储空间和链表长度无关13.数据结构反映了数据元素之间的结构关系。链表是一种_D_。   A 顺序存储线性表   B  非顺序存储非线性表    

5、;C  顺序存储非线性表    D  非顺序存储线性表  14.链接存储的存储结构所占存储空间_A_   A 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针   B  只有一部分，存放结点值   C  只有一部分，存储表示结点间关系的指针   D  分两部分，一部分存放结点值，另一部分存放结点所占单元数15.线性表在_B_ 情况下适用于使用链式结构实现。   A 需经常修改中的结点值 

6、;   B  需不断对进行删除插入    C  中含有大量的结点   D  中结点结构复杂  16.线性链表不具有的特点是_A_ 。   A 随机访问   B  不必事先估计所需存储空间大小   C  插入与删除时不必移动元素   D  所需空间与线性表长度成正比 17.在长度为n的顺序表中，往其第i个元素（1in）之前插入一个新的元素时，需要往后移动 _B_ 个元素

7、。An-iBn-i+1Cn-i-1Di18.在长度为n的顺序表中，删除第i个元素（1in）时，需要往前移动_A_个元素。An-iBn-i+1Cn-i-1Di19.往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动_B_个结点。AnBn/2Cn+1D(n+1)/220.带表头结点的单链表Lk_h为空的判定条件是_B_ 。ALk_h = NULLBLk_h->Next = NULLCLk_h->Next = Lk_hDLk_h != NULL21.在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点

8、，要执行的操作应该是_C_。Artr->Next = ptr->Next;ptr->Next = rtr;Bptr->Next = rtr->Next;Cqtr->Next = rtr;rtr->Next = ptr;Dptr->Next = rtr;rtr->Next = qtr->Next;22.在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是_B_ 。Aqtr->Next = ptr ;Bqtr->Next = ptr->Next ;ptr->Nex

9、t = qtr ; ptr->Next = qtr ;Cqtr->Next = ptr->Next ;Dptr->Next = qtr ;ptr = qtr ; qtr->Next = ptr ;23.栈与一般线性表的区别在于_B_。A、数据元素的类型不同 B、运算是否受限制C、数据元素的个数 D、逻辑结构不同24.栈的插入和删除操作在_A_进行。A、栈顶 B、栈底 C、任意位置 D、指定位置25.一个顺序栈一旦被声明，其占用空间大小_A_。A、已固定 B、可以变化 C、不能固定 D、动态变化26.设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6

10、依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为_B_   A 2  B  3   C  4  D  5  27.若让元素1，2，3依次进栈，则出栈次序不可能出现_C_种情况。   A 3，2，1  B  2，1，3   C  3，1，2   D  1，3，2  28.一个栈的入栈序列是abcde，则栈不可能的输出序列是_C_。A、e

11、dcba B、decba C、dceab D、abcde29.队列的插入操作是在_B_进行的。A、队首 B、队尾 C、队前 D、队后30.队列的删除操作是在_A_进行的。A、队首 B、队尾 C、队前 D、队后31.为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是 _A_。 A.队列      B.栈         C.线

12、性表     D.有序表32.下列关于线性表、栈和队列的叙述，错误的是_A_。 A.线性表是给定的n（n必须大于零）个元素组成的序列。 B.线性表允许在表的任何位置进行插入和删除操作。 C.栈只允许在一端进行插入和删除操作。 D.队列允许在一端进行插入，在令一端进行删除。33.一个队列的入队序列是1,2,3,4，则队列的确定输出序列_B_ A. 4,3,2,1     B. 1,2,3,4     C. 1,4,3,2 

13、60;       D. 3,2,4,1 34.若用一个大小为6的数组来实现循环队列,且当前rear 和front的值分别为0和3.当从队列中删除一个元素,再加入两个元素后, rear 和front的值分别为_B_ A. 1和5 B. 2和4 C. 4和2 D. 5和135.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是_B_。 A. (rear+1)%n=front B. rear=front C. rear+1=front D. (rear-l)%n=front36.循环队列存储在

14、数组A0.m中，则入队时的操作为_D_。 A. rear=rear+1 B. rear=(rear+1)%(m-1) B. rear=(rear+1)%m D. rear=(rear+1)%(m+1)37.数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为 _D_    A rf;  B  （nfr）% n;  C  nrf;    D  （nrf）% n  38.一个长度为50的循环队列中，队头指针（fr

15、ont）等于41，队尾指针（rer）等于20，则队列中有_D_个元素。   A 41   B  20  C  21   D  29  39.二维数组M，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M35的起始地址与M按列存储时元素_B_的起始地址相同。 A、M24 B、M34 C、M35 D、M4440.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是_C_A、80 B、100

16、 C、240 D、27041.有一个二维数组mn，按行存储，假设00存放位置在644（10进制），22存放位置在676（10进制），每个元素占一个空间，则45在_C_位置。   A 692   B  626   C  709   D  724  42.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为_C_。A、SA+141 B、SA+144 C、SA+222 D、SA+225

17、43.在具有100个结点的树中，其边的数目为_C_。   A 101   B  100   C  99   D  98  44.按照树的定义，具有3个结点的树有_A_种形态。A、2 B、3 C、4 D、545.按照二叉树的定义，具有3个结点的二叉树有_D_种形态。A、2 B、3 C、4 D、546.下面说法中，_D_是正确的。A、度为2的树是二叉树 B、度为2的有序树是二叉树C、子树有严格左、右之分的树是二叉树 D、子树有左、右之分、且度不超过2的树是二叉树47.下面的说法中

18、，_C_是正确的。A、二叉树的度为2 B、二叉树中任意一个结点的度都为2C、任何二叉树中结点度可以小于2 D、任何二叉树中至少有一个结点的度为248.若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数_B_。A、9 B、11 C、12 D、不确定49.具有10个叶结点的二叉树中有_A_个度为2的结点。A、9 B、11 C、12 D、不确定50.若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为_B_。A、512 B、1024 C、2048 D、409651.具有65个结点的完全二叉树的高度为_B_。   A 8   B  7&#

19、160;  C  6   D  5  52.深度为5的二叉树至多有_B_个结点。A、16 B、31 C、15 D、3053.在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的_A_结点。A、兄弟 B、父子 C、祖先 D、子孙54.在一棵树的双亲表示中，每个数据元素包含_B_个域。A、1 B、2 C、3 D、455.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用_C_次序的遍历实现编号。A先序 B. 中序 C. 后序 D. 从根开始按

20、层次遍历56.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则前序序列是_B_AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不对 57.二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是_C_A、 E B、 F C、 G D、 H 58.把一棵树转换为二叉树后，这棵二叉树的形态是_A_。    A 唯一的    B  有多种，但根结点都没有左孩子   C

21、0; 有多种  D  有多种，但根结点都没有右孩子 59.在一个图中，所有顶点的度数之和等于所有边的数目的_C_倍。A、1/2 B、1 C、2 D、460.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A、1/2 B、1 C、2 D、461.一个具有n个顶点的无向图最多有_A_条边。A、n×（n1）/2 B、n×（n1）C、n×（n+1）/2 D、n×n62.一个具有n个顶点的有向图最多有_B_条边。A、n×（n1）/2 B、n×（n1）C、n×（n+1）/2 D、n

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

23、255个记录，采用线性查找法（也称顺序查找法）查找该表，在等概率条件下的平均查找长度为_A_。   A 128  B  127  C  126  D  255 68.在表长为的链表中进行线性查找，它的平均查找长度为_B_   A   B  （）   C  n / 2  D  （） 69.线性表必须是_B_，才能进行二分查找。A、用数组存储的线性表 B、用数组存储的有序表C、用链表存储的线性表 D、用链表存储

24、的有序表70.有一个顺序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当折半查找值为82的结点时，_A_次比较后查找成功。   A 4  B  2  C  1   D  8  71.链表适用于 _A_ 查找   A 顺序  B  二分法  C  顺序、，也能二分法  D  随机  72. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元

25、素20，它将依次与表中元素_A_比较大小。   A 28，6，12，20  B  38,12,20  C  20  D  38,70,88,100 73. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 _A_比较大小，查找结果是失败。   A 20，70，30，50  B  30，88，70，50   C  20，50   D  30，88

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

27、字序列26,25,72,38,8,18,59依次存储到哈希表中。那么，元素59存放在哈希表中的地址是_D_。A. 8B. 9 C. 10D. 1178. 给定n=8，对数组R中的8个元素做升序排列，数组R中的关键字为：（8，3，2，1，7，4，6，5），则简单选择排序过程中第二趟排序结束后关键字的顺序是_A_    A 1,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,8 7

28、9.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做_A_排序。A、插入 B、交换 C、选择 D、归并80.有关键字序列20，6，15，7，3，作升序排列，则线性插入排序过程中第三趟排序结束后关键字的顺序是 _C_。 A 20，6，15，7，3  B  6，20，15，7，3  C  6，15，20，7，3  D  6，7，15，20，3 81.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 _C_    A 顺序查找  B&#

29、160; 折半查找   C  散列查找  D  线性查找  82.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是_A_   A 访问第i个结点（1in）和求第i个结点的直接前驱（2in）    B  在第i个结点后插入一个新结点（1in）   C  删除第i个结点（1in）   D  将n个结点从小到大排序 83. 数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素的方法以及它们之间的_A_和运算等的学科。A、结构 B、关系 C、运算 D、 算法84.算法的计算量的大小称为计算的_B_。A、效率 B、 复杂性 C、 现实性 D、 难度85. 以下数据结构中，_A_ 是非线性数据结构A、树