1．链表结点类和链表类定义：

template struct Node { T data;

Node *next; //此处也可以省略 };

template class LinkList { public:

LinkList( ); //建立只有头结点的空链表

LinkList(T a[ ], int n); //建立有n个元素的单链表 ~LinkList(); //析构函数

void Insert(int i, T x); //在单链表中第i个位置插入元素值为x的结点 T Delete(int i); //在单链表中删除第i个结点

void PrintList( ); //遍历单链表，按序号依次输出各元素 private: Node *first; //单链表的头指针 };

2． 二叉树类基本定义: template

struct BiNode //二叉树的结点结构 { T data;

BiNode *lchild, *rchild; };

template class BiTree {public:

BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode* Getroot(); //获得指向根结点的指针

void PreOrder(BiNode *root); //前序遍历二叉树 void InOrder(BiNode *root); //中序遍历二叉树 void PostOrder(BiNode *root); //后序遍历二叉树 void LeverOrder(BiNode *root); //层序遍历二叉树 private:

BiNode *root; //指向根结点的头指针 BiNode *Creat( ); //有参构造函数调用

void Release(BiNode *root); //析构函数调用 };

3．图的邻接表类定义：

const int MaxSize=12;

struct ArcNode //定义边表结点 { int adjvex; //邻接点域

ArcNode *next; //指向下一个边结点的指针 };

template

struct VertexNode //定义顶点表结点 { T vertex; //顶点的名称 ArcNode *firstedge; //边表的头指针 };

template class ALGraph {public:

ALGraph(T a[ ],int n,int e);//构造函数，初始化一个有n个顶点e条边的图 ~ALGraph(); //析构函数，释放邻接表中各边表结点的存储空间 T GetVex(int i); //取图中第i个顶点数据信息 void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private:

VertexNode adjlist[MaxSize]; //存放顶点表的数组 int vertexNum, arcNum; //图的顶点数和边数 };

练习题： 一、填空题

1、______是数据的最小单位，_________是讨论数据结构时涉及的最小数据单位。 2、设一棵完全二叉树具有50个结点，则此完全二叉树有 个度为2的结点。 3、在用于表示有向图的邻接矩阵中，对第i列的元素进行累加，可得到第i个顶点的______度。

4、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有____________ 个叶子的结点。 5、有一个长度为20的有序表采用二分查找方法进行查找，共有＿＿＿＿＿＿个元素的查找长度为3。

6、对于双向链表，在两个结点之间插入一个新结点需要修改的指针共______个。 删除一个结点需要修改的指针共__________个。

7、已知广义表LS=(a,(b,c,d),e)，它的深度是__________，长度是__________。 8、循环队列的引入是为了克服__________。

9、表达式a*(b+c)-d/f的后缀表达式是________________。

10、数据结构中评价算法的两个重要指标是 。

11、设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是___________；r=s; r->next=null;。

12、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为a，b，c，d，e，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

13、模式串P=‘abaabcac’的next函数值序列为________。 14、任意连通图的连通分量只有一个，即是 。 15、栈的特性是 。 16、串的长度是 。

17、如果一个有向图中没有＿＿＿＿＿＿，则该图的全部顶点可能排成一个拓扑序列。 18、在具有n个叶子结点的哈夫曼树中，分支结点总数为 。

19、在线性表的散列存储中，装填因子?又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则?等于________。

20、排序的主要目的是为了以后对已排序的数据元素进行 。

21、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。

22、线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 23、两个栈共享空间时栈满的条件_______。

24、深度为H 的完全二叉树至少有_ __个结点；至多有_ __个结点；H和结点总数N之间的关系是 __。

25、在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________。

26、数据结构被形式地定义为（D,R），其中D和R 的含义是（ ）。数据的逻辑结构包

括哪四种类型（ ）。从存储结构的概念上讲，顺序表是线性表的（ ），链表是（ ）。

27、算法的五个重要特性有哪些。（ ）。抽象数据类型是指一个（ ）以及定义在该

模型上的（ ）。 28、在含有n个结点的顺序存储的线性表中，在任意一个结点前插入一个结点所需要移动结点的平均次数为（ ）。在含有n个结点的顺序存储的线性表中，任意删除一个结点所需要移动结点的平均次数为（ ）。对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（ ）。

29、线性结构中的一个结点代表一个（ ）。若线性表中最常用的操作是取第i个元素和

查找该元素的前驱，则采用的存储方式最能节省时间的是（ ）。若最常用的操作是插入和删除第i个元素，则采用的存储方式最能节省时间的是（ ）。 30、在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除操作过程不

同，需要修改（ ）。在单链表中设置头结点的作用是（ ），无论链表是否为空，使（ ）均不为空。

31、如果以链栈为存储结构，则出栈操作时( )，与顺序栈相比，链栈有一个明显

的优势是( )。 32、循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾

指针。为区分队列的满和空，约定：队中能够存放的元素个数最大为n-l，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（ ） ；入队时，可用语句（ ）求出新元素在数组data中的下标。 33、已知栈的输入序列为1，2，3?．，n，输出序列为a1，a2，?，an，a2=n的输出序列

共有（ ）种输出序列。

34、稀疏矩阵一般的压缩存储方法有两种，它们是用（ )。对矩阵压缩存储是为了( )。 35、将下三角矩阵A[l..8，1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址为 （ ）。 二、选择题

1、从逻辑上可以把数据结构分为（ ）两大类。

A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构

2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A. O(0) B. O(1) C. O(n) D. O(n)

3、若已知一个栈的入栈序列是1,2,3,?,n，其输出序列为p1,p2,p3，?，pN,若pN是n，则pi是( )。

A. i B. n-i C. n-i+1 D. 不确定 4、已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。

A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L））））D. head（tail(head（tail（tail（L）））)） 5、下列陈述中正确的是（ ）。

A.二叉树是度为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为2的结点 D.二叉树中最多只有两棵子树，并且有左右之分

6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F 中第一棵树的结点个数是（ ）。

A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 7、．算术表达式a+b*（c+d/e）转为后缀表达式后为（ ）。

A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 8、关键路径是事件结点网络中（ ）。

A．从源点到终点的最长路径 B．从源点到终点的最短路径 C．最长回路 D．最短回路

9、具有12个关键字的有序表，二分查找的平均查找长度（ ）。 A. 2.5 B. 4 C. 3.1 D. 5 10、AVL树是一种平衡的二叉排序树，树中任一结点的（ ）

A.左、右子树的高度均相同 B.左、右子树高度差的绝对值不超过1 C.左子树的高度均大于右子树的高度 D.左子树的高度均小于右子树的高度 11、线性表采用链接存储时，其地址（ ）。

A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.连续与否均可以

12、栈和队列是两种特殊的线性表，只能在它们的（ ）处添加或删除结点。 Ａ．中间点 Ｂ．端点 Ｃ．随机存取点 Ｄ．结点 13、输入序列为ABC，可以变为BAC时，经过的栈操作为（ ）。

A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop 14、下面（ ）不是算法所具有的特性。

Ａ．有穷性 Ｂ．确切性 Ｃ．高效性 Ｄ．可行性 15、下面关于串的的叙述中，（ ）是不正确的？

A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算

D．串既可以采用顺序存储，也可以采用链式存储

16、数组A[6][7]的每个元素占五个字节，将其按行优先次序存储在起始地址为2000的内存单元中，则元素A[3][5]的地址是( )。

A. 2130 B. 2180 C. 2205 D. 2210

17、对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。

22

A．n B．(n-1) C．n-1 D．n 18、若广义表A满足Head(A)=Tail(A)，则A为（ ）。

A．（ ） B．（（）） C．（（），（）） D．（（），（），（）） 19、堆的形状是一棵 ( )。

2