武汉软件工程职业学院软件技术专业大二2019年数据结构期末测试

武汉软件工程职业学院软件技术专业大二2019年数据结构期末测试（1）下列数据结构，（）属于线性结构。（）［单选题］*A.图B.栈与队列（正确答案）C.集合D.树⑵非线性结构中的每个结点（）。（）［单选题］*A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D.可能有多个直接前趋结点和多个直接后继结点（正确答案）⑶以下任何两个结点之间都没有逻辑关系的是（）（）［单选题］*A.图形结构B.线性结构C.树形结构D.集合（正确答案）⑷顺序存储结构的最大优点是（）。（）［单选题］*A.便于随机存取（正确答案）B.存储密度底C.无需预分配空间D.便于进行插入和删除操作⑸链式存储设计时，结点内的存储单元地址（）。（）［单选题］*A.一定连续（正确答案）B.一定不连续C.不一定连续D.部分连续，部分不连续（1）算法能正确的实现预定功能的特性称为算法的（）。（）［单选题］*A.正确性（正确答案）B.易读性C.健壮性D.高效性⑵算法的描述便于阅读，以利于后续对算法的理解和修改称为算法的（）。（）［单选题］*A.正确性B.易读性（正确答案）C.健壮性D.高效性⑶下列算法的时间复杂度是（）（）x=0;y=0;s=0;for（i=1;i<=n;++i）for（k=1;k<=n;++k）for（j=1;j<=n;++j）｛++y;s+=y;）for（k=1;k<=n;++k）｛++x;s+=x;｝［单选题］*A.O(n)O(n2)O(n3)(正确答案)O(1)⑷下列算法的时间复杂度是()。()x=0;y=0;s=0;++y;s+=y;++x;s+=x;［单选题］*A.O(n)O(n2)OO(n3)O(1)(正确答案)⑸下列算法的时间复杂度是()。()publicstaticmyOut()｛for(i=1;i<=n;i=10*i)printf("%4d",i);｝［单选题］*A.O(n)O(n2)O(n3)O(log10n)(正确答案)（1）假设在顺序表｛a0,a1,……,an-1｝中，每一个数据元素所占的存储单元的数目为4,且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（）。（）［单选题］*106107C.124D.128（正确答案）⑵假设在顺序表｛a0,a1,……,an-1｝中，每一个数据元素所占的存储单元的数目为2,且第0个数据元素的存储地址为100,则第7个数据元素的存储地址是（）。（）［单选题］*106107C.114（正确答案）D.118（3）7.要将一个顺序表｛a0,a1,……,an-1｝中第i个数据元素ai（0SiSn-1）删除，需要移动（）个数据元素。（）［单选题］*A.in-i-1（正确答案）n-in-i+1⑷要在一个顺序表｛a0,a1,……,an-1｝的第i的位置插入一个数据元素（0SiSn-1）,需要移动（）个数据元素。（）［单选题］*A.in-i-1n-i（正确答案）n-i+1［单选题］*⑸在有n［单选题］*0（1）0（n）（正确答案）0（n2）O（log2n）（1）在线性表的单链表存储结构中，数据域（）。（）［单选题］*A.用于记录头结点的B.用于存储链表长度的C.用于存储数据元素值本身（正确答案）D.用于存储后继结点的地址⑵在线性表的单链表存储结构中，指针域（）。（）［单选题］*A.用于存储单链表首地址的B.用于存储前驱结点的地址C.用于存储数据元素值本身D.用于存储后继结点的地址（正确答案）⑶单链表的示意图如下，指向链表Q结点的前趋的指针是（）。（）TOC\o"1-5"\h\z1rJ〕i। ।才mAs3「 B-i3-r-w/ /""at ~~: -Q। ［单选题］*A.LB.P（正确答案）⑷对于下图所示的单链表，下列表达式值为真的是（）。（）,—口/*—►e［单选题］*head.next.data='C'是“3head.data=='B'是"A”P1.data=='B'（正确答案）P2.next=='E'是空的⑸在含有n个结点的单链表中，若要插入一个指定的结点p，则首先必须找到（插入位置的）（）。（）［单选题］*A.头结点B.后继结点C.首结点D.前驱结点（正确答案）（6）两个指针P和Q,分别指向单链表的两个元素，Q所指元素是P所指元素前驱的条件是（）。（）［单选题］*A.P.next==Q.nextB.P.next==QC.Q.next==P（正确答案）D.P==Q（1）关于单循环链表的描述，正确的是（）。（）［单选题］*A.将单链表的最后一个结点的后继指针指向第一个结点（正确答案）B.每一个结点有两个指针域C.每一个结点有两个数值域D.存在由前驱指针和后继指针连接而成的两个环⑵关于双向链表的描述，正确的是（）。（）[单选题]*A..将单链表的最后一个结点的后继指针指向第一个结点B.每一个结点有两个指针域（正确答案）C.每一个结点有两个数值域D.存在由前驱指针和后继指针连接而成的两个环⑶访问p结点的后继节点的于java语句（）。（）[单选题]*A.p二p.next.next;B.p.next二p;C.p.next二p.next.next;D.p二p.next;（正确答案）⑷在顺序表i的位置插入一个元素，该算法中的循环语句for（intj=curLen;j>i;j--）的循环体语句是（），其中curLen表示顺序表长度，listElem□中存放顺序表。（）[单选题]*A.listElem[j]=listElem[j-1]（正确答案）B.listElem[j+1]=listElem[j]C.listElem[j]=listElem[j+1]D.listElem[j-1]=listElem[j]⑸从顺序表上删除第i个元素，该算法中的循环语句for（intj=i;j<curLen-i;j++）的循环体语句是（），其中curLen表示顺序表长度，listElem□中存放顺序表。（）[单选题]*A.listElem[j]=listElem[j-1]B.listElem[j+1]=listElem[j]C.listElem[j]=listElem[j+1]（正确答案）D.listElem[j-1]=listElem[j]（1）如下图所示不带头结点的链栈，top为栈顶指针，则栈顶元素是（）（）j2口H| A| |-JB| D[.[单选题]*A.H（正确答案）B.BC.CD.D⑵在一个栈顶指针为top的不带头结点的链栈中，将栈置空，应执行下列（）命令。（）[单选题]*A.top=null;（正确答案）B.top=0；C.top.next二null;D.top.next=0;⑶在一个栈顶指针为top的链栈中，取栈顶元素，应执行下列（）命令。（）[单选题]*A. data.top；B. data;C. top.next;D. top.data;（正确答案）⑷在链栈中，进行入栈操作时（）。（）［单选题］*A.需要判断栈是否满B.需要判断栈是否为空C.需要判断栈元素的类型D.无需对栈作任何判别（正确答案）⑸在队列中存取数据的原则是（）。（）［单选题］*A.先进先出（正确答案）B.先进后出C.后进先出D.没有限制（6）在链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则队列的判空条件是（）。（）［单选题］*A.rear==frontfront!二rearfront==null（正确答案）front==rear+1（1）下面关于顺序队列的描述正确的是（）。（）［单选题］*A.顺序队列存在假溢出问题。（正确答案）B.初始化顺序队列时，不必指定其大小。C.顺序队列采用链式结构实现。D顺序队列是目前应用比较广泛的一种数据结构。（2）如何解决顺序队列的假溢出现象（）。（）［单选题］*A.采用多一个存储空间的方法B.构造循环顺序队列（正确答案）C.采用设置状态位的方法D.采用设置计数器的方法⑶下面关于循环顺序队列的描述正确的是（）。（）［单选题］*A.循环顺序队列采用链式结构实现。B.初始化循环顺序队列时，不必指定其大小。C.循环顺序队列存在假溢出问题。D.通过对顺序队列最大长度的取模运算构造出循环顺序队列。（正确答案）⑷循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize,则队列的判满条件是（）。（）［单选题］*A.rear==front+1front!二rearfront==rear+1front==（rear+1）%maxSize（正确答案）⑸在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize,则队列置空语句是（）。（）［单选题］*rear二front=0（正确答案）rear二front二nullrear二frontD.front=0（6）在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，使用queueElem口数组存储循环顺序队列，则访问队尾元素的java语句是（）。（）［单选题］*A.queueElem［（rear-1+queueElem.length）%queueElem.length］;（正确答案）（1）链式存储结构的最大优点是（）。（）［单选题］*A.无需预分配空间B.存储密度高C.便于进行插入和删除操作（正确答案）D.便于随机存取⑵下列数据结构，（）不属于线性结构。（）［单选题］*A.树（正确答案）B.队列C.线性表D.栈⑶每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（）结构。（）［单选题］*A•链式存储B.散列存储C.索弓［存储D.顺序存储（正确答案）（4）线性结构中的每个结点（）。（）［单选题］*A.无直接后继结点B.可能有多个直接前趋结点和多个直接后继结点C.除起始节点和终端节点外，只有一个直接前趋结点和一个直接后继结点(正确答案)D.无直接前趋结点⑸下列()结构中的数据元素的关系是“多对多''的关系。()［单选题］*A.图(正确答案)B.线性表C.二叉树D.栈与队列(6)下列算法的时间复杂度是()。()x=0;y=0;s=0;for(k=1;k<=n;++k){++x;s+=x;)for(i=1;i<=n;++i)for(j=1;j<=n;++j){++y;s+=y;}［单选题］*A.O(n3)B.O(n)C.O(1)D.O(n2)(正确答案)⑺算法在发生非法操作时可以作出处理的特性称为算法的()。()［单选题］*A.高效性B.健壮性(正确答案)C.易读性D.正确性⑻下列算法的时间复杂度是()。()publicstaticintrSearch(int［］a,intx){intn=a.length;for(inti=0;i<n&&!x.equals(a［i］);i++);if(i==n)return-1;elsereturni;}［单选题］*A.O(n3)B.O(n)(正确答案)C.O(1)D.O(n2)(9)算法分析的两个主要方面是()。()［单选题］*A.正确性和简明性B.可读性和文档性C.数据复杂性和程序复杂性D.空间复杂性和时间复杂性(正确答案)(10)算法要做到执行时间尽量短，所需最大存储空间尽量少称为算法的()。()［单选题］*A.正确性B.高效性(正确答案)C.健壮性D.易读性（1）在线性表的单链表存储结构中，用于存储数据元素值本身的是（）（）［单选题］*A.指针域B.头结点C.数据域（正确答案）D.后继结点的值⑵在线性表的单链表存储结构中，用于存储后继结点地址的是（）。（）［单选题］*A.指针域（正确答案）B.头结点C.数据元素D.数据域⑶对于下图所示的单链表，下列表达式值为真的是（）。（）［单选题］*A.head.next.data='C'B.head.data=='A'（正确答案）C.P1.data=='D'D.P2.next=='E'⑷两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。（）［单选题］*A.Q.next==PB.P.next==Q.nextC.P==QD.P.next==Q（正确答案）⑸在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到（）。（）［单选题］*A.头结点B.后继结点C.前驱结点（正确答案）D.首结点（6）假设在顺序表｛a0,a1,……,an-1｝中，每一个数据元素所占的存储单元的数目为4,且第0个数据元素的存储地址为110，则第6个数据元素的存储地址是（）。（）［单选题］*TOC\o"1-5"\h\zA. 116B. 130C. 115D. 134（正确答案）⑺假设在顺序表｛a0,a1,……,an-1｝中，每一个数据元素所占的存储单元的数目为2,且第0个数据元素的存储地址为120,则第8个数据元素的存储地址是（）。（）［单选题］*A. 136（正确答案）TOC\o"1-5"\h\zB. 108C. 107D. 134⑻要将一个顺序表｛a0,a1,……,an-1｝中第5个数据元素ai（0SiSn-1）删除，需要移动（）个数据元素。（）［单选题］*A. n-5B. 5C. n-5+1D. n-6（正确答案）(9)在有n个结点的顺序表上做查找结点运算的时间复杂度为()。()［单选题］*A.O(log2n)B.O(n)(正确答案)C.O(1)D.O(n2)(10)在有n个结点的顺序表上做删除结点运算的时间复杂度为()。()［单选题］*A.O(n2)B.O(log2n)C.O(1)D.O(n)(正确答案)(11)在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是()。()［单选题］*A.O(n)(正确答案)B.O(1)C.O(log2n)D.O(n2)(12)要在一个顺序表｛a0,a1,……,an-1｝的第8的位置插入一个数据元素(0SiSn-1),需要移动()个数据元素。()［单选题］*TOC\o"1-5"\h\zA. n-8+1B. 8C. n-8-1D. n-8(正确答案)(13)关于单循环链表的描述，正确的是()。()［单选题］*A.存在由前驱指针和后继指针连接而成的两个环B.将单链表的最后一个结点的后继指针指向第一个结点（正确答案）C.每一个结点有两个指针域D.每一个结点有两个数值域（14）关于双向链表的描述，正确的是（）。（）[单选题]*A.将单链表的最后一个结点的后继指针指向第一个结点B.每一个结点有两个数值域C.存在由前驱指针和后继指针连接而成的两个环D.每一个结点有两个指针域（正确答案）（15）从顺序表上删除第i个元素，该算法中的循环语句for（intj=i;j<curLen-i;j++通循环体语句是（），其中curLen表示顺序表长度，listElem□中存放顺序表。（）[单选题]*A.istElem[j+1]=listElem[j]B.listElem[j-1]=listElem[j]C.listElem[j]=listElem[j+1]（正确答案）D.listElem[j]=listElem[j-1]（16）在顺序表i的位置插入一个元素，该算法中的循环语句for（intj=curLen;j>i;j--）的循环体语句是（），其中curLen表示顺序表长度，listElem□中存放顺序表。（）[单选题]*A.listElem[j-1]=listElem[j]B.listElem[j]=listElem[j-1]（正确答案）C.listElem[j+1]=listElem[j]D.listElem[j]=listElem[j+1]（17）访问p结点的后继节点的于java语句（）。（）[单选题]*A.p.next二p;B.p.next二p.next.next;C.p二p.next;（正确答案）D.p二p.next.next;（1）在栈中存取数据的原则是（）（）［单选题］*A.后进先出（正确答案）B.后进后出C.没有限制D.先进先出⑵若将字符A、B、C、D依次进栈，则不可能得到的出栈序列是（）。（）［单选题］*A.ACBDB.ABCDC.ADBC（正确答案）D.DCBA⑶在顺序栈中，进行入栈操作时（）。（）［单选题］*A.需要判断栈是否为空B.无需对栈作任何判别C.需要判断栈元素的类型D.需要判断栈是否满（正确答案）⑷在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，使用stackElem口数组存储顺序栈，则栈顶元素的访问形式是（）。（）［单选题］*A.stackElem[0]B.stackElem[top]C.stackElem[top-1]（正确答案）D.top.data⑸在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，使用stackElem口数组存储顺序栈，则表示栈长度的语句是（）。（）［单选题］*A.stackElem［top］B.top（正确答案）C.top-1D.stackElem［top-1］（6）若将整数3、4、5、6依次进栈，则不可能得到的出栈序列是（）。（）［单选题］*A.6543B.3645（正确答案）C.3546D.3456⑺在一个栈顶指针为top的链栈中，判断栈空，应执行下列（）命令。（）［单选题］*A.top=0；B.top.next==0;C.top.next==null;D.top=null;（正确答案）⑻在链栈中，进行出栈操作时（）。（）［单选题］*A.需要判断栈是否满B.无需对栈作任何判别C.需要判断栈是否为空（正确答案）D.需要判断栈元素的类型（9）在一个栈顶指针为top的链栈中执行链栈操作时，通常会再初始化一个指向栈顶的指针P，则下面描述不正确的是（）。（）［单选题］*A.可以使用p！=null;来判断是否访问到栈尾。B.在遍历链栈的过程中执行p=p.next;语句完成访问后继结点的功能。C.top指针始终指向栈顶。D.也可以将p初始化为栈底指针。（正确答案）（10）从一个栈顶指针为top的链栈中执行出栈操作，用x保存出栈结点的值，应执行下列（）命令。（）［单选题］*A.top二top.next;x=top.data;B.x二top;top二top.next;C.x二top.data;top二top.next;（正确答案）D.x二top.data;（11）在一个栈顶指针为top的链栈中，将一个s指针所指的结点入栈，应执行下列（）命令。（）［单选题］*A.top.next二s;B.s.next=top.next;top.next=s;C.s.next二top.next;top二s;D.s.next二top;top二s;（正确答案）（12）在队列中存取数据的原则是（）。（）［单选题］*A.没有限制B.后进后出（正确答案）C.先进后出D.后进先出（13）在链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则取队首元素的语句是（）。（）［单选题］*A.rear.data;B.front.data；（正确答案）C.rear.next.data;D.front.next.data;（14）下面关于对队列的描述不正确的是（）。（）［单选题］*A.队列是一种操作受限的特殊线性表。B.队列中存取数据的原则是先进先出。C.所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行。D.允许插入的一端称为队首，允许删除的一端称为队尾。（正确答案）（15）在非空链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，使用p保存出队结点，则出队语句是（）。（）［单选题］*A.p=front;front二front.next;（正确答案）B.front二front.next;p=front;C.rear.next=p；rear=p;D.rear二p;rear.next=p；（16）在非空链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则将结点p入队语句是（）。（）［单选题］*A.rear.next=p；rear二p;（正确答案）B.front二front.next;p=front;C.rear=p;rear.next=p；D.p=front;front二front.next;(17)循环顺序队列中，采用以下哪一种方法不能区分队列判满和判空的条件()[单选题]*A.采用设置标志变量的方法B.采用多一个存储空间的方法(正确答案)C.采用设置计数器的方法