数据结构 习题答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构习题答案第1章概论

1.数据结构是一门讨论非数值计算的程序设计问题中,数据元素的①Ｃ、数据信息在计算机中的②A以及一组相关的运算等的课程。

①A．操作对象Ｂ．计算办法Ｃ．规律结构Ｄ．数据映象

②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法

2.计算机算法指的是①C，它必具备输入、输出和②B等五个特性。

①A.计算办法B.排序办法

C.解决问题的有限运算序列

D.调度办法

②A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性

D.易读性、稳定性和平安性

3.下面程序段的时光复杂度是D

for(i=0;inext=p；p->next=s；

B.s->next=p->next；p->next=s；

C.s->next=p->next；p=s；

D.p->next=s；s->next=p；

2.非空的不带头结点的循环单链表，首结点由first指向，尾结点由p指向，则满足：

C

A.p->next==NULL；

B.p==NULL；

C.p->next==first；

D.p==first；

3.在一个长度为n的挨次存储的线性表中，删除第i个元素（0≤i≤n-1）时，需要移动多少个元素？C

A.n-i

B.n-i+1

C.n-i-1

D.I

4.在带头结点指针head的单链表中，链表为空的推断条件是？B

A.head==NULL

B.head->next==NULL

C.head!=NULL

D.head->next==head；

5.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是B

A.p=p->next;

B.p->next=p->next->next;

C.p->next=p;

D.p=p->next->next;

6.在双链表中删除某个结点p，实现的语句是A

A.p->prior->next=p->next;p->next->prior=p->prior;

B.p->prior->next=p->next->prior;p->next->prior=p->prior;

C.p->next=p->prior;p->prior=p->next;

D.p->prior->next=p->next;

7.在双链表中给定结点p之后插入一个新结点s，实现的语句是C

A.s->next=p->next;s->prior=p;p->prior=s;p->next=s;

B.p->next=s;s->next=p->next;s->prior=p;p->next->prior=s;

C.s->next=p->next;s->prior=p;p->next->prior=s;p->next=s;

D.s->next=p->next;s->prior=p;p->next=s;p->prior=s;

8.在双链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向后继结点。

9.在线性结构中，第一个结点没有前驱结点，其余每个结点有且惟独1个前驱结点；最后一个结点没有后续结点，其余每个结点有且惟独1个后续结点。

第3章栈和队列

1.引起循环队列头位置发生变化的操作是？A

A.出对

B.入对

C.取对头元素

D.取对尾元素

2.若进栈序列为1，2，3，4，下面哪一个序列不行能是这个栈的输出序列？C

A.1，3，2，4

B.2，3，4，1

C.4，3，1，2

D.3，4，2，1

3.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插举行，则可能浮现的出栈序列

为B

A．3，2，6，1，4，5B．3，4，2，1，6，5

C．1，2，5，3，4，6D．5，6，4，2，3，1

4.一个队列的数据入队序列是1，2，3，4，则队列的出队时输出序列是？B

A.4，3，2，1

B.1，2，3，4

C.1，4，3，2

D.3，2，4，1

5.栈的两种常用存储结构分离为A

A．挨次存储结构和链式存储结构B．挨次存储结构和散列存储结构

C．链式存储结构和索引存储结构D．链式存储结构和散列存储结构

6.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分离为8

和3，则该队列的当前长度为C

A．5B．6C．16D．17

7.已知循环队列的存储空间为数组data[25]，且当前队列的头指针和尾指针的值分离为10

和5，则该队列的当前长度为？A

A．20B．25C．10D．15

8.判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是A。

A.((rear-front)+Maxsize)%Maxsize==m0

B.rear-front-1==m0

C.front==rear

D.front==rear+1

9.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分离是front和rear，则当前

队列中的元素个数是A。

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

10.栈和队列都是A

A．限制存取位置的线性结构B．挨次存储的线性结构

C．链式存储的线性结构D．限制存取位置的非线性结构

11.队和栈的主要区分是D

A.规律结构不同

B.存储结构不同

C.所包含的运算个数不同

D.限定插入和删除的位置不同

12.已知循环队列的存储空间为数组data[18]，且当前队列的头指针和尾指针的值分离为7和2，则该队列的当前长度为？A

A．13B．5C．9D．18

13.向量、栈和队列都是线性结构，可以在向量的_任何___位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和队首删除元素。

第4章串第5章数组

1.二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开头延续存放在存储器内，存放该数组至少需要的字节数是C。

A.80

B.100

C.240

D.270

2.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开头延续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为C。

A.SA+141

B.SA+144

C.SA+222

D.SA+225

3.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开头延续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为B。

A.SA+141

B.SA+180

C.SA+222

D.SA+225

4.已知二维数组A[m][n]采纳行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是__LOC(A[0][0])+(n*i+j)*k_____。

5.二维数组A[10][20]采纳列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是__200+（6*20+12）=326__。

6.二维数组A[10..20][5..10]采纳行序为主方式存储，每个元素占4个存储单元，并且A[10][5]的存储地址是1000，则A[18][9]的地址是_1000+((18-10)*6+(9-5))*4=1208__。

第6章树

1.如图所示的4棵二叉树，C不是彻低二叉树。

(A)(B)(C)(D)

2.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序？B

A.发生转变

B.不发生转变

C.不能确定

D.以上都不对

3.一棵含18个结点的二叉树的高度至少为C

A.3

B.4

C.5

D.6

4.根据二叉树的定义，具有3个结点的不同外形的二叉树有几种？A

A.5

B.4

C.3

D.6

5.对一个满二叉树，m个树叶，n个结点，深度为h，则?D

A.n=h+m

B.h+m=2n

C.m=h-1

D.n=2h-1

6.一棵二叉树中双分支结点数为15，单分支结点数为30个，则叶子结点数为16个。

7.在一棵二叉树中，度为零的结点个数为n

0，度为2的结点个数为n

2

，则有n

=n

2

+1。

8.一棵二叉树的第i（i≥1）层最多有2i-1个结点。

9.已知彻低二叉树T的第5层惟独7个结点，则该树共有叶子结点数目为11。

10.深度为5的二叉树至多有31个结点。

11.某二叉树的前序遍历结果为stuwv，中序遍历为uwtvs，那么后序遍历为wuvts。

12.某二叉树的前序遍历为abdgcefh，中序遍历为dgbaechf，则后序遍历的为gdbehfca。

13.在树型结构中，树根结点没有前驱结点，其余每个结点有且惟独1个直接前驱结点，叶子结点没有后继结点，其余每个结点的直接后继结点可以随意多个。

14.有一棵树如图所示，回答下面的问题：

⑴这棵树的根结点是__k1__；

⑵这棵树的叶子结点是

_k2,k5,k7,k4___；

⑶结点k3的度是_2___；

⑷这棵树的度是_3___；

⑸这棵树的深度是__4__；

⑹结点k3的子女是__k5,k6__；

⑺结点k3的父结点是__k1__；

15.设字符a,b,c,d,e,f的使用权值分离是7,9,12,22,23,27，画出Huffman树，并写出a,b,c,d,e,f的Huffman编码。

Huffman编码为

a:1110b:1111c:110d:00e:01f:10

16.设字符a,b,c,d,e,f,g的使用权值分离是4，5，6，7，10，12，18，画出Huffman树，并写出a,b,c,d,e,f,g的Huffman编码。

Huffman编码为

a:1100b:1101c:010d:011e:111f:00g:10

17．二叉树如图所示，要求完成如下任务：

（1）画出该二叉树的中序线索二叉树；（2）画出该二叉树对应的森林。。

中序线索二叉树为：该二叉树对应的森林为：

18．已知二叉树的先序序列和中序序列分离为HDACBGFE和ADCBHFEG。（1）画出该二

叉树；（2）画出（1）中求得的二叉树对应的森林。

二叉树:二叉树对应的森林:

19.已知二叉树的先序序列和中序序列分离为ABDEGCFH和DBGEACFH。（1）画出该二叉树；（2）画出（1）中求得的二叉树对应的森林。

二叉树:二叉树对应的森林:

第7章图

1.在用于表示无权有向图的相邻矩阵中，对第j列的非0元素个数举行累加，可得到第j个顶点的？B

A．出度B．入度C．权值D．衔接边个数

2.在用于表示无权有向图的相邻矩阵中，对第i行的非0元素个数举行累加，可得到第i个顶点的？A

A．出度B．入度C．权值D．衔接边个数

3.在一个图中，全部顶点的度数之和等于全部边数的几倍？C

A．1/2B．1C．2D．4

4.假如某图的相邻矩阵是对称的，则此图是？D

A.彻低图

B.连通图

C.有向图

D.无向图

5.对于一个具有n个结点和e条边的无向图，若采纳邻接表表示，则邻接表的存储单元大小为A

A．n+2eB．nC．eD．n+e

6.在图型结构中，每个结点的前驱结点数和后续结点数可以随意多个。

7.在一个具有n个顶点的无向图中，要连通所有顶点至少需要n-1条边。

8.一个有n个顶点的无向图最多有n(n-1)/2条边。

9.具有4个顶点的无向彻低图有6条边。

10.已知有向图的邻接矩阵如图所示，要求完成如下任务：（1）请画出此有向图；（2）给出该有向图的邻接表。

?

????????????

???????

?????

?=00

1

000010000010000000010000000000000000010001001100001000100

A

有向图为：邻接表为：

11．已知有向图的邻接表如图所示，要求完成如下任务：（1）请画出此有向图；（2）给出该有向图的邻接矩阵。

有向图为：邻接矩阵为：

????????????

?

???????

??????=00

1