数据结构算法(第二章)
∥算法2.1: 将所有在线性表Lb中但不在La中的数据元素插入到La中void union(List &La, List Lb){
La_len=ListLength(La)；
Lb_len=ListLength(Lb)；
for(i=1;i<=Lb_len;i++){
GetElem(Lb,i,e)；
if(!LocateElem(La,e,equal)) ListInsert(La，++La_len,e);
}
}∥union
∥算法2.2: 已知线性表La和Lb中的数据元素按值非递减排列。
∥归并La和Lb得到新的线性表Lc ,Lc的数据元素也接值非递减排列。void MergeList(ListLa,List Lb, List &Lc){
InitList(Lc);
i=j=1; k=0;
La_len=ListLength(La); Lb_len=ListLengtb(Lb);
while((i<=La_len)&&(j<=Lb_len)){∥La和Lb均非空
GetElem(La,i,ai);GetElem(Lb,j,bj);
if (ai<=bj) { ListInsert(Lc, ++k, ai); ++i; }
else{ListInsert(Lc, ++k, bj); ++j;}
}
while(i<=La_len){
GetElem(La, i++, ai); ListInsert(Lc,++k,ai);
}
while(j<=Lb_len){
GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj);
}
}∥MergeList
∥算法 2.3:构造一个空的线性表L。
Status InitList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem) exit(OVERFLOW);
L.length=0；
L.listsize=LIST_INIT_SIZE;
return oK;
}∥InitList_Sq
∥算法2.4：在顺序线性表L中第i个位置之前插入新的元素e,
∥i的合法值为1≤i≤ListLength_ Sq(L)+1
Status ListInsert_ Sq(SqList &L, int i, ElemType e){
if(i<1|| i>L.length+1) return ERROR;
if (L.length>=L.listsize){
newbase= (ElemType *)realloc(L.elem, (L.listsize+ LISTINCREMENT)* sizeof(ElemType));
if(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT；
}
q=& (L.elem[i-l])；
for(p=&(L.elem[L.length-l]);p>=q；--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}∥Listlnsert_ Sq
∥算法2.5：在顺序线性表L中删除第i个元素，并用e返回其值
∥i的合法值为1≤i≤ListLength_ Sq(L)
Status ListDelete_ Sq(SqList &L, int i,ElemType &e){
if((i<1)|(1> L.length)) return ERROR;
p=&(L.elem[i-l]);
e=*p；
q=L.elem+L.length -1；
for(++p;p<=q;++p) *(p一1）=*p；
--L.length;
Return OK;
}//ListDelete_Sq
算法2.6：在顺序线性表L中查找第1个值与e满足compare()的元素的位序，//若找到，则返回其在L中的位序，否则返回0
LocateElem_Sq(SqList_L, ElemType e, Status(*compare)
(ElemType,ElemType)){
；
L.elem;
while(i<=L.length&&!(*compare)(*p++，e)) ++i;
if(i<=L.length) return i;
else return0；
}∥LocateElem_Sq
∥算法2.7：已知顺序线性表La和Lb的元素按值非递减排列
∥归并La和Lb得到新的顺序线性表Lc ,Lc的元素也按值非递减排列
void MergeList_ Sq(SqList La, SqList Lb, SqList &Lc){
pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
pc=Lc.elem=(ElemType* )malloc(Lc.listsize* sizeof(ElemType));
if(!Lc.elem) exit(OVERFLOW)；
pa_last=La.elem+La.length-l;
pb_last=Lb.elem+Lb.length-l;
while (pa<=pa_last&&pb<=pb_last){
*pc++=*pa++;
while (pa<=pa_ last) *pc++=*pa++；
while (pb<=pb_ last) *pc++=*pb++；
}∥MergeList_Sq
∥算法2.8：L为带头绪点的单链表的头指针。
∥当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
Status GetElem_ L(LinkList L,int i,ElemType &e){
p= L->next；j=l；
while(p&&j p=p->next;++j； } if(!p ||j>i) return ERROR; e=p ->data; return OK; }∥GetElem_L ∥算法2.9：在带头结点的单链线性表L中第i个位置之前插入元素e Status ListInsert_ L(LinkList &L, int i, ElemType e){ p=L; j=0； while（p&&j if ( !p || j>i-1 ) return ERROR; s = (LinkList) malloc ( sizeof (LNode)); s->data = e; s->next = p->next; p->next = s; return OK ; }∥ Listlnsert L ∥算法2.10：在带头结点的单链线性表L中，删除第i个儿素，并山e返回其值 Status ListDelete L(LinkList &L, int i,ElemType &e){ p=L；j =0; while (p->next&&j p=p->next; ++j； } if(!(p->next) || j>i--1) return ERROR; q = p->next; p->next=q->next; e=q->data; free(q); return OK; }∥ListDelete_L ∥算法2.11：逆位序输入n个几素的值，建立带表头结点的单链线性表L void CreateList_L(LinkList &L, int n){ L = (LinkList) malloc( sizeof (LNode)); L->next = NULL; for (i=n;j>0 ;--i){ p=( LinkList) malloc( sizeof( LNode)) scanf( &p ->data); p->next = L->next; L->next = p; } }∥CreateList_L ∥算法2.12：已知单链线性表La和Lb的元素按值非递减排列 ∥归并La和Lb得到新的单链线性表Lc ,Lc的元素也按值非递减排列 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb){ if(pa ->data<=pb->data){ pc->next=pa; pc=pa;pa=pa->next; } else{pc->next=pb; pc=pb; pb=pb->next;} } pc->next = pa ? pa : pb; free( Lb); }∥ MergeList_ L ∥算法2.13：在静态单链线性表L中查找第1个值为e的元素。 ∥若找到，则返回它在L中的位序，否则返回0。 int LocateElem_SL(SLinkList S,ElemType e){ i= S[0].cur; while(i&&S[i].data!=e) i= S[i].cur; return i； )∥LocateElem_SL ∥算法2.14：将一维数组space中各分量链戚一个备用链表，spaca[0]. cur 为头指针，“0”表示空指针 void InitSpace_SL(SLinkList &space){ for(i=0;i space[MAXSIZE- l].cur=0; )∥InitSpace_SL ∥算法2.15：若备用空间链表非空，则返回分配的结点下标，否则返回0 int Malloc_SL(SLinkList &space){ i=space[0].cur; ． if (space[0].cur) space[0].cur=space[i].cur; return i; }∥Malloc_SL ∥算法2.16：将下标为k的空闲结点回收到备用链表 void Free_SL(SLinkList &space, int k){ space[k].cur=space[0].cur; space[0].cur=k; )∥Free_ SL //算法2.17 //依次输入集合A和B的元素，在一维数组space中建立集合（A-B） ∪（B-A） //的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为其头指针 void difference(SLinkList &space,int &S){ InitSpace_SL( space)； S=Malloc_SL( space); r=S; scanf(m,n); for(j=1；j<=m;++j){ i= Malloc_SL(space); scanf( space[i]. data); space[r].cur = i; r = i; }∥for space[r].cur = 0; for(j=1;j<=n;++i){ scanf(b); p=S; k=space[S].cur; while(k!=space[r].cur&&space[k].data!=b){ p=k;k= space[k].cur; }∥while if(k==space[r].cur){ i= Malloc_SL(space); space[i].data=b； space[i].cur=space[r].cur; space[r].cur=i； }∥if else{ space[p].cur=space[k].cur; Free_ SL(space,k)； if(r==k)r=p； }∥else }∥for }∥difference //算法2. 18：在带头结点的双链循环线性表L中第i个位置之前插入元素e Status Listlnsert_DuL(DuLinkList &L, int i,ElemType e){ if(!(p=GetElemP_ DuL(L, i))) ∥在L中确定插入位置 return ERROR; ∥p=NULL，即插入位置不合法 if(!(s=(DuLinkList)malloc(sizeof(DuLNode))) return ERROR; s->data=e； s->prior=p->prior; p->prior->next=s; s->next=p； p->prior=s; return OK; }∥Listlnsert_ DuL //算法2.19: 删除带头结点的双链循环线性表L的第i个元素， //i的合法值为l≤i≤表长 Status ListDelete_DuL(DuLinkList &L,int i,ElemType &e){ if(!(p=GetElemP_DuL(L，i))) return ERROR; e= p->data; p->prior->next = p->next; p->next->prior=p->prior; free(P)； return OK； }∥ListDelete_ DuL 数据结构作业系统_第五章答案 5.21④假设稀疏矩阵A和B均以三元组表作为存储结构。 试写出矩阵相加的算法，另设三元组表C存放结果矩阵。 要求实现以下函数： Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C); /* 三元组表示的稀疏矩阵加法: C=A+B */ 稀疏矩阵的三元组顺序表类型TSMatrix的定义： #define MAXSIZE 20 // 非零元个数的最大值 typedef struct { int i,j; // 行下标,列下标 ElemType e; // 非零元素值 }Triple; typedef struct { Triple data[MAXSIZE+1]; // 非零元三元组表,data[0]未用 int mu,nu,tu; // 矩阵的行数、列数和非零元个数 }TSMatrix; Status AddTSM(TSMatrix A,TSMatrix B,TSMatrix &C) /* 三元组表示的稀疏矩阵加法: C=A+B */ { int k=1,n=1,p=1; ElemType ce; if(A.mu!=B.mu||A.nu!=B.nu)return ERROR; while(k<=A.tu&&n<=B.tu) { if(A.data[k].i==B.data[n].i&&A.data[k].j==B.data[n].j) { ce=A.data[k].e+B.data[n].e; if(ce) { C.data[p].i=A.data[k].i; C.data[p].j=A.data[k].j; C.data[p].e=ce; p++; //printf("%d,,%d ",ce,C.data[p-1].e); } k++;n++; } else if(A.data[k].i 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） 习题参考答案 一．选择题 1.从逻辑上可以把数据结构分为（C)两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.在下面的程序段中，对x的斌值语句的频度为（C)。 for( t＝1；k＜＝n;k＋＋） for（j=1;j＜＝n; j＋＋） x=x十1； A. O(2n) B. O (n) C. O (n2)． D. O（1og2n) 3.采用链式存储结构表示数据时，相邻的数据元素的存储地址（C)。 A.一定连续B．一定不连续 C.不一定连续 D.部分连续，部分不连续 4.下面关于算法说法正确的是（D）。 A.算法的时间复杂度一般与算法的空间复杂度成正比 B.解决某问题的算法可能有多种，但肯定采用相同的数据结构 C.算法的可行性是指算法的指令不能有二义性 D.同一个算法，实现语言的级别越高，执行效率就越低 5.在发生非法操作时，算法能够作出适当处理的特性称为（B）。 A.正确性 B.健壮性 C.可读性 D.可移植性 二、判断题 1.数据的逻辑结构是指数据的各数据项之间的逻辑关系。（√） 2.顺序存储方式的优点是存储密度大，且插人、删除运算效率高。（×） 3.数据的逻辑结构说明数据元素之间的次序关系，它依赖于数据的存储结构。（×） 4.算法的优劣与描述算法的语言无关，但与所用计算机的性能有关。（×） 5.算法必须有输出，但可以没有输人。（√） 三、筒答题 1．常见的逻辑结构有哪几种，各自的特点是什么？常用的存储结构有哪几种，各自的特点是什么？ 【答】常见的四种逻辑结构： ①集合结构：数据元素之间是“属于同一个集合” ②线性结构：数据元素之间存在着一对一的关系 ③树结构：数据元素之间存在着一对多的关系 ④结构：数据元素之间存在着多对多的关系。 常见的四种存储结构有： ①顺序存储：把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。 ②链接存储：对逻辑上相邻的元素不要求物理位置相邻的存储单元，元素间的逻辑关系通过附设的指针域来表示。 ③索引存储：通过建立索引表存储结点信息的方法，其中索引表一般存储结点关键字和一个地点信息，可通过该地址找到结点的其他信息。 ④散列存储：根据结点的关键字直接计算出该结点的存储地址的方法。 2．简述算法和程序的区别。 【解答】一个算法若用程序设计语言来描述，则它就是一个程序。算法的含义与程序十分相 一、概念题（每空1分，共53分） 1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2．由３个结点所构成的二叉树有种形态。 3．一棵深度为6的满二叉树有个分支结点和个叶子。 4．一棵具有２５７个结点的完全二叉树，它的深度为。 5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。 8．设一棵完全二叉树有700个结点，则共有个叶子结点。 9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。 10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。 11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 12.中序遍历的递归算法平均空间复杂度为。 13.二叉树通常有______存储结构和______存储结构两类存储结构。 14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有： （1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。 （3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 15.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左 右孩子，其余的________个指针域为NULL。 18.二叉树有不同的链式存储结构，其中最常用的是________与________。 19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。 20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 21.树的结点数目至少为________，二叉树的结点数目至少为________。 22.树的主要遍历方法有________、________、________等三种。 23.由________转换成二叉树时，其根结点的右子树总是空的。 24.哈夫曼（Huffman）树是带权路径度________的树，通常权值较大的结点离根________。 25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。 二、选择题（每空1分，共12分） （）1．不含任何结点的空树。 （Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 （）2．二叉树是非线性数据结构，所以。 ?．算法分析 2.1.?标 ·了解为何算法分析的重要性 ·能够??“O ”表?法来描述算法执?时间 ·了解在Python 列表和字典类型中通?操作??“O ”表?法表?的执?时间 ·了解Python 数据类型的具体实现对算法分析的影响 ·了解如何对简单的Python 程序进?执?时间检测 2.2.什么是算法分析 计算机初学者经常将??的程序与他?的?较。你也可能注意到了电脑程序常常看起来很相似，尤其是那些简单的程序。?个有趣的问题出现了，当两个看起来不同的程序解决相同的问题时，?个程序会优于另?个吗？ 为了回答这个问题，我们需要记住的是，程序和它所代表的基本算法有着重要差别。在第?章中我们说到，算法是问题解决的通?的分步的指令的聚合。这是?种能解决任何问题实例的?法，?如给定?个特定的输?，算法能产?期望的结果。从另???看，?个程序是?某种编程语?编码后的算法。同?算法通过不同的程序员采?不同的编程语?能产?很多程序。 为进?步探究这种差异，请阅读接下来展?的函数。这个函数解决了?个我们熟知的问题，计算前n 个整数的和。其中的算法使?了?个初始值为0的累加变量的概念。解决?案是遍历这n 个整数，逐个累加到累加变量。 代码2.1前n 个正整数求和（active1 ） 现在看下?的foo函数。可能第?眼看上去?较奇怪，但是进?步观察你会发现，这个函数所实现的功能与之前代码2.1中的函数基本相同。看不太懂的原因是糟糕的编码。我们没有使?好的变量命名来增加可读性，并且在累加过程中使?了多余的赋值语句。 回到前?我们提出的问题：是否?个程序会优于另?个？答案取决于你??的标准。如果你关?可读性，那么sum_of_n函数肯定?foo函数更好。实际上，在你的编程?门课程上你可能见过很多这样的例?，因为这些课程的?标之?就是帮助你编写更具可读性的程 代码2.2 另?种前n个正整数求和（ac ve2） def foo(tom): fred=0 for bill in range(1,tom+1): barney = bill fred = fred + barney return fred print (foo(10)) 序。然?，在这门课程中，我们主要感兴趣的是算法本?的特性。（我们当然希望你可以继续努?写出更具可读性的代码。） 算法分析主要就是从计算资源的消耗的?度来评判和?较算法。我们想要分析两种算法并且指出哪种更好，主要考虑的是哪?种可以更?效地利?计算资源。或者占?更少的资源。从这个?度，上述两个函数实际上是基本相同的，它们都采?了?样的算法来解决累加求和问题。 全国计算机二级考试 第一章数据结构与算法 1.一个算法一般都可以用_____、_____ 、 _____三种控制结构组合完成。 [解析]顺序、选择（分支）、循环（重复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是________。 [解析]算法的控制结构 在一般的计算机系统中，有算术运算、逻辑运算、关系运算和________四类基本的操作和运算。 [解析]数据传输 2.常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]列举就是列举出所有可能性，将所有可能性统统列举出来，然后解决问题的方法。所以A 3.根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的，这是算法设计基本方法中的____。 [解析]列举法 4.通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]B 5.在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是（） A．列举法 B.归纳法 C.递归法 D.减半递推法 [解析]二分法就是从一半处比较，减半递推技术也称分治法，将问题减半。所以D 6.将一个复杂的问题归结为若干个简单的问题，然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的___。如果一个算法P显式地调用自己则称为___。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为_____. [解析]递归法直接递归间接递归调用 7.算法中各操作之间的执行顺序称为_____。描述算法的工具通常有_____、_____ 、 _____。 [解析]控制结构传统流程图、N-S结构化流程图、算法描述语言 8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基 本单位，在计算机程序常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数据 项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入 5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 //四章算法 //说明 //sqstring——顺序串 listring——链串 //目录 //算法1:按字典顺序比较两个串s和t的大小(sqstring.cpp) //算法2:求串s中第一个最长的连续相同字符构成的平台(sqstring.cpp) //算法3:把串s中最先出现的子串"ab"改为"xyz"(listring.cpp) //算法4:BF算法(listring.cpp) //算法5:KMP算法(sqstring.cpp) //算法6:改进的KMP算法(sqstring.cpp) //算法 //算法1：按字典顺序比较两个串s和t的大小 #include"sqstring.cpp" int Strcmp(SqString s,SqString t) { int i,comlen; if (s.length 第一章绪论 一．选择题 1．数据结构被形式地定义为（K，R），其中K是①_B_的有限集合，R是K上的②_D_的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 2．算法分析的目的是①C，算法分析的两个主要方面是②A。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为(B) A．逻辑结构B．顺序存储结构 C．链表存储结构D．以上都不对 4．数据结构中，在逻辑上可以把数据结构分成：( C ）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（A ）。 A．存储密度大B．插入运算方便 C．删除运算方便D．可方便地用于各种逻辑结构的存储表示 6．数据结构研究的内容是（D ）。 A．数据的逻辑结构B．数据的存储结构 C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面 7．链式存储的存储结构所占存储空间（A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 8．一个正确的算法应该具有5 个特性，除输入、输出特性外，另外3 个特性是（A ）。 A．确定性、可行性、有穷性B．易读性、确定性、有效性C．有穷性、稳定性、确定性D．可行性、易读性、有穷性9．以下关于数据的逻辑结构的叙述中正确的是（A）。 A．数据的逻辑结构是数据间关系的描述 B．数据的逻辑结构反映了数据在计算机中的存储方式 C．数据的逻辑结构分为顺序结构和链式结构 D．数据的逻辑结构分为静态结构和动态结构 10．算法分析的主要任务是（C ）。 A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系 二．解答 设有一数据的逻辑结构为：B=(D, S)，其中： D={d1, d2, …, d9} S={ 第5章常用数据结构与算法 5.1 字符串 字符串(string)类型直接从object类派生,它是被密封的,不能再有派生类。 5.1.1字符串类型定义 1.定义 2.两种字符串: (1)规则字符串:由包含在双引号中的零个或多个字符组成,并且可以 包含简单转义序列、十六进制转义序列、Unicode转义序列。 如：”hello” (2)逐字字符串:由@后跟双引号字符、零个或多个字符组成。如： @”hello” 区别：规则字符串要对字符串中的转义序列进行解释 逐字字符串除了对双引号进行解释之外，对其他字符，原样显示。例如：string str1;//定义字符串类型 string str2=”hello,word”//规则字符串hello,word string str3=@”hello,word”//逐字字符串hello,word string str4=”hello\tword”//规则字符串hello word string str5=@”hello\tword”//逐字字符串hello\tword 5.1.2 字符串类型的应用 1．判断一个字符串的长度 在C#中，字符串类型有一个Length属性，利用它可得到一个字符串变量或 一个字符串常量的长度。 例如： string str=”abcdefghijk”;// str变量中的串由11个字符组成Console.WriteLine(str.Length); //str变量的长度为11 Console.WriteLine(”abcdefghijk”.Length);//直接取串的长度为11 2.比较两个字符串是否相等 C#直接重载了”==”和”!=”两个运算符处理两个字符串是否相等。 在C#中，字符串相等的条件： 两个字符串都为空串（null）或两个字符串实例长度相同，并且每个字符位置中的字符都相同。 例如： string str1=”abcdefghijk”; string str2=”abcdefghijk”; Console.WriteLine(str1==str2); //str1和str2相等，得到真值true 3.字符串的连接 直接使用”+”运算符. string str1=”abcde”; str1+=”fghijk”; Console.WriteLine(str1); //str1的值为”abcdefghijk” 4.在字符串中插入另一字符串 使用字符串类的Insert方法。该方法的参数有两个,前一个参数是新字符串要插入的位置,后一个参数是要插入的字符串。 绪论单元测试 1 【判断题】(2分) 数据结构主要研究内存中数据组织和数据处理方法。 A. 错 B. 对 正确 本题总得分2分 2 【多选题】(2分) 数据结构与算法课程的学习目标是（）。 A. 理解并掌握典型数据结构及七本运算的实现算法。 B. 提高计算思维能力 C. 能利用所学数据结构和算法知识解决实际问题。 D. 具备基本的算法设计与分析能力。 3 【多选题】(2分) 数据结构课程的学习重点是（） A. 掌握各种数据结构的逻辑特性 B. 掌握基本的算法分析方法。 C. 掌握各种数据结构的存储结构的设计与实现。 D. 掌握基本的算法设计方法 第一章测试 1 【多选题】(3分) 算法分析主要分析的是算法的（） A. 空间复杂性 B. 时间复杂性 C. 正确性 D. 可读性 2 【判断题】(2分) 数据结构是数据对象与对象中数据元素之间关系的集合。 A. 错 B. 对 3 【判断题】(2分) 数据元素是数据的最小单位。 A. 错 B. 对 4 【判断题】(2分) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 A. 对 B. 错 5 【判断题】(3分) 算法和程序没有区别，所以在数据结构中二者是通用的。 A. 错 B. 对 6 【单选题】(3分) 数据结构中，与所使用的计算机无关的是数据的（）结构 A. 存储 B. 物理与存储 C. 逻辑 D. 物理 7 【单选题】(3分) 算法分析的目的是（） A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 8 【单选题】(3分) 设x,y,n为正整数，下列程序片段的渐进时间复杂度是（）x=1；y=1； while（x+y<=n）{ if（x>y）y++； elsex++；} A. O(n2) B. O(log2n) C. O(n) D. O((2/3)n) 9 【多选题】(3分) 在数据结构中，从逻辑上可以把数据结构分成（） 《数据结构与算法》(张晓莉)习题：选择题、判断题(同名10048) 第一章绪论 1. 从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2. 在下面的程序段中，对x的赋值语句的频度为（ C ）。 For（k=1；k<=n；k++） For（j=1；j<=n；j++） x=x＋1； A．O(2n) B．O(n) C．O(n2) D．O(log2n) 3. 采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ A ）。 A．一定连续B．一定不连续 C．不一定连续D．部分连续、部分不连续 4. 下面关于算法的说法，正确的是（ D ）。 A．算法的时间复杂度一般与算法的空间复杂度成正比 B．解决某问题的算法可能有多种，但肯定采用相同的数据结构 C．算法的可行性是指算法的指令不能有二义性 D．同一个算法，实现语言的级别越高，执行效率就越低 5. 在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。 A．正确性B．健壮性C．可读性D．可移植性 第二章线性表 1. 线性表是（ A ）。 A．一个有限序列，可以为空B．一个有限序列，不能为空 C．一个无限序列，可以为空D．一个无限序列，不能为空 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．n/2 B．（n＋1）/2 C．（n－1）/2 D．n 3．线性表采用链式存储时，其地址（ D ）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续与否均可以 4．用链表表示线性表的优点是（C）。 A．便于随机存取B．花费的存储空间较顺序存储少 C．便于插入和删除D．数据元素的物理顺序与逻辑顺序相同 第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 第五章数据结构与算法基础 5.1 数据结构与算法的概念 随着计算机科学与技术的发展，计算机技术已渗透到国民经济的各行各业和人们日常生活的方方面面。计算机已不仅用于数值计算，而更多地用于非数值计算，其加工处理的对象从纯粹的数值数据发展到字符、文字、表格、声音、图形、图像等各种复杂的具有一定结构的数据。为了更有效地处理各种数据，开发出高清晰、高效率、高可靠的软件，就必须对处理数据的特性、数据间的关系以及数据在计算机中的表示与操作进行深入的研究。这就是“数据结构”这门学科形成和发展的背景。 5.1.1 数据结构基本概念 数据（data）是指计算机可以保存和处理的信息。 数据元素（data element）是构成数据的基本单位，在计算机程序中通常作为一个整体进行处理。一个数据元素可以由一个或多个数据项组成。数据元素也称为元素、结点（node）或记录（record）。 数据项（data item）是指数据中不可分割的、含有独立意义的最小单位，也称字段（field）或域。 【例5－1】实现对某高校的教职工档案进行管理，设每位教职工档案内容包括工号、姓名、性别、年龄、职称等，则每位教职工的工号、姓名、性别、年龄、职称等各项就是数据项，每位教职工的所有数据项就构成一数据元素。 显然，如果没有将属于同一个人的有关数据项集中构成一数据元素、数据元素之间没有按照一定的规则组织起来，则对这些数据的操作将是十分困难的甚至是无法实现的。 数据结构是研究数据及数据元素之间关系及其操作实现算法的一门学科。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。它包括三个方面的内容：数据的逻辑结构、数据的存储结构和数据的运算。 1.数据的逻辑结构 数据的逻辑结构就是数据元素之间的逻辑关系。可表示为： Data_Structure =(D，R) 其中，D是组成数据的数据元素的有限集合，R是数据元素之间的关系集合。 根据数据元素之间关系的不同特性，数据结构可分为线性数据结构和非线性数据结构。 （1）线性结构的逻辑特征是除第一个结点和最后一个结点外，其他所有结点都有且只有一个直接前趋和一个直接后继结点。 （2）非线性结构的逻辑特征是一个结点可能有多个直接前趋和直接后继。 2.数据的存储结构 数据的逻辑结构是面向应用问题的，是从用户角度看到的数据的结构。数据必须在计算机内存储，数据的存储结构(storage structure)是研究数据元素和数据元素之间的关系如何在计算机中表示，是逻辑数据的存储映像，它是面向计算机的。 实现数据的逻辑结构到计算机存储器的映像有多种不同的方式。通常，数据在存储器中的存储有四种基本的映像方法。 （1）顺序存储结构（Sequential Storage Structure）：把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，它主要用于线性数据结构，非线性的数据结构也可以通过某种线性化 1. 从逻辑上可以把数据结构分为（ C ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 在下面的程序段中，对x的赋值语句的频度为（ C ）。 For（k=1；k<=n；k++） For（j=1；j<=n；j++） x=x＋1； n) A．O(2n) B．O(n) C．O(n2) D．O(log 2 3. 采用顺序存储结构表示数据时，相邻的数据元素的存储地址（ A ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续、部分不连续 4. 下面关于算法的说法，正确的是（ D ）。 A．算法的时间复杂度一般与算法的空间复杂度成正比 B．解决某问题的算法可能有多种，但肯定采用相同的数据结构 C．算法的可行性是指算法的指令不能有二义性 D．同一个算法，实现语言的级别越高，执行效率就越低 5. 在发生非法操作时，算法能够作出适当处理的特性称为（ B ）。 A．正确性 B．健壮性 C．可读性 D．可移植性 第二章线性表 1. 线性表是（ A ）。 A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（ A ）个元素。 A．n/2 B．（n＋1）/2 C．（n－1）/2 D．n 3．线性表采用链式存储时，其地址（ D ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续与否均可以 4．用链表表示线性表的优点是（ C ）。 A．便于随机存取 B．花费的存储空间较顺序存储少 C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同 5．链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ C ）存储方式最节省运算时间。 A．单链表 B．双链表 C．单循环链表 D．带头结点的双向循环链表6．下面关于线性表的叙述，错误的是（ B ）。 《数据结构与算法设计》习题册 第一章绪论 一、单项选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运 算等的学科。 ①A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象 ②A. 结构 B. 关系 C. 运算 D. 算法 2.数据结构被形式地定义为（K，R），其中K是①的有限集，R是K上的②有限集。 ①A. 算法 B. 数据元素 C. 逻辑结构 D. 数据操作 ②A. 操作 B. 存储 C. 映象 D. 关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 4.数据结构在计算机内存中的表示是指。 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 5.在数据结构中，与所使用的计算机无关的是数据的结构。 A. 逻辑 B. 存储 C. 逻辑和存储 D. 物理 6.算法分析的目的是①，算法分析的两个主要方面是②。 ①A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ②A. 空间复杂度和时间复杂度 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 7.计算机算法指的是①，它必须具备输入、输出和②等5个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 8.在以下叙述中，正确的是。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 9.在决定选取何种存储结构时，一般不考虑。 A. 各结点的值如何 B. 结点个数的多少 C. 对数据有哪些运算 D. 所用编程语言实现这种结构是否方便 10.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。 第四章栈和队列 一、选择题 1．对于栈操作数据的原则是（B ）。 A．先进先出B．后进先出C．后进后出D．不分顺序 2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（ B ）。 A．不确定B．n-i+1 C．i D．n-i 3．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ） A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 4．设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。 A．1，2，4，3，B．2，1，3，4，C．1，4，3，2，D．4，3，1，2，E．3，2，1，4， 5．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。 A．a，c，b，d B．b, c，d，a C．c, d，b, a D．d, c，a，b 6．设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B．YZX C．ZXY D．ZYX 7．输入序列为ABC，可以变为CBA时，经过的栈操作为（B ）A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 8．若一个栈以向量V[1．．n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( C )。 A．top:=top+1; V [top]:=x B．V [top]:=x; top:=top+1 C．top:=top-1; V [top]:=x D．V [top]:=x; top:=top-1 10．栈在（ D ）中应用。 A．递归调用B．子程序调用C．表达式求值D．A，Ｂ，Ｃ11．一个递归算法必须包括（ B ）。 《数据结构与算法》廖明宏课后答案第一次作业(第2章) 4.List Combine(List &L1,List &L2) { LNode *ap1,*ap2,*p; ap1=L1->next; ap2=L2->next; if(ap1->element 以在链表的每个节点中增加一个代表链表元素总数的整型num。该环形链表的每个节点可说 明为: struct celltype{ Elementtype element; celltype *next; int num; }List; 顺时针方向查找就按照普通单向链表的查找;逆时针方向查找不是直接一步就达到，逆时针 查找当前节点的下一个节点可以通过顺时针转一圈来达到，代表元素总数的整型num就决 定了p=p->next(p为当前节点)所需循环的次数，最终达到逆时针查找的目的。顺时针访问表的每个节点的算法为: void TravelList(List la) { List p=la->next; int i=0; while(i 18.void R(List la,elementtype x) { LNode* p=la->next; LNode* q=la->next; int n=1; while(p-next!=NULL && p->data!=x) { p=p->next; n++; } if(p==NULL) { LNode *s; int j=0; while(q && j数据结构作业系统_第五章答案
数据结构 习题 第一章 绪论
数据结构与算法第1章参考答案
数据结构第五章自测题及解答
《数据结构与算法 Python精品课程》第二章：算法分析
全国计算机二级考试 数据结构与算法
大数据结构与算法设计知识点
数据结构第五章算法
数据结构与算法习题库(考前必备)
第5章 常用数据结构与算法
智慧树知道网课《数据结构与算法》课后章节测试满分答案
《数据结构与算法》(张晓莉)习题：选择题、判断题(同名10048)
数据结构与算法习题及答案
第五章 数据结构与算法基础
数据结构与算法习题：选择题、判断题
数据结构习题汇编01 第一章 绪论 试题
数据结构及应用算法教程习题第四章 栈和队列
《数据结构与算法》廖明宏课后答案
- 数据结构(1,2,3章)课后题答案
- (完整版)数据结构作业系统_第二章答案
- 数据结构与算法习题讲解(全)
- 数据结构与算法分析第二章算法分析精品PPT课件
- 数据结构与算法习题册参考答案
- 数据结构与算法分析第2章线性表2精品PPT课件
- 数据结构Java版第二章习题
- 数据结构与算法习题库(考前必备)
- 919518-数据结构与算法(第2版)-第2章(PPT)5节
- 《数据结构与算法》习题：选择题、判断题
- 2数据结构与算法分析_第二章、线性表习题及答案
- 数据结构与算法分析 第2章
- 数据结构与算法总复习题
- 《数据结构与算法》廖明宏课后答案
- 顾为兵《数据结构与算法》第二章作业解析
- 《数据结构与算法》习题选择题判断题
- 大数据结构与算法设计知识点
- 《数据结构与算法》廖明宏课后答案
- 数据结构第二章课后答案解析
- 第2章 数据结构与算法