内容发布更新时间 : 2024/12/23 8:26:57星期一 下面是文章的全部内容请认真阅读。
A.提高查找速度 B.更方便数据的插入和删除 C.节约存储空间 D.很快回收存储空间
(20) 与单链表相比,双链表的优点之一是( )。 A.插入和删除操作更简单 B.可以进行随机访问 C.可以省略表头指针或表尾指针 D.访问其后相邻结点更灵活
(21) 带头结点的循环双链表L为空表的条件是( )。 A.L->next->prior=NULL B.L->prior=L C.L->next=L D.B和C都对
(22) 在循环双链表的p所指结点后插入s所指结点的操作是( )。 A.p->next=s; s->prior=p; p->next->prior=s; s->next=p->next; B.p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C.s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D.s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
(23) 在双链表中指针pa所指结点后面插入pb所指结点,执行的语句序列是( )。 ①pb->next=pa->next; ②pb->prior=pa; ③pa->next=pb; ④pa->next->prior=pb; A.①②③④ B.④③②① C.③④①② D.①④③②
(24) 在一个双链表中,删除结点p的操作是( )。 A.p->prior->next=p->next; p->next->prior=p->prior; B.p->prior=p->prior->prior; p->prior->prior=p; C.p->next->prior=p; p->next=p->next->next;
D.p->next=p->prior->prior; p->prior=p->prior->prior;
应用题
(25) 单链表设置头结点的作用是什么?
(26) 线性表的顺序存储结构具有三个弱点:其一,插入或删除操作需要移动大量元
素;其二,由于难以估计,必须预先分配较大的空间,往往使存储空间不能得到充分利用;其三,表的容量难以扩充。试问,线性表的链接存储结构是否能够克服上述三个弱点?
(27) 若频繁地对一个线性表进行插入和删除操作,该线性表采用什么存储结构比较
好?
(28) 设n表示线性表中的元素个数,P表示指针所需的存储单元大小,E表示存储
数据元素所需的存储单元大小,则使用单链表存储方式存储该线性表需要多少存储空间(不考虑头结点)?
算法设计题
11
(29) 设计算法依次打印单链表中每个结点的数据信息。
(30) 求单链表的长度。
(31) 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前,
若找不到值为k的结点,则将x插入到链表的末尾。
(32) 判断非空单链表是否递增有序。
(33) 已知非空线性链表由list指出,结点结构为(data,link)。请编写算法,将链
表中数据域最小的结点移到链表的最前面。要求:不得额外申请新的结点。
(34) 给定一个带头结点的单链表,设head为头指针,设计算法按递增次序输出单
链表中各结点的数据元素,并释放结点所占的存储空间(要求:不允许使用数组作辅助空间)。
(35) 已知非空线性链表由list指出,设计算法交换p所指结点与其后续结点在链表中的位置(设p所指结点不是链表的最后一个结点)。
(36) 设计算法实现将单链表就地逆置。
(37) 头插法建立单链表。
(38) 尾插法建立单链表
(39) 复制一个单链表。
(40) 设计算法实现将单链表就地逆置。
(41) 在一个有序单链表(假设从小到大排列)中插入一个元素值为x的结点,使得插入后单链表仍然有序。
(42) 设单链表以非递减有序排列,设计算法实现在单链表中删去值相同的多余结
点。
(43) 已知单链表中各结点的元素值为整型且递增有序,设计算法删除表中大于
mink且小于maxk的所有元素,并释放被删结点的存储空间。
(44) 有两个整数序列A=(a1,a2,?,am)和B=(b1,b2,?,bn)已经存入两个单链
表中,设计算法判断序列B是否是序列A的子序列。
(45) 设线性表C=(a1,b1,a2,b2,?,an,bn)采用带头结点的单链表存储,设计算
法将表C拆分为两个线性表A和B,使得A=(a1,a2,?,an),B=(b1,b2,?,bn)。
12
(46) 有两个递增有序的单链表la和lb,设计算法将这两个单链表合并为一个有序
链表。
(47) 有两个有序的单链表,一个表为升序,另一个表为降序,设计算法将这两个链
表合并为一个有序链表。
(48) 已知单链表A和B的数据(设为整型)递增有序,设计算法利用原有结点,
将表A中与表B具有相同值的结点删除,将表B中与原表A不同值的结点存入表A中,并保持表A的递增有序。
(49) 设计算法将循环单链表就地逆置。
(50) 已知L为单链表的头结点地址,表中共有m(m>3)个结点,从表中第i个(1
<i<m)结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。
(51) 假设在长度大于1的循环单链表中,即无头结点也无头指针,s为指向链表中
某个结点的指针,试编写算法删除结点s的前驱结点。
(52) 设循环单链表L1,对其遍历的结果是:x1,x2,x3,?,xn-1,xn。请将该循
环链表拆成两个循环单链表L1和L2,使得L1中含有原L1表中序号为奇数的结点且遍历结果为:x1,x3,?;L2中含有原L1表中序号为偶数的结且遍历结果为:?,x4,x2。
(53) 已知一单链表中的数据元素含有三类字符:字母、数字和其他字符。试编写算
法,构造三个循环单链表,使每个循环链表中只含同一类字符。
(54) 有两个循环链表tail1和tail2(tail1和tail2分别指向循环链表的尾指针),编
写算法将循环链表tail2链接到循环链表tail1之后,并使链接后的链表仍是循环链表。
(55) 已知p指向循环单链表最后一个结点的指针,试编写只包含一个循环的算法,
将线性表(a1,a2,?,an-1,an,)改造成(a1,a2,?,an-1,an,an-1,?,a2,a1)。
(56) 判断带头结点的循环双链表是否对称。
(57) 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。
(58) 已知非空循环双链表head的存储结构为: Struct DNode { TElem info; Struct DNode *left; Struct DNode *right;
13
};
设计算法实现从链表中删除指针p所指结点的前驱结点(假设该结点存在)。
(59) 已知非空双链表由d指出,结点结构为(priordatanext),请设计算法将链表中
数据值最大(假定唯一)的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。
(60) 设计算法实现将双链表中结点p与其后继结点互换位置。
(61) 设有一个双链表,每个结点中除了有prior、data和next三个域外,还有一个
访问频度域freq,在链表被起用之前,其值均初始化为零,每当在双链表上进行一次LOCATE运算时,令元素值为x的结点中freq域的值增1,并使此链表中结点保持频度递减的顺序排列,以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。
14
5 静态链表
选择题
(1) 静态链表中指针表示的是( )。 A.下一结点在内存中的地址 B.下一元素在数组中的下标 C.左、右孩子的存储位置 D.左、右孩子的地址
(2) 以下说法错误的是( )。
①静态链表既有顺序存储的优点又有动态链表的优点。所以,它存取表中第i个元素的时间与i无关
②静态链表中能容纳的元素个数在定义表时必须是确定的
③静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动 A.①,② B.① C.①,②,③ D.②
(3) 用数组r存储静态链表,结点的next域指向后继,工作指针j指向链中某结点,
使j沿链移动的操作为( )。 A.j=r[j].next B.j=j+1 C.j=j->next D.j=r[j]->next
(4) 线性表的静态链表存储与顺序存储相比,优点是( )。 A.所有基本操作的算法实现简单 B.便于随机存取 C.便于插入和删除 D.便于利用零散的存储空间
(5) 下图所示数组中以静态链表形式存储了一个线性表,设头指针为a[0].link,则
该线性表的元素依次为( )。
下标 0 1 2 3 4 5 6 7 8
data link
4 60 63 40 45 3 7 6 2 74 25 0 1 A.60,63,40,45,74,25 C.74,25,45,60,40,63
B.45,63,25,60,40,74 D.25,45,60,40,63,74
15