数据结构 答案

第3章数据结构一、选择题图形结构是数据元素之间存在一种—B。A一对多关系B多对多关系C多对一关系D一对一关系算法分析的目的是C。A找出数据结构的合理性 B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性算法的时间复杂度与A有关。A问题规模B计算机硬件性能C程序设计语言的类型或版本D算法设计者的水平有下面的算法段：for(i=0;i<n;i++)k++;其时间复杂度为B。0(1) B.0(n) C.O(log2n) D.0(n2)计算机算法必须具备输入、输出和C―。A、计算方法 B、排序方法C、解决问题的有限运算步骤 D、程序设计法是数据的基本单位。A、数据结构 B、数据元素 C、数据项 D、数据类型7.下面，对非空线性表特点的论述，C—是正确的。所有结点有且只有一个直接前驱所有结点有且只有一个直接后继每个结点至多只有一个直接前驱，至多只有一个直接后继结点间是按照1对多的邻接关系来维系其逻辑关系的8.在顺序表中，只要知道 D ，就可以在相同的时间内求出任一结点的存储地址。A、开始结点小B、终端结点C、向量大小D、基地址和结点大9.在非空线性表中，有且只有一个直接前驱和一个直接后继的结点是__C―。A、开始结点B、终端结点C、内部结点D、所有结点10.顺序表中逻辑上相邻的结点的物理位置为 A___。A、一定相邻B、不必相邻C、按某种规律排列。、不要求一个向量第一个元素的存储地址是100，每个元素的长度为2,则第5个元素的地址是B。A110B108C100D120链表不具有的特点是A。A、可以随机访问任何一个元素 B、插入和删除元素不需要移动元素C、不必事先估计存储空间 D、所需的存储空间和链表长度无关数据结构反映了数据元素之间的结构关系。链表是一种D。A顺序存储线性表 B非顺序存储非线性表C顺序存储非线性表D非顺序存储线性表链接存储的存储结构所占存储空间AA分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B只有一部分，存放结点值C只有一部分，存储表示结点间关系的指针D分两部分，一部分存放结点值，另一部分存放结点所占单元数线性表L在B情况下适用于使用链式结构实现。A需经常修改L中的结点值B需不断对L进行删除插入CL中含有大量的结点DL中结点结构复杂线性链表不具有的特点是A_。A随机访问B不必事先估计所需存储空间大小C插入与删除时不必移动元素D所需空间与线性表长度成正比在长度为n的顺序表中，往其第i个元素（lWiWn）之前插入一个新的元素时，需要往后移动B—个元素。n-iB.n-i+1C.n-i-1D.i在长度为n的顺序表中，删除第i个元素（1WiWn）时，需要往前移动—A个元素。n-iB.n-i+1C.n-i-1D.i往一个顺序表的任一结点前插入一个新数据结点时，平均而言，需要移动B―个结点。nB.n/2C.n+1D.（n+1）/2带表头结点的单链表Lk_h为空的判定条件是B。A.Lk_h==NULL B.Lk_h->Next==NULLC.Lk_h->Next==Lk_hD.Lk_h!=NULL在一个单链表中，已知qtr所指结点是ptr所指结点的直接前驱。现要在qtr所指结点和ptr所指结点之间插入一个rtr所指的结点，要执行的操作应该是__C 。rtr->Next=ptr->Next;ptr->Next=rtr;ptr->Next=rtr->Next;qtr->Next=rtr; rtr->Next=ptr;ptr->Next=rtr; rtr->Next=qtr->Next;在单链表中，如果指针ptr所指结点不是链表的尾结点，那么在ptr之后插入由指针qtr所指结点的操作应该是B。

A.qtr->Next=ptr;ptr->Next=qtr;CA.qtr->Next=ptr;ptr->Next=qtr;C.qtr->Next=ptr->Next;ptr=qtr;23.栈与一般线性表的区别在于A、数据元素的类型不同C、数据元素的个数qtr->Next=ptr->Next;ptr->Next=qtr;D.ptr->Next=qtr;qtr->Next=ptr;__B 。B、运算是否受限制D、逻辑结构不同栈的插入和删除操作在A进行。A、栈顶 B、栈底 C、任意位置 D、指定位置一个顺序栈一旦被声明，其占用空间大小A。A、已固定 B、可以变化C、不能固定D、动态变化设有一个顺序栈S,元素si,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,si，则顺序栈的容量至少应为 B A2B3C4D5若让元素1,2,3依次进栈，则出栈次序不可能出现C种情况。A3,2,1B2,1,3C3,1,2D1,3,2一个栈的入栈序列是abcde，则栈不可能的输出序列是―C―。A、edcba B、decba C、dceabD、abcde队列的插入操作是在B进行的。A、队首 B、队尾 C、队前 D、队后队列的删除操作是在―A进行的。A、队首 B、队尾 C、队前 D、队后为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是AOA.队列B.栈C.线性表D.有序表下列关于线性表、栈和队列的叙述，错误的是A。线性表是给定的n(n必须大于零)个元素组成的序列。线性表允许在表的任何位置进行插入和删除操作。栈只允许在一端进行插入和删除操作。队列允许在一端进行插入，在令一端进行删除。一个队列的入队序列是1,2,3,4，则队列的确定输出序列―BA.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3.当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为___B A.1和5B.2和4 C.4和2 D.5和1最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是B。A.(rear+1)%n==frontB.rear==frontrear+1==front D.(rear-l)%n==front循环队列存储在数组A[0..m]中，则入队时的操作为D。rear=rear+1 B.rear=(rear+1)%(m-1)rear=(rear+1)%m D.rear=(rear+1)%(m+1)数组Q[n]用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾元素的位置，假定队列中元素的个数小于n，计算队列中元素的公式为__D__Ar—f;B(n+f—r)%n;Cn+r—f; D(n+r—f)%n一个长度为50的循环队列中，队头指针(front)等于41，队尾指针(rer)等于20,则队列中有—D个元素。A41B20C21D2939,二维数组M,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素B的起始地址相同。A、M[2]⑷ B、M[3北4] C、M[3][5]D、Mee数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是__CA、80 B、100C、240 D、270有一个二维数组[m][n]，按行存储，假设[0][0]存放位置在644（10进制），[2][2]存放位置在676（10进制），每个元素占一个空间，则[4][5]在__C位置。A692B626C709D724数组A中，每个元素的长度为3个字节，行下标i从1到8,列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为___C___。A、SA+141 B、SA+144C、SA+222D、SA+225在具有100个结点的树中，其边的数目为—C―。A101B100C99D98按照树的定义，具有3个结点的树有A种形态。A、2 B、3 C、4 D、5按照二叉树的定义，具有3个结点的二叉树有__D__种形态。A、2 B、3 C、4 D、5下面说法中，_。__是正确的。A、 度为2的树是二叉树B、 度为2的有序树是二叉树C、 子树有严格左、右之分的树是二叉树D、 子树有左、右之分、且度不超过2的树是二叉树下面的说法中，―C—是正确的。A、二叉树的度为2 B、二叉树中任意一个结点的度都为2C、任何二叉树中结点度可以小于2 D、任何二叉树中至少有一个结点的度为2若一棵二叉树有10个度为2的结点，则该二叉树的叶结点的个数B。A、9 B、11 C、12 D、不确定具有10个叶结点的二叉树中有A个度为2的结点。A、9 B、11 C、12 D、不确定若一棵满二叉树有2047个结点，则该二叉树中叶结点的个数为B。A、512B、1024 C、2048D、4096具有65个结点的完全二叉树的高度为B。A8B7C6D5深度为5的二叉树至多有B个结点。A、16B、31C、15D、30在一棵树的左孩子-右兄弟表示法中，一个结点的右孩子是该结点的A结点。A、兄弟B、父子 C、祖先D、子孙在一棵树的双亲表示中，每个数据元素包含B_个域。A、1 B、2 C、3 D、4对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用—C—次序的遍历实现编号。A.先序 B.中序 C.后序 D.从根开始按层次遍历56.某二叉树中序序列为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,FC.E,A,G,C,F,B,DD.上面的都不对二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是CA、E B、F C、G D、H把一棵树转换为二叉树后，这棵二叉树的形态是A。A唯一的 B有多种，但根结点都没有左孩子C有多种 D有多种，但根结点都没有右孩子在一个图中，所有顶点的度数之和等于所有边的数目的。倍。A、1/2B、1C、2D、4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。A、1/2B、1C、2D、4一个具有n个顶点的无向图最多有A条边。A、nX(n—1)/2 B、nX(n—1)C、nX(n+1)/2D、nXn一个具有n个顶点的有向图最多有B条边。A、nX(n—1)/2 B、nX(n—1)C、nX(n+1)/2D、nXn一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个A。A、对称矩阵B、对角矩阵 C、三角矩阵 D、稀疏矩阵具有n个顶点、e条边的无向图采用邻接矩阵存储方法。则邻接矩阵的大小为__D__。A、nBA、nB、(n-1)X(n+1)C、(n+1)X(n+1)D、nXn通常把查找过程中对关键字需要执行的C作为衡量一个查找算法效率优劣的标准。A、BST B、WPLC、ASLD、BFS在表长是N的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数—C。A、N B、1C、N+1 D、N-1一个顺序存储结构的线性表有255个记录，采用线性查找法（也称顺序查找法）查找该表，在等概率条件下的平均查找长度为A。A128B127C126D255在表长为n的链表中进行线性查找，它的平均查找长度为B.AASL=n BASL=（n+l）/2CASL=n/2DASL^log2（n+l）-l69.线性表必须是，69.线性表必须是，A、用数组存储的线性表C、用链表存储的线性表B、用数组存储的有序表D、用链表存储的有序表70,有一个顺序表为｛1，3折半查找值为82的结点时，100｝，当12，32，41，45，62，70,有一个顺序表为｛1，3折半查找值为82的结点时，100｝，当次比较后查找成功。71.链表适用于A71.链表适用于A顺序B A二分法查找C顺序、，也能二分法D随机折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素A比较大小。A28，6，12，20B38,12,20C20D38,70,88,100折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中A比较大小，查找结果是失败。A20，70，30，50B30，88，70，50C20，50D30，88，50对22个记录的有序表作折半查找，当查找失败时，至少需要比较C次关键字。A3B4C5D6散列查找是由键值__B确定散列表中的位置，并进行存储或查找。A、本身B、散列函数值 C、相反数。、平方设某散列表长度为100,散列函数H(k)k%p,则P通常情况下最好选择CA、91B、93 C、97D、99哈希表的地址区间为0-17,哈希函数为H(k)=kmod17。采用线性探测法处理冲突，并将关键字序列｛26,25,72,38,8,18,59｝依次存储到哈希表中。那么，元素59存放在哈希表中的地址是D。A.8 B.9C.10 D.11给定n=8，对数组R中的8个元素做升序排列，数组R中的关键字为：(8,3,2,1，7,4,6,5)，则简单选择排序过程中第二趟排序结束后关键字的顺序是___A A1,2,3,8,7,4,6,5B1,3,2,8,7,4,6,5C1,2,3,4,5,6,8,7D1,2,3,4,5,6,7,8每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做—A排序。人、插入B、交换C、选择D、归并有关键字序列｛20,6,15,7,3｝,作升序排列，则线性插入排序过程中第三趟排序结束后关键字的顺序是___C___。A20，6，15，7，3B6，20，15，7，3C6，15，20，7，3D6，7，15，20，3在各种查找方法中，平均查找长度与结点个数n无关的查找方法是CA顺序查找B折半查找C散列查找D线性查找在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是AA访问第i个结点（1<i<n）和求第i个结点的直接前驱（2<i<n）B在第i个结点后插入一个新结点（1<i<n）C删除第i个结点（1<i<n）D将n个结点从小到大排序数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素的方法以及它们之间的A和运算等的学科。A、结构 B、关系C、运算D、算法算法的计算量的大小称为计算的B。A、效率 B、复杂性 C、现实性D、难度以下数据结构中，A是非线性数据结构A、树 B、字符串C、队D、栈线性表元素之间的关系是A。A、一对一B、一对多C、多对多D、无关系下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是A。A、集合 B、线性结构 C、树形结构D、图形结构―D不是线性表的特性。A、 除第一个元素之外，每个元素都有前驱B、 除最后一个元素外，每个元素都有后继C、 线性表是数据的有限序列D、 线性表的长度为n，且n尹0下列关于线性表存储结构的叙述中正确的是D。A、 链表中的元素一定存放在不连续的存储空间里B