《c语言数据结构》第2章__自测卷答案
- 格式:doc
- 大小:50.50 KB
- 文档页数:15
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。
则采用()存储方式最节省运算时间。
【北京理工大学 2000 一、1(2分)】A.单链表 B.双链表 C.单循环链表 D.带头结点的双循环链表8. 静态链表中指针表示的是(). 【北京理工大学 2001 六、2(2分)】A.内存地址 B.数组下标 C.下一元素地址 D.左、右孩子地址9. 链表不具有的特点是()【福州大学 1998 一、8 (2分)】A.插入、删除不需要移动元素 B.可随机访问任一元素C.不必事先估计存储空间 D.所需空间与线性长度成正比10. 下面的叙述不正确的是()【南京理工大学 1996 一、10(2分)】A.线性表在链式存储时,查找第i个元素的时间同i的值成正比B. 线性表在链式存储时,查找第i个元素的时间同i的值无关C. 线性表在顺序存储时,查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时,查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有((1))和链接两种。
试指出下列各表中使用的是何种存储方式:表1是((2))存储方式;表2是((3))存储方式;表3是((4))存储方式;表4是((5))存储方式。
表左的s指向起始表元。
供选择的答案:A.连续B.单向链接C.双向链接D.不连接E.循环链接F.树状G.网状H.随机I.顺序J.顺序循环【上海海运学院 1995 二、1(5分)】12.(1) 静态链表既有顺序存储的优点,又有动态链表的优点。
所以,它存取表中第i个元素的时间与i无关。
(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了,以后不能增加。
(3) 静态链表与动态链表在元素的插入、删除上类似,不需做元素的移动。
以上错误的是()【南京理工大学 2000 一、3(1.5分)】A.(1),(2) B.(1) C.(1),(2),(3) D.(2)13. 若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为()(1Rlink=p;p->Llink->Rlink=q;q->Llink=q;B. p->Llink=q;p->Llink->Rlink=q;q->Rlink=p;q->Llink=p->Llink;C. q->Rlink=p;q->Llink=p->Llink;p->Llink->Rlink=q;p->Llink=q;D. q->Llink=p->Llink;q->Rlink=q;p->Llink=q;p->Llink=q;24.在单链表指针为p的结点之后插入指针为s的结点,正确的操作是:()。
数据结构C语言版第一二章习题答案Document number:BGCG-0857-BTDO-0089-2022第1章绪论习题1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。
3.简述逻辑结构的四种基本关系并画出它们的关系图。
4.存储结构由哪两种基本的存储方法实现?5.选择题(1)在数据结构中,从逻辑上可以把数据结构分成()。
A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()。
A.存储结构 B.存储实现C.逻辑结构 D.运算实现(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性,这意味着()。
A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同,而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等(4)以下说法正确的是()。
A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构(5)以下与数据的存储结构无关的术语是()。
A.顺序队列 B. 链表 C.有序表 D. 链栈(6)以下数据结构中,()是非线性数据结构A.树 B.字符串 C.队 D.栈6.试分析下面各程序段的时间复杂度。
(1)x=90; y=100;?while(y>0)if(x>100){x=x-10;y--;}else x++;(2)for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;(3)s=0;for i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j];sum=s;(4)i=1;while(i<=n)i=i*3;(5)x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(6)x=n; //n>1y=0;while(x≥(y+1)* (y+1)) y++;(1)O(1)(2)O(m*n)(3)O(n2)n)(4)O(log3(5)因为x++共执行了n-1+n-2+……+1= n(n-1)/2,所以执行时间为O(n2)(6)O(n)第2章线性表1.选择题(1)一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()。
习题2.1选择题1、线性表的顺序存储结构是一种(A)的存储结构,线性表的链式存储结构是一种(B)的存储结构。
A、随机存取B、顺序存取C、索引存取D、散列存取2、对于一个线性,既要求能够进行较快的插入和删除,又要求存储结构能够反映数据元素之间的逻辑关系,则应该选择(B)。
A、顺序存储方式B、链式存储方式C、散列存储方式D、索引存储方式3、已知,L是一个不带头结点的单链表,p指向其中的一个结点,选择合适的语句实现在p结点的后面插入s结点的操作(B)。
A、p->next=s ; s->next=p->next ;B、s->next=p->next ; p->next=s ;C、p->next=s ; s->next=p ;D、s->next=p ; p->next=s ;4、单链表中各结点之间的地址( C D)。
A、必须连续B、部分地址必须连续C、不一定连续D、连续与否都可以5、在一个长度为n的顺序表中向第i个元素(0<i<=n+1)之前插入一个新元素时,需向后移动(B)个元素。
A、n-iB、n-i+1C、n-i-1D、i2.2填空题1、顺序存储的长度为n的线性表,在任何位置上插入和删除操作的时间复杂度基本上都一样。
插入一个元素大约移动表中的(n/2)个元素,删除一个元素时大约移动表中的((n-1)/2)个元素。
2、在线性表的顺序存储方式中,元素之间的逻辑关系是通过(物理顺序)来体现的;在链式存储方式,元素之间的逻辑关系是通过(指针)体现的。
3、对于一个长度为n的单链表,在已知的p结点后面插入一个新结点的时间复杂度为(o(1)),在p结点之前插入一个新结点的时间复杂度为(o(n)),在给定值为e的结点之后插入一个新结点的时间复杂度为(o(n))。
4、在双向链表中,每个结点包含两个指针域,一个指向(前驱)结点,另一个指向(后继)结点。
第2章1. 名词解释(1)线性表具有相同数据类型的n(n>=0)个数据元素的有限序列,排列方式为“一个接一个的排列”。
通常记为:(a1,a2,… a i-1,a i,a i+1,…a n)其中,n为表长,n=0时称为空表。
(2)顺序表用顺序存储方式存放的线性表叫顺序表,顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。
特点:①用物理上的相邻实现数据元素逻辑关系上的相邻;②可实现随机存取。
(3)线性单链表用链式存储方式存放的线性表叫链表。
链表是通过一组任意的存储单元来存储线性表中的数据元素,对每个数据元素a i,除了存放数据元素的自身的信息a i之外,还需要存放其后继a i+1 所在的存贮单元的地址,这两部分信息组成一个“结点”,存放数据元素信息的称为数据域data,存放其后继地址的称为指针域next。
因此n个元素的线性表通过每个结点的指针域联成了一个“链子”,称之为链表。
其中:线性、单向链结构的叫线性单链表;线性、双向链结构的叫线性双向链表;环形、单向链结构的叫单循环链表;环形、双向链结构的叫双循环链表。
(4)单循环链表在单链表的基础上,链表最后一个结点的指针域不为空,而是指向第一个结点,使得链表头尾结点相连,整个链表形成一个环。
单循环链表特点:从表中任何一个结点出发均可找到其它结点。
(单链表特点:要找链表中任何一个结点,必须从头结点开始遍历该结点以前的整个链表。
)2. 判断题(在各题后填写“√”或“×”)(1) 线性表若采用链式存储表示时所有存储结点之间的地址可连续可不连续( √ )(2) 链式存储在插入和删除时需要保持数据元素原来的物理顺序,不需要保持原来的逻辑顺序。
(×)(3) 链表中每个结点都是两个域。
(×)解析:单链表中每个结点都是两个域,双链表不是两个域。
(4) 在顺序表中,逻辑上相邻的元素在物理位置上不一定相邻。
(×)(5) 顺序表可以按下标随机(或直接)访问,顺序表还可以从某一指定元素开始,向前或向后逐个元素顺序访问。
数据结构第2章习题参考答案1. 简答题1.1 什么是数据结构?数据结构是指相互之间存在一种或多种特定关系的数据元素的集合,它包括数据的逻辑结构和物理结构。
1.2 数据结构的分类有哪些?数据结构可以分为线性结构和非线性结构。
线性结构包括线性表、栈、队列和串;非线性结构包括树和图。
1.3 数据结构的逻辑结构有哪些?数据结构的逻辑结构包括线性结构、树形结构和图形结构。
1.4 数据结构的物理结构有哪些?数据结构的物理结构包括顺序存储结构和链式存储结构。
1.5 什么是算法?算法是指求解问题的具体步骤和方法。
1.6 算法的特性有哪些?算法应具有有穷性、确定性、可行性和输入输出性。
2. 选择题2.1 在栈的顺序存储结构中,栈的存储位置是:A. 自顶向下递增B. 自底向上递增C. 自底向上递减D. 自顶向下递减答案:D2.2 下列哪个数据结构不适合表示有父子关系的数据?A. 二叉树B. 图C. 链表D. 堆答案:D2.3 对于一棵完全二叉树,叶子节点的个数为n,则树中节点的总数为:A. 2nB. 2n + 1C. nD. n + 1答案:A2.4 假设有一个长度为10的栈,初始时栈为空,若对该栈连续执行5次入栈操作,然后执行4次出栈操作,最后执行1次入栈操作,则栈中剩余的元素个数为:A. 0B. 1C. 4D. 6答案:D3. 编程题3.1 实现一个栈数据结构的基本操作,包括入栈、出栈、获取栈顶元素和判断栈是否为空。
```Pythonclass Stack:def __init__(self):self.items = []def is_empty(self):return len(self.items) == 0def push(self, item):self.items.append(item)def pop(self):if self.is_empty():return Nonereturn self.items.pop()def peek(self):if self.is_empty():return Nonereturn self.items[-1]```3.2 实现一个队列数据结构的基本操作,包括入队、出队、获取队首元素和判断队列是否为空。
数据结构习题集答案(C语言版严蔚敏)第2章线性表2.1 描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。
解:头指针是指向链表中第一个结点的指针。
首元结点是指链表中存储第一个数据元素的结点。
头结点是在首元结点之前附设的一个结点,该结点不存储数据元素,其指针域指向首元结点,其作用主要是为了方便对链表的操作。
它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解:(1) 在顺序表中插入或删除一个元素,需要平均移动表中一半元素,具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。
单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中,除了首元结点外,任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好?解:当线性表的数据元素在物理位置上是连续存储的时候,用顺序表比用链表好,其特点是可以进行随机存取。
2.4 对以下单链表分别执行下列各程序段,并画出结果示意图。
解:2.5 画出执行下列各行语句后各指针及链表的示意图。
L=(LinkList)malloc(sizeof(LNode)); P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next; P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2);for(i=1;i<=3;i++) Del_LinkList(L,i);解:2.6 已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列。
a. 在P结点后插入S结点的语句序列是__________________。
数据结构C语言版第2版课后习题答案数据结构(C语言版)(第2版)课后习题答案李冬梅2015.3第1章绪论 0第2章线性表 (4)第3章栈和队列 (14)第4章串、数组和广义表 (27)第5章树和二叉树 (34)第6章图 (43)第7章查找 (55)第8章排序 (66)第1章绪论1•简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案:数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。
在有些情况下,数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。
数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。
例如,学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象:是性质相同的数据元素的集合,是数据的一个子集。
例如:整数数据对象是集合N={0,± 1,±2,…},字母字符数据对象是集合C={ ‘ A',' B',…,'b',…,‘ z' },学生基本信息表也可是一个数据对象。
数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。
逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。
因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构:数据对象在计算机中的存储表示,也称为物理结构。
抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。
数据结构第2章习题参考答案2.7习题2.7.1知识点:线性表的逻辑结构一、选择题1①线性表l=(a1,a2,…,an),下列说法正确的是(d)。
a.每个元素都有一个直接前驱和一个直接后继。
b.线性表中至少要有一个元素。
c.表诸元素的排序顺序必须就是由小到大或由小至大。
d.除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。
2①在线性表的下列运算中,不改变数据元素之间结构关系的运算是(d)。
a.插入b.删除c.排序d.定位3①线性表就是具备n个(c)的非常有限序列(n>0)。
【清华大学1998】a.表元素b.字符c.数据元素d.数据项e.信息项二、判断题(t)1①线性表中的每个结点最多只有一个前驱和一个后继。
(f)2①线性表中的每个结点都至少存有一个前驱结点和后继结点。
(f)3①线性表就是n个数的非常有限序列。
(f)4①同一线性表的数据元素可以具有不同的特性。
(t)5①线性表的长度n就是表数据元素的个数,当n=0时,称作空表。
(t)6①线性表就是一个相当有效率的数据结构,它的长度可以根据须要快速增长或延长。
(f)7①对线性表中的数据元素就可以展开出访,无法展开填入和删掉操作方式。
2.7.2知识点:线性表的顺序存储结构一、选择题1①在一个长度为n的顺序表中,在第i个元素(1<=i<=n+1)之前插入一个新元素时需向后移动(b)个元素.a.n-1b.n-i+1c.n-i-1d.i2①若某线性表中最常用的操作方式就是挑第i个元素和打听第i个元素的前趋元素,则使用(d)存储方式最节省时间。
a.单链表b.双链表c.单向循环d.顺序表3②一个数组第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是(b)a.110b.108c.100d.1204①下列哪一条就是顺序存储结构的优点(a)。
【北方交通大学2001】a.存储密度小b.填入运算便利c.删除运算方便d.可方便地用于各种逻辑结构的存储表示5③若长度为n的线性表使用顺序存储结构,在其第i个边线填入一个新元素的算法的时间复杂度为(c)(1<=i<=n+1)。
第二章习题和解答一判断题1.线性表的逻辑顺序和存储顺序总是一致的。
2.顺序存储的线性表可以按序号随机存取。
3.顺序表的插入和删除操作不需要付出很大的时间代价,因为每次操作平均只有近一半的元素需要移动。
4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此是属于同一数据对象。
5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。
6.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上不一定相邻。
7.线性表的链式存储结构优于顺序存储结构。
8.在线性表的顺序存储结构中,插入和删除时,移动元素的个数和该元素的位置有关。
9.线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
10.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。
二单选题 (请从下列A,B,C,D选项中选择一项)1.线性表是( ) 。
(A) 一个有限序列,可以为空;(B) 一个有限序列,不能为空;(C) 一个无限序列,可以为空;(D) 一个无序序列,不能为空。
2.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的。
插入一个元素时平均要移动表中的()个元素。
(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3.线性表采用链式存储时,其地址( ) 。
(A) 必须是连续的;(B) 部分地址必须是连续的;(C) 一定是不连续的;(D) 连续和否均可以。
4.用链表表示线性表的优点是()。
(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序和逻辑顺序相同5.某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素,则采用( )存储方式最节省运算时间。
(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6.循环链表的主要优点是( )。
(A)不在需要头指针了(B)已知某个结点的位置后,能够容易找到他的直接前趋(C)在进行插入、删除运算时,能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7.下面关于线性表的叙述错误的是( )。
抽出时间去学习,凡事从小做起,不怕单调和重复,长期的积累坚持,想不成功,也难。
第1章绪论习题1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型2.试举一个数据结构的例子叙述其逻辑结构和存储结构两方面的含义和相互关系3.简述逻辑结构的四种基本关系并画出它们的关系图4.存储结构由哪两种基本的存储方法实现?5.选择题(1)在数据结构中从逻辑上可以把数据结构分成()A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结构 D.内部结构和外部结构(2)与数据元素本身的形式、内容、相对位置、个数无关的是数据的()A.存储结构 B.存储实现C.逻辑结构 D.运算实现(3)通常要求同一逻辑结构中的所有数据元素具有相同的特性这意味着()A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同而且对应数据项的类型要一致C.每个数据元素都一样D.数据元素所包含的数据项的个数要相等(4)以下说法正确的是()A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构(5)以下与数据的存储结构无关的术语是()A.顺序队列 B. 链表 C. 有序表 D. 链栈(6)以下数据结构中()是非线性数据结构A.树 B.字符串 C.队 D.栈6.试分析下面各程序段的时间复杂度(1)x=90; y=100;while(y>0)if(x>100){x=x-10;y--;}else x++;(2)for (i=0; i<n; i++)for (j=0; j<m; j++)a[i][j]=0;(3)s=0;for i=0; i<n; i++)for(j=0; j<n; j++)s+=B[i][j];sum=s;(4)i=1;while(i<=n)i=i*3;(5)x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(6)x=n; //n>1y=0;while(x≥(y+1)* (y+1))y++;(1)O(1)(2)O(m*n)(3)O(n2)(4)O(log3n)(5)因为x++共执行了n-1+n-2+......+1= n(n-1)/2所以执行时间为O(n2)(6)O()第2章线性表1.选择题(1)一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是()A.110 B.108 C.100 D.120 (2)在n个结点的顺序表中算法的时间复杂度是O(1)的操作是()A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D.将n个结点从小到大排序(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动的元素个数为()A.8 B.63.5 C.63 D.7(4)链接存储的存储结构所占存储空间()A.分两部分一部分存放结点值另一部分存放表示结点间关系的指针B.只有一部分存放结点值C.只有一部分存储表示结点间关系的指针D.分两部分一部分存放结点值另一部分存放结点所占单元数(5)线性表若采用链式存储结构时要求内存中可用存储单元的地址()A.必须是连续的 B.部分地址必须是连续的C.一定是不连续的 D.连续或不连续都可以(6)线性表L在()情况下适用于使用链式结构实现A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中含有大量的结点D.L中结点结构复杂(7)单链表的存储密度()A.大于1 B.等于1 C.小于1 D.不能确定(8)将两个各有n个元素的有序表归并成一个有序表其最少的比较次数是()A.n B.2n-1 C.2n D.n-1(9)在一个长度为n的顺序表中在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动()个元素A.n-i B.n-i+1 C.n-i-1 D.i(10) 线性表L=(a1a2......an)下列说法正确的是()A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中诸元素的排列必须是由小到大或由大到小D.除第一个和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继(11) 若指定有n个元素的向量则建立一个有序单链表的时间复杂性的量级是()A.O(1) B.O(n) C.O(n2) D.O(nlog2n)(12) 以下说法错误的是()A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B.顺序存储的线性表可以随机存取C.由于顺序存储要求连续的存储区域所以在存储管理上不够灵活D.线性表的链式存储结构优于顺序存储结构(13) 在单链表中要将s所指结点插入到p所指结点之后其语句应为()A.s->next=p+1; p->next=s;B.(*p).next=s; (*s).next=(*p).next;C.s->next=p->next; p->next=s->next;D.s->next=p->next; p->next=s;(14) 在双向链表存储结构中删除p所指的结点时须修改指针()A.p->next->prior=p->prior; p->prior->next=p->next;B.p->next=p->next->next; p->next->prior=p;C.p->prior->next=p; p->prior=p->prior->prior;D.p->prior=p->next->next; p->next=p->prior->prior;(15) 在双向循环链表中在p指针所指的结点后插入q所指向的新结点其修改指针的操作是()A.p->next=q; q->prior=p; p->next->prior=q; q->next=q;B.p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;C.q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;D.q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;2.算法设计题(1)将两个递增的有序链表合并为一个递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中不允许有重复的数据void MergeList_L(LinkList &LaLinkList &LbLinkList &Lc){pa=La->next; pb=Lb->next;Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){if(pa->data<pb->data){ pc->next=pa;pc=pa;pa=pa->next;}else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素删除Lb的元素pc->next=pa;pc=pa;pa=pa->next;q=pb->next;delete pb ;pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}(2)将两个非递减的有序链表合并为一个非递增的有序链表要求结果链表仍使用原来两个链表的存储空间不另外占用其它的存储空间表中允许有重复的数据void union(LinkList& LaLinkList& LbLinkList& Lc) {pa = La->next; pb = Lb->next; // 初始化Lc=pc=La; //用La的头结点作为Lc的头结点Lc->next = NULL;while ( pa || pb ) {if ( !pa ) { q = pb; pb = pb->next; }else if ( !pb ) { q = pa; pa = pa->next; }else if (pa->data <= pb->data ) { q = pa; pa = pa->next; } else { q = pb; pb = pb->next; }q->next = Lc->next; Lc->next = q; // 插入}delete Lb; //释放Lb的头结点}(3)已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出A与B的交集并存放于A链表中void Mix(LinkList& LaLinkList& LbLinkList& Lc) {pa=la->next;pb=lb->next;∥设工作指针pa和pb;Lc=pc=La; //用La的头结点作为Lc的头结点while(pa&&pb)if(pa->data==pb->data)∥交集并入结果表中{ pc->next=pa;pc=pa;pa=pa->next;u=pb;pb=pb->next; delete u;}else if(pa->data<pb->data) {u=pa;pa=pa->next; delete u;} else {u=pb; pb=pb->next; delete u;}while(pa){ u=pa; pa=pa->next; delete u;}∥释放结点空间while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间pc->next=null;∥置链表尾标记delete Lb; ∥注:本算法中也可对B表不作释放空间的处理(4)已知两个链表A和B分别表示两个集合其元素递增排列请设计算法求出两个集合A和B 的差集(即仅由在A中出现而不在B中出现的元素所构成的集合)并以同样的形式存储同时返回该集合的元素个数void Difference(LinkedList AB*n)∥A和B均是带头结点的递增有序的单链表分别存储了一个集合本算法求两集合的差集存储于单链表A中*n是结果集合中元素个数调用时为0{p=A->next;∥p和q分别是链表A和B的工作指针q=B->next; pre=A;∥pre为A中p所指结点的前驱结点的指针while(p!=null && q!=null)if(p->data<q->data){pre=p;p=p->next;*n++;} ∥ A链表中当前结点指针后移else if(p->data>q->data)q=q->next;∥B链表中当前结点指针后移else {pre->next=p->next;∥处理AB中元素值相同的结点应删除u=p; p=p->next; delete u;} ∥删除结点(5)设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C其中B表的结点为A表中值小于零的结点而C表的结点为A表中值大于零的结点(链表A的元素类型为整型要求B、C表利用A表的结点)(6)设计一个算法通过一趟遍历在单链表中确定值最大的结点ElemType Max (LinkList L ){if(L->next==NULL) return NULL;pmax=L->next; //假定第一个结点中数据具有最大值p=L->next->next;while(p != NULL ){//如果下一个结点存在if(p->data > pmax->data) pmax=p;p=p->next;}return pmax->data;(7)设计一个算法通过遍历一趟将链表中所有结点的链接方向逆转仍利用原表的存储空间void inverse(LinkList &L) {// 逆置带头结点的单链表 Lp=L->next; L->next=NULL;while ( p) {q=p->next; // q指向*p的后继p->next=L->next;L->next=p; // *p插入在头结点之后p = q;}}(8)设计一个算法删除递增有序链表中值大于mink且小于maxk的所有元素(mink和maxk是给定的两个参数其值可以和表中的元素相同也可以不同)void delete(LinkList &Lint minkint maxk) {p=L->next; //首元结点while (p && p->data<=mink){ pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) {while (p && p->data<maxk) p=p->next;// 查找第一个值≥maxk 的结点q=pre->next; pre->next=p; // 修改指针while (q!=p){ s=q->next; delete q; q=s; } // 释放结点空间 }//if}(9)已知p指向双向循环链表中的一个结点其结点结构为data、prior、next三个域写出算法change(p)交换p所指向的结点和它的前缀结点的顺序知道双向循环链表中的一个结点与前驱交换涉及到四个结点(p结点前驱结点前驱的前驱结点后继结点)六条链void Exchange(LinkedList p)∥p是双向循环链表中的一个结点本算法将p所指结点与其前驱结点交换{q=p->llink;q->llink->rlink=p;∥p的前驱的前驱之后继为pp->llink=q->llink;∥p的前驱指向其前驱的前驱q->rlink=p->rlink;∥p的前驱的后继为p的后继q->llink=p;∥p与其前驱交换p->rlink->llink=q;∥p的后继的前驱指向原p的前驱p->rlink=q;∥p的后继指向其原来的前驱}∥算法exchange结束(10)已知长度为n的线性表A采用顺序存储结构请写一时间复杂度为O(n)、空间复杂度为O(1)的算法该算法删除线性表中所有值为item的数据元素[题目分析] 在顺序存储的线性表上删除元素通常要涉及到一系列元素的移动(删第i个元素第i+1至第n个元素要依次前移)本题要求删除线性表中所有值为item的数据元素并未要求元素间的相对位置不变因此可以考虑设头尾两个指针(i=1j=n)从两端向中间移动凡遇到值item的数据元素时直接将右端元素左移至值为item的数据元素位置void Delete(ElemType A[ ]int n)∥A是有n个元素的一维数组本算法删除A中所有值为item的元素{i=1;j=n;∥设置数组低、高端指针(下标)while(i<j){while(i<j && A[i]!=item)i++;∥若值不为item左移指针if(i<j)while(i<j && A[j]==item)j--;∥若右端元素值为item 指针左移if(i<j)A[i++]=A[j--];}[算法讨论] 因元素只扫描一趟算法时间复杂度为O(n)删除元素未使用其它辅助空间最后线性表中的元素个数是j。
决战高考,改变命运。
屡挫屡战,笑傲群雄。
第2章自测卷答案姓名班级题号一二三四五六七总分题分1310101071040100得分一、填空(每空1分共13分)1. 【严题集2.2①】在顺序表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与表长和该元素在表中的位置有关2. 线性表中结点的集合是有限的结点间的关系是一对一的3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时需向后移动 n-i+1 个元素4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时需向前移动 n-i 个元素5. 在顺序表中访问任意一结点的时间复杂度均为 O(1)因此顺序表也称为随机存取的数据结构6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻单链表中逻辑上相邻的元素的物理位置不一定相邻7. 【严题集2.2①】在单链表中除了首元结点外任一结点的存储位置由其直接前驱结点的链域的值指示8.在n个结点的单链表中要删除已知结点*p需找到它的前驱结点的地址其时间复杂度为O(n)二、判断正误(在正确的说法后面打勾反之打叉)(每小题1分共10分)(×)1. 链表的每个结点中都恰好包含一个指针答:错误链表中的结点可含多个指针域分别存放多个指针例如双向链表中的结点可以含有两个指针域分别存放指向其直接前趋和直接后继结点的指针(×)2. 链表的物理存储结构具有同链表一样的顺序错链表的存储结构特点是无序而链表的示意图有序(×)3. 链表的删除算法很简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动错链表的结点不会移动只是指针内容改变(×)4. 线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型错混淆了逻辑结构与物理结构链表也是线性表!且即使是顺序表也能存放记录型数据(×)5. 顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取错正好说反了顺序表才适合随机存取链表恰恰适于"顺藤摸瓜"(×)6. 顺序存储方式的优点是存储密度大且插入、删除运算效率高错前一半正确但后一半说法错误那是链式存储的优点顺序存储方式插入、删除运算效率较低在表长为n的顺序表中插入和删除一个数据元素平均需移动表长一半个数的数据元素(×)7. 线性表在物理存储空间中也一定是连续的错线性表有两种存储方式顺序存储和链式存储后者不要求连续存放(×)8. 线性表在顺序存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻错误线性表有两种存储方式在顺序存储时逻辑上相邻的元素在存储的物理位置次序上也相邻(×)9. 顺序存储方式只能用于存储线性结构错误顺序存储方式不仅能用于存储线性结构还可以用来存放非线性结构例如完全二叉树是属于非线性结构但其最佳存储方式是顺序存储方式(后一节介绍)(×)10. 线性表的逻辑顺序与存储顺序总是一致的错理由同7链式存储就无需一致三、单项选择题(每小题1分共10分)( C )1.数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称之为:(A)存储结构(B)逻辑结构(C)顺序存储结构(D)链式存储结构( B )2.一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是(A)110 (B)108 (C)100 (D)120( A )3. 在n个结点的顺序表中算法的时间复杂度是O(1)的操作是:(A)访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)(B)在第i个结点后插入一个新结点(1≤i≤n)(C)删除第i个结点(1≤i≤n)(D)将n个结点从小到大排序( B )4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动个元素(A)8 (B)63.5 (C)63 (D)7( A )5. 链接存储的存储结构所占存储空间:(A)分两部分一部分存放结点值另一部分存放表示结点间关系的指针(B)只有一部分存放结点值(C)只有一部分存储表示结点间关系的指针(D)分两部分一部分存放结点值另一部分存放结点所占单元数( B )6. 链表是一种采用存储结构存储的线性表;(A)顺序(B)链式(C)星式(D)网状( D )7. 线性表若采用链式存储结构时要求内存中可用存储单元的地址:(A)必须是连续的(B)部分地址必须是连续的(C)一定是不连续的(D)连续或不连续都可以( B )8.线性表L在情况下适用于使用链式结构实现(A)需经常修改L中的结点值(B)需不断对L进行删除插入(C)L中含有大量的结点(D)L中结点结构复杂( C )9.单链表的存储密度(A)大于1;(B)等于1;(C)小于1;(D)不能确定( B )10.设a1、a2、a3为3个结点整数P034代表地址则如下的链式存储结构称为P034P0-->3-->a24-->A3(A)循环链表(B)单链表(C)双向循环链表(D)双向链表四、简答题(每小题5分共10分)1. 【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点在什么情况下用顺序表比链表好?答:①顺序存储时相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的优点:存储密度大(=1?)存储空间利用率高缺点:插入或删除元素时不方便②链式存储时相邻数据元素可随意存放但所占存储空间分两部分一部分存放结点值另一部分存放表示结点间关系的指针优点:插入或删除元素时很方便使用灵活缺点:存储密度小(<1)存储空间利用率低顺序表适宜于做查找这样的静态操作;链表宜于做插入、删除这样的动态操作若线性表的长度变化不大且其主要操作是查找则采用顺序表;若线性表的长度变化较大且其主要操作是插入、删除操作则采用链表2 .【严题集2.1①】描述以下三个概念的区别:头指针、头结点、首元结点(第一个元素结在单链表中设置头结点的作用是什么?答:首元结点是指链表中存储线性表中第一个数据元素a1的结点为了操作方便通常在链表的首元结点之前附设一个结点称为头结点该结点的数据域中不存储线性表的数据元素其作用是为了对链表进行操作时可以对空表、非空表的情况以及对首元结点进行统一处理头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针若链表中附设头结点则不管线性表是否为空表头指针均不为空否则表示空表的链表的头指针为空这三个概念对单链表、双向链表和循环链表均适用是否设置头结点是不同的存储结构表示同一逻辑结构的问题头结点head-->datalink头指针首元结点简而言之头指针是指向链表中第一个结点(或为头结点或为首元结点)的指针;头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息(内放头指针?那还得另配一个头指针!!!)首元素结点是指链表中存储线性表中第一个数据元素a1的结点五、【软考题】线性表具有两种存储方式即顺序方式和链接方式现有一个具有五个元素的线性表L={2317470531}若它以链接方式存储在下列100~119号地址空间中每个结点由数据(占2个字节)和指针(占2个字节)组成如下所示:0517X23V31Y47Z^^100120其中指针XYZ的值分别为多少?该线性表的首结点起始地址为多少?末结点的起始地址为多少?(10分)答:X= 116 Y= 0 Z= 100 首址= 108 末址= 112六、阅读分析题(10分)【严题集2.10②】指出以下算法中的错误和低效(即费时)之处并将它改写为一个既正确又高效的算法答:错误有两处:①参数不合法的判别条件不完整例如表长为10若从第一位置(i=1)删除10个元素(k=10)要求合理但会被判为非法合法的入口参数条件为(0<i≤a.length)^ (0≤k≤a.length-i)应将if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE改为:if (!((0<i≤a.length)^ (o≤k≤a.length-i))) return INFEASIBLE 第二个FOR语句中元素前移的次序错误应将for ( j = a.length; j>=i+1; j--) a.elem[j-1] = a.elem[j];改为for (j>=i+1; j = a.length; j++) a.elem[j-1] = a.elem[j];七、编程题(每题10分共40分)1. 【徐士良题集2002年1月省统考题】写出在顺序存储结构下将线性表逆转的算法要求使用最少的附加空间解:输入:长度为n的线性表数组A(1:n)输出:逆转后的长度为n的线性表数组A(1:n)C语言描述如下(其中ET为数据元素的类型):2. 【严题集2.6②】已知L是无表头结点的单链表且P结点既不是首元结点也不是尾元结点请写出在P结点后插入S结点的核心语句序列答:此题答案不唯一但若从已给定序列中挑选则限制颇多(7) Q=P;(11) P=L;(8) while(P->next!=Q)P=P->next;(10) P=Q;(4) S->next=P->next;P->next=S;3. 编写程序将若干整数从键盘输入以单链表形式存储起来然后计算单链表中结点的个数(其中指针P指向该链表的第一个结点)注:统计结点个数是【省统考样题】的要求也是教材P60 4-6计算链表长度的要求编程又简单很容易作为考题解:编写C程序如下(已上机通过):全局变量及函数提前说明:---------------------------------#include<stdio.h>#include<stdlib.h>typedef struct liuyu{int data;struct liuyu*link;}test; liuyu *p*q*r*head;int m=sizeof(test);void main () /*第一步从键盘输入整数不断添加到链表*/{int i;head=(test*)malloc(m); /*m=sizeof(test);*/p=head; i=0;while (i!=-9999){ printf("/ninput an integer [stop by '-9999']:");scanf("%d"&i);p->data=i; /* input data is saved */p->link=(test*)malloc(m); /*m=sizeof(test));*/q=p;p=p->link;}q->link=NULL; /*原先用p->link=NULL似乎太晚!*/p=head; i=0; /*统计链表结点的个数并打印出来*/ while (p->link!=NULL){printf("%d"p->data);p=p->link;i++;}printf("\n node number=%d\n"i-1); /*结点的个数不包括-9999*/}0301陈建武:3.程序中统计结点数应是i个而不是i-1.假设链表表长为ni从0开始则在统计某一结点后 i 加一此时p已指向下一个结点第一结点统计结束i为1p指向第二结点即当p指向尾结点(第n个结点)时i的值为n-1while循环条件不符(指针域为null)退出循环即得统计的结点数为n-1.所以 i 的值就是结点数不必再减一4. 请编写26个字母按特定字母值插入或删除的完整程序可自行选用顺序存储或链表结构答:#include<stdio.h> /*全局变量及函数提前说明:*/#include<stdlib.h>typedef struct liuyu{char data;struct liuyu*link;}test;liuyu *p*q*r*head;int L; /*元素的个数*/int m=sizeof(test);void build(); /* 主函数中会被调用的函数应当预先说明 */ void display();int insert_char(charchar); /*插入一个字母在第字母Y之前若无字母则加到末尾*/int delet_char(char); /* 删除元素X注意保存X的前趋元素指针! *//*---------------------------------------------------------*/void build() /*字母链表的生成*/{int i;head=(test*)malloc(m); /*m=sizeof(test);*/p=head;for(i=1;i<L;i++){ p->data=i+'a'-1; /* 'a'也可用其ASCII码97来表示 */ p->link=(test*)malloc(m); /*m=sizeof(test));*/p=p->link; }p->data=i+'a'-1;p->link=NULL;}/*---------------------------------------------------------*/void display() /*字母链表的输出*/{p=head;while (p->link!=NULL){ printf("%c"p->data);p=p->link; }printf("%c\n"p->data);}/*---------------------------------------------------------*/ int insert_char(char Xchar Y) /*插入一个字母X在某个字母Y之前若找不到Y字母则加到末尾*/{p=head;r=(test*)malloc(m);r->data=X;if(head->data==Y){ head=r;r->link=p; }else{ while((p->data!=Y)&&(p->link!=NULL)) {q=p; p=p->link;} if(p->data==Y) { q->link=r; r->link=p; }else{p->link=r;r->link=NULL;}}L++;return(0);}/*---------------------------------------------------------*/ int delet_char(char X) /* 删除元素X注意保存X的前趋元素指针! */{ p=head;if(head->data==X){head=head->link;free(p);}else{ while((p->data!=X)&&(p->link!=NULL)){q=p;p=p->link;}if(p->data==X){ q->link=p->link;free(p); }else return(-1);}L--;return(0);}/*---------------------------------------------------------*/ void main(void) /*字母线性表的生成和输出*/{ L=26;build();display();printf("insert return value=%d\n"insert_char('L''W'));display();printf("delete return value=%d\n"delet_char('z'));display();}附:屏幕上显示的执行结果是:a b c d e f g h i j k l m n o p q r s t u v w x y z insert return value=0a b c d 9 e f g h i j k l m n o p q r s t u v w x y z L delete return value=0a b c d e f g h i j k l m n o p q r s t u v w x y L0301陈建武修改意见:一. display()函数代码可优化为四行void display() /*字母链表的输出*/{p=head;while (p->link!=NULL)//改为while(p)因为当p指向尾结点时p不为null条件成立循环//printf()然后p被赋值为null此时循环条件不符退出正好.{ printf("%c"p->data);p=p->link; }printf("%c\n"p->data); //用while(p)此行可删}二.对int insert_char(char Xchar Y)若用带头结点的链表代码可减为10行我的程序如下(若参数没有slist p代码要多一行让q指向头指针)void InsertFind(slist pchar insertcharchar insertpos)//字母insertpos前插入字母insertchar{slist ppriornewnode; //newnode新结点pprior为插入位置结点的直接前驱newnode = new liuyu; //为新结点分配内存newnode->data = insertchar; //对结点数据域初始化while(p) //当p指向尾结点时最后一次循环{pprior = p; //pprior从头指针开始指向p的直接前驱p = p->next; //p从首元结点开始不断前移直至最后p为nullif(p&&(p->data == insertpos)) //当p为null或者结点p的数据域为所要插入的字母break; //则退出循环}newnode->next = pprior->next; //在找到的位置前插入pprior->next = newnode;}对删除结点的操作若有头结点同样可以减少代码由此可见创建一个头结点对简化程序有很大的帮助.上面的观点仅供参考不对之处请指教!。