数据结构实验考试题

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，共计30分）

1. 数据结构是指 。 A. 一种数据类型 B. 数据的存储结构

C. 一组性质相同的数据元素的集合

D. 相互之间存在一种或多种特定关系的数据元素的集合 2. 以下算法的时间复杂度为 。

void fun(int n) { }

int i=1; while (i<=n)

i++;

A. O(n) B. O(n)

C. O(nlog2n) D. O(log2n)

3. 在一个长度为n的有序顺序表中删除元素值为x的元素时，在查找元素x时采用二分查找，此时的时间复杂度为 。

A. O(n) C. O(n2)

B. O(nlog2n) D. O(n)

4. 在一个带头结点的循环单链表L中，删除元素值为x的结点，算法的时间复杂度为 。

A. O(n)

B. O(n)

C. O(nlog2n) D. O(n2) 5. 若一个栈采用数组s[0..n-1]存放其元素，初始时栈顶指针为n，则以下元素x进栈的正确操作是 。

A.top++;s

要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。

一、单项选择题（每小题1.5分，20小题，共计30分）

1. 以下数据结构中 属非线性结构。 A.栈 B.串 2. 以下算法的时间复杂度为 。

void func(int n) { int i=0,s=0; while (s<=n) { i++; s=s+i; } }

C.队列 D.平衡二叉树

A. O(n)

B. O(n) D. O(log2n)

C. O(nlog2n)

3. 在一个双链表中，删除p所指节点（非首、尾节点）的操作是 。 A.p->prior->next=p->next;p->next->prior=p->prior; B.p->prior=p->prior->prior;p->prior->prior=p; C.p->next->prior=p;p->next=p->next->next;

D.p->next=p->prior->prior;p->prior=p->prior->prior;

4. 设n个元素进栈序列是1、2、3、…、n，其输出序列是p1、p2、…、pn，若p1=3，则p2的值为 。

A.一定是2

第一部分 选择题(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

第一部分 选择题(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

数据结构习题集含答案

目录

目录 ............................................................................................................................. 1 选择题 ......................................................................................................................... 2

第一章绪论 ................................................................................................................................................. 2 第二章 线性表 ..............................................................................................

数据结构试题一

一、单项选择题（每小题3分，共30分）

1、在有n 个叶子结点的哈夫曼树中，其结点总数为（ ）。 A、不确定 B、2n C、2n+1 D、2n-1 2、下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类 型是字符串）。

A、[da，ax，eb，de，bb]ff[ha，gc] B、[cd，eb，ax，da]ff[ha，gc，bb] C、[gc，ax，eb，cd，bb]ff[da，ha] D、[ax，bb，cd，da]ff[eb，gc，ha]

3、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ ） 存储方式节省时间。

A、单链表 B、双链表 C、单循环链表 D、顺序表 4、下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlogn)的是 （ ）。 A、堆排序 B、冒泡排序 C、直接选择排序 D、快序排序

5、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的 二叉树。

A、空

第七章 图

一、选择题

1．图中有关路径的定义是（ ）。【北方交通大学 2001 一、24 （2分）】

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 2．设无向图的顶点个数为n，则该图最多有（ ）条边。

2

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n 【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】 【北京航空航天大学 1999 一、7 （2分）】

3．一个n个顶点的连通无向图，其边的个数至少为（ ）。【浙江大学 1999 四、4 (4分)】

A．n-1 B．n C．n+1 D．nlogn； 4．要连通具有n个顶点的有向图，至少需要（ ）条边。【北京航空航天大学 2000 一、6(2分）】

A．n-l B．n C．n+l

实验一

实验题目：运动会成绩统计 实验目的：

（1）掌握结构体类型数组的概念和使用； （2）掌握枚举类型的概念与使用；

（3）设计并掌握算法，学会分析算法并培养用算法解决实际问题的能力。 实验要求：

（1）设计相应原始表格（比赛的成绩），选择恰当的数据结构； （2）统计各院校的男、女总分和团体总分，并输出。

实验重点：针对具体的应用问题选择适当的数据结构，设计出高效算法，编写出正确的程序，得到正解的实验结果。

实验难点：（1）针对具体的应用问题选择适当的数据结构，设计出高效算法，编写出正确的程序，并对算法进行性能分析；

（2）程序的编译与调试。 实验内容：

假设有A、B、C、D、E五个高校进行田径比赛，各院校的单项成绩均已存入计算机，并构成一张表，表的每一行的形式为：项目名称 性别 校名 成绩 得分

编程统计各院校的男、女总分和团体总分，并输出。 实验原理与步骤： （1）数据结构 #define NULL 0 typedef struct{

char *sport;

enum{male,female} gender;

实验4查找

一、实验目的或任务

通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

1.了解实验目的及实验原理；

2.编写程序，并附上程序代码和结果图；

3.总结在编程过程中遇到的问题、解决办法和收获。

三、实验教学的内容或要求

1.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)

2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树

3.编写函数,在以上二叉排序树中删除某一指定关键字元素

4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

四、实验类型或性质

验证性

五、实验开出要求

必做

六、实验所需仪器设备

1.计算机

2.相关软件（如C,C++,PASCAL,VC,DELPHI等等）

七、实验所用材料

计算机耗材

一、程序运行界面：

二、源程序

#define _CRT_SECURE_NO_W ARNINGS

#include<stdio.h>

#include<malloc.h>

#define MAXNODE 256

typedefstruct Node

{

int data;

str

《数据结构A》实验大纲

课程编码： 07040021

课程英文名： Data Structure A

适用专业： 计算机科学与技术本科、网络工程本科、计算机科学与技术（师范）本科 实验学时： 16学时 学 分： 0.5学分

一、实验课程的性质、目的和任务

数据结构是计算机专业的一门核心课程，是计算机及相关专业的重要的基础理论课程。该课程既有较强的理论，又要联系实际。通过《数据结构》实验的开设，使学生学会分析数据的特性，给出数据结构的描述，写出相应的算法，培养和训练学生编写复杂程序的能力，使学生的编程能力有一个质的提高。

二、实验环境

1、硬件：计算机 2、软件：vc6.0

三、实验内容：

实验1抽象数据类型的实现实验

（一）实验目的要求

1. 了解结构体和抽象数据类型（ADT）的基本概念，及描述方法。

2. 通过对复数抽象数据类型ADT的实现，熟悉VC环境（掌握结构体类型），为以后章节的学习打下基础。

（二）实验学时：2 学时 （三）实验类型：验证 （四）实验内容

1．复数抽象数据类型ADT的描述及实现。 [复数ADT的描述] ADT complex{

数据对象：D={ c1,c2