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

………密…………………封………线………密…………………封………线……………专业专业________班级________姓名__________学号________《数据结构》（供医学信息本科专业使用）注意事项：1．请按要求在试卷的密封区填写专业、班级、姓名和学号。2．请仔细阅读各种题目的答题要求，在规定的位置填写答案。3．不要在试卷上乱写乱画，不要在密封区填写无关的内容。题号一二三四五总分得分总分合计人：复核人：得分评卷人一、填空（共20分，每空1分。）1.宏观地讲，数据结构是一门研究非数值性程序设计中计算机操作的________________________的学科。2.下面程序段的时间复杂度为________。for(inti=0;i<m;i++)for(intj=0;j<n;j++)a[i][j]=i*j;3.我们以程序语句的__________即_______作为时间量度，来做为程序效率分析的标准。4.设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s3,s2,s5,s6,s4,s1，则顺序栈的层数至少为_______。5.一个链队列中，若front指针等于NULL通常为_____，rear指针等于NULL通常为_____。6.n维数组是一个同构的数据结构，即它的每一个数据元素均属于_______________或。7.若将结点New插入单链表中，*p指向欲插入结点，将New插入其后端,语句如下：p->Next=New；New->Next=p->Next；则会产生的问题是____________。8.对于数组仿真的堆栈，若事先分配的存储空间为Maxsize=Maxtop+1，表示指针的向量为top，则push操作中产生上溢的指针情况________________，如此可能产生的情况是___________。若以temp做为暂存出栈元素的变量，请描述pop操作的主要步骤：________________________________________。9.使用环状队列解决空间利用问题，若以数组描述队列，事先分配的存储空间长度为Maxsize，则环状队列的有效利用空间为___________；队首（或队尾）指针的前移方式为：____________________________。10.函数调用过程中，调用函数和被调函数之间的链接和信息交换需要通过_____来进行。当有多个函数构成嵌套调用时，遵循____________原则。11.普通树形结构与二叉树的二叉链表的表示法中，唯一不同就是其右指针指向的是_______________。12.当以二叉链表作为树或森林的存储结构时，可以使用二叉树的两种方式遍历一棵树或森林。13.中序线索满二叉树中非终端结点的直接前驱是___________________。得分评卷人二、选择题（共10分，每题1分。）1.循环单链表不具有的特点是【】A．具备随机访问特性B．插入删除不需要移动元素C．不必事先估计存储空间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．用于打印缓冲“spooling”5.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加【】A．2B．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.有关如下声明，下列那个语句的指定是正确的？【】char*s1=”hello!”;char*s2=”excellent”;char*string;chars1[20];A．s1=s2;B．s2=string;C．string=s1;D．s1[20]=*s2;9.对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为【】A.R-F

B.n+R-F

C.(R-F+1)modn

D.(n+R-F)modn10.设有一个nn的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A[i][i]存放于B中（）处。A.(i+3)*i/2 B.(i+1)*i/2 C.(2n-i+1)*i/2 D.(2n-i-1)*i/2得分评卷人三、判断题（共10分，每题1分。）1、在数组结构中，可根据给出的索引值，找到该数组的内容值，因此说数组中的数据具备随机存取性。........................................（）2、线性表的逻辑顺序与物理顺序一致。...........................（）3、基于链栈的元素序列，插入与删除运算只能在序列首进行。.......（）4、对含有n个结点、树高为h的二叉树实施前、中、后序遍历，空间复杂度均为O(h)。.......................................................（）5、C语言中，字符串在函数间是以传址调用的方式进行传递的，形参就是字符串的名称。....................................................（）6、具有n个结点的完全二叉树的深度为不大于log2n的整数。.......（）7、在程序运行过程中可以扩充的数组是动态分配的结构数组。这种数组在声明它时需要使用数组指针。........................................（）8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。......................................................（）9、通常递归的算法简单、易懂、容易编写，而且执行的效率也高。...（）10、对于树进行后序遍历的结果等于对其相应的二叉树中序遍历的结果；树的先序遍历结果等于对其相应二叉树先序遍历的结果。....（）得分评卷人四、综合题（共35分。每题占分在题后标注。）有一稀疏矩阵如右下表所示。请描述其存储方式。（7分）012345678000302000011004000702050006000300000000040009000805000000000设有一个长整型的二维数组共有7行8列，在内存中的起始地址为100。请求出以列为主序进行数据存储时，第5行第6列的元素的内存地址。（5分）现有一个班级40个同学的姓名、性别、年龄和住址,请将学生资料定义成一个结构数组。并列出对结构数组成员的访问形式（列出一二项即可）。（5分）4、请将前序表达式“*/+A*BCD－E/FG”转换为中序、后序表达式。（4分）5、设有广义表F(A(a,(b,c,d)),B(e))，请描述其存储结构，并会出其链式存储结构逻辑图。（8分）6、有一二叉树如下，请分别写出对其前序、中序、后序遍历的顺序。（6分）+－+－－－－*－－a－－f－－/－－e－－b－－－－－c－－d－－得分评卷人五、算法及分析题（共25分。每题占分在题后标注。）1、已知二叉查找树中的结点类型B_TreeNode定义为:structB_TreeNode{intdata;B_TreeNode*left,*right;};其中data为结点值域，left和right分别为指向左、右子结点的指针域。参数t指向一棵二叉查找树，该树的广义表表示为:(25(10(5,16(12)),40(32(,38))))。根据下面算法按标号把答案填写到算法后面相应标号的位置。（每空2分，本题共计6分）intLN(B_TreeNode*t,intX) {if(t==NULL)return0; elseif(t->data==X)return1; elseif(t->data>X) return1+LN(t->left,X); else return1+LN(t->right,X); }执行LN(pt,40)调用后返回的值为__________。执行LN(pt,38)调用后返回的值为__________。执行LN(pt,5)调用后返回的值为_________。2、试写出使用链表结构描述“输入限制性双端队列”的算法。（本题1