数据结构作业答案

第1章4．答案：（1）顺序存储结构顺序存储结构是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，通常借助程序设计语言的数组类型来描述。

（2）链式存储结构顺序存储结构要求所有的元素依次存放在一片连续的存储空间中，而链式存储结构，无需占用一整块存储空间。

但为了表示结点之间的关系，需要给每个结点附加指针字段，用于存放后继元素的存储地址。

所以链式存储结构通常借助于程序设计语言的指针类型来描述。

5. 选择题(1)~(6)：CCBDDA6．（1）O(1) （2）O(m*n) （3）O(n2)（4）O(log3n) （5）O(n2) （6）O(n)第2章1．选择题（1）~（5）：BABAD （6）~（10）：BCABD （11）~（15）：CDDAC 2．算法设计题（1）将两个递增的有序链表合并为一个递增的有序链表。

要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。

表中不允许有重复的数据。

[题目分析]合并后的新表使用头指针Lc指向，pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，依次摘取其中较小者重新链接在Lc表的最后。

如果两个表中的元素相等，只摘取La表中的元素，删除Lb表中的元素，这样确保合并后表中无重复的元素。

当一个表到达表尾结点，为空时，将非空表的剩余元素直接链接在Lc表的最后。

void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){//合并链表La和Lb，合并后的新表使用头指针Lc指向pa=La->next; pb=Lb->next;//pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点Lc=pc=La; //用La的头结点作为Lc的头结点while(pa && pb){ if(pa->data<pb->data){pc->next=pa; pc=pa; pa=pa->next;}//取较小者La中的元素，将pa链接在pc的后面，pa指针后移else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;}//取较小者Lb中的元素，将pb链接在pc的后面，pb指针后移else //相等时取La中的元素，删除Lb中的元素{pc->next=pa;pc=pa;pa=pa->next;q=pb->next; delete pb ; pb =q;}}pc->next=pa?pa:pb; //插入剩余段delete Lb; //释放Lb的头结点}（5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A中的元素为非零整数，要求B、C表利用A表的结点）。

第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。

1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。

1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。

A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。

A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。

1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。

1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。

A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。

A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。

数据结构第一次作业数据结构第一次作业一．单项选择题(20分)( )1.已知一算术表达式的后缀形式为ABC *+DE-/，则其中缀形式为 _________。

a、(A＋B *C)/(D-E)b、A+B*C /D-Ec、(A+B*C)/D-Ed、A+B*C/(D-E)( )2.若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用________存储方式最节省运算时间（假设链表仅设有一个first指针）。

a. 单链表b. 带头结点的双循环链表c. 单循环链表d. 双链表( )3.设一个栈的输入序列为A，B，C，D，则所得到的输出序列不可能是_______。

a. A，B，C，Db. D，C，B，Ac. A，C，D，Bd. D，A，B，C( )4.若线性表最常用的操作是存取第i个元素及其直接前驱的值，则采用_____存储方式节省时间。

a．顺序表 b．双链表 c．单循环链表 d．单链表( )5.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为_______。

(1≤i≤n+1)a、O(0)b、O(1)c、O(n)d、O(n2)( )6.若指针L指向一带头结点的循环单链表的头结点，该表为空表的条件是_______为真值；a. !( L -> link );b. L == (L -> link) -> link;c. L -> link;d. L == L -> link;( )7.用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是________：a. front = (front + 1) mod N;b. front = (front - 2)mod N;c. front = front + 1;d. front = front – 2;( )8.若用Head()和Tail()分别表示取广义表的表头和表尾，广义表A=（1,2,(3,4),(5,(6,7))），则Head(Tail(Head(Tail(Tail(A))))) 。

head第3章 栈和队列 自测卷答案 姓名 班级一、填空题（每空1分，共15分）1. 【李春葆】向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。

不允许插入和删除运算的一端称为 栈底 。

3. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在一个循环队列中，队首指针指向队首元素的 前一个 位置。

(注：不一定，这是一种约定，在殷教材中是队首指针指向队列的首元素位置)5. 在具有n 个单元的循环队列中，队满时共有 n-1 个元素。

6. 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

7. 从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。

(注：不一定，这是一种约定，在殷教材中是先 取出元素 ，后移动队首指针 )8. 〖00年统考题〗带表头结点的空循环双向链表的长度等于 0 。

解：二、判断正误（判断下列概念的正确性，并作出简要的说明。

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

错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。

（ × ）2. 在表结构中最常用的是线性表，栈和队列不太常用。

错，不一定吧调用子程序或函数常用，CPU 中也用队列。

（ √ ）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同而已。

（×）5. 栈和链表是两种不同的数据结构。

错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同类项。

参考答案第一章、绪论一、选择题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)基于时间的考虑。

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

数据结构作业题⽬答案⼀、单择题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.在( 循环 )链表中，从任何⼀结点出发都能访问到表中的所有结点。

东北农业大学网络教育学院数据结构作业题(一)、选择题(每题2分，共20 分)1在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。

2A Qn) B、O(n/2) C、O(1) D O(n )2.带头结点的单链表first为空的判定条件是( )。

A、first == NULL ;B、first->link == NULL ;C、first->link == first ;D、first != NULL ;3•在一棵树中，( )没有前驱结点。

A、分支结点B、叶结点C、树根结点D、空结点4•在有向图中每个顶点的度等于该顶点的( )。

A、入度B、出度C、入度与出度之和D、入度与出度之差5.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( ) 的值除以9。

A、20B、18C、25D、226•下列程序段的时间复杂度为( )。

s=0;for(i=1 ; i<n; i++)for(j=1 ; j<n ; j++)s+=i*j ;2A、O(1)B、O(n)C、O(2n)D、O(n)7•栈是一种操作受限的线性结构，其操作的主要特征是( )。

A、先进先出B、后进先出C、进优于出D、出优于进&假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( )。

4•在二叉树的第i 层上至多有 ______________ 结点。

5.对于一棵具有 n 个结点的二叉树，若一个结点的编号为A、 C、 (rear-front-1) % n B 、(rear-front) % n (front-rear+1) % nD 、(rear-front+n) % n高度为5的完全二叉树中含有的结点数至少为(16B 、17C 、3110.如图所示有向图的一个拓扑序列是D 、32)A 、 ABCDEFB 、 FCBEADC 、 FEDCBAD 、 DAEBCF二、填空题(每空1分，共20 分)1. n (n > 0)个顶点的无向图最多有2.在一棵AVL 树中，每个结点的左子树高度与右子树高度之差的绝对值不超过 ________ 。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

作业1. 线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。

参考答案#include <>#include <>#include <>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;立单链表 ");printf("2.取元素值 ");printf("3.查找 \n");printf("4.插入 ");printf("5.删除 ");printf("6.显示\n");printf("7.删除大于mink且小于maxk的元素值 ");printf("8.就地升序排序\n");printf("9.就地逆置 ");printf("a.有序表插入 ");printf("q.退出\n");printf("\n请选择操作：");fflush(stdin);scanf("%c",&choice);switch(choice){case '1': printf("请输入单链表中结点个数：");scanf("%d",&n);Create_L2(L,n);break;case '2': printf("请输入元素位序：");scanf("%d",&i);GetElem_L(L,i,e);printf("元素值为：%d\n",e);break;case '3': printf("请输入要查找的元素：");scanf("%d",&e);if(dlbcz(L,e))printf("查找成功！");elseprintf("查找失败。

数据结构作业答案单选题1、下列关于算法的基本特征，说法不正确的是（）。

能行性是算法中的每一个步骤必须能够实现且能达到预期的目的。

算法的确定性是指算法中的每一个步骤必须是有明确的定义，不允许模棱两可。

算法的有穷性是指算法必须能在有限的时间内做完。

算法与提供情报无关。

[D] 教师批改：D2、算法的时间复杂度取决于（）。

问题的规模待处理的数据的初态问题的难度 A 和 B[D] 教师批改：D3、下列选项中，不是算法基本特征的是（）。

可行性有穷性确定性高效率[D] 教师批改：D4、通常一个好的算法应达到的目标中，不包括（）。

正确性可读性技巧性健壮性[C] 教师批改：C5、在一般的计算机系统中，基本的运算和操作不包括（）。

语法处理算术运算关系运算数据传输[A] 教师批改：A6、工程上常用的分治法是（）。

列举法归纳法减半递推技术回溯法[C] 教师批改：C多选题7、算法设计的要求包括（）。

正确性可读性健壮性唯一性[ABC] 教师批改：A，B，C8、算法的时间复杂度应该与（）无关。

所使用的计算机程序设计语言基本运算的执行次数程序编制者[ABD] 教师批改：A，B，D9、下列关于算法的描述中，不正确的有（）。

算法即是计算机程序算法是解决问题的计算方法算法是排序方法算法是解决问题的有限运算序列[ABC] 教师批改：A，B，C填空题16、所谓算法是指（）。

教师批改：解题方案的准确而完整的描述17、算法的基本特征有（）、（）、（）和（）教师批改：能行性、确定性、有穷性和拥有足够的情报。

18、一个算法通常由两种基本要素组成，它们是（）和（）。

教师批改：算法中对数据的运算和操作。

算法的控制结构。

19、工程上常用的几种算法设计方法有列举法、（）、（）、（）、（）和回溯法。

教师批改：归纳法、递推、递归、减半递推技术。

20、算法的复杂度主要包括（）复杂度和（）复杂度。

教师批改：时间、空间综合题21、设给定3个整数a，b，c，试写出寻找这3个整数的中数的算法；并分析在平均情况与最坏情况下，该算法分别要做多少次比较？寻找这3个整数的中数的算法用C语言描述如下（中数m由函数值返回）：int mid ( int a, int b, int c){ int m ; m=a ;if ( m>=b ) { if (m>=c) { if ( b>=c ) m=b ; else m=c ; } }else { if ( m<=c) { if (b>=c) m=c; else m=b ; } }return ( m ) ;}假设a，b，c中的每一个数为中数的概率相等（均为1/3）。