数据结构(专)阶段练习1

《数据结构(专)阶段练习1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华东理工大学网络学院（专科）《数据结构》（ch1绪论和ch2线性表）班级学号姓名成绩一、名词解释（每小题2分，共10分）1.数据结构2.逻辑结构3.存储结构4.线性结构5.非线性结构1.数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。2.逻辑结构：指数据元素之间的逻辑关系。3.存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。4.线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一

2、个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。5.非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。二、填空题（每小题1分，共10分）1.一个算法具有有穷性、确定性、可行性、输入和输出五个重要特性。2.对于给定的n个数据元素，可能构造出集合、线性结构、树形结构和网状（图形）结构四种逻辑结构。3.非空的循环单链表head的尾结点p满足条件p->nex

3、t==head。4.在一个单链表中p所指结点之后插入s所指结点时,应执行s->next=p->next和p->next=s的操作。三、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）（×）1.线性数据结构只能用顺序结构存放，非线性数据结构只能用链式存储存放。（√）2.单链表中逻辑上相邻的元素未必在存储的物理位置次序上相邻。（√）3.顺序表中逻辑上相邻的元素的物理位置必定相邻。（×）4.链式存储是一种随机存取的数据结构。（×）5.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（√

4、）6.在顺序表中按下标序号访问任意一结点的时间复杂度均为O(1)。（√）7.在顺序表中插入或删除一个元素，需要平均移动表中一半元素。（√）8.带头结点的单向链表L为空的判定条件是L->next=null。（×）9.线性表的逻辑顺序与存储顺序总是一致的。（√）10.任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。第6/6页四、单选题（每题2分，共30分）1.有程序如下：i=1;k=0; while(i

5、（1）BO(n)CO(n+1)DO(n2)2.从逻辑上可以把数据结构分成CA动态结构和静态结构B顺序结构和链式结构C线性结构和非线性结构D初等结构和组合结构3.以下对循环链表的叙述错误的是D：A单链表和双向链表经首尾相接都可以形成循环链表B循环链表可以用头指针表示，也可以用尾指针表示C从循环链表的任何一个结点出发都能访问到表中的其他结点D构成循环链表需要增加存储空间4.循环双链表中在p所指结点之后插入结点s的操作是D。Ap->next=s;s->prior=p;p->next->prior=s;s->ne

6、xt=p->nextBp->next=s;p->next->prior=s;s->prior=p;s->next=p->nextCs->prior=p;s->next=p;p->next=s;p->next->prior=sDs->prior=p;p->next=s;s->next=p->next;p->next->prior=s;5.在n个结点的带头结点的单链表中，要在已知结点*p之后插入一个新结点，则其操作的时间复杂度为A。AO（1）BO(n)CO(n+1)DO(n2)6.在n个结点的带头结点的单链表

7、中，要在已知结点*p之前插入一个新结点，则其操作的时间复杂度为B。AO（1）BO(n)CO(n+1)DO(n2)7.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动B个元素。A8B63.5C63D78.在n个结点的单链表中，算法的时间复杂度是O(n)的操作是A：A求链表的第i个结点B在地址为p的结点之后插入一个结点C删除开始结点D删除地址为p的结点的后继结点第6/6页9.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是A：A访问第i个结点（1≤i≤n）和求第i个结点的直接

8、前驱（2≤i≤n）B在第i个结点后插入一个新结点（1≤i≤n）C删除第i个结点（1≤i≤n）D将n个结点从小到大排序10.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是BA110B108C100D12011.对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为：CA顺序表B用头指针表示的单循环链表C用尾指针表示的单循环链表D单链表12.线性表若采用链式存储结构时，要求内存中可用存储单元的地