数据结构期末复习.docx

《数据结构期末复习.docx》由会员分享，可在线阅读，更多相关《数据结构期末复习.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构期末复习1.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。 单选题 *A. edcbaB. decbaC. dceab(正确答案)D. abcde2.若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i 个栈( i =1,2)栈顶，栈1 的底在v1，栈2 的底在Vm，则栈满的条件是（）。 单选题 *A. top2-top1|=0B. top1+1=top2(正确答案)C. top1+top2=mD. top1=top23.若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn，若p1=n，则pi为（）。 单选题 *A. iB. n=

2、iC. n-i+1(正确答案)D. 不确定4.栈结构通常采用的两种存储结构是（）。 单选题 *A. 顺序存储结构和链式存储结构(正确答案)B. 散列方式和索引方式C. 链表存储结构和数组D. 线性存储结构和非线性存储结构5.判定一个栈ST(最多元素为m0)为空的条件是（）。 单选题 *A. ST.top != -1B. ST.top = = -1(正确答案)C. ST.top != m0-1D. ST.top = = m0-16.判定一个栈ST(最多元素为m0)为栈满的条件是（）。 单选题 *A. ST.top != -1B. ST.top = = -1C. ST.top != m0-1D.

3、ST.top = = m0-1(正确答案)7.栈的特点是（），队列的特点是（）。 *A. 先进先出(正确答案)B.先进后出(正确答案)8.一个队列的入列序列是1，2，3，4，则队列的输出序列是（）。 单选题 *A. 4，3，2，1B. 1，2，3，4(正确答案)C. 1，4，3，2D. 3，2，4，19.判定一个循环队列QU(最多元素为m0)为空的条件是（）。 单选题 *A. front= =rear(正确答案)B. front！=rearC. front= =(rear+1)%m0D. front！=(rear+1)%m010.判定一个循环队列QU(最多元素为m0)为满队列的条件是（）。 单

4、选题 *A. front= = rearB. front！= rearC. front= =(rear+1)%m0(正确答案)D. front！=(rear+1)%m011.循环队列用数组A0，m-1存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）。 单选题 *A. (rear-front+m)%m(正确答案)B. rear-front+1C. rear-front-1D. rear-front12.栈和队列的共同点是（）。 单选题 *A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点(正确答案)13.在一棵度为3的树中，

5、度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。 单选题 *A. 4B. 5C. 6(正确答案)D. 714.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。 单选题 *A. 15B. 16(正确答案)C. 17D. 4715.假定一棵三叉树的结点数为50，则它的最小高度为（）。 单选题 *A. 3B. 4C. 5(正确答案)D. 616.在一棵二叉树上第4层的结点数最多为（）。 单选题 *A. 2B. 4C. 6D. 8(正确答案)17.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R1.n，结点Ri若

6、有左孩子，其左孩子的编号为结点（）。 单选题 *A. R2i+1B. R2i(正确答案)C. Ri/2D. R2i-118.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 单选题 *A. 24B. 48C. 72D. 53(正确答案)19.线性结构是数据元素之间存在一种（）。 单选题 *A一对多关系B多对多关系C多对一关系D一对一关系(正确答案)20.数据结构中，与所使用的计算机无关的是数据的（）结构。 单选题 *A存储B物理C逻辑(正确答案)D物理和存储21.算法分析的目的是（）。 单选题 *A找出数据结构的合理性B分析算法的效率以求改进(正确答案)C研究

7、算法中的输入和输出的关系D分析算法的易懂性和文档性22.算法分析的两个主要方面是（）。 单选题 *A空间复杂性和时间复杂性(正确答案)B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性23.计算机算法指的是（）。 单选题 *A计算方法B排序方法C解决问题的有限运算序列(正确答案)D调度方法24.从逻辑上可以把数据结构分为（）。 单选题 *A线性结构和非线性结构(正确答案)B紧凑结构和非紧凑结构C动态结构和静态结构D内部结构和外部结构25.线性表是（）。 单选题 *A一个有限序列，可以为空(正确答案)B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空26.带头结点的单

8、链表L为空的判定条件是（）。 单选题 *Ahead=nullBhead .next=null(正确答案)Chead .next=LDhead!=null27.在表长为n的单链表中，算法时间复杂度为O(n)的操作为（）。 单选题 *A删除p结点的直接后继结点B在p结点之后插入一个结点C删除表中第一个结点D查找单链表中第i个结点(正确答案)28.在表长为n的顺序表中，算法时间复杂度为O(1)的操作为（）。 单选题 *A在第i个元素前插入一个元素B删除第i个元素C在表尾插入一个元素(正确答案)D查找其值与给定值相等的一个元素29.设单链表中指针p指向结点ai，若要删除ai结点，则需修改指针的操作为（

9、）。 单选题 *Ap=p.nextBp.next=p.next.next(正确答案)Cp=p.next.nextDnext=p单选题1.数据的物理结构包括_ 的表示和存储和 _的表示和存储。 填空题_(答案：顺序结构、链式结构)2.对于给定的n个元素,可以构造出的逻辑结构有（ ）,( )，( )，( )四种。 填空题_(答案：集合结构、线性结构、树形结构、图状结构)3.一个算法具有5个特性：( )、（ ）、（ ），有零个或多个输入、有一个或多个输出。 填空题_(答案：有穷性、确定性、可行性)4.抽象数据类型被形式地定义为（ ），其中D是（ ）的有限集合，S是D上的（ ）有限集合， P是对D的（

10、 ）集合。 填空题_(答案：D,S,P、数据元素、关系、基本操作)5.数据结构主要包括数据的（ ）、数据的（ ）和数据的（ ）这三个方面的内容。 填空题_(答案：逻辑结构、存储结构、操作)6.一个算法的效率可分为（ ）效率和（ ）效率。 填空题_(答案：时间、空间)7.线性表的两种存储结构分别为（ ）和（ ）。 填空题_(答案：顺序存储结构、链式存储结构)8.顺序表中，逻辑上相邻的元素，其物理位置（ ）相邻。在单链表中，逻辑上相邻的元素，其物理位置（ ）相邻。 填空题_(答案：不一定、一定)9.若经常需要对线性表进行插入和删除操作，则最好采用（ ）存储结构，若线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，则最好采用（ ）存储结构。 填空题_(答案：链式、顺序)10.在带头结点的非空单链表中，头结点的存储位置由 ( ) 指示，首元素结点的存储位置由 ( ) 指示，除首元素结点外，其它任一元素结点的存储位置由 () 指示。 填空题_(答案：数据域、指针域、指针域)