数据结构第2章-习题

《数据结构第2章-习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章线性表数据结构作业答案一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。02、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是。03、在有n个元素的顺序表中插入一个新元素，需要平均移动元素，具体移动的元素个数与和有关。04、线性表中结点的集合是的，结点间的关系是的。05、向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动个元素。06、向一个长度为n的顺序表中

2、删除第i个元素(1≤i≤n)时，需向前移动个元素。07、在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表也称为的数据结构。08、顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。09、在单链表中，除了首结点外，任一结点的存储位置由指示。10、在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复杂度为。11、设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data域为x的结点，指针py指向data域为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：

3、12、在单链表中设置头结点的作用是。13、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为，在给定值为x的结点后插入一个新结点的时间复杂度为。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是：15、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->next=p;s->prior=;p->prior=s;=s;16、链接存储的特点是利用来表示数据元素之间的逻辑关系。17、对于双向链表，在两个结点之间插入一个新结点需修改的指针共个，单链表为个。1

4、8、循环单链表的最大优点是。19、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是20、带头结点的双循环链表L中只有一个元素结点的条件是21、在单链表L中，指针p所指结点有后继结点的条件是22、带头结点的双循环链表L为空表的条件是23、在单链表p结点之后插入s结点的操作是二、判断题01、链表的每个结点中都恰好包含一个指针。02、链表的物理存储结构具有同链表一样的顺序。03、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。04、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个

5、复杂类型。05、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。06、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。07、线性表在物理存储空间中也一定是连续的。08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。09、顺序存储方式只能用于存储线性结构。10、线性表的逻辑顺序与存储顺序总是一致的。11、链表中的头结点仅起到标识的作用。12、顺序存储结构的主要缺点是不利于插入或删除操作。13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。14、对任何数据结构链式存储结构一定优于顺序存储

6、结构。15、集合与线性表的区别在于是否按关键字排序。16、所谓静态链表就是一直不发生变化的链表。17、线性表的特点是每个元素都有一个前驱和一个后继。18、取线性表的第i个元素的时间同i的大小有关。19、循环链表不是线性表。20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。5第2章线性表数据结构作业答案三、单项选择题01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___。A)存储结构B)逻辑结构C)顺序存储结构D)链式存储结构02、一个向量第一个元素的存储地址是100

7、，每个元素的长度为2，则第5个元素的地址是。A)110B)108C)100D)12003、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是___。A)访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B)在第i个结点后插入一个新结点(1≤i≤n)C)删除第i个结点(1≤i≤n)D)将n个结点从小到大排序04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动_个元素。A)8B)63.5C)63D)705、链式存储的存储结构所占存储空间___。A)分两部分，一部分存放结点值，另一部分存放表示

8、结点间关系的指针B)只有一部分，存放结点值C)只有一部分，存储表示结点间关系的指针D)分两部分，一部分存放结点值，另一部分存放结点所占单元数06、下述___是顺序存储结构的优点。A)存储密度大B)插入运算方