南京信息工程大学数据结构参考书

滨江学院

数据结构课程设计

题 目 算术表达式的求解

院 系 计算机系 专 业 学生姓名 学 号

指导教师 李燕

二Ｏ一六 年 六 月十日

目 录

1.前言 ......................................................................................................... 1 1.1课题内容及要求 ........................................................................... 1 1.2选题目的及意义 ........................................................................... 1 2.系统分析 .....................................................................................

前 言

《数据结构》是计算机及相关专业的一门核心基础课程，也是很多高校考研专业课之一。它主要介绍线性结构、树结构、图结构三种逻辑结构元素的存储实现，在此基础上介绍一些典型算法及时、空效率分析。这门课程的主要任务是培养学生的算法设计能力及良好的程序设计习惯。通过学习，要求学生能够掌握典型算法的设计思想及程序实现，能够根据实际问题选取合适的存储方案，设计出简洁、高效、实用的算法，为后续课程的学习及软件开发打下良好的基础。学习这门课程，习题和实验是两个关键环节。学生理解算法，上机实验是最佳的途径之一。因此，实验环节的好坏是学生能否学好《数据结构》的关键。为了更好地配合学生实验，特编写实验指导书。 一、实验目的

更好的理解算法的思想、培养编程能力。 二、实验要求

1、每次实验前学生必须根据试验内容认真准备实验程序及调试时所需的输入数据。 2、在指导教师的帮助下能够完成实验内容，得出正确的实验结果。 3、实验结束后总结实验内容、书写实验报告。

4、遵守实验室规章制度、不缺席、按时上、下机。

5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现

象，取消本次上机资格，平时成绩扣10分。

一、单项选择题

1、在以下的叙述中，正确的是( A )。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出

2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。 A. qu->front==qu->rear B. qu->front!=qu->rear C. qu->front=(qu->rear+1)%m0 D. qu->front!=(qu->rear+1)%m0

3、向一个栈顶指针为hs的链栈中插入一个s所指结点时，则执行( C )。 A. hs->next=s;

B. s->next=hs->next;hs->next=s; C. s->next=hs;hs=s; D. s->next=hs;hs=sh->next

4、串是一种特殊的线性表，其特殊性体现在（ B ）。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元

助人教育QQ：707223565

数据结构试题

一、单项选择题

1．数据结构是（ D ）

A．一种数据类型 B．数据的存储结构

C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 2．算法分析的目的是（ B ）

A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性

3．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ） A．插入 C．排序

B．删除 D．定位

4．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ A ） A．1207 C．1211

B．1209 D．1213

5．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ A ） A．不一定相同 C．都不相同

B．都相同 D．互为逆序

6．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C ） A．层次遍历算法 C．中序遍历算法

B．前序遍历算法 D．后序

云南财经大学信息学院

《数据结构》习题及参考答案

《数据结构》课程建设小组

第 1 章 绪 论

基础知识题

1.1 ① 简述下列术语：数据、数据元素、数据对象、存储结构、数据类型、和抽象数据类型。

1.2 ② 试描述数据结构和抽象类型的概念与程序设计语言中数据类型概念的区别。 1.3 ③设有数据结构（D，R），其中

D={d1,d2,d3,d4},R={r},r={(d1,d2),(d2,d3),(d3,d4)}。 试按图论中的画法惯例画出其逻辑结构图。

1.4 ②试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有

理数是其分子，分母均为自然数其分母不零的分数）。 1.5 ②试画出与下列程序段等价的框图 （1） product=1 ; i=1;

while (i<=n){ product * = i;

i++; }

(2) i=0 ;

do { i++

} while ((i !=n )&&(a[i]!=x));

(3) swith {

case x

case x=y : z =abs(x * y);break ; defult : z= (x – y) /abs (x) * abs (y

1. 算法设计：利用顺序存储结构实现PriorElem(L,cur_e,&pre_e)操作。 #define OK 1 #define ERROR 0 typedef int Status;

//---------------------线性表的顺序存储表示----------------------- typedef struct { ElemType *elem; int length; int listsize;

}SqList;

//----------------------算法描述----------------------------------------- Status PriorElem(SqList L,ElemType cur_e,ElemType pre_e) { //若cur_e是顺序表L中的元素，且不是第一个，则用pre_e返回它的前驱，

//否则，操作失败，pre_e无意义。 for(j=1;j<=L.length;j++)

if(L.elem[j-1]==cur_e)

break;

if(j==1||j>L.length) return ERROR;

pre_e=L.elem[j-2]; return

NUIST

校徽

校风校训 校训：明德格物 立己达人 校风：艰苦朴素、勤奋好 学、追求真理、自强不息

南京信息工程大学始建于1960年，原名南京气象学院，1978年 被确定为全国重点大学，2004年更名为南京信息工程大学，是 中国气象局和江苏省人民政府共建的全国重点高校，是江苏省 重点建设大学，教育部本科教学工作水平评估优秀学校，具有 完整的学士、硕士、博士教育培养体系，并设有博士后科研流 动站。学校致力于建成世界著名的气象最高学府，江苏省主管， 江苏省人民政府和中国气象局共建的全国重点高校，江苏省 “十一五”重点建设的15所大学之一。

学校简介

南京信息工程大学坐落在钟灵毓秀、虎踞龙蟠的六朝古都南京，始建 于1960年，前身是有“中国气象人才摇篮”美誉的南京气象学院， 1978年被确定为全国重点大学，2004年更名为南京信息工程大学，是 教育部、中国气象局和江苏省人民政府三方共建的全国重点高校，是 江苏省重点建设大学，是教育部本科教学工作水平评估优秀学校。学 校现有全日制在校生30000余人，其中研究生2000余人，专任教师 1000余人，具有高级职称或博士学位的达70%以上，占地2189亩，校 舍总建筑面积65万平方米。图书馆馆藏纸质文献

习题1

一、单项选择题

1. 数据结构是指（ ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ ）。

for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（1），算法分析的两个主要方面是（2）。

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

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

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1）

信息管理与信息系统专业《数据结构》实验指导

实验一 线性表的插入和删除

一、

实验目的

1、掌握使用Turbo Pascal上机调试线性表的基本方法；

2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。

二、

实验要求

1、认真阅读和掌握本实验的程序。 2、上机运行本程序。

3、保存和打印出程序的运行结果，并结合程序进行分析。

4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果

三、

注意事项：

在磁盘上创建一个目录，专门用于存储数据结构实验的程序。 四、

实验内容

程序1：线性表基本操作的实现

这个程序中演示了顺序表的创建、插入、删除和查找。 程序如下：

PROGRAM seqlist(input,output);

{线性表可能达到的最大长度} CONST

maxlen = 1024;

TYPE

elemtp = integer;

{线性表的顺序存储结构} TYPE

seqlisttp = RECORD

1

{用一维数组来描述线性表的顺序存储结构} elem: ARRAY[1..maxlen] OF elemtp;

{

《数据结构》实验指导书

杨先凤 朱小梅 编

西南石油大学计算机科学学院

二零零七年九月

目 录

写在上机实习之前 ........................................ I 实验一 顺序表的建立和基本运算 ........................... 1 实验二 实验三 实验四 实验五 实验六 实验七 实验八 实验九

链表的建立和基本运算 ............................. 8 栈结构及其应用 .................................. 14 队列应用 ....................................... 17 串的操作及应用 .................................. 18 二叉树的建立和遍历 .............................. 19 图的应用及其算法 ................................ 23 查找 ........................................... 27 内排序 .........