数据结构复习题

数据结构复习题·精简版

数据结构体大题：

1．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文

的编码最短。

2.设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02，试设计哈夫曼树及其编码。使用0---7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点。

3. 已知一棵二叉树的前序遍历为ABECDFGHIJ，中序遍历为EBCDAFHIGJ。试画出这棵树和它的中序线索树。假定用于通讯的电文仅有8个字母C1，C2，…，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。

4．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。

20 1 2 5 11 9 6 14 6 3 10

10

4 6 5 18

第3题图

5．已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 V2 V3 V4 V5 V6 V7 V8 V9 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 V10 0

当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。

1

6．下表给出了某工程各工序之间的优先关系和各工序所需时间（10分）

（1）．画出相应的AOE网 （2）．列出各事件的最早发生时间,最迟发生时间 （3）．找出关键路径并指明完成该工程所需最短时间. 工序代号 ABC D E F G H I J K L 30 M N 所需时间 15 10 50 8 15 40 300 15 120 60 15 先驱工作 -- -- A,B B C,D B E G,I E 20 40 G I F,I H,J,K L

7．数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：

（1）存放该数组所需多少单元？

（2）存放数组第4列所有元素至少需多少单元？

（3）数组按行存放时，元素A[7,4]的起始地址是多少？ （4）数组按列存放时，元素A[4,7]的起始地址是多少？

8．已知一图如下图所示：

（1）．写出该图的邻接矩阵； （2）．写出全部拓扑排序； （3）．以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； （4）．求V1结点到各点的最短距离。 V1 V3 3 3 V7 10 V5 3 2 1 2

5 4 V6 6 V8 V2 V4

第8 题图

9．设某二叉树的前序遍历序列为:ABCDEFGGI，中序遍历序列为:BCAEDGHFI：

（1）试画出该二叉树；

（2）写出由给定的二叉树的前序遍历序列和中序遍历序列构造出该二叉树的算法。 （3）设具有四个结点的二叉树的前序遍历序列为ａｂｃｄ；Ｓ为长度等于四的由ａ，ｂ，ｃ，ｄ排列构成的字符序列，若任取Ｓ作为上述算法的中序遍历序列，试问是否一定能构造出相应的二叉树，为什么？试列出具有四个结点二叉树的全部形态及相应的中序遍历序列。

（4）已知一棵二叉树的前序遍历结果是：ABCDEFGHIJ,中序遍历的结果是：BCEDAGHJIF,试画出这棵二叉树。

（5）已知二叉树BT各结点的先序、中序遍历序列分别为ABCDEGF和CBAEDF，试画出该二叉树。

2

判断题：

1. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。( ) 3．强连通图的各顶点间均可达。（ ）

4. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. ( ) 5．由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ） 6. 二维以上的数组其实是一种特殊的广义表。（ ） 8. 循环队列也存在空间溢出问题。（ ） 9. 完全二叉树一定存在度为1的结点。（ ）

10. 对于有N个结点的二叉树，其高度为log2n。（ ） 11．深度为K的二叉树中结点总数≤2k-1。（ ）

12. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ 13 若一个广义表的表头为空表，则此广义表亦为空表。（ ）

14. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（15. 所谓取广义表的表尾就是返回广义表中最后一个元素。（ ）

3

） ） 填空题：

1．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______。

2.判断一个无向图是一棵树的条件是______。

3. 对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为______，邻接表的边结点个数为______。

4. 执行顺序查找时，储存方式可以是__ _，二分法查找时，要求线性表__ __，分块查找时要求线性表 __ _，而散列表的查找，要求线性表的存储方式是__ _。

5．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。

6. 将整型二维数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：_______。

7．设广义表L=((),()), 则head(L)是__ _；tail(L)是__ _；L的长度是__ _；深度是__ _。

8. 对于给定的n个元素,可以构造出的逻辑结构有__ _，__ _， __ _，____ _四种。

9．有向图G的强连通分量是指______。 10．一个连通图的______是一个极小连通子图。

11. 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是______遍历方法。

12．二叉树由__ _，__ _，__ _ 三个基本单元组成。

13. Prim（普里姆）算法适用于求______的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求______的网的最小生成树。

14. 设数组A[0..8,1..10],数组中任一元素A[i,j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （l） 存放该数组至少需要的单元数是_______;

（2） 存放数组的第8列的所有元素至少需要的单元数是_______; （3） 数组按列存储时，元素A[5,8]的起始地址是_______。

4

选择题：

1．程序段 FOR i:=n-1 DOWNTO 1 DO

FOR j:=1 TO i DO IF A[j]>A[j+1]

THEN A[j]与A[j+1]对换；

其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ） A. O（n） B. O(nlogn) C. O(n3) D. O(n2)

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

3. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。

A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1

4. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。

A. 1和1 B. 1和3 C. 1和2 D. 2和3

5. 在下述结论中，正确的是（ ）

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③ B．②③④ C．②④ D．①④

6．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。

A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序

7．无向图G=(V,E),其中：

V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。

A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b

8. 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ ）算法，最费时间的

是（ ）算法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序

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

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

10．用相邻矩阵A表示图，判定任意两个顶点Vi和Vj之间是否有长度为m 的路径相连，

5

则只要检查（ ）的第i行第j列的元素是否为零即可。

m

A．mA B．A C．A D．Am-1

11．若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行

concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index(S2,‘8’),length(S2))) 其结果为（ ）

A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 12．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

13. 已知广义表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）））)）

14．一个n个顶点的连通无向图，其边的个数至少为（ ）。

A．n-1 B．n C．n+1 D．nlogn；

15．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的

2

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N

16. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:

tail(head(tail(C))) =( )。

A.（a） B. A C. a D. (b) E. b F. (A)

17. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。

A. (c,d) B. c,d C. ((c,d)) D. d

18. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1

19. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。

A. 0 B. 1 C. 2 D. 不确定

20. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )

A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点

6

21．下列哪一种图的邻接矩阵是对称矩阵？（ ）

A．有向图 B．无向图 C．AOV网 D．AOE网

22. 下列说法不正确的是（ ）。

A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 C．图的深度遍历不适用于有向图

B．遍历的基本算法有两种：深度遍历和广度遍历 D．图的深度遍历是一个递归过程

23．如果待排序序列中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的。（ ）就是不稳定的排序方法。

A．起泡排序 B．归并排序 C．Shell排序 D．直接插入排序 E．简单选择排序

7

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