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

1、武汉软件工程职业学院软件技术专业大二2019年数据结构期末测试(1)下列数据结构，( )属于线性结构。（） 单选题 *A.图B.栈与队列(正确答案)C.集合D.树(2)非线性结构中的每个结点( )。（） 单选题 *A.无直接前趋结点B.无直接后继结点C.只有一个直接前趋结点和一个直接后继结点D.可能有多个直接前趋结点和多个直接后继结点(正确答案)(3)以下任何两个结点之间都没有逻辑关系的是( )（） 单选题 *A.图形结构B.线性结构C.树形结构D.集合(正确答案)(4)顺序存储结构的最大优点是( )。（） 单选题 *A.便于随机存取(正确答案)B.存储密度底C.无需预分配空间D.便于进行插入

2、和删除操作(5)链式存储设计时，结点内的存储单元地址()。（） 单选题 *A.一定连续(正确答案)B.定不连续C.不一定连续D.部分连续，部分不连续(1)算法能正确的实现预定功能的特性称为算法的( )。（） 单选题 *A.正确性(正确答案)B.易读性C.健壮性D.高效性(2)算法的描述便于阅读，以利于后续对算法的理解和修改称为算法的( )。（） 单选题 *A.正确性B.易读性(正确答案)C.健壮性D.高效性(3)下列算法的时间复杂度是( )（）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+=

3、y;for(k=1;k<=n;+k)+x; s+=x; 单选题 *A.O(n)B. O(n2)C. O(n3)(正确答案)D. O(1)(4)下列算法的时间复杂度是( )。（）x=0;y=0;s=0;+y; s+=y;+x; s+=x; 单选题 *A.O(n)B. O(n2)C. OO(n3)D. O(1)(正确答案)(5)下列算法的时间复杂度是( )。（）public static myOut()for (i=1; i<=n; i=10*i)printf("%4d", i); 单选题 *A.O(n)B. O(n2)C. O(n3)D. O(log10n)(正确

4、答案)(1)假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是( )。（） 单选题 *A. 106B. 107C.124D.128(正确答案)(2)假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为2，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是( )。（） 单选题 *A. 106B. 107C.114(正确答案)D.118(3)7要将一个顺序表a0,a1,an-1中第i个数据元素ai(0in-1)删除，需要移动( )个数据元素。（） 单选题 *AiB. n-i-1(

5、正确答案)C. n-iD. n-i+1(4)要在一个顺序表a0,a1,an-1的第i的位置插入一个数据元素(0in-1)，需要移动( )个数据元素。（） 单选题 *AiB. n-i-1C. n-i(正确答案)D. n-i+1(5)在有n个结点的顺序表上做插入结点运算的时间复杂度为( )。（） 单选题 *A. O(1)B. O(n)(正确答案)C. O(n2)D. O(log2n)(1)在线性表的单链表存储结构中，数据域( )。（） 单选题 *A用于记录头结点的B用于存储链表长度的C用于存储数据元素值本身(正确答案)D用于存储后继结点的地址(2)在线性表的单链表存储结构中，指针域( )。（） 单

6、选题 *A用于存储单链表首地址的B用于存储前驱结点的地址C用于存储数据元素值本身D用于存储后继结点的地址(正确答案)(3)单链表的示意图如下，指向链表Q结点的前趋的指针是( )。（）单选题 *ALBP(正确答案)CQDR(4)对于下图所示的单链表，下列表达式值为真的是( )。（）单选题 *A. head.next.data='C' 是“B”B. head.data ='B'是“A”C. P1.data='B'(正确答案)D. P2.next='E' 是空的(5)在含有n个结点的单链表中，若要插入一个指定的结点p，则首先必须找到(插

7、入位置的)( )。（） 单选题 *A头结点B后继结点C首结点D前驱结点(正确答案)(6)两个指针P和Q，分别指向单链表的两个元素，Q所指元素是P所指元素前驱的条件是( )。（） 单选题 *AP.next=Q.nextBP.next= QCQ.next= P(正确答案)DP= Q(1)关于单循环链表的描述，正确的是( )。（） 单选题 *A.将单链表的最后一个结点的后继指针指向第一个结点(正确答案)B.每一个结点有两个指针域C.每一个结点有两个数值域D.存在由前驱指针和后继指针连接而成的两个环(2)关于双向链表的描述，正确的是( )。（） 单选题 *A.将单链表的最后一个结点的后继指针指向第一个

8、结点B.每一个结点有两个指针域(正确答案)C.每一个结点有两个数值域D.存在由前驱指针和后继指针连接而成的两个环(3)访问p结点的后继节点的于java语句( )。（） 单选题 *Ap =p.next.next;B.p.next=p;Cp.next=p.next.next;D.p =p.next;(正确答案)(4)在顺序表i的位置插入一个元素，该算法中的循环语句for(int j = curLen;j>i;j-)的循环体语句是( )，其中curLen表示顺序表长度，listElem 中存放顺序表。（） 单选题 *A.listElemj=listElemj-1(正确答案)B.listElem

9、j+1=listElemjC.listElemj=listElemj+1D.listElemj-1=listElemj(5)从顺序表上删除第i个元素，该算法中的循环语句for(int j = i; j<curLen-i; j+)的循环体语句是( )，其中curLen表示顺序表长度，listElem 中存放顺序表。（） 单选题 *A.listElemj=listElemj-1B.listElemj+1=listElemjC.listElemj=listElemj+1(正确答案)D.listElemj-1=listElemj(1)如下图所示不带头结点的链栈，top为栈顶指针，则栈顶元素是(

10、)（）单选题 *AH(正确答案)BBCCDD(2)在一个栈顶指针为top的不带头结点的链栈中，将栈置空，应执行下列( )命令。（） 单选题 *Atop =null;(正确答案)Btop=0；Ctop.next=null;Dtop.next=0;(3)在一个栈顶指针为top的链栈中，取栈顶元素，应执行下列( )命令。（） 单选题 *Adata.top；Bdata;Ctop.next;Dtop.data;(正确答案)(4)在链栈中，进行入栈操作时( )。（） 单选题 *A需要判断栈是否满B. 需要判断栈是否为空C. 需要判断栈元素的类型D. 无需对栈作任何判别(正确答案)(5)在队列中存取数据的原

11、则是( )。（） 单选题 *A. 先进先出(正确答案)B. 先进后出C. 后进先出D. 没有限制(6)在链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则队列的判空条件是( )。（） 单选题 *Arear=frontB. front!=rearC. front=null(正确答案)D. front=rear+1(1)下面关于顺序队列的描述正确的是( )。（） 单选题 *A.顺序队列存在假溢出问题。(正确答案)B.初始化顺序队列时，不必指定其大小。C.顺序队列采用链式结构实现。D顺序队列是目前应用比较广泛的一种数据结构。(2)如何解决顺序队列的假溢出现象( )

12、。（） 单选题 *A采用多一个存储空间的方法B构造循环顺序队列(正确答案)C采用设置状态位的方法D采用设置计数器的方法(3)下面关于循环顺序队列的描述正确的是( )。（） 单选题 *A.循环顺序队列采用链式结构实现。B.初始化循环顺序队列时，不必指定其大小。C.循环顺序队列存在假溢出问题。D.通过对顺序队列最大长度的取模运算构造出循环顺序队列。(正确答案)(4)循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的判满条件是( )。（） 单选题

13、 *Arear=front+1B. front!=rearC. front=rear+1D. front=(rear+1)% maxSize(正确答案)(5)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列置空语句是( )。（） 单选题 *A. rear=front=0(正确答案)B. rear=front=nullC. rear=frontD. front=0(6)在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件

14、，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，使用queueElem 数组存储循环顺序队列，则访问队尾元素的java语句是( )。（） 单选题 *A.queueElem(rear-1+queueElem.length)%queueElem.length;(正确答案)(1)链式存储结构的最大优点是( )。（） 单选题 *A无需预分配空间B存储密度高C便于进行插入和删除操作(正确答案)D便于随机存取(2)下列数据结构，( )不属于线性结构。（） 单选题 *A树(正确答案)B队列C线性表D栈(3)每个结点只含有一个数据

15、元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为( )结构。（） 单选题 *A链式存储B散列存储C索引存储D顺序存储(正确答案)(4)线性结构中的每个结点( )。（） 单选题 *A无直接后继结点B可能有多个直接前趋结点和多个直接后继结点C除起始节点和终端节点外，只有一个直接前趋结点和一个直接后继结点(正确答案)D无直接前趋结点(5)下列( )结构中的数据元素的关系是“多对多”的关系。（） 单选题 *A图(正确答案)B线性表C二叉树D栈与队列(6)下列算法的时间复杂度是( )。（）x=0;y=0;s=0;for(k=1;k<=n;+k)+x; s+=x;for(i=1;i&

16、lt;=n;+i)for(j=1;j<=n;+j)+y; s+=y; 单选题 *A.O(n3)B.O(n)C.O(1)D.O(n2)(正确答案)(7)算法在发生非法操作时可以作出处理的特性称为算法的( )。（） 单选题 *A.高效性B.健壮性(正确答案)C.易读性D.正确性(8)下列算法的时间复杂度是( )。（）public static int rSearch(int a,int x)int n=a.length;for(int i=0; i<n&&!x.equals(ai);i+);if (i=n)return -1;elsereturn i; 单选题 *A.O

17、(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.后继结点的值(2)在线性表的单链表存储结构中，用于存储后继结点地址的是( )。（） 单选题 *A.指针域(正确答案)B

18、.头结点C.数据元素D.数据域(3)对于下图所示的单链表，下列表达式值为真的是( )。（） 单选题 *A.head.next.data='C'B.head.data ='A'(正确答案)C.P1.data='D'D.P2.next='E'(4)两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是( )。（） 单选题 *A.Q.next= PB.P.next=Q.nextC.P= QD.P.next= Q(正确答案)(5)在含有n个结点的单链表中，若要删除一个指定的结点p，则首先必须找到( )。（） 单选题

19、*A头结点B后继结点C前驱结点(正确答案)D首结点(6)假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为110，则第6个数据元素的存储地址是( )。（） 单选题 *A116B130C115D134(正确答案)(7)假设在顺序表a0,a1,an1中，每一个数据元素所占的存储单元的数目为2，且第0个数据元素的存储地址为120，则第8个数据元素的存储地址是( )。（） 单选题 *A136(正确答案)B108C107D134(8)要将一个顺序表a0,a1,an-1中第5个数据元素ai(0in-1)删除，需要移动( )个数据元素。（） 单选题 *An

20、-5B5Cn-5+1Dn-6(正确答案)(9)在有n个结点的顺序表上做查找结点运算的时间复杂度为( )。（） 单选题 *AO(log2n)BO(n)(正确答案)CO(1)DO(n2)(10)在有n个结点的顺序表上做删除结点运算的时间复杂度为( )。（） 单选题 *AO(n2)BO(log2n)CO(1)DO(n)(正确答案)(11)在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是( )。（） 单选题 *AO(n)(正确答案)BO(1)CO(log2n)DO(n2)(12)要在一个顺序表a0,a1,an-1的第8的位置插入一个数据元素(0in-1)，需要移

21、动( )个数据元素。（） 单选题 *An-8+1B8Cn-8-1Dn-8(正确答案)(13)关于单循环链表的描述，正确的是( )。（） 单选题 *A.存在由前驱指针和后继指针连接而成的两个环B.将单链表的最后一个结点的后继指针指向第一个结点(正确答案)C.每一个结点有两个指针域D.每一个结点有两个数值域(14)关于双向链表的描述，正确的是( )。（） 单选题 *A.将单链表的最后一个结点的后继指针指向第一个结点B.每一个结点有两个数值域C.存在由前驱指针和后继指针连接而成的两个环D.每一个结点有两个指针域(正确答案)(15)从顺序表上删除第i个元素，该算法中的循环语句for(int j = i

22、; j<curLen-i;j+)的循环体语句是( )，其中curLen表示顺序表长度，listElem 中存放顺序表。（） 单选题 *A.istElemj+1=listElemjB.listElemj-1=listElemjC.listElemj=listElemj+1(正确答案)D.listElemj=listElemj-1(16)在顺序表i的位置插入一个元素，该算法中的循环语句for(int j = curLen;j>i;j-)的循环体语句是( )，其中curLen表示顺序表长度，listElem 中存放顺序表。（） 单选题 *A .listElemj-1=listElemjB

23、.listElemj=listElemj-1(正确答案)C.listElemj+1=listElemjD.listElemj=listElemj+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.先进先出(2)若将字符A、B、C、D依次进栈，则不可能得到的出栈序列是( )。（） 单选题 *A.ACBDB.ABCDC.ADBC(正确答案)D.D

24、CBA(3)在顺序栈中，进行入栈操作时( )。（） 单选题 *A.需要判断栈是否为空B.无需对栈作任何判别C.需要判断栈元素的类型D.需要判断栈是否满(正确答案)(4)在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，使用stackElem 数组存储顺序栈，则栈顶元素的访问形式是( ) 。（） 单选题 *A.stackElem0B.stackElemtopC.stackElemtop-1(正确答案)D.top.data(5)在顺序栈中，假设栈顶指针top是指向栈顶元素的下一个存储单元，使用stackElem 数组存储顺序栈，则表示栈长度的语句是( ) 。（） 单选题 *A.stac

25、kElemtopB.top(正确答案)C.top-1D.stackElemtop-1(6)若将整数3、4、5、6依次进栈，则不可能得到的出栈序列是( )。（） 单选题 *A.6543B.3645(正确答案)C.3546D.3456(7)在一个栈顶指针为top的链栈中，判断栈空，应执行下列( )命令。（） 单选题 *A.top=0；B.top.next=0;C.top.next=null;D.top =null;(正确答案)(8)在链栈中，进行出栈操作时( )。（） 单选题 *A.需要判断栈是否满B.无需对栈作任何判别C.需要判断栈是否为空(正确答案)D.需要判断栈元素的类型(9)在一个栈顶指针

26、为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.d

27、ata;(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分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则取队首元素的语句是( )。（） 单选题 *Arear.data;Bfront.data；(正确答案

28、)Crear.next.data;Dfront.next.data;(14)下面关于对队列的描述不正确的是( )。（） 单选题 *A队列是一种操作受限的特殊线性表。B队列中存取数据的原则是先进先出。C所有的插入操作均限制在表的一端进行，而所有的删除操作都限制在表的另一端进行。D允许插入的一端称为队首，允许删除的一端称为队尾。(正确答案)(15)在非空链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，使用p保存出队结点，则出队语句是( )。（） 单选题 *Ap=front; front=front.next;(正确答案)Bfront=front.next; p=

29、front;Crear.next=p；rear=p;Drear=p;rear.next=p；(16)在非空链队列中，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素，则将结点p入队语句是( )。（） 单选题 *Arear.next=p；rear=p;(正确答案)Bfront=front.next; p=front;Crear=p; rear.next=p；Dp=front; front=front.next;(17)循环顺序队列中，采用以下哪一种方法不能区分队列判满和判空的条件（） 单选题 *A.采用设置标志变量的方法B.采用多一个存储空间的方法(正确答案)C.采用设置计数器的方法