淮海工学院数据结构期末试卷及答案(2).doc

淮 海 工 学 院06 - 07 学年 第2学期 数据结构试卷A( 闭卷)题号一二三四五六七八九总 分得分一、选择题（本大题共20小题，每题1分，共20分；答案填在下表内）12345678910111213141516171819201算法分析的目的是( C )。A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性2（ B ）是具有相同特性数据元素的集合，是数据的子集。 A.数据符号 B.数据对象 C.数据 D.数据结构3用链表表示线性表的优点是 ( C )。A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同4输入序列为（A,B,C,D）不可能的输出有（D）。 A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)5在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B)。A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front6设有串t=I am a good student ，那么Substr(t,6,6)=（ D ）。A. student B. a good s C. good D. a good7设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（B ）。 A.23 B.33 C.18 D. 408已知广义表LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（C）。 A. Gethead(Gethead(LS) B. Gettail(Gethead(LS) C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS)9若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为(A) 。A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10下列存储形式中，( C ) 不是树的存储形式。A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法11对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( C)。A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序12采用折半查找方法进行查找，数据文件应为（ A），且限于（A ）。A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构13就平均查找速度而言，下列几种查找速度从慢至快的关系是（B ）A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半14执行下面程序段时，执行S语句的次数为（D ）for(int I=1;I=n;I+) for(int j=1;j0 ) p=stacktop; top-; printf(“%d”,p-data); if(p-rchild!=NULL) top+ ; stacktop=p-rchild; if( p-lchild!=NULL ) top+; stacktop=p-lchild ;3.请在标号处填写合适的语句。完成下列程序。(每空1分，共5分)int Binary_Search(S_TBL tbl，KEY kx) /* 在表tbl中查找关键码为kx的数据元素，若找到返回该元素在表中的位置，否则，返回0 */ int mid，flag=0；low=1；high=length； while( low=high &!flag ) /* 非空，进行比较测试 */mid= (low+high)/2； if(kxtbl.elemmid.key) low=mid+1 ； else flag= 1 ；break； return flag;4.下面是一个采用直接选择排序方法进行升序排序的函数，请在标号处填写合适的语句。(每空1分，共5分)程序：Void seletesort(int An,int n) int i,j,t,minval,minidx; for(i=1;i=n-1;i+) minval=Ai+1; minidx=i+1for(j=i+2;jAj) minval=Aj; minidx=j; if(i!=j) t=Ai+1; Ai+1=Aminidx Aminidx=t; 5 试写出求有向无环图的关键路径算法的设计思路（1