软件设计师——数据结构练习

目录

一、单选题

二、填空题

四、计算题

1.给出下图该树对应的”双亲表示法“的存储结构。

2.给出下图该树对应的“孩子表示法”的存储结构。

3.给出下图二叉树的先序遍历、中序遍历和后序遍历的结果。

4.一个树有6个结点及其对应的权值分别为：a:45，b:13，c:12，d:16，e:9，f:5，求该树的带权路径长度，并画出构造的哈夫曼树及其哈夫曼编码。

5.请给出下图A1无向图和A2有向图对应的“邻接矩阵表示法”的存储结构。 

6.请给出下图无向图对应的“邻接链表表示法”的存储结构。

7.给出下图树对应的深度优先遍历和广度优先遍历的结果。 

8.利用Prim算法给出下图的最小生成树。

9.现在要对序列：4，5，6，3，2，1，进行排序，请给出冒泡排序的过程。

10.当前序列{10,18,4,3,6,12,1,9,15,8 }，增量设置为5,3,1，请给出希尔排序的过程。

11.快速排序：

12.基数排序：

---

一、单选题

1.串是任意有限个（）。

A、符号构成的有限序列

B、符号构成的有限集合

C、字符构成的有限序列

D、字符构成的有限集合

正确答案：C

2.如果以链表作为栈的存储结果，则出栈操作时（）。

A、必须判别栈是否为满

B、对栈不作任何判别

C、必须判别栈是否为空

D、判别栈元素的类型

正确答案：C

3.深度为6(根的层次为1)的二叉树至多有（ ）个结点。

A、64

B、32

C、31

D、63

正确答案：D

4.使用双向链表存储数据，其优点是可以（ ）。

A、提高检索速度

B、很方便地插入和删除数据

C、节约存储空间

D、很快回收存储空间

正确答案：A

5.下列属于简单排序的是（）。

A、堆排序

B、希尔排序

C、快速排序

D、冒泡排序

正确答案：D

6.下列不属于排序算法好坏的衡量标准的是（）。

A、时间复杂度

B、算法稳定性

C、空间复杂度

D、算法复杂性

正确答案：D

7.栈和队列的共同特点是(      )。

A、只允许在端点处插入和删除元素

B、都是先进先出

C、都是先进后出

D、没有共同点

正确答案：A

8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（      ）

A、O（1）

B、O（n）

C、 O（log2n）  

D、O（n*n）

正确答案：C

9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）= K %9作为散列函数，则散列地址为1的元素有（   ）个。

A、1

B、2

C、3

D、4

正确答案：D

10.设有6个结点的无向图，该图至少应有(      )条边才能确保是一个连通图。

A、5

B、6

C、7

D、8

正确答案：A

11.数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为()

A、存储结构

B、逻辑结构

C、顺序存储结构

D、链式存储结构

正确答案：C

12.线性表若采用链式存储结构时，要求内存中可用存储单元的地址:( )

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续或不连续都可以

正确答案：D

二、填空题

1.一个算法的时间复杂度为(

+ log2n+14n)/ ，其数量级表示为________。

正确答案：

O(n)

2.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。

正确答案：

第一空： 

n(n-1)/2 

第二空： 

n(n-1)

3.在快速排序、堆排序、归并排序中，_________排序是稳定的。

正确答案：

归并

4向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动 ______ 个元素。

正确答案：

n-i+1

三、判断题（共18题,36.0分）

1.在线性表中，每一个元素只能有一个直接前驱，但可以有多个直接后继。

正确答案： ×

2.在顺序存储中，插入和删除操作需要移动大量元素。

正确答案： √

3.链式存储的结点空间需要事先分配。

正确答案： ×

4.在队列中，允许插入元素的一端称为队头，允许删除元素的一端称为队尾。

正确答案： ×

5.空串是空格串的子串，它的长度为0。

正确答案： √

6.一个稀疏矩阵可由表示非0元素的三元组及其行、列数唯一确定。

正确答案： √

7单个字符是字符串，单个表不是广义表。

正确答案： ×

8.广义表可以是递归表，其表中的元素可以是它本身。

正确答案： √

9.结点的度为1，则称这个结点为叶子结点。

正确答案： ×

10.树的后根遍历是先访问根结点，再依次后根遍历树的各颗子树

正确答案： ×

11.二叉树的中序遍历，是按照左子树->右子树->根节点的顺序访问。

正确答案： ×

12.一个完全图的顶点数是n个，则它具有(n*n)/2条边。

正确答案： ×

13一个图只有唯一的一个生成树。

正确答案： ×

14.如果在一棵生成树上添加一条边，必定构成环。

正确答案： √

15.折半查找属于静态查找的一种方法。

正确答案： √

16.平衡二叉树的左右两个子树的高度差的绝对值可以超过1。

正确答案： ×

17.哈希冲突是指不同key值产生相同的地址。

正确答案： √

18.具有12个结点的完全二叉树有5个度为2的结点。

正确答案： √

四、计算题

1.给出下图该树对应的”双亲表示法“的存储结构。

正确答案：

2.给出下图该树对应的“孩子表示法”的存储结构。

正确答案： 

 

3.给出下图二叉树的先序遍历、中序遍历和后序遍历的结果。

 

正确答案：

先(根)序遍历（根左右）：A B D H E I C F J K G

中(根)序遍历（左根右） : D H B E I A J F K C G

后(根)序遍历（左右根） : H D I E B J K F G C A

4.一个树有6个结点及其对应的权值分别为：a:45，b:13，c:12，d:16，e:9，f:5，求该树的带权路径长度，并画出构造的哈夫曼树及其哈夫曼编码。

正确答案：

WPL = 1×45+3x(13+12+16)+4x(5+9)=224

5.请给出下图A1无向图和A2有向图对应的“邻接矩阵表示法”的存储结构。 

正确答案：

6.请给出下图无向图对应的“邻接链表表示法”的存储结构。

正确答案：

7.给出下图树对应的深度优先遍历和广度优先遍历的结果。 

 

正确答案：

深度优先遍历：a->b->d->h->e->c->f->g->i

广度优先遍历：a->b->c->d->e->f->g->h->i

8.利用Prim算法给出下图的最小生成树。

 正确答案：

9.现在要对序列：4，5，6，3，2，1，进行排序，请给出冒泡排序的过程。

正确答案：

10.当前序列{10,18,4,3,6,12,1,9,15,8 }，增量设置为5,3,1，请给出希尔排序的过程。

正确答案：

d=5 后 {10,1,4,3,6,12,18,9,15,8 }

d=3 后 {3,1,4,8,6,12,10,9,15,18 }

d=1后 {1,3,4,6,8, 9 ,10,12,15,18 }

11.快速排序：

 

12.基数排序：

正确答案： 

文章知识点与官方知识档案匹配，可进一步学习相关知识算法技能树首页概览33963 人正在系统学习中

来源：一条小橘猫