文档介绍：第1章绪论
选择题
1. 算法的时间复杂度取决于( c )
A)问题的规模 B) 待处理数据的初态 C) A和B
,它必须具备( B ) 这三个特性。
A)可执行性、可移植性、可扩充性B) 可执行性、确定性、有穷性C) 确定性、有穷性、稳定性D) 易读性、稳定性、安全性
( C )两大类。
A)动态结构、静态结构 B)顺序结构、链式结构 C)线性结构、非线性结构 D)初等结构、构造型结构
,对x的赋值的语句频度为( C )
for(i=0;i<n;i++)
for(j=0;j<n;j++) x=x+1;
A) O(2n) B)O(n) (n2) (log2n)
, n为正整数,则最后一行的语句频度在最坏情况下是( D )
for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
if (A[j]>A[j+1])
A[j]与A[j+1]对换;
A. O(n) B) O(nlog2n) C) O(n3) D) O(n2)
填空题
2. 对于给定的n个元素,可以构造出的逻辑结构有集合、线性结构、树形结构、图状结构或网状结构四种。
:算法的时间复杂度和空间复杂度。
5. 数据结构是研讨数据的__逻辑结构_和_物理结构_以及它们之间的相互关系,并对与这种结构定义相应的_操作(运算)_设计出相应的_算法_。
:有穷性_、确定性、可行性,有零个或多个输入、有一个或多个输出。
 
for(i=n;i>0;i--) {语句1}
{ x=x+1; {语句2}
for(j=n;j>=i;j--) {语句3}
y=y+1; {语句4}
}
语句1执行的频度为_n+1_;语句2执行的频度为_n__;语句3执行的频度为_n(n+3)/2_;语句4执行的频度为_n(n+1)/2_。
,对x的赋值语句的频度为_____________(表示为n的函数)
for(i=0;i>n;i++)
for(j=0;j>i;j++)
for(k=0;k>j;k++)
x=x+delta;【答案】1+(1+2)+(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6 , O(n3)
。
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章线性表
选择题
,则选择( A )最节省时间
A)顺序表 B)带头结点的双循环链表 C)单链表 D)带尾结点的单循环链表
2 .若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法时间复杂度为( C )(1≤i≤n+1)。
A) O(0) B) O(1) C) O(n) D) O(n2)
,prior和next,分别指向前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为(D )
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;
(C )
A)O(nlog2n) B) O(1) C) O(n) D) O(n2)
5. 在一个以 h 为头指针的单循环链中,p 指针指向链尾结点的条件是( B )
A)p->next==NULL