《数据结构ch2习题答案》由会员分享，可在线阅读，更多相关《数据结构ch2习题答案（11页珍藏版）》请在金锄头文库上搜索。
1、Ch2线性表一填空：1按顺序存储方法存储的线性表称为 顺序表 ，按链式存储方法存储的线表称为 链表 。2线性表是n个数据元素的 有限序列 。3在个n结点的顺序表中插入一个结点需平均移动 n/2 个结点，在第i个之前插入一个元素时，需向后移动 n-i+1 个元素。1 2 3 i-1 i i+1 n4在个n结点的顺序表中删除一个结点需平均移动 (n-1)/2 个结点，删除第i个元素时，需向前移动 n-i 个元素。5一个顺序表的第一个元素的存储地址是1000，每个元素的长度是2，则向量的第五个元素的地址是 1008 。Loc(ai)=Loc(a1)+(i-1)*L6带头结点的单链表head为空的判定
2、条件是 head-next=NULL ，不带头结点的单链表head为空的判定条件是 head=NULL 。7在一个单链表中，已知p所指结点不是最后结点，若删除p的后继结点，则执行 p-next=p-next-next 。8用单链表方式存储的线性表，存储每个结点需要两个域，一个是 数据 域，另一个是 指针 域。9在一个单链表中，已知p所指结点是q所指结点的前驱结点，若在q之前插入结点s，要执行的操作为 p-next=s;s-next=q 。10线性表的顺序存储结构是用一组 地址连续的存储单元 依次存储各元素。11在双向链表中，每个结点有两个指针域，一个指向 前驱 ，另一个指向 后继 。12在一个
3、单链表中的p所指结点之后插入一个s所指结点时，执行的操作为 s-next=p-next；p-next=s 。13在一个单链表中的p所指结点之前插入一个s所指结点时，执行的操作为s-next=p-next；p-next=s； t=p-data； p-data=s-data；s-data=t 。(交换)14在一个单链中删除p所指结点时，应执行的操作是 p -data=p-next-data；p-next=p-next-next 。15对于一个具有n个结点的单链表，在已知p所指结点之后插入一个新结点的时间复杂度为 O(1) ；在给定值为x的结点后插入一个新结点的时间复杂度为 O(n) 。16线性表的
4、顺序存储中，元素之间的逻辑关系是通过 相对位置 决定的；线性表的链接存储中，元素之间的逻辑关系是通过 指针 决定的。17在单链表中，每个结点有 1 个指针域，最后一个结点的指针域为 空 。18对于一个线性表经常进行的是存取操作，很少进行插入和删除操作时，则采用 顺序 存储结构为宜；相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构为宜。29顺序表相对于链表的优点有 容易实现 和 随机存取 。链表相对于顺序表的优点有 不需要预分配存储空间 和 插入、删除 操作方便。二选择：1下面关于线性表的叙述错误的是 D 。A若用数组表示，表中诸元素的存储位置是连在一起的 B若用链表表示，便于插入和
5、删除操作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线性表的每个元素都有一个直接前驱和直接后继 B线性表至少要有一个元素C线性表中的元素必
6、须按递增或递减的顺序排列D除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继6对于一个线性表若既要求能够进行较快的插入和删除，又要求存储结构能反映数据元素间的逻辑关系，应该 B A以顺序方式存储 B以链接方式存储 C以散列方式存储 D.以索引方式存储7下列描述线性表叙述错误的是 A A线性表的顺序存储的元素是从小到大顺序排列的 B线性表的链接存储，便于插入删除操作C除第一个元素和最后一个元素外，其余每个元素有且仅有一个直接前驱和直接后继 D线性表可以为空8线性表的逻辑顺序与存储顺序总是一致的，这种说法 B A正确 B不正确9与数据元素本身的形式、内容、相对位置、个数
7、无关的是数据的 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, next，下面算法要找出不带头节点的单链表中第i个元素的位置。此算法是 B A正确 B错误Lin
8、klist Get(Linklist V, int i ) p=V; if(p=NULL) return (NULL); for(j=1;jjnext; if(p=NULL) return (NULL); return p; 三. 综合1已知一个单链表如图所示，编写一个函数将该单链表复制一个拷贝。解：本题的算法思想是依次查找该单链表（其头指针为head1）中的每个节点，对每个节点复制一个新节点并链接到新的单链表（其头指针为head2）中。实现本题功能的函数如下： void copy(LinkList head1,LinkList head2) LinkList p,q,new;head2=(L
9、inkList)malloc(sizeof(Node); /*建立一个头节点*/p=head1;q=head2;while(p!=NULL) new= LinkList)malloc(sizeof(Node); /*复制一个新节点new*/ new-Data=p-Data;q-Next=new; /*将new链接到q之后*/q=new;p=p-Next;q-Next=NULL; /*将最后一个节点的Next域置为NULL*/p=head2; /*删除头节点*/head2-head2-Next;free(p);2编写一个函数交换单链表中p所指向的位置和其后续位置上的两个节点，head指向该单链表
10、的表头，p指向该单链表中的某一节点。解：本题的算法思想是：如果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-next; q-next=p; head=q;else /*若p指向第二个之后的节点*/ back=head; /*查找p
11、的前驱节点*/ while(back-next!=p) back=back-next; back-next=q; /*交换p和q的位置*/ p-next =q-next; q-next=p; return(head);else return(NULL);/*若p不存在后续，则返回NULL*/3有两个具有相同节点个数的单链表heada和headb如图所示，编写一个函数将其合并成如图所示的单链表headc。a1an a2heada b1bn b2headb bn b2a2anb1a1headc 解：本题的算法思想是:遍历两个单链表heada,headb,依次将两链表中的节点复制headc中，直到链
12、表遍历完为止。实现本题功能的函数如下：LinkList sum(LinkList heada,LinkList headb) LinkList headc; headc=(LinkList)malloc(sizeof(LNode); pa=heada;pb=headb;pc=headc;while(pa!=NULL) newnode=(LinkList)malloc(sizeof(Node); /*复制一个与heada链表中节点相同的节点，把它链接到headc中*/ newnode-data=pa-data;pc-next=newnode;pa=pa-next;pc=newnode; /*pc始终指向headc链表的最后一个节点*/ new=(LinkList)malloc(sizeof(LNode); /*复制一个与headb链表中节点相同的节点，把它链接到headc中*/ newnode-data=pb-data;pc-next=newnode;pb=pb-next;pc=newnode; /*pc始终指向headc链表的最后一个节点*/ pc-next=NULL; newnode=headc
