《数据结构09级信本期中试卷.2011.5.5》由会员分享，可在线阅读，更多相关《数据结构09级信本期中试卷.2011.5.5（13页珍藏版）》请在金锄头文库上搜索。
1、密封线河北北方学院-第二学期期中考试试卷专业_ 班级_ 姓名_ 学号_数据构造（供 医学信息本科 专业使用)注意事项: .请按规定在试卷的密封区填写专业、班级、姓名和学号。 2.请仔细阅读多种题目的答题规定，在规定的位置填写答案。3.不要在试卷上乱写乱画，不要在密封区填写无关的内容。题号一二三四五总分得分 总分合计人: 复核人： 得分评卷人一、填空(共20分，每空1分。)1宏观地讲，数据构造是一门研究非数值性程序设计中计算机操作的_的学科。2 下面程序段的时间复杂度为_。 fr （it i0；m；+) fr(nt =;jNx=New；NewNext =pext；则会产生的问题是_。8对于数组仿
2、真的堆栈，若事先分派的存储空间为asiz=axtop1,表示指针的向量为top,则pus操作中产生上溢的指针状况_,如此也许产生的状况是_。若以ep做为暂存出栈元素的变量，请描述o操作的重要环节：_。 使用环状队列解决空间运用问题,若以数组描述队列，事先分派的存储空间长度为Mxsiz，则环状队列的有效运用空间为_;队首（或队尾）指针的前移方式为：_ _。10. 函数调用过程中，调用函数和被调函数之间的链接和信息互换需要通过_来进行。当有多种函数构成嵌套调用时,遵循_ _ _原则。1.一般树形构造与二叉树的二叉链表的表达法中,唯一不同就是其右指针指向的是_ _。2. 当以二叉链表作为树或森林的存
3、储构造时,可以使用二叉树的 两种方式遍历一棵树或森林。3 中序线索满二叉树中非终端结点的直接前驱是_ _ _。得分评卷人二、选择题(共10分,每题1分。） 1. 循环单链表不具有的特点是【 】.具有随机访问特性 B插入删除不需要移动元素不必事先估计存储空间 .循环单链表可由头点或尾结点拟定. 堆栈和队列都是【 】.顺序存储的线性构造 B链式存储的顺序构造限制存取点的线性构造 D.限制存取点的非线性构造3设三个函数f、g、，函数式分别为：f(n）=103n2+0 g(n)=25n3500n2 h（）n1.5000nlgn。下列关系中不成立的是【 】A. ()=O（g(n) . g(n)O（f(n
4、)C.h(n)=O（n.5） D. h(n）=O(nlgn)4. 一般不属于队列应用范畴的是 【 】A优先队列 B操作系统中的工作调度 C解决子函数的调用 D.用于打印缓冲“spln”.在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加【 】A2 B. C D 6 在一种单链表中,若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行【 】A sln = plink； ink=s; pink = s; slnk=q；C. pin =slin； slnk = p; D. slink p ；qlnk = s；7. 对于树的特性，描述有误的是【 】A树是层次构造 B树结点具有唯一的前趋与后
5、继C.递归是树固有的特性 .N元树的分支度即为N8 有关如下声明,下列那个语句的指定是对的的？【 】cha *1=”helo！”;cr *s2=”exclln”;chr*sing;car 120；As=2; B.s2=stig； Cstring=s1; D.s120*s2;9. 对于顺序存储的队列，存储空间大小为，头指针为F,尾指针为。若在逻辑上看一种环,则队列中元素的个数为【 】A. R-F B. n- C. （-+1） mod D. (+RF) mon10.设有一种的对称矩阵A，将其上三角部分按行寄存在一种一维数组中，A00寄存于中,那么第i行的对角元素A寄存于中（ ）处。A. (+3)*
6、i2 . （i+1)*i/2 C (ni+1)*i2 D.(2-i-1)*i/ 得分评卷人三、判断题(共10分，每题1分。)1、在数组构造中,可根据给出的索引值,找到该数组的内容值，因此说数组中的数据具有随机存取性。.()2、线性表的逻辑顺序与物理顺序一致。.（ ）3、基于链栈的元素序列，插入与删除运算只能在序列首进行。.（ )4、对具有个结点、树高为h的二叉树实行前、中、后序遍历，空间复杂度均为O（h）。.( )5、C语言中，字符串在函数间是以传址调用的方式进行传递的,形参就是字符串的名称。.( ）6、具有n个结点的完全二叉树的深度为不不小于log2的整数。.( )7、在程序运营过程中可以扩
7、大的数组是动态分派的构造数组。这种数组在声明它时需要使用数组指针。.（ )8、线性的数据构造可以顺序存储,也可以链接存储。非线性的数据构造只能链接存储。.（ )9、一般递归的算法简朴、易懂、容易编写,并且执行的效率也高。.（ )0、对于树进行后序遍历的成果等于对其相应的二叉树中序遍历的成果；树的先序遍历成果等于对其相应二叉树先序遍历的成果。.( )得分评卷人四、综合题(共35分。每题占分在题后标注。)1、 有一稀疏矩阵如右下表所示。请描述其存储方式。(7分）1235780030200001040750000000000000400900000000002、 设有一种长整型的二维数组共有7行8列
8、,在内存中的起始地址为0。祈求出以列为主序进行数据存储时，第5行第6列的元素的内存地址。（5分)3、 既有一种班级40个同窗的姓名、性别、年龄和住址, 请将学生资料定义成一种构造数组。并列出对构造数构成员的访问形式（列出一二项即可）。(5分)4、请将前序体现式“*+*BCDEG”转换为中序、后序体现式。（4分）、设有广义表F（A(a,(，c,) ，() ，请描述其存储构造,并会出其链式存储构造逻辑图。（分)、有一二叉树如下,请分别写出对其前序、中序、后序遍历的顺序。（6分)+ * a f / e b c d得分评卷人五、算法及分析题(共2分。每题占分在题后标注。)1、已知二叉查找树中的结点类型
9、_TreNde定义为: structB_eNd nt at； B_TrNode*et, *rgh；;其中data为结点值域,lt和right分别为指向左、右子结点的指针域。参数t指向一棵二叉查找树,该树的广义表表达为:(25(10(5,1（12),4(32（,38)。根据下面算法按标号把答案填写到算法背面相应标号的位置。(每空分,本题合计6分) ntLN(B_eNoe* t， it ) if(t=NULL) retur 0; lse if(-data=X) rtur 1;ele if(t-dat)tn 1+LN(-eft,X);lsereturn +N(-right,X);执行LN（t,40)调用后返回的值为_。 执行N(t,38)调用后返回的值为_。 执行L(pt,5)调用后返回的值为_ 。2、试写出使用链表构造描述“输入限
