数据结构2011-2012-1半期考

《数据结构2011-2012-1半期考》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福建师范大学数学与计算机科学学院2011—2012学年第1学期半期考试卷考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿装订线专业：年级：课程名称:数据结构任课教师：试卷类别：开卷（）闭卷（√）考试用时：分钟考试时间:年月日午点分题号一二三四五总得分评卷人得分题号六七八九十得分福建师范大学试卷纸第5页共6页一、选择：(每题2分，共20分)1、已知二叉树的前、中根序列分别是abdefcg和defbagc，则该二叉树的后

2、根遍历序列是()。A.defbgcaB.fedbgcaC.abcdefgD.gfedcba2、数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为()A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构3、一个栈的输入序列为12345，则下列序列中不可能是栈的输出序列的是（）。A.23415B.54132C.23145D.154324、在具有n个结点的单链表中,实现()的操作,其算法的时间复杂度是O(n).A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除

3、地址为p的结点的后继结点.5、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A.r－f;B.（n＋f－r）%n;C.n＋r－f;D.（n＋r－f）%n6、判定一个栈ST（最多元素为m0）为空的条件是()A．ST->top<>0B．ST->top==0C．ST->top<>m0D．ST->top==m07、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如图所示）按行序存放在一维数组B[1,n(n-1)/2]中，对下三角部分中任一

4、元素ai,j(i≤j),在一维数组B中下标k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j8、线性表Ｌ在________________情况下适用于使用链式结构实现。A.需经常修改Ｌ中的结点值B.需不断对Ｌ进行删除插入C.Ｌ中含有大量的结点D.Ｌ中结点结构复杂9、单链表的存储密度（）A.大于1；B.小于1；C.等于1；D.不能确定福建师范大学试卷纸第5页共6页考　　　　　　生　　　　　　信　　　　　　息　　　　　　栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿

5、＿专业＿＿＿＿＿＿年级　　　　姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线10、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：Ａ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF一、填空题：(每空1.5分，共30分)1、数据的存储结构可用四种基本的存储方法表示,分别是_顺序存储，

6、链式存储_索引存储与散列存储。2、在顺序表中插入或删除一个元素，需要平均移动_一半_元素，具体移动的元素个数_表长__与_插入或删除的位置_有关。3、链表相对于顺序表的优点有_插入_和_删除_操作方便。4、在n个结点的单链表中要删除已知结点*p,需找到_*p结点的直接前趋结点_,其时间复杂度为_O(n)_.5、设循环向量有m个元素，循环向量中有一个循环队列，在循环队列中设队头指针front指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。.在循环队列中，队空标志为_rear==front_队满标志为_(rear+

7、1)%m==front_.当rear>=front时，队列长度为_rear-front_；当rear

8、0、设数组a[1…60,1…70]的基地址为2000，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为（57*60+31）*2+2000=8902。福建师范大学试卷纸第5页共6页一、解答题：(每题5分，共30分)1、写出下列算法的语句频度和时间复杂度。x=0;for(i=1;i