数据结构与算法的习题

发布 2021-05-02 17:27:28 阅读 8998

1.计算机识别、存储和加工处理的对象被统称为( )

a.数据b.数据元素。

c.数据结构d.数据类型。

2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( )

3.队和栈的主要区别是( )

a.逻辑结构不同b.存储结构不同。

c.所包含的运算个数不同d.限定插入和删除的位置不同。

4.链栈与顺序栈相比,比较明显的优点是( )

a.插入操作更加方便b.删除操作更加方便。

c.不会出现下溢的情况d.不会出现上溢的情况。

5.下列说法中正确的是()

a. 二叉树中任何一个结点的度都为2

b. 二叉树的度为2

c. 任何一棵二叉树中至少有一个结点的度为2

d. 一棵二叉树的度可以小于2

6.在一非空二叉树的中序遍历序列中,根结点的右边()

a. 只有右子树上的所有结点。

b. 只有右子树上的部分结点。

c. 只有左子树上的所有结点。

d. 只有左子树上的部分结点。

7.在一个具有n个顶点的无向完全图中,包含的边的总数是()

a. n(n-1)/2

b. n(n-1)

c. n(n+1)

d. n(n+1)/2

8.下面的程序在执行时,s语句共执行的()次。

i=1;while (i<=n)

for(j=i;j', altimg': w': 22', h': 21'}]

9.设二叉树有n个结点,则其深度为()

a. n-1 b. nc. 5log2n+1 d. 不确定。

10.已知一棵二叉树结点的先根序列为abdgcfk,中根序列为dgbafck,则结点的后根序列为()

a. acfkbdg b. gdbfkca c. kcfagdb d. abcdfkg

11.任何一个带权的无向连通图的最小生成树()

a.只有一棵 b.有一棵或多棵 c.一定有多棵 d.可能不存在。

12.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,则它的前序遍历序列是()

a. acbedb. decabc. deabcd. cedba

13.设深度为k的二叉树上只有度为0和度为2的结点,则这类二叉树上所含结点总数量是(c)个。

a. k+1b. 2kc. 2k-1d. 2k+1

14.下面程序的时间复杂性是()

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

a[i][j]=i*j;

a. o(['altimg': w':

27', h': 21b. o(['altimg':

w': 22', h': 21c.

o(m*nd. o(m+n)

15.含n个顶点的连通图中的任意一条简单路径,其长度不可能超过()

a. 1b. n/2c. n-1d. n

16. 下列说法正确的是(a)

a.树的先根遍历序列与其对应的二叉树的先根遍历序列相同。

b.树的先根遍历序列与其对应的二叉树的后根遍历序列相同。

c.树的后根遍历序列与其对应的二叉树的先根遍历序列相同。

d.树的后根遍历序列与其对应的二叉树的后根遍历序列相同。

17.对于一个具有n个结点和e条边的无向图,若采用邻接表示,则表头向量的大小是(a)

a. nb. n+1c. n-ed. n-1

18.判断一个有向图是否存在回路,除了可以利用拓扑排序方法,还可以利用()

a.求关键路径的方法。

b.求最短路径的dijkstra方法。

c.广度优先遍历方法。

d. 深度优先遍历方法。

19.一个队列的输入序列是1,2,3,4,则队列的输出序列是()

a,4,3,2,1 b.1,2,3,4 c.1,4,3,2 d.3,2,4,1

20.任何一个带权的无向连通图的最小生成树(b)

a.只有一棵 b.有一棵或多棵 c.一定有多棵 d.可能不存在。

1)**性表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。

2)顺序表中逻辑上相邻的元素的物理位置紧邻,单链表中逻辑上相邻的元素物理位置紧邻。

3)在单链表中,除了首元结点外,任意结点的存储位置由指示。

4)记录的结构是数据在物理存储器上的存储方式。

5)在非空队列中,头指针始终指向 ,而尾指针始终指向 。

6)n个顶点的连通图,至少有条边。

7)对于一个长度为n的线性表,假设表中各结点的查找概率相同,则在查找成功的情况下,平均查找长度为 ,如果k不在表中,则需要进行次比较后才能确定查找失败。

8)在二叉排序树中,其左子树中任何一个结点的关键字一定其右子树的各结点的关键字。

9)已知无向图g的结点数为n,边数为e,其邻接表表示中的表结点数与表头结点数之和为 。

10)若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点,则它必是孩子树的后序遍历序中的个结点。

11)有m个叶子结点(又称外结点)的哈夫曼树,其结点总数是。

12)如果一个图中有n条边,则此图的生成树含有条边,所以生成树是图的边数最少的连通图。

13)由权值为1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树,则带权的路径的长度为 。

14)在顺序队列中,应该有队头和队尾两个指针来指示,队头指针和队尾指针的初值在队列的初始化时均应该设置为 ,当对队列进行插入和删除的操作后,如果头指针和尾指针相等时,队列为 。

15)树有三种常用的存储结构,即孩子链表法、孩子兄弟链表法和 。

16)无向图的邻接矩阵是的,并且主对角线上的元素的值为 。

17)在结点数目相同的二叉树中, 的路径长度最短。

18)栈和队列均可视为特殊的线性表,所不同的在于对这二种特殊线性表和运算的限定不一样。

16.当问题的规模n趋向无穷大时,算法执行时间t(n)的数量级被称为算法的___时间复杂度___

17.下面程序段的时间复杂度为。

sum=1;

for(i=0;sumsum+=1;

18.已知链表结点定义如下:

typedef struct node构造的哈夫曼(huffman)树的带权路径长度是。

22.若无向图g中有n个顶点m条边,采用邻接矩阵存储,则该矩阵中非0元素的个数为。

23.影响排序效率的两个因素是关键字的次数和记录的移动次数。

24.对任一m阶的b树,每个结点中最多包含个关键字。

25.在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作___

26.已知链栈的结点结构为栈顶指针为top,则实现将指针p所指结点插入栈顶的语句依次为___和___

27.空串的长度是___空格串的长度是___

28.在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是___

1)栈:。2)树:。

3)森林:。

4)满二叉树:。

5)数据:。

6)数据对象:。

7)数据结构:。

8)算法:

1)简述算法的五个重要特性。

2)算法设计的基本要求。

3)试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。

4)简述二叉树的特点。

5)已知一棵度为k的树中有[',altimg': w': 22', h':

23'}]个度为1的结点,['altimg': w': 22', h':

23'}]个度为2的结点,。。altimg': w':

23', h': 23'}]个度为k的结点,问该树中有多少个叶子节点?

7)写出下列树的先根序列和后根序列。

8)已知如图所示的有向图,请给出该图的:

1) 每个顶点的入/出度。

2) 邻接矩阵。

答案:1)简述以下算法的功能:

status a (linkedlist l)

数据结构与算法的习题

构造的哈夫曼 huffman 树的带权路径长度是 33 22.若无向图g中有n个顶点m条边,采用邻接矩阵存储,则该矩阵中非0元素的个数为 2 m 23.影响排序效率的两个因素是关键字的 比较 次数和记录的移动次数。24.对任一m阶的b树,每个结点中最多包含 m 1 个关键字。25.在链表的结点中,数...

算法与数据结构习题

一 单项选择题。1 算法的时间复杂度的表示方法是 a 实现算法的程序在指定机器上执行的时间。b 标准程序在机器上的执行时间。c 基本操作重复次数,即问题规模n的某个函数。d 与刻画基本操作重复次数的函数同阶无穷大的函数f n 2 在一个双向链表中,假设结点的域分别为left,right,以及data...

算法与数据结构习题

6 页共 8 页。一 单项选择题。1.在数组a8 10中,行列下标从0开始,每一个数组元素占用3个字节存储,所有数据元素相继存放在一个地址连续的存储空间中,则存放该数组至少需要的字节数是 a 6 页共 8 页。算法与数据结构 习题2 一 单项选择题。1.在数组a8 10中,行列下标从0开始,每一个数...