数据结构第二章线性表习题..doc

02　线性表 【单选题】 1. 下列不属线性结构特点的是（C）。 Ａ、有且仅有一个数据元素无直接前驱 Ｂ、有且仅有一个数据元素无直接后继 Ｃ、有且仅有一个数据元素既无直接前驱又无直接后继 Ｄ、大多数据元素有且仅有一个直接前驱，有且仅有一个直接后继 2. 线性表是具有n个（C）的有限序列。 Ａ、信息项　Ｂ、字符　Ｃ、数据元素　Ｄ、数据项 3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 Ａ、正确　Ｂ、不正确 4. 在顺序表中，数据元素e1与其直接后继e2在存储位置上（A）。 Ａ、必相邻　Ｂ、必不相邻　Ｃ、可相邻可不相邻 5. 在长为n的顺序表中删除一个数据元素，平均需移动（D）个数据元素。 Ａ、n　Ｂ、n-1　Ｃ、n/2　Ｄ、(n-1)/2 6. 在长为n的顺序表中插入一个数据元素，平均需移动（C）个数据元素。 Ａ、n　Ｂ、n-1　Ｃ、n/2　Ｄ、(n-1)/2 7. 单链表是一种（B）存取的存储结构 Ａ、随机　Ｂ、顺序　Ｃ、索引　Ｄ、连续 8. 以下属于顺序存储结构优点的是（A）。 Ａ、存储密度大　Ｂ、插入运算方便　Ｃ、删除运算方便 Ｄ、可方便地用于各种逻辑结构的存储表示 9. 以下属单链表优点的是（C）。 Ａ、顺序存取　Ｂ、插入操作能在O(1)的时间复杂度上完成 Ｃ、插入时不需移动数据元素　Ｄ、节省存储空间 10.在单链表中，数据元素e1与其直接后继e2在存储位置上（C）。 Ａ、必相邻　Ｂ、必不相邻　Ｃ、可相邻可不相邻 11.以下属单链表与循环链表区别的是（B）。 Ａ、结点结构不同　Ｂ、查找结点的算法中，循环结束条件不同 Ｃ、对存储空间连续性的要求不同　Ｄ、对是否包含头结点的要求不同 12.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（A）存储方式最节省时间。 Ａ、顺序表　Ｂ、双链表　Ｃ、带头结点的双向循环链表　Ｄ、单循环链表 13.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（D）存储方式最节省运算时间。 Ａ、单链表　Ｂ、仅有头指针的单循环链表　Ｃ、双链表　Ｄ、仅有尾指针的单循环链表 14.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（D）存储方式最节省运算时间。 Ａ、单链表　Ｂ、单循环链表　Ｃ、带尾指针的单循环链表　Ｄ、带头结点的双循环链表 【计算题】 1. 设有单链表如图，试画出执行如下程序段后，各指针变量及单链表的示意图。 ⑴ p=L; while(p){ p.data=p.data*2; p=p.next; } 参考答案： ⑵ s=new OnelinkNode(8); p=L; while(p.next) p=p.next; s.next=p.next; p.next=s; 参考答案： 【算法题】 1. 设有结点类OnelinkNode和单链表类OnelinkList如下： public class OnelinkNode{ public int data; public OnelinkNode next; public OnelinkNode(int x){ data=x; next=null; } }//OnelinkNode public class OnelinkList{ private OnelinkNode head; //单链表的头指针 public OnelinkList(){ head=new OnelinkNode(0); } } ⑴试在OnelinkList类中添加方法public int deleteall(int x)，用于删除单链表中所有值为x的数据元素，并返回所删除的数据元素的总个数； 参考答案： public int deleteall(int x){ p=head; count=0; while(p.next!=null){ if (p.next.data==x){ p.next=p.next.next; count++; }else{ p=p.next; } }//while return count; }//deleteall ⑵试在OnelinkList类中添加方法public void selectsort()，用于按直接选择排序法对单链表中的数据元素进行排序。 参考答案： public void selectsort(){ p=head; while(p.next!=null){ min=p; q=p