数据结构复习题及答案

数据结构复习题及答案

数据结构练习题 习题1 绪论

1.1 单项选择题

1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的② A 以及一组相关的运算等的课程。

① A．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①限集合，R是D上的② D 有限集合。

① A．算法 Ｂ．数据元素 Ｃ．数据操作 Ｄ．数据对象 ② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。

A．动态结构和静态结构 Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构 Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②

① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系

C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性

C. 可读性和文档性 D. 数据复杂性和程序复杂性

5. 计算机算法指的是①，它必具备输入、输出和② ① A. 计算方法 B. 排序方法

C. 解决问题的有限运算序列 D. 调度方法

② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性

1.2 填空题（将正确的答案填在相应的空中）

1. 数据逻辑结构包括线性结构、树形结构和图形结构三种类型，树形结构和图形结构合称为非线性结构。

2. 在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。

3. 个直接前驱结点，叶子结点没有后续结点，其余每个结点的直接后续结点可以任意多个。

4.

5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

6.

7. 分析下面算法（程序段），给出最大语句频度2，该算法的时间复杂度是O (n2

for (i=0;i<n;i++) for (j=0;j<n; j++) A[i][j]=0; 8. 分析下面算法（程序段），给出最大语句频度该算法的时间复杂度是2。

for (i=0;i<n;i++) for (j=0; j<i; j++)

A[i][j]=0;

数据结构复习题及答案

9. 分析下面算法（程序段），给出最大语句频度3，该算法的时间复杂度是_ O (n3。

s=0;

for (i=0;i<n;i++) for (j=0;j<n;j++)

for (k=0;k<n;k++) s=s+B[i][j][k];

sum=s; 110. 分析下面算法（程序段）给出最大语句频度，该算法的时间复杂度是O (n)。 i=s=0; while (s<n) { i++;

s+=i; //s=s+i }

11. 分析下面算法（程序段）给出最大语句频度该算法的时间复杂度是

i=1;

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

习题2 线性表 2.1 单项选择题

1. 一个数组（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__B __。

A. 110 B. 108 C. 100 D. 120

2. 线性表的顺序存储结构是一种的存储结构，而链式存储结构是一种的存储结构。

A．随机存取 B．索引存取 C．顺序存取 D．散列存取 3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法。

A. 正确 B. 不正确

4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_。

A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 5. 在以下的叙述中，正确的是_。

A. 线性表的顺序存储结构优于链表存储结构

B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构

6. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法_。

A. 正确 B. 不正确

7. 不带头结点的单链表head为空的判定条件是__A__。

A. head= =NULL B. head.next= =NULL C. head.next= =head D. head!=NULL 8. 带头结点的单链表head为空的判定条件是__B__。

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

9. 非空的循环单链表head的尾结点（由p所指向）满足_C___。

A. p.next= =NULL B. p= =NULL C. p.next= =head D. p= =head

10. 在双向循环链表的p所指结点之后插入s所指结点的操作是_D___。

A. p.right=s; s.left=p; p.right.left=s; s.right=p.right; B. p.right=s; p.right.left=s; s.left=p; s.right=p.right; C. s.left=p; s.right=p.right; p.right=s; p.right.left=s;

2

数据结构复习题及答案

D. s.left=p; s.right=p.right; p.right.left=s; p.right=s;

11. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行__B__。

A. s.next=p.next; p.next=s; B. p.next=s.next; s.next=p; B. q.next=s; s.next=p; C. p.next=s; s.next=q;

12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_B___。

A. s.next=p; p.next=s; B. s.next=p.next; p.next=s; C. s.next=p.next; p=s; C. p.next=s; s.next=p;

13. 在一个单链表中，若删除p所指结点的后续结点，则执行___A_。

A. p.next= p.next.next； B. p= p.next; p.next= p.next.next； C. p.next= p.next; D. p= p.next.next；

14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_D___个结点。

A. n B. n/2 C. (n-1)/2 D. (n+1)/2

15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 。

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

16. 给定有n个元素的数组，建立一个有序单链表的时间复杂度是。

A. O(1)） B. O(n) C. O (n2) D. O (n*log2n)

1. 线性结表 2. 前驱结点、后继结点 3. s, p 4. q.next, q 5. p.next, s 6. O (1) , O (n)

2.2 填空题（将正确的答案填在相应的空中）

1.

2. 3. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作：

q=head;

while (q.next!=p) q=q.next;

s= new Node; s.data=e;

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

q= p.next;

delete ;

5. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行< …… 此处隐藏：2985字，全部文档内容请下载后查看。喜欢就下载吧 ……