数据结构导论2016年10月真题及答案解析（02142）

若采用二路归并排序方法对关键字序列{25，9，78，6，65，15，58，18，45，20}进行升序排序，写出其每趟排序结束后的关键字序列。

写出向存储结构为邻接矩阵的无向图G中插入一条边(x,y)的算法。算法的头函数为：void AddEdgetoGraph(Graph*G, VertexType X, VertexType y>，无向图G的存储结构为：

#define MaxVertex num

typedef char VertexType;

typedef int EdgeType;

typedef struct graph{

  int n, e;    //图的实际顶点数和边数

  EdgeType edge[MaxVertex][MaxVertex];

  VertexType vertex[MaxVertex];   //顶点表

}Graph;

某电商有关手机的库存信息，按其价格从低到高存储在一个带有头结点的单循环链表中，链表中的结点由品牌型号(nametype)、价格(price)、数量(quantity)和指针(next)四个域组成。现新到in台、价格为c、品牌型号为x的新款手机需入库，写出相应的存储结构和实现该要求的算法。

先序遍历、中序遍历一个森林分别等同于先序、中序遍历该森林所对应的二叉树。现已知一个森林的先序序列和中序序列分别为ABCDEFIGJH和BDCAIFJGHE，试画出该森林。

设有一组关键字值序列{e，b，d，f，a，g，C}现要求：(1)根据二叉排序树的创建方法构造出相应的二叉排序树(关键字值的大小按字母表顺序计);(2)计算等概率情况下在该二叉排序树上查找成功的平均查找长度ASL。

为便于表示二叉树的某些基本运算，则深度为k.的二叉树的顺序存储结构中的数组的大小为多少?画出如题30图所示的二叉树的顺序存储结构示意图，并说明对一般形态的二叉树不太适合使用顺序存储结构来表示的原因。

借助于队列能够将含有n个数据元素的栈逆置，比如栈S中的元素为{a，b，C}逆置后变成{C，b，a}。试简述你的解决方案。

对长度为n的有序顺序表进行二分查找，则查找表中的任意一个元素时，无论查找成功与失败，最多与表中______个元素进行比较。

一般情况下，时闯复杂度是O(nlog₂n)且其空间复杂度最优的排序方法是______。

排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素按序进行比较，将其插入已排序序列的正确位置上的方法称为______。

设有散列函数H(k)和键值k₁、k₂(k₁≠k₂)，若H(k₁)=H (k₂)，则这种现象称为“冲突”，且称键值k₁和k₂互为______。

一个图的最小生成树是满足一定条件的生成树，即一个图的最小生成树是指该图的所有生成树中______的生成树。

设一个完全二叉树共含有196个结点，则该完全二叉树中含有叶结点的个数是________。

假设高度为h二叉树中只有度为2和度为0这两种类型的结点，则该类二叉树中结点个数至多为2^h-1、至少为________。

若以数据集{34，5，12，23，8，18}为叶结点的权值构造一棵哈夫曼(HUffman)树，那么该Huffman树的带权路径长度WPL______。

设以数组Q[m]存放循环队列的元素，变量rear和queuelen分别表示循环队列中队尾元素的下标位置和元素的个数。则计算该队列中队头元素下标位置的公式是________。

二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则每个数组元素占用的存储单元的个数是________。

在表长为n的顺序表中插入或删除一个元素，则需移动元素的具体个数与表长和____有关。

非空的单循环链表的头指针为head，尾指针为rear，则rear->next=_______。

满足最小堆定义的是(　　)

设有两个长度分别为m、n的降序有序序列{a₁，a₂，…，a_m}、{b₁，b₂，…，b_n}，采用二路归并方法将它们合并成长度为m+12的降序有序序列，则归并过程中元素比较次数最少的条件一定是(　　)

从宏观上看，数据、数据元素和______ 反映了数据组织的三个层次。

已知散列表的存储空间为T[0，…，16]，散列函数为H(k)=k mod 17，用二次探测法解决冲突。散列表中已插入下列关键字：T[5]=39、T[6]=57和T[7]=7，则下一个关键字值23在该散列表中插入的位置是(　　)

对关键字序列{eSC，tab，ah，con，brk，del}进行排序时，若关键字序列的变化情况如下;①esc，tab，ah，con，brk，del ②ah，tab，eSC，con，brk，del ③alt，brk，esc，con，tab，del ④alt，brk，con，esc，tab，del ⑤ah，brk，con，del，tab，esc ⑥ah，brk，con，del，esc，tab。则所用的排序方法是(　　)

无向图的邻接矩阵一定是(　　)

根据连通图的深度优先搜索的基本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是(　　)

用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进行查找，现假设查找其中每个数据元素的概率不相等，那么(　　)

若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是(　　)

任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是(　　)

栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是(　　)

在实现队列的链表结构中，其时间复杂度最优的是(　　)

若线性表采用链式存储结构，则适用的查找方法为(　　)

已知指针p和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述单链表应执行的语句为(　　)

已知问题规模为n，则下列程序片段的时间复杂度是(　　)

i=1; j=0;

while(i+j<=n) i="">j) j++; else i++; }

若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是(　　)