专升本数据结构试题解析(2)

数据结构上机实验与习题解析 亱店↘打烊oO

【答案】1+（1+2）+（1+2+3）+…+（1+2+…+n）=n(n+1)(n+2)/6 ， O(n3)

11.下面程序段中带下划线的语句的执行次数的数量级是_____________。

i=1; while(i<n) i=i*2;

【答案】log2n

12. 计算机执行下面的语句时，语句s的执行次数为_____________。

for(i=l;i<n-l;i++)

for(j=n;j>=i;j--) s;

【答案】(n+3)(n-2)/2

13. 下面程序段的时间复杂度为_____________。(n>1)

sum=1;

for (i=0;sum<n;i++) sum+=1;

【答案】O(n)

第2章 线性表

2.1 选择题

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

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

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

【答案】A

2．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（ ）(1≤i≤n+1)。

A） O(0) B） O(1) C） O(n) D） O(n2)

【答案】C

3．双向链表中有两个指针域，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

4．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）

A）O(nlog2n） B） O(1） C） O(n） D） O(n2）

【答案】C

5． 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（ ）

A）p->next==NULL B） p->next==h

C）p->next->next==h D） p->data==-1

【答案】B

6．对于一个具有n个结点的线性表，建立其单链表的时间复杂度是（ ）

A）O(n) B） O(1) C）O(nlog2n) D） O(n2)

【答案】A

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

A）p->prior->next=p->next p->next->prior=p->prior;

B）p->prior=p->prior->prior p->prior->next=p;

C）p->next->prior=p p->next=p->next->next

D）p->next=p->prior->prior p->prior=p->next->next;

【答案】A

9．线性表采用链式存储时，其元素地址（ ）

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

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

【答案】D

2.2 填空题

1．线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素