数据结构实验题目[1]

“数据结构”课程设计-指导书 2011-6-2

选题一：迷宫与栈问题

【问题描述】

以一个mXn的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

【任务要求】

1) 首先实现一个以链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，d）的形式输出。其中：（i，j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如，对于下列数据的迷宫，输出一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。

2) 编写递归形式的算法，求得迷宫中所有可能的通路。

3) 以方阵形式输出迷宫及其通路。

【测试数据】

迷宫的测试数据如下：左上角（0，1）为入口，右下角（8，9）为出口。

87654321001234567899入口出口008765432101111111110100000001011010001201001011130101100014000001001501100100160100001117000000001811111111911111111119入口出口 “数据结构”课程设计-指导书 2011-6-2

选题二：算术表达式与二叉树

【问题描述】

一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式的操作。

【任务要求】

假设算术表达式Expression内可以含有变量（a～z）、常量（0～9）和二元运算符（+，-，*，/，^(乘幂)）。实现以下操作：

1) ReadExpre(E)—以字符序列的形式输入语法正确的前缀表达式并构造表达式E。

百度文库 - 让每个人平等地提升自我

1 数据结构多项式相加实验报告

篇一：数据结构实验多项式加法

数据结构实验报告

实验名称：多项式加减法

学号：1XX10419

姓名：林强

实验日期：XX.5.05

一、实验目的

通过实现多项式的加减法，对链表有更深入的了解

二、实验具体内容

1、实验题目1：

（1）题目设计一个一元稀疏多项式简单的加减法计算器

实

现要求：

一元稀疏多项式简单计算器的基本功能是：

（1）输入并建立多项式：

A(x)?7?3x?9x8?5x17；

B(x)?8x?22x7?9x8

（2）输出多项式

（3）多项式A和B相加，建立多项式C＝A＋B，并输出相加的结果多项式C 百度文库 - 让每个人平等地提升自我

2 （4）选作：多项式A和B相减，建立多项式C＝A－B，并输出相加的结果多项式D

（2）分析

1：本程序的任务是实现两个多项式的加法其中多项式的系数为浮点型，

指数为整数，输出的结果也为系数和指数。

（1）输入的形式和输入值的范围：

输入多项式的系数a和未知数X的指数b，当a和b都为零时，输入结束。输入值的范围：a为实数，b为整数。

（2）输出形式：输出多项式的系数和多项式未知数X的指数即(a,b)形式。

（3）程序所能达到的功能，实现两个多项式的加法，并输出最后的结果

2：

整个程序运行期间实行动态创建节点，一边输入数据，

一边创建节点当将全部数据输入到单链表中后再调用多项式加法这

个函数，并一边实现多项式的相加，一边释放节点，有效防止了

在程序反复运行过程中可能出现系统空间不够分配的现象

（3）实验代码 百度文库 - 让每个人平等地提升自我

3 typedef int Status;

#define OVERFLOW -1

数据结构-1

(总分100,考试时间90分钟)

一、单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的

1. 设数组data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为( )

A. front:=front+1

B. front:=(front+1)mod m

C. rear:=(rear+1)mod m

D. front:=(front+1)mod(m+1)

2. 在Hash函数H(k)=k MOD m中，一般来讲，m应取( )

A. 奇数 B. 偶数

C. 素数 D. 充分大的数

3. 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。

A. 二叉链表 B. 广义表

C. 三叉链表 D. 顺序

4. 向一个栈顶指针为Top的链栈中插入一个s所指结点时，其操作步骤为( )

A. Top—＞next=s;

B. s—＞next=Top—＞next;Top—＞next=s;

C. s—＞next=Top;top=s;

D. s—＞next=Top; Top=Top—＞next;

5. 快速排序在最坏情况下的时间复杂度是( )

A. O(nlog

B. O(n2)

C. O(n3)

D. 都不对

6. 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。

A. 归并排序 B. 插入排序

C. 快速排序 D. 选择排序

7. 对于一个具有N个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )

A. (N-1)×(N-1) B. N×N

C. (N+1)×(N+1) D. 不确定

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

数据结构课程设计题目

以下7个题目任选其一。

1．排序算法比较

利用随机函数产生30000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并且

（1）统计每一种排序上机所花费的时间。

（2）统计在完全正序，完全逆序情况下记录的比较次数和移动次数。

（3）比较的指标为关键字的比较次数和记录的移动次数(一次记录交换计为3次移动)。

（4）对结果作简单分析，包括对各组数据得出结果波动大小的解释。

2．图的深度遍历

对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索遍历。画出搜索顺序示意图。

3．图的广度遍历

对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索遍历。画出搜索顺序示意图。

4．二叉树的遍历

对任意给定的二叉树（顶点数自定）建立它的二叉链表存贮结构，并利用栈的五种基本运算（置空栈、进栈、出栈、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种遍历，输出三种遍历的结果。画出搜索顺序示意图。

5．链表操作

利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。画出搜索顺序示意图。

6．一元稀疏多项式简单计数器

（1）输入并建立多项式

（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2……cn，en，其中n是多项式的项数，ci，ei分别为第i项的系数和指数。序列按指数降序排列。（3）多项式a和b相加，建立多项式a+b，输出相加的多项式。

（4）多项式a和b相减，建立多项式a-b，输出相减的多项式。

用带头结点的单链表存储多项式。