数据结构期末复习题及答案.doc

《数据结构期末复习题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、一、是非题1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。.......................(T)2.线性表的逻辑顺序与物理顺序总是一致的........(F)3.线性表中的每个结点最多只有一个前驱和一个后继。......(T)4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................(F)5.栈和队列逻辑上都是线性表。..........................(T)6.单链表从任何一个结点

2、出发，都能访问到所有结点........(F)7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(T)8.在用单链表表示的链式队列中，队头在链表的链尾位置。....(F)9.多维数组是向量的推广。..............................(T)10.栈是一种先进先出的线性表。....(F)11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......(T)1

3、2.设串S的长度为n,则S的子串个数为n(n+1)/2。...........(F)13.一般树和二叉树的结点数目都可以为0。................(F)14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结点。....(T)15.后序序列和中序序列能唯一确定一棵二叉树。....(T)16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂度为O(n).............(T)17.网络的最小代价生成树是唯一的。...(T)18.图的拓扑有序序列不是唯一的。..

4、.(T)19.进行折半搜索的表必须是顺序存储的有序表。...(T)二、单选题1.算法指的是（D）A．计算机程序      B．解决问题的计算方法C．排序算法        D．解决问题的有限运算序列2.线性表采用链式存储时，结点的存储地址（B）A．必须是不连续的B．连续与否均可C．必须是连续的D．和头结点的存储地址相连续3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C）A．O（1）        B．O（n）    C．O（m）    D．O（m+n）4.在一个长度为n的顺序表的表尾插入一个

5、新元素的渐进时间复杂度为(B)。A．O(n)B．O(1)C．O(n2)D．O(log2n)T5.线性表L在(B)情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.L中含有大量的结点D.L中结点结构复杂6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?(B)A．s一>1ink=p一>1ink；p一>1ink＝sB．q一>1ink＝s；s一>link=pC．p一>link＝s一>1i

6、nk；s一>1ink＝pD．p一>1ink＝s；s一>1ink＝q1.已知指针p所指不是尾结点，若在*p之后插入结点*s，应执行下列哪个操作(B)　　A.s->link=p；p->link=s；　　B.s->link=p->link；p->link=s；　　C.s->link=p->link；p=s；　　D.p->link=s；s->link=p；2.非空的循环单链表first的尾结点（由p所指向）满足：(C)　　A.p->link==NULL；　　B.p==NULL；　　C.p->link==first；　　D.

7、p==first；3.若让元素1，2，3依次进栈，则出栈次序不可能出现(C)种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，24.若进栈序列为1234，则不可能得到的出栈序列是C。A）3，2,1，4B）3,2，4,1，C）4,2，3,1D）2,3，4,15.由两个栈共享一个向量空间的好处是：（B）A．减少存取时间，降低下溢发生的机率B．节省存储空间，降低上溢发生的机率C．减少存取时间，降低上溢发生的机率D．节省存储空间，降低下溢发生的机率6.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R

8、。若在逻辑上看一个环，则队列中元素的个数为......................(D)A．R-FB.n+R-FC.(R-F+1)modnD.(n+R-F）modn7.在一个链队列中,假定front和rear分别为队首和队尾指针，则插入指针s所指的结点的操作为C。A）front->next=s;B)s->next=rear;rear=s;C)rear->