数据结构期末复习试卷B.doc

《数据结构期末复习试卷B.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、装订线《数据结构》复习卷B题号一二三四总分得分得分评卷人一．选择题(1*15=15分)1．算法指的是……..……………………………..…………………..……………（）  A．计算机程序      B．解决问题的计算方法  C．排序算法        D．解决问题的有限运算序列2．某程序的时间复杂度为（3n+n2+8）,其数量级表示为.…….……（）A．O（3n）B．O（n）C．O（n2）D．13．线性表采用链式存储时，结点的存储地址………………………….…………（）  A．必须是不连续的  B．连续与否均可  C．必须是连续的  D．和头结点

2、的存储地址相连续4．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为…………………………（）  A．front=front+1        B．front=(front+1)%(m-1)  C．front=(front-1)%m    D．front=(front+1)%m5．若已知一个栈的入栈序列是12345，不可能有下列那个出栈序列（）A．12345B．13425C．34521D．142356．一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第

3、5个元素的地址是………………………………………………………………（）第7页共7页A.110B.108C.100D.1207．一棵二叉树有8个叶子,则度为2的结点个数为……………..……..…()A．8      B．2C．9         D．78．一棵深度为5层的二叉树，其结点总数最多不会超过：………..……..…()A．31个B．36个C．72个D．63个9．串是一种特殊的线性表，其特殊性体现在：………………………()A．可以顺序存储B．串中的每个数据元素仅由一个字符组成C．可以链式存储D．数据元素可以是多个字符10．下面程序段的时间复

4、杂度为………..………………..……………..()y=0;For(i=1;i<=n;i++)y++;A．O(n)B．O(n2)C．O(sqrt(n))D．O(1)11．设有两个串p和q，求q在p中首次出现的位置的运算称作…………（）Ａ．连接B．子串定位操作C．求子串D．求串长12．已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（）A．DEBAFCB．DEFBCAC．DEBCFAD．DEBFCA13．按照二叉树的定义,具有3个结点的二叉树的状态数为……………….……（）A.5B.4C.3 D.214．将长度为n的单链表

5、链接在长度为m的单链表之后的的时间复杂度为……（）第7页共7页  A．O（1）        B．O（n）    C．O（m）    D．O（m+n）装订线15．在线性表的下列运算中，不改变数据元素之间结构关系的运算是…..……（）A．插入B．删除C．排序D．定位得分评卷人二．填空题(1*20=20分)1．所有能输入到计算机中并被计算机程序处理的符号总称，被称为___________。在计算机程序中通常作为一个整体进行考虑和处理的，通常被称为_____________。不可分割的、含有独立意义的数据的最小单位，被称为_____________

6、。2．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=___。3．线性结构包括__________、___________、__________、数组、串。4．判定顺序表a为空的条件是：__________________________________。5．顺序存储结构的队列称为_________________，链式存储结构的队列称为________________。6．串的存储方式主要分为二种：_____________存储结构和_______________存储结构。7．若二叉树有

7、m个叶结点，则度为2的结点有个。8．树中结点的最大层次称为树的_____________。树中除根结点以外，每个结点都有_____________个前驱和0到多个后继。9．对于一棵完全二叉树按层次从左到右编号之后，结点i的左孩子编号为_________，右孩子编号为__________，其父结点的编号为__________。10．深度为K的二叉树，结点最多有个，最少有个。第7页共7页得分评卷人三．综合运用题(5*5=25分)1．写出按先根序列遍历下面二叉树的结果：CBAIHFDKJGE2．4．把下列森林转换为对应的二叉树。3.已知一棵二叉树的

8、后序扫描序列和中序扫描序列分别为DECBHGFA和BDCEAFHG，试画出该二叉树。ABCDEFGHLIJK4．画出下面树的孩子兄弟表示法。第7页共7页装订线CBA