当前位置：文档之家 › 数据结构1--3章

数据结构1--3章

  • 格式：doc
  • 大小：109.50 KB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

数据结构第1-3章作业参考答案(严薇敏,吴伟民编著)

数据结构第1-3章作业参考答案(严薇敏,吴伟民编著)

操作结果 构造一个有理数 R，元素 r1, r2 分 被赋 参数 v1, v2 的值 DestroyRational (&R) 初始条件 有理数 R 已存在 操作结果 销毁有理数 R Get(R, k, &e) 初始条件 有理数 R 已存在，1 k 2 操作结果 用 e 返回有理数 R 的第 k 元的值 Put(&R, k, e) 初始条件 有理数 R 已存在，1 k 2，若 k=2，则 e≠0 操作结果 用 e 更新有理数 R 的第 k 元的值 IsAscending(R) 初始条件 有理数 R 已存在 操作结果 若有理数 R 的两个元素按升序排列，则返回 1，否则返回 0 IsDescending(R) 初始条件 有理数 R 已存在 操作结果 若有理数 R 的两个元素按降序排列，则返回 1，否则返回 0 Max(R, &e) 初始条件 有理数 R 已存在 操作结果 用 e 返回有理数 R 的两个元素中值较大的一个 Min(R, &e) 初始条件 有理数 R 已存在 操作结果 用 e 返回有理数 R 的两个元素中值较小的一个 }ADT Rational
}//Descending
//使 x y //使 temp>z
算法二如 ( 算法是冒泡排序算法)
void Descending(){ scanf(x, y, z);
if(x<y) x ↔ y ; if(y<z) y ↔ z ; if(x<y) x ↔ y ;
printf(x, y, z); }//Descending
第 2 页 共 12 页
操作结果 求有理数 R1 的绝对值，用有理数 R 返回 NegativeRational(&R, R1) 初始条件 有理数 R1 已存在 操作结果 求有理数 R1 的相 数，用有理数 R 返回 }ADT Rational

数据结构习题1-3及其答案

数据结构习题1-3及其答案

1.设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。

(1) i=1; k=0;while(i<n){ k=k+10*i;i++;}(2) i=1; j=0;while(i+j<=n){if (i>j) j++;else i++;}(3)x=n; // n>1while (x>=(y+1)*(y+1))y++;第二章线性表2.1下述算法的功能是什么?LinkList Demo(LinkList L){ // L是无头结点单链表ListNode *Q,*P;if(L&&L->next){Q=L;L=L->next;P=L;while (P->next) P=P->next;P->next=Q; Q->next=NULL;}return L;}// Demo答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

2.9设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。

在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。

算法如下：//顺序表存储结构如题2.7void InsertIncreaseList( Seqlist *L , Datatype x ){int i;if ( L->length>=ListSize)Error(“overflow");for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--)L->data[ i ]=L->data[ i ] ; //比较并移动元素L->data[ i ] =x;L -> length++;}2.14已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min和max是两个给定的参数。

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)

《数据结构》第二版严蔚敏课后习题作业参考答案(1-7章)【第一章绪论】1. 数据结构是计算机科学中的重要基础知识，它研究的是如何组织和存储数据，以及如何通过高效的算法进行数据的操作和处理。

本章主要介绍了数据结构的基本概念和发展历程。

【第二章线性表】1. 线性表是由一组数据元素组成的数据结构，它的特点是元素之间存在着一对一的线性关系。

本章主要介绍了线性表的顺序存储结构和链式存储结构，以及它们的操作和应用。

【第三章栈与队列】1. 栈是一种特殊的线性表，它的特点是只能在表的一端进行插入和删除操作。

本章主要介绍了栈的顺序存储结构和链式存储结构，以及栈的应用场景。

2. 队列也是一种特殊的线性表，它的特点是只能在表的一端进行插入操作，而在另一端进行删除操作。

本章主要介绍了队列的顺序存储结构和链式存储结构，以及队列的应用场景。

【第四章串】1. 串是由零个或多个字符组成的有限序列，它是一种线性表的特例。

本章主要介绍了串的存储结构和基本操作，以及串的模式匹配算法。

【第五章数组与广义表】1. 数组是一种线性表的顺序存储结构，它的特点是所有元素都具有相同数据类型。

本章主要介绍了一维数组和多维数组的存储结构和基本操作，以及广义表的概念和表示方法。

【第六章树与二叉树】1. 树是一种非线性的数据结构，它的特点是一个节点可以有多个子节点。

本章主要介绍了树的基本概念和属性，以及树的存储结构和遍历算法。

2. 二叉树是一种特殊的树，它的每个节点最多只有两个子节点。

本章主要介绍了二叉树的存储结构和遍历算法，以及一些特殊的二叉树。

【第七章图】1. 图是一种非线性的数据结构，它由顶点集合和边集合组成。

本章主要介绍了图的基本概念和属性，以及图的存储结构和遍历算法。

【总结】1. 数据结构是计算机科学中非常重要的一门基础课程，它关注的是如何高效地组织和存储数据，以及如何通过算法进行数据的操作和处理。

本文对《数据结构》第二版严蔚敏的课后习题作业提供了参考答案，涵盖了第1-7章的内容。

数据结构1-3章习题答案2013

数据结构1-3章习题答案2013
{sNode *p=HL;
while(p->next!=NULL)
p=p->next;
temp=p->data;
delete p;
return temp;
}
4、数据结构简单地说是指数据以及相互之间的联系。
5、算法应具备以下5个特性：有穷性、正确性、可行性、输入和输出。
6、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(素的个数远远少于零元素的个数。
8、的运算规则为后进先出，队列的运算规则为先进先出。
C.(rear+1) %n= =frontD. (rear-1)%n= = front
5、下列是顺序存储线性表排序的算法
void Sort(List& L)
{
int i,j;
ElemType x;
for(i=1;i<L.size;i++)
{
x=L.list[i];
for(j=i-1;j>=0;j--)
}
不考虑健壮性条件，写出下列出队算法中缺失的语句：
ElemType OutQueue(struct QueueSq* Q)
{…
Q->front=(Q->front+1)%Q->MaxSize;
return Q->queue[Q->front];
…
}
参考以上两算法和数据结构，写出队满的条件：
(Q->rear+1)%Q->MaxSize==Q->front
和队空的条件：
Q->front==Q->rear
六、用f(n)=2n为例，说明栈与递归算法之间的关系。

数据结构1-3章习题

数据结构1-3章习题

一、选择题1、在数据结构中。

与所使用的计算机无关的是（D ）。

A、存储结构B、物理结构C、物理和存储结构D、逻辑结构2、非线性结构中每个结点（D）。

A、无直接前驱结点B、只有一个直接前驱和直接后继结点C、无直接后继结点D、可能有多个直接前驱和多个直接后继结点3、可以把数据的逻辑结构划分成（D ）。

A、内部结构和外部结构B、动态结构和静态结构C、紧凑结构和非紧凑结构D、线性结构和非线性结构4、算法指的是（D ）。

A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列5、在决定选取何种存储结构时，一般不考虑（A ）。

A、各结点的值如何B、结点个数的多少C、对数据有哪些运算D、所用编程语言实现这种结构是否方便6、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（C ）。

A、数据的处理方法B、数据元素的类型C、数据元素之间的关系D、数据的存储方法7、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ B ）。

A、数据元素具有同一特点B、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致C、每个数据元素都一样D、数据元素所包含的数据项的个数要相等8、以下说法正确的是（A ）。

A、数据元素是数据的基本单位B、数据项是数据的基本单位C、数据结构是带结构的数据项的集合D、一些表面上很不相同的数据可以有相同的逻辑结构二、简答题：下面是几种数据的逻辑结构)S=，分别画出对应的数据D(R,逻辑结构，并指出它们分别属于何种结构。

defcD==Rba}{r},,{,,,=fed<d<>>ba<racbbd,,,,,>,,},><(><){,=fee>d<><bb<racbdc,,,,,>},,<>,)(>{,<=fde<<d><>rba>cbcdadb,,,,,,},,,,><><(>,{)<一、选择题1、下面关于线性表的叙述中，错误的是（D ）。

《算法与数据结构》第1~3章 习题(包含了线性表、栈和队列,含答案)

《算法与数据结构》第1~3章 习题(包含了线性表、栈和队列,含答案)
{p=p1; p1=p1->next; s2=s2+1; delete(p) }; else if(p1->data>p2->data) p2=p2->next; else (p1->data==p2->data)
{ p=p1; p1=p1->next; p->next= pa->next; pa->next= p; p2= p2->next;s1=s1+1;};
的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是(C)。
A． 6 B. 4 C. 3 D. 2
13.若用一个大小为6的数组来实现循环队列，且当前rear和
front的值分别为0和3，当从队列中删除一个元素，再加入两个
元素后，rear和front的值分别为多少？(B)
A. 1和 5 B. 2和4 C. 4和2 D. 5和1
10. 表达式3* 2^(4+2*2-6*3)-5求值过程中当扫描到6时，对
象栈和算符栈为（ D ），其中^为乘幂 。
• 3,2,4,1,1；*^(+*- B. 3,2,8；*^- C. 3,2,4,2,2；*^(-
D. 3,2,8；*^(-
算法与数据结构
第1~3章 习题课
5 /31
11.循环队列存储在数组A[0..m]中，则入队时的操作为（D）。
C. q->next=p;q->pre=p->pre;p->pre->next=q;p->pre=q;
D. q->pre=p->pre;q->next=q;p->pre=q;p->pre=q; 5.栈的特点是（ B ）,队列的特点是（ A ）,栈和队列都是 （ A ）。若进栈序列为1,2,3,4 则（ C ）不可能是一个出栈序 列（不一定全部进栈后再出栈）；若进队列的序列为1,2,3,4 则 （ E ）是一个出队列序列。 ①, ②: A. 先进先出 B. 后进先出 C. 进优于出 D. 出 优于进

数据结构1-3习题

数据结构1-3习题

第1章绪论1.1选择题1. 算法的时间复杂度取决于（）A）问题的规模B）待处理数据的初态C）A和B2.计算机算法指的是解决问题的步骤序列，它必须具备（）这三个特性。

A）可执行性可移植性可扩充性B）可执行性、确定性、有穷性C）确定性、有穷性、稳定性D）易读性、稳定性、安全性5．从逻辑上可以把数据结构分为（）两大类。

A）动态结构、静态结构B）顺序结构、链式结构C）线性结构、非线性结构D）初等结构、构造型结构6．在下面的程序段中，对x的赋值的语句频度为（）for(i=0;i<n;i++)for(j=0;j<n;j++) x=x+1;A）O(2n) B）O(n) C．O(n2) D．O(log2n)7．下面的程序段中，n为正整数，则最后一行的语句频度在最坏情况下是（）for(i=n-1;i>=1;i--)for(j=1;j<=i;j++)if (A[j]>A[j+1])A[j]与A[j+1]对换；A. O（n）B）O(nlog2n) C）O(n3) D）O(n2)1.2填空题2. 对于给定的n个元素,可以构造出的逻辑结构有_____________，_____________，_____________，_____________四种。

4．数据结构中评价算法的两个重要指标是_____________。

5. 数据结构是研讨数据的_____________和_____________，以及它们之间的相互关系，并对与这种结构定义相应的_____________，设计出相应的_____________。

6．一个算法具有5个特性：_____________、_____________、_____________，有零个或多个输入、有一个或多个输出。

9．已知如下程序段for(i=n;i>0;i--) {语句1}{ x=x+1; {语句2}for(j=n;j>=i;j--) {语句3}y=y+1; {语句4}}语句1执行的频度为_____________；语句2执行的频度为_____________；语句3执行的频度为_____________；语句4执行的频度为_____________。

数据结构第一章--绪论(严蔚敏版)

数据结构第一章--绪论(严蔚敏版)

解 T = (D, R ) D={A,B,a,b,c }
R是D上的关系的集合 是 上的关系的集合
A
B
a R={ P1,P2 } P1 ={<A,a>, <A,b>, <A,c>} P2 ={<B,a>, <B,b>, <B,c>}
b
c
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数可以表示为 a+bi 一个复数可以表示为 复数 C={a,b}
也可以表示成一个有序对 <a, b>
∴这里存在一种关系 P ={<a,b>} (只有一个有序对 只有一个有序对) 只有一个有序对
而R是C上的关系的集合 R={ P } 是 上的关系的集合
写出一个复数的数据结构 例3 写出一个复数的数据结构 Complex= (C , R) 解 一个复数的数据结构为 Complex= (C , R) 其中， 其中， C={a,b} R={ P } P ={<a,b>}
a b c
解 其数据结构可描述为 d e T = (D, R ) D是数据元素的集合 D={a,b,c,d,e} 是数据元素的集合
R是D上的关系的集合 R={ P } 是 上的关系的集合
P ={<a,b>,<a,c>,<b,d>,<b,e>}
例2
一小组有a,b,c 三个学生，一个导师A 一小组有a,b,c 三个学生，一个导师A 和一个辅导员B 和一个辅导员B，此小组的数据结构如图：
48
ADT 抽象数据类型名 { 数据对象： 数据对象：〈数据对象的定义〉 数据关系： 数据关系：〈数据关系的定义〉 基本操作： 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 基本操作名 初始条件：〈初始条件描述〉 初始条件： 操作结果：〈操作结果描述〉 操作结果

数据结构习题(1-2-3章)

数据结构习题(1-2-3章)

第一章绪论一．选择题1．下面关于算法说法正确的是（）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的2．以下哪一个术语与数据的存储结构无关？（）A．栈 B．哈希表 C．线索树 D．循环队列3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）A．算法执行一步就完成B．算法执行1秒钟就完成C．算法执行常数步就完成 D．算法执行可变步数就完成4．数据结构研究的内容是（）。

A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。

A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性6．以下关于数据的逻辑结构的叙述中正确的是（）。

A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构7．下列时间复杂度中最坏的是（）A．O(1) B．O(n) C．O(log2n） D．O(n2)8．算法的时间复杂度取决于（）A．待处理数据的初态 B．问题的规模C．程序本身所占的空间 D．问题的规模和待处理数据的初态二．综合应用题1.有下列运行时间函数：（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。

2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j){int m;if(i!=j){mergesort(i,m);mergesort(m+1,j);merge(i,j,m);//本函数时间复杂度为 O(n)}}第二章线性表一．选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。

数据结构课程1

数据结构课程1

-------------------
-------
-------
-------
-------
-------
这张表中的元素存在一个顺序关系，即谁在谁前，谁在谁 后的信息（即病人诊断顺序依次为张立，田方，……） 。 所以，可以用线性结构来刻画这种关系。。
例1-3 大学系级行政机构
大学系级行政机构，如图1.1所示：
数据结构的含义
因此可以认为，数据结构是介于数学、计算机硬件和计 算机软件三者之间的一门核心课程（如图1.1所示）。
数学
代数系统
编码理论 数据类型 算子关系
数据表示法
数据的操作 文件系统
存储装置
数据结构
硬件
数据存取
（ 计 算 机 系机器组织
统设计）
数据组织
信息检索
软件
（计算机程 序设计）
图1.1 “数据结构”所处的地位
3. 数据的操作
一般而言，必须对数据进行加工处理，才能得到问题的 解。在非数值性问题中，对数据的操作（或运算）已不限 于对数据进行加、减、乘、除等数学运算。数据的操作是 定义在逻辑结构上的，而操作的具体实现是在存储结构上 进行的。基本的数据操作主要有以下几种：
（1）查找：在数据结构中寻找满足某个特定条件的数据元 素的位置或值。
现实问
数学模
算法
程序
解
题
型
图1.8 计算机求解问题的流程
即首先要从现实问题出发，抽象出一个适当的数学模型，
然后设计一个求解此数学模型的算法，最后根据这个算法 编出程序，经过测试、排错、运行直至得到最终的解答。 （现实）问题、数学模型、算法和程序是问题求解过程中 出现的四个不同的概念。

数据结构1-3习题答案

数据结构1-3习题答案

课堂练习
1、在什么情况下用顺序表比链表好? 、在什么情况下用顺序表比链表好 2、画出执行下列各行语句后各指针及链表的 示意图。 示意图。 、 L=(LinkList) malloc (sizeof(LNode));//等价于 等价于L=new 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.8 在下面两列中，左侧是算法（关于问题规模） 的执行时间，右侧是一些时间复杂度。 的执行时间，右侧是一些时间复杂度。请用连 线的方式表示每个算法的时间复杂度。 线的方式表示每个算法的时间复杂度。 100n3 6n2-12n+1 1024 n+2log2n n(n+1)(n+2)/6 2n+1+100n
判断下述计算过程是否是一个算法： 2.4 判断下述计算过程是否是一个算法： Step1: 开始 Step2: n<=0; Step3: n=n+1; 重复步骤3; Step4: 重复步骤3; 结束; Step5: 结束; 该计算过程不是一个算法， 答：该计算过程不是一个算法，因为其不满足算法的 有穷性。 有穷性。
回顾
第一章知识要点： 第一章知识要点： • 基本概论：数据、数据元素、数据项、数据对象 基本概论：数据、数据元素、数据项、 • 数据结构(D,S) 数据结构(D,S)

数据结构概论1-3在线作业

数据结构概论1-3在线作业

一、单选:1.数据结构通常是研究数据的( )及它们之间的相互关系.A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为( )A.存储结构B.逻辑结构5C.顺序存储结构D.链式存储结构3.非线性结构是数据元素之间是存在的一种( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.非线性结构中,每个结点( )A.无直接前趋.B.只有一个直接前驱和后继C.只有一个直接前驱和个数不受限制的直接后继D.有个数不受限制的直接前驱和后继.5.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为算法的:A.时间效率B.空间效率C.硬件效率D.软件效率二、填空1、数据结构包括数据的_逻辑结构_,数据的_存储结构_,数据的__运算__,这三个方面的内容 .2、数据结构按逻辑结构可分为两大类,分别是__线性结构和非线性结构 _.3、数据的存储结构可用四种基本的存储方法表示,分别是__顺序、链式、索引、散列_.4、线性结构反映结点间的逻辑关系是_一对一关系_.非线性结构反映结点间的逻辑关系是多对多关系.5、一个算法的效率可分为时间效率和_空间效率_.三、简答：分别写出下列两个算法的时间复杂度.1、x=0;for(i=1;i<n;i++)for(j=i+1;j<=n;j++)x++;答：2、x=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;答：欧一、填空1、在栈中存取数据的原则是：_先进后出_2、在栈中，出栈操作的时间复杂度为：_ 0(1)3、栈与一般线性表的区别主要在于__栈只允许在表尾进行插入和删除操作_4、顺序栈是空栈的条件是：_ s.top=0_5、插入和删除只能在一端进行的线性表，称为：__受限线性表_6、设循环向量有m个元素，循环向量中有一个循环队列，在循环队列中设队头指针front指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。

数据结构严蔚敏完整版

数据结构严蔚敏完整版
图1-1 树形结构
例3：交通网络图
从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题，数据与数据成多对多的 关系，是一种非线性关系结构。
佛山
广州
中山
东莞
惠州
珠海
图1-2 网状结构
深圳
1.1.2 基本概念和术语
数据(Data) ：是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。
信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂，导致信息量剧增与信 息范围的拓宽，使许多系统程序和应用程序的规模很大， 结构又相当复杂。因此，必须分析待处理问题中的对象 的特征及各对象之间存在的关系，这就是数据结构这门 课所要研究的问题。
计算机求解问题的一般步骤
编写解决实际问题的程序的一般过程：
<基本操作名>(<参数表>) 初始条件： <初始条件描述> 操作结果： <操作结果描述>
– 初始条件：描述操作执行之前数据结构和参数应 满足的条件;若不满足，则操作失败，返回相应的出 错信息。
– 操作结果：描述操作正常完成之后，数据结构的 变化状况和 应返回的结果。
1.3 算法分析初步
1.3.1 算法
问题：必须先运行依据算法编制的程序；依赖软硬 件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。
与此相关的因素有： – 依据算法选用何种策略； – 问题的规模； – 程序设计的语言； – 编译程序所产生的机器代码的质量； – 机器执行指令的速度； 撇开软硬件等有关部门因素，可以认为一个特定算
数据元素(Data Element) ：是数据的基本单位，在 程序中通常作为一个整体来进行考虑和处理。

数据结构1

数据结构1

第 1 章 绪 论1.1 数据结构的兴起和发展一、数据结构起源于程序设计。

·程序设计的新问题：应如何组织待处理的数据以及数据之间的关系（结构）。

·70年代初，数据结构作为一门独立的课程开始进入大学课堂。

二、数据结构随着程序设计的发展而发展。

程序设计经历了三个阶段：无结构阶段、结构化阶段和面向对象阶段，相应地，数据结构的发展也经历了三个阶段：三、数据结构的发展并未终结。

1． 数据结构将继续随着程序设计的发展而发展；2． 面向各专门领域的数据结构得到研究和发展，各种空间数据结构也在探索中。

应用领域：科学计算；程序设计面向计算机 应用领域：科学计算与非数值处理；算法＋数据结构=程序 应用领域：更多地应用于非数值处理；（算法＋数据结构）=程序1.2 数据结构的研究对象例1-1 学籍管理问题例1-2 人——机对弈问题例1-3 教学计划编排问题表1-1 学生学籍登记表 (a) 井字棋的一个格局 (b) 对弈树的局部 图1-2 对弈问题中格局之间的关系1.3 数据结构的基本概念1.3.1 数据结构1. 数据：在计算机科学中是指所有能输入到计算机中并能被计算机程序识别和处理的符号集合。

2. 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

构成数据元素的不可分割的最小单位称为数据项。

3. 数据对象：是具有相同性质的数据元素的集合，是数据的子集。

4. 数据结构：是指相互之间存在一定关系的数据元素的集合。

按照视点的不同，数据结构分为逻辑结构和存储结构。

数据的逻辑结构是指数据元素之间逻辑关系的整体。

根据数据元素之间逻辑关系的不同，数据结构分为四类：⑴集合数据元素之间的关系是。

⑵线性结构数据元素之间的关系是。

⑶树结构数据元素之间的关系是。

⑷图结构数据元素之间的关系是。

数据的存储结构又称为物理结构，是数据及其逻辑结构在计算机中的表示。

有两种存储结构：顺序存储结构和链接存储结构。

数据结构第1-4章选择题(有答案)

数据结构第1-4章选择题(有答案)

第1章绪论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．栈第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A．110 B．108 C．100 D．120说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。

（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个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

数据结构(1-2-3章)课后题答案解析

数据结构(1-2-3章)课后题答案解析
西北大学可视化技术研究所
q=p; p=p->next; b->next=q; q->next=B; b=b->next; } else {//分出其他字符结点 q=p; p=p->next; c->next=q; q->next=C; c=c->next; } } }//结束
西北大学可视化技术研究所
A．双向链表
B．双向循环链表
C．单向循环链表 D．顺序表
（4）下列选项中， D 项是链表不具有的特点。
A．插入和删除运算不需要移动元素
B．所需要的存储空间与线性表的长度成正比
C．不必事先估计存储空间大小
D．可以随机访问表中的任意元素
西北大学可视化技术研究所
(5)在链表中最常用的操作是删除表中最后一个结点和 在最后一个结点之后插入元素，则采用 C 最 节省时间。
西北大学可视化技术研究所
8.假设两个按元素值递增有序排列的线性 表A和B，均以单链表作为存储结构，请 编写算法，将A表和B表归并成一个按元 素值递减有序排列的线性表C，并要求利 用原表（即A表和B表的）结点空间存放 表C。
西北大学可视化技术研究所
算法描述：要求利用现有的表A和B中的结 点空间来建立新表C，可通过更改结点的next 域来重新建立新的元素之间的线性关系。为保 证新表递减有序可以利用头插法建立单链表的 方法，只是新建表中的结点不用malloc，而只 需要从A和B中选择合适的点插入到新表C中即 可。
西北大学可视化技术研究所
1.3填空题： （1）变量的作用域是指 变量的有效范围 （2）抽象数据类型具有 数据抽象 、 信息隐 蔽 的特点。 （3）一种抽象类型包括 数据对象 、 结构 关系 和 基本操作 。

数据结构1-4章习题答案

数据结构1-4章习题答案

第1章概论习题参考解答一、填空题1、数据的逻辑结构是数据元素之间的逻辑关系，通常有下列4类：（）、（）、（）、（）。

【答】集合、线性结构、树型结构和图状结构。

2、数据的存储结构是数据在计算机存储器里的表示，主要有4种基本存储方法：（）、（）、（）、（）。

【答】顺序存储方法、链接存储方法、索引存储方法和散列存储方法。

二、选择题1、一个算法必须在执行有穷步之后结束，这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】B。

2、算法的每一步，必须有确切的定义。

也就是说，对于每步需要执行的动作必须严格、清楚地给出规定。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】C。

3、算法原则上都是能够由机器或人完成的。

整个算法好像是一个解决问题的“工作序列”，其中的每一步都是我们力所能及的一个动作。

这是算法的（）。

（A）正确性（B）有穷性（C）确定性（D）可行性【答】D。

三、简答题1、算法与程序有何异同？【答】尽管算法的含义与程序非常相似，但两者还是有区别的。

首先，一个程序不一定满足有穷性，因此它不一定是算法。

例如，系统程序中的操作系统，只要整个系统不遭受破坏，它就永远不会停止，即使没有作业要处理，它仍处于等待循环中，以待一个新作业的进入。

因此操作系统就不是一个算法。

其次，程序中的指令必须是计算机可以执行的，而算法中的指令却无此限止。

如果一个算法采用机器可执行的语言来书写，那么它就是一个程序。

2、什么是数据结构？试举一个简单的例子说明。

【答】数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（即数据元素的组织形式）。

例如，队列的逻辑结构是线性表（先进先出）；队列在计算机中既可以采用顺序存储也可以采用链式存储；对队列可进行删除、插入数据元素以及判断是否为空队列、将队列置空等操作。

3、什么是数据的逻辑结构？什么是数据的存储结构？【答】数据元素之间的逻辑关系，也称为数据的逻辑结构。

1-3-数据结构——从概念到C++实现(第3版)-王红梅-清华大学出版社

1-3-数据结构——从概念到C++实现(第3版)-王红梅-清华大学出版社

从 概 念
别并做出处理，而不是产生错误动作或陷入瘫痪。
到 实 现
）
（3）可理解性：算法容易理解和实现。
清 华
大
学
（4）抽象分级：用合适的抽象分级来组织表达算法的思想， 启发式规则7±2。
出 版
社
（5）高效性：具有较短的执行时间并占用较少的辅助空间。
米勒原则：人类的短期记忆能力一般限于一次记忆 5～9 个对象
数 据
48和36的最大公约数为2×2×3=12。
结 构
（
从
【算法】设两个自然数是m和n，算法如下：
概 念
到
实
步骤 1：找出 m 的所有质因子
现
不满足确定性、有穷性！
） 清
步骤 2：找出 n 的所有质因子
华 大
学
步骤 3：从第 1 步和第 2 步得到的质因子中找出所有公因子
出 版
社
步骤 4：将找到的所有公因子相乘，结果即为 m 和 n 的最大公约数
） 清
华
姚期智（Chi-Chih Yao）发明了伪随机数的生成算法以及加密/解密算法；
大 学
出
Sutherland发明的图形图像算法改善了屏幕刷新的文件显示；
版 社
Dijkstra发明了单源点的最短路径算法Dijkstra算法；
Wilkinson在数值线性代数方面发现很多有意义的算法；
Blum发现了著名的算法设计技术——分支限界法……
2. 锅里放油
概 念 到
3. 把鸡蛋倒进去炒熟
实 现 ）
4. 加入葱花
清 华
5. 把柿子放进去放少许盐和味精
大 学 出
6. 翻炒几下出锅装盘
版 社
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

第1章绪论一、选择题1. 算法的计算量的大小称为计算的（）。

2. 算法的时间复杂度取决于（）3.计算机算法指的是（），它必须具备（）这三个特性。

4．一个算法应该是（）。

5. 下面关于算法说法错误的是（）A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D. 以上几个都是错误的6. 下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构C．线性结构、非线性结构 D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（）。

A．循环队列 B. 链表 C. 哈希表 D. 栈9．以下数据结构中，哪一个是线性结构（）？A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串10．以下那一个术语与数据的存储结构无关？（）A．栈 B. 哈希表 C. 线索树 D. 双向链表11．在下面的程序段中，对x的赋值语句的频度为（）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与A[j+1]对换；其中 n为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n）B. O(nlogn)C. O(n3)D. O(n2)13．以下哪个数据结构不是多型数据类型（）A．栈 B．广义表 C．有向图 D．字符串14．以下数据结构中，（）是非线性数据结构A．树 B．字符串 C．队 D．栈15. 下列数据中，（）是非线性数据结构。

A．栈 B. 队列 C. 完全二叉树 D. 堆16．连续存储设计时，存储单元的地址（）。

A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）。

A．顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题1. 数据元素是数据的最小单位。

( )2. 记录是数据处理的最小单位。

( )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( )4．算法的优劣与算法描述语言无关，但与所用计算机有关。

( )5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

( )6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。

( )7．程序一定是算法。

( )8．数据的物理结构是指数据在计算机内的实际存储形式。

( )9. 数据结构的抽象操作的定义与具体实现有关。

( )10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。

( )11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

( )12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。

( )13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( )三、填空1．数据的物理结构包括的表示和的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），__（4）_四种。

3．数据的逻辑结构是指。

4．一个数据结构在计算机中称为存储结构。

5．抽象数据类型的定义仅取决于它的一组__（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不影响其外部使用。

6．数据结构中评价算法的两个重要指标是7. 数据结构是研讨数据的_（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的_（3）_，设计出相应的（4）_。

8．一个算法具有5个特性: （1）、（2）、（3），有零个或多个输入、有一个或多个输出。

9．已知如下程序段FOR i:= n DOWNTO 1 DO {语句1}BEGINx:=x+1； {语句2}FOR j:=n DOWNTO i DO {语句3}y:=y+1; {语句4}END；语句1执行的频度为（1）；语句2执行的频度为（2）；语句3执行的频度为（3）；语句4执行的频度为（4）。

10．在下面的程序段中，对ｘ的赋值语句的频度为______（表示为n的函数）FOR i：＝１ TO n DOFOR j：＝１TO i DOFOR k：＝1 TO j DOｘ：＝ｘ＋delta；11.下面程序段中带下划线的语句的执行次数的数量级是：i：=1； WHILE i<n DO i：=i*2;12. 下面程序段中带下划线的语句的执行次数的数量级是( )。

i:=1;WHILE i<n BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；13. 下面程序段中带有下划线的语句的执行次数的数量级是( )i：=n*n WHILE i<>1 DO i:=i div 2;14. 计算机执行下面的语句时，语句s的执行次数为 _______ 。

FOR(i=l；i<n-l；i++)FOR(j=n;j>=i;j--)s;15. 下面程序段的时间复杂度为________。

(n>1)sum=1；for (i=0;sum<n;i++) sum+=1;16．设m.n均为自然数，m可表示为一些不超过n的自然数之和，f(m,n)为这种表示方式的数目。

例f(5,3)=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。

①以下是该函数的程序段，请将未完成的部分填入，使之完整int f(m,n)int m,n;{ if(m==1)return (1) ;if(n==1){return (2) ;}if(m<n){return f(m,m);}if (m==n){return 1+ (3) ;}return f(m.n-1)+f(m-n, (4) );}②执行程序，f(6,4)= 。

17. 在有n个选手参加的单循环赛中，总共将进行______场比赛。

四、应用题1. 数据结构是一门研究什么内容的学科？2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3. 数据类型和抽象数据类型是如何定义的。

二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4. 回答问题（每题2分）（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。

这样的说法对吗？举例说明之。

（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。

这样说法对吗？举例说明之。

（4）评价各种不同数据结构的标准是什么？5．评价一个好的算法，您是从哪几方面来考虑的？6．解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？8．对于一个数据结构，一般包括哪三个方面的讨论？9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？10. 若将数据结构定义为一个二元组（D，R）,说明符号D，R 应分别表示什么？11．数据结构与数据类型有什么区别？12．数据的存储结构由哪四种基本的存储方法实现？13．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？14. 运算是数据结构的一个重要方面。

试举一例，说明两个数据结构的逻辑结构和存储方式完全相同，只是对于运算的定义不同。

因而两个结构具有显著不同的特性，是两个不同的结构。

15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么? 16. 试举一例，说明对相同的逻辑结构,同一种运算在不同的存储方式下实现，其运算效率不同。

17. 有实现同一功能的两个算法A1和A2，其中A1的时间复杂度为Tl=O(2n)，A2的时间复杂度为T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。

18．设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。

19. 写出下面算法中带标号语句的频度。

TYPE ar=ARRAY[1..n] OF datatype;PROCEDURE perm ( a: ar; k, n: integer);VAR x: datatype; i:integer;BEGIN（1）IF k=nTHEN BEGIN（2）FOR i:=1 TO n DO（3）write (a[i]);writeln;ENDELSE BEGIN（4） FOR i:=k TO n DO（5）a[i]:=a[i]+i*i;（6） perm (a, k+1, n);END;END;设k的初值等于1。

20. 分析下面程序段中循环语句的执行次数。

i:=0;s:=0;n:=100;REPEATi:=i+1;s:=s+10*i;UNTIL NOT((i<n) AND (s<n));21．下列算法对一n位二进制数加1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。

TYPE num=ARRAY [1..n] of [0..1]；PROCEDURE Inc （VAR a：num）；VAR i：integer；BEGIN i：=n；WHILE A[i]=1 DOBEGIN A[i]：=0； i：=i-1；END；END；A[i]：=1；END Inc；22. 阅读下列算法，指出算法A的功能和时间复杂性PROCEDURE A (h,g:pointer);(h,g分别为单循环链表（single linked circular list）中两个结点指针) PROCEDURE B(s,q:pointer)；VAR p:pointer;BEGINp:=s;WHILE p^.next<>q DO p:=p^.next;p^.next:=s;END;(of B)BEGINB(h,g); B(g,h);END;（of A）23. 调用下列C函数f(n)或PASACAL函数f(n) 回答下列问题 :（1）试指出f(n)值的大小，并写出f(n) 值的推导过程;（2）假定n= 5，试指出f(5)值的大小和执行f(5)时的输出结果。