《数据结构附含答案解析》由会员分享,可在线阅读,更多相关《数据结构附含答案解析(20页珍藏版)》请在金锄头文库上搜索。
1、数据结构与算法复习题选择题1 在数据结构中,从逻辑上可以把数据结构分为C 。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D部结构和外部结构2数据结构在计算机存中的表示是指 A 。A数据的存储结构B数据结构C数据的逻辑结构 D数据元素之间的关系3在数据结构中,与所使用的计算机无关的是数据的A 结构。A 逻辑 B 存储 C 逻辑和存储D 物理4在存储数据时,通常不仅要存储各数据元素的值,而且还要存储C。A数据的处理方法B数据元素的类型C数据元素之间的关系D数据的存储方法5在决定选取何种存储结构时,一般不考虑A 。A各结点的值如何B结点个数的多少C对数据有哪些运算D所用的编程语言
2、实现这种结构是否方便。6以下说确的是 D 。A数据项是数据的基本单位B数据元素是数据的最小单位C数据结构是带结构的数据项的集合D些表面上很不相同的数据可以有相同的逻辑结构(1) A 找出数据结构的合理性C分析算法的效率以求改进(2) A 空间复杂度和时间复杂度C可读性和文档性B研究算法中的输入和输出的关系C分析算法的易读性和文档性B正确性和简明性D数据复杂性和程序复杂性8下面程序段的时间复杂度是s =0;for( I =0; in; i+)for(j=0;jn;j+)s +=Bij;sum = s ;9下面程序段的时间复杂度是for( i =0; in; i+) for(j=0;jm;j+)A
3、ij = 0;10 下面程序段的时间复杂度是 3i = 0 ;while(inext =NULLC head-next =headD head!=NULL15 带头结点的单链表head为空的判定条件是 B 。A head = NULLB head-next =NULLC head-next =headD head!=NULL16若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个 结点,则采用D存储方式最节省运算时间。A单链表 B给出表头指针的单循环链表C双链表 D带头结点的双循环链表17需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是B_。A 单链表 B静态链表
4、C线性链表 D顺序存储结构18 非空的循环单链表head的尾结点(由p所指向)满足 C 。Ap-next = NULLBp = NULLC p-next =headD p = head19 在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。A p-prior = s ; s-next=p ; p-prior-next = s ; s-prior = p-priorB p-prior = s ; p-prior-next = s;s-next = p ; s-prior = p-priorC s-next = p ; s-prior=p-prior;p-prior = s ; p-pr
5、ior-next = sD s-next = p ; s-prior=p-prior;p-prior-next = s ; p-prior = s20 如果最常用的操作是取第i个结点及其前驱,则采用D 存储方式最节省 时间。A 单链表 B 双链表 C 单循环链表 D 顺序表21 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时 间复杂度是氏。A0(1) BO(n) C0(n2) D O (nlog2n)22 在一个长度为n (n1)的单链表上,设有头和尾两个指针,执行 B 操 作与链表的长度有关。A删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一
6、个新元素D在单链表最后一个元素后插入一个新元素23 与单链表相比,双链表的优点之一是 D 。A插入、删除操作更简单B可以进行随机访问C可以省略表头指针或表尾指针D顺序访问相邻结点更灵活24 如果对线性表的操作只有两种,即删除第一个元素,在最后一个元素的后 面插入新元素,则最好使用 B 。A 只有表头指针没有表尾指针的循环单链表B 只有表尾指针没有表头指针的循环单链表C非循环双链表D循环双链表25 在长度为n的顺序表的第i个位置上插入一个元素(1W i Wn+1),元素的移动次数为:。An- i + 1Bn- iCiDi- 126对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为 C
7、。A顺序表B 用头指针表示的循环单链表C用尾指针表示的循环单链表D单链表27 下述哪一条是顺序存储结构的优点?C 。A插入运算方便 B可方便地用于各种逻辑结构的存储表示C存储密度大D删除运算方便28 下面关于线性表的叙述中,错误的是哪一个?B 。A线性表采用顺序存储,必须占用一片连续的存储单元B线性表采用顺序存储,便于进行插入和删除操作。C线性表采用链式存储,不必占用一片连续的存储单元D线性表采用链式存储,便于进行插入和删除操作。29 线性表是具有n个 B的有限序列。A 字符B数据元素C数据项D 表元素30 在n个结点的线性表的数组实现中,算法的时间复杂度是0(1 )的操作是A。A 访问第i
8、(1=i=n)个结点和求第i个结点的直接前驱(1i=n)B 在第i (1=i=n)个结点后插入一个新结点C 删除第i (1=inext=s ; s-next=p-next next=s;C p-next=s ; p-next=s-next36线性表的顺序存储结构是一种 AA随机存取的存储结构C索引存取的存储结构37 栈的特点是B ,队列的特点是A先进先出B先进后出38 栈和队列的共同点是 C 。A都是先进后出C只允许在端点处插入和删除元素39 一个栈的进栈序列是a,b,c,d,e C 。B s-next=p-next ; p-D p-next=s-next ; p-next=sB都是先进先出D
9、没有共同点则栈的不可能的输出序列是B顺序存取的存储结构D Hash存取的存储结构A。A edcba B decba C dceab D abcde40 设有一个栈,元素依次进栈的顺序为A、B、C、D、E。下列 C 是不可 能的出栈序列。AA,B,C,D,E BB,C,D,E,A C E,A,B,C,D D E,D,C,B,A41 以下 B 不是队列的基本运算?A从队尾插入一个新元素B从队列中删除第i个元素42 若已知一个栈的进栈序列是l,2,3,n,其输出序列为pl,p2, p3,pn,若 p1 = n,贝U pi 为 C 。A i B ni C n i +1 D 不确定43 判定一个顺序栈s
10、t (最多元素为MaxSize)为空的条件是 B 。A st-top!=-1Bst-top=-1C st-top!=MaxSizeDst-top =MaxSize44 判定一个顺序栈st (最多元素为MaxSize)为满的条件是 D 。A st-top!=-1Bst-top=-1C st-top!=MaxSizeDst-top=MaxSize45 一个队列的入队序列是1,2,3, 4,则队列的输出序列是B 。A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,146 判定一个循环队列qu (最多元素为MaxSize)为空的条件是 C 。A qu-rear - qu-front =Ma
11、xSizeB qu-rear - qu-front -1=MaxSizeC qu-rear =qu-frontD qu-rear =qu-front -147 在循环队列中,若front与rear分别表示对头元素和队尾元素的位置,则判断循环队列空的条件是 C 。B rear=front+1C front=rearA front=rear+1D front=048 向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时,应执 行D操作。Ah-next=s ; Bs-next=h ;C s-next=h ;h =s ; D s-next=h-next ;h-next=s ;49 输入序列为ABC,可以变为CBA时,经过的栈操作为B 。A push,pop,push,pop,push,pop B push,push,push,pop, pop, popC push,push,pop, pop,push,pop D push,pop,push,push, pop, pop50 若栈采用顺序存储方式存储,现两栈共享空间V1 m,