《一基础知识题》PPT课件.ppt

一 基础知识题 2 2填空题 1 在顺序表中插入或删除一个元素 需要平均移动表中一半元素 具体移动的元素个数与表长和该元素在表中的位置有关 2 顺序表种逻辑上相邻的元素的物理位置必定紧邻 单链表种逻辑上相邻的元素的物理位置不一定紧邻 3 在单链表种 除了首元结点外 任一结点的存储位置由其直接前驱结点的链域的值指示 4 在单链表种设置头结点的作用是插入合删除首元素时不必进行特殊处理 2 6已知L是无表头结点的单链表 且P结点既不是首元结点 也不是尾元结点 试从下列提供的答案中选择合适的语句序列 a 在P结点后插入S结点的语句序列是 4 1 b 在P结点前插入S结点的语句序列是 7 11 8 4 1 c 在表首插入S结点的语句序列是 5 12 d 在表尾插入S结点的语句序列是 11 9 1 6 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 2 7已知L是带表头结点的非空单链表 且P结点既不是首元结点 也不是尾元结点 试从下列提供的答案中选择合适的语句序列 a 删除P结点的直接后继结点的语句序列是 11 3 14 b 删除P结点的直接前驱结点的语句序列是 10 12 8 11 3 14 c 删除P结点的语句序列是10 12 7 3 14 d 删除首元结点的语句序列是 12 11 3 14 e 删除尾元结点的语句序列是 12 9 11 3 14 1 P P next 2 P next P 3 P next P next next 4 P P next next 5 while P NULL P P next 6 while Q next NULL P Q Q Q next 7 while P next Q P P next 8 while P next next Q P P next 9 while P next next NULL P P next 10 Q P 11 Q P next 12 P L 13 L L next 14 free Q 简述以下算法的功能 StatusA LinkedListL L是无表头的单链表 if LQ next null returnok 解答 如果链表为空或只有一个结点就不做处理 否则 把链表中的第2个结点变成头结点 而把表中第1结点放置到链表尾部作为尾结点 简述以下算法的功能 voidBB LNode s LNode q p s while p next q p p next p next s BBvoidAA LNode pa LNode pb pa和pb分别指向单循环链表中的两个结点BB pa pb BB pb pa AA此算法的功能为 解答 首先你清楚什么是循环链表吧 比如说一根绳子 收尾连在一起 就是一个圆圈了 这个圆圈上有两个点 一个s 一个q 然后用剪刀在q点之前剪断 剪断后再连接到s点 自己想象一下这跟绳子变成什么效果了 是不是好像蝌蚪形状了 这个就是AA里面的第一个BB函数的功能 AA里面的第二个BB函数功能 就是将蝌蚪的尾巴截断 再绕成一个圈 于是就变成两个圈了 也就是两个循环链表 所以 AA的功能就是将一个循环链表变成两个循环链表 BB的功能就是将链表中的节点截断并形成一个新的小的循环链表 2 11设顺序表va中的数据元素递增有序 试写一算法 将x插入到顺序表的适当位置上 以保持该表的有效性 2 19已知线性表中的元素以值递增有序 并以单链表作存储结构 试写一高效的算法 删除有序表中所有其值大于mink且小于maxk的数据元素 2 21试写一算法 实现顺序表的就地逆置 即利用原表的存储空间将线性表 a1 a2 an 逆置为 an an 1 a1 2 22试写一算法 对单链表进行就地逆置 2 41试以循环链表作为稀疏多项式的存储结构 编写求其导函数的算法 要求利用原多项式中的结点空间存放其导函数 多项式 同时释放所有无用 被删 的结点 本章算法设计涉及的顺序表和线形链表的类型定义如下 defineLIST INIT SIZE100 defineLISTCREMENT10typedefstruct ElemType elem 存储空间基址intlength 当前长度intlistsize 当前分配的存储容量 SqList 顺序表类型 typedefstructLnode ElemTypedata structLnode next LNode LinkList 线性链表类型 StatusInsert Sq SqList Insert Sq 题2 11 返回 题2 19 删除有序表中所有其值大于mink且小于maxk的数据元素 首先分析需要删除的结点的特点 mink maxk pre q p 修改指针 pre next p 释放结点 while q p s q next free q q s voiddelete LinkList L intmink intmaxk delete while p 查找第一个值 mink的结点 if p if q pre next pre next p 修改指针 while q p s q next deleteq q s 释放结点空间 p L next while p 查找第一个值 maxk的结点 返回 2 21顺序表的就地逆置 voidreverse SqList reverse 题2 22 逆置线性链表 a1 a2 a3 L p a1 a2 a3 基本操作 1 标志后继结点 2 修改指针 将 p插入在头结点之后 3 重置结点 p p重新指向原表中后继 voidinverse LinkList 返回 题2 41 voidDifference L LinkedPolypa pa为指向稀疏多项式循环链表的头指针 本算法将链表改变为该多项式的导函数p pa nex