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

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.next; do{

if (q.data

if(min!=p){temp=min.data; min.data=p.data; p.data=temp;} p=p.next; }//while }//selectsort

⑶试在OnelinkList类中添加方法public void reverse()，用于对单链表进行就地逆置。 分析：⑴将头结点与表中其它结点断开，独自构成一新空表；

⑵将原表中结点逐一取下并插入新表，每次插入均在头结点之后进行。 参考答案：

public void reverse ( ){

r=head.next; //r指向剩余链表 head.next=null; //断开单链表的头结点 while (r!=null){

p=r; //p指向当前待处理结点 r=r.next; p.next=head.next;

head.next=p; //将当前待处理结点插入在头结点之后 }//while }//reverse

2.设有顺序表类SqList如下： public class SqList { private Object[] table; private int len;

public SqList(int maxsize){ table=new Object[maxsize]; len=0; }

}

并有结点类OnelinkNode和单链表类OnelinkList如下： public class OnelinkNode{ public Object data;

public OnelinkNode next; public OnelinkNode(Object obj){ data=obj; next=null; }

public OnelinkNode(){ this(null); }

}//OnelinkNode

public class OnelinkList{

private OnelinkNode head; //单链表的头指针 public OnelinkList(){ head=new OnelinkNode(); } }

试在OnelinkList类中添加构造函数public OnelinkList(SqList L)。 参考答案：

先在SqList类中添加下列方法：

public Object get(int i){ if (i<0||i>len) return null; else return table[i]; } public int length(){ return len; }

然后在OnelinkList中添加如下构造函数： public OnelinkList(SqList L){

head=new OnelinkNode(); for(i=L.length()-1;i>=0;i--){ s=new OnelinkNode(L.get(i)); s.next=head.next; head.next=s; }//for }//OnelinkList

3. 设有循环链表如下，试定义相应的循环链表类，并在其中添加一个可以将链表中指针方向取反的方法。

参考答案：

public class OnelinkNode{ public Object data; public OnelinkNode next; public OnelinkNode(Object obj){ data=obj; next=null; }

public OnelinkNode(){ this(null); }

}//OnelinkNode

本文来源：https://www.bwwdw.com/article/mvef.html