数据结构09级信本期中试卷.2011.5.5

《数据结构09级信本期中试卷.2011.5.5》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、………………………………………密…………………………………封………………………………………线……………………………………………河北北方学院2010-2011学年第二学期期中考试试卷专业________班级________姓名__________学号________《数据结构》（供医学信息本科专业使用）注意事项：1．请按要求在试卷的密封区填写专业、班级、姓名和学号。2．请仔细阅读各种题目的答题要求，在规定的位置填写答案。3．不要在试卷上乱写乱画，不要在密封区填写无关的内容。题号一二三四五总分得分总分合计人：复核人：得分评卷人一、填空（共

2、20分，每空1分。）1.宏观地讲，数据结构是一门研究非数值性程序设计中计算机操作的________________________的学科。2.下面程序段的时间复杂度为________。for(inti=0;i

3、，则顺序栈的层数至少为_______。5.一个链队列中，若front指针等于NULL通常为_____，rear指针等于NULL通常为_____。6.n维数组是一个同构的数据结构，即它的每一个数据元素均属于_______________或。7.若将结点New插入单链表中，*p指向欲插入结点，将New插入其后端,语句如下：p->Next=New；New->Next=p->Next；则会产生的问题是____________。8.对于数组仿真的堆栈，若事先分配的存储空间为Maxsize=Maxtop+1，表示指针的向量为top，则pus

4、h操作中产生上溢的指针情况________________，如此可能产生的情况是___________。若以temp做为暂存出栈元素的变量，请描述pop操作的主要步骤：________________________________________。9.使用环状队列解决空间利用问题，若以数组描述队列，事先分配的存储空间长度为Maxsize，则环状队列的有效利用空间为___________；队首（或队尾）指针的前移方式为：____________________________。10.函数调用过程中，调用函数和被调函数之间的链接和信息交换需

5、要通过_____来进行。当有多个函数构成嵌套调用时，遵循____________原则。11.普通树形结构与二叉树的二叉链表的表示法中，唯一不同就是其右指针指向的是_______________。12.当以二叉链表作为树或森林的存储结构时，可以使用二叉树的两种方式遍历一棵树或森林。13.中序线索满二叉树中非终端结点的直接前驱是___________________。得分评卷人二、选择题（共10分，每题1分。）本试卷共9页第9页本试卷共9页第9页1.循环单链表不具有的特点是【】A．具备随机访问特性B．插入删除不需要移动元素C．不必事先估计存储

6、空间D．循环单链表可由头点或尾结点确定2.堆栈和队列都是【】A．顺序存储的线性结构B．链式存储的顺序结构C．限制存取点的线性结构D．限制存取点的非线性结构3.设三个函数f、g、h，函数式分别为：f(n)＝100n3＋n2＋1000g(n)＝25n3＋5000n2h(n)＝n1.5＋5000nlgn。下列关系中不成立的是【】A.f(n)＝O(g(n))B．g(n)＝O(f(n))C．h(n)＝O(n1.5)D．h(n)＝O(nlgn)4.通常不属于队列应用范围的是【】A．优先队列B．操作系统中的工作调度C．处理子函数的调用D．用于打印缓冲“

7、spooling”5.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加【】A．2B．1C．0D．–16.在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行【】A．s→link=p→link;q→link=s;B．p→link=s;s→link=q;C．p→link=s→link;s→link=p;D．s→link=p；q→link=s;7.对于树的特性，描述有误的是【】A．树是层次结构　　　　　B．树结点具备唯一的前趋与后继C．递归是树固有的特性D．N元树的分支度即为N8.有关如下声明，下列那个语句的指定是

8、正确的？【】char*s1=”hello!”;char*s2=”excellent”;char*string;chars1[20];本试卷共9页第9页A．s1=s2;B．s2=string;C