大连海事大学2019计算机考研,大连海事大学计算机考研——选择部分

题型判断(20*1)&＃43; 选择(10*2)&＃43;简答(含树和森林的转化&＃xff0c;时间复杂度&＃xff0c;二叉排序树&＃xff0c;平衡二叉树&＃xff0c;KMP&＃xff0c;Hash表&＃xff0c;程序输出)&＃43;证明(15*1) &＃43; 编程(15*1)

选择

Head Tail运算从一个表中&＃xff0c;用Head(H)&＃xff0c;Tail(T)分离出一个元素原则&＃xff1a;H操作提取第一个元素(原子或广义表)&＃xff1b;T操作去掉第一个元素(原子或广义表)&＃xff1b;写顺序是从后往前写例1&＃xff0c;L&＃61;((( (a,b), e &＃xff0c; ( (x), d) ))) 从中提取x初始&＃xff1a;((( (a,b), e &＃xff0c; ( (x), d) )))第一步&＃xff0c;HH(去两个括号)&＃xff1a;( (a,b), e &＃xff0c; ( (x), d) )第二步&＃xff0c;T(去掉首元素)&＃xff1a; ( e &＃xff0c; ( (x), d) )第三步&＃xff0c;T (去掉首元素)&＃xff1a; ( ( (x), d) )第四步&＃xff0c;H (提取首元素)&＃xff1a; ( (x), d)第五步&＃xff0c;H (提取首元素)&＃xff1a; (x)第六步&＃xff0c;H (提取首元素)&＃xff1a; x综上&＃xff0c;从表中提取X的步骤为&＃xff1a;HHHTTHH

2. 二维数组

二维数组&＃xff0c;列(行)序为主序顺序存储&＃xff0c;告诉一个点的地址&＃xff0c;

每个元素占几个存储单元&＃xff0c;求另一个点的地址。

分析&＃xff1a;这种的画图做就可以&＃xff0c;仔细些&＃xff0c;难度不大。

3. 单链表存储队列

不带头的单链表存储队列&＃xff0c;队头指向队头结点&＃xff0c;队尾指向队尾结点&＃xff0c;

在进行插入操作时&＃xff1a;只需修改队尾指针

分析&＃xff1a;链表是顺序存储&＃xff0c;插入只能在队尾插入&＃xff0c;因此只需要移动队尾指针

4.循环队列

循环队列是【0..m】&＃xff0c;则数组的长度是m&＃43;1&＃xff1b;

因为是队列&＃xff0c;所以进队从后面进&＃xff0c;移动rear指针&＃xff1b;出队从前面出&＃xff0c;移动front指针

5.折半查找

有序&＃xff0c;顺序表&＃xff0c;折半查找&＃xff0c; 27个元素&＃xff0c; 查找失败时&＃xff0c;至少需要与关键字比较的次数&＃xff1a;27

分析&＃xff1a;折半查找查找失败至少需要与关键字的比较次数&＃xff1a;log2(x)向下取整

6.m阶B树

1.非终端结点至多有m个指针&＃xff0c;m-1个关键字

至少有(m/2向上取整)个指针&＃xff0c;(m/2向上取整)-1 个关键字

2.根结点&＃xff0c;至少两个指针(分支)&＃xff0c;1个关键字

3.所有叶子节点都在同一层上&＃xff0c;且不带任何信息。

7.四维数组

例&＃xff1a;四维数组B【1..3&＃xff0c;2..8&＃xff0c;0..5&＃xff0c;1..8】以行主序 顺序存储&＃xff0c;每个元素占2个存储单元&＃xff0c;B【1,4,0,1】地址2000&＃xff0c;则B【2,3,4,5】地址&＃xff1f;

分析&＃xff1a;四维数组B【1..3&＃xff0c;2..8&＃xff0c;0..5&＃xff0c;1..8】(3,7,6,8)(3-1&＃43;1&＃xff0c;8-2&＃43;1&＃xff0c;5-0&＃43;1&＃xff0c;8-1&＃43;1)

2000&＃43;【(2-1)*7*6*8 &＃43; (3-4)*6*8 &＃43; (4-0)*8 &＃43; (5-1)】*2 &＃61; 2648

8.排序

1.冒泡排序&＃xff1a;逆序的情况下&＃xff0c;比较次数最多

2.比较次数

最好的情况&＃xff1a;直接插入排序: O(n)

冒泡&＃xff1a;O(n) //最好&＃xff0c;直接插&＃xff0c;冒的好&＃xff0c;即原数列有序

简单选择排序&＃xff1a;O(n) //与原始序列无关(折半插入同样无关)

快速&＃xff1a;O(n)

希尔: O(n)

归并: O【(log2(n)】

3.时间复杂度

平均情况&＃xff1a;快速&＃xff0c;希尔&＃xff0c;归并&＃xff0c;堆 (快些归队)&＃xff1a; O【nlog2(n)】

其他&＃xff1a; O(n)

最坏情况&＃xff1a;快速O(n)&＃xff0c;其他与平均相同

最好情况&＃xff1a;简单插入排序&＃xff1a;O(n)

4.空间复杂度

快速&＃xff1a; O【log2(n)】

归并&＃xff1a; O(n)&＃xff0c;

基数&＃xff1a; O(rd)&＃xff0c;

其余&＃xff1a; O(1)

5.辅助空间

堆排序 O(1)

直接选择排序O(1)

归并排序O(1)

快速排序O(log2n)

直接插入排序O(1)

5.每一趟都可以选出一个元素放到其最终位置上的是&＃xff1a;

交换类(冒泡&＃xff0c;快速)、选择类(简单选择&＃xff0c;堆)

6.&＃xff5b;50&＃xff0c;80&＃xff0c;30&＃xff0c;40&＃xff0c;70&＃xff0c;60}&＃xff0c;快速排序&＃xff0c;以第一个为基准&＃xff0c;一趟后的结果&＃xff1a;

快速排序

9. 查找

对长度为n的顺序表进行顺序查找时&＃xff0c;查找失败需要与键值的比较次数&＃xff1a;n&＃43;1

折半查找&＃xff0c;查找失败至少需要的比较次数&＃xff1a;log2(n)向下取整

10. 图

例1.G是有8个顶点的非连通简单无向图&＃xff0c;该图最多有( 21 )条边

分析&＃xff1a;全连通图 边 M 和 点N的关系满足&＃xff1a;M &＃61; N(N-1) /2

反过来看&＃xff0c;即问有()条边&＃xff0c;最少有8个点

M &＃61; (16-21) &＃xff0c; N ≥ 7 &＃xff1b;( 7对应的最大是21&＃xff0c;最小是6对应的&＃43;1&＃xff0c;15&＃43;1 &＃61; 16)

即当M有(16 -21)条边&＃xff0c;连通图最少有 7个顶点&＃xff0c; 非连通图最少有8个顶点

所以&＃xff0c;M最大为21

例2.G是一个非连通无向图&＃xff0c;共有(22-28)条边&＃xff0c;该图至少有( 9 )个顶点。

分析&＃xff1a;全连通图 边 M 和 点N的关系满足&＃xff1a;M &＃61; N(N-1) /2

当M &＃61; (22-28)&＃xff0c; N(N-1) /2 ≥(22-28)&＃xff0c;解得&＃xff1a;8≤N&＃xff1c;9&＃xff0c;即N &＃61; 8

因为非连通&＃xff0c;所以连通的加1&＃xff0c;即8&＃43;1 &＃61; 9

11. 循环队列

大小为6的数组实现循环队列&＃xff0c;front &＃61; 3 &＃xff0c;rear &＃61; 0&＃xff1b;删除一个&＃xff0c;进队三个&＃xff0c;

front &＃61; &＃xff1f; rear &＃61; &＃xff1f; (4 &＃xff0c; 3)

分析&＃xff1a;队列&＃xff0c;先进先出。删除在队头front&＃xff0c;进入在队尾rear。

12. 图

邻接矩阵 - 稠密图

邻接多重表- 无向图

十字链表 - 有向图

邻接表 - 稀疏图

补充&＃xff1a;

1. 一个堆又是一个完全二叉树

2.n个节点的huffman树&＃xff0c;有(n&＃43;1)/2个叶子节点。

3.在一颗深度为3的树中&＃xff0c;有2个度为3的节点&＃xff0c;1个度为2的节点&＃xff0c;度为0的节点为&＃xff1f;

分析&＃xff1a;此题中没有度为1的节点&＃xff0c;总分支数 &＃61; 总节点数 - 1&＃xff1b;

即 n0 &＃43; n2(1 )&＃43; n3(2) &＃61; (2*3 &＃43; 1*2) -1

解得&＃xff1a;n0 &＃61; 6&＃xff1b;

4. 65个节点的完全二叉树&＃xff0c;(根的层次号为1)的深度为&＃xff1a;7

分析&＃xff1a;1&＃43;2&＃43;4&＃43;8&＃43;16&＃43;32 &＃61; 63 6层最多63个节点&＃xff0c;7层最(64-127)

结语&＃xff1a;判断选择的先更新这些&＃xff0c;肯定还有漏掉的&＃xff0c;以后必定补充上。

明天开始更新答题的&＃xff0c;必然每日一更&＃xff0c;直到结束&＃xff01;&＃xff01;&＃xff01;

举报/反馈