www.kdzikao.com
栈顶和栈底 难易程度 一般
21.为节省存储空间，将矩阵中多个值相同的元素只分配一个存储空间，零元素不存储，这种存储方式通常称为矩阵的____。 正确答案 压缩存储 知识点名称
用一维数组存储特殊矩阵的压缩存储方法 难易程度 简单
22.100个结点的二叉树采用二叉链表存储时，空指针域NULL有____个。 正确答案 101 知识点名称 二叉树的基本运算 难易程度 一般
23.已知完全二叉树的第五层有5个结点，则整个完全二叉树有____个叶结点。 正确答案 10 知识点名称 二叉树的性质 难易程度 一般
24.一个树的最少结点个数为____。 正确答案 0
www.kdzikao.com
知识点名称 树的基本概念 难易程度 简单
25.索引顺序表由两部分组成：一个是顺序表，另一个是____。 正确答案 索引表 知识点名称 索引顺序表 难易程度 简单
26.二叉排序树上的平均查找长度等价于____和O(n)之间。 正确答案 $$$\\[
{\\rm{O}}\\left( {\\log _2 n} \\right) \\] ### 知识点名称
二叉排序树的平均查找长度 难易程度 一般
27.二分查找算法的复杂度是____。 正确答案 $$$\\[
{\\rm{O}}\\left( {\\log _2 n} \\right) \\]### 知识点名称 二分查找算法 难易程度 一般
www.kdzikao.com
28.最好情况下，冒泡排序法的时间复杂度为____，它是一种稳定的排序方法。 正确答案 O(n) 知识点名称
冒泡排序的基本步骤和算法 难易程度 一般 三 应用
29.如图所示，在栈的输入端元素的输入顺序为A,5，8,试写出出栈的输出端可以得到的以数字开头的所有序列，并写出进栈，出栈的操作过程(用push(x)表示x进栈，pop(x)表示x出栈) 题
干
附
图:http://img.kdzikao.com/exercise/image/87a8ff0b518772e5cb7f6f7aa477306d.png 正确答案
5A8 push(A);push(5);pop(5);pop(A);push(8);pop(8) 58A push(A);push(5);pop(5);push(8);pop(8);pop(A) 85A push(A);push(5);push(8);pop(8);pop(5);pop(A) 知识点名称 栈的后进先出特征 难易程度 一般
30.分别写出如图所示的二叉树的先序遍历、中序遍历、后序遍历的结点序列。 题
干
附
图:http://img.kdzikao.com/exercise/image/616860d7a9d01c121b59d3bbc559c7b0.png 正确答案
先序遍历序列：ABCEDFGKH;中序遍历序列:ECBDAGKFH;后先序遍历序列:ECDBKGHFA 知识点名称
给出二叉树先序序列、中序序列和后序序列 难易程度 一般
www.kdzikao.com
31.写出如图所示的顶点的所有拓扑排序序列。 题
干
附
图:http://img.kdzikao.com/exercise/image/3051c215542719f2964bc14d179d0c15.png 正确答案
ABCEDF;ABCDEF;ABDCEF;BACEDF;BACDEF;BADCEF 知识点名称 拓扑排序 难易程度 一般
32.将图转换为二叉树。 题
干
附
图:http://img.kdzikao.com/exercise/image/253c94b05f0d21bfaa8c59abc8f4f71a.png 正确答案 图如文本讲解所示 知识点名称
图的存储结构;图的深度优先搜索算法 难易程度 困难
33.判断序列(28,75,33,68,25,56,47,99,86,36)是否为堆？如果不是，则把它调整为堆（最小堆）。 正确答案 图如文本讲解所示 知识点名称 堆 难易程度 一般
四 算法设计
34.单链表的结构定义如下：typedef struct node
www.kdzikao.com
{
int data;
struct node *next;
}Node,*LinkList;试写出算法int CountLinklist(LinkList head,int x)实现在带头结点的单链表head中计算值为x的结点数。 正确答案
int CountLinklist(LinkList head,int x) { }
知识点名称 求表长 难易程度 一般
35.假设线性表中结点是按键值递增的顺序排列，试编写一个顺序查找算法，将岗哨设在高下标端，并说明等概率情况下查找成功和不成功时的平均查找长度。 正确答案
int Search_sqtable(Sqtable R,KeyType k) { }
该方法等概率情况下查找成功和不成功时的平均查找长度都为O(n)
int i=0;
R.elem[R.n].key=k; while(R.elem[i].key i++; Node *p=head; int cnt=0; while(p->next!=NULL) { } return(cnt); p=p->next; if(p->data==x)cnt++; if(R.elem[i].key>k||i==R.n)return -1; else return i; www.kdzikao.com 知识点名称 顺序查找算法 难易程度 一般 2016最新整理-口袋自考APP出品