历年链表考题及答案

历年链表考题及答案历年链表考题及答案 2005 秋秋 II 14 设已建立了两条单向链表 这两链表中的数据已按从小到大的次序排好 指针 h1 和 h2 分别指向这两条链表的首结点 链表上结点的数据结构如下 struct node int data node next 以下函数 node Merge node h1 node h2 的功能是将 h1 和 h2 指向的两条链表上的结 点合并为一条链表 使得合并后的新链表上的数据仍然按升序排列 并返回新链表的首结 点指针 算法提示 首先 使 newHead 和 q 都指向首结点数据较小链表的首结点 p 指向另一 链表首结点 其次 合并 p 和 q 所指向的两条链表 在 q 不是指向链尾结点的情况下 如 果 q 的下一个结点数据小于 p 指向的结点数据 则 q 指向下一个结点 否则使 p1 指向 q 的 下一个结点 将 p 指向的链表接到 q 所指向的结点之后 使 q 指向 p 所指向的结点 使 p 指向 p1 所指向的链表 直到 p 和 q 所指向的两条链表合并结束为止 注意 在合并链表的 过程中 始终只有两条链表 函数函数 4 分 分 node Merge node h1 node h2 node newHead p p1 使 newHead 和 q 指向首结点数据较小链表的首结点 p 指向另一链表首结点 if 27 newHead h1 p h2 h1 datadata else newHead h2 p h1 node q newHead 合并两条链表 while q next if q next data data 28 q q next else 29 p1 q next q next p q p p p1 q next p 30 return newNead 2005 春春 II 11 设已建立一条单向链表 指针 head 指向该链表的首结点 结点的数据结构 如下 struct Node int data Node next 以下函数 sort Node head 的功能是 将 head 所指向链表上各结点的数据按 data 值从 小到大的顺序排序 算法提示 初始时 使 p 指向链表的首结点 从 p 之后的所有结点中找出 data 值最小 的结点 让 p1 指向该结点 将 p 指向的结点的 data 值与 p1 指向的结点的 data 值进行交换 让 p 指向下一个结点 依此类推 直至 p 指向链表的最后一个结点为止 程序程序 4 分 分 Node sort Node head Node p head p1 p2 if p NULL return head while p next NULL p1 p p2 p next while p2 NULL if p2 data data p1 p2 p2 p2 next if p p1 int t t p data p data p1 data t p1 data p p next return head 2004 秋秋 II 11 已建立一条无序链表 head 指向链首 链表上结点的数据结构为 struct Node double num Node next 以下函数 sort Node head 的功能为 将参数 head 所指向链表上的各个结点 按 num 值的升序排序 并返回排序后链表的链首指针 算法提示 先让 h 指向空链 依次从 head 所指向的链表上取下一个结点 然后将取下 的结点插入到已排序的 h 所指向的链表上 Node sort Node head if head 0 return head Node h p h 0 while head p head 27 27 head head next 或 head p next Node p1 p2 if h 0 h p 28 28 p next 0 或 h next 0 else if 29 29 h num p num 或 p numnum p next h h p else p2 p1 h while p2 next p2 p2 next if 30 30 p2 num num 或 p num p2 num p2 next p p next 0 else p next p2 p1 next p return h 2004 春春 II 11 输入一行字符串 用单向链表统计该字符串中每个字符出现的次数 方法是 对该字符串中的每个字符 依次查找链表上的结点 若链表结点上有该字符 则将该结点 的 count 值加 1 否则产生一个新结点 存放该字符 置 count 为 1 并将该结点插入链首 最后 输出链表上的每个结点的字符及出现次数 链表的结构如下图所示 include struct node char c int count node next void print node head while head cout 字符 c t 出现 count next c count next c count next c count next c count next head void dele node head node p while head NULL p head head 27 27 head next delete p node search node head char ch node p p head while p if p c ch p count break 28 28 p p next if p 0 p new node p c ch p count 1 if head 29 29 p next head else p next 0 30 30 head p return head void main void char s 300 p s node h 0 char c cout 请输入一行字符串 cin getline s 300 while c p h search h c print h dele h 2003 秋秋 II 12 用链表实现对候选人的得票进行统计 函数 Statistic 的输入参数 head 指向 链首 name 存放候选人的姓名 该函数的功能为 若在链表的结点上找到 name 则将姓 名为 name 的结点上得得票数加 1 否则新建一个结点 初始化其姓名和的票数 并将新结 点插入链尾 最后返回链表的首指针 链表的结构如下图所示 name count next name count next name count next name count next head include include struct Node char name 12 候选人姓名 int count 计数候选人的得票 Node next Node Statistic Node head char name Node p1 head p2 if head 0 空表 插入第 1 个结点 head new Node strcpy head name name head count 1 head next 0 else 不是空表 进行结点数值查找 while p1 if 27 找到了 strcmp p1 name name 0 p1 count break else 不是待查结点 移动指针 准备下一结点查找 p2 p1 28 p1 p1 next if 29 待查结点不存在 p1 NULL p1 new Node 在尾部插入新结点 strcpy p1 name name p1 count 1 p1 next 0 30 p2 next p1 return head void List Node head 输出结果 while head cout name t count next void Free Node head 释放链表空间 Node p while head p head head head next delete p void main 连续输入得票候选人的姓名 以输入 0 结束 Node head 0 char name 12 cout name while strcmp name 0 0 head Statistic head name cout name cout 统计得票结果 n 姓名 得票数 n List head Free head 2003 春春 II 14 以下程序使用递归函数实现单向链表操作 完成链表的创建 显示 释放链 表的结点 include struct node float data node next void ShowChain node head 依次输出每一个结点上的数据 if head cout data next ShowChain head next void AddNode node p node p else AddNode p head next void DeleteChain node head 依次删除链表上的每一个结点 node p head if p head head next delete p if head DeleteChain head void main void node head NULL temp temp new node while 2 temp next NULL cout temp data if temp data 0 AddNode temp head 新结点加入链表尾部 else delete temp break temp new node ShowChain head DeleteChain head 2002 秋秋 II 14 n 个人围成一圈 他们的序号依次为 1 到 n 从第一个人开始顺序报数 1 2 3 m 报到 m 者退出圈子 并输出退出圈子的人的序号 接着再顺序报数 直到圈子中留下一个人为止 用一个有 n 个结点的环形链表模拟围成一圈的人 假定有 10 个人围成一圈 凡报到 5 者退出圈子 则退出圈子人的序号依次为 5 10 6 2 9 8 1 4 7 最后留在圈中的人是 3 号 单向环形链表的结构如下图所 示 其中 head 指向第一个人 include struct Node int x 围成一圈时 人的序号 Node next Node DelNode Node head int m 依次输出环形链表中凡报到 m 者的序号 Node p int count if head NULL return head while head head next 直到链表上只有一个结点为止 count 0 while countnext p head next 删除 p 所指向的结点 head next p next head head next cout x x 1 head next NULL p head for i 2 inext new Node 新结点加入链尾 p p next p x i p next 构成循环链 head head DelNode head 5 cout 最后的一个人为 x endl 2002 春春 II 14 设链表上结点的数据结构定义如下 struct NODE int x NODE next 函数 create 的功能为 创建一个有序的链表 结点中 x 的值按升序排序 参数 n 为 链表上要产生的结点的个数 函数返回该有序链表的头指针 算法思想 每产生一个新的 结点 插入到链表的恰当位置 使得插入新结点以后的链表仍然保持有序 creat int n NODE 或 struct NODE NODE p p1 p2 h NULL int i 0 if n 1 return NULL while i p x p next NULL if h p h NULL 或 h else p1 p2 h while p2 p2 p2 next if p2 h p next p2 h p else p next p2 p1 next p i return h 2001 秋秋 II 14 设链表上结点的数据结构定义如下 struct PNODE int x PNODE next 设已建立了一条链表 h 为链首指针 函数 DelAdd 的功能为 若链表上能找到结点的 x 值为 value 则从链表上删除该结点 假定链表上各个结点的值是不同的 否则构造一 个新结点 其 x 的值为 value 并将新结点插入链尾 该函数返回新链表的首指针 程序程序 4 分 分 PNODE DelAdd PNODE h int value PNODE p1 p2 int flag 0 值为 1 时 表示已删除值为 value 的结点 p1 h while p1 if p1 h h 27 delete p1 p1 next else p2 next 28 delete p1 p1 next else p2 p1 p1 29 p1 next if flag 0 p1 new PNODE p1 x value p1 next 0 if h 0 h p1 else 30 p2 next p1 return h 2001 春春 II 13 下面程序中 函数 padd 的功能为调整 pa 指向的链表中结点的位置 使得所 有 x 值为偶数的结点出现在链表的前半部 所有 x 值为奇数的结点出现在链表的后半部 如本程序的输出为 10 8 6 4 2 1 3 5 7 9 include struct NODE int x NODE next NODE padd NODE pa NODE p1 p2 p p1 p2 pa while p1 if p1 x 2 0 p1 p1 next p1 从链表上取下偶数结点并插入链首 p2 next p next pa pa p else p2 p1 p1 p1 next return pa void main void NODE a 10 1 2 3 4 5 6 7 8 9 10 ha a p int i for i 0 i 9 i a i next 拉成链表 ha padd ha p ha while p cout x next cout y pb y pt new 28 PNODE pt x pa x pb x pt y pa y pt next NULL if pc NULL pc pcr pt else pcr next pt 29 pcr pt pa pa next pb pb next else if 30 pb pb next pa y pb y else pa pa next return pc 05 级试卷级试卷 A 学生的记录由学号和成绩组成 设若干名学生的数据已在主函数中存放到链 表中 下列函数 fun 的功能是 用链表中高于或等于平均分的学生数据构成一个由头指针 h 所指向的新链表 建立新链表时每次都将新生成的结点插入到头结点的前面 形参 head 是链表头指针 平均分通过形参 aver 带回 函数返回新链表的头指针 h include include struct student char no 10 学号 float grade 成绩 student next student fun student head float float sum 0 int n 0 aver 0 p head while p NULL 求成绩和 sum sum p grade n p p next aver sum n h NULL p head while p NULL 用高于或等于平均分的学生数据构成一个新的链表 if p grade aver p1 new student strcpy p1 no p no p1 grade p grade p1 next h h p1 p p next return h 05 级试卷级试卷 B 以下用面向对象的方法实现一个单向链表 主要实现在链表尾追加一个结点 的功能 要求 1 定义一个结点类 Node 结构如上图所示 data 是一个整型数据 2 定义一个链表类 List 作为 Node 类的友元类 其私有数据成员 Node head 为指向链 表首结点的指针 各成员函数的功能见程序中的注释 请完善程序 include class Node int data Node next public Node int d 0 构造函数 data d next NULL 将 List 类说明成本类的友元类 friend class List class List Node head public List 缺省构造函数 建立一个空链表 head NULL List int d 构造一个第 1 个结点数据值为 d 的结点 void append int d 0 追加一个数据值为 d 的结点到链表尾部 void print 输出链表各结点值 List 析构函数 释放链表各结点空间 List List int d 构造一个第 1 个结点数据值为 d 的结点 head new Node d void List append int d 追加一个数据值为 d 的结点到链表尾部 if head NULL head new Node d else data next data next data NULL head List Node Node Node Node p head while 循环结束后 p 指向链表最后一个结点 p next NULL p p next p next new Node d void List print 输出链表各结点值 函数体略 List List 析构函数 释放链表各结点空间 Node p head while head NULL p head next delete head head p void main List list int d cout d while d 假定链表中的值为正数 假定以输入 0 结束 list a