《数据结构第2章-答案.doc》由会员分享，可在线阅读，更多相关《数据结构第2章-答案.doc（7页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表数据结构作业答案一、填空题01、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用顺序存储结构。02、线性表L=（a1,a2,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是(n-1)/2。03、在有n个元素的顺序表中插入一个新元素，需要平均移动n/2元素，具体移动的元素个数与表长和该元素在表中的位置有关。04、线性表中结点的集合是有限的，结点间的关系是一对一的。05、向一个长度为n的顺序表的第i个元素(1in+1)之前插入一个元素时，需向后移动n-i+1个元素。06、向一个长度为n的顺序表
2、中删除第i个元素(1in)时，需向前移动n-i个元素。07、在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。08、顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置未必相邻。09、在单链表中，除了首结点外，任一结点的存储位置由其直接前驱结点的链域值指示。10、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O(n)。11、设单链表的结点结构为(data,next)，next 为指针域，已知指针px指向单链表中data域为x的结点，指针py 指向data域为y的新结点，若将结点y插入结点x之后，则
3、需要执行以下语句：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所指的结点，则需执行
4、下列语句：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=L21、在单链表L 中，指针p 所指结点有后继结点的条件
5、是 p-next!=null22、带头结点的双循环链表L为空表的条件是 L-next=L & L-prior=L23、在单链表p结点之后插入s结点的操作是 s-next=p-next; p-next=s;二、判断题01、链表的每个结点中都恰好包含一个指针。02、链表的物理存储结构具有同链表一样的顺序。03、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。04、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。05、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 06、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
6、07、线性表在物理存储空间中也一定是连续的。08、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。09、顺序存储方式只能用于存储线性结构。10、线性表的逻辑顺序与存储顺序总是一致的。11、链表中的头结点仅起到标识的作用。12、顺序存储结构的主要缺点是不利于插入或删除操作。13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。14、对任何数据结构链式存储结构一定优于顺序存储结构。15、集合与线性表的区别在于是否按关键字排序。16、所谓静态链表就是一直不发生变化的链表。17、线性表的特点是每个元素都有一个前驱和一个后继。18、取线性表的第i个元素的时间同i的大小有
7、关。19、循环链表不是线性表。20、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。三、单项选择题C01、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为_。 A) 存储结构 B) 逻辑结构 C) 顺序存储结构 D) 链式存储结构B02、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 。 A) 110 B) 108 C) 100 D) 120A03、在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是_。 A) 访问第i个结点(1in)和求第i个结点的直接前驱(2in) B) 在第i个结点后插入一
8、个新结点(1in) C) 删除第i个结点(1in) D) 将n个结点从小到大排序B04、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 _ 个元素。 A) 8 B) 63.5 C) 63 D) 7A05、链式存储的存储结构所占存储空间_。 A) 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B) 只有一部分，存放结点值 C) 只有一部分，存储表示结点间关系的指针 D) 分两部分，一部分存放结点值，另一部分存放结点所占单元数A06、下述_是顺序存储结构的优点。 A) 存储密度大 B) 插入运算方便 C) 删除运算方便 D)可方便地用于各种逻辑结构的存储
9、表示D07、线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。 A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续都可以B08、线性表L在 情况下适用于使用链式结构实现。 A) 需经常修改L中的结点值 B) 需不断对L进行删除插入 C) L中含有大量的结点 D) L中结点结构复杂C09、单链表的存储密度_。 A) 大于1 B) 等于1 C) 小于1 D) 不能确定D10、若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用_存储方式最节省运算时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 带头结点的双
10、向循环链表D11、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用_存储方式最节省时间。 A) 单向链表 B) 双向链表 C) 单向循环链表 D) 顺序表A12、链表不具有的特点是_。 A) 可随机访问任一元素 B) 插入删除操作不需要移动元素 C) 不必事先估算存储空间 D) 所需空间与线性表长度成正比B13、在单向链表的指针p所指结点后插入结点*s(*p不是尾结点)，则应执行_操作。 A) s-next=p; p-next=s; B) s-next=p-next; p-next=s; C) s-next=p-next; p=s; D) p-next=s; s-next=p;C14、
11、非空的循环单向链表first的尾结点(由p指向)满足_。 A) p-next=NULL B) p=NULL C) p-next=first D) p=firstC15、下列关于线性表的叙述中，不正确的是_。 A) 线性表是n个结点的有穷序列 B) 线性表可以为空表 C) 线性表的每一个结点有且仅有一个前趋和一个后继 D) 线性表结点间的逻辑关系是1:1的联系 A16、在双向链表存储结构中删除p所指的结点时，需要按_修改指针的链接。 A) p-prior-next=p-next; p-next-prior=p-prior; B) p-prior=p-prior-next; p-prior-pri
12、or-next=p; C) p-prior-prior-next=p; p-prior=p-prior-prior; D) p-next-next-prior=p; p-next=p-next-next;A17、在单循环链表中指针p指向结点A，若要删除A之后的结点(存在)，则其中指针的链接操作为_。 A) p-next=p-next-next B) p=p-next C) p=p-next-next D) next=pB18、带头结点的单链表head为空的判定条件是_。 A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULL
13、D19、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较_个结点。 A) n B) n/2 C) (n-1)/2 D) (n+1)/2B20、在一个具有n个结点的有序单链表中插入一个新结点，并仍然有序的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()C21、给定有n个元素的向量，建立一个有序的单链表的时间复杂度为_。 A) O(1) B) O(n) C) O() D) O()A22、下面程序的功能是_。void delete(Linklist *L) p=L; while (p-next!=NULL) m=p-next-data; q=p; while (q-next!=NULL) if (q-next-data=m) r=q-next; q-next=r-next; free(r); q=q-next; p=p-next; A) 在单链表中删除重复结点 B) 在单链表中删除第m个结点 C) 在单链表中的第m个位置插入结点 D) 在单链表中统计结点的数目并保存到m中C23、线性表是具有n 个_的有限序列(n0)。 A) 表元素 B) 字符 C) 数据元素 D) 数据项A24、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入
