第二章线性表答案

《第二章线性表答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、习题与练习二一、选择题1.线性表是（A）oA.一个有限序列，可以为空B.一个有限序列，不可以为空C.一个无限序列，可以为空D.一个无限序列，不可以为空2.以下关于线性表的说法不正确的是（C）oA.线性表中的数据元素可以是数字、字符、记录等不同类型。B.线性表中包含的数据元素个数不是任意的。C.线性表中的每个结点都有且只有一个直接前趋和直接后继。D.存在这样的线性表：表中各结点都没有直接前趋和直接后继。3.线性表的顺序存储结构是一种（A）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取4.在顺序表中，只要知道（D）,就可在相同时间内求出任一结点的存储地

2、址。A.基地址B.结点大小C.向量大小D.基地址和结点大小5.在等概率情况下，顺序表的插入操作要移动（B）结点。A.全部B.一半C.三分之一D.四分之一6•在（C）运算中，使用顺序表比链表好。A.插入B・删除C.根据序号查找D.根据元素值查找7在一个长度为n的顺序存储线性表中，向第i个元素（lWiWn+1）之前插入一个新元素时，需要从后向前依次后移（B）个元素。A.n—jB.n—j+lC・n—j—lD.j8若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。A顺序表B双链表C带头节点的双循环链表D单循环链表9

3、链表不具有的特点是（B）.A插入、删除不需要移动元素B可随机访问任一元素C不必事先估计存储空间D所需空间与线性长度成正比10在单链表指针为P的节点之后插入指针为S的节点，正确的操作是（B）.A.p->next二s;s->next=p->next;C.p—〉next二s;p—>next=s~>next;B.s->next=p->next;p->next二s;D.p->next=s->next;p->next=s;11在双向链表指针P的节点前插入一个指针q的节点，正确的操作是（0.A.p->prior=qq—〉next二p:p->prior一〉next二q;q—〉p

4、rior二q;B.p->prior=q;p->prior->next=q;q->next二p;q->prior=p->prior;C・q->next=pq~>prior=p->prior;p->prior->next=q;p->prior=q;D.q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;12在一个以h为头的单循环链中，p指针指向链尾的条件是(B)。A.p->ncxt==hB.p->ncxt==NULLA.p->next->next==hD.p->data==-l13用链接方式存储的队列，在进行删除运算时

5、(D).A仅修改头指针B仅修改尾指针C头、尾指针都要修改D头、尾指针可能都要修改14在一个单链表HL中，若要删除由指针q所指向节点的后继节点,贝执行(B)oA.p二q->next:p->next=q->next;B.p二q->next;q-〉next二p->next;C・p二q->next;q->next=p;B.q->next=q->next->ncxt;q-〉ncxt=q;15静态链表中指针表示的是(B)oA内存地址B数组下标C下一元素地址D左、右孩子地址16对于一个头指针为head的带头节点的单链茬，判定该表为空表的条件是(B).A.hcad==NULLB

6、.hcad->ncxt==NULLC.head->next二二headD.head!=NULL17.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是(B)o二、填空题1.线性表是一种典型的结构。线性2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移个元素。n-i+13•顺序表中逻辑上相邻的元素的物理位置o相邻4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需—一个位置，移动过程是从向依次移动每一个元素。后移后前5.在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链接存储中，元素之间的逻辑关系是通

7、过决定的。物理位置指针6.在双向链表中，每个结点含有两个指针域，一个指向结点,另一个指向结点。前趋后继7•顺序表中逻辑上相邻的元素，物理位置相邻，单链表中逻辑上相邻的元素，物理位置相邻。一定不一定8.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为,在给定值为X的结点后插入一个新结点的时间复杂度为o0(1)0(n)9.下述算法的功能是什么？链表首元素与尾元素对换LinkList*Demo(LinkList*L){//L是无头结点的单链表LinkList*q,*p;辻(L&&L->next){q=L;L=L->ncxt:p=L;while

8、(p->next)p=p