太原理工大学数据结构试题库及答案.doc

数据结构试题库及答案第一章概论一、选择题1、研究数据结构就是研究(D)。 、存储结构及其基本操作2、算法分析的两个主要方面是(A)。 、具有线性结构的数据结构是(D)。 、算法是(D)。 、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示(C)。(n) (nlog2n) (n2) (log2n)11、抽象数据类型的三个组成部分分别为(A)。、数据关系和基本操作 、逻辑结构和存储结构 、数据元素和数据类型 、数据结构和数据类型二、填空题三、综合题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)一、(D,R),其中D是数据元素的有限集合,R是D上的关系有限集合。、数据的存储结构和数据的运算这三个方面的内容。,它们分别是线性结构和非线性结构。,它们分别是顺序、链式、索引、散列。,它们分别是插入、删除、修改、查找、排序。二、单项选择题(C),与所使用的计算机无关的是数据的结构;A)存储B)物理C)逻辑D)物理和存储三、?答:简单地说,数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素,而且还在其上定义了一组操作。。答:线性结构反映结点间的逻辑关系是一对一的,非线性结构反映结点间的逻辑关系是多对多的。四、=0;for(i=0;i<n;i++)for(j=0;j<n;j++)s+=B[i][j];sum=s;(i=0;i<n;i++)for(j=0;j<m;j++)A[i][j]=0;=0;for(i=1;i<n;i++)for(j=1;j<=n-i;j++)x++;=1;while(i<=n)i=i*3;Mnnnnnlog3n五、设有数据逻辑结构S=(D,R),试按各小题所给条件画出这些逻辑结构的图示,并确定其是哪种逻辑结构。={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}={d1,d2,…,d9}R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}第二章线性表一、选择题1、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素算法的时间复杂度()。(log2n) (1) (n) (n2)2、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用()存储方式最节省时间。 、在双向循环链表中,在p指针所指的结点后插入一个指针q所指向的新结点,修改指针的操作是(c)。 ->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;10、线性表是n个()的有限序列。 11、从表中任一结点出发,都能扫描整个表的是()。 、在具有n个结点的单链表上查找值为x的元素时,其时间复杂度为()。(n) (1) (n2) (n-1)15、在线性表的下列存储结