1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 3 及答案解析(总分：98.00，做题时间：90 分钟)一、单项选择题(总题数：28，分数：56.00)1.线性表是具有 n 个_的有限序列(n0)。【清华大学 1998 年】（分数：2.00）A.表元素B.字符C.数据元素D.数据项2.一个顺序表所占用的存储空间大小与无关。【北京航空航天大学 2004 年】（分数：2.00）A.表的长度B.元素的存放顺序C.元素的类型D.元素中各字段的类型3.线性表的顺序存储结构是一种_。【北京理工大学 2006 年】（分数：2.00）A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.
2、Hash 存取的存储结构4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。【青岛大学 2000 年】（分数：2.00）A.0(n)0(n)B.0(n)0(1)C.0(1)0(n)D.0(1)0(1)5.若长度为 n 的非空线性表采用顺序存储结构，删除表的第 i 个数据元素，首先需要移动表中个数据元素。【北京航空航天大学 2004 年】（分数：2.00）A.n-iB.n+iC.n-i+1D.n-i-16.对顺序存储的线性表，设其长度为 n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的_个元素。【华中科技大学 2007 年】（分数：2.00）A.n2B.(
3、n+1)2C.(n 一 1)2D.n7.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_。(1in+1)【北京航空航天大学 1999 年】（分数：2.00）A.0(0)B.0(1)C.0(n)D.0(n)8.线性表中各链接点之间的地址_。【北京航空航天大学 2002 年】（分数：2.00）A.必须连续B.部分地址必须连续C.不一定连续D.连续与否无所谓9.在 n 个结点的线性表的数组表示中，算法的时间复杂度是 0(1)的操作是_。【哈尔滨工业大学 2003年】（分数：2.00）A.访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)B
4、.在第 i 个结点后插入一个新结点(1in)C.删除第 i 个结点(1in)D.以上都不对10.单链表中，增加一个头结点的目的是为了_。【江苏大学 2005 年】（分数：2.00）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储11.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是_。【北京工商大学 2001年】（分数：2.00）A.head=NULLB.head-next=NULLC.head 一next=headD.headl=NULL12.将长度为 n 的单链表链接在长度为 m 的单链表后面的算法的时间复杂度采
5、用大 0 形式表示应该是_。【北京航空航天大学 2007 年】（分数：2.00）A.0(1)B.0(n)C.0(m)D.0(n+m)13.静态链表中指针表示的是_。【中南大学 2003 年】（分数：2.00）A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址14.非空的循环单链表 head 的尾结点 p 满足_。【武汉大学 2000 年】（分数：2.00）A.p-link。headB.p-link=NULLC.p=NULLD.p=head15.某线性表用带头结点的循环单链表存储，头指针为 head，当 head-next-next=head 成立时，线
6、性表长度可能是_。【华中科技大学 2007 年】（分数：2.00）A.0B.1C.2D.316.在什么情况下，应使用链式结构存储线性表 L?_。【北京交通大学 2006 年】（分数：2.00）A.需经常修改 L 中的结点值B.需不断对 L 进行删除插入C.需要经常查询 L 中结点值D.L 中结点结构复杂17.与单链表相比较，双向链表的优点之一是_。【北京航空航天大学 2005 年】（分数：2.00）A.可以省略头结点指针B.可以进行随机访问C.插入、删除操作更简单D.顺序访问相邻结点更灵活18.某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用_作为存储结构，能使其存储
7、效率和时间效率最高。【华中科技大学 2007 年】（分数：2.00）A.单链表B.仅用头指针的循环单链表C.双向循环链表D.仅用尾指针的循环单链表19.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用_存储方式最节省运算时间。【北京理工大学 2000 年】（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表20.对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够反映数据之间的逻辑关系，则应用_。【浙江大学 2004 年】【哈尔滨工业大学 2005 年】（分数：2.00）A.顺序方式存储B.散列方式存储C.链接方式存储D.以上方式
8、均可21.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。【哈尔滨工业大学 2001 年】（分数：2.00）A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表22.若线性表最常用的操作是存取第 i 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为_。【北京理工大学 2004 年】（分数：2.00）A.单链表B.双向链表C.单循环链表D.顺序表23.下面哪一条是顺序存储结构的优点?_。【江苏大学 2006 年】（分数：2.00）A.插入运算方便B.可方便地用于各种逻辑结构的存储表示C.存储密度大D.删除运算方便24.下面关于线
9、性表的叙述中，错误的是_。【北方交通大学 2001 年】（分数：2.00）A.线性表采用顺序存储，必须占用一批连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。25.在非空线性链表中由 p 所指的链接点后面插入一个由 q 所指的链接点的过程是依次执行动作。【北京航空航天大学 2002 年】（分数：2.00）A.q-link=p；p-link=q：B.q-link=p-link：p。link=q;C.q-link=p-link；p=q；D.p 一link=q;q-link=p26.在非空
10、双向循环链表中由 q 所指的链接点前面插入一个由 p 指的链接点的过程是依次执行语句prlink=q：p-llink=qllinkq-llink=p；_。【北京航空航天大学 2007 年】（分数：2.00）A.q-rlink-llink=p；B.q-llink-rlink=pC.p-rlink-llink=p；D.p-Uink-rlink=p；27.在非空双向循环链表中由 q 所指的链接点后面插入一个由 p 指的链接点的动作依次为_。【北京航空航天大学 2005 年】（分数：2.00）A.p-llink=q；p-rlink=q-rlink；q-rlink=p；q-rlink-llink=p：B
11、.p-rlink=q-rlink;p-Uink=q；q-rlink=p；q-rlink-llink=pC.p-llink=q；p-rlink=q-rlink；q-rlink=p；p-llink-rlink=pD.p-llink=q；p-rlink=q-rlink；q-rlink=p;p-rlink-llink=p；28.在双向链表存储结构中，删除 p 所指的结点时须修改指针_。【西安电子科技大学 1998 年】（分数：2.00）A.p-llink-rlink=p-rlink;p-rlink-llink=p-llink;B.p-llink=p-llink 一llink;p-llink-dink=
12、p;C.p-rlink-llink=pp-rlink=p-rlink-rlinktD.p-rlink=p-llink-llink;p-llink=p-rlink-rlink；二、综合题(总题数：21，分数：42.00)29.利用顺序表的操作，实现以下函数：1)从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第 i个元素并由函数返回被删除元素的值。如果 j 不合理或顺序表为空则显示出错信息并退出运行。3)向顺序表中第 i 个位置插入一个新的元素 x。如果 i 不合理则显示出错信息并退出运行。4)从顺序
13、表中删除具有给定值 x 的所有元素。5)从顺序表删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素。如果 s 或 t不合理或者顺序表为空，则显示错误信息并退出。6)从有序顺序表中删除其值在给定值 s 与 t 之间(要求s 小于 t)的所有元素。如果 s 或 t 不合理或顺序表为空，则显示错误信息并退出。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。（分数：2.00）_30.请设计算法将不带头结点的单链表就地逆置。【北京交通大学 2001 年】（分数：2.00）_31.有一个单链表 L(至少
14、有 1 个结点)，其头结点指针为 head，编写一个过程将 L 逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学 2001 年】（分数：2.00）_32.设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3)若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 年】（分数：2.00）_33.给定(已生成)一个带表头结点的单链表，设 head 为头指针，结点的结构为(data，next)，data 为整型元素，next 为指针，试写出算法：按递增
15、次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。【华中科技大学 2000 年】（分数：2.00）_34.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学 1998 年】（分数：2.00）_35.在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10，10，21，30，42，42，42，51，70)将变为(7，10，21，30，42，5
16、1，70)。【北京工业大学 1996 年】（分数：2.00）_36.试编写在带头结点的单链表中删除一个最小值结点的高效算法：voiddelete(Linklist NODE*dlf ference(NOI)E*A，N0 L)E*B) （分数：2.00）_42.设一单向链表的头指针为 head，链表的记录中包含着整数类型的 key 域，试设计算法，将此链表的记录按照 key 递增的次序进行就地排序。【中科院计算所 1999 年】（分数：2.00）_43.设计算法将一个带头结点的单链表 A 分解为两个具有相同结构的链表 B、C，其中 B 表的结点为 A 表中值小于零的结点，而 C 表的结点为 A
17、表中值大于等于零的结点(链表 A 的元素类型为整型，要求 B、C 表利用 A 表的结点)。【北京理工大学 2000 年】（分数：2.00）_44.将一个带头结点的单链表 A 分解为两个带头结点的单链表 A 和 B，使得 A 表中含有原表中序号为奇数的元素，而 B 表中含有原表中序号为偶数的元素，且保持其相对顺序不变。1)写出其类型定义。2)写出算法。【山东工业大学 2000 年】（分数：2.00）_45.两个整数序列 A=a 1 ,a 2 ，a 3 ，a n 和 B=b 1 ，b 2 ,b 3 ，b n 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。【东北大学 1
18、999 年】（分数：2.00）_46.已知线性表(a 1 ，a 2 ，a 3 ，a n )按顺序存于内存，每个元素都是整数，试设计用最少时间把所有值为负数的元素移到全部正数值(假设 0 为正数)元素前边的算法。例如：(x，一 x，一 x，x，x，一x，x)变为(一 x，一 x，一 x，x，x，x)。【东北大学 1998 年】（分数：2.00）_47.一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域 coef，指数域 exp 和指针域 next。现对链表求一阶导数，链表的头指针为 ha，头结点的 exp 域为一 1。【南京理工大学 2000 年】（分数：2.00）_48.设用带头结点的
19、双向循环链表表示的线性表为 L=(a 1 ，a 2 ，a n )。写出算法将 L 改造成：L=(a 1 ，a 3 ，a n ，a 4 ，a 2 )。【华中科技大学 2007 年】结点和结点指针类型定义如下：typedefstrUCtnodeElemTypedata；strLICtnode*prior，next；*DLinkList；（分数：2.00）_49.设有一头指针为 L 的带有表头结点的非循环双向链表，其每个结点中除有 pred(前驱指针)、data(数据)和 next(后继指针)域外，还有一个访问频度域 freq。在链表被起用前，其值均初始化为零。每当在链表中进行一次 Loga,te(
20、L，x)运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持按访问频度非增(递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的 Locate(L，x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。【清华大学 1997 年】（分数：2.00）_计算机专业基础综合数据结构（线性表）历年真题试卷汇编 3 答案解析(总分：98.00，做题时间：90 分钟)一、单项选择题(总题数：28，分数：56.00)1.线性表是具有 n 个_的有限序列(n0)。【清华大学 1998 年】（分数：2.00）A
21、.表元素B.字符C.数据元素 D.数据项解析：解析：考查线性表的概念。线性表是由 n 个数据元素组成的有序序列。2.一个顺序表所占用的存储空间大小与无关。【北京航空航天大学 2004 年】（分数：2.00）A.表的长度B.元素的存放顺序 C.元素的类型D.元素中各字段的类型解析：解析：考查顺序表的相关概念。顺序表是线性表的数组存储表示，一占用的存储空间大小与元素存放顺序无关。3.线性表的顺序存储结构是一种_。【北京理工大学 2006 年】（分数：2.00）A.随机存取的存储结构 B.顺序存取的存储结构C.索引存取的存储结构D.Hash 存取的存储结构解析：解析：考查顺序表的存储结构。应该注意到
22、顺序存储和顺序存取的不同。顺序表既可以随机存取，也可以顺序存取，但顺序表的特点只能是随机存取。随机存取是指可以通过数组下标存取任意位置的元素。4.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为_。【青岛大学 2000 年】（分数：2.00）A.0(n)0(n)B.0(n)0(1)C.0(1)0(n) D.0(1)0(1)解析：解析：考查顺序表的基本操作。顺序存储可以随机访问结点，但是增加、删除结点的效率较低。5.若长度为 n 的非空线性表采用顺序存储结构，删除表的第 i 个数据元素，首先需要移动表中个数据元素。【北京航空航天大学 2004 年】（分数：2.00）A.n-i B.n
23、+iC.n-i+1D.n-i-1解析：解析：考查顺序表的删除操作。删除第 i 个元素，需将其后的 ni 个元素顺序前移。6.对顺序存储的线性表，设其长度为 n，在任何位置插入或删除操作都是等概率的。删除一个元素时平均要移动表中的_个元素。【华中科技大学 2007 年】（分数：2.00）A.n2B.(n+1)2C.(n 一 1)2 D.n解析：解析：考查顺序表的删除操作。对顺序表进行删除操作时要将删除位置后的所有元素前移。对此题来说，删除每个元素的概率均为 ln，从第一个元素开始，删除时所要移动的元素个数分别为 n 一 1，n一 2，n 一 3，1，0 所以删除一个元素时平均要移动表中的(0 十
24、 1+2+n 一 1)n=(n1)2 个元素。7.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为_。(1in+1)【北京航空航天大学 1999 年】（分数：2.00）A.0(0)B.0(1)C.0(n) D.0(n)解析：解析：考查线性表的插入操作。8.线性表中各链接点之间的地址_。【北京航空航天大学 2002 年】（分数：2.00）A.必须连续B.部分地址必须连续C.不一定连续 D.连续与否无所谓解析：解析：考查线性表两种存储结构的比较。线性表的顺序存储要求存储在地址连续的存储单元中。链式存储结构的结点地址可以不用连续。所以 c 正确。D 不正确
25、是因为不能说连续与否无所谓，因为顺序存储必须是连续的。9.在 n 个结点的线性表的数组表示中，算法的时间复杂度是 0(1)的操作是_。【哈尔滨工业大学 2003年】（分数：2.00）A.访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in) B.在第 i 个结点后插入一个新结点(1in)C.删除第 i 个结点(1in)D.以上都不对解析：解析：考查顺序表的各种操作。线性表用数组表示，即顺序存储。顺序存储可以方便地访问第 i 个结点。10.单链表中，增加一个头结点的目的是为了_。【江苏大学 2005 年】（分数：2.00）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便
26、运算的实现 D.说明单链表是线性表的链式存储解析：解析：考查单链表的头结点。如果没有头结点，对于插入、删除等操作需要使用不同的代码。增加头结点之后，可以用相同的操作方法实现插入和删除。11.对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是_。【北京工商大学 2001年】（分数：2.00）A.head=NULLB.head-next=NULL C.head 一next=headD.headl=NULL解析：解析：考查单链表的特点。注意 C 为循环链表为空的条件。12.将长度为 n 的单链表链接在长度为 m 的单链表后面的算法的时间复杂度采用大 0 形式表示应该是_。【北京航
27、空航天大学 2007 年】（分数：2.00）A.0(1)B.0(n)C.0(m) D.0(n+m)解析：解析：考查单链表的链接。两个单链表的链接，需要将第一个单链表的尾结点指向第二个单链表的第一个结点。找到第一个链表的尾结点的时间与第一个链表的长度 m 成正比，所以算法时间复杂度为 0(m)。13.静态链表中指针表示的是_。【中南大学 2003 年】（分数：2.00）A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置 D.左链或右链指向的元素的地址解析：解析：考查静态链表的概念。静态链表中的指针所存储的不再是链表中的指针域，而是其下一结点在一维数组中的位置其实就是数组下标。14.非
28、空的循环单链表 head 的尾结点 p 满足_。【武汉大学 2000 年】（分数：2.00）A.p-link。head B.p-link=NULLC.p=NULLD.p=head解析：解析：考查循环单链表的特点。尾结点指针应该指向链表头。15.某线性表用带头结点的循环单链表存储，头指针为 head，当 head-next-next=head 成立时，线性表长度可能是_。【华中科技大学 2007 年】（分数：2.00）A.0B.1 C.2D.3解析：解析：考查循环单链表的特点。通过画图可以很清晰地看到，head-next 指向头指针后一个结点，head-next-next 指向 head，所以总
29、共有两个结点。头结点不存储线性表元素，所以线性表长度为 1。16.在什么情况下，应使用链式结构存储线性表 L?_。【北京交通大学 2006 年】（分数：2.00）A.需经常修改 L 中的结点值B.需不断对 L 进行删除插入 C.需要经常查询 L 中结点值D.L 中结点结构复杂解析：解析：考查链式结构的特点。链式结构与顺序结构相比可以方便地对线性表进行插入、删除操作。17.与单链表相比较，双向链表的优点之一是_。【北京航空航天大学 2005 年】（分数：2.00）A.可以省略头结点指针B.可以进行随机访问C.插入、删除操作更简单D.顺序访问相邻结点更灵活 解析：解析：考查双向链表的特点。A 不对
30、，双向链表也可以有头指针。B 是顺序存储的特点。C 与单链表相比，双向链表增加了指针数量，使得插入、删除操作更麻烦。D 正确，因为双向链表即可以访问前驱结点，也可以访问后继结点。18.某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用_作为存储结构，能使其存储效率和时间效率最高。【华中科技大学 2007 年】（分数：2.00）A.单链表B.仅用头指针的循环单链表C.双向循环链表D.仅用尾指针的循环单链表 解析：解析：考查链式存储的各种实现。首先看题意，要方便删除第一个数据元素，必须要能方便获取指向头结点的指针；要在最后一个元素后添加新元素，则要有一个指向尾结点的指针。单
31、链表显然不行，最后结点后添加新结点需要遍历线性表，效率太低。仅用头指针的循环单链表在获取尾指针时也需要遍历。双向循环链表的存储效率太低。仅用尾指针的循环单链表，可以很方便地获得头指针，满足两个条件。19.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用_存储方式最节省运算时间。【北京理工大学 2000 年】（分数：2.00）A.单链表B.双链表C.单循环链表D.带头结点的双循环链表 解析：解析：考查链式存储的各种实现。A、B、C 都需要遍历才能得到尾结点的指针。D 可以通过头结点方便地得到尾结点。20.对于一个线性表既要求能够进行较快的插入和删除，又要求存储结构能够
32、反映数据之间的逻辑关系，则应用_。【浙江大学 2004 年】【哈尔滨工业大学 2005 年】（分数：2.00）A.顺序方式存储B.散列方式存储C.链接方式存储 D.以上方式均可解析：解析：考查链式存储的各种实现。要想能够反映数据之间的逻辑关系，必须是线性表，而又要求能够进行较快地插入和删除，则应该选择链接方式存储。21.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。【哈尔滨工业大学 2001 年】（分数：2.00）A.顺序表 B.双链表C.带头结点的双循环链表D.单循环链表解析：解析：考查线性表两种存储的特点。本题较易出错，存取任一指定序号
33、的元素，很显然应该是顺序表。顺序表不方便进行插入和删除操作，不过本题只要求在最后进行插入和删除，顺序表完全满足要求。所以应选择顺序表。22.若线性表最常用的操作是存取第 i 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式为_。【北京理工大学 2004 年】（分数：2.00）A.单链表B.双向链表C.单循环链表D.顺序表 解析：解析：考查线性表各种存储方式的特点。随机存取第 i 个元素最快捷的方式是采用顺序存储，而且，顺序表中元素存储地址相邻，可以方便地存取其前驱和后继元素。23.下面哪一条是顺序存储结构的优点?_。【江苏大学 2006 年】（分数：2.00）A.插入运算方便B.可方便
34、地用于各种逻辑结构的存储表示C.存储密度大 D.删除运算方便解析：解析：考查两种存储结构的特点。A 和 D 属于链式结构的优点，B 属于线性表的优点。24.下面关于线性表的叙述中，错误的是_。【北方交通大学 2001 年】（分数：2.00）A.线性表采用顺序存储，必须占用一批连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。 C.线性表采用链接存储，不必占用一片连续的存储单元。D.线性表采用链接存储，便于插入和删除操作。解析：解析：考查线性表两种存储结构的特点。顺序存储占用连续单元，插入和删除需要移动大量数据，所以不利于插入和删除操作。25.在非空线性链表中由 p 所指的链接点后
35、面插入一个由 q 所指的链接点的过程是依次执行动作。【北京航空航天大学 2002 年】（分数：2.00）A.q-link=p；p-link=q：B.q-link=p-link：p。link=q; C.q-link=p-link；p=q；D.p 一link=q;q-link=p解析：解析：考查单链表的插入操作。26.在非空双向循环链表中由 q 所指的链接点前面插入一个由 p 指的链接点的过程是依次执行语句prlink=q：p-llink=qllinkq-llink=p；_。【北京航空航天大学 2007 年】（分数：2.00）A.q-rlink-llink=p；B.q-llink-rlink=pC
36、.p-rlink-llink=p；D.p-Uink-rlink=p； 解析：解析：考查双向链表的插入操作。执行完以上三步之后，只需要再将原线性表前面结点的 rlink 指向 p 即可。所以题目答案为 p-llink-rlink=p。27.在非空双向循环链表中由 q 所指的链接点后面插入一个由 p 指的链接点的动作依次为_。【北京航空航天大学 2005 年】（分数：2.00）A.p-llink=q；p-rlink=q-rlink；q-rlink=p；q-rlink-llink=p：B.p-rlink=q-rlink;p-Uink=q；q-rlink=p；q-rlink-llink=pC.p-ll
37、ink=q；p-rlink=q-rlink；q-rlink=p；p-llink-rlink=pD.p-llink=q；p-rlink=q-rlink；q-rlink=p;p-rlink-llink=p； 解析：解析：考查双向链表的插入操作。解答过程与上一题基本一致，读者可以自己画图解决此类问题。28.在双向链表存储结构中，删除 p 所指的结点时须修改指针_。【西安电子科技大学 1998 年】（分数：2.00）A.p-llink-rlink=p-rlink;p-rlink-llink=p-llink; B.p-llink=p-llink 一llink;p-llink-dink=p;C.p-rli
38、nk-llink=pp-rlink=p-rlink-rlinktD.p-rlink=p-llink-llink;p-llink=p-rlink-rlink；解析：解析：考查双向链表的删除操作。二、综合题(总题数：21，分数：42.00)29.利用顺序表的操作，实现以下函数：1)从顺序表中删除具有最小值的元素并由函数返回被删除元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第 i个元素并由函数返回被删除元素的值。如果 j 不合理或顺序表为空则显示出错信息并退出运行。3)向顺序表中第 i 个位置插入一个新的元素 x。如果 i 不合理则显示出错信息并退
39、出运行。4)从顺序表中删除具有给定值 x 的所有元素。5)从顺序表删除其值在给定值 s 与 t 之间(要求 s 小于 t)的所有元素。如果 s 或 t不合理或者顺序表为空，则显示错误信息并退出。6)从有序顺序表中删除其值在给定值 s 与 t 之间(要求s 小于 t)的所有元素。如果 s 或 t 不合理或顺序表为空，则显示错误信息并退出。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。（分数：2.00）_正确答案：(正确答案：考查顺序表各种操作的实现。线性表这一章出综合题的概率很大，且出题灵活。但是不论出什么
40、样的题目，同学们应扎实掌握线性表的基础操作，以不变应万变。1)实现删除具有最小值元素的函数。算法的基本设计思想：从前向后遍历线性表，用个变量记录最小值，同时用另一个变量记录最小值位置。遍历之后将最小值删除。算法的代码： DataType deleteMin(SeqL 5st 假定 0 号元素的值最小 int i，pos=0； for(i=1；iLn) return false; 表空或者 i 不合理，终止操作 value=Ldatai； for(int j=i+1；jLn) return false; 表空或者 i 不合理，终止操作 value=Ldatai； for(int j=i+1；jL
41、n) return falSe; 表满或者参数不合理，终止操作 for(int J=Ln; Ji；J 一一) LdataJ=LdataJ 一 1j Ldatai=value， 从第 i 个位置插入 Ln+； retUrn true ; insertnoi 4)从顺序表中删除具有给定值 X 的所有元素。 算法的基本设计思想：从后向前遍历，一直找到具有 x 值的元素，然后依次将此后的元素前移。 算法的代码： void deleteValue(SeqLiStL，DataType value) int i，J； for(i=Ln 一 1;i=0ji 一一) 循环，寻找具有 X 值的元素并删除 if(L
42、datai=value) 删除具有 x 值的元素 for(J=i+1；J=t) return false； int i，j， for(i=Ln 一 1；i=0；i 一一) 循环，寻找在给定范围内的元素并删除它 if(Ldatai=sLdatainextj p 为工作指针。本文中所有未定义指针都假设为全局定义 L-next=NULL； 第一个结点成为尾结点 while(P!=NULL) r=P 一next； p 一next=L； 将 P 结点插到 L 结点前面。 L=pj L 指向新的链表“第一”元素结点。 p=r； return L; invert)解析：31.有一个单链表 L(至少有 1 个
43、结点)，其头结点指针为 head，编写一个过程将 L 逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。【燕山大学 2001 年】（分数：2.00）_正确答案：(正确答案：算法的基本设计思想： 将头结点摘下，然后从第一个结点开始，直到最后一个结点为止，依次前插入头结点的后面，则实现了链表的逆置。 算法的代码： LinkList invert(LinkList la)la 是带头结点的单链表 p=la 一next， p 为工作指针 1a 一next=NULL； while(p!=NULL) r=p 一next; 暂存 P 的后继 p 一next=la 一next; 将 P 结点前插入头结点后 la-next=p; p=r; return 1a； invert)解析：32.设有一个由正整数组成的无序(向后)单链表，编写完成下列功能的算法：1)找出最小值结点，且打印该数值。2)若该数值是奇数，则将其与直接后继结点的数值交换。3)若该数值是偶数，则将其直接后继结点删除。【东北大学 2000 年】（分
