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

数据结构试题库及答案

第一章 概论

一、选择题

1、研究数据结构就是研究（ D）。

A.数据的逻辑结构 B.数据的存储结构

C.数据的逻辑结构和存储结构 D.数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（A）。

A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（D）。

A.图 B.树 C.广义表 D.栈 6、算法是（ D）。

A.计算机程序 B.解决问题的计算方法 C.排序算法 D.解决问题的有限运算序列

7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 11、抽象数据类型的三个组成部分分别为（A ）。

A. 数据对象、数据关系和基本操作 B.数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 二、填空题 三、综合题

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. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。

2. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。

3. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

8．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引、散列。

9. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

二、单项选择题

（C）2. 数据结构中，与所使用的计算机无关的是数据的结构；

A)存储 B)物理 C)逻辑 D)物理和存储

三、简答题

1.数据结构和数据类型两个概念之间有区别吗？

答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

2. 简述线性结构与非线性结构的不同点。

答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。

四、分析下面各程序段的时间复杂度

1. for (i=0; i

3. x=0;

for(i=1; i

for (j=1; j<=n-i; j++)

x++;

Mn nn nn log3n

2. s=0;

for (i=0; i

for(j=0; j

4. i=1;

while(i<=n) i=i*3;

五、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定其是哪种逻辑结构。

1. D={d1,d2,d3,d4} R={(d1,d2),(d2,d3),(d3,d4) }

2． D={d1,d2,?,d9}

R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) }

3．D={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个位置插入一个新元素算法的时间复杂度（）。

A. O(log2n) B.O(1) C. O(n) D.O(n2) 2、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。

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

7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（c）。

A. p->next=q;q->prior=p;p->next->prior=q;q->next=q;

B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next;

C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D. q->next=p->next;q->prior=p;p->next=q;p->next=q; 10、线性表是n个（）的有限序列。

A. 表元素 B. 字符 C. 数据元素 D. 数据项 11、从表中任一结点出发，都能扫描整个表的是（）。

A. 单链表 B.顺序表 C. 循环链表 D.静态链表 12、在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（）。

A. O(n) B. O(1) C. O(n2) D. O(n-1) 15、在线性表的下列存储结构中，读取元素花费的时间最少的是（）。 A. 单链表 B. 双链表 C. 循环链表 D. 顺序表

16、在一个单链表中，若删除p所指向结点的后续结点，则执行（）。

A. p->next=p->next->next;

B. p=p->next;p->next=p->next->next; C. p =p->next;

D. p=p->next->next;

17、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。

A. O(1) B. O(n) C. O(m) D. O(m+n) 18、线性表的顺序存储结构是一种（a）存储结构。N

A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 19、顺序表中，插入一个元素所需移动的元素平均数是（）。 A. (n-1)/2 B. n C. n+1 D. (n+1)/2 11、不带头结点的单链表head为空的判定条件是（ b）。

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL

12、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。

A. 访问第i个元素的前驱（1

C.删除第i个元素(1?i?n) D. 对顺序表中元素进行排序 13、已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ a ）。

A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next； C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next；

15、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（a）。

A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 二、填空题 1、设单链表的结点结构为（data,next）。已知指针p指向单链表中的结点，q指向新结点，欲将q插入到p结点之后，则需要执行的语句：；。 答案：q->next=p->next p->next=q

3、写出带头结点的双向循环链表L为空表的条件。 答案：L->prior==L->next==L

5、在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q= p->next;

p->next=_ q->next ___; 三、判断题

3、用循环单链表表示的链队列中，可以不设队头指针，仅在队尾设置队尾指针。

x

4、顺序存储方式只能用于存储线性结构。? 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素但是在物理位置上不一定是相邻的。?

6、链式存储的线性表可以随机存取。? 四、程序分析填空题

1、函数GetElem实现返回单链表的第i个元素，请在空格处将算法补充完整。 int GetElem(LinkList L,int i,Elemtype *e){

LinkList p；int j； p=L->next;j=1; while(p&&j

p=p->next;++j; }

if(!p||j>i) return ERROR; *e=p->data; return OK; }

2、函数实现单链表的插入算法，请在空格处将算法补充完整。