数据结构辅导线性结构

1、数据结构辅导201003A第一章绪论基本知识点：数据结构与算法的概念。重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。难点：分析算法的时间复杂度。知识要点：数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。数据元素：数据的基本单位，是数据的一个元素。数据对象：性质相同的数据元素的集合，是数据的一个子集。数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。数据类型：一个值的集合和定义在这个值集上的一组运算的总称。数据结构是一门研究非数值计算的程序设计问题中计算机

2、的操作对象(数据元素)以及它们之间关系和操作(运算)的学科。数据的逻辑结构是指数据元素之间逻辑关系的整体。数据的存储结构是指数据结构在计算机内的表示。四种基本数据结构：集合、线性结构、树形结构、图结构。算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。算法执行的时间是问题规模的函数。算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为0(f(n)。算法的时间复杂度与问题的规模有关。例题：编写一个算法，求一个整数数组中的最大元素和最小元素，并指出该算法的时间复杂度。解：对应的算法如下：void MaxM in (i nt

3、a,i nt n, int &max, int &min)该算法求数组a0 n-1的最大元素 max和最小元素 min。 max= min=a0;for(i nt i=1 ;i<=n_1 ;i+)if(ai>max) max=ai;else if(ai< min) min=ai;该算法的时间复杂度为0( n)。例题：编写一个算法，求一个整数数组中的最大元素和次大元素，并指出该算法的时间复杂度。解：对应的算法如下：void Max12(i nt a, i nt n, i nt & max1, i nt & max2)该算法求数组 a0 n-1的最

4、大元素 max1和次大元素 max2。if(a0>a1) max 仁a0 ;max2=a1 ;else max 仁 a1; max2=a0;for(i nt i=2;i<=n _1;i+)if(ai>max1)max2=max1; max1=ai;else if(ai>max2) max2=ai;该算法的时间复杂度为0( n)。例题：编写一个算法，求一个整数数组中的最小元素和次小元素，并指出该算法的时间复杂度。解：对应的算法如下：void Min 12(i nt a, i nt n, i nt &min 1, i nt &min2)该算法求数组 a0n-

5、1的最小元素 min1和次小元素 min2。 if(a0<a1) mi n1=a0; min 2=a1;else mi n仁 a1;mi n2=a0;for(i nt i=2;i<=n _1;i+)if(ai<mi n1) mi n2=mi n1;mi n1=ai;else if(ai< min2) min 2=ai;该算法的时间复杂度为O( n)。例题：选择题1、 数据结构是一门研究程序设计中数据的 以及它们之间的关系和运算等的学科。(A) 元素 (B)计算方法(C)逻辑存储(D)映像2、 在数据结构中，从逻辑上可以把数据结构分为 两类。(A) 动态结构和静态结构(B

6、) 紧凑结构和非紧凑结构(C) 线性结构的非线性结构(D) 内部结构和外部结构3、数据的逻辑结构是关系的整体。(A) 数据数据之间逻辑(B) 数据项之间逻辑(C) 数据类型之间(D) 存储结构4、 在链式存储结构中，一个存储结点存储一个 。(A) 数据项(B) 数据元素(C) 数据结构(D) 数据类型5、 数据结构在计算机内存中的表示是指 。(A) 数据的存储结构(B) 数据结构(C) 数据的逻辑结构(D) 数据元素之间的关系6、 在数据结构中，与所使用的计算机无关的是 。(A) 逻辑结构(B) 存储结构(C) 逻辑结构和存储结构(D) 物理结构7、 数据采用链式存储结构时，要求 。(A) 每

7、个结点占用一片连续的存储区域(B) 所有结点占用一片连续的存储区域(C) 结点的最后一个数据域是指针类型(D) 每个结点有多少个后继，就设多少个指针域8、算法的时间复杂度与有关。(A) 问题规模(B) 计算机硬件性能(C) 编译程序质量(D) 程序设计语言9、算法分析的目的是。(A) 找出数据结构的合理性(B) 研究算法中输入与输出的关系(C) 分析算法的效率以求改进(D) 分析算法的易读性和文档性10、 某算法的时间复杂度为0(n2)，表明该算法的 (A) 问题的规模是n2(B) 执行时间等于n2(C) 执行时间与n2成正比(D) 问题规模与n2成正比第2章线性表基本知识点：线性表的逻辑结构

8、特征，线性表的基本运算，线性表的两种存储结构，以及在 这两种存储结构下线性表的基本运算算法的实现，顺序表和链表的优缺点比较。重点：掌握线性表的定义和特点，线性表的存储结构；顺序表和链表的组织方法和算法设计。难点：单链表和双链表的各种算法设计。例题1、已知顺序表L,请设计一算法，在L的第i个位置插入x。解：存储结构如下：解:存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;在顺序表L的第i个位置(下标为i-1)上插入x的算法如下：void In sertSqList(SqList &

9、L, int i, ElemType x)ElemType *p, *q;if(i<1 | i>L.length) return; / 插入位置不合法。p=&L.elemi-1; q=&L.elemL.le ngth-1;while(q>=p) *(q+1)=*q; q-;/后移*p=x;/ 插入L.len gth+;例题2、已知顺序表L,请设计一个算法，删除L中所有值为x的结点。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void D

10、eleteAllx(SqList &L, ElemType x) int num=0;int i, j;i=0; j=0;while(j<=Len gth-1)if(L.elemj=x) j+;nu m+; else L.elemi+=L.elemj+;L.len gth=Len gth-num;例题3、已知顺序表L是有序表，其值从小到大，请编写算法，在L中插入一个数据元素x并且保持L的有序性。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void In s

11、ertOrderSqList(SqList &L, ElemType x) int k=L.le ngth-1;while(k>=0 && x<L.elemk) L.elemk+1=L.elemk; k=k-1;L.elemk+1=x;L.len gth+;例题4、编写一个算法逆置顺序表。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void Reverse(SqList &L) ElemType *p, *q;p=&L

12、.elem0; q=&L.elemL.le ngth-1;while(pvq) ElemType *temp=*p; *p=*q; *q=temp;例题5、编写一个算法，归并两个有序的顺序表。 解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;算法如下：void MergeSqList(SqList & L1, SqList & L2, SqList & L3) int i, j, k; i=j=k=O;while(i<L1.le ngth &am

13、p;& j<L2.le ngth)if(L1.elemi<=L2.elemj) L3.elemk+=L1.elemi+; else L3.elemk+=L2.elemj+;while(i<L1.le ngth) L3.elemk+=L1.elemi+;while(j<L2.le ngth) L3.elemk+=L2.elemj+;L3.le ngth=k;例题6、设计算法，统计单链表中元素的个数。解：存储结构如下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法

14、如下：(假设单链表是带头结点的)int Nodes(Li nkList &H) int num=0;LNode *p=H-> next;while(p) nu m+; p=p->n ext; return num;说明：，则算法如下:上面的算法中，若假设单链表是带头指针的(即不带头结点)int Nodes(Li nkList &H)int num=0;LNode *p=H;while(p) nu m+; p=p->n ext;return num;例题7、设有一个单链表 H，其数据元素按从小到大有序，设计一个算法, 值为x的结点，并保持其有序性。解：存储结构如

15、下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：(假设单链表是带头结点的)void In sertOrderLi nkList(Li nkList &H, ElemType x)LNode *n ewNode=new LNode; n ewNode->data=x;LNode *p=H-> next;while(p->n ext && p->n ext->data<x) p=p->n ext;n ewNode->

16、n ext=p->n ext;p->n ext =n ewNode;例题8设计算法，在单链表H中删除所有值为x的结点。解：存储结构如下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：(假设单链表是带头结点的)void DeleteAllx(Li nkList &H, ElemType x) LNode *p, *s;p=H;while(p-> next)if(p->n ext->data=x) s=p->n ext; p->n ext=

17、s->n ext; delete s; else p=p->n ext;例题9、假设不带头结点单链表H中有重复的数据域，设计算法，删除即相同数据域的结点只剩一个。解：存储结构如下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：void DeleteToS in gle(Li nkList &H) LNode *pre, *p, *p next, *s;H中插入一个H中重复的数据域,pre=H;while(pre) p=pre;while(p)if(p->n e

18、xt && p->n ext->data=pre->data)s=p->n ext; p->n ext=s->n ext; delete s;else p=p->n ext;pre=pre _>n ext;例题9B、编写算法，在带头结点的单链表中删除重复多余的值(每个值只保留一个) 解：存储结构如下：typedef struct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：在带头结点的单链表中删除重复多余的值的算法如下：void DeleteOthe

19、rxLi nkList(L in kList &L) LNode *pre,*p, *p n, *s;p=L->n ext;while(p)pre=p;pn=p_ >n ext;while(p n)if(p n->data=p_>data)pre->n ext=p n->n ext; delete pn; pn=pre->n ext;else pre=p n; pn=pn_>n ext;p=p->n ext;例题10、判断带头结点的单链表H的数据域是否是递增的。解：存储结构如下：typedef struct LNode ElemTy

20、pe data;struct LNode *n ext;LNode, *Li nkList;算法如下：int Isln crease(Li nkList &H)LNode *p, *p next;p=H _>n ext;if(!p | !p->n ext) retur n 0;while(p && p-> next) if(p->data>p->n ext->data) retur n 0;else p=p->n ext;return 1;例题11、编写一个算法，逆置带头结点的单链表。 解：存储结构如下：typedef s

21、truct LNode ElemType data;struct LNode *n ext;LNode, *Li nkList;算法如下：void Reverse(Li nkList &H)LNode *p, *q;p=H _>n ext;H-> next=0;while(p) q=p; p=p->n ext; q_>n ext=H _>n ext; H_>n ext=q;例题12、叙述线性表的两种存储结构各自的主要特点。答：线性表的两种存储结构分别是顺序存储结构和链式存储结构。 顺序存储结构的主要特点是：(1) 结点中只有自身的信息域，没有关联信息

22、域。因此，顺序存储结构的存储密度大、存 储空间利用率高。(2 )通过计算地址直接访问任何数据元素，即可以随机访问。(3)插入和删除操作会引起大量元素的移动。链式存储结构的主要特点是：(1 )结点除自身的信息域外，还有表示关联信息的指针域。因此，链式存储结构的存储密 度小、存储空间利用率低。(2) 在逻辑上相邻的结点在物理上不必相邻，因此，不可以随机存取，只能顺序存取。(3) 插入和删除操作方便灵活，不必移动结点只需修改结点中的指针域即可。例题13、编写一个算法，在顺序表中统计值为x的数据元素的个数。解：存储结构如下：typedef struct SqList ElemType *elem;in

23、 t le ngth;in t listsize;SqList;在顺序表中统计值为 x的数据元素的个数的算法如下：int Cou ntxSqList(SqList &L, ElemType x) int num=0;int i=0;while(i<=L .len gth-1) if(L.elemi=x) nu m+; i+;return num;例题14、编写算法，在顺序表中删除所有值为x的数据元素。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;在顺序表中删除所有值为

24、x的数据元素的算法如下：void DeleteAllxSqList(SqList &L, ElemType x)int i=0,j=0;while(j<=Len gth-1) if(L.elemj!=x) L.elemi+=L.elemj;j+;L.len gth=i;例题15、编写算法，在顺序表中删除重复多余的值(每个值只保留一个)。解：存储结构如下：typedef struct SqList ElemType *elem;in t le ngth;in t listsize;SqList;在顺序表中删除重复多余的值的算法如下：void DeleteOtherxSqList(S

25、qList &L) int i,j,k;i=0;while(i<L.le ngth-1)j=i+1;while(j<=Len gth-1) if(L.elemj=L.elemi)for(k=j; k<L.le ngth-1; k+) L.elemk=L.elemk+1;L.len gth-;else j+;i+;例题：设计一个算法，将两个元素有序(从小到大)的顺序表合并成一个有序顺序表。 例题：试写一个算法，求带头结点的单链表L中所有结点的数据之和。例题：设计一个算法，将顺序表逆置。例题：设计一个算法，求带头结点的单链表的结点个数。例题：选择题1、线性表是。(A) 一

26、个有限序列，可以为空(B) 个有限序列，不可以为空(C) 一个无限序列，可以为空(D) 一个无限序列，不可以为空2、 链表不具有的特点是 。(A) 可以随机访问任- 元素(B) 插入删除不需要移动元素(C) 不必事先估计存储空间(D) 所需空间与线性表长度成正比3、 线性表采用链式存储结构时，其地址 。(A) 必须是连续的(B) 一定是不连续的(C) 部分地址必须是连续的(D) 连续与否均可以4、 在线性表的的下列存储结构中，读取指定序号的元素花费时间最少的是。(A) 单链表(B) 双链表(C) 循环链表(D) 顺序表5、 若线性表最常用的运算是存取第i个元素及其前趋的值，则采用 存储方式节省

27、时间。(A) 单链表(B) 双链表(C) 循环单链表(D) 顺序表6、在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为.(A) O(log 2n)(B) 0(1)(C) 0( n2)(D) 0( n)7、 在一个单链表中，删除*p结点之后的一个结点的操作是 。(A) p_>n ext=p(B) p->n ext->n ext=p->n ext(C) p->n ext- >n ext=p(D) p->n ext=p->n ext- >n ext8、 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下

28、，查找成功时的平均查找长度为。(A) n(B) n/2(C) (n+1)/2(D) (n-1)/29、 在一个长度为n的顺序表中，删除值为x的元素时需要比较元素和移动元素的总次数是。(A) (n+1)/2(B) n/2(C) n(D) n+110、 在一个顺序表的表尾插入一个元素的时间复杂度是 。(A) O( n)(B) 0(1)2(C) O(n )(D) O(log 2n)11、 在一个顺序表的任何位置插入一个元素的时间复杂度是 。(A) 0( n)(B) 0(1)2(C) 0(n )(D) O(log 2n)12、 在一个不带头结点(首结点为*head )的单循环链表中，至少有一个结点的条

29、件是。(A) head!=NULL(B) head-> next!=NULL(C) head=NULL(D) head-> next=NULL13、 在带头结点*head的循环单链表中，至少有一个结点的条件是 。(A) head-next!=NULL(B) head->n ext!=head(C) head=NULL(D) head-< next=NULL14、 带头结点的单链表head为空的判定条件是 。(A) head=NULL(B) head-> next=NULL(C) head->n ext=head(D) head!=NULL15、 将两个长度为

30、n的有序表归并为一有序表时，算法的时间复杂度是 。(A) 0(1)(B) 0( n)(C) 0( n2)(D) 0(log 2n)第3章栈和队列基本知识点：理解栈和队列的定义、特点及与线性表的异同；掌握顺序栈和链栈的组织方法，栈空、栈满的判断及其描述；掌握顺序队列、循环队列和链队列的组织方法，队满、队空的 判断及其描述。递归的相关概念。重点：栈和队列的特点，顺序栈和链栈上基本运算的实现算法；顺序队列、循环队列和链队列上基本运算算法。递归模型，递归算法的执行过程和递归设计思想。难点：灵活运用栈和队列设计解决应用问题的算法。将递归算法转换成非递归算法。例题1、对于顺序队列来说，如果知道队首元素的位

31、置和队列中元素的个数，则队尾元素所 在的位置显然是可以计算的。也就是说，可以用队列中元素个数代替队尾指针。试编写出这种循环顺序队列的初始化、入队、出队和判队空算法。解：对于顺序队列来说，当已经知道队首元素的位置front和队列中元素的个数 count，则队空的条件是：count=O ；队满的条件是：coun t=MaxSize;计算队尾的位置为：rear=(fro nt+cou nt+MaxSize)%MaxSize;存储结构和对应的算法如下： 存储结构：typedef struct SqQueue ElemType elemMaxSize;int front;int count;SqQueu

32、e;队列初始化的算法为：void In itSqQueue(SqQueue &Q) Q.fro nt=O; Q.cou nt=O;队列的入队算法如下：void En SqQueue(SqQueue &Q, ElemType x) if(Q.cou nt=MaxSize) cout<< "队满！ n”；return;int rear=(Q.fro nt+Q.cou nt+MaxSize)%MaxSize; Q.elemrear=x; Q.co un t+;队列的出队算法如下：void DelSqQueue(SqQueue &Q, ElemType &

33、amp;x) if(Q.count=O) cout<< "队空！ n”；return;x=Q.elemQ.fro nt;Q.fron t=(Q.fro nt+1+MaxSize)%MaxSize;Q.co un t-;判别队列是否为空的算法如下：int lsEmpty(SqQueue &Q) retur n Q.co un t=0;例题2、假设以带头结点的循环链表示队列，并且只设一个指向队尾元素结点的指针(注意 不设头指针)，试设计相应的队列的初始化、入队、出队及判别队列是否空的算法。 解：存储结构如下：typedef struct QNodeElemType d

34、ata;struct QNode *n ext;QNode, *QL in kList;相应的算法分别如下：队列的初始化算法：void Ini tQueue(QL in kList &Q)Q=new QNode; Q-> next=Q;入队列的算法：void En Queue(QL in kList &Q, ElemType x) QNode *p=new QNode; p->data=x;p_>n ext=Q; Q_>n ext=p; Q=p;出队的算法：void DelQueue(QL in kList &Q, ElemType &x

35、) if(Q->next=Q) cout<< "Queue Empty!'n ” return;QNode *p=Q-> next-next;Q->n ext- >n ext=p->n ext;if(Q=p) Q=p->n ext;x=p->data;delete p;判别队列是否为空的算法：int IsEmpty(QLi nkList &Q) return Q->n ext=Q; 例题3、已知An是整型数组，编写一个递归算法求n个元素的平均值。解：求数组An中前k个元素的平均值的递归算法如下：double

36、average(i nt A, int k) if(k=0) return A0;else retru n (average(A, k-1)*(k-1)+Ak-1)/k;注：算法思路：前1个元素的平均值为 A0,前k个元素的平均值为前k-1个元素的和加上第k个元素(Ak-1),再除以k。例题4、设A是含有n个元素的整型数组，分别写出求n个元素之和及n个元素之积的递归定义。解：(1 )对于含有n个元素的整型数组，n个元素的和的递归定义如下：如果 n=1，贝U sum(A, n)=A0;如果 n>1，贝U sum(A,n)=sum(A,n-1)+An-1;这里数组的下标从0开始。(2) 对于

37、含有n个元素的整型数组，n个元素的积的递归定义如下：如果 n=1，贝U sum(A, n)=A0;如果 n>1，贝V sum(A,n)=sum(A,n-1)*An-1;这里数组的下标从0开始。例题4、有一个不带头结点的单链表，其结点类型如下：typedef int ElemType;typedef struct LNode ElemType data;struct node *n ext;LNode, *Li nkList设计如下递归算法：(1) 求以L为头指针的单链表的结点个数；(2) 正向显示以L为头指针的单链表的所有结点值；(3) 反向显示以L为头指针的单链表的所有结点值；(4)

38、删除以L为头指针的单链表中值为x的第一个结点；(5) 删除以L为头指针的单链表中值为x的所有结点；(6) 输出以L为头指针的单链表中最大结点值；(7) 输出以L为头指针的单链表中最小结点值。解：(1)求以L为头指针的单链表的结点个数递归算法如下：int Cou nt(L in kList &L) if(L=0) return 0; else return 1+Cou nt(L-> next);(2)正向显示以L为头指针的单链表的所有结点值的递归算法如下：void DisplayLi nkListFL(L in kList &L) if(L=0) return;else c

39、out<<L->data; DisplayL in kListFL(L->n ext); (3) 反向显示以L为头指针的单链表的所有结点值的递归算法如下：void DisplayLi nkListLF(L in kList &L) if(L=0) return;else DisplayL in kList(L->n ext); cout<<L->data; (4) 删除以L为头指针的单链表中值为x的第一个结点的递归算法如下:void DeletexL in kList(L in kList &L, ElemType x) if(L=0) return;if(L->data=x) LNode *s=L;L=L->n ext; delete s; return; DeletexL in kList(L->n ext, x);(5) 删除以L为头指针的单链表中值为x的所有结点的递归算法如下：void DeleteAllxLi nkList(Li nkList &L