数据结构课后练习习题及解析第二章.docx
文本预览下载声明
第二章习题
描述以下三个概念的区别：头指针，头结点，首元素结点。
填空：
（ 1 ）
在顺序表中插入或删除一个元素，需要平均移
动
元素，具体移动的元素个数与
有
关。
（ 2 ）
在顺序表中，逻辑上相邻的元素，其物理位
置
相邻。在单链表中，逻辑上相邻的元素，其物理位
置
相邻。
（ 3 ）
在带头结点的非空单链表中，头结点的存储位置
由
指示，首元素结点的存储位置
由
指示，除首元素结点外，其它任一元素结点的存储位置
由
指示。
3．已知 L 是无表头结点的单链表，且
P 结点既不是首元素结点，也不是尾元素结点。按要
求从下列语句中选择合适的语句序列。
a.
在
P
结
点
后
插
入
S
结
点
的
语
句
序
列
是：
。
b.
在
P
结
点
前
插
入
S
结
点
的
语
句
序
列
是：
。
c.
在
表
首
插
入
S
结
点
的
语
句
序
列
是：
。
d.
在
表
尾
插
入
S
结
点
的
语
句
序
列
是：
。
供选择的语句有：
1） P-next=S;
2） P-next= P-next-next;
3） P-next= S-next;
4） S-next= P-next;
5） S-next= L;
6） S-next= NULL;
7） Q= P;
8） while(P-next!=Q) P=P-next;
9） while(P-next!=NULL) P=P-next;
10） P= Q;
11） P= L;
12） L= S;
13） L= P;
4.
设线性表存于 a(1:arrsize)
的前 elenum 个分量中且递增有序。试写一算法，
将 X 插入到线性表的适当位置上，以保持线性表的有序性。
5.
写一算法，从顺序表中删除自第
i 个元素开始的 k 个元素。
6.
已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试
写一高效算法，删除表中所有大于
mink 且小于 maxk 的元素（若表中存在这样的元素）
，分
析你的算法的 复 度（注意： mink 和 maxk 是 定的两个参 量，它 的 任意的整数）。
7. 分 以不同的存 构 性表的就地逆置算法，即在原表的存 空 将
性表（ a1, a2..., an ）逆置 （ an, an-1,..., a1 ）。
（1） 以一 数 作存 构， 性表存于 a(1:arrsize) 的前 elenum 个分量中。
（2） 以 表作存 构。
8.
假 两个按元素 增有序排列的 性表
A 和 B，均以 表作 存 构，
写算法，将 A 表和 B 表 并成一个按元素 减有序排列的 性表
C，并要求利用原表
（即 A 表和 B 表的） 点空 存放表 C。
9.
假 有一个循 表的 度大于
1，且表中既无 点也无 指 。已知
s
指向 表某个 点的指 ， 写算法在 表中 除指
s 所指 点的前 点。
10.
已知有 表表示的 性表中含有三 字符的数据元素
（如字母字符、 数字字符和其
它字符）， 写算法来构造三个以循 表表示的 性表，
使每个表中只含同一 的字符，
且利用原表中的 点空 作 三个表的 点空 ， 点可另辟空 。
11.
性表 A=(a1, a2, ? ,am) ， B=(b1, b2, ? ,bn)
， 写一个按下列 合并
A、B
性表 C 的算法，使得：
C= (a1, b1, ? ,am, bm, bm+1,
? ,bn)
当 m≤ n ；
或者
C= (a1, b1, ? ,an, bn, an+1,
? ,am)
当 mn 。
性表 A、B、C均以 表作 存 构，
且 C表利用 A 表和 B 表中的 点空 构成。
注意：
表的 度 m和 n 均未 式存 。
12.
将一个用循 表表示的稀疏多 式分解成两个多 式，
使 两个多 式中各自 含
奇次 或偶次 ，并要求利用原 表中的 点空 来构成 两个 表。
13.
建立一个 点的 性 表，用以存放 入的二 制数， 表中每个 点的
data
域存放一个二 制位。并在此 表上 二 制数加
1的运算 。
14.
多 式 P(x) 采用 本中所述 接方法存 。写一算法， 定的
x ，求 P(x) 的
。
1．
将若干城市的信息存入一个 点的 表，
点中的城市信息包括城市名、
城市
的位置坐 。要求：
（1） 定一个城市名，返回其位置坐 ；
2） 定一个位置坐 P 和一个距离 D，返回所有与 P 的距离小于等于 D 的城市。
2． 瑟夫 。
瑟夫 的一种描述是： 号 1， 2，?， n 的 n 个人按
显示全部