数据结构与算法

数据结构与算法辅导填空题栈和队列都是线性结构，栈只能在栈顶位置插入和删除元素，队只能在队首位置插入和队尾位置删除元素。
设有一顺序栈S，元素a1,a2,a3,a4,a5,a6依次进栈，如果6个元素出栈的顺序是a2,a3,a4,a6,a5,a1,则栈的容量至少应该是3。
Prim算法和Kruskal算法是求无向图的最小（填最小/最大）生成树算法。
若原始记录基本有序，在选择排序，插入排序，快速排序中，应选用插入排序较好。
如果树的某一结点A有3个兄弟，而且B结点是A的双亲，则B的度是4。
一棵二叉树的层次数为5，则第5层上最多有16节点。
根结点为第一层，则深度为K的完全二叉树至少有2K-1个结点，至多有2K-1个节点。
n个顶点的无向完全图具有n(n-1)/2条边，n个顶点的有向完全图具有n(n-1)条弧。
设有一数据包从路由器R1经过链路欲到达路由器R7，现在为了转发的最短路径应使用迪杰斯特拉算法数据结构中评价算法的两个重要指标是时间复杂度和空间复杂度_。
深度为6的二叉树（深度从0开始），至多有127个结点，至少有7个结点。
在直接插入排序、选择排序、冒泡排序中，快速排序，排序不稳定的是快速排序。
在双链表中，每个结点有两个指针域，一个指向_前驱_，另一个指向后继。
栈中存取数据的原则先进后出，列队中存取数据的原则先进先出。
线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
向栈中推入元素的操作是压栈。
数据结构中的抽象数据类型在现在的程序设计语言中体现为数据与操作两部分。
快速排序是不稳定排序算法。
在排序表（8,11,15,19,25,26,30,33,42,48,50）中用二分（折半）法查找关键码值20，需做的关键码比较次数为4。设一组初始记录关键字序列为(45，80，48，40，22，78），按以下要求从小到大进行排序。
1、给出前3趟每趟简单选择排序的结果。
2、给出前2趟每趟直接插入排序后结果。
3、以第一个数作为基准给出第一趟快速排序后结果。

已知关键字序列R={11,4,3,2,17,30,19}，请构造一棵哈夫曼树，并计算出它的带权路径长度WPL。设有关键码序列{23,38,43,18,33,28,41}，按关键码的先后顺序构造一棵二叉排序树。
请写出下列的二叉树的先序遍历序列，中序遍历序列，后序遍历序列。


有5个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素Ｂ为第一个出栈，D第二个出栈的次序有哪几种并写出每一种的结果。ＡＢＣＤＥＦ有一棵树如图所示，回答下面的问题：
1）这棵树的根结点是____；
2）这棵树的叶子结点是____；
3）结点k3的度是____；
4）这棵树的度是____；
5）这棵树的深度是____；
6）结点k3的子女是___；
7）结点k3的父结点是__；
对顺序存储的元素进行冒泡排序，已知元素的关键字集合为{57,36,89,43,55,67,2,15}，请按照从小到大的顺序写出每一趟排序后关键字的排序序列，仅给出经过冒泡排序后整个集合的有序序列不得分。k1kkkkkk243567在地址空间为0~16的散列区中，对以下关键字序列构造一个散列表：{24,11,53,12,61,27,74,39,63,18,46}散列函数为：H(key）=keyMOD13,散列表长为m=16，用线性探测法处理冲突，即Hi=(H(key）+i）MODm（i=1,2,…m-1）
并计算平均查找长度ＡＳＬ。



将下列计算过程补充完整
H(24）=11
H(11）=11，H1=(11+1）MOD16=12


ASL=01234567891011121314152411画出右图的最小生成树即最小支撑树（只需画出结果）。




假设通信电文使用的字符集为{a,b,c,d,e,f,g}，这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，请画出此霍夫曼树，对字符集中的字符进行编码，及求出带权路径长度。写出该数的前、中、后序遍历的结果。






设有一个关键字的序列是{46,25,78,62,12,80}
（1）试画出生成的二叉排序树。
（2）如果上述的关键字是按照从小到大的顺序排序好的，请用二分法查找关键字25。ABFECDGHJI将下列给定的图：
（1）用邻接矩阵法存储。
（2）并将其简化为最小的生成树，要求从顶点1出发。12537468356101221597Typestructnode
{
Elemtypedata;
stuctnodenext;
}Node,pnode,linklist;
设有一个带头结点的单链表L，试编写插入函数intlistInsert（linkListH，inti，Elemtypeelem）。
解答：
intlistinsert(linklistlist,intI,elemtypeelem)
{
linklistp;
intj=0;
p=list;
while(p&&j{
p=p->next;
j++;
}
If(!p||j>i-1)
{return0;}
s=(pnode)malloc(sizeof(node));
S->data=(creatnode(elem));
S->next=p->next;
P->next=s;
Return1;
}