数据结构考试试题剖析.doc

东华理工大学2015 —2016学年第 一 学期考试试卷 A 《答案》  填空题（50分） 1、数据结构是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。（2分） 2、数据结构的类型通常分为： 集合、线性结构、树形结构、图状结构或网状结构 ；从逻辑上可以把它们分成： 线性结构和非线性结构 。 3、数据的 逻辑结构 只抽象反映数据元素的 逻辑关系 ；数据的 存储（物理）结构 是数据的逻辑结构 在计算机存储器中的实现 。 4、算法分析的目的是分析算法的 效率以求改进 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。 5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。 6、线性结构中元素之间的关系存在 一对一 关系，树形结构中元素之间的关系存在 一对多 关系，图形结构中元素之间的关系存在 多对多 关系。 7、试写出以下算法的时间复杂度 i=s=0 while (sn) { i++; s += i; } 7、试写出以下算法的时间复杂度 i = 1 while( i = n) i = i*2 O(log2n) 8、抽象数据类型的定义由三元组来定义：(D,S,P) 其中，D是 数据对象， S是D上的关系集，P是 对D的基本操作集。 9、写出抽象数据类型线性表的定义 ADT List{ 数据对象：D={ai | ai ( Elemset, i=1,2,…,n,n(0} 数据关系：R={ ai-1 , ai | 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, int i, ElemType e){ //删除第i个元素e p = L; j =0; //p指向头结点 while(p-next ji-1){ p = p-next; ++j } //寻找第i个结点,并令p指向其前驱 if(!(p-next) || ji-1) return ERROR; //删除位置不正确 q= p -next; p-next = q-next ; //删除与释放结点 e = q-data; free(q); return OK; } 12、在一个长度为n的线性链表中第i个元素（1(i(n）之前插入一个元素时，需向后移动 n-i+1 个元素。 13、在一个长度为n的线性链表中删除第i个元素（1(i(n）时，需向前移动 n-i 个元素。 14、在一个单链表中p所指结点之后插入一个 s所指结点时，应执行 s-next = p-next 和 p-next = s 的操作。 15、在单链表中，插入或删除一个结点元素时，仅需要修改 指针 而不需要移动 元素 。 16、栈(Stack)是限定仅在表尾进行插入和删除操作的线性表， 17、栈链式存储结构中删除栈顶元素，并用e返回，完成下列算法 Status Pop(ListStack S, SElemType e){ if(S.top=NULL) return ERROR; //栈无元素 p