南京工业大学 数据结构 作业答案 作业6

数据构造作业题及答案第一章绪论1、简述以下概念：数据、数据元素、数据构造、逻辑构造、存储构造、线性构造、非线性构造。

数据：指能够被计算机识别、存储与加工处理的信息载体。

数据元素：就是数据的根本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。

数据元素有时可以由假设干数据项组成。

数据构造：指的是数据之间的相互关系，即数据的组织形式。

一般包括三个方面的内容:数据的逻辑构造、存储构造与数据的运算。

逻辑构造：指各数据元素之间的逻辑关系。

存储构造：就是数据的逻辑构造用计算机语言的实现。

线性构造：数据逻辑构造中的一类，它的特征是假设构造为非空集，那么该构造有且只有一个开场结点与一个终端结点，并且所有结点都最多只有一个直接前趋与一个直接后继。

线性表就是一个典型的线性构造。

非线性构造：数据逻辑构造中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋与直接后继。

2、常用的存储表示方法有哪几种?顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来表达。

由此得到的存储表示称为顺序存储构造。

链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。

由此得到的存储表示称为链式存储构造。

索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

3、求解以下算法的时间复杂度第二章线性表1、试描述头指针、头结点、开场结点的区别、并说明头指针与头结点的作用。

答：开场结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。

链表的头指针是一指向链表开场结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。

头结点是我们人为地在链表的开场结点之前附加的一个结点。

有了头结点之后，头指针指向头结点，不管链表否为空，头指针总是非空。

Ch6 树一、选择题：1．下列关于哈夫曼树的叙述，错误的是 (C )。

A ．哈夫曼树根结点的权值等于所有叶结点权值之和。

B ．具有 n 个叶结点的哈夫曼树共有 2n-1个结点。

C ．哈夫曼树是一棵二叉树，因此它的结点的度可以为 0，1，2。

D ．哈夫曼树是带权路径长度最短的二叉树。

2．由 3 个结点可以构成多少棵不同形态的二叉树(C )。

A ．3 B ．4 C ．5 D ． 63．如果一棵二叉树结点的前序序列是 A ，B，C ，后序序列是 C ，B ，A ，则该二叉树结点的中序序列是 (D )。

A ．A ，B，C B ．A ，C ，B C ．B，C，A D ．不能确定4．如图所示的 4 棵二叉树中， (B )不是彻底二叉树。

A ．B ．C ． D．5．二叉树按某种顺序线索化后，任一结点均有指向其前趋和后继的线索，这种说法 (B )A ．正确B ．错误若结点有左子树，则令其 lchild指针指示其左孩子；若结点没有左子树，则令其 lchild指针指示其前驱；若结点有右子树，则令其 rchild指针指示其右孩子；若结点没有右子树，则令其 rchild指针指示其后继。

6．二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 (A )。

A ．正确B ．错误7．对一棵 70 个结点的彻底二叉树，它有(A )个叶子结点。

A． 35 B ．40 C ． 30 D ．448．设一棵二叉树中，度为 1 的结点数为 9，则该二叉树的叶子结点的数目为 (D )。

A ．10 B ．11 C ．12 D ．不确定 n =n +1 9．假定根结点的层次为 0，含有 15 个结点的二叉树最小高度为 (A )。

A ． 3 B ． 4 C ． 5 D ． 6假定根结点的层次为 1，含有 15 个结点的二叉树最小高度为 410．若一棵二叉树中，度为 2 的结点数为 9，该二叉树的叶子结点的数目为 (A )。

参考答案第一章、绪论一、选择题1 B；2 A； 3 B；4 C ；5 C； 6 B；7 C；8 C；9 D；10 B。

二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。

三、问答题与算法题1、3 ；2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;T4 ( n ) = 1.5 n 2 + O ( n ) 。

T4 ( n ) 较优，T3 ( n )较劣。

3、见课本。

第二章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。

三、问答题与算法题1、头指针：结点或头结点的指针变量。

其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。

头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。

其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。

首结点：是链表的第一个结点。

2、(1)基于空间的考虑。

当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。

(2)基于时间的考虑。

若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。

一、一、单选题（每题2 分，共20分）1. 1. 栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2. 2. 用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 3. 以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4. 4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965. 5. 树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6. 6. 二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.10. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、二、填空题（每空1分，共26分）1. 1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。

数据结构作业题⽬答案⼀、单择题1.栈和队列的共同特点是(A)。

A.只允许在端点处插⼊和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.⼆叉树的第k层的结点数最多为（2的k-1次⽅)。

A.2k-1B.2K+1C.2K-1D. 2k-13.数据结构中，从逻辑上可以把数据结构分成(C)。

A.动态结构和静态结构B.进凑结构和⾮进凑结构C.线性结构和⾮线性结构D.内部结构和外部结构4.设⼆叉树的先序遍历序列和后序遍历序列正好相反，则该⼆树满⾜的条件是(全部是左⼦树或全部是右⼦树 CD )。

A.空或只有⼀个结点B.⾼度等于其结点数C.任⼀结点⽆左孩⼦D.任⼀结点⽆右孩⼦5.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( A )个元素。

A. n-iB. n+l -iC.n-1-iD. i6.判定⼀个栈ST（最多元素为m0）为空的条件是(B)。

A.ST→TOP!=0B.ST→TOP==0C.ST→TOP!=m0D.ST→TOP==m0B7. ⾮空的循环单链表head的尾结点（由P所指向）满⾜( C )。

A.p->next=NULLB.p=NULLC.p->next=headD.p=head8.在线性结构中，所有结点都有( B )个直接后继。

A.0B.0或1C.1D.不确定9.设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执⾏⼊队操作时修改指针的语句是。

A、sq.front=(sq.front+1)%mB、sq.front=(sq.front+1)%(m+1)C、sq.rear=(sq.rear+1)%mD、sq.rear=(sq.rear+1)%(m+1)⼆、填空题1.已知⼀棵⼆叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，则该⼆叉树的前序序列是( ABDECFH )。

2.在( 循环 )链表中，从任何⼀结点出发都能访问到表中的所有结点。

第六章树和二叉树（下载后用阅读版式视图或web版式可以看清）习题一、选择题1．有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。

表示该遗传关系最适合的数据结构为( )。

A.向量B.树C图 D.二叉树2．树最合适用来表示( )。

A.有序数据元素 B元素之间具有分支层次关系的数据C无序数据元素 D.元素之间无联系的数据3．树B的层号表示为la，2b，3d，3e，2c，对应于下面选择的( )。

A. la (2b (3d,3e),2c)B. a(b(D,e),c)C. a(b(d,e),c)D. a(b,d(e),c)4.高度为h的完全二叉树至少有( )个结点，至多有( )个结点。

A. 2h_lB.h C．2h-1 D. 2h5.在一棵完全二叉树中，若编号为f的结点存在右孩子，则右子结点的编号为( )。

A. 2iB. 2i-lC. 2i+lD. 2i+26.一棵二叉树的广义表表示为a(b(c)，d(e(，g(h))，f))，则该二叉树的高度为( )。

A.3B.4C.5D.67.深度为5的二叉树至多有( )个结点。

A. 31B. 32C. 16D. 108.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。

A. 15B. 16C. 17D. 479.题图6-1中，( )是完全二叉树，( )是满二叉树。

1 / 1710.在题图6-2所示的二叉树中：(1)A结点是A.叶结点 B根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(2)J结点是A.叶结点 B．根结点但不是分支结点C根结点也是分支结点 D.分支结点但不是根结点(3)F结点的兄弟结点是A.EB.D C．空 D.I(4)F结点的双亲结点是A.AB.BC.CD.D(5)树的深度为A.1B.2C.3D.4(6)B结点的深度为A.1B.2C.3D.4(7)A结点所在的层是A.1B.2C.3D.411.在一棵具有35个结点的完全二叉树中，该树的深度为( )。

数据结构答案第6章第6章数据结构答案1. 栈的应用栈是一种常见的数据结构，其特点是先进后出。

下面是一些关于栈的应用场景。

1.1 函数调用栈在程序中，每当一个函数被调用时，相关的变量和状态信息会被存储在一个称为函数调用栈的栈中。

1.2 表达式求值栈也常用于表达式求值，特别是中缀表达式转后缀表达式的过程中。

通过使用栈，我们可以很方便地进行算术运算。

1.3 逆序输出如果我们需要逆序输出一段文本、字符串或者其他数据，可以使用栈来实现。

将数据依次压入栈中，然后再逐个弹出即可。

2. 队列的实现与应用队列是另一种常见的数据结构，其特点是先进先出。

下面是一些关于队列的实现和应用。

2.1 数组实现队列队列可以使用数组来实现。

我们可以使用两个指针分别指向队列的前端和后端，通过移动指针来实现入队和出队的操作。

2.2 链表实现队列队列还可以使用链表来实现。

我们可以使用一个指针指向队列的头部，并在尾部添加新元素。

通过移动指针来实现出队操作。

2.3 广度优先搜索（BFS）队列常用于广度优先搜索算法。

在BFS中，我们需要按照层级来访问节点。

使用队列可以帮助我们按照顺序存储和访问节点。

3. 树的遍历和应用树是一种非常重要的数据结构，在计算机科学中应用广泛。

下面是一些关于树的遍历和应用的介绍。

3.1 深度优先搜索（DFS）深度优先搜索是树的一种遍历方式。

通过递归或者使用栈的方式，可以按照深度优先的顺序遍历树的所有节点。

3.2 广度优先搜索（BFS）广度优先搜索也可以用于树的遍历。

通过使用队列来保存要访问的节点，可以按照层级的顺序遍历树。

3.3 二叉搜索树二叉搜索树是一种特殊的二叉树，它的每个节点的值都大于左子树中的值，小于右子树中的值。

这种结构可以用于高效地进行数据查找。

4. 图的表示与遍历图是由节点和边组成的一种数据结构。

下面是一些关于图的表示和遍历的说明。

4.1 邻接矩阵表示法邻接矩阵是一种常见的图的表示方法。

使用一个二维数组来表示节点之间的连接关系。

数据结构课后习题答案1--7题目1：请你设计一个栈数据结构，使其具备以下功能：可以在O(1)的时间复杂度内获取栈的最小元素。

解答1：要实现在O(1)的时间复杂度内获取栈的最小元素，可以使用两个栈来实现。

一个栈用来保存原始数据，另一个栈用来保存当前栈的最小元素。

具体实现如下：1. 初始化两个栈：stack和min_stack，其中stack用于保存所有元素，min_stack用于保存当前栈中的最小元素。

2. 插入元素时，先将元素插入stack中，然后判断插入的元素是否比min_stack的栈顶元素小，如果是，则将元素也插入到min_stack中；如果不是，则将min_stack的栈顶元素再次插入到min_stack中。

3. 删除元素时，分别从stack和min_stack中弹出栈顶元素。

这样，min_stack的栈顶元素始终是stack中的最小元素。

题目2：请你设计一个队列数据结构，使其具备以下功能：可以在O(1)的时间复杂度内获取队列的最大元素。

解答2：要实现在O(1)的时间复杂度内获取队列的最大元素，可以使用两个队列来实现。

一个队列用来保存原始数据，另一个队列用来保存当前队列的最大元素。

具体实现如下：1. 初始化两个队列：queue和max_queue，其中queue用于保存所有元素，max_queue用于保存当前队列中的最大元素。

2. 插入元素时，先将元素插入queue中，然后判断插入的元素是否比max_queue的队尾元素大，如果是，则将元素也插入到max_queue的队尾；如果不是，则将max_queue中所有比插入元素小的元素都弹出，再将插入元素插入到max_queue的队尾。

3. 删除元素时，分别从queue和max_queue中弹出队头元素。

这样，max_queue的队头元素始终是queue中的最大元素。

题目3：请你设计一个栈数据结构，使其除了具有常规的入栈和出栈功能外，还具备以下功能：能够在O(1)的时间复杂度内获取栈中的最大元素。

《数据结构》各章课后作业答案 第一章 绪论课后作业答案1. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

2．分析下面各程序段的时间复杂度（每小题5分，共20分）解：1.第一个for 循环执行n+1次，第二个for 循环执行n(m+1)次，A[i][j]=0;语句执行n*m 次，此程序段总的执行次数为n+1+n*(m+1)+n*m=2nm+2n+1次。

故时间复杂度为O(n*m)。

2.算法的时间复杂度是由嵌套最深层语句的执行次数决定的，本程序段嵌套最深层语句为：s+=B[i][j];它的执行次数为n 2，所以本程序段的时间复杂度是O(n 2)。

3. 该算法的基本操作是语句x++, 其语句频度为：1111n n i i j --==∑∑=10()n i n i -=-∑=(1)2n n - 所以本程序段的时间复杂度是O(n 2)。

4.设语句执行m 次，则有3m≤n ⇒m ≤log 3n所以本程序段的时间复杂度为O(log 3n)。

第二章 线性表课后作业答案1. 填空题。

（1）在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

（2）线性表中结点的集合是 有限 的，结点间的关系是 一对一的。

（2）s=0;for （i=0; i<n; i++)for(j=0; j<n; j++) s+=B[i][j]; sum=s; 答：O （n 2）（1） for (i=0; i<n; i++) for (j=0; j<m; j++) A[i][j]=0;(3) x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;(4)i=1;while(i<=n)i=i*3;（3）向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。

作业11. 数据结构和数据类型两个概念之间有区别吗？答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。

数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

2•阅读下列C程序段，写出相应的执行结果(每小题4分，共8分)(〔)。

printf( In put x ); ( 2)。

Io ng int fact (n)scanf( “ ％d'，&x);if (x<=30)if(x>20) y=x;else if (x>10) y=2*x;if (x>0&& x<30)pri ntf(“ x=%d,y= %d ”else printf(输入数据错！”)；试写出当x分别为18，8时的执行结果。

答：运行结果为：x=18，y=36x=8，y=运行前的值，且从x = 30开始为数据错int n;{long f;if(n >1)f= n*fact( n-1);else f=1;,x,y);return(f);}main (){int n;long y;n=5;y=fact( n);printf( “ %d,% n” ,n,y);}答：运行结果为：5，120 此题为递归运算3.分析下面各程序段的时间复杂度1. for (i=0; i<n; i++)for (j=0; j<m; j++)A[i][j]=0;答：0( m*n)3. x=0;for(i=1; i<n; i++)for (j=1; j<=n-i; j++)x++;解：因为x++共执行了n-1+ n-2+ ........... + 1 = n(n-1)/2，所以执行时间为O (n2)"J H "J f}.( IT— 1)作业2 2. s=0;for i=0; i<n; i++)for(j=0; j< n; j++)s+=B[i][j]; sum=s; 答: O(n2)4. i=1;while(i<=n) i=i*3; 答：O (log3n)1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点。