数据结构答案

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

2、基本单位。A、数据结构B、数据元素C、数据项D、数据类型7 .下面，对非空线性表特点的论述，C是正确的。A.所有结点有且只有一个直接前驱8 .所有结点有且只有一个直接后继C.每个结点至多只有一个直接前驱，至多只有一个直接后继D.结点间是按照1对多的邻接关系来维系其逻辑关系的8 .在顺序表中，只要知道D,就可以在相同的时间内求出任一结点的存储地址。A、开始结点B、终端结点C、向量大小D、基地址和结点大小9 .在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是_CoA开始结点B、终端结点C、内部结点D、所有结点10 .顺序表中逻辑上相邻的结点的物理位置为A0A一定相邻B、不必相邻C、按某种

3、规律排列D、不要求11 .一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是B0A110B108C100D12012 .链表不具有的特点是AA、可以随机访问任何一个元素B、插入和删除元素不需要移动元素C、不必事先估计存储空间D、所需的存储空间和链表长度无关13 .数据结构反映了数据元素之间的结构关系。链表是一种D。A顺序存储线性表B非顺序存储非线性表C顺序存储非线性表D非顺序存储线性表14 .链接存储的存储结构所占存储空间AA分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存

4、放结点值，另一部分存放结点所占单元数15 .线性表L在B情况下适用于使用链式结构实现。A需经常修改L中的结点值B需不断对L进行删除插入CL中含有大量的结点DL中结点结构复杂16 .线性链表不具有的特点是A。A随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比17 .在长度为n的顺序表中，往其第i个元素(1<i<n)之前插入一个新的元素时，需要往后移动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.

5、i19 .往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B个结点。A.nB.n/2C,n+1D,(n+1)/220 .带表头结点的单链表Lk_h为空的判定条件是B。A.Lk_h=NULLB.Lk_h->Next=NULLC.Lk_h->Next=Lk_hD,Lk_h!=NULL21.在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是_C。A. rtr->Next=ptr->Next;ptr->Next=rtr;B. ptr->Next=rtr-&

6、gt;Next;C. qtr->Next=rtr;rtr->Next=ptr;D. ptr->Next=rtr;rtr->Next=qtr->Next;22 .在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是BoA.C.qtr->Next=ptr;ptr->Next=qtr;qtr->Next=ptr->Next;ptr=qtr;B.qtr->Next=ptr->Next;ptr->Next=qtr;D.ptr->Next=qtr;qtr->Next=pt

7、r;23 .栈与一般线性表的区别在于B。A、数据元素的类型不同B、运算是否受限制C、数据元素的个数D、逻辑结构不同24 .栈的插入和删除操作在A进行。A、栈顶B、栈底C、任意位置D、指定位置25 .一个顺序栈一旦被声明，其占用空间大小AoA、已固定B、可以变化C、不能固定D、动态变化26 .设有一个顺序栈S,元素si,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,si,则顺序栈的容量至少应为BA2B3C4D527 .若让元素1,2,3依次进栈，则出栈次序不可能出现C种情况。A32iB2i3C3i2Di3228 .一个栈的入栈序列是abode,则栈不

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

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

10、n=front36 .循环队列存储在数组A0.m中，则入队时的操作为D。A. rear=rear+1B.rear=(rear+1)%(m-1)B. rear=(rear+1)%mD.rear=(rear+1)%(m+1)37 .数组Qn用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n,计算队列中元素的公式为_D_Arf;B(n+fr)%n;Cn+rf;D(n+rf)%n38 .一个长度为50的循环队列中，队头指针(front)等于41,队尾指针(rer)等于20,则队列中有D个元素。A41B20C21D2939 .二维数组M,行下标i的范围从0

11、到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素B的起始地址相同。A、M24B、M34C、M35D、M4440 .数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是_CA、80B、100C、240D、27041 .有一个二维数组mn,按行存储，假设00存放位置在644（10进制），22存放位置在676（10进制），每个元素占一个空间，则45在_C位置。A692B626C709D72442 .数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10,从首地址SA

12、开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为C。A、SA+141B、SA+144C、SA+222D、SA+22543 .在具有100个结点的树中，其边的数目为C。A101B100C99D9844 .按照树的定义，具有3个结点的树有A种形态。A、2B、3C、4D、545 .按照二叉树的定义，具有3个结点的二叉树有_D_种形态。A、2B、3C、4D、546 .下面说法中,_D_是正确的。A、度为2的树是二叉树B、度为2的有序树是二叉树C、子树有严格左、右之分的树是二叉树D子树有左、右之分、且度不超过2的树是二叉树47 .下面的说法中，C是正确的。A、二叉树的度为2B、二叉树中任

13、意一个结点的度都为2C、任何二叉树中2点度可以小于2D、任何二叉树中至少有一个结点的度为248 .若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数B。A9B、11C、12D、不确定49 .具有10个叶结点的二叉树中有A个度为2的结点。A9B、11C、12D、不确定50 .若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为B。A512B、1024C、2048D、409651 .具有65个结点的完全二叉树的高度为B。A8B7C6D552 .深度为5的二叉树至多有B个结点。A16B、31C、15D、3053 .在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的A结点oA、

14、兄弟B、父子C、祖先D、子孙54 .在一棵树的双亲表示中，每个数据元素包含B_个域。A1B、2C、3D、455 .对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用C次序的遍历实现编号。A.先序B.中序C.后序D.从根开始按层次遍历56 .某二叉树中序序列为A,B,C,D,E,F,G,后序序列为B,D,C,A,F,G,E则前序序歹U是BA.E,G,F,A,C,D,BB.E,A,C,B,D,G,FC.E,A,G,C,F,B,DD.上面的都不对57 .二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK中

15、序遍历:HFIEJKGo该二叉树根的右子树的根是CA、EB、FC、GD、H58 .把一棵树转换为二叉树后，这棵二叉树的形态是AoA唯一的B有多种，但根结点都没有左孩子C有多种D有多种，但根结点都没有右孩子59 .在一个图中，所有顶点的度数之和等于所有边的数目的C倍。A、1/2B、1C、2D、460 .在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。A、1/2B、1C、2D、461 .一个具有n个顶点的无向图最多有A条边。A、nx(n-1)/2B、nX(n-1)C、nX(n+1)/2D、nXn62 .一个具有n个顶点的有向图最多有B条边。A、nX(n1)/2B、nX(n1)C、n

16、X(n+1)/2D、nXn63 .一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个AA、对称矩阵B、对角矩阵C、三角矩阵D、稀疏矩阵64 .具有n个顶点、e条边的无向图采用邻接矩阵存储方法。则邻接矩阵的大小为_D_oD、nxnA、nB、(n-1)义(n+1)C、(n+1)义(n+1)65 .通常把查找过程中对关键字需要执行的C作为衡量一个查找算法效率优劣的标准。ABSTB、WPLC、ASLD、BFS66 .在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数CoANB、1C、N+1D、N-167 .一个顺序存储结构的线性表有255个记录，采用线性查找法(也称顺序查找法)查

17、找该表，在等概率条件下的平均查找长度为A0A128B127C126D25568 .在表长为n的链表中进行线性查找，它的平均查找长度为BAASL=nBASL=(n+l)/2CASL=n/2DASLPog2(n+1)169 .线性表必须是B,才能进行二分查找。A、用数组存储的线性表B、用数组存储的有序表C、用链表存储的线性表D、用链表存储的有序表70 .有一个顺序表为1,3,9,12,32,41,45,62,75,77,82,95,100,当折半查找值为82的结点时，A次比较后查找成功。A4B2C1D871 .链表适用于A查找A顺序B二分法C顺序、，也能二分法D随机72 .折半查找有序表(4,6,

18、12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素A比较大小。A2861220B38,12,20C20D38,70,88,10073 .折半查找有序表(4,6,10,12,20,30,50,70,88,100)。若查找表中元素58,则它将依次与表中A比较大小、查找结果是失败。A20,70,30,50B30,88,70,50C20,50D30,88,5074 .对22个记录的有序表作折半查找，当查找失败时，至少需要比较C次关键字。A3B4C5D675 .散列查找是由键值B确定散列表中的位置，并进行存储或查找。A、本身B、散列函数值C、相反数D、平方76 .

19、设某散列表长度为100,散歹函数H(k)k%p,则P通常情况下最好选择CA、91B、93C、97D、9977.哈希表的地址区间为0-17,哈希函数为H(k)=kmod17。采用线性探测法处理冲突，并将关键字序列26,25,72,38,8,18,59依次存储到哈希表中。那么，元素59存放在哈希表中的地址是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,5B1,3,2,8,7,4,6,5C1,2,3,4,5,6,8,7D1,2,

20、3,4,5,6,7,879 .每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做A排序。A、插入B、交换C、选择D、归并80 .有关键字序列20,6,15,7,3,作升序排列，则线性插入排序过程中第三趟排序结束后关键字的顺序是CoA20,6,15,7,3B6,20,15,7,3C6,15,20,7,3D6,7,15,20,381 .在各种查找方法中，平均查找长度与结点个数n无关的查找方法是CA顺序查找B折半查找C散列查找D线性查找82 .在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是AA访问第i个结点（1&i0n和求第i个结点的直接前驱（2&i

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