数据结构期末考试(题集).doc

数据结构的基本概念

选择题
（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。
A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。
A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。
A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系
C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。
A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。
A．数据的处理方法 B．数据元素的类型
C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。
A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储区域
C．结点的最后一个域是指针类型 D．每个结点有多少个后继就设多少个指针

（7） 下列说法不正确的是（ ）。
A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小单位
C．数据可由若干个数据项构成 D．数据元素可由若干个数据项构成

（8） 以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B．链表 C．散列表 D．栈

（9） 以下术语属于逻辑结构的是（ ）。
A．顺序表 B．哈希表 C．有序表 D．单链表

（10） 可以用（ ）定义一个完整的数据结构。
A．数据元素 B．数据对象 C．数据关系 D．抽象数据类型

（11） 对于数据结构的描述，下列说法中不正确的是（ ）。
A．相同的逻辑结构对应的存储结构也必相同
B．数据结构由逻辑结构、存储结构和基本操作三方面组成
C．数据结构基本操作的实现与存储结构有关
D．数据的存储结构是数据的逻辑结构的机内实现

（12） 以下关于链接存储结构的叙述中，（ ）是不正确的。
A．结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构
B．逻辑上相邻的结点物理上不一定相邻
C．可以通过计算得到第i个结点的存储地址
D．插入和删除操作方便，不必移动结点

（13） 可以用（ ）、数据关系和基本操作定义一个完整的抽象数据类型。
A．数据元素 B．数据对象 C．原子类型 D．存储结构

应用题
（14） 设有数据结构（D，R），其中D={1，2，3，4，5，6}，R={(1，2)，(2，3)，(2，4)，(3，4)，(3，5)，(3，6)，(4，5)，(4，6)}。试画出其逻辑结构图并指出属于何种结构。

（15） 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

（16） 说明数据的逻辑结构和存储结构之间的关系。

（17） 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？

1 算法和算法分析

选择题
（1） 算法指的是（ ）。
A．对特定问题求解步骤的一种描述，是指令的有限序列
B．计算机程序
C．解决问题的计算方法
D．数据处理

（2） 下面（ ）不是算法所必须具备的特性。
A．有穷性 B．确切性 C．高效性 D．可行性

（3） 算法必须具备输入、输出和（ ）等特性。
A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性
C．确定性、稳定性和有穷性 D．易读性、稳定性和健壮性

（4） 算法应该具有确定性、可行性和有穷性，其中有穷性是指（ ）。
A．算法在有穷的时间内终止 B．输入是有穷的
C．输出是有穷的 D．描述步骤是有穷的

（5） 当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的（ ）。
A．可读性 B．健壮性 C．正确性 D．有穷性

（6） 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。
A．找出数据结构的合理性 B．研究算法中输入和输出的关系
C．分析算法的效率以求改进 D．分析算法的易读性和文档性
E．空间性能和时间性能 F．正确性和简明性
G．可读性和文档性 H．数据复杂性和程序复杂性

（7） 算法的时间复杂度与（ ）有关。
A．问题规模 B．计算机硬件性能
C．编译程序的质量 D．程序设计语言

（8） 算法的时间复杂度与（ ）有关。
A．问题规模 B．待处理数据的初态
C．算法的易读性 D．A和B

（9） 某算法的时间复杂度是○(n2)，表明该算法（ ）。
A．问题规模是n2 B．执行时间等于n2
C．执行时间与n2成正比 D．问题规模与n2成正比

（10） 下面说法错误的是（ ）。
①算法原地工作的含义是指示不需要如何额外的辅助空间
②在相同的规模n下，复杂度○(n)的算法在时间上总是优于复杂度○(2n)的算法
③所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
④同一个算法，实现语言的级别越高，执行效率就越低

（11） 算法
for (i=n-1; i>=1; i--)
for (j=1; j<=i; j++)
if (a[j]>a[j+1]) a[j]与a[j+1]交换；
其中n为正整数，则最后一行语句的频度（执行次数）在最坏情况下是（ ）。
A．○(n) B．○(nlog2n) C．○(n3) D．○(n2)

（12） 算法的时间复杂度属于一种（ ）。
A．事前统计的方法 B．事先分析估算的方法
C．事后统计的方法 D．事后分析估算的方法

（13） 设某算法完成对n个元素进行处理，所需的时间是T(n)=100 nlog2n+200n+500，则该算法的时间复杂度是（ ）。
A．○(1) B．○(n) C．○(nlog2n) D．○(nlog2n+n)

（14） 假设时间复杂度为○(n2)的算法在有200个元素的数组上运行需要3.1ms，则在有400个元素的数组上运行需要（ ）ms。
A．3.1 B．6.2 C．12.4 D．x（无法确定）

（15） 下列程序段加下划线的语句执行（ ）次。
for (m=0,i=1; i<=1; i++)
for (j=1; j<=2*i; j++)
m=m+1；
A．n2 B．3n C．n(n+1) D．n3

应用题
（16） 将下列函数按它们的n→∞时的无穷大阶数，从小到大排列。
n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n

（17） 分析以下程序段，并用大○记号表示其执行时间。

① i=1;k=0;
while (i<n-1)
{
k=k+10*i;
i++;
}
② i=1;j=0;
while (i+j<=n)
if (i>j) j++;
else i++;
③ for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=j;k++)
x++;
④ i=1;k=0;
do
{
k=k+10*i;
i++;
} while (i<=n)
⑤ y=0;
while ((y+1)*(y+1)<=n)
y=y+1

⑥ for (i=0;i<n;i++)
for (j=0;j<m;j++)
a[i][j]=0;

（18） 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为T1=○(2n)，A2的时间复杂度为T2=○(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。

综合应用题
（19） 设n是偶数，且有程序段：
for (i=1;i<=n;i++)
if (2*i<=n)
for (j=2*I;j<=n;j++)
y=y+i*j;
则语句y=y+i*j的执行次数是多少？要求列出计算公式。

（20） 斐波那契数列Fn定义如下：
F0=0，F1=1，…，Fn=Fn-1+Fn-2 n=2，3，…
请就此斐波那契数列，回答下列问题。
① 在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，…，F1，F0精确计算多少次？
② 用大○表示法给出递归计算时递归函数的时间复杂度是多少？

（21） 运算是数据结构的一个重要方面。举例说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性，则这两个数据结构是不同的。

（22） 针对给定的实际问题建立数据结构时，应从哪些方面考虑。

2 线性表的逻辑结构

选择题
（1） 线性表是具有n个（ ）的有限序列。
A．数据 B．字符 C．数据元素 D．数据项

（2） 线性表是（ ）。
A．一个有限序列，可以为空 B．一个有限序列，不能为空
C．一个无限序列，可以为空 D．一个无限序列，不能为空

（3） 关于线性表，下列说法中正确的是（ ）。
A．线性表中每个元素都有一个直接前驱和一个直接后继
B．线性表中的数据元素可以具有不同的数据类型
C．线性表中数据元素的类型是确定的
D．线性表中任意一对相邻的数据元素之间存在序偶关系

（4） （ ）是一个线性表。
A．由n个实数组成的集合 B．由所有实数组成的集合
C．由所有整数组成的序列 D．由n个字符组成的序列

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表示存储数据元素所需要的存储单元大小，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均为升序序列）。
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．说明单链表是线性表的链式存储

（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） 使用双链表存储线性表，其优点是可以（ ）。
A．提高查找速度 B．更方便数据的插入和删除
C．节约存储空间 D．很快回收存储空间

（20） 与单链表相比，双链表的优点之一是（ ）。
A．插入和删除操作更简单 B．可以进行随机访问
C．可以省略表头指针或表尾指针 D．访问其后相邻结点更灵活

（21） 带头结点的循环双链表L为空表的条件是（ ）。
A．L->next->prior=NULL B．L->prior=L
C．L->next=L D．B和C都对

（22） 在循环双链表的p所指结点后插入s所指结点的操作是（ ）。
A．p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
B．p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
C．s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
D．s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

（23） 在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是（ ）。
①pb->next=pa->next; ②pb->prior=pa;
③pa->next=pb; ④pa->next->prior=pb;
A．①②③④ B．④③②① C．③④①② D．①④③②

（24） 在一个双链表中，删除结点p的操作是（ ）。
A．p->prior->next=p->next; p->next->prior=p->prior;
B．p->prior=p->prior->prior; p->prior->prior=p;
C．p->next->prior=p; p->next=p->next->next;
D．p->next=p->prior->prior; p->prior=p->prior->prior;

应用题
（25） 单链表设置头结点的作用是什么？

（26） 线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？

（27） 若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？

（28） 设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？

算法设计题
（29） 设计算法依次打印单链表中每个结点的数据信息。

（30） 求单链表的长度。

（31） 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，若找不到值为k的结点，则将x插入到链表的末尾。

（32） 判断非空单链表是否递增有序。

（33） 已知非空线性链表由list指出，结点结构为（data，link）。请编写算法，将链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。

（34） 给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。

（35） 已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中的位置（设p所指结点不是链表的最后一个结点）。

（36） 设计算法实现将单链表就地逆置。

（37） 头插法建立单链表。

（38） 尾插法建立单链表

（39） 复制一个单链表。

（40） 设计算法实现将单链表就地逆置。

（41） 在一个有序单链表（假设从小到大排列）中插入一个元素值为x的结点，使得插入后单链表仍然有序。

（42） 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。

（43） 已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于mink且小于maxk的所有元素，并释放被删结点的存储空间。

（44） 有两个整数序列A=(a1，a2，…，am)和B=(b1，b2，…，bn)已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列。

（45） 设线性表C=(a1，b1，a2，b2，…，an，bn)采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和B，使得A=(a1，a2，…，an)，B=(b1，b2，…，bn)。

（46） 有两个递增有序的单链表la和lb，设计算法将这两个单链表合并为一个有序链表。

（47） 有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。

（48） 已知单链表A和B的数据（设为整型）递增有序，设计算法利用原有结点，将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。

（49） 设计算法将循环单链表就地逆置。

（50） 已知L为单链表的头结点地址，表中共有m（m＞3）个结点，从表中第i个（1＜i＜m）结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。

（51） 假设在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。

（52） 设循环单链表L1，对其遍历的结果是：x1，x2，x3，…，xn-1，xn。请将该循环链表拆成两个循环单链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1，x3，…；L2中含有原L1表中序号为偶数的结且遍历结果为：…，x4，x2。

（53） 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环单链表，使每个循环链表中只含同一类字符。

（54） 有两个循环链表tail1和tail2（tail1和tail2分别指向循环链表的尾指针），编写算法将循环链表tail2链接到循环链表tail1之后，并使链接后的链表仍是循环链表。

（55） 已知p指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表（a1，a2，…，an-1，an，）改造成（a1，a2，…，an-1，an，an-1，…，a2，a1）。

（56） 判断带头结点的循环双链表是否对称。

（57） 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。

（58） 已知非空循环双链表head的存储结构为：
Struct DNode {
TElem info;
Struct DNode *left;
Struct DNode *right;
};
设计算法实现从链表中删除指针p所指结点的前驱结点（假设该结点存在）。

（59） 已知非空双链表由d指出，结点结构为（priordatanext），请设计算法将链表中数据值最大（假定唯一）的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。

（60） 设计算法实现将双链表中结点p与其后继结点互换位置。

（61） 设有一个双链表，每个结点中除了有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零，每当在双链表上进行一次LOCATE运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。
5 静态链表
选择题
（1） 静态链表中指针表示的是（ ）。
A．下一结点在内存中的地址 B．下一元素在数组中的下标
C．左、右孩子的存储位置 D．左、右孩子的地址

（2） 以下说法错误的是（ ）。
①静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关
②静态链表中能容纳的元素个数在定义表时必须是确定的
③静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动
A．①，② B．① C．①，②，③ D．②

（3） 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中某结点，使j沿链移动的操作为（ ）。
A．j=r[j].next B．j=j+1
C．j=j->next D．j=r[j]->next

（4） 线性表的静态链表存储与顺序存储相比，优点是（ ）。
A．所有基本操作的算法实现简单 B．便于随机存取
C．便于插入和删除 D．便于利用零散的存储空间

（5） 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a[0].link，则该线性表的元素依次为（ ）。
下标
0
1
2
3
4
5
6
7
8
data

60
63
40
45

74
25

link
4
3
7
6
2

0
1

A．60，63，40，45，74，25 B．45，63，25，60，40，74
C．74，25，45，60，40，63 D．25，45，60，40，63，74

6 线性表综合
选择题
（1） 下面关于线性表的叙述中，错误的是（ ）。
A．线性表采用顺序存储，必须占用一片连续的存储单元
B．线性表采用顺序存储，便于进行插入和删除操作
C．线性表采用链接存储，不必占用一片连续的存储单元
D．线性表采用链接存储，便于插入和删除操作

（2） 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（ ）存储方法最节约时间。
A．顺序表 B．单链表 C．双链表 D．循环单链表

（3） 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（ ）存储方法最节约时间。
A．单链表 B．循环双链表
C．循环单链表 D．带尾指针的循环单链表

（4） 设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现的效率更高。
A．输出第i（1≤i≤n）个元素值
B．交换第1个和第2个元素的值
C．顺序输出所有n个元素
D．查找与给定值x相等的元素在线性表中的序号

（5） 如果对于具有n（n＞1）个元素的线性表的基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。则最好使用（ ）。
A．只设尾指针的循环单链表
B．只设尾指针的非循环单链表
C．只设头指针的循环双链表
D．同时设置头指针和尾指针的循环单链表

应用题
（6） 请比较线性表的两种基本的存储结构——顺序表和单链表。

（7） 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，算法的效率不同。

（8） 如果某线性表中数据元素的类型不一致，但是希望能根据下标随机存取每个元素，请为这个线性表设计一个合适的存储结构。

（9） 线性链表有哪几种常见的变形？各有何特点？

算法设计题
（10） 用顺序表表示集合，设计算法实现集合的求交集运算。

（11） 用顺序表表示集合，设计算法实现集合的求并集运算。

（12） 用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。

（13） 假定以有序表表示集合，设计算法判断两个给定集合是否相等。

（14） 设两个单链表L1和L2分别表示两个集合，设计算法判断L1是否是L2的子集。

（15） 已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序，求A、B的交集C，并以同样的递增形式存储，要求尽可能节省时间。

（16） 在某商店的仓库中，对电视机按其价格从低到高建立一个单链表，链表的每个结点指出同样价格的电视机的台数。现有m台价格为n元的电视机入库，请编写算法完成仓库的进货管理。

（17） 从键盘输入n个英语单词，输入格式为n，w1，w2，…，wn，其中n表示随后输入英语单词个数，试编写算法建立一个单链表，要求：
①如果单词重复出现，则只在链表上只保留一个；
②统计单词重复出现的次数，然后输出次数最多的前k（k＜n）个单词。

（18） 一元稀疏多项式可以采用单链表形式存储，设计算法完成A(x)+B(x)，其中A(x)和B(x)均为稀疏的一元多项式，要求利用原表的存储空间。

（19） 假设用不带头结点的单链表表示八进制数，例如，八进制数536可以表示成三个结点的链表。要求写一个函数Add，该函数有两个参数P和Q，分别指向表示八进制数的链表，执行函数调用Add(P,Q)后，将返回表示八进制数P加八进制数Q所得结果数的链表。

（20） 约瑟夫环问题：设有编号为1，2，…，n的n（n＞0）个人围成一个圈，每个人持有一个密码m（m≠1），从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，…，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。

（21） 编写算法，完成下述要求：
①建立一个链表用于存放输入的二进制数，链表中的每个结点的data域存放一个二进制位。
②在此链表上实现对二进制数加1的运算，并输出运算结果。

（22） 有一个不带头结点的单链表h，通过遍历链表将链表中所有的链接方向逆转，算法如下，请在空格处填写正确的语句。
void Inverse(&h) {
if ( ① ) return;
p=h->next; pr=NULL;
while ( ② ) {
h->next=pr;pr=h;
h=p; ③
}
}

（23） 设两个带头结点的单链表A和B，表中结点的数据为整型，下面算法产生表A和表B的并集并以表C存储，请填写算法中空白处的语句，完成其功能。

7 栈的基本概念

选择题
（1） 经过以下栈运算后，x的值是（ ）。
InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，GetTop(s,x)
A．a B．b C．1 D．0

（2） 经过以下栈运算后，StackEmpty(s)的值是（ ）。
InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，Pop(s,y)
A．a B．b C．1 D．0

（3） （ ）不是栈的基本运算。
A．删除栈顶元素 B．删除栈底元素
C．判断栈是否为空 D．将栈置为空栈

（4） 设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单位的存储空间，则执行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，栈顶指针值为（ ）。
A．1002H B．1003H C．1004H D．1005H

（5） 一个栈的入栈序列是{1，2，3，4，5}，则栈的不可能的输出序列是（ ）。
A．{5，4，3，2，1} B．{4，5，3，2，1}
C．{4，3，5，1，2} D．{1，2，3，4，5}

（6） 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（ ）。
A．不确定 B．n-i C．n-i-1 D．n-i+1

（7