《计算机软件技术基础》课后题答案 - 图文(2)

}，画出这个逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？

答：图略。开始结点k1、k2，终端结点k6、k7。

7．设有如图1.1所示的逻辑结构图，给出它的逻辑结构，并说出它是什么类型的逻辑结构。

答：数据逻辑结构为：D={k1，k2，k3，?，k8}，R={，，，，，，}，其逻辑结构类型为树型结构。

8．分析下列程序的时间复杂度(设n为正整数)。 (1)int rec(int n)

{if(n==1)return(1)； else return(n*rec(n-1))； } (2)x=91；y=100；

While (y>0) if(x>10) y--； (3)i=1；j=0； while(i+j<=n)

if(i>j)j++； else i++; (4)x=n；y=0；

while(x>=(y+1)*(y+1)) y++；

答：(1) O(n) (2) O(1) (3) O(n) (4) O(n)

6

1/2

9．设n为正数。试确定下列各程序段中前面加记号@的语句的频度： (1)i=1；k=0；

while(i<=n-1) {@k+=10*i； i++； ) (2) k=0；

for(i=1；i<=n；i++)

for(j=i；j<=n：j++) @k++； 答：(1)n-1 (2)n+(n-1)+??+1=n(n+1)/2

第二节 线性表 一、选择题

1．线性结构中的一个结点代表一个( )。

*A．数据元素 B．数据项 C．数据 D．数据结构

2．线性表L=(a1，a2，?，ai，?，an)，下列说法正确的是( )。

A．每个元素都有一个直接前驱和直接后继 B．线性表中至少要有一个元素 C．表中诸元素的排列顺序必须是由小到大或由大到小的 D．*除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继 3．顺序表是线性表的( )。

A．链式存储结构 *B．顺序存储结构 C．索引存储结构 D．散列存储结构 4．对于顺序表，以下说法错误的是( )。

* A．顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B．顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C．顺序表的特点是：逻辑结构中相邻的结点在存储结构中仍相邻 D．顺序表的特点是：逻辑上相邻的元素，存储在物理位置也相邻的单元中 5．对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( )为标准操

7

作。

A．条件判断 *B．结点移动 C．算术表达式 D．赋值语句 6．对于顺序表的优缺点，以下说法错误的是( )。

A．无需为表示结点间的逻辑关系而增加额外的存储空间 B．可以方便地随机存取表中的任一结点 *C．插入和删除操作较方便 D．由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)

7．在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为( )。

A．n *B．n/2 C．(n-1)/2 D．(n+1)/2

8．在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数为( )。

A．n B．n/2 *C．(n-1)/2 D．(n+1)/2 9．带头结点的单链表为空的条件是( )。

A．head=NULL *B．head->next=NULL C．head->next=head D．head!=NULL 10．非空单循环链表head的尾结点*p满足( )。

A．p->next=NULL B．p=NULL *C．p->next=head D．p=head 11．在双循环链表的*p结点之后插入*s结点的操作是( )。

A．p->next=s；s->prior=p；p->next->prior=s；s->next=p->next； B．p->next=s；p->next->prior=s；s->prior=p：s->next=p->next； C．s->prior=p；s->next=p->next；p->next=s；p->next->prior=s； *D．s->prior=p；s->next=p->next；p->next->pror=s；p->next=s； 12. 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行( )。

A．s->next=p->next；p->next=s； B．p->next=s->next；s->next=p；

8

*C．q->next=s; s->next=p； D．p->next=s; s->next=q；

13. 在一个单链表中，若*p结点不是最后结点。在*p之后插入结点*s，则执行( )。

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;

14. 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用( )存储方式最节省时间。

*A．顺序表 B. 单链表 C．双链表 D．单循环链表

15．设rear是指向非空带头结点的单循环链表的尾指针，则删除表头结点的操作可表示为( )。

A．p=rear；rear=rear->next； free(p) B．rear=rear->next；free(rear)； C．rear=rear->next->next； free(rear)； *D．p=rear->next->next；rear->next->next=p->next；free(p)； 16．在一个单链表中，若删除*p结点的后继结点，则执行( )。

*A．q=p->next；p->next=q->next；free(q)； B．p=p->next；p->next=p->next->next；free(p)； C．p->next=p->next；free(p->next)； D．p=p->next->next；free(p->next)；

17．设指针p指向双链表的某一结点，则双链表结构的对称性可用( )式来刻画。 AB*C

．．．

p->prior->next->==p->next->next p->prior->prior==p->next->prior p->prior->next->==p->next->prior

D．p->next->next==p->prior->prior

18．在循环链表中，将头指针改设为尾指针rear后，其头结点和尾结点的存储

9

位置分别是( )。 A．rear

和

rear->next->next *B．rear->next

和

rear

C．rear->next->next和rear D．rear和rear->next 19．循环链表的主要优点是( )。

A．不再需要头指针了 B．已知某个结点的位置后，容易找到它的直接前驱 C．在进行插入、删除操作时，能更好地保证链表不断开 *D．从表中任一结点出发都能扫描到整个链表

20．在线性表的下列存储结构中，读取元素花费时间最少的是( )。 A．单链表 B．双链表 C．循环链表 *D．顺序表 二、判断题

√1．顺序存储的线性表可以随机存取。

╳2．顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。

√3．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

╳4．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。

√5．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 √6．在单链表中，可以从头结点开始查找任何一个元素。 ╳7．线性表的链式存储结构优于顺序存储结构。

√8．在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。

╳9．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

10