搜索
福建师范大学试卷纸第1页共4页福建师范大学数学与计算机科学学院2010—2011学年第1学期半期考试卷考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿装订线专业：计算机科学与技术年级：09课程名称:数据结构任课教师：严宣辉试卷类别：开卷（）闭卷（√）考试用时：100分钟考试时间:年月日午点分题号一二三四五总得分评卷人得分题号六七八九十得分福建师范大学试卷纸第2页共4页一、选择：(每题2分，共20分)1、数据结构通常是研究数据的()及它们之间的相互关系.A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑2、数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为()A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构3、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154324、在具有n个结点的单链表中,实现()的操作,其算法的时间复杂度是O(n)。A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除地址为p的结点的后继结点.5、数组Ｑ[ｎ]用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为()。A.r－f;B.（n＋f－r）%n;C.n＋r－f;D.（n＋r－f）%n6、线性表Ｌ在什么情况下适用于使用链式结构实现。（）A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂7、设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（）A.p-RLink=s;s-LLink=p;p-RLink-LLink=s;s-RLink=p-RLink;B.p-RLink=s;p-RLink-LLink=s;s-LLink=p;s-RLink=p-RLink;C.s-LLink=p;s-RLink=p-RLink;p-RLink=s;p-RLink-LLink=s;D.s-LLink=p;s-RLink=p-RLink;p-RLink-LLink=s;p-RLink=s;8、一棵含有n个节点的k叉树，可能的最小深度为多少？（）A.n-kB.n-k+1C.|logkn|+1D.|logkn|其中|k|表示下取整9、单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（）。A.O(n)B.O(1)C.O(n*n)D.O(n*logn)10、在具有n个结点的二叉链表共中，共有（）个空指针。A.n.Bn-1C.n+1D.不确定福建师范大学试卷纸第3页共4页考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线二、填空题：(每空1.5分，共30分)1、数据的存储结构可用四种基本的存储方法表示,分别是_______、________、“索引”和“散列”。2、在顺序表中插入或删除一个元素，需要平均移动__________元素，具体移动的元素个数与____________有关。3、链表相对于顺序表的优点有_____________和_______________操作方便。4、在n个结点的单链表中要删除已知结点*p,需找到_____________,其时间复杂度为_____________________.5、一个顺序循环队列有m个元素，在循环队列中设队头指针front指向队头元素，队尾指针rear指向队尾元素后的一个空闲元素。在循环队列中，队空标志为____________________队满标志为________________。当rear=front时，队列长度为_____________________；当rearfront时，队列长度是_______________。6、对于完全二叉树中的任一结点，若其右下分支子孙的最大层次为h，则其左分支下的子孙的最大层次可能为__________________。7、有如下递归过程：voidreverse(intn){printf(“%d”,n%10);if(n/10!=0)reverse(n/10);}调用语句reverse(582)的结果是。8、线索二叉树中某结点S没有左孩子的充要条件是_______________。9、带头结点的单链表head为空的判定条件是_______________。10、一棵树的结点数为n，其分支（边）的数量为_________。11、设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f依次进入栈S，若每个元素出栈后立即进入队列Q，且6个元素出队的顺序是b,d,c,f,e,a，则栈S的容量至少是________。12、在有n个叶子结点的哈夫曼树中，总结点数是_______。13、在双链表中，在指针P所指结点前面插入一个结点S时的语句序列是：S-next=P;S-prior=P-prior;P-prior=S;_______________。福建师范大学试卷纸第4页共4页三、解答题：(共30分)1、（4分）写出下列算法的语句频度和时间复杂度。x=0;for(i=1;in;i++)for(j=i+1;j=n;j++)x++;2、（5分）现有前序遍历二叉树的结果为ABC，画出可以得到这一结果的所有二叉树。3、(6分）铁路进行列车调度时,常把站台设计成栈式结构的站台，如右图所示，设有编号为1,2,3,4,5,6的六辆列车,顺序开入栈式结构的站台。试问：是否能够得到435612,325641,154623和135426的出站序列,如果不能,说明为什么不能;如果能,说明如何得到(即写出进栈或出栈的序列)。4、（6分）将给定的一组权值：15、22、14、6、7、5、7，构造成一棵哈夫曼树，并计算出它的带树路径长度。5、（9分）设某二叉树的前序遍历序列为：ABCDEFGHI，中序遍历序列为：BCAEDGHFI。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。四、算法题：(每题10分，共20分)1、设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针,试设计一个算法,将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间,不另外占用其它的存储空间。表中允许有重复的数据。2、设二叉树以二叉链表的形式存储，试设计算法，返回二叉树中度为1的结点的个数。