数据结构期末考试复习题

1

第一部分 线性 一.选择题（共10题） 1.以下说法正确的是（）。

A.数据元素是数据的最小单位。B. 数据结构是带结构的各数据项的集合。 C.数据项是数据的基本单位。D. 数据结构是带结构的数据元素的集合。 2. 在设计存储结构时，通常不仅要存储各数据元素的值，而且还要存储（）。 A.数据的处理方法

B.数据元素的类型 D.数据的存储方法

D.一对多

C.数据元素之间的关系 A.一对一

3.树状结构中的数据元素之间存在（）逻辑关系。

B.多对一

C.多对多

4.以下数据结构中，哪一个不属于线性结构（）。 A.串 B.广义表 C.栈 D.树

5.对一个具有n个结点的单链表，在表头位置插入其值等于x的结点时，操作的时间复杂度为（）。 A. O(1)

B. O(x)

C. O(n)

D. O(n2)

6. 设一顺序栈已含3个元素a（栈底）、b、c（栈顶），元素d正等待进栈。那么下列4个序列中不可能出现的出栈序列是（）。

A. dcba B. cdba C. cbda D. cadb 7. 如果栈采用顺序存储结构，则入栈操作时（）。

A. 必须判别栈是否满。 B. 必须判别栈是否空。 C. 判别栈元素的类型。 D. 对栈不做任何操作。

8.用一个大小为N的数组来实现循环队列Q，假定front和rear分别为队头指针和队尾指针，判断该循环队列为满的条件是（）。

A.(Q.rear+1)==Q.front B. Q.front==Q.rear C.(Q.rear+1)%N==Q.front D. (Q.front+1)%N==Q.rear 9.串S=“串string”的长度是（）。

A. 6 B. 7 C. 8 D. 9

10.设二维数组arr[6][4]（行列下标从0开始）的每个元素占6个单元，按行优先顺序存放在起始地址为2000的连续内存单元中，则存储地址为2066的是元素（）。 A. arr[2][3] B. arr[3][3] C. arr[5][1] D. arr[4][1] 二.填空题（共25空）

1.根据数据元素之间关系的不同特性，通常有4类基本数据结构，它们是: (____________)、(___________)、(___________)、(___________)。

2.在数据结构中，(______________)用于完整地描述一个研究对象，是数据的基本单位。 3.计算机中的算法指的是解决某类问题的有限操作序列，它必须具备输入、输出、(____________)、(______________)、(______________)等5个特性。

2

4.顺序表中逻辑上相邻的元素的物理位置(___________)。 5.下面程序段的时间复杂度是(___________)。 int r=1; int i=1; while(i

6.循环单链表H中，指针P所指结点是表尾结点的判断条件是(___________)。

7. 在线性表A,采用单链表存储，已经有数据（b,c,d,e,f,h）中，要删除元素c，此时已经有指针p指向b元素，语句为：q=p->next; (___________); x=q->data;free(q);

要插入元素g，使得此线性表变为（b,c,d,e,f,g,h）,此时已经有指针p指向f元素，插入g的语句为：s->data=‘g’，s->next= (___________); p->next=s;

8. 设有一顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是A、D、F、E、C、B，则栈的容量至少应该是(___________)。

9.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做入栈处理时，top变化为(___________)。

10.设有一空栈，现有输入序列a，b，c，d，e，操作push代表入栈，pop代表出栈，经过push，push，push，pop，push，pop，pop后，栈顶元素为(___________)。

11. 用一个大小为10的数组来实现循环队列，且当前队头和队尾的值分别为2和7，当从队列中删除3个元素，再加入4个元素后，rear的值为(___________)，front的值为(___________)，当前队列的长度为(___________)。

12.若Replace(S,V,T)表示用字符串T替换主串S中的所有子串V的操作，则对于S=“software”，V=“ware”，T=“ly”，Replace（S,V,T）=(___________)。

13.设二维数组A[6][4]（行列下标从0开始）的每个元素占6个单元，将其按列优先顺序存放在起始地址为200的连续内存单元中，则元素a[4][3]的地址为(___________)。

14.广义表(b,(d,a),(c,e)) （其中，a、b、c、d、e是原子）的深度为(___________)，长度为(___________)，表头为(___________)，表尾为(___________)。 三.应用题

1.利用算符优先算法对表达式#(7 – 3)× 5 #求值，写出操作符栈和操作数栈在任意时刻的状态。 2.已知L是带头结点的单链表的头指针，链表结点定义如下： typedef struct LNode { int data; // 数据域 struct LNode *next; // 指针域 } LNode，* LinkList;

请写算法统计并输出单链表L中小于x的数据元素的个数。 void count(LinkList L, int x)

i ++;

3

三、解答：

4

第二部分 树

假设在一棵二叉树中，度为2的结点有10个，度为1的结点有7个，则叶子结点为( )个。

2.在具有7个结点的二叉链表中，空的链域个数为( ) 。

3.已知完全二叉树的第6层有20个叶子结点，则整个二叉树的结点最多有( )个，最少有( )个。

4.有31个结点的完全二叉树深度为( ) ；有( )个叶子，度为1的结点有( )个，度为2的结点有( )个。

5.已知二叉树的先序遍历序列为ACBGFDE，中序遍历序列为BCFGADE ，则这棵二叉树的后序遍历序列为( ) ，该二叉树有个( )叶子，二叉树的深度为( )，对应的森林包括( ) 棵树。

6.如果在树的孩子兄弟链存储结构中有9个空的左指针域，8个空的右指针域，则该树中叶子结点的个数为( ) 个。

7.如果二叉树B是由树T转换而来，那么树T中结点的先根遍历就是二叉树B中结点的( )。树T中结点的后根序列就是二叉树B中结点的( ) 序列。 8.对于一颗具有n个结点，度为4的树来说，树的高度至多是( )。

9.设森林T中有3棵树，第一、二、三棵树的结点个数分别是10、20、30，那么当把森林T转换成一棵二叉树后，该二叉树一共就( )个结点，根结点的左子树上有( )个结点，根结点的右子树上有( )个结点。

10.在有9个叶子结点的哈夫曼树中，其结点总数为( ) 。 11.画出下列顺序存储结构对应的二叉树，并将其转换成对应的森林。

1 A 2 B 3 C 4 D 5 E 6 7 F 8 9 G 10 H 11 12 13 14 15 16 17 18 19 20 I J K 12.已知一棵二叉树的后序遍历序列为HBCGFEDA，中序遍历序列为CHBADGEF，画出该二叉树，并写出二叉树的先序遍历序列。

13.已知在一份电文中只使用了6个字符A、B、C、D、E、F，各字符出现的次数分别为：{6，3，12，8，2，9}。

(1)请画出以各字符出现次数为叶子权值构造而成的哈夫曼树(权值小的为左子树)。 (2)请写出各字符的哈夫曼编码。

(3)请求出该哈夫曼树的带权路径长度WPL。为1的结点个数n1。

lchild data rchild

14.二叉树采用二叉链表存储结构，每个结点结构如上图所示，请写算法统计输出二叉树中度

5

11~14解答：

6

第三部分 图

1.若有5个结点的有向图是强连通图，则最少有( )条弧. 2.有向图中所有顶点的出度之和为n，则入度之和为( ) 3.在任何一个图G中，所有顶点的度数之和等于所有边数之和的( )倍。 4.在有8条边的无向图中，所有顶点的度之和为( ) 5.G是一个非连通无向图，共有9个顶点，则该图最多有( )条边。

6.若无向图的顶点集为{A，B，C，D，E，F，G}，边集为{(A，B)，(A，C)，(B，D)，(E，F)}，则该图含有( )个连通分量。

7.连通有7个顶点的有向图的所有顶点至少需要( )条弧，连通有7个顶点的无向图的所有顶点至少需要( )条边。

8.已知图的顶点集为 {v0,v1,v2,v3,v4} , 其邻接矩阵如下图（左）所示，从顶点v0出发，按照深度优先搜索算法得到的遍历序列为( )，按照广度优先搜索算法得到的遍历序列为( )。

9.已知一个有向图的邻接表如上图（右）所示，顶点V1的入度为( )，顶点V2的出度为( )，从顶点V0出发得到的深度优先遍历序列是( )，从顶点V1出发得到的广度优先遍历序列是( )。

10.已知无向网如下图（左）所示，请使用普里姆(prim)算法，按步骤画出从顶点A开始，构造最小生成树的详细过程。

D972B8152F36A3

11.已知有向网如上图（中）所示， （1）请写出下图的所有拓扑序列。

（2）请求出各顶点事件的最早发生时间Ve和最迟发生时间Vl。 （3）请求出源点A到汇点F的关键路径。

EC12.已知一个有向网G如上图（右）所示，求源点A到其它各顶点的最短路径及长度（写详细求解过程）。 10~12解答：

6

第三部分 图

1.若有5个结点的有向图是强连通图，则最少有( )条弧. 2.有向图中所有顶点的出度之和为n，则入度之和为( ) 3.在任何一个图G中，所有顶点的度数之和等于所有边数之和的( )倍。 4.在有8条边的无向图中，所有顶点的度之和为( ) 5.G是一个非连通无向图，共有9个顶点，则该图最多有( )条边。

6.若无向图的顶点集为{A，B，C，D，E，F，G}，边集为{(A，B)，(A，C)，(B，D)，(E，F)}，则该图含有( )个连通分量。

7.连通有7个顶点的有向图的所有顶点至少需要( )条弧，连通有7个顶点的无向图的所有顶点至少需要( )条边。

8.已知图的顶点集为 {v0,v1,v2,v3,v4} , 其邻接矩阵如下图（左）所示，从顶点v0出发，按照深度优先搜索算法得到的遍历序列为( )，按照广度优先搜索算法得到的遍历序列为( )。

9.已知一个有向图的邻接表如上图（右）所示，顶点V1的入度为( )，顶点V2的出度为( )，从顶点V0出发得到的深度优先遍历序列是( )，从顶点V1出发得到的广度优先遍历序列是( )。

10.已知无向网如下图（左）所示，请使用普里姆(prim)算法，按步骤画出从顶点A开始，构造最小生成树的详细过程。

D972B8152F36A3

11.已知有向网如上图（中）所示， （1）请写出下图的所有拓扑序列。

（2）请求出各顶点事件的最早发生时间Ve和最迟发生时间Vl。 （3）请求出源点A到汇点F的关键路径。

EC12.已知一个有向网G如上图（右）所示，求源点A到其它各顶点的最短路径及长度（写详细求解过程）。 10~12解答：

本文来源：https://www.bwwdw.com/article/d4r7.html