第二章作业解答一、基础知识题2.1试描述头指针、头结点、开始结点的区别，并说明头指针和头结点的作用。
答：头指针是指向头结点或开始结点的指针，我们就是靠它来描述和访问整个线性链表，如果失去了头指针，整个线性链表也就无法访问，因而线性链表的存在与否也就失去了意义。
头结点是为了对线性链表操作的方便而引入的，引入头结点主要有两方面的方便，一是当在线性链表的第一个位置进行操作时无需做特殊处理；二是就整个线性链表而言无论空表和非空表，对表的操作可以保持一致性。
头结点的数据域为空而指针域指向开始结点，如果存在头结点，那么线性链表的头指针就指向它。
开始结点是真正存储数据的第一个线性链表的结点，如果有头结点的话，头结点的指针域就指向它；如果没有头结点的话，头指针就指向它。
2.2何时选用顺序表、何时选用链表作为线性表的存储结构为宜？答：从空间复杂度上考虑：顺序表的存储空间是静态分配的，链表的存储空间是动态分配的，顺序表的存储密度为1，链表的存储密度小于1，因此如果表的长度变化较大，事先难以确定表的规模宜采用链表，否则用顺序表。
从时间复杂度上考虑：顺序表的最大优点是，它是一种随机存取结构，查找算法的时间复杂度低；最大缺点是插入删除操作的时间复杂度较链表高；链表的最大优点是插入删除操作的时间复杂度低；最大缺点是查找算法的时间复杂度较顺序表高。
因此对于频繁进行插入和删除的线性表，宜采用链表做存储结构。
若插入和删除操作较少，而查找操作较多时宜采用顺序表。
2.3在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应链表中删除？若可以，其时间复杂度各为多少？答：要删除某结点，我们需要知道该结点的前后两个结点。
在单链表中，不知道头指针，则无法访问该结点的前一个结点，因此无法删除。
在双链表中可以删除，时间复杂度为O(1)。
在单循环链表中可以删除，时间复杂度为O(n)。
2.4下述算法的功能是什么？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功能是：如果线性表的长度大于1，则将线性表第一个位置上结点放到最后一个位置上。
形考作业一题目1把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（选择一项：A. 逻辑结构B. 给相关变量分配存储单元C. 算法的具体实现D. 物理结构题目2下列说法中，不正确的是（）。
选择一项：A. 数据可有若干个数据元素构成B. 数据元素是数据的基本单位C. 数据项是数据中不可分割的最小可标识单位* D.数据项可由若干个数据元素构成题目3一个存储结点存储一个（）。
选择一项：A. 数据结构B. 数据类型C. 数据项* D.数据元素题目4数据结构中，与所使用的计算机无关的是数据的（）。
选择一项：A. 物理结构母B.逻辑结构C. 物理和存储结构D. 存储结构题目5下列的叙述中，不属于算法特性的是（）。
选择一项：A.有穷性B.可行性■*C.可读性C D.输入性题目6正确获得分中的分A.研究算法中的输入和输出的关系°B.分析算法的易懂性和文档性I二C.分析算法的效率以求改进D. 找出数据结构的合理性题目7算法指的是（）。
选择一项：A. 排序方法B. 解决问题的计算方法C. 计算机程序I* D.解决问题的有限运算序列题目8算法的时间复杂度与（）有关。
选择一项：A.所使用的计算机□ B.数据结构* C.算法本身D. 计算机的操作系统题目9设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第素），插入一个元i个元素，则移动元素个数为（）。
选择一项：A. n-i+1B. n-i-1C. n-iD. i题目10设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（选择一项：A.B. n-i-1因C. n-i+1D. i题目11在一个单链表中，p、q分别指向表中两个相邻的结点，且后继，现要删除q所指结点，可用语句（）O 选择一项：A. p->n ext=q->nextr-iB. p=q _>n ext◎ C. q-> next=NULLD. P_>next=q题目12在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（选择一项：C-A. p=s->nextB. p・>n ext= s; s->n ext=p・>next仁C. p->n ext=s->n ext;D. s・>n ext=p->n ext; p・>next=s-题目13非空的单向循环链表的尾结点满足（）（设头指针为head,选择一项：r —A. p== headB. p==NULLC. p・>n ext==headD. p->n ext==NULL题目14链表不具有的特点是（）o 选择一项：A. 可随机访问任一元素B. 插入删除不需要移动兀索C. 不必事先估计存储空间D. 所需空间与线性表长度成正比题目15带头结点的链表为空的判断条件是（）（设头指针为head ）。
大工16秋《数据结构》在线作业21：若一棵二叉树的先序遍历序列为abdgcefh，中序遍历的序列为dgbaechf，则后序遍历的结果为（）。
A：gdbehfcaB：bdgaechfC：gdbecfhaD：gcefhabd正确答案：A2：具有3个结点的二叉树可能有（）种不同的形态。
A：3B：4C：5D：6正确答案：C3：若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（）。
A：cbedaB：decabC：deabcD：cedba正确答案：D4：（）方法可以判断出一个有向图中是否有环（回路）。
A：深度优先遍历B：拓扑排序C：求最短路径D：求关键路径正确答案：B5：深度为k的完全二叉树，其叶子结点必在第（）层上。
A：k-1B：1C：kD：k-1或k正确答案：D6：Huffman树的带权路径长度WPL等于（）。
A：除根结点之外的所有结点权值之和B：所有结点权值之和C：根结点的值D：各叶子结点的带权路径长度之和正确答案：D7：具有N个结点的完全二叉树的深度是（）。
A：log2NB：log2N +1C：log2(2N)D：log2N -1正确答案：B8：设有8个结点的无向图，该图至少应有（）条边才能确保是一个连通图。
A：5B：6C：7D：8正确答案：C9：任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（）。
A：发生改变B：不发生改变C：不能确定D：以上都不对正确答案：B10：一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。
A：250B：254C：501D：505正确答案：C11：在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
A：错误B：正确正确答案：A12：中缀表达式A+(B-C/D)*E的后缀形式是ABCD/-E*+。
A：错误B：正确正确答案：B13：度为2的有序树是二叉树。
A：错误B：正确正确答案：A14：若已知一棵二叉树的前序遍历序列和后序遍历序列，可以恢复该二叉树。
国家开放大学《数据结构（本）》形考作业1-4参考答案形考作业1一、单项选择题（每小题3分，共60分）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. 不能随机访问任一结点7.下列的叙述中，不属于算法特性的是（）。
A. 可读性B. 输入性C. 可行性D. 有穷性8.算法的时间复杂度与（）有关。
A. 算法本身B. 计算机的操作系统C. 数据结构D. 所使用的计算机9.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。
A. n-i+1B. n-i-1C. n-iD. i10.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。
A. iB. n-iC. n-i-1D. n-i+111.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。
A. p->next=q->nextB. p=q->nextC. p->next=qD. q->next=NULL12.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。
