2 线性表的逻辑结构
选择题
（1） 线性表是具有n个（ ）的有限序列。 A．数据 B．字符 C．数据元素 D．数据项
（2） 线性表是（ ）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空
（3） 关于线性表，下列说法中正确的是（ ）。 A．线性表中每个元素都有一个直接前驱和一个直接后继 B．线性表中的数据元素可以具有不同的数据类型 C．线性表中数据元素的类型是确定的
D．线性表中任意一对相邻的数据元素之间存在序偶关系
（4） （ ）是一个线性表。 A．由n个实数组成的集合 B．由所有实数组成的集合 C．由所有整数组成的序列 D．由n个字符组成的序列
6
3 顺序线性表
选择题
（1） 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元
素的地址为144，则第一个元素的地址是（ ）。 A．108 B．180 C．176 D．112
（2） 在长度为n的线性表中查找值为x的数据元素的时间复杂度为（ ）。 A．○(0) B．○(1) C．○(n) D．○(n2)
（3） 在一个长度为n的线性表的第i（1≤i≤n+1）个元素之前插入一个元素，需
向后移动（ ）个元素，删除第i（1≤i≤n）个元素时，需向前移动（ ）个元素。 A．n-i B．n-i+1 C．n-i D．n-i+1
（4） 线性表的顺序存储结构是一种（ ）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取
（5） 顺序存储结构的优点是（ ）。 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示
（6） n个结点的线性表采用数组实现，算法的时间复杂度是○(1)的操作是（ ）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．以上都不对
（7） 对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为
（ ）。
A．○(n)、○(n) B．○(n)、○(1) C．○(1)、○(n) D．○(1)、○(1)
（8） 顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若
申请失败，则说明系统没有（ ）可分配的存储空间。 A．m个 B．m个连续的 C．n+m个 D．n+m个连续的
应用题
（9） 设A是一个线性表（a1，a2，?，an），采用顺序存储结构，则在等概论的前
提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间(1≤i≤n)的概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动的元素个数是多少？
（10） 设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小，
7
D表示可以在数组中存储线性表的最大元素个数（D≥n），则使用顺序存储方式存储线性表需要多少存储空间？
（11） 在什么情况下线性表使用顺序存储比较好？
算法设计题
（12） 试以顺序表作存储结构，实现线性表就地逆置。
（13） 设计算法判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符
串，例如abcba或abba是回文，而abcda不是回文。
（14） 设计一个时间复杂度为○(n)的算法，实现将数组A[n]中所有元素循环左移k
个位置。
（15） 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有
元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为○(n)。
（16） 假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。
（17） 顺序存储的线性表A，其数据元素为整型，设计算法将A拆成B和C两个表，
使A中值大于0的元素存入表B，值小于0的元素存入表C，要求B和C不另外设置存储空间而利用A的空间。
（18） 已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保
持表L仍递增有序。
（19） 设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度
为○(1)。
（20） 设计算法实现从顺序表L中删除所有值在x和y之间的所有元素，要求时间
性能复杂度为○(n)，空间性能为○(1)。
（21） 设计算法删除顺序表中重复的元素，要求算法移动元素的次数较少并使剩余元
素间的相对次序保持不变。
（22） 给定n个记录的有序序列A[n]和m个记录的有序序列B[m]，将它们归并为一
个有序序列，存放在C[n+m]中，试写出这一算法（假设A、B和C均为升序序列）。
8
4 线性链表
选择题
（1） 线性表的链接存储结构是一种（ ）的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取
（2） 线性表采用链接存储时，其（ ）。 A．地址必须是连续的 B．部分地址必须是连续的 C．地址一定是不连续的 D．地址连续与否均可以
（3） 链表不具有的特点是（ ）。 A．可随机访问任一元素 B．插入、删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与线性表长度成正比
（4） 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是
（ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)
（5） 对于n个元素组成的线性表，建立一个单链表的时间复杂度是（ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)
（6） 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ ）。 A．○(1) B．○(n) C．○(n2) D．○(nlog2n1)
（7） 在单链表中删除指针p所指结点的后续结点，则执行（ ）。 A．p->next=p->next->next B．p->next=p->next C．p=p->next->next D．p=p->next; p->next=p->next->next
（8） 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间
插入s所指结点，则执行（ ）操作。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p; C．p->next=s->next; s->next=p; D．p->next=s; s->next=q
（9） 在一个长度为n（n>1）的带头结点的单链表h上，另设有尾指针r指向尾结
点，执行（ ）操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素
C．在单链表第一个元素前插入一个新元素
D．在单链表的最后一个元素后插入一个新元素
（10） 在单链表中附加头结点的目的是为了（ ）。 A．保证单链表中至少有一个结点 B．标识单链表中首结点的位置 C．方便运算的实现 D．说明单链表是线性表的链式存储
9
（11） 将长度为n个单链表链接在长度为m的单链表之后的算法，其时间复杂度是
（ ）。 A．○(1) B．○(n) C．○(m) D．○(n+m)
（12） 循环单链表的主要优点是（ ）。 A．不再需要头指针了
B．从表中任一结点出发都能扫描到整个链表
C．已知某个结点的位置后，能够容易找到它的直接前驱 D．在进行插入、删除操作时，能更好地保证链表不断开
（13） 将线性表（a1，a2，?，an）组织为一个带头结点的循环单链表，设H为链表
的头指针，则链表中最后一个结点的指针域中存放的是（ ）。 A．变量H的地址 B．变量H的值 C．元素a1的地址 D．空指针
（14） 非空的循环单链表L的尾结点p满足（ ）。 A．p=NULL B．p->next=NULL C．p->next=L D．p=L
（15） 若要在○(1)的时间内实现两个循环单链表的首尾相接，则两个循环单链表应
各设一个指针，分别指向（ ）。 A．各自的头结点 B．各自的尾结点 C．各自的第一个元素结点 D．一个表的头结点，一个表的尾结点
（16） 设线性表非空，（ ）可以在○(1)的时间内在表尾插入一个新结点。 A．带头结点的单链表，有一个链表指针指向头结点 B．带头结点的循环单链表，有一个链表指针指向头结点
C．不带头结点的单链表，有一个链表指针指向表的第一个结点
D．不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）
（17） 设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元
素结点，正确的操作是（ ）。 A．s=rear; rear=rear->next; B．rear=rear->next;
C．rear=rear->next->next;
D．s=rear->next->next; rear->next->next=s->next;
（18） 设有两个长度为n个单链表，以h1为头指针的链表是非循环的，以h2为尾指
针的链表是循环的，则（ ）。
A．在两个链表上删除第一个结点的操作，其时间复杂度均为○(1) B．在两个链表的表尾插入一个结点的操作，其时间复杂度均为○(n) C．循环链表要比非循环链表占用更多的存储空间 D．循环链表要比非循环链表占用更少的存储空间
（19） 使用双链表存储线性表，其优点是可以（ ）。
10