数据结构试卷及答案.doc

《数据结构试卷及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、东华理工大学2015—2016学年第一学期考试模拟试卷A一、填空题（50分）1、数据结构是一门研究非数值计算的程序设计问题中的数据元素以及它们之间关系和运算等的科学。（2分）2、数据结构的类型通常分为：集合、线性结构、树形结构、图状结构或网状结构；从逻辑上可以把它们分成：线性结构和非线性结构。3、数据的逻辑结构只抽象反映数据元素的逻辑关系；数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。4、算法分析的目的是分析算法的效率以求改进，算法分析的两个主要方面是空间复杂度和时间复杂度。A5、计算机算法是解决问题的有限运算序列，它必须具备输入、输

2、出、确定性、有穷性和稳定性等5个方面的特性。6、线性结构中元素之间的关系存在一对一关系，树形结构中元素之间的关系存在一对多关系，图形结构中元素之间的关系存在多对多关系。7、试写出以下算法的时间复杂度i=s=0while(s

3、aiÎElemset,i=1,2,…,n

4、,n³0}数据关系：R={

5、ai-1,aiÎD,i=2,…,n}基本操作：InitList(&L)//构造一个空的线性表LDestroyList(&L)//消毁线性表LListLength(L)//返回L中数据元素的个数ListInsert(&L,i,e)//1≤i≤ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e)//1≤i≤ListLength(L),删除L中的第i个元素，并用e返回ListTraverse(L,visit())//依次对L的每个元素调用函数vis

6、it()…………}ADTList10、指出线性表顺序存储、链式存储结构的优缺点。答：顺序存储优点：逻辑上相邻，物理位置也相邻，可以随机存取表中任一元素；缺点：插入和删除元素时需要移动大量元素。链式存储结构优点：插入、删除元素时不需要移动元素；缺点：逻辑上相邻，物理位置不一定相邻，不能随机存取表中元素，需要依次查找，求线性表的长度时不如顺序存储结构方便，需要逐个结点搜索计算，或设置带头结点的线性链表。11、完成下列在单链表中删除元素算法StatusListDelete_L(LinkList&L,inti,ElemType&e){//删除第i个元素ep=

7、L;j=0;//p指向头结点while(p->next&&jnext;++j}//寻找第i个结点,并令p指向其前驱if(!(p->next)

8、

9、j>i-1)returnERROR;//删除位置不正确q=p->next;p->next=q->next;//删除与释放结点e=q->data;free(q);returnOK;}12、在一个长度为n的线性链表中第i个元素（1£i£n）之前插入一个元素时，需向后移动n-i+1个元素。13、在一个长度为n的线性链表中删除第i个元素（1£i£n）时，需向前移动n-i个元素。14、在一个单链表

10、中p所指结点之后插入一个s所指结点时，应执行s->next=p->next和p->next=s的操作。15、在单链表中，插入或删除一个结点元素时，仅需要修改指针而不需要移动元素。16、栈(Stack)是限定仅在表尾进行插入和删除操作的线性表，17、栈链式存储结构中删除栈顶元素，并用e返回，完成下列算法StatusPop(ListStack&S,SElemType&e){if(S.top=NULL)returnERROR;//栈无元素p=S.top;S.top=S.top->next;e=p->data;free(p);//释放节点批pS.len--;

11、returnOK;}17、设有一队列，(a1,a2,…,an)则对头元素是a1队尾元素是an。18、假设队列以带头结点的链式表示，则删除一个元素并返回给e的算法如下：StatusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)returnEEROR;p=Q.front->next;//p为需要删除的结点e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;//队列中只有一个元素被删除时，队尾等于队头free(p);returnOK

12、;}19、循环队列中，假设少用一个元素，则插入元素到队尾的算法StatusEnQueue(SqQueue&Q