浙江财经大学数据结构期末考卷

_…__…__…__…__…__…__…__…__…_：…名…姓…… __…__…__…__…__…__…__…_：…号线..学… _…__…__…__…__…__…__ 订.__…__…：…级…班… …__…__装_..__…__…__…__…__…__…__…__…：…业…专… _…__…__…__…__…__…__…：…级…年……诚信应考 考出水平 考出风格

浙江大学城市学院

2013 — 2014 学年第 一 学期期末考试试卷

《 数据结构基础 》

开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 1 月 14 日； 所需时间： 120 分钟 题序 一 二 三 四 五 六 总 分 得分 评卷人 得分 一．选择题 (本大题共 18 题，每题 1 分，共 18 分)

1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D

实 验（实训）报 告

项 目 名 称 各种排序算法时间复杂度测试 所属课程名称 数据结构 项 目 类 型 综合实验 实验(实训)日期 2012年11月21日—30日

班 级 学 号 姓 名 指导教师 万贤美

浙江财经学院教务处制

第7章实验 排序算法时间效率测试

实验类型：综合型

实验目的：

1. 理解排序算法的基本思路； 2. 掌握排序算法的设计与实现；

3. 学会运用相关函数和工具测试算法时间耗费。

实验要求：

1. 认真阅读课本关于各种排序算法的思路，掌握分析排序算法的图示方法；

2. 设计算法测试程序，用六种排序算法分别对随机产生的数据进行排序，记录时间耗费； 3. 对实验结果进行处理与分析。

实验任务： 1、 以学生本人的学号为工程名，建立一个win32 console application工程。 2、 3、 4、

设计直接插入排序、冒泡排序、快速排序、简单选择排序算法，每个算

数 据 结 构 习 题 集

一、选择题

１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动 B 个元素。

A. n-1 B. n-i+1 C. n-i-1 D. i ２.在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。

A. top不变 Ｂ. top＝ -n C. top＝top-1 D. top=top+1 ３.向顺序栈中压入元素时，是 A 。

A. 先存入元素，后移动栈顶指针 B.先移动栈顶指针，后存入元素 ４.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。

A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 ５.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序

“数据结构”期末考试试题

一、单选题(每小题2分，共12分)

1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL；

D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边

C.n(n—1)／2条有向边 D.n(n一1)条有向边

3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)

C.O(1Ogzn) D.O(n2)

4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48

C． 72 D． 53

5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。

A.整形 B.引用型

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

数据结构的基本概念

选择题

（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构

中的数据元素之间的逻辑关系是由（ ）表示的。 A．线性结构 B．非线性结构 C．存储位置 D．指针

（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲

或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A．树 B．图 C．线性表 D．集合

（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。 A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系 C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系

（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。 A．树 B．图 C．线性表 D．集合

（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。 A．数据的处理方法 B．数据元素的类型 C．数据元素之间的关系 D．数据的存储方法

（6） 在链接存储结构中，要求（ ）。

A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储

第一部分 选择题(30分)

一、选择题（20分）

1．组成数据的基本单位是（ ）。 (A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ ）。

(A) 线性结构

(B) 树型结构 (C) 图型结构 (D) 集合

3．数组的逻辑结构不同于下列（ ）的逻辑结构。 (A) 线性表 (B) 栈 (C) 队列 (D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。

(A) 2i (B) 2i (C) 2i-1 (D) 2i-1

5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。

(A) p->next=p->next->next (C) p=p->next->next

(B) p=p->next (D) p->next=p

6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ ）。 (A) 6 (B) 4 (C) 3