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） 线性链表有哪几种常见的变形？各有何特点？
16
算法设计题
（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，通过遍历链表将链表中所有的链接方向逆转，
17
算法如下，请在空格处填写正确的语句。 void Inverse(&h) { if ( ① ) return; p=h->next; pr=NULL; while ( ② ) { h->next=pr;pr=h; h=p; ③ } }
（23） 设两个带头结点的单链表A和B，表中结点的数据为整型，下面算法产生表A
和表B的并集并以表C存储，请填写算法中空白处的语句，完成其功能。
18
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） 若一个栈的输入序列是1，2，3，?，n，其输出序列是p1，p2，?，pn，若
p1=3，则p2的值（ ）。 A．一定是2 B．一定是1 C．不可能是1 D．以上都不对
（8） 若一个栈的输入序列是p1，p2，?，pn，其输出序列是1，2，3，?，n，若
p3=1，则p1的值（ ）。 A．可能是2 B．一定是2 C．不可能是2 D．不可能是3
（9） 当字符序列t3_依次通过栈，输出长度为3且可用作C语言标识符的序列有
（ ）。 A．4个 B．5个 C．3个 D．6个
应用题
（10） 设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，
若能，请写出操作序列，若不能，请说明原因。
19
①C，E，A，B，D ②C，B，A，D，E
（11） 在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈
顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）
（12） 设元素1、2、3、P、A依次经过一个栈，进栈次序为123PA，在栈的输出序
列中，有哪些序列可作为C++程序设计语言的变量名。
（13） 如果进栈序列为A、B、C、D，则可能的出栈序列是什么？
算法设计题
（14） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出
栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
① 下面所示的序列中哪些是合法的？ A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO ② 通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，
否则返回false（假定被判定的操作序列已存入一维数组中）。
20