数据结构期末考卷13-14

《数据结构期末考卷13-14》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、诚信应考考出水平考出风格浙江大学城市学院20132014学年第一学期期末考试试卷《数据结构基础开课单位：计箅分院；考试形式：闭卷；考试时间：2014年1月14日:所需时间：120分钟题序—•」二四五/、总分得分评卷人:得分一.选择题(本大题共18题，每题1分，共18分)參攀<1.数据的包括集合、线性结构、树形结构和图形结构叫种®本类型。A.存储结构B.逻辑结构C.基本运算D.算法描述2.屮任何两个结点之叫都没有逻辑关系。A.树形结构B.集合C.图形结构D.线性结构3.下側的程序段违反了算法的原则。voidfun(){intx=2;while(!(x%

2、2))x=x*2;printf(“％d”,x);}A.健壮性B.确定性C.可行性D.有穷性4.算法分析的两个主要方面是。A.空fid复杂性和时l'id复杂性B.正确性和简明性C.可读性和文档性D.数裾复杂性和程序复杂性第1页共1页1.用数组表示线性表的优点是。A.便于插入和删除操作B.便于随机存取C.讨以动态地分配存储空间D.不需要占用一片相邻的存储空闷2.循环链表的主要优点足。A.节约存储空间B.已知菜个结点的位置后，能够很容易找到它的直接前驱C.在进行插入、删除运算吋，能更好的保证链表不断开D.从表屮的任意结点出发都能访问到任何一个结点3.可以用

3、带表头附加结点的链表表示线性表，也可以用不带尖结点的链表表示线性表，前者鉍主要的好处是OA.可以加快对表的遍历B.节右存储空间C.使空表和非空表的处理统一D.可以提高存取表元素的速度4.在头指针为h且表长人于1的单循环链表屮，指针P指表屮的某个结点，若p->next->next==h,则。A.p指叫头结点B.p指向尾结点C.*p的直接f•继是头结点D.*^的百接后继是尾结点5.线性表中，只冇直接前驱而无后继的元素足。A.首元素B.尾元素C.中间元素D.全部元素6.以下不是栈的某本运算的是。A.删除栈顶元素B.删除栈底元素c.判断栈足否为空d.将栈a为

4、空栈7.若用一个大小为6的数组来实现循环队列,且当前rear和fornt的值分別为1和4。从当前队列中删除一个元素，再加入两个元素盾，rear和^front的值分别为。A.3和5B.2和0C.0和2D.5和38.敁不适合用作链队的链表是。A.只带队1•桁针的非循环双链农B.只带队头指针的循环双链表C.只带队尾指针的循环双链表D.只带队尾指针的循环单链表9.蛣不适合用作栈的链表是。A.只有表头指针没有表尾指针的循环双链表B.只有表尾指针没有表头指针的循环双链表C.只有表尾指针没有表失指针的循环单链表D.只有表头指针没柯表尾指针的循环单链表10.一个递归

5、的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率。A.高B.低C.相同D.无法确定1.设n和m为一棵二叉树上的两个结点，中序遍历时，n在m盾的条件是。A.n在m的右子树上B.n是m祖先C.n在m的左子树上D.n是m子孙2.已知一棵咎通树的广义表表示为a(b，c(e(h,i,j),f),d(g)),则此树的深度为A.2巳.3C.4D.53.G足一个非连通无向图，共有21条边，则该图至少有个顶点。A.7B.8C.9D.234.用邻接表存储图，所用的空间大小oA.与图的顶点数和边数都有关B.只与图的边数旮关

6、C.从与图的顶点数有关D.与边数的平方柯关得分二.填空题(本大题共10题，每题2分，共20分)1.数据结构主要研究三方而的内容：数裾的逻辑结构、。2.计算机算法指的是解决问题的有限运算序列，它必具备输入、输!H、有穷性和这五个特性。3.K列算法的吋间复杂度为。inttest(intn){ints=1;while(s<=n)s=s*2;returns;}4.在单链表中，指针p指向某中间结点，实现“删除p结点的后继结点”的语句是。5.向一个栈顶桁针为top的链式栈屮插入一个s所指的結点吋，则执行。6.在一个非空的链式队列中，假设f和r分别为队头和队尾指针

7、，则实现出队列运算并将删除结点元素值赋给x的语句是。7.栈s的初始状态为空，6个元素a，b，c，d，e，f依次入栈，若出栈的顺序是b，d，c，f,e，a,则栈s的容量至少应该是。8.已知二叉树的后序遍历是dabec:中序遍历是debac，则其前序遍历是。9.设森林「屮有三棵树，第一、第二和第三棵树的结点个数分别为m、n和p，则与森林F对应的二义树根结点的右子树上的结点个数是。10.对于稠密阁，适合使用存储结构。得分三.解答题(本大题共3题，每题6分，共18分)1.设栈S的初始状态为空，队列Q的初始状态如下图所示:a1a3a4T队头T队尾若对栈S和队列

8、Q进行以下两步操作：①对队列Q依次执行出队列操作，丼将出队列的元素依次入栈S,直到Q为空;②依次将栈S中的元