东华理工大学2015 —2016学年第 一学期考试试卷 A 《答案》一、填空题（ 50 分）1、数据结构是一门研究非数值计算的程序设计问题中的数据元素以及它们之间关系和运算等的科学。 （2 分）2、数据结构的类型通常分为：集合、线性结构、树形结构、图状结构或网状结构；从逻辑上可以把它们分成：线性结构和非线性结构。3、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。4、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂度和时间复杂度。5、计算机算法是解决问题的有限运算序列，它必须具备输入、输出、确定性、有穷性和稳定性等 5 个方面的特性。6、线性结构中元素之间的关系存在一对一关系，树形结构中元素之间的关系存在一对多关系，图形结构中元素之间的关系存在多对多关系。7、试写出以下算法的时间复杂度i=s=0 while (s | ai-1 , ai D, i=2,⋯,n}基本操作：InitList(&L) //构造一个空的线性表L DestroyList(&L) //消毁线性表L ListLength(L) //返回 L 中数据元素的个数ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在 L 中第 i 个位置之前插入数据元素 e,L 长度加 1 ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除 L 中的第 i 个元素，并用e返回ListTraverse(L,visit()) //依次对 L 的每个元素调用函数visit() ⋯⋯⋯⋯} ADT List 10、指出线性表顺序存储、链式存储结构的优缺点。答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻， 不能随机存取表中元素，需要依次查找， 求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。11、完成下列在单链表中删除元素算法Status ListDelete_L(LinkList &L,...
