数据结构第2章-答案.doc

一、填空题 01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。 02、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。 03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。 04、线性表中结点的集合是有限的，结点间的关系是一对一的。 05、向一个长度为n的顺序表的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。 06、向一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动n-i个元素。 07、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 08、顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置未必相邻。 09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。 10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n)。 11、设单链表的结点结构为(data,next)，next 为指针域，已知指针px指向单链表中data域为x的结点，指针py 指向data域为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：py-next=px-next; px-next=py; 12、在单链表中设置头结点的作用是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。 13、对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x 的结点后插入一个新结点的时间复杂度为O(n)。 14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是：f-next=p-next; f-prior=p; p-next-prior=f; p-next=f; 15、在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s-next=p; s-prior= p-prior; p-prior=s; s-prior-next =s; 16、链接存储的特点是利用指针来表示数据元素之间的逻辑关系。 17、对于双向链表，在两个结点之间插入一个新结点需修改的指针共4个，单链表为2个。 18、循环单链表的最大优点是从任一结点出发都可访问到链表中每一个元素。 19、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是 u=p-next; p-next=u-next; free(u); 20、带头结点的双循环链表L中只有一个元素结点的条件是 L-next-next==L 21、在单链表L 中，指针p 所指结点有后继结点的条件是 p-next!=null 22、带头结点的双循环链表L为空表的条件是 L-next==L L-prior==L 23、在单链表p结点之后插入s结点的操作是 s-next=p-next; p-next=s; 二、判断题 ×01、链表的每个结点中都恰好包含一个指针。 ×02、链表的物理存储结构具有同链表一样的顺序。 ×03、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 ×04、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 ×05、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 ×06、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 ×07、线性表在物理存储空间中也一定是连续的。 ×08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 ×09、顺序存储方式只能用于存储线性结构。 ×10、线性表的逻辑顺序与存储顺序总是一致的。 ×11、链表中的头结点仅起到标识的作用。 √12、顺序存储结构的主要缺点是不利于插入或删除操作。 √13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 ×14、对任何数据结构链式存储结构一定优于顺序存储结构。 ×15、集合与线性表的区别在于是否按关键字排序。 ×16、所谓静态链表就是一直不发生变化的链表。 ×17、线性表的特点是每个元素都有一个前驱和一个后继。 ×18、取线性表的第i个元素的时间同i的大小有关。 ×19、循环链表不是线性表。 √20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 三、单项选择题 C01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___。 A) 存储结构 B) 逻辑结构