数据结构期末复习试卷a

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

1、装订线《数据结构》复习卷A题号一二三四五总分得分得分评卷人一．选择题(1*15=15分)1．数据结构是………………………………………………………………（D）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．计算机算法必须具备输入、输出和5个特性。（B）A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性3．下面程序段的时间复杂度为………..………………..………………..(B)y

2、=0;for(i=1;i<=n*n;i++)y++;A．O(n)B．O(n2)C．O(sqrt(n))D．O(1)4．线性表Ｌ在情况下适用于使用顺序存储结构实现。（）Ａ.需经常修改Ｌ中的结点值Ｂ.需不断对Ｌ进行删除、插入Ｃ.需要经常查询Ｌ中的结点Ｄ.Ｌ中结点结构复杂5．一个线性表第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是……..………………..………………....…………………..(A)A.110B.108C.100D.120第7页共8页6．设数组data[m]作为循环队列S

3、Q的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为………………………（D）  A．front=front+1        B．front=(front+1)%(m-1)  C．front=(front-1)%m    D．front=(front+1)%m7．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为……………………………………………………………（B）A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5

4、，3，4，6D．5，6，4，2，3，18．线性表若采用链式存储结构时，内存中可用存储空间的地址…….….（D）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以9．一棵二叉树有5个叶子,则度为2的结点个数为……………..……..…(B)A．4       B．3       C．6         D．710．一棵深度为6层的二叉树，其结点总数最多不会超过：………..……..…(D)A．7个B．36个C．72个D．63个11．设有两个串p和q，求q在p中首次出现的位置的运算

5、称作…………（B）Ａ．连接B．子串定位操作C．求子串D．求串长12．串是一种特殊的线性表，其特殊性体现在：………………………(D)A．可以顺序存储B．串中的每个数据元素仅由一个字符组成C．可以链式存储D．数据元素可以是多个字符13．已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()A．DEBAFCB．DEFBCAC．DEBCFAD．DEBFCA第7页共8页14．在链队列中每删除一个元素，需要………………………………..…（D）装订线A．修改队头指针B．既不修改队头指针也不修改队

6、尾指针C．修改队尾指针D．同时修改队头指针和队尾指针15．哈夫曼树的特点是……………………………………………………（C）A．分支路径数量最少B．分支总长度最短C．叶子结点带权路径长度之和最小D．叶子结点权值最小得分评卷人二．填空题(1*20=20分)1．数据存储结构分为线性存储和链式存储。2．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_p->rear__。3．栈顶的位置是随着___操作而变化的。4．深度为K的二叉树，结点最多有个，最少有个。5．

7、在串S=“factory”中，以t为首字符的子串有个。6．线性结构包括__________、___________、__________、数组、串。7.有循环队列q，头指针为fornt，尾指针为rear，队列长度为MAXSIZE，则循环队列的队空条件为：___________________________________；循环队列的队满条件为：___________________________________________。8．串的存储方式主要分为二种：__________存储结构和______

8、______存储结构。9．对于一棵完全二叉树按层次从左到右编号之后，结点i的左孩子编号为_________，右孩子编号为__________，其父结点的编号为__________。10．遍历二叉树通常有三种顺序，分别为_____________，_____________和_____________。第7页共8页得分评卷人三．程序填空题(2*10=20分)1．以下函数功能是：顺序表中在指定位置上插入一个元素，请填空。intinsert(SE