数据结构与算法：线性表的题库

数据结构与算法：线性表的题库 线性表是一种基本的数据结构，它是由零个或多个数据元素组成的有序集合。线性表的存储结构可以分为顺序存储结构和链式存储结构两种。顺序存储结构是将所有元素存储在一块连续的存储空间中，每个元素占用固定大小的存储空间。链式存储结构是将每个元素存储在独立的存储空间中，并使用指针将元素连接起来。 单链表是链式存储结构的一种，它由多个结点组成，每个结点包含一个数据域和一个指针域。指针域存储了下一个结点的地址，通过指针域可以将所有结点连接起来。 静态链表存储结构是指将所有结点存储在一块连续的存储空间中，每个结点占用固定大小的存储空间。静态链表存储结构的优点是便于随机存取和插入删除操作。 问题1：线性表的静态链表存储结构与顺序存储结构相比，优点是（A）所有操作算法实现简单（B）便于随机存取（C）便于插入和删除（D）便于利用零散的存储器空间 答案：B 问题2：将下图所示的s所指结点加到p所指结点之后，其语句应为（）p sA s->next=p+1;p->next=s; B (*p).next=s;(*s).next=(*p).next; C s->next=p->next;p->next=s->next; D s->next=p->next;p->next=s; 答案：D 问题3：不带头结点的单链表head为空的判定条件是（）A head= =NULL B head->next= =NULL C head->next= =head D head!=NULL 答案：A 问题4：带头结点的单链表head为空的判定条件是（）A head= =NULL B head->next= =NULL C head->next= =head D head!=NULL 答案：B 问题5：在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行语句（）A s->next=p->next;p->next=s;B p->next=s->next;s->next=p; C q->next=s;s->next=p; D p->next=s;s->next=q; 答案：C 问题6：在一个单链表中，若p所指结点不是最后结点，在p之后插入s结点，则应执行语句（）A s->next=p->next;p->next=s; B s->next=p->next;p->next=s->next; C s->next=p->next;p=s;D p->next=s;s->next=p; 答案：A 问题7：在一个单链表中，若删除p所指结点的后续结点，则应执行语句（）A p->next=p->next->next; B p=p->next;p->next=p->next->next;C p->next=p->next; D p=p->next->next; 答案：A 问题8：从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）A n B n/2 C (n-1)/2 D (n+1)/2 答案：C 问题9：数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构 答案：C 问题10：一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110 （B）108 （C）100 （D）120 答案：D 问题11：在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序 答案：A 问题12：向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（A）8 （B）63.5 （C）63 （D）71 答案：B 问题13：链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针（B）只有一部分，存放结点值（C）只有一部分，存储表示结点间关系的指针（D）分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A 问题14：链表是一种采用_______存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状 答案：B 问题15：线性表若采用链式存储结构时，要求内存中可用存储单元的地址：（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以 答案：C 问题16：线性表Ｌ在 情况下适用于使用链式结构实现。（Ａ）需经常修改Ｌ中的结点值 （Ｂ）需不断对Ｌ进行删除插入 （Ｃ）Ｌ中含有大量的结点 （Ｄ）Ｌ中结点结构复杂 答案：Ｂ 问题17：单链表的存储密度（Ａ）大于1； （Ｂ）等于1； （Ｃ）小于1； （Ｄ）不能确定 答案：Ｃ 问题18：设a1、a2、a3为3个结点，整数P0、3、4代表地址，则如下的链式存储结构称为P034P0a13a24A30（Ａ）循环链表 （Ｂ）单链表 （Ｃ）双向循环链表 （Ｄ）双向链表 答案：Ｂ 问题19：线性表是具有n个_______的有限序列。A 表元素 B 字符 c 数据元素 d 数据项 e 信息项 答案：C 问题20：线性表的静态链表存储结构的优点是（A）便于随机存取（B）便于插入和删除（C）便于利用零散的存储器空间（D）所有操作算法实现简单 答案：B