数据结构复习题

一、填空：

1、抽象数据类型的三要素是 ， ， 。 2、队列是 。 3、线索二叉树是 。 4、数据的逻辑结构是 。 5、在大根堆中，关键值最大的元素是 。 6、在记录集{2、5、7、10、14、15、18、20、22}中，进行二分查找，若要查找元素18，共需要比较 次关键字 。

7、分层依次将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么树的深度为 。

8、在一个长度为 n 的顺序表中第 i 个位置插入新元素时，需向后移动元素个数是 。

9、在直接插入排序中使用监视哨的作用是 。 10、在含n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为 。 二、判断题（正确在题后括号内划“√”，错误划“×”）

1、在拓扑排序中，拓扑序列的第一个顶点必定是出度为零的顶点。（ ） 2、算法DFS应用于一个带权连通图时，所经过的边形成一棵最小生成树。（ ） 3、（101，88，46，70，34，39，45，58，66，10）是堆。（ ） 4、n个结点的树的各结点度数之和为n-1。（ ）

5、由二叉树的前序序列和中序序列能唯一确定一棵二叉树。（ ）

6、有向图中一个顶点i的出度等于其邻接矩阵中第i列的非0元素的个数。（ ） 7、哈夫曼树的带权路径长度WPL等于各叶子结点的带权路径长度之和（ ） 8、所谓冲突即是两个关键字的值不同的元素，其散列地址相同。（ ） 9、设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中B[1] 存储矩阵中第一个元素a[1,1], 则B[5] 中存放的元素是a[2,3]。（ ） 10、在串S =\"structure\" 中，以 t 为首字符的子串有 8个。（ ） 三、求解与简答题：

1、以数据集{2，6，13，17，20，30}为叶子结点的权值。（1）构造一棵哈夫曼

树。（2）计算其带权路径长度。

2、从一棵空的二叉排序树开始，将以下关键字值依次插入：28,20，13,15,31,7,23,37，请画出插入全部完成后的二叉排序树。假定每个数据的查询概率相等，试计算查找成功的平均查找长度ASL的值。 3、请比较队列与栈两种数据结构异同点，举例说明其应用场合。

4、对关键字序列( 72, 87, 61, 23, 100, 15, 7, 60 ) 进行堆排序，结果应按关键字递减次序排列（采用小根堆排序）。（1）试以二叉树的形式给出得到初始堆的过程；（2）写出经过二趟排序后关键字序列状态。 5、设有下列无向图：

（1） 请写出图的邻接矩阵与该图的邻接表。

（2） 从V1出发，以邻接矩阵为存储结构，给出其ＤＦＳ序列。 （3） 从V1出发，以邻接表为存储结构，给出其ＢＦＳ序列。

四、算法与编程题：

１、采用顺序存储结构，写出对n个记录进行简单选择排序的算法。

２、假设以数组seq[Maxqsize] 循环存放队列的元素，同时设立队头指针front,队尾指针rear。

（1）用typedef定义出使用的存储结构；（2）给出初始化队列的算法；（3）给出入队的算法；

３、以二叉链表为存储结构，给出分层遍历二叉树的算法（从上至下、从左到右）。

V3 V5 V4 V1 V2 V6 参考答案

一、填空：

1、数据对象、数据关系、数据上的基本操作。

2、先进先出的线性表（FIFO）。插入在表的一端进行，删除在在表的另一端进行。

3、加上线索的二叉树，线索是指向结点的前驱与后续的指针。 4、数据元素之间的逻辑关系。 5、根元素 6、2 7、[log2n]+1 8、n-i+1

9、减少比较次数、提高算法效率。 10、 n2 –2 e 二、判断题

（正确在题后括号内划“√”，错误划“×”） 1、 × 2、× 3、 √ 4、√ 5、√ 6、 × 7、 √ 8、 √ 9、√ 10、× 三、求解与简答题： 1、

88 37 17 20 解：（1）哈夫曼树为：（6分） 51

6 8 2 13 30 21 （2）带权路径长度WPL=(2+6)*4+13*3+(17+20+30)*2=205

2、（10分）

（1）二叉排序树为：（6分）

（2）查找成功的平均查找长度ASL=（4*2+3*3+2*2+1）/8=11/4 3、相同点：都是一种线性表；

不同点：对操作进行了不同限制，队列具有：FIFO特性，栈具有：LIFO特性。（3分）

函数递归调用情况用栈，图的BFS遍历用队列。（） 4、

（1）初始堆为：（）

87 60 23 7 15 7 13 23 20 28 31 37 15 100 72 61 （2）二趟排序后关键字序列状态为：{ 23，60，61，87，100，72，15，7 } （）

5、（15分）

（1）邻接矩阵为：（4分） A=

0 1 1 1 0 0 1 0 0 0 0 1 1 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 邻接表： V1 V2 V3 V4 V5 V6 2 1 1 1 3 2 3 6 5 5 4 4 6 4 V （2）从V1出发，以邻接矩阵为存储结构，给出其ＤＦＳ序列为：V1,V2,V6,V4,V5,V3;

（3）从V1出发，以邻接表为存储结构，给出其ＢＦＳ序列为：

V1,V2,V3,V4,V6,V5;

四、算法与编程题：

1、简单选择排序的算法： Typedef struct {

Keytype key ;

Infotype otherinfo;} Redtype;

Typedef struct {

Redtype r[Maxsize+1] ;

Int length ;} Sqlist;

Void Selectsort(Sqlist & L) {

for (i=1;i<=L.length;++i){ k=i;

for (j=i+1;j<=L.length;++j){ if (L.r[j].key< L.r[k].key) k=j;}

if (k!=i){temp=L.r[i];L.r[i]=L.r[k];L.r[k]=temp;} }

}

2、

（1）用typedef定义出存储结构

#Define Maxqsize 100; Typedef int Qelemtype; Typedef struct { QElemtype *seq; Int front ,rear;} SqQueue;

(2）置空队列的算法 Status InitQueue(SqQueue &Q)

{ Q. seq = (Qelemtype*) mallac(Maxqsize*sizeof(Qelemtype)); if (!Q. seq) exit(errorinfomation); Q.front =Q.rear=0//或Maxqsize-1 Return ok; }

（3）入队的算法

Status EnQueue(SqQueue &Q, Qelemtype e) {

if ((Q.rear+1)% Maxqsize== Q.front) return error; Q. seq [Q.rear]=e;

Q.rear=(Q.rear+1)% Maxqsize; Return ok; } 3、

typedef struct node { Telemtype data; struct node *lchild, *rchild;

} BiTNode, *BiTree; Status Levelorder(BiTree T) { InitQueue(Q); if(!T) RETURN OK; ENQUEUE (Q,T); while (!EMPTY(Q)){ p=DEQUEUE(Q); Printf(p->data);

if (p-> lchild) ENQUEUE (Q, p-> lchild); if (p->rlchild) ENQUEUE (Q, p->rlchild); }

}

复习题二

一、填空：

1、图的最小生成树，是指 。 2、栈是指 。 3、哈希函数是指 。 4、索引文件是指 。 5、算法是指 。 6、分层依次将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么当18、对一棵二叉查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是 。

9、如果入栈序列是1，3，5，„，97，99，且出栈序列的第一个元素为99，则出栈序列中第10个元素为______。

10、在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为 。

二、判断题（正确的在题后括号内划“√”，错误的划“×”）： 1、用邻接矩阵表示图所用的存储空间大小与图的边数成正比。（ ） 2、散列表中产生冲突的可能性大小与负载因子有关。（ ） 3、队列只能采用顺序存储方式。（ ）

4、树转化为对应的二叉树后，两者的边数相等。（ ）

5、由二叉树的先序序列和中序序列能唯一确定一棵二叉树。（ ）

6、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根很较近。（ ） 7、某带头结点的单链表的头指针为head，判定该链表为非空的条件是head==NULL。（ ）

8、将一棵树转换成二叉树后，根结点只有一棵子树。（ ）

9、对n个元素用快速排序方法进行排序，平均时间复杂度是O(n2)。（ ）

10、在含n个顶点的无向连通图中，任意两个不同顶点之间的一条简单路径最多包含n-1条边。（ ） 三、求解与简答题：

1、以数据集{9，2，5，7，13，30}为叶子结点的权值。 （1）构造一棵哈夫曼树。（2）给出叶结点集的哈夫曼编码。

2、设a1, a2, a3 是不同的关键字且a1 < a2 < a3，可组成6种不同的输入顺序。（1）哪几种输入顺序所构成的二叉排序树的高度为3；（2）画出对应的二叉排序树。

3、把记录集（28,13，19,35,15,37，100）用快速排序方法进行排序，详细给出第一趟排序的过程，写出每趟排序完成的记录集状态。 4、简述用哈希表进行存储中处理碰撞（冲突）的两类基本方法 5、设有下列有向图：

V2 V5 V3 V4 V1 （1）请写出图的邻接矩阵与该图的邻接表。（2）从V1出发，以邻接矩阵为存储结构，给出其ＤＦＳ序列。（3）从V1出发，给出其拓扑排序序列。 四、算法与编程题：

1、写出对n个记录进行直接插入排序的算法。

2、假设以数组seq[maxqsize]存放循环队列的元素，同时设立队头指针front,队尾指针rear。

（1）队列满、队列空的条件；（2）写出出队的算法； 3、以二叉链表为存储结构，试给出求二叉树高度的算法。

参考答案

一、填空：

1、连通图中最小代价生成树。

2、先进后出的线性表（LIFO）。插入、删除都在表的一端进行。 3、关键字与存储位置之间的映射函数。 4、包括文件数据区与索引表两部份的文件。

5、求解问题的有限指令序列，具有有穷性等五个重要特征。 6、[i/2],i+1 7、{4,1,3,2,6,5,7} 8、小于关系 9、90。

10、子串最后一个字符。 二、判断题

（正确在题后括号内划“√”，错误划“×”） 1、 × 2、√ 3、 × 4、√ 5、√ 6、 √ 7、 × 8、 √ 9、× 10、√ 三、求解与简答题： 1、（）

66 30 解：（1）哈夫曼树为：（6分） 36

（2）叶结点的哈夫曼编码为

2 5 7 7 14 22 9 13 2：0000； 5：0001； 7：001； 9：010； 13：011； 30：0； 2、（）

（1）输入顺序为：（）

1)a1,a2,a3 ; 2) a1,a3,a2; 3) a3,a2,a1; 4) a3,a1,a2 ; （2）对应的二叉排序树 （4分） a1 a3 a2 a3 a2 a1 a1 a3 a3 a2 a1 a2 1) 2) 3) 4)

3、(10分)

1）[15，13，19 ]，28，[35，37，100] 2）[13]，15 ，[19]，28，35，[37，100] 3）13，15，19，28，35，37，[100] 4）13，15，19，28，35，37，100

4、哈希表进行存储时，当key1 !=key2 时，但f（key1）=f(key2);此时出现冲突。

处理冲突方法有1）开放地址法：允许对其它未存储元素的哈希表的单元进行探查并使用。2）链地址法：将所有同义的关键字的记录存储在同一线性链表中。

5、（15分）

（1）邻接矩阵为：（4分） A=

0 1 1 1 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 邻接表： V1 V2 V3 V4 V5 4 2 5 2 5 3 4 V

（2）从V1出发，以邻接矩阵为存储结构，给出其ＤＦＳ序列为：V1,V2,V5,V4,V3; （3）从V1出发，给出其拓扑排序序列为：V1,V3,V2,V5,V4;

四、算法与编程题：

1、简单选择排序的算法： Typedef struct {

Keytype key ;

Infotype otherinfo;} Redtype;

Typedef struct {

Redtype r[Maxsize+1] ;

Int length ;} Sqlist;

Void Insertsort(Sqlist & L) {

for (i=2;i<=L.length;++i){ if (L.r[i].key< L.r[i-1].key){ L.r[0]=L.r[i];

L.r[i]=L.r[i-1];

for( j=i-2;LT(L.r[0], L.r[j]);--j) L.r[j+1]=L.r[j]; L.r[j+1]=L.r[0]; } }

}

2、

#Define Maxqsize 100; Typedef int Qelemtype; Typedef struct { QElemtype *seq;

Int front ,rear;} SqQueue; (1) 队列满的条件: (Q.rear+1)% Maxqsize== Q.front 队列满的条件：Q.rear == Q.front

（2）出队的算法

Status DeQueue(SqQueue &Q, Qelemtype &e) {

if (Q.rear+1 == Q.front) return error; e = Q. seq [Q.front];

Q.front=(Q.front+1)% Maxqsize; Return ok; }

3、（5分）

typedef struct node { Telemtype data; struct node *lchild, *rchild;

} BiTNode, *BiTree;

Status Heightree(BiTree p) { if(!p) RETURN (0); int h1= Heightree(p-> lchild); int h2= Heightree(p-> rchild); int h=max(h1,h2); return (h);

}