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

第2章线性表

选择题

1.对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素,则选择()最节省时间

A)顺序表B)带头结点的双循环链表

C)单链表D)带尾结点的单循环链表

【答案】A

2.双向链表中有两个指针域,prior和next,分别指向前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为()

A)p-prior=q;q-next=p;p-prior-next=q;q-prior=p-prior;

B)q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q-next;

C)q-next=p;p-next=q;p-prior-next=q;q-next=p;

D)p-prior-next=q;q-next=p;q-prior=p-prior;p-prior=q;

【答案】D

3.在一个以h为头指针的单循环链中,p指针指向链尾结点的条件是()

A)p-next==NULLB)p-next==h

C)p-next-next==hD)p-data==-1

【答案】B

4.在双向链表存储结构中,删除p所指的结点时须修改指针()

A)p-prior-next=p-nextp-next-prior=p-prior;

B)p-prior=p-prior-priorp-prior-next=p;

C)p-next-prior=pp-next=p-next-next

D)p-next=p-prior-priorp-prior=p-next-next;

【答案】A

5.线性表采用链式存储时,其元素地址()

A)必须是连续的B)一定是不连续的

C)部分地址是连续的D)连续与否均可

【答案】D

填空题

1.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是_____________。

【答案】(n-1)/2

2.在单链表中设置头结点的作用是_____________。

【答案】主要是使插入和删除等操作统一,在第一个元素之前插入元素和删除第一个结点不必另作判断。另外,不论链表是否为空,链表头指针不变。

3.线性表的顺序存储是通过_____________来反应元素之间的逻辑关系,而链式存储结构是通过_____________来反应元素之间的逻辑关系。

【答案】(1)数据元素的前后顺序(2)元素中的指针

4.当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,则采用_____________存储结构最节省时间,相反当经常进行插入和删除操作时,则采用_____________存储结构最节省时间。

【答案】(1)顺序(2)链式

5.对于双向链表,在两个结点之间插入一个新结点需修改的指针共_____________个,单链表为_____________个。

【答案】(1)4(2)2

6.循环单链表的最大优点是_____________。

【答案】从任一结点出发都可访问到链表中每一个元素。

7.若要在一个不带头结点的单链表的首结点*p结点之前插入一个*s结点时,可执行下列操作:

s-next=_____________;

p-next=s;

t=p-data;

p-data=_____________;

s-data=_____________;

【答案】(1)p-next(2)s-data(3)t

8.某线性表采用顺序存储结构,每个元素占据4个存储单元,首地址为100,则下标为11的(第12个)元素的存储地址为_____________。

【答案】144

判断题

1.取线性表的第i个元素的时间同i的大小有关()

【答案】×

2.线性表的特点是每个元素都有一个前驱和一个后继()

【答案】×

3.顺序存储方式的优点是存储密度大,且插入、删除运算效率高()

【答案】×

4.线性表采用链表存储时,结点的存储空间可以是不连续的()

【答案】√

5.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存储结构中效率高()

【答案】√

6.顺序存储方式只能用于存储线性结构()

【答案】×

【解析】线性结构、树型结构和图状结构均可用顺序存储表示。

7.顺序存储结构的主要缺点是不利于插入或删除操作()

【答案】√

8.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好()

【答案】×