数据结构试题集(包含答案 完整版).doc

数据结构试题集(包含答案_完整版)一、选择题1、研究数据结构就是研究(D)。 、存储结构及其基本操作2、算法分析的两个主要方面是(A)。 、具有线性结构的数据结构是(D)。 、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、(B)等5个特性。、可移植性和可扩充性 、有穷性和确定性 、有穷性和稳定性 、稳定性和确定性5、下面程序段的时间复杂度是(C)。 for(i=0;i<m;i++) for(j=0;j<n;j++) a[i][j]=i*j; (m2) (n2) (m*n) (m+n)6、算法是(D)。 、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示(C)。(n) (nlog2n) (n2) (log2n)8、下面程序段的时间复杂度为(C)。 i=1; while(i<=n) i=i*3;(n) (3n) (log3n) (n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的(B)和运算等的学科。 、下面程序段的时间复杂度是(A)。 i=s=0; while(s<n){ i++;s+=i;根号(n) }(n) (n2) (log2n) (n3)11、抽象数据类型的三个组成部分分别为(A)。、数据关系和基本操作 、逻辑结构和存储结构 、数据元素和数据类型 、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 ,以便调试、修改和扩充 ,算法能适当地做出反应或进行处理,不会产生不需要的运行结果 、下列程序段的时间复杂度为(B)。 x=n;y=0; while(x>=(y+1)*(y+1)) y=y+1; (n) B. C. O(1) (n2)二、填空题1、程序段“i=1;while(i<=n)i=i*2;”的时间复杂度为。2、数据结构的四种基本类型中,树形结构的元素是一对多关系。三、综合题1、将数量级O(1),O(N),O(N2),O(N3),O(NLOG2N),O(LOG2N),O(2N)按增长率由小到大排序。答案:O(1)O(log2N)O(N)O(Nlog2N)O(N2)O(N3)O(2N)第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度()。(log2n) (1) (n) (n2)2、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用()存储方式最节省时间。 、具有线性结构的数据结构是()。 、在一个长度为n的顺序表中,在第i个元素之前插入一个新元素时,需向后移动()个元素。-i -i+1 -i-1 、非空的循环单链表head的尾结点p满足()。->next==head ->next==NULL ==NULL ==head6、链表不具有的特点是()。 、在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,修改指针的操作是()。 ->next=q;q->prior=p;p->next->prior=q;q->next=q; ->next=q;p->next->prior=q;q->prior=p;q->next=p->next; ->prior=p;q->next=p->next;p->next->prior=q;p->next=q; ->next=p->next;q->prior=p;p->next=q;p->next=q;8、线性表采用链式存储时,结点的存储地址()。 、在一个长度为n的顺序表中删除第i个