《数据结构(第二版)习题答案第3章》由会员分享，可在线阅读，更多相关《数据结构(第二版)习题答案第3章（11页珍藏版）》请在金锄头文库上搜索。
1、3 1 选择题 第 3 章 线性表的链式存储 1 两个有序线性表分别具有n 个元素与m 个元素且n m 现将其归并成一个有序表 其最少的比较次数是 A A nB mC n 1D m n 2 非空的循环单链表head 的尾结点 由p 所指向 满足 C A p next NULL B p NULL C p next head D p head 3 在带头结点的单链表中查找x 应选择的程序体是 C A node p head next while p if p info x return p else return NULL B node p head while p return p C node
2、 p head next while p return p D node p head while p info x p p next return p 4 线性表若采用链式存储结构时 要求存中可用存储单元的地址 D A 必须是连续的 C 一定是不连续的 B 部分地址必须是连续的 D 连续不连续都可以 5 在一个具有n 个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间 复杂度是 B A O 1 B O n C O n 2 D O nlog2n 6 用不带头结点的单链表存储队列时 其队头指针指向队头结点 其队尾指针指向队 尾结点 则在进行删除操作时 D A 仅修改队头指针 C 队头
3、队尾指针都要修改 B 仅修改队尾指针 D 队头 队尾指针都可能要修改 7 若从键盘输入n 个元素 则建立一个有序单向链表的时间复杂度为 B A O n B O n 2 C O n 3 D O n log2 n 8 下面哪个术语与数据的存储结构无关 D A 顺序表B 链表C 散列表 D 队列 9 在一个单链表中 若删除p 所指结点的后续结点 则执行 A A p next p next next B p p next p next p next next C p next p next D p p next next 10 在一个单链表中 若p 所指结点不是最后结点 在p 之后插入s 所指结点 则
4、执行 B A s next p p next s B s next p next p next s C s next p next p s D p next s s next p 3 2 设计一个算法 求一个单链表中的结点个数 答 单链表存储结构定义如下 相关文件 linklist h include 11 include typedef struct node int data struct node next linknode typedef linknode linklist 尾插法创建带头结点的单链表 linklist creatlinklist linklist head r x s
5、 head r linklist malloc sizeof linknode printf n 请输入一组以0 结束的整数序列 n scanf d while x s linklist malloc sizeof linknode s data x r next s r s scanf d r next NULL return head 输出带头结点的单链表 void print linklist head linklist p p head next printf List is n while p printf 5d p data p p next printf n 基于上述结构定义 求
6、单链表中的结点个数的算法程序如下 int count linklist head int c 0 linklist p head while p c 12 p p next return c 3 3 设计一个算法 求一个带头结点单链表中的结点个数 答 带头结点的单链表的存储结构定义同题3 2 实现本题功能的算法程序如下 3 3 c include linklist h int count linklist head int c 0 linklist p head next while p c p p next return c main 测试函数 linklist head head crea
7、tlinklist print head printf nLength of head is d count head getch 当输入5 个数据时 产生的输出结果如下图所示 3 4 设计一个算法 在一个单链表中值为y 的结点前面插入一个值为x 的结点 即使值为x 的 新结点成为值为y 的结点的前驱结点 答 include linklist h void insert linklist head int y int x 在值为y 的结点前插入一个值为x 的结点 linklist pre p s pre head p head next 13 while p p p next if p 找到了
8、值为y 的结点 s linklist malloc sizeof linknode s data x s next p pre next s void main linklist head int y x 测试程序 head creatlinklist 创建单链表 print head 输出单链表 printf n 请输入y 与 x 的值 n scanf d d insert head y x print head 程序的一种运行结果如下图所示 3 5 设计一个算法 判断一个单链表中各个结点值是否有序 答 include linklist h int issorted linklist hea
9、d char c 当参数c a 时判断链表是否为升序 当参数c d 是判断链表是否为降序 int flag 1 linklist p head next switch c case a 判断带头结点的单链表head 是否为升序 14 while p else flag 0 break case d 判断带头结点的单链表head 是否为降序 while p else flag 0 break return flag int main 测试程序 linklist head head creatlinklist print head if issorted head a printf 单链表head
10、 是升序排列的 n else if issorted head d printf 单链表head 是降序排列的 n else printf 单链表head 是无序的 n 程序运行时的三种输出结果如下图所示 3 6 设计一个算法 利用单链表原来的结点空间将一个单链表就地转置 答 include linklist h void verge linklist head 本函数的功能是就地倒置带头结点的单链表 15 linklist p q p head next head next NULL while p q p p p next 每次从原表取一个结点插入到新表的最前面 q next head n
11、ext head next q int main linklist head 测试函数 head creatlinklist 创建单链表 print head 输出原单链表 verge head 就地倒置单链表 print head 输出倒置后的单链表 3 7 设计一个算法 将一个结点值自然数的单链表拆分为两个单链表 原表中保留值为偶数的 结点 而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表 答 include linklist h linklist sprit linklist head 将带头结点的单链表head 中的奇数值结点删除生成新的单链表并返回 linklist L p
12、re p r L r linklist malloc sizeof linknode r next NULL pre head p head next while p if p data 2 1 pre next p next r next p r p p pre next else pre p p p next 删除奇数值结点 保留偶数值结点 16 r next NULL return L 置链表结束标记 int main linklist head L 测试函数 head creatlinklist 创建单链表 print head 输出原单链表 L sprit head 分裂单链表hea
13、d printf n 原单链表为 n print head 输出倒置后的单链表 printf n 分裂所得奇数单链表为 n print L 本程序的一组测试情况如下图所示 3 8 设计一个算法 对一个有序的单链表 删除所有值大于x 而不大于y 的结点 答 include linklist h void deletedata linklist head datatype x datatype y 删除带头结点单链表中所有结点值大于x 而不大于y 的结点 linklist pre head p q p head next 初始化 while p while p q pre next pre nex
14、t p pre q next 删除大于x 而小于y 的结点 17 while pre p free q q pre pre pre next 释放被删除结点所占用的空间 void main linklist head L datatypex y 测试函数 head creatlinklist 创建单链表 print head 输出原单链表 printf n 请输入要删除的数据区间 n scanf d d deletedata head x y print head 输出删除后的单链表 3 9 设计一个算法 在双链表中值为y 的结点前面插入一个值为x 的新结点 即使值为x 的新 结点成为值为y
15、的结点的前驱结点 答 首先定义双链表的数据结构 相关文件dlink h 容如下 typedef int datatype 预定义的数据类型 typedef struct dlink node 双链表结点定义 datatype data struct dlink node llink rlink dnode typedef dnode dlinklist 双链表结点指针类型定义 尾插法创建带头结点的双链表 dlinklist creatdlinklist void dlinklist head r s datatype x head r dlinklist malloc sizeof dnode
16、 建立双链表的头结点 head llink head rlink NULL printf n 请输入双链表的容 整数序列 以0 结束 n scanf d while x 输入结点值信息 以0 结束 s dlinklist malloc sizeof dnode s data x s rlink r rlink 将新结点s 插入到双链表链尾 18 s llink r r rlink s r s scanf d return head 输出双链表的容 void print dlinklist head dlinklist p p head rlink printf n 双链表的容是 n while p printf 5d p data p p rlink 本题的求解程序如下 include include dlink h void insertxaty dlinklist head datatype y datatype x dlinklist s p 首先在双链表中找y 所在的结点 然后在y 前面插入新结点 p head rlink while p if p printf n 双链表中不
