数据结构半期考试卷.docVIP

工程技术学院 数据结构 科半期考试题 班级 学号 姓名 一、单项选择题：（每题1分，25小题，共25分） 1、链表不具有的特点是___________。 ???A、 可随机访问任一元素????????? B、 插入删除不需要移动元素 ???C、 不必事先估计存储空间????????D、 所需空间与线性表长度成正比 2、? 一个栈的输入序列是1 2 3 4 5，则下列序列中是栈的输出序列的是___________。 ?? A、 2,3,4,1,5???? B、 5,4,1,3,2???? C、? 3,1,2,4,5?? D、? 1,4,2,5,3 3、栈和队列都是_____________。 ?? A、顺序存储的线性结构??????? B、限制的线性结构 ?? C、链式存储的线性结构??????? D、限制的非线性结构 4、队列操作的原则是_____________。 A、先进先出?? B、后进先出???? C、只能进行插入? D、只能进行删除 5、3个结点可构成____________棵不同形态的二叉树。 A、2????? B、3?????? C、4????? D、5 6、下面哪一种二叉树的先序序列和后序序列正好相反？____________ A、空或者只有两个结点?????? B、高度大于其结点数 C、任一结点无左孩子?????? D、任一结点既有左孩子又有右孩子 7、深度为6（根的层次为1）的二叉树至多有____________结点。 A、 64????? B、 32?????? C、 31?????? D、 63 8、在有n个结点的二叉链表中，值为非空的链域的个数是_____________。 A、 n-1??? B、 2n-1??? C、 n+1??? D、 2n+1 9、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为______________。 A、 98????? B、 99?????? C、 50?????? D、 48 10、有一个初始为空的栈和下面的输入序列 A、 B、 C、 D、 E F、 G，现经过如下操作： push ， push ， pop ， push ， push ， top ， push ， pop ， pop ，则______ 是从栈中删除元素的序列。 A、 BEDB、 BDE C、 BEDCD、 BDEC 11．设语句x++的执行时间时单位时间，以下语句的时间复杂度是________。 for(i=1; i=n; i++) for(j=1; j=n; j++) x++; A．O(1) B．O(n) C．O(n*n*n) D．O(n*n) 12．一高度为h的非空二叉树（假设只含根节点的树的高度为1）最多有________个节点 A．2h B．2h-1 C．2h-1 D．2h 13．设双链表的节点类型定义如下， typedef struct node *link; struct node{ ListItem element; link left; link right; }*p,*q,*r; 删除双链表中节点p(由p指向的节点)的操作是______________。 q=p-left; r=p-right; q-right=r; r-left=q; q=p-right; r=p-left; q-right=r; r-left=q; q=p-left; r=p-right; q-left=r; r-right=q; D．q=p-left; r=p-right; q-right=r-left; 14．会引起循环队列队头位置发生变化的操作是____________。 A．出队列 B．入队列 C．取队首元素 D．取队尾元素 15．用指针实现二叉树，在n个节点的二叉树中含有________个空指针。 A．n B．n-1 C．n+1 D．2n 16. 具有3个结点的二叉树最多可有种不同的形态。A、2 B、3 C、4 D、5 17．已知单链表结构为 struct node{ int data; struct node *next; }*p,*q,*r ; 删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是_______________ A、q=p-next; p-next=q-next; B、p-next=p-next-next; C、r=p-next; p-next=q-next; D、q=p-next; r=q-next; p-next=r; 1