交大数据结构

北 京 交 通 大 学 考 试 试 题 （A卷）

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题（每空2分，共20分）

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，

r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50

北 京 交 通 大 学 考 试 试 题 （A卷）

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题（每空2分，共20分）

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，

r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50

《数据结构》实验报告

说明：本软件在win7 64位系统测试通过，需要安装.net 3.5以上

版本

七、数制转换问题

1.问题描述

对于输入的任意一个非负十进制整数，输出与其等值的其他进制数(二进制、八进制或十六进制)。

2.任务要求

⑴ 建立模型，确定存储结构；

⑵ 对任意十进制数，实现进制转换问题。

3.实验指导

(1) 实验类型：

设计实验。本实验要求同学们针对“数制转换”这个经典的问题，应用栈的存储结构，自己设计一个方案，并上机实现。此实验的目的是培养学生对数据结构的简单应用能力。 (2) 预备知识：

栈的基本定义、栈的基本操作算法、栈的存储结构。 (3) 实现方法提示：

1) 以十进制转换为八进制为例。将十进制数整除8，计算过程中得到的余数依次进栈，按出栈序列输出栈中的内容即为与输入的十进制数对应的八进制数。设Conversion函数执行数制转换的操作，对(1348)10 转换为8进制的过程如下：

N 1348 168 21 2

2) 设计数制转换的算法。

N div 8 168 21 2 0

N mod 8 4 0 5 2

4.实现方案

1) 方案描述：

本方案采用Ｃ＃语言实现，实现十进制与其他进制直接的转换 2) 实现代

《数据结构》上机题（C语言程序）

1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。 例如输入：2 6 4 7 3 0（0为结束符），建立：

所求结果=4

程序结构： 类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( )

{ 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止 }

上机题1：

#include #include

typedef int datatype; //设当前数据元素为整型 typedef struct node //节点类型 {

datatype data; //节点的数据域 struct node *next; //节点的后继指针域

}Linknode,*Link;

《数据结构》上机题（C语言程序）

1．输入数据（设为整型）建立单链表，并求相邻两节点data值之和为最大的第一节点。 例如输入：2 6 4 7 3 0（0为结束符），建立：

所求结果=4

程序结构： 类型说明； 建表函数：Creatlist(L); 求值函数：Adjmax(L); main( )

{ 变量说明； 调用Creatlist(L)建表；调用Adjmax(L)求值； 打印数据；释放链表空间； Y 继续？ N 停止 }

上机题1：

#include #include

typedef int datatype; //设当前数据元素为整型 typedef struct node //节点类型 {

datatype data; //节点的数据域 struct node *next; //节点的后继指针域

}Linknode,*Link;

数据结构与算法上机作业

第二章线性表

一、选择题

1、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新的元素算法的时间复杂度为。 A. O(log2n) B. O(1) C. O(n) D. O(n2) 2、以下关于线性表的说法中，不正确的是。 A. 线性表中的数据元素可以是数字、字符、结构等不同类型 B. 线性表中包含的数据元素个数不是任意的 C.线性表中的每一个结点都有且只有一个直接前驱和直接后继（单项链表） D.存在这样的线性表：表中各结点都没有直接前驱和直接后继（数组实现） 3、在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为。 A. O(1) B. O(n) C. O(n2) D. O(log2n)

4、等概率情况下，在有n个结点的顺序表上做插入结点操作，需平均移动的结点数目为 。 A. n B. (n-1)/2 C. n/2 D. (n+1)/2

已经有N个点了,再加一个就是N+1个.假设新加的结点插在第i位,那么后面N+1-i个结点都要往后移动. i的取值服从1到N+1的平均分布,即概率是1/(N+1).

求期望得N/2,即平均要移动N/2个结点期望有计算公式，这里等于

(N+1

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

数据结构（本）期末综合练习

2009年6月

为了帮助同学们进行期末复习，特拟定以下三套期末综合练习题，望同学们逐一认真完成。

数据结构（本）期末综合练习一

一、单项选择题

1．针对线性表，在存储后如果最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。

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

2．线性表采用链式存储时，其地址（ ）。

A．一定是不连续的 B．必须是连续的

C．可以连续也可以不连续 D．部分地址必须是连续的 3．数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A．物理 B．存储 C．逻辑与物理 D．逻辑

4．带头结点的单向链表的头指针为head，该链表为空的判定条件是（ ）的值为真。

A．head = = NULL B．head->next= =head C．head->next= = NULL D．head = =head->next 5．以下特征中，（ ）不是算法的特性。

A．有穷性

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集

数据结构复习201406

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。

难点：分析算法的时间复杂度。 知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。 数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

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

数据的逻辑结构是指数据元素之间逻辑关系的整体。 数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为O(f(n))。