第二章 线性表 练习题
- 格式：doc
- 大小：65.50 KB
- 文档页数：9
一、选择题
1．线性表的链接实现有利于( A )运算。
(A)插入 (B)读表元 (C)查找 (D)定位
2．设单链表中指针p指向结点A，若要删除A之后的结点(若存在)，则修改指针的
操作为( A)。
(A)P一＞next＝p一＞next一＞next (B)p＝P一＞next
(C)p＝P一＞next一＞next (D)p一＞next＝p
3．线性表采用链式存储时，其地址( D )。
(A)必须是连续的 (B)部分地址必须是连续的
(c)一定是不连续的 (D)连续与否均可以
4．在一个具有n个结点的单链表中查找其值等于x的结点．在查找成功的情况下需平均比较( c)个元素结点。
(A) n/2 (B) n (C) (n+1)/2 (D) (n-1)/2
5．在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是( B )。
(A) p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;
(B) s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;
(C) p->next=s; p->next->prior=s; s->prior=p; s->next=p->next;
(D) s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
6．已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分查找值为90的元素时，需( D )次比较可查找成功。
(A)1 (B)2 (C)3 (D)4
7．在顺序存储的线性表R[029]上进行顺序查找的平均查找长度为(①)，进行二
分查找的平均查找长度为(②)，讲行分块查找（设分为5块)的平均查找长度为(③)
①(A)15 (B)15．5 (C)16 (D)20
②(A)4 (B)62／15 (C)64／15 (D)25／6
③(A)6 (B)11 (C)5 (D)6．5
8．若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用( B )存储方式最节省时间。
(A)单链表 (B)双向链表 (C)单循环链表 (D)顺序表
二、填空题
1．循环链表的主要优点是__表的处理方便________________。
2．在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为______ f->prior=p; f->next=p->next; p->next=f; p->next->prior=f__________
3．双向循环链表的主要优点是____克服单链表的单向性__________。
4．在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为_____f->prior_＝p;f一＞next＝p一＞next;_ p->next->prior ＝f;p一＞next＝f。
5．若要在一个单链表的*p结点之前插入一个*s结点时，可执行下列操作 s->next=____p->next________； p->next=s；t=p->data；p->data=_ s->data _；s->data=____t _____。
6．假定对线性表R[059]进行分块查找，共分10块，每块长度等于6。若假定查找索引表和块均用顺序查找法，则查找每一个元素的平均查找时间为___________。
7．在一个长度为n的顺序表中插入一个元素，最少需要移动_0_个元素，最多需要移动____n____个元素。
8．如果某线性表的每一个元素都没有后继元素，则其长度最多是_1______________。
9．设单链表中指针p指着结点A，若要删除A之后的结点(假设存在), 则需要修改指针的操作为__p->next=p->next->next_____________。
三、判断题
1．具有线性序关系的集合中，若a，b是集合中的任意两个元素，则必有a
2．在单链表中任何两个元素的存储位置之间都有固定的联系，因此可以从首结点进行查找任何一个元素。(错 )
3．如果某数据结构的每一个元素都最多只有一个直接前驱，则必为线性表。（错 ）
4．一个有序的单链表不能采用折半查找法进行查找。(错)
5．线性表的惟一存储形式就是链表。( 错 )
四、读程序填空
1．以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素。如果找不到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成以下程序。(8分)
typedef struct {
int elem[100];
int length;
}SQ;
int ins(SQ *a, int x, int y)
{
int k,i;
if( _a=NULL_ )
return 0;
for(k=0; klength; k++)
if(a->elem[k]==x)
break;
if(k==a->length) k--;
else
for(i=a->length-1; i>k; i--) ____a->elem[i+1]=a->elem[i]__________ ;
____a->elem[k]__ =y;
return 1;
}
2．在单链表(表首指针为head)的元素中找出最后一个值为e的元素，返回其指针；如果找不到，返回NULL。完成以下程序。(6分)
Typedef struct LinkNode{
int data;
Struct LinkNode *next;
}Node;
Node *search_link(Node *head, int e)
{
Node *p, *q;
q=____head___ ;
for(p=head; __p->next!=NULL_ ; p=p->next)
if(p->data==e) ____q=p____________;
return q;
}
3．已知单链表的表首指针为head，下面的函数delete是从单链表中删除指针为p的结点，并返回新的表首指针。请完成如下程序。(4分)
typedef struct LinkNode{
int data;
struct LinkNode *next;
}Node;
Node *delete(Node *head, Node *p)
{
Node *pf;
if(head==p){
head=______head->next____________;
free(p);}
else{
for(pf=head; pf->next!=p; pf=pf->next);
_____p_ = p->next;
free(p);}
}
return head;
}
4．以下算法是将线性表L中所有负数元素删除，返回被删除的元素个数。完成以下算法。(7分)
typedef struct{
int elem[100];
int length;
}SQ;
int deln(SQ *L)
{
／* 算法思路是，对每个元素做以下循环，如果第i个元素大于等于0，且前面有c个小于0的元素，则将它前移c个位置*／
int i，c; ／* c将记录小于0的元素个数 *／ for(i=0,c=0; ilength; i++)
{
if(__SQ->elem[i]_<0) c++;
else if(c>0) x->e[i - ____c______]=x->e[i];
}
x->length=_x->length-c_____;
return c;
}
5．以下算法将元素递增排列的顺序存储线性表A和B的元素的交集存人线性表C中。在空格处填上合适的语句或表达式完成该算法。(每空2分)
void SqList_Intersect(SqList A, SqList B, SqList &C
{ int i=1,j=1,k=0; ／* 下标初始化，A、B、C的下标都从1开始 */
while(i<=A.num && j<=B.num) ／* A、B表均末到表尾 */
{if(A.elem[i]
____i++_________;
if(_A.elem[i]>B.elem[j]_) j++;
if(A.elem[i]==B.elem[j]) ／* 当发现了一个在A和B中都存在的元素 *／
{C.elem[_k++_]=A.elem[i]; /* 添加到C中 */
i++; j++;
}
}/* while */
C.num=k; /* C表长度置位 */
} /* SqList_Intersect */
6．已知一个单链表的表首指针为h，每个结点含元素值data和下一结点的地址next。链表一共有5个结点，其元素值分别为100，200，300，400，500，经过下列语句后，输出什么结果?(3分)
for(p=h; p->data<300; p=p->next);
p->next=p->next->next;
printf("%d", p->data);
答案：300
五、简答题
1．排序
(1)写出线性表(26，45，12，z0，30，5，15，29，16，2，18)采用基数排序后，第一趟结束时的结果。(4分)
(2)线性表采用简单选择排序算法对线性表(26，15，12，16，5，30)进行排序，进行交换的第一对元素是哪两个元素，在什么情况下，第一趟不需要进行元素的交换?(6分)
2．线性表有顺序表和链表两种存储结构，简述各自的优缺点。（4分）
顺序存储结构的特点：以数据元素在计算机内“物理位置相邻”来表示顺序表中数据元素之间的逻辑关系，能随机存取顺序表中任一数据元素。但它也使得插入和删除操作需移动大量的数据元素。由于顺序表需要一组地址连续的存储单元，对于长度可变的线性表就需要预分配足够的空间，有可能使一部分存储空间长期闲置不能充分利用。也可能由于估计不足，当表长超过预分配的空间而造成溢出，在这种情况下，又难于扩充连续的存储空间。
