内容发布更新时间 : 2025/1/12 0:46:08星期一 下面是文章的全部内容请认真阅读。
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所得结果数的链表。
(2