数据结构(第二版)习题答案第3章

数据结构答案

第
3章线性表的链式存储


3.1选择题
（1）两个有序线性表分别具有 n个元素与 m个元素且 n≤m，现将其归并成一个有序表，
其最少的比较次数是（ A ）。
A．n B．m C．n . 1 D．m + n
（2）非空的循环单链表 head的尾结点（由 p所指向）满足（ C）。
A．p->next==NULL B．p==NULL C．p->next==head D．p==head
（3）在带头结点的单链表中查找 x应选择的程序体是（ C ）。
A．node *p=head->next; while (p && p->info!=x) p=p->next;
if (p->info==x) return p else return NULL;
B．node *p=head; while (p&& p->info!=x) p=p->next; return p;
C．node *p=head->next; while (p&&p->info!=x) p=p->next; return p;
D．node *p=head; while (p->info!=x) p=p->next ; return p;
（4）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。
A．必须是连续的 B．部分地址必须是连续的
C．一定是不连续的 D．连续不连续都可以
（5）在一个具有 n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间
复杂度是（ B ）。
A．O(1) B．O(n) C．O(n2) D．O(nlog2
n)
（6）用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队
尾结点，则在进行删除操作时（ D ）。
A．仅修改队头指针 B．仅修改队尾指针
C．队头、队尾指针都要修改 D．队头,队尾指针都可能要修改
（7）若从键盘输入 n个元素，则建立一个有序单向链表的时间复杂度为（ B ）。
A．O(n) B．O(n2) C．O(n3) D．O(n × log2n)
（8）下面哪个术语与数据的存储结构无关（ D ）。
A．顺序表 B．链表 C．散列表 D．队列
（9）在一个单链表中，若删除 p所指结点的后续结点，则执行（ A ）。
A．p->next=p->next->next; B．p=p->next; p->next=p->next->next;
C．p->next=p->next; D．p =p->next->next;
（10）在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（ B ）。
A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;
C．s->next=p->next;p=s; D．p->next=s;s->next=p;
3.2设计一个算法，求一个单链表中的结点个数。
【答】：单链表存储结构定义如下（相关文件： linklist.h）
#include <stdlib.h>

#include <stdio.h>
typedef struct node
{ int data;

struct node *next;
}linknode;
typedef linknode *linklist;
/*尾插法创建带头结点的单链表
*/
linklist creatlinklist()
{ linklist head,r,x,s;

head=r=(linklist)malloc(sizeof(linknode));
printf("\n请输入一组以
0结束的整数序列：
\n");
scanf("%d",&x);
while (x)
{ s=(linklist)malloc(sizeof(linknode));


s->data=x;
r->next=s;
r=s;
scanf("%d"
,&x);


}
r->next=NULL;
return head;


}
/*输出带头结点的单链表
*/
void print(linklist head)
{ linklist p;

p=head->next;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构(第二版)习题答案第3章在线全文阅读。