数据结构习题集

《数据结构》习题集

学号：___________

姓名：___________

指导教师：

第1章绪论

1、填空题

1.常见的数据结构有结构，结构，结构，结构等四种。

2.常见的存储结构有结构，结构等两种。

3.数据的基本单位是，它在计算机中是作为一个整体来处理的。

4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，和—

2、选择题

1-算法的计克笊的大小标为计算的(),

A.效率B,复杂性C.现实性D,难度

2.算法的时间更杂度取决于()

A.问题的规模B.待处理数据的初态C.A和BD.以上都不对

3.计算机算法指的是(1)(),它必须具备(2)()这三个特性。

(1)A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法

(2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性D.易读性、稳定性、安全性

1,下面关于算法说法错误的是()

A.算法最终必须由计算机程序实现

B.为解决某问题的党法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性D.以上几个都是错误的

3、应用题

1、给出以下算法的时间复杂度.

voidfun(intn)

(

inti=l,k=100;

while(i<n)

(

k-k+1;

i=i+2:

)

}

时间红杂度为______________

2、给出以下算法的时间红杂度.

voidfun2(intn)

(

inti=l,k=100;

while(i<n)

(

i=i*10：

k=k+l;

}

时间复杂度为

第2章线性表

1、填空题

L线性表按照存储结构不同主要有两种实现方式，一种是表，另一种是

_______________表。

2.顺序表采用访问机制对数据元素进行访问。

3.若在单链表结点p的后面插入一个新的结点s,则其操作序列为：

___________________________；

②_____________________________：

4.在单向链表中，若要删除其个结点p,必须要找到结点，才能实现该操作。

2、选择题

I.将两个各有n个元素的有序表归并成一•个有序表，其最少的比校次数是。

(A)n(B)2n-1(C)2n(D)nl

2.在单链表中，如果在结点p之后插入一个新结点s,其操作为。

(A)s>next=p>next;p>next=s;

(B)p>next=s;s>next=p>next;

(C)s>next=p;p>next=s>next;

(D)p>nexl=s：s>next=p;

3.若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间更杂度为

()o(IWiWn)

C.O(O)B.0(1)C.O(n)D.0(n2)

4.若长度为n的线性表采用顺序存储结构，在其第i个位置前插入•个新元素需要移动的元素个数

为()。(］爸iWn+1)

A.niB.ni+1C.iD.nil

3、判断题

1.线性表中每一个元素都有一个前驱和一个后继。()

2.在顺序存储结构中，有时也存储数据结构中元素之间的关系。()

3.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()

4、程序设计题

】、单链表的结点结构定义如下：

structLinkNodc

(

LinkNode*next;

intdata;

)：

请根据描述函数的功能写程序。

voidInsert(LinkNode*h,LinkNode*s)

{〃h指向链表的头结点(即及链表中没有元素，头结点也存在。)

〃链表中元素已经递增有序

〃函数功能为将结点s插入到链表h中。插入后链表仍然保持递增的顺序

}

第3章栈和队列

1、填空题

1.栈和队列在本质上都是。

2.栈的操作特点是°队列的操作特点是__________.

2、选择题

1.消除递归不一定需要使用板,此说法O

A.正确B.错误

2.用单循环链表表示队列，正确的说法是.

(A)可设一个头指针使入队、出队都方便；

⑻可设个尾指针使入队、出队都方便；

(C)必须设头尾指针才能使入队、出队都方便；

(D)无论如何，只可能使入队万便。

3、判断题

1.栈的特点是先进先出。()

2.可以在队列的任意位置插入元素。()

3.如果进栈的序列为(1,2,3,4),则(4,2,3,1)不可能是出栈序列。()

4.在用峨序表表示的循环队列中，可用标志位来区分队空或队满的条件。()

第4章串

1、选择题

1.设有两个中P和q，求q在p中首次出现的位置的运算称作（）

A.连接B.模式匹配C.求子串D.求串长

2、判断题

1.空串和空格串是同一个概念，二者没有区别。（）

第5章数组和广义表

1、填空题

1.二维数组在内存中存储可以有两种存储方式，一种是优先存储，一种是优先存

储。

2.设广义表L=(0,0,(())),则head(L)是；tail(L)是：L的长度

是;L的深度是。

3.设广义表L=((a),⑹,((c)))则hcad(L)是——；tail(L)是0

2、选择题

1.在C语言中,如果有数组定义intA[8][9]；假定每个整型数据占2字节，则数组元素

的地址是()。

AA+RORA+76C,A+«2D以上都不对

2.广义表人=(a,b,(c,d),(e,(f,g))),则下面式子的值为()；

Head(Tai1(Head(Tail(Tai1(A)))))

A.(g)C.cD.d(d)C.cD.d

3、判断题

1.在。语有中，多维数组的存储来取的运行优先的方式。()

2.广义表在木质上也是线性表。()

3.可以用三元组存储法来压缩存储稀疏矩阵。()

4.已知广义表A=((a,b,c),(d,e,。)，从A中取出原子e的运算是head(tai1(head(tai1(A)))),

()

第6章树和二叉树

1、填空题

I.-•棵62个叶结点的完全二叉树,最多1T个结点.

2.若规定仅有根的二叉树的高度为1,那么高为h的完全二叉树最多有个结点，最

少有个结点o

3.设只包含有根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为,

最小结点数为.

4.设仅包含根结点的二叉树的高度为1,则高度为k的二叉树的最火结点数为,最

小结点数为.

2、选择题

1.具布•N个结点的完全二叉树的深度是—。

(A)log盘(B)logzN+1

(0logl(2N)(D)log?N1

2.设二叉树的树根为第一层，则第i层上至多有结点。

(A)l(B)2(O21'(D)2il

3、判断题

1.二叉树的左右子树次序是严格的，不能够任意改变。()

2.深度为k的满二叉树的结点为241。()

3.二叉树的三叉链表存储结杓可以方便的访问到双亲结点。()

4、应用题

L在一段文字中,共出现a、b、c、d、e、f六种字符,每种字符出现的频率分别为7,9,12,22,23,27。

请回答下列问题：

（1）什么是哈夫曼树？（3分）

（2）根据题目所给频率值，画出相应的哈夫曼树。（11分）

（3）给出各个字符对应的哈夫曼编码。（6分）

（4）该段文字经过哈夫曼编码后，长度是多少。（4分）

2.设一棵二叉树的先序遍历序列为abcde,中序遍历序列为badce,请画出对应的二叉树，并写出对

应后序遍历序列。（15分）

3.通信报文中出现的字符A、B、C,D,E,在报文中出现的频率分别为0.23、0.2、0.32、0.12,

0.13,分别给出相应字符的哈夫灵编码（要求画出哈夫曼树，并且把权值小的结点放在左边）。（共

14分）

4.请证明对于任何一棵二叉树，如果其终端结点数为nO,度为2的结点数为n2,则nO=n2+l.（10

分）

5.请按照孩子兄弟表示法，将图1所示树转化为二叉树。（共14分）

图I

6.已知某二叉树的前序遍历序列为：ABCDEFG和中序遍历序列为：CBEDAFG。请画出该二叉树。

7.已知通信联络中只可能出现A、E、C、D、E、F、G、H共8种字符，其出现次数分别为5,28,7,9,14,

23,3,11次。

（1）请画出赫夫曼树（权值小的结点在左边）。（15分）

（2）计算该树的带权路径长度。（3分）

第7章图

1、填空题

1.有n个顶点的有向连通图最多有条边，最少有条边。

2.具有n个顶点的完全无向图有条边，完全有向图有条边。

2、选择题

1.方法可以判断出一个有向图中是否有环(回路)。

(A)深度优先遍历(B)拓扑排序

(C)求最短路径(D)求关键路径

2.关键路径是指。

(A)从开始事件到终止事件路径长度最短的路径

(B)从开始事件到终止事件路径长度最长的路径

(C)从开始事件到终止事件活动最少的路径

(D)从开始事件到终止事件活动最多的路径

3、判断题

I,具有n个顶点的有向图最多有n*(nD条边。()

2.在AOV网中，不应该出现有向环，因为存在环就意味着活动可以以白已为先决条件。(

4、应用题

I、已知某图的存储结构如下，试写出该图从顶点A开始的深度优先遍历序列。(II分)

ABCDFIJK

01111100000

00000010000

00000001000

00000000100

00000000010

00000000001

01000000000

00100000000

00010000000

00001000000

00000100000

2.请给出图1的所有最小生成树。（10分）

图1

3.已知某图采取如图2所示的邻接矩阵表示法，请回答下列问题。（共12分）

123456

0

1011000

2100110

3100011

4010000

5011000

6001000

图2

（1）请画出该图。（6分）

（2）对其从顶点A开始进行深度优先遍历，写出遍历序列。（6分）

4、（本题总计7分）

构造该图的最小生成树。

第9章查找

1、选择题

1,若在线性表中采用二分查找法查找元素，该线性表应该（）。

A.元素按值有序R.采用顺序存储结构

C.元素按值有序，且采用顺序存储结构

D.元素按值有序，且采用链式存储结构

2.对二叉排序树进行______遍历，可以得到该二叉树所有结点构成的有序序列。

（A）前序（B）中序（C）后序（D）按层次

3.利用逐点插入法建立序列（51,71,43,81,74,20,34,45,64,30）对应的二叉排序树以后,查

找元素3，1要进行（）元素间的比较。

A.4次B.5次C.7次D.10

4.对二叉排序树进行__________遍历，可以得到该二叉树所有结点构成的有序序列。

（A）前序（B）中序（C）后序（D）按层次

5.散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。

A.最大概率B,最小概率C.同等概率D,平均概率

6•一个哈希函数被认为是“好的”，如果它满足条件_________°

（A）哈希地址分布均匀

（B）保证不产生冲突

（C）所有哈希地址在表氏范围内

（D）满足⑻和（C）

7.哈希表的平均行找长度是________的函数。

（A）哈赤表的长度（B）表中元素的多少

（C）哈希函数（D）哈希表的装满程度

8.平均查找长度最短的查找方法是__________°

（A）折半查找（B）顺序查找（C）哈希查找（4）其他

2、判断题

I.在有序表的查询过程中，设