算法与数据结构

《数据结构与算法》二

您的姓名： [填空题] *

_________________________________

一、单选题

1. 深度优先搜索遍历类似于二叉树的（）. [单选题] *

A. 先序遍历(正确答案)

B. 中序遍历

C. 后序遍历

D. 按层次遍历

2. 无向图顶点v的度是关联于该顶点（）的数目. [单选题] *

A. 顶点

B. 边(正确答案)

C. 序号

D. 下标

3. 有n个顶点的无向图的邻接矩阵是用（）数组存储。. [单选题] *

A. 一维

B. n行n列(正确答案)

C. 任意行n列

D. n行任意列

4.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）. [单选题] * A. n-1

B. n+1

C. n(正确答案)

D. n+e

5. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）. [单选题] *

A. k1

B. k2(正确答案)

C. k1-k2

D. k1+k2

6. 广度优先遍历类似于二叉树的（）. [单选题] *

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层次遍历(正确答案)

7. 任何一个无向连通图的最小生成树（）. [单选题] *

A. 只有一棵

B. 有一棵或多棵(正确答案)

C.

一定有多棵

D. 可能不存在

二、多选题

8. 在某图中，下列选项中说法不正确的是（）. *

A. 不存在顶点到自身的边，或者重复的边，则该图是简单图 B. 不存在顶点到自身的边，或者重复的边，则该图是复杂图(正确答案)

C. 不存在顶点到自身的边，或者重复的边，则该图是无向图(正确答案)

D. 不存在顶点到自身的边，或者重复的边，则该图是有向图(正确答案)

9. 有关图的说法不正确的是（）. *

A. 有向图的边是有向的，又称为弧

B. 有向图的边是有向的，又称为箭头(正确答案)

1 [试题分类]：数据结构与算法

1.数据结构可形式地定义为(D, S)，其中S是D上( )的有限集。

A.操作

B.存储映像

C.关系

D.数据元素

答案:C

题型:单选题

知识点:1.2 基本概念和术语

难度:1

2.一般而言，最适合描述算法的语言是( )。

A.自然语言

B.计算机程序语言

C.介于自然语言和程序设计语言之间的伪语言

D.数学公式

答案:C

题型:单选题

知识点:1.4 算法和算法分析

难度:1

3．在下列序列中，不是线性表的是( )。

A. (‘a’, ‘b’)

B. (a, b)

C. (‘AB’, ‘CD’)

D. (‘a’, b)

答案:D 2 题型:单选题

知识点:2.1 线性表的类型定义

难度:2

4.对于顺序表的优缺点，以下说法错误的是( )。

A.插入和删除操作较方便

B.可以方便地随机存取表中的任一结点

C.无需为表示结点间的逻辑关系而增加额外的存储空间

D.由于顺序表要求占用连续的空间，存储分配只能预先进行

题型:单选题

知识点:2.2线性表的顺序表示和实现

难度:2

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

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

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

C. q->next=s;s->next=p;

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

题型:单选题

知识点:2.3线性表的链式表示和实现

难度:2

6.若某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。

A.单链表

B.带头结点的单链表

C.单循环链表 3 D.带头结点的双循环链表

题型:单选题

知识点:2 线性表

难度:3

7.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是( )。

- 欢迎下载

学 生 实 验 报 告 册

（理工类）

课程名称：算法与数据结构 专业班级

学生学号： 学生姓名：

所属院部： 计算机工程学院 指导教师： 章海鸥

2016 ——2017 学年 第 1 学期

金陵科技学院教务处制 -

欢迎下载 实验报告书写要求

实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。

实验报告书写说明

实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。

填写注意事项

（1）细致观察，及时、准确、如实记录。

（2）准确说明，层次清晰。

（3）尽量采用专用术语来说明事物。

（4）外文、符号、公式要准确，应使用统一规定的名词和符号。

（5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。

实验报告批改说明

实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。

实验报告装订要求

实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

-

欢迎下载 实验项目名称： 顺序表 实验学时： 2

同组学生姓名： ╱ 实验地点：

实验日期： 实验成绩：

批改教师： 批改时间： -

第1章 数据结构概论

一、判断题

1 算法可以没有输入语句。

2 数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类，线性的数据结构指数据元素只有一个前驱，非线性的则有多个前驱。

3 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。

二、选择题

1 算法的时间复杂度取决于 。

(A)．问题的规模 (B)．待处理数据的初态

(C)．编码的语言 (D)．占用内存的大小

2 算法与程序的主要区别在于程序可以不满足算法的 B 。

(A)．确定性 (B)．有穷性 (C)．可行性 (D)．健壮性

3. 算法分析的两个方面是 。

(A)．空间复杂性和时间复杂性 (B)．正确性和简明性

(C)．可读性和文档性 (D)．数据复杂性和程序复杂性

三、填空题

1 若算法中语句频度之和为nnnnT2log43720)(，则算法的时间复杂度为 。

2 数据的存储结构分为 、 、 和 四种。

3 在线性结构、树结构和图结构中，前驱和后继结点之间分别存在着 、 和

的关系。

4 算法的计算工作量大小和实现算法所需的存储单元多少，分别称为计算的

和 。

四、应用题

1 计算带下划线语句的执行次数， n为已知的正整数。

(1) x = 91, y = n;

while ( y > 0 )

{ if ( x > 100 ) { x = x-10; y --; }

else x ++;

}

(2) j =0，k = 0;

while ( k < n ) { j ++; k+= 10*j; }

2 一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。