数据结构第一章绪论自测题

数据结构第一章课件

西安科技大学精品课程

第一章 绪论主要内容： 数据结构的定义；数据结构研究的范围；研究数据结构采用的方法； 算法描述的工具；算法性能的评价。 教学目的： 使学生掌握数据结构中涉及的基本概念，为以后各章的学习打好基础。 重点： 数据结构的定义；算法描述的工具；算法性能的评价； 难点： 算法性能的评价；

数据结构第一章课件

西安科技大学精品课程

1.1 数据结构的基本概念一、数据结构的概念计算机可以处理： a、数值计算 b、非数值计算数据结构复杂，关系 无法用数学方程描述

用计算机解决一个具体问题的步骤：抽象数学模型 设计算法 编制程序,上机调试 寻求数学模型： 分析问题 提取操作对象 找操作对象之间关系 用数学的 语言描述

数据结构第一章课件

西安科技大学精品课程

二、有关术语简介1. 数据(Data)数据——所有能被输入到计算机中，并能被计算机处理的符号集合。是计 算机操作对象的总称。

数据是信息的载体，是计算机程序加工处理的原料。 2. 数据元素(Data Element)数据元素——是数据的基本单位, 在计算机中通常作为一个整体进行考 虑和处理。 eg:学生信息检索系统 3. 数据项(Data Item) 数据项------具有独立含义

第一章 绪论

一、选择题

1.以下数据结构中哪一个是非线性结构？( )

A. 队列 B. 栈 C. 线性表 D. 二叉树

2．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。 A. 线性结构 B. 树型结构 C. 物理结构 D. 图型结构 3．下面程序的时间复杂为（ ）

for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} A. O(n) B.O(n2) C. O(n3) D. O(n4) 4．数据的最小单位是（ ）。

A.数据项 B. 数据类型 C.数据元素 D. 数据变量

5．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ ）。

23

A. O(n) B. O(nlog2n) C. O(n) D. O(n/2) 6．下列程序段的时间复杂度为（ ）。

for(i=0； i

for(i=0； i

A. O(m*n*t) B. O(m+n+t) C. O(m+n*t) D. O(m*t+n) 7．下列程序段的时间复杂度为（ ）。

i=0，s=0； while (s

A. O(n1/2) B. O(n1/3) C. O(n) D. O(n2

1. AUB 将所有在Lb中但不在La中的数据元素插入到La中 Void Union（ List &La， List Lb） ｛ La_len=ListLength（La）； Lb_len=ListLength（Lb）； For（i=1；i<=Lb_len；i++） ｛

GetElem（Lb，i，&e）;

If（！LocateElem（La，e，equal）） ListInsert（La，++La_len，e）; ｝ ｝

2. La，Lb中的数据元素按值非递减有序排列，现要求将La，Lb归并为一个新的线性表Lc，且Lc的数据元素仍为递减有序排列。 Void MergeList（List La，List Lb，List &Lc） ｛

InitList（Lc）； i=j=1； K=0；

La_len=ListLength（La）； Lb_len=ListLength（Lb）； While（（i<=La_len）&&（j<=Lb_len））｛//La，Lb均为非空 GetElem（La，i，&ai）; GetElem（Lb，j，&bj）;

if（ai<=bj）

｛ ListInsert（Lc，++k，ai）; ++i ； ｝ else

｛ ListInsert（Lc，++k，bj）; ++j ； ｝ ｝

While（i<=La_len）｛ GetElem（La，i++，ai）; While（j<=Lb_len）｛ GetElem（Lb，j++，bj）; ｝

3. 顺序表的存储结构静态描述：

#defin

计算机与信息学院《数据结构》第一、二章自测题

一、选择题

1. 计算机算法必须具备输入、输出和( )等5个特性。

A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性 C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性 2. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。 A．p->next=s;s->next=p->next; B．p->next=s->next;p->next=s; C．p->next=s;p->next=s->next; D．s->next=p->next;p->next=s; 3. 数据结构在计算机内存中的表示是指（ ） A．数据结构

B．数据的逻辑结构 D．数据元素

C．数据的存储结构

4. L是一个带头结点的空单向循环链表，若要向L中插入一个由指针p指向的结点，则执

行（ ）。

A.L=p; p->next=L; B. L->next=p; p->next=L; C. p->next=L; p=L; D.p->

一、概念题（每空0.5分，共28分）

1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2．由３个结点所构成的二叉树有 种形态。

3．一棵深度为6的满二叉树有 个分支结点和 个叶子。 4．一棵具有２５７个结点的完全二叉树，它的深度为 。

5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。 6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。

7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。

8．设一棵完全二叉树有700个结点，则共有 个叶子结点。

9.设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。

10.一棵含有n个结点的k叉树，可能达到的最大深度为 ，最小深度

第一章概论 自测题答案

一、填空题

1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。

2. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。

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

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

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

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

7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。

8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

A) O(n ) B ) O(l) C) O(n) D) O(n)

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).

第一章 线性表 一 单选题

1 线性表是具有n个____的有限序列。 A) 表元素 B) 字符 C) 数据元素 D) 数据项 E)信息项

**2 线性表的静态链表存储结构与顺序存储结构相比优点是_____。 A) 所有的操作算法实现简单 B) 便于随机存储 C) 便于插入和删除 D) 便于利用零散的存储器空间 3 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素算法的时间复杂度为____。

2

A) O(n ) B ) O(l) C) O(n) D) O(n)

**4 (1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关; (2) 静态链表中能容纳元素个数的最大数在定义是就确定了,以后不能增加; (3) 静态链表与动态链表在元素的插入,删除上类似,不需做元素的移动. 以上错误的是_____. A) (1),(2) B) (1) C) (1),(2),(3) D) (2) P 5 将图1.10所示的s所指结点加到p所指结点之后,其语句应为____.

A) s?next=p+1; p?next=s; B) (*p).

《数据结构》第一章练习题

1、单项选择题

1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。

①A数据元素 B计算方法 C逻辑存储 D数据映像 ②A结构 B关系 C运算 D算法

1.2数据结构被形式的定义为（K,R），其中K是（ ）的有限集，R是K上的（ ）有限集。

①A算法B数据元素C数据操作D逻辑结构 ②A操作B映像C存储D关系

1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A动态结构和静态结构 B紧凑结构和非紧凑结构 C线性结构和非线性结构 D内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A数据的存储结构 B数据结构

C数据的逻辑结构 D数据元素之间的关系

1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A逻辑 B存储 C逻辑和存储 D物理

1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。 ①A找出数据结构的合理性 B研究算法中输入与输出的关系 C

自测题（B卷）

（满分100分，时间100分钟）

一、填空题（每题3分，共21分） 1、文字算式游戏：

例如：（十）拿（九）稳一（七）上（八）下=（三）位（一）体

对应的算式为：109–78=31 （1）（ ） 光 （ ）色×不（ ）价=（ ）货公司 （2）（ ）（ ）火 急 ×（ ）指 连 心=（ ）（ ）富翁 （3）（ ）（ ）生 肖 ×（ ）级 跳=（ ）（ ）（ ）计 （4）（ ）（ ）面 威 风 ×（ ）窍生烟=（ ）颜（ ）色 （5）（ ）天 打 鱼 ×（ ）天 晒 网=（ ）亲不认

答案：（1）五、十、二、百；（2）十、万、十、百、万；（3）十、二、三、三、十、六；（4）八、七、五、六；（5）三、两、六． 2、计算19+299+3999+49999= ． 答案：54316

3、按规律填数：1，1，2，3，5， ， ， ． 答案：8，13，21

4、在横线上填上运算符号或括号，使等式成立．

4__4 4__4=1， 4__4__4___4=2，