厦门理工学院数据结构期末考试试题.doc

《厦门理工学院数据结构期末考试试题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、考生信息栏系专业级班级姓名学号装订线厦门理工学院试卷20－20学年第学期课程名称数据结构与算法试卷卷别A√B□专业级班级考试方式闭卷□开卷□本试卷共6大题(6页)，满分100分，考试时间120分钟。请在答题纸上作答，在试卷上作答无效。一、判断题：（本题共10小题，每题1分，共10分）1、线性表的逻辑顺序与存储顺序总是一致的。（）2、线性表的链式存储结构是一种随机存取的存储结构。（）3、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索。（）4、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。（）5、任何一棵二叉树的叶结点在先

2、序、中序和后序遍历序列中的相对次序是不一样的。（）6、在一个图中，所有顶点的度数之和等于所有边数的2倍。（）7、数据元素是数据的最小单位。（）8、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）9、从长度为n的顺序表中删除一个元素，所需要的时间都是O（n）。（）10、凡是空的单链表都是不含任何结点的。（）二、填空题：（本题共10小题，，每空1分，共15分）1、数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。2、计算机算法指的是，它必具备输入、输出和等五个特性。第6页共6页3、若已知一个栈的入栈序列是1，2，3

3、，4，。。。。。。，n，其输出序列为p1,p2,p3,……,pn，若p1=n，则pi为。4、在一棵二叉树中，度为0的结点的个数为n0，度为2的结点的个数为n2，则有n0=。5、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6、在分块查找方法中，首先查找，然后再查找相应的。7、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为。8、下面程序段的时间复杂度是。i=s=0;while(s

4、;i

5、）A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以4、在以下的叙述中，正确的是（）A、线性表的线性存储结构优于链表存储结构B、栈的操作方式是先进先出C、二维数组是其数据元素为线性表的线性表D、队列的操作方式是先进后出5、一个栈的入队序列是1,2,3,4,5，则栈的不可能的输出序列是（）；A、54321B、43512C、45321D、123456、链表不具有的特点是（）。A、可随机访问任一元素B、插入删除不需要移动元素C、不必事先估计存储空间D、所需空间与线性表长度成正比7、深度为6的二叉树至多有（）个结点。A、32

6、B、31C、63D、648、带头结点的单链表head为空的判定条件是（）；A、head==NULLB、head->next==NULLC、head->next==headD、head!=NULL9、栈和队列的共同点是（）。A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10、某算法的时间复杂度为O（n2），表明该算法的（）。A、问题规模是n2B、执行时间等于n2C、执行时间与n2成正比D、问题规模与n2成正比第6页共6页11、若线性表最常用的运算是存取第i个元素及其前驱的值，则采用（）存储方式节省时间。A、单链表B、

7、双链表C、单循环链表D、顺序表。12、在一个单链表中，删除*p结点之后的一个结点的操作是（）。A、p->next=p;B、p->next->next=p->next;C、p->next->next=p;D、p->next=p->next->next;13、循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（1）A、（rear-front+m）%mB、rear-front+1C、rear-front-1D、rear-front14、在一非空二叉树的中序遍历序列中，根结点的左边（）。A、只有

8、右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分结点D、只有左子树上的所有结点15、对一个满二叉树，m个树叶，n个结点