数据结构程序题

数据结构程序填空题

S设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变

量，p指向链表中某结点a（设链表中没有结点的数据域与结点a的数据域相同）, 写出相关语句

答案

（1）q->next=head;（2）p=p->next;（3）q->next=p->next;

设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，

p指向链表中结点a, （设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句

答案：（1）q->next=head (2) p=p->next; （3）q->next=p->next

设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链

表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。

（1）p=p->next;（2）p->data或prep->data（3）p->next

设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链

表中各

福建农林大学计算机与信息学院实验报告

数据结构的程序实现

一、 实验目的和要求

1) 进一步了解数据结构的实现策略。 2) 掌握动态结构的静态实现方法。 3) 了解大批量数据的组织策略。 4) 掌握数据结构在问题建模中的应用。 二、 实验内容和原理 实验内容：

编程实现Josephus问题。 实验原理：

【问题描述】设有n个人围坐一圈并由1~n编号。从某个人（例如编号为k的人）开始报数，数到m的人出列；接着从出列的下一个人开始重新1~m报数，数到m的人又出列；如此反复地报数和出列，知道最后一个人出列为止。试设计确定这n个人出列序列的程序。

【解题思路】有问题描述可以很自然地联想到循环列表，用循环列表对Josephus问题建模，可以做到程序世界和问题世界的完全一致性，符合面向对象的设计思想。考虑到反复报数的过程，可选用不带头结点的单循环链表，以避免报数过程中识别头结点的麻烦。由此，程序中可以先构建一个具有n个结点的单循环链表，然后从约定的结点开始1到m计数，计到m时从链表中删除对应结点；接着从被删除结点的下一个结点起计数，知道最后一个结点从链表中删除后结

束。

三、 实验环境 Windows XP系统 visual c++6.0 四、 实验习

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

几种排序：要求随机输入一组数据 随时给出某一趟排序的变化情况 1.直接插入排序；

2.冒泡排序，快速排序； 3.简单选择排序

程序源代码（已通过编译并运行成功）：

#include #include

//////直接插入排序

void InsertSort(int a[],int n) {

int i,j,k=1;

for(i=2;i<=n;i++) { if(a[i]

a[0]=a[i]; a[i]=a[i-1];

for(j=i-2;a[0]

a[j+1]=a[0];}

printf(\第%d趟结果为:\ for(k=1;k<=n;k++) printf(\ } }

//////冒泡排序

void Bubsort(int a[],int n) { int i,j,flag,temp,k; for (i=n;i>=2;i--) { flag=0;

for (j=1;j<=i-1;j++) if (a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; flag=1; }

if (flag

数据结构

知识:

1.数据结构中对象的定义,存储的表示及操作的实现.

2.线性:线性表、栈、队列、数组、字符串（广义表不考） 树：二叉树

集合：查找，排序 图(不考) 能力：

分析，解决问题的能力 过程：

● 确定问题的数据。 ● 确定数据间的关系。

● 确定存储结构（顺序－数组、链表－指针） ● 确定算法 ● 编程

● 算法评价（时间和空间复杂度，主要考时间复杂度）

一、数组

1、存放于一个连续的空间

2、一维～多维数组的地址计算方式

已知data[0][0]的内存地址，且已知一个元素所占内存空间Ｓ求data[i][j]在内存中的地址。

公式：（add+(i*12+j)*S)(假设此数组为data[10][12])

注意：起始地址不是data[0][0]时候的情况。起始地址为data[-3][8]和情况；

3、顺序表的定义

存储表示及相关操作

4、顺序表操作中时间复杂度估计

5、字符串的定义（字符串就是线性表），存储表示 模式匹配算法（简单和KMP（不考））

6、特殊矩阵：存储方法（压缩存储（按行，按列）） 三对角：存储于一维

第1章绪论

一、选择题

1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】

A．效率 B. 复杂性 C. 现实性 D. 难度

2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】

A．问题的规模 B. 待处理数据的初态 C. A和B

3.计算机算法指的是（1），它必须具备（2）这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A可执行性、可移植性、可扩充性 B.可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性

D.易读性、稳定性、安全性

【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】

4．一个算法应该是（）。【中山大学 1998 二、1（2分）】

A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C.

5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】

A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令

第1章 绪论

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

解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。

1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存

一、判断题 (每题1分,共131分)

1. 线性表的逻辑顺序总是与其物理顺序一致。（ ） 【答案】错

2. 线性表的顺序存储优于链式存储。（ ） 【答案】错

3. 在长度为n的顺序表中，求第i个元素的直接前驱算法的时间复杂度为0（1）。（ ） 【答案】对

4. 若一棵二叉树中的结点均无右孩子，则该二叉树的中根遍历和后根遍历序列正好相反。（ ） 【答案】错

5. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ ） 【答案】对

6. 内部排序是指排序过程在内存中进行的排序。（ ）

【答案】对

7. 当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（ ） 【答案】错

8. 用邻接矩阵存储一个图时，在不考虑压缩存储的情

况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 ( )

14. 当向一个最小堆插入一个具有最小值的元素时，该

元素需要逐层向上调整，直到被调整到堆顶位置为止。( )

【答案】对

15. 哈希查找法中解决冲突问题的常用方法是除留余数法。（ ） 【答案】错

16. 对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。( ) 【答案】错

17. 堆排序是一种稳定的排序

历届竞赛数据结构选择题

单项选择题（共10题，每题1.5分）

[10]7. 前缀表达式“+ 3 * 2 + 5 12 ” 的值是（ ）。 A. 23 B. 25 C. 37 D. 65

[10]9. 完全二叉树的顺序存储方案，是指将完全二叉树的结点从上到下、从左到右依次存放到一个顺序结构的数组中。假定根结点存放在数组的1号位置上，则第k号结点的父结点如果存在的话，应当存放在数组中的（ ）号位置。

A. 2k B. 2k+1 C. k/2下取整 D. (k+1)/2

[09]4. 在字长为16位的系统环境下，一个16位带符号整数的二进制补码为1111111111101101。其对应的十进制整数应该是：( )

A. 19 B. -19 C. 18 D.-18

[09]5. 一个包含n个分支结点(非叶结点)的非空满k叉树，k>=1，它的叶结点数目为：( )

A. nk+1 B. nk-1 C. (k+1)n-1 D. (k-1)n+1 [09]6. 表达式a*(b+c)-d的后缀表达式是：( )

A. abcd*+- B. abc+*d- C. abc*+d

数据结构（c语言版）

课程设计报告

文章编辑程序的设计

学 院： 信息科学技术学院 班 级： 信息工程09级 1 班 学 号： 200941843107 姓 名： 指导教师：

董升 何儒云

完成日期： 2010年12月

目录

1.需求分析——文章编辑.......................................... - 3 - 2.程序设计...................................................... - 3 -

结构体的设计： .............................................. - 3 - 函数的设计： ................................................ - 3 - 主函数的设计： .............................................. - 8 - 3.测试分析.........