数据结构复习资料--覆盖所有知识点

数据结构复习及答案

一、选择填空

1. 下面关于线性表的叙述中，错误的是哪一个？（ B ） A）线性表采用顺序存储，必须占用一片连续的存储单元。 B）线性表采用顺序存储，便于进行插入和删除操作。 C）线性表采用链接存储，不必占用一片连续的存储单元。 D）线性表采用链接存储，便于插入和删除操作。

2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用

（ A ）存储方式最节省时间。

A）顺序表 B）双链表 C）带头结点的双循环链表 D）单循环链表 3. 链表不具有的特点是（ B ）。

A）插入、删除不需要移动元素 C）不必事先估计存储空间

B）可随机访问任一元素 D）所需空间与线性长度成正比

4. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度

为（ C ）(1<=i<=n+1)。 A）O(0) B）O(1)

C）O(n) D）O(n2)

5. 线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（ C ）。

A）O(i) B）O(1) C）O(n) D）O(i-1)

6. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ B ）。 A）p->next=s;s->next=p->next; B） s->next=p->next;p->next=s; C）p->next=s;p->next=s->next; D） p->next=s->next;p->next=s;

7. 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( A )。

A）p->next=p->next->next C）p=p->next->next

B） p=p->next D） p->next=p

8. 在双向链表指针p的结点前插入一个指针q的结点操作是（ C ）。

A） p->prior=q;q->next=p;p->prior->next=q;q->prior=q； B） p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior; C） q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q;

D） q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

9. 在双向链表存储结构中，删除p所指的结点时须修改指针（ A ）。 A） (p->prior)->next=p->next (p->next)->prior=p->prior; B） p->prior=(p->prior)->prior (p->prior)->next=p; C） (p->next)->prior=p p->next=(p->next)->next

D） p->next=(p->prior)->prior p->prior=(p->next)->next; 10. ( A )又称为FIFO表；( C )又称为FILO表。

1

A）队列 B）散列表 C）栈 D）哈希表

11. 对于栈操作数据的原则是（B）。

A）先进先出 B）后进先出 C）后进后出 D）不分顺序

12. 用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则

在进行删除操作时( D )。 A）仅修改队头指针

B）仅修改队尾指针

D）队头、队尾指针都可能要修改

C）队头、队尾指针都要修改

13. 假设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素

个数为（ A ）。

A）(rear-front+m)%m B）rear-front+1 C）(front-rear+m)%m D）(rear-front)%m 14. 栈和队列的共同点是（ C ）。

A）都是先进先出

B）都是先进后出

C）只允许在端点处插入和删除元素 D）没有共同点

15. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈

后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。 A） 6 B）4 C）3 D）2

16. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储

地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A）12

B）33

C）18

D）40

17. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组

B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( 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

18. 由3 个结点可以构造出多少种不同的二叉树？( D ) A）2

B）3

C）4

D）5

19. 二叉树中第i(i≥1)层上的结点数最多有( C )个。

A） 2i

B） 2i

C） 2i-1

D） 2i-1

20. 在有n个叶子结点的哈夫曼树中，其结点总数为( D )。

A）不确定

B）2n C）2n+1

D）2n-1

21. 一棵二叉树高度为h，所有结点的度或为0、或为2，则这棵二叉树最少有( A )结点。

A）2h

B）2h-1

C）2h+1

D）h+1

22. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( A )。

A）9

B）11

C）15

D）不确定

23. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为( D )。

A）5

B）6

C）7

D）8

24. 树的后根遍历序列等同于该树对应的二叉树的( B )。

2

A）先序序列 B）中序序列 C）后序序列 25. 在下列存储形式中，哪一个不是树的存储形式？( D )

D.层序序列

A）双亲表示法 B）孩子链表表示法 C）孩子兄弟表示法 D）顺序存储表示法 26. 在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( B )。

A）都不相同

B）完全相同

D）中序和后序相同，而与先序不同

C）先序和中序相同，而与后序不同

27. 下列哪一种图的邻接矩阵是对称矩阵？( B )

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

28. 在一个无向图中，所有顶点的度数之和等于所有边数( B )倍，在一个有向图中，所有顶点的

入度之和等于所有顶点出度之和的( C )倍。 A）1/2

B）2

C）1

D）4

29. 一个有n个顶点的无向图最多有( D )条边。由n个顶点组成的有向图，最多可以有( D )条

边。 A）n*n

B）2n C）n(n-1)

D）n(n-1)/2

30. 下列说法不正确的是( C )。

A）图的遍历是从给定的源点出发每一个顶点仅被访问一次 B）遍历的基本算法有两种：深度遍历和广度遍历 C）图的深度遍历不适用于有向图 D）图的深度遍历是一个递归过程

31. 下面哪一方法可以判断出一个有向图是否有环(回路)。( AB ) A）深度优先遍历

B）拓扑排序

C）求最短路径 D）求关键路径

32. 下列算法中，( A )算法用来求图中每对顶点之间的最短路径。

A）Dijkstra

B）Floyed

C）Prim

D）Kruskal

33. 关键路径是事件结点网络中( A )。

A）从源点到汇点的最长路径 B）从源点到汇点的最短路径 C）最长回路 D）最短回路

34. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记

录，其平均查找长度ASL为( C )。 A） (n-1)/2

B）n/2

C）(n+1)/2

D）n

35. 下面关于二分查找的叙述正确的是 ( D ) 。

A）表必须有序，表可以顺序方式存储，也可以链表方式存储 B）表必须有序，而且只能从小到大排列

C）表必须有序且表中数据必须是整型，实型或字符型 D）表必须有序，且表只能以顺序方式存储 36. 折半查找的时间复杂性为( D ) 。

3

A）O(n2)

B）O(n) C）O(nlogn) D） O(logn)

37. 下面关于哈希(Hash，杂凑)查找的说法正确的是( C )。 A）哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B）除留余数法是所有哈希函数中最好的 C）不存在特别好与坏的哈希函数，要视情况而定

D）若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可 38. 下面给出的四种排序法中( D )排序法是不稳定性排序法。 A）插入

B）冒泡 C）二路归并 D）堆

39. 有一组数据(15，9，7，8，20，-1，7，4) 用快速排序的划分方法进行一趟划分后数据的排序

为 ( A )(按递增序)。

A）下面的B，C，D都不对。 B）9，7，8，4，-1，7，15，20 C）20，15，8，9，7，-1，4，7 D）9，4，7，8，7，-1，15，20

40. 设有一个文件有200个记录，按分块查找法查找记录，如分成10块，每块20个记录，用二分

查找法查索引表，用顺序查找法查块内记录，则平均查找长度为( )。 A）8.4

B）10.5

C）13.4

D）16

41. 快速排序在最坏情况下的时间复杂性为( )。

A）O(nlog2n) 二、填空

1. 一个算法的效率可分为 空间 效率和 时间 效率。

2. 线性表L=（a1,a2,…,an）用数组表示，假定插入、删除表中任一元素的概率相同，则插入、删

除一个元素平均需要移动元素的个数是 和 。

3. 对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为

O(1) ，在给定值为x的结点后插入一个新结点的时间复杂度为 O(n) 。

4. 顺序存储结构是通过 元素的存储地址 表示元素之间的逻辑关系的；链式存储结构是通过 节点的指针 表示元素之间的逻辑关系的。

5. 顺序栈S用data[1..n]存储数据，栈顶指针是top，则值为x的元素入栈的操作是data[++top]=x。 6. 已知链队列Q的头尾指针分别是f和r，则将值x入队的操作序列是

s=(LinkedList)malloc(sizeof(LNode));s->data=x;s->next=r->next;r->next=s;r=s; s->next=r->next 。 7. 稀疏矩阵的存储策略是只存储稀疏矩阵的非零元素。

8. 稀疏矩阵的存储方法主要有两个：一个是三元组表 ，另一个是十字链表示法。 9. 二叉树由 根 ，叶子节点 、 层数 三个基本单元组成。

10. 一棵有n个结点的满二叉树有0个度为1的结点、有 （n-1）/2 个分支 (非终端)结点和 (n+1)/2

叶子，该满二叉树的深度为 log2 (n+1) 。

11. 线索二叉树的左线索指向其 前驱右线索指向其 后继。

B）O(n2)

C）O(n)

D）O(nlogn)

4

12. 在有n个结点的二叉链表中，空链域的个数为n+1。 13. 在有n个结点的二叉链表中，空链域的个数为 。

14. 设一棵完全二叉树具有1000个结点，则此完全二叉树有 个叶子结点，有_499_个度

为2的结点，有 500 个度为1的结点。

15. 若用n表示图中顶点数目，则有 n(n-1)/2 条边的无向图成为完全图。

16. 设无向图 G 有n 个顶点和e 条边，每个顶点Vi 的度为di(1<=i<=n〉，则e=（d1+d2+d3+......+dn）/2。

17. 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的 度 ；对于有向图来说等于该顶点的 出度 。

18. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次；当使用监视

哨时，若查找失败，则比较关键字的次数为 n+1 。

19. 在顺序表(8,11,15,19,25,26,30,33,42,48,50)中，用二分(折半)法查找关键码值20，需做的关键码

比较次数为 4 。

20. 已知二叉排序树的左右子树均不为空，则 左子树 上所有结点的值均小于它的根结点值, 右子树 上所有结点的值均大于它的根结点的值。

21. 动态查找表和静态查找表的重要区别在于前者包含有 插入 和 删除 运算，而后者不包含这两

种运算。

22. 为了能有效地应用HASH查找技术，必须解决的两个问题是___构造一个好的HASH函数和__

确定解决冲突的方法。

23. 属于不稳定排序的有 希尔排序、简单选择排序、快速排序、堆排序等 。

24. 对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 n(n-1)/2_。 25. 快速排序算法的时间复杂度为 O(n2) 。 三、应用题

1. 试画出下列稀疏矩阵的三元组表示。

稀疏矩阵

5

二叉树有哪几种基本形态? 画图说明之。

2. 写出下列二叉树的前序，中序，后序遍历序列及对应的森林 。

3. 设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C

(1) 画出这棵二叉树。

(2)画出这棵二叉树的后序线索树。

(3)将这棵二叉树转换成对应的树(或森林)。

4. 已知二叉树的中序和后序遍历序列如下，试构造该二叉树。

中序：A C B D H G E F 后序：A B C D E F G H

b c a + * d - / e

5. 试将森林 F={ T1,T2,T3,T4 }转换为一棵二叉树。

6

T1 T2 T3 T4

6. 画出下列二叉树对应的先序、中序、后序线索二叉树存储结构。a b c d e f g h i

7

7. 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。

8. 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩

子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。

8

9.

已

知

有

向

图

G=(V,E)

，

其

中

V={V1,V2,V3,V4,V5,V6,V7}

，

E={,,,,,,,,},G的拓扑序列是( )。

10. 有7个顶点（v1,v2,v3,v4,v5,v6,v7） 的有向图的邻接矩阵如右图。请回答相关问题： （1） 画出该有向图。

（2） 写出从v1出发的深度优先遍历和广度优先遍历序列。

9

∞ ∞ ∞ ∞ ∞ ∞ ∞

2 ∞ ∞ ∞ ∞ ∞ ∞ 5 2 ∞ ∞ ∞ ∞ ∞ 3 ∞ 1 ∞ ∞ ∞ ∞ ∞ ∞ 3 5 ∞ ∞ ∞ ∞ 8 5 ∞ 3 ∞ ∞ ∞ ∞ ∞ ∞ 9 5 ∞

（1）画出该有向图

（2）画出邻接表

（3）写出从v1出发的深度优先遍历和广度优先遍历序列（4分） 深度dfs v1 v4 v5 v7 v6 v3 v2 广度bfs v1 v4 v3 v2 v5 v6? v7

（4）将图看成AOE网，画出关键活动及相应的有向边，写出关键路径的长度

关键路径的长度为20

11. 已知如图所示的有向图，请给出该图的 :答案不全

10

（1） 每个顶点的入/出度； 顶点 1 2 3 4 5 6 （2） 邻接矩阵； 入度 （3） 邻接表；

出度

（4） 邻接表定义：

typedef struct node {

int adjvex; //邻接点域，存放与Vi邻接的点在表头数组中的位置 struct node *next; //链域，指示下一条边或弧 }JD;

typedef struct node {

char vexdata[100]; //存放顶点信息 JD *firstarc; //指示第一个邻接点 }TD;

TD ga[MAX];

（5） 逆邻接表。

12. 下面的邻接表表示一个给定的无向图

(1) 给出从顶点v1开始,对图G用深度优先搜索法进行遍历时的顶点序列；（1）V1V2V4V3V5V6

(2)给出从顶点v1开始,对图G用广度优先搜索法进行遍历时的顶点序列。 11

（2）V1V2V3V4V5V6

13. 设无向图G（所下图所示），要求给出该图的深度优先和广度优先遍历的序列，找出下面网

络的最小生成树。

分别说明Huffman算法、Dijkstra算法、Prim算法、Kruskal算法的功能。

Huffman算法:求Huffman树（带权路径长度最短的二叉树） Dijkstra算法:求图中从某个源点到其余各顶点的最短路径 Prim算法:求最小生成树 Kruskal算法:求最小生成树 14. 已知图G如图所示。 （1） 画出图G的邻接表；

（2） 画出从顶点1出发的深度优先生成树和广度优先生

成树；

（3） 写出图G的拓扑排序列； 14.

12

15. 已知AOE网如下，试求其关键路径。要求写出计算过程。

16. 试利用Dijkstra算法求下图中从顶点a到其他个顶点间的最短路径，写出执行算法过程中各

步的状态。

13

17. 设一组记录的关键字为{4，5，7，2，1，3，6}，请回答相关问题：

（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并

求出在等概率情况下查找成功的平均查找长度。

（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树。并求出在等概率情况下查找成功的

平均查找长度。

18. 假定一个线性表为L=（18，75，60，43，54，90，46，31，58，73，15，34）进行散列存

储，采用的Hash函数为H（K）=K mod 13 ，当发生冲突时用线性探测法处理冲突，设Hash表的表长为13，试构造Hash表，并求出平均查找长度。

19. 序列{40，38，60，95，76，10，25，50，99}是堆吗？若不是，首先创建一个堆，然后用堆

排序方法进行从小到大排序。要求写出主要过程。

14

20. 给出如下关键字序列321，156，57，46，28，7，331，33，34，63试按链式基数排序方法，

列出一趟分配和收集的过程。

按LSD法 →321→156→57→46→28→7→331→33→34→63 分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 321 33 34 156 57 28 331 63 46 7

收集 →321→331→33→63→34→156→46→57→7→28

四、算法设计题

1. 从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变（采用顺序存储结构实现）。 Status deldup_sq(SqList &L){ int j=0,k;

if(L）length >0)

{ for(int i=1;ij) L.elem [++j]=L.elem [i]; } L.length =j+1; return OK; } else return ERROR;}

15

2. 设有一带头结点的单链表，编写一个算法将链表颠倒过来。

void invert(LinkList &La){

/*逆置单链表*/

LinkList r,p=La->next; /*p为工作指针*/ La->next=NULL; while(p!=NULL){ }

}/*结束invert函数*/

3. 已知L为带头结点的单链表，设计一个算法计算数据域为x的结点个数。

int count(LinkList La,ElemType x){ //计数x出现的次数

LinkList p=La->next; //p为工作指针 int n=0; while(p){

if(p->data ==x) n++; p=p->next ;

r=p->next; /*暂存p的后继*/ p->next=La->next; La->next=p; p=r;

}return n;}

4. 设L为有序顺序表，试编写一个算法删除L中的重复元素。要求不要另开辟数据存储空间。

例如：L=（1，1，2，4，4，9，9，9），执行算法后L=（1，2，4，9）

int delduplicate(int a[],int n){ int i,j,k,count; i=0;

while (i

16

n=n-count;i++; }

return n;}

假设一个人算术表达式包含圆括弧，编写一个判别表达式中括弧是否正确匹配的算法。

Status AllBrackets_Test(char *str)// 判别表达式中三种括号是否匹配 {

InitStack(s); for(p=str;*p;p++) {

if(*p=='('||*p=='['||*p=='{') push(s,*p); else if(*p==')'||*p==']'||*p=='}') {

if(StackEmpty(s)) return ERROR; pop(s,c);

if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR;

if(*p=='}'&&c!='{') return ERROR; // 必须与当前栈顶括号匹配 } }//for

if(!StackEmpty(s)) return ERROR; return OK;

5. 17

}//AllBrackets_Test

6. 设二叉树采用二叉链表法存储，试编写一个求二叉树深度的算法。 int Depth (BiTree &T ){ // 返回二叉树的深度 int depthval,depthLeft,depthRight; if ( !T ) depthval = 0; else { depthLeft = Depth( T->lchild ); depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ? depthLeft : depthRight);

}

return depthval;}

7. 编写算法,求二叉树中度为2结点个数。

void Countdu2 (BiTree &T, int &count){ //统计二叉树中度为2结点的个数 if ( T ) {

if ((T->lchild)&& (T->rchild))

count++; // 对度为2的结点计数 Countdu2( T->lchild, count); Countdu2( T->rchild, count); } // if } // Countdu2

8. 编写算法,求二叉树中叶结点的个数。

void CountLeaf (BiTree &T, int &count){ if ( T ) {//统计叶子节点个数 if ((!T->lchild)&& (!T->rchild)) count++; // 对叶子结点计数 CountLeaf( T->lchild, count); CountLeaf( T->rchild, count); } // if} // CountLeaf

18

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