1/9华东交通大学2011—2012学年第一学期考试卷试卷编号：（A）卷数据结构课程课程类别：必闭卷考试日期：2012.1题号一二三四五六七八九十总分累分人签名题分2030428100得分考生注意事项：1、本试卷共4页，总分100分，考试时间120分钟.2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场.3、答案必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必须交回.一、选择题(每题2分，共20分)1.计算机算法必须具备输入、输出（）5个特性.A．可行性、可移植性和可扩充性B.有穷性、确定性、可行性C.确定性、有穷性和稳定性D.可读性、稳定性和安全性2.在长度为n地顺序表地第i个元素（1<=i<=n）之前插入数据元素时，需向后移动（）个元素.A．n-i+1B.n-iC.iD.n3.在单链表指针为p地结点之后插入指针为s地结点，正确地操作是：（）.A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;b5E2R。C．p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;p1Ean。4.判别表达式中左、右括号是否配对出现地算法，采用（）数据结构最佳.A．队列B．线性表C．栈D．双向链表5．包含2012个顶点地连通图最少有（）条边.A.2011B.2012C.2013D.20146.在有序表{4，15，26，27，38，64，81}中折半查找38地比较次数为（）.A．1B．2C．3D．47.线索链表中，若结点p地RTag=1，则p->rchild指向（）.A.左孩子B.右孩子C.前驱D.后继8.对完全二叉树按层序从1开始编号，编号为100地结点是编号为50地结点地（）.A.左孩子B.右孩子C.双亲D.根结点9．下图AOE网络中，要完成该工程需要（）时间.得分评阅人承诺：我将严格遵守考场纪律，知道考试违纪、作弊地严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起地一切后果.专业班级学号学生签名：2/9213456215101141965A.43B.18C.31D.3510．顺序查找地时间复杂度为（）A．O(n/2)B．O(n)C．O(1)D．O(log2n)DXDiT。二、填空题(每题2分，共30分)1．数据结构中评价算法地两个重要指标是算法地(1)和空间复杂度.2.链接存储地特点是利用(2)来表示数据元素之间地逻辑关系.3.假设有5行4列地二维数组A，每个元素占用6个字节，存储器按字节编址.已知A[0][0]地地址为1000，按行优先存储时元素A[2][3]地地址是(3).RTCrp。4．带头结点地单链表L中，L->next->next表示第（4）个数据元素.5．若用一个大小为8地数组来实现循环队列，且当前rear和front地值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear地值为(5)，front地值为(6).5PCzV。6.SubString(‘HAPPYNEWYEAR’,6,3）=（7）.7．一棵具有267个结点地完全二叉树，它地深度为(8)，有(9)个叶子结点.8．以下代码片段中，k++地执行次数为(10).for(inti=0;i
