数据结构第2阶段练习题

评分标准：有向图、无向图两种存储方式各占4分。
3.建立平衡二叉树过程如图2所示(图中加阴影的结点表示要调整的结点)。
图2构造平衡二叉树过程
评分标准：每次调整占1分。
4.答：不能。因为在这里，二分查找只减少了关键字间的比较次数，而记录的移动次数不变，时间的复杂度仍为O(n2)。
评分标准：答对“不能”占3分，说明理由占5分。
A.872B.860
C.868D.864
8.一个具有1025个结点的二叉树的高h为。
A.11B.10
C.11～1025D.12～1024
9.一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为。
A.ACBEDB.DECAB
C.DEABCD.CEDBA
10.对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列。
2.给出如下各种情况下求任意一个顶点的度的过程（只需文字描述）：（8分）
（1）含n个顶点的无向图采用邻接矩阵存储；
（2）含n个顶点的无向图采用邻接表存储；
（3）含n个顶点的有向图采用邻接矩阵存储；
（4）含n个顶点的有向图采用邻接表存储。
3.将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树。（要求画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出是什么类型的调整，12分）
A.输出第i(1≤i≤n)个元素值
B.交换第1个元素与第2个元素的值
C.顺序输出这n个元素的值
D.输出与给定值x相等的元素在线性表中的序号
4.设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是1，2，3，…，n，若p3=3，则p1的值。
A.可能是2B.一定是2

数据结构课程第二章部分习题解答第二章数组2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。

下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。

请以n = 9, s= 1, m= 5为例，人工模拟Josephus的求解过程以求得问题的解。

【解答】出局人的顺序为5, 1, 7, 4, 3, 6, 9, 2, 8。

2-2 试编写一个求解Josephus问题的函数。

用整数序列1, 2, 3, ……, n表示顺序围坐在圆桌周围的人，并采用数组表示作为求解过程中使用的数据结构。

然后使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。

最后分析所完成算法的时间复杂度。

【解答】函数源程序清单如下：void Josephus( int A[ ], int n, s, m ) {int i, j, k, tmp;if ( m== 0 ) {cout<< "m= 0是无效的参数！" << endl;return;}for ( i = 0;i < n;i++ ) A[i] =i + 1;/*初始化，执行n次*/ i = s- 1;/*报名起始位置*/for ( k = n;k > 1;i-- ) {/*逐个出局，执行n-1次*/if ( i ==k ) i = 0;i = ( i + m- 1 ) % k;/*寻找出局位置*/if ( i != k-1 ) {tmp = A[i]; /*出局者交换到第k-1位置*/for ( j = i;j < k-1;j++ )A[j] = A[j+1];A[k-1] = tmp;}}for ( k = 0;k < n / 2;k++ ) {/*全部逆置, 得到出局序列*/tmp= A[k];A[k] = A[n-k+1];A[n-k+1] = tmp;}}例：n = 9, s = 1, m = 50 1 2 3 4 5 6 7 8第4局, i= 2 k第3人出局, i= 1 k第6人出局, i= 1 k第9人出= 2 k第2人出局, i= 0第8人出局, i= 0最终出局顺序例：n = 9, s = 1, m = 0报错信息m= 0是无效的参数！例：n = 9, s = 1, m = 100 1 2 3 4 5 6 7 8第1人出局, i= 0第3人出局, i= 1第6人出局, i = 3 第2人出局, i = 0 第9人出局, i = 4k第5人出局, i = 1 第7人出局, i = 1k第4人出局, i= 0第8人出局, i= 0最终出局顺序当m= 1时，时间代价最大。

departThr( Link L , Link *LA, Link *LN; Link *LO) { Node *q, *t; q=L->next; (*LA)=L; (*LA)->next=(*LA); (*LN)=(Link ) malloc(sizeof(Node)); (*LN)->next=(*LN); (*LO)=(Link ) malloc(sizeof(Node)); (*LO)->next=(*LO);
LinkList combineAB( LinkList ha,LinkList hb ) { Node *p,*q,*r; p=ha->next; q=hb->next; r=ha; while(p!=NULL && q!=NULL) { r->next=p; r =p; p=p->next; r->next=q; r =q; q=q->next; } if(p!=NULL) r->next=p; if(q!=NULL) r->next=q; free(hb); return ha; }
A. 在P结点后插入S结点的语句序列是
A. P->next=S; E A B. P->next=P->next->next; C. P->next=S->next; E. S->next=P->next; F. S->next=L; G. S->next=NULL; H. Q=P; I. while( P->next!=Q ) P=P->next; J. while( P->next!=NULL ) P=P->next K. P=Q; L. P=L; M. L=S; N. L=P;

)。

第2章线性表1 .选择题(1)顺序表中 第一个 元素的存储 地址是100，每个元素的 长度为2，则第5个元素的 地址是( )。

A . 110 答案：B 解释：顺序表中的数据连续存储，所以第D . 120 5个元素的地址为： 100+2*4=108。

(3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移 动的元素个数为( )。

C . 63 A . 8 B . 答案：B 解释：平均要移动的元素个数为： (4) 链接存储的存储结构所占存储空间(n/2。

）。

A .分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B .只有一部分，存放结点值C .只有一部分，存储表示结点间关系的指针D .分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A(5) 线性表若采用链式存储结构时，要求内存中可用存储单元的地址(A .必须是连续的C . 一定是不连续的答案：D(6) 线性表1在( B •部分地址必须是连续的D •连续或不连续都可以)情况下适用于使用链式结构实现。

B.需不断对L 进行删除插入 D.L 中结点结构复杂A .需经常修改L 中的结点值C . L中含有大量的结点答案：B解释：链表最大的优点在于插入和删除时不需要移动数据，直接修改指针即可。

(7) 单链表的存储密度( )。

A .大于1 B .等于1答案：C 解释：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比，假设单链表一个结点本身所占的空间为 D ，指针域所占的空间为 N ，则存储密度为：D/(D+N)，—定小于 1。

(8) 将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是(C •小于1D •不能确定 B . 2n-1 C . 2n D . n-1C . 100答案：A解释：当第一个有序表中所有的元素都小于(或大于)第二个表中的元素，只需 要用第二个表中的第一个元素依次与第一个表的元素比较，总计比较n 次。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

试卷B一、选择题（本题共20分,每题2分）1．在数据结构中，从逻辑上可以把数据结构分成（ ） 。

A ．动态结构和静态结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧凑结构 D. 内部结构和外部结构 2. 下列程序段的时间复杂度是（ ）count=0;for(k=1;k<=n;k*=2) for(j=1;j<=n;j++) count++;A.O(nlog2n)B.O(n)C.O(log2n)D.O(n2) 3. 以下描述错误的是：（ ）A. 线性表是n 个数据元素的有限非空集合。

B. 栈和队列都是操作受限的线性表。

C. 串（或字符串）是由零个或多个字符组成的有限序列。

D. 非空栈中的栈顶指针top 始终指向栈顶元素的下一个位置。

4. 若采用少用一个队列空间的方法来区分队满队空两种状态，则判定一个顺序循环队列 Q （最大队列长度MAXSIZE ）为满队列的条件是( )。

A. Q.front=Q.rearB. Q.front!=Q.rearC. Q.front=(Q.rear+1) % MAXSIZED. Q.front!=(Q.rear+1) % MAXSIZE 5. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。

A. 3 B. 4 C. 5 D. 66. 设矩阵A （如下图所示）是一个对称矩阵，为了节省存储，将其下三角（包括对角线）部分按行序存放在一维数组 B[n(n+1)/2]中，对下三角部分中任一元素 ai,j(i ≥j)，在一维数组 B 的下标位置k 的值是（ ）。

A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j0,01,01,11,01,11,1...............n n n n a a a A a a a ----⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦7. 有一个有序表为｛5, 18，23, 33, 42, 54,56,78｝，当折半查找56时，经过（ ）次比较后查找成功。

数据结构（C语言版）（第2版）课后习题答案李冬梅目录第1章绪论............................................. 错误!未定义书签。

第2章线性表........................................... 错误!未定义书签。

第3章栈和队列......................................... 错误!未定义书签。

第4章串、数组和广义表................................. 错误!未定义书签。

第5章树和二叉树....................................... 错误!未定义书签。

第6章图................................................ 错误!未定义书签。

第7章查找............................................. 错误!未定义书签。

第8章排序............................................. 错误!未定义书签。

第1章绪论1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。

如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。

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

在有些情况下，数据元素也称为元素、结点、记录等。

数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。

数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。

例如，学生基本信息表中的学号、姓名、性别等都是数据项。

数据结构-阶段测评11.单选题计算机识别、存储和加工处理的对象被统称为(A )您答对了a数据b数据元素c数据结构d数据类型本题考核数据的基本概念非空的循环单链表head的尾结点（由p所指向）满足（C）。

您答对了ap->next==NULLbp==NULLcp->next==headdp==head本题考核循环单链表的基本特点。

若长度为n的线性表采用顺序存储结构存储，在第i个位置上插入一个新元素的时间复杂度为（A）。

您答对了aO(n)bO(1)cO(n2)dO(n3)本题考核顺序表的插入运算的时间复杂度。

下面程序段中a[i][j]=0语句执行的时间复杂度是( D)。

for(i=0;i<n;i++)for(j=1;j<m;j++)a[i][j]=0；您答对了aO(n)bO(m+n+1)cO(m+n)dO(m*n)本题考核时间复杂度的计算方法在一个具有n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间复杂度是（B）。

您答对了aO(1)bO(n)cO(n2)dO(nlog2n)因要保持有序，所以需要查找插入结点的位置，而在链表中查找结点位置的时间复杂度为O(n)，所以本题选B。

在一个长度为n的顺序表中删除第i个元素（1<=i<=n）时，需向前移动（A）个元素。

您答对了an-ibn-i+1cn-i-1di考核顺序表的基本操作设顺序表有10个元素，则在第5个元素前插入一个元素所需移动元素的个数为（ B）。

您答对了a5b6c7d9在第5个元素前插入元素需要将第5个元素开始的所有元素后移，所以本题答案为B。

算法指的是（D ）。

您答对了a计算机程序b解决问题的计算方法c排序算法d解决问题的有限运算序列考核算法的基本概念线性表采用链式存储时，结点的存储地址（B ）您答对了a必须是不连续的b连续与否均可c必须是连续的d和头结点的存储地址相连续链式存储分配的结点在内存连续与不连续均可，所以答案选B。

数据结构与算法上机作业第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。

A. O(log2n)B. O(1)C. O(n)D. O(n2)2、以下关于线性表的说法中，不正确的是。

A. 线性表中的数据元素可以是数字、字符、结构等不同类型B. 线性表中包含的数据元素个数不是任意的C.线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表）D.存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现）3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为。

A. O(1)B. O(n)C. O(n2)D. O(log2n)4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为。

A. nB. (n-1)/2C. n/2D. (n+1)/2已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动.i的取值服从1到N+1的平均分布,即概率是1/(N+1).求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于(N+1-1)*1/(N+1)+(N+1-2)*1/(N+1)+(N+1-3)*1/(N+1)+...+(N+1-N-1)*1/(N+1)=N/25、在一个长度为n的顺序存储的线性表中查找值为x的元素时，平均查找长度(及x同元素的平均比较次数，假定查找每个元素的概率都相等)为。

A. nB. n/2C. (n+1)/2D. (n-1)/26、在顺序表中，只要知道，就可以求出任一结点的存储地址。

A. 基地址B. 结点大小C. 向量大小D. 基地址和结点大小7、将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数是。

A. nB. 2n-1C. 2nD. n-18、线性表采用链表存储时其存储地址要求。

A. 必须是连续的B. 部分地址必须是连续的C. 必须是不连续的D. 连续的和不连续的都可以9、下面关于线性表的描述中，错误的是。

数据结构(C语言版)(第2版)课后习题答案数据结构(C语言版)(第2版)课后习题答案1. 简介数据结构是计算机科学领域中非常重要的一门学科，它研究的是数据的组织、存储和管理方式。

本文将针对《数据结构(C语言版)(第2版)》的课后习题提供答案，帮助读者更好地理解和应用数据结构。

2. 第一章: 绪论在第一章中，主要介绍了数据结构的基本概念、分类和基本操作。

以下是部分习题的答案：2.1 习题1习题描述：什么是数据结构？答案：数据结构是指数据对象中元素之间的关系，以及对这些关系进行操作的方法和技术的集合。

2.2 习题2习题描述：数据结构的分类有哪些？答案：数据结构可以分为线性结构和非线性结构。

线性结构包括线性表、栈、队列等；非线性结构包括树、图等。

3. 第二章: 线性表第二章介绍了线性表的定义、分类和实现。

以下是部分习题的答案：3.1 习题1习题描述：什么是线性表？答案：线性表是由n个数据元素a1, a2, ..., an组成的有限序列，其中元素之间存在着一一对应的关系。

3.2 习题2习题描述：线性表的分类有哪些？答案：线性表可以分为顺序表和链表。

顺序表是用一段地址连续的存储单元一次存储线性表的所有元素，而链表是采用链式存储结构，通过每个元素存储其后继元素的地址来实现元素之间的逻辑关系。

4. 第三章: 栈与队列第三章讲解了栈和队列的定义、特性和实现。

以下是部分习题的答案：4.1 习题1习题描述：栈和队列有什么区别？答案：栈是一种后进先出的线性表，只能在表尾进行插入和删除操作；队列是一种先进先出的线性表，只能在表的一端进行插入和删除操作。

4.2 习题2习题描述：栈的应用有哪些？答案：栈在计算机科学中有广泛的应用，如函数的调用和返回、括号匹配、表达式求值等。

5. 第四章: 串第四章讲解了串的定义、模式匹配和实现。

以下是部分习题的答案：5.1 习题1习题描述：什么是串？答案：串是由零个或多个字符组成的有限序列，串中的字符个数称为串的长度。

数据结构练习题1~5章 数据结构练习题 数据结构练习题（1－5章） 一、选择题 1、从逻辑上可以把数据结构分为（ B ）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2、以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 3、在下面的程序段中，对x的赋值语句的频度为（） for (i=1;i<=n;i++) for (j=1;j<=n;i++) x=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 4、下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个 元素，则采用（）存储方式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指 针的单循环链表 6、静态链表中指针表示的是（）. A．内存地址 B．数组下标 C．下一元素地址 D．左、右 孩子地址 7、下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的 算法的时间复杂度为（ C ）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i （1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 12、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出 栈序列？（） 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 13、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出 栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 14、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear， 则当前队列中的元素个数为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 15、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别 为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分 别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16、下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串->(空格串是 由空格组成的) C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用 链式存储 17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法 称为（） A．求子串 B．联接 C．匹配 D．求串长 18、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的 值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素 A[5，8]的存储首地址为( )。30*6＝180 A. BA+141 B. BA+180 C. BA+222 D. BA+225 19、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算 是（）。 A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail （L）））)） 20、广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。 Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d 二、判断题 1、数据元素是数据的最小单位。( ) 2、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描 述，则算法实际上就是程序了。( ) 3、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 ( ) 5、线性表的特点是每个元素都有一个前驱和一个后继。( ) 6、一个稀疏矩阵A 采用三元组形式表示，若把三元组中有关行下标与列下 m*n 的转置运算。（） 标的值互换，并把m和n的值互换，则就完成了A m*n 7、所谓取广义表的表尾就是返回广义表中最后一个元素。（） 三、填空题 1、数据的物理结构包括 __ ___的表示和__ ___的表示。 2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_____ _存储结构。 3、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是___ __。 4、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为 ______,在给定值为x的结点后插入一个新结点的时间复杂度为__ ___。 5、带头结点的双循环链表L中只有一个元素结点的条件是：_ ____ 6、一个栈的输入序列是：1，2，3则不可能的栈输出序列是___。 7、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为 ___。 8、_ ___又称作先进先出表。 9、组成串的数据元素只能是 ____。 10、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6][6]存储地址为__ ___。(没说明，则下标从0开始) 四、算法与应用题 1. 设线性表存放在向量A[arrsize]的前elenum个分量中且递增有序，试写一算法将x插入到线性表的适当位置，以保持线性表的有序性并分析其时间复杂度。 2.已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。 3.在长度大于1的单循环链表L中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 五、程序填空题 1、下面是用c语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L返回逆置后的链表的头指针，试在空缺处填入适当的语句。 void reverse（linklist &L）{ p=null；q=L； while（q！=null） { (1); q->next=p；p=q；(2) ___ ; } (3) } } } 2、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。（10分） typedef struct node {int data; struct node *next; }linknode,*link; void Insertsort(link L) { link p,q,r,u; p=L->next; (1) ___; while((2)_ __________) { r=L; q=L->next; while((3) _&& q->data<=p->data) {r=q; q=q->next; } u=p->next; (4)_ p->next=q ___ ; (5)_ r->next= p_; p=u; } }

第一章绪论一、问答题1. 什么是数据结构？2. 叙述四类基本数据结构的名称与含义。

3. 叙述算法的定义与特性。

4. 叙述算法的时间复杂度。

5. 叙述数据类型的概念。

6. 叙述线性结构与非线性结构的差别。

7. 叙述面向对象程序设计语言的特点。

8. 在面向对象程序设计中，类的作用是什么？9. 叙述参数传递的主要方式及特点。

10. 叙述抽象数据类型的概念。

二、判断题（在各题后填写“√”或“×”）1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。

（）2. 算法就是程序。

（）3. 在高级语言（如C或PASCAL）中，指针类型是原子类型。

（）三、计算下列程序段中X=X+1的语句频度for(i=1;i<=n;i++) for(j=1;j<=i;j++)for(k=1;k<=j;k++) x=x+1;四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。

注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。

通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递。

（2）通过全局变量隐式传递。

试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

第二章线性表2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。

2.2 填空：（1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元素个数与＿＿插入或删除的位置＿＿有关。

（2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。

在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。

（3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。

数据结构第2版习题答案第1章：引言数据结构是计算机科学中非常重要的一个领域，它关注如何以高效的方式组织和存储数据，以及如何在数据集合中进行操作和处理。

本章将回答《数据结构第2版》中的习题，帮助读者更好地理解和掌握数据结构。

第2章：算法分析习题1：算法复杂度问题描述：给定一个算法中的递归函数，分析其时间复杂度。

解答：对于递归算法的时间复杂度分析，可以使用递归树或者递推关系式来求解。

根据习题中给出的递归函数具体形式，我们可以推导出其递归关系式，并通过求解递推关系式确定时间复杂度。

习题2：渐进符号问题描述：给定两个函数f(n)和g(n)，证明f(n)的渐进复杂度小于等于g(n)的渐进复杂度。

解答：为了证明f(n)的渐进复杂度小于等于g(n)的渐进复杂度，我们需要使用大O符号进行形式化的证明。

通过定义和性质的证明，可以得出结论。

第3章：线性表习题3：线性表的实现问题描述：实现一个线性表的数据结构，并给出相关操作的算法。

比如插入元素、删除元素、查找元素等。

解答：一个线性表可以通过数组或链表来实现。

我们可以定义一个包含元素和相关操作的类来表示线性表。

在插入、删除、查找元素等操作中，可以通过遍历或者索引等方式来实现。

习题4：线性表的应用问题描述：举例介绍线性表的应用场景，并分析其对应的实现方法和复杂度。

解答：线性表的应用场景非常广泛，比如数组、链表、队列、栈等。

我们可以通过具体的案例，如存储学生成绩、处理任务队列、实现表达式求值等，来说明线性表的应用和对应的实现方法。

第4章：栈和队列习题5：栈和队列的实现问题描述：实现一个栈和队列的数据结构，并给出相关操作的算法。

解答：栈和队列可以通过数组或链表来实现。

我们可以定义相应的类来表示栈和队列，并实现相关操作，如入栈、出栈、入队、出队等。

习题6：栈和队列的应用问题描述：举例介绍栈和队列的应用场景，并分析其对应的实现方法和复杂度。

解答：栈和队列的应用非常广泛，比如表达式求值、括号匹配、图的深度优先搜索等。

第1章绪论练习题答案判断题1. 数据元素是数据的最小单位。

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

(× )3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。

(× )4．算法的优劣与算法描述语言无关，但与所用计算机有关。

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

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

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

(× )第2章线性表练习题答案一、填空1. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

2. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

3. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

4. 在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

5．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。

二、判断正误（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

某线性表中最常用的操作是在最后一个 元素之后插入一个元素和删除第一个元 素，则采用 存储方式最节省运算时间。
A. 单链表 B. 仅有头指针的单循环链表 C. 双向链表 D. 仅有尾指针的单循环链表
链表结构不具有下列
特点。
A. 插入和和删除元素无需移动元素 B. 可随机访问链表中的任意元素 C. 无需事先分配存储空间 D. 所需空间与结点个数成正比
O(n)
在类SingleList中增加一个成员函数，将单链 表逆置运算，直接实现该函数并分析其时间 复杂度。
template <class T> void SingleList<T>::invert() { Node<T> *p=first,*q; first=NULL; while (p) { q=p->link; p->link=first; first=p; p=q; } }
在类LinearList 中增加一个成员函数，将顺序 表逆置，实现该函数并分析算法的时间复杂 度。不利用类SeqList 提供的操作直接实现。
template <class T> void SeqList<T>::Invert(){ T e; for (int i=0;i<length/2;i++){ e=elements[i]; elements[i]=elements[length-i-1]; elements[length-i-1]=e; } }
利用线性表类LinearList提供的操作，设计实 现两个集合的交和差运算。
#include <iostream.h> #include "seqlist0.h" #include "conio.h" template <class T> //集合交操作 void InterSection(SeqList<T> &LA,SeqList<T> &LB) { int m=LB.Length(); SeqList<T> LC(10); T x; for (int i=1;i<=m;i++) { LB.Find(i,x);//返回第i个元素到X中 if (LA.Search(x)) LC.Insert(LC.Length()+1,x); } cout<<LC; }