信息学奥赛初赛数据结构之二 .pdfVIP

数据结构复习题

一、选择题

1.算法的计算量的大小称为计算的（）。

A．效率B.复杂性C.现实性D.难度

2.算法的时间复杂度取决于（）

A．问题的规模B.待处理数据的初态C.A和B

3.计算机算法指的是（），它必须具备（）这三个特性。

(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法

(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性D.易读性、稳定性、安全性

4．以下数据结构中，（）是非线性数据结构

A．树B．字符串C．队D．栈

5.下列数据中，（）是非线性数据结构。

A．栈B.队列C.完全二叉树D.堆

6．以下属于逻辑结构的是（）。

A．顺序表B.哈希表C.有序表D.单链表

7．下面关于线性表的叙述中，错误的是哪一个？（）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

8．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储

方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表

9．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。

A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表

10.链表不具有的特点是（）

A．插入、删除不需要移动元素B．可随机访问任一元素

C．不必事先估计存储空间D．所需空间与线性长度成正比

11．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向

一待插入结点，现要求在p前插入q，则正确的插入为（）

A.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q^.llink:=p^.llink;

B.q＾.llink:=p^.llink;p＾.llink^.rlink:=q;q＾.rlink:=p;p^.llink:=q^.rlink;

C.q^.rlink:=p;p^.rlink:=q;p^.llink^.rlink:=q;q^.rlink:=p;

D.p^.llink^.rlink:=q;q^.rlink:=p;q^.llink:=p^.llink;p^.llink:=q;

12．在双向链表指针p的结点前插入一个指针q的结点操作是（）。

A.p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q；

B.p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink;

C.q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q;

D.q-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q;

13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）

A．head==NULLB．head→next==NULLC．head→next==headD．head!=NULL

14.在双向链表存储结构中，删除p所指的结点时须修改指针（）。

A．(p^.llink)^.rlink:=p^.rlink(p^.rlink)^.llink:=p^.llink;

B．p^.llink:=(p^.llink)^.llink(p^.llink)^.rlink:=p;

C．(p^.rlink)^.llink:=pp^.rlink:=(p^.rlink)^.rlink

D．p^.rlink:=(p^.llink)^.llinkp^.llink:=(p^.rlink)^.rlink;

15.对于栈操作数据的原则是（）。

A.先进先出B.后进先出C.后进后出D.不分顺序

16.在作进栈运算时,应先判别栈是否(①),在作退栈运算时应先判别栈是否(②)。当栈中元素为n个,作

进栈运算时发生上溢,则说明该栈的最大容量为(③)。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(④

)分别设在这片