数据结构Ch2习题答案Word下载.docx

1、next=q 。10线性表的顺序存储结构是用一组 地址持续的存储单元 依次存储各元素。11在双向链表中，每一个结点有两个指针域，一个指向 前驱 ，另一个指向 后继 。12在一个单链表中的p所指结点以后插入一个s所指结点时，执行的操作为 s-next；p-next=s 。13在一个单链表中的p所指结点之前插入一个s所指结点时，执行的操作为s-next=s； t=p-data； p-data=s-data=t 。（互换）14在一个单链中删除p所指结点时，应执行的操作是 p -data=p-15关于一个具有n个结点的单链表，在已知p所指结点以后插入一个新结点的时刻复杂度为 O（1） ；在给定值为x的

2、结点后插入一个新结点的时刻复杂度为 O（n） 。16线性表的顺序存储中，元素之间的逻辑关系是通过 相对位置 决定的；线性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。17在单链表中，每一个结点有 1 个指针域，最后一个结点的指针域为 空 。18关于一个线性表常常进行的是存取操作，很少进行插入和删除操作时，那么采纳 顺序 存储结构为宜；相反，当常常进行的是插入和删除操作时，那么采纳 链式 存储结构为宜。29顺序表相关于链表的优势有 容易实现 和 随机存取 。链表相关于顺序表的优势有 不需要预分派存储空间 和 插入、删除 操作方便。二选择：1下面关于线性表的表达错误的选项是 D 。A假设

3、用数组表示，表中诸元素的存储位置是连在一路的 B假设用链表表示，便于插入和删除操作C假设用链表表示，不需要占用一片相邻的存储空间 D表的插入和删除操作仅许诺在表的一端运行2用带表头结点的链表表示线性表的要紧益处是 B 。A能够加速对表的遍历 B使空表和非空表的处置统一 C节省存储空间 D能够提高存取元素的速度3线性表的顺序存储结构是一种 A 的存储结构。A随机存取 B顺序存取 C索引存取 DHASH存取4在线性表的第i个元素之前入一个元素时，需将第n至第i个元素 C 位置。A向前移动一个 B向前移动i个 C向后移动一个 D向后移动i个5在下面关于线性表的表达中，选出正确的一项 D A线性表的每

4、一个元素都有一个直接前驱和直接后继 B线性表至少要有一个元素C线性表中的元素必需按递增或递减的顺序排列D除第一个元素和最后一个元素外，其余每一个元素都有一个且仅有一个直接前驱和直接后继6关于一个线性表假设既要求能够进行较快的插入和删除，又要求存储结构能反映数据元素间的逻辑关系，应该 B A以顺序方式存储 B以链接方式存储 C以散列方式存储 D.以索引方式存储7以下描述线性表表达错误的选项是 A A线性表的顺序存储的元素是从小到大顺序排列的 B线性表的链接存储，便于插入删除操作C除第一个元素和最后一个元素外，其余每一个元素有且仅有一个直接前驱和直接后继 D线性表能够为空8线性表的逻辑顺序与存储顺

5、序老是一致的，这种说法 B A正确 B不正确9与数据元素本身的形式、内容、相对位置、个数无关的是数据的 C ？A存储结构 B存储实现 C逻辑结构 D运算实现10顺序存储结构 A A仅适合于静态查找表的存储 B仅适合于动态查找表的存储 C既适合静态又适合于动态查找表的存储 D既不适合静态又不适合于动态查找表的存储 11假设某线性表中最经常使用的操作是取第i个元素和找第i个元素的前趋元素，那么采纳 A 存储方式最节省时刻。 A顺序表 B单链表 C双链表 D单循环链表12关于有个元素的顺序表，任意删除一个元素后，平均移动次数约为 C An Blogn Cn/2 D113单链表的结点结构为data,

6、next，下面算法要找出不带头节点的单链表中第i个元素的位置。此算法是 B A正确 B错误Linklist Get（Linklist V, int i ） p=V; if（p=NULL） return （NULL）; for（j=1;jData=p-Data;q-Next=new; /*将new链接到q以后*/q=new;p=p-Next;Next=NULL; /*将最后一个节点的Next域置为NULL*/p=head2; /*删除头节点*/head2-head2-free（p）;2编写一个函数互换单链表中p所指向的位置和其后续位置上的两个节点，head指向该单链表的表头，p指向该单链表中的某

7、一节点。此题的算法思想是：若是p存在后续节点，看它是不是是头节点，若是是，那么互换后要改变该链表的head，假设不是头节点，那么直接互换。LinkList swap（LinkList head,LinkList p） LinkList q,back; q=p-next;if（q!=NULL） /*假设p存在后续节点，那么进行相应处置*/if（p=head） /*假设p指向头节点，那么将该链表的前两个节点互换位置*/ p-next=q- q-next=p; head=q;else /*假设p指向第二个以后的节点*/ back=head; /*查找p的前驱节点*/ while（back-next!

8、=p） back=back- back-next=q; /*互换p和q的位置*/next =q- return（head）;else return（NULL）;/*假设p不存在后续，那么返回NULL*/3有两个具有相同节点个数的单链表heada和headb如图所示，编写一个函数将其归并成如下图的单链表headc。heada headb headc 此题的算法思想是:遍历两个单链表heada,headb,依次将两链表中的节点复制headc中，直到链表遍历完为止。LinkList sum（LinkList heada,LinkList headb） LinkList headc; headc=（L

9、inkList）malloc（sizeof（LNode）; pa=heada;pb=headb;pc=headc;while（pa! newnode=（LinkList）malloc（sizeof（Node）; /*复制一个与heada链表中节点相同的节点，把它链接到headc中*/ newnode-data=pa-data;pc-next=newnode;pa=pa-pc=newnode; /*pc始终指向headc链表的最后一个节点*/ new=（LinkList）malloc（sizeof（LNode）; /*复制一个与headb链表中节点相同的节点，把它链接到headc中*/data=

10、pb-pb=pb- pc-next=NULL; newnode=headc; headc=headc- /*删除headc链表的头节点*/free（newnode）;4有一单链表，其结点的元素值以非递减有序排列。试编写删除该单链表中多余的元素值相同的结点的算法。此题采纳的算法是：从头至尾扫描该单链表，并作如此的操作：假设当前元素节点的元素值与后续节点的元素值不相等，那么指针后移，不然删除该后续节点，直到扫描所有的节点。void delete（LinkList head） 于开始结点的位置被寄存在头结点的指针域中，因此对链表第一个位置的操作同其他位置一样，不必特殊处置。不管链表是不是为空，其头指针是指向头结点的非空指针，因此了，简化了链表操作的实现。