数据结构A习题课

一、填空题

1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，即数据的逻辑结构、数据的

和数据的运算。2、若一个算法中的程序步为T(n)=10log2n+50n+10000，则算法的时间复杂度为

。3、顺序表相对于链表的优点有无需增加额外的存储空间和

。4、当线性表的长度变化较大，难以估计其存贮规模时，以采用

作为存贮结构为好。5、具有72个结点的完全二叉树的深度为

6、有n个叶子的哈夫曼树的结点总数为________。7、树中结点A有2005个兄弟，结点B是A的双亲，则结点B的度是________。8、已知一无向图G=(V,E)，其中V={a,b,c,d,e}，E={(a,b),(a,d),(a,c)(d,c),(b,e)}，现用某一种遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__________遍历方法。9、设有一组记录的关键字为{19,14,1,68,20,27,55,79}，用拉链法构造哈希表，哈希函数为h(key)=key%13，哈希地址为1的链中有________个记录。10、已知有序表为(16,18,28,35,47,52,62,88,90,118,256)，当用二分法查找90时，需经过________次查找成功。二、选择题

1、在单链表指针为p的节点之后插入指针为s的结点，正确的操作是（）A)p->link=s;s->link=p->link;B)s->link=p->link;p->link=s;C)p->link=s;p->link=s->link; D)p->link=s->link;p->link=s;2、具有n个顶点的有向完全图中，边的总数为（）条。A）n（n+1）B）n（n-1）C）n（n-1）/2D）n（n+1）/23、散列函数不是一对一的关系，因此选用好的（）方法是散列文件的关键。A）散列函数B）除余法中的质数C）冲突处理D）散列函数和冲突处理4、假设以行序为主序存储二维数组A[i][j]（1≤i≤100，1≤j≤100），设每个数据元素占2个存储单元，二维数组存储的起始地址为10，则Loc(A[5][5])=( )A)808 B)818C)1010 D)10205、深度为6（根的层次为1）的二叉树至多有（）个结点。A）64B）32C）31D）636、设一个栈输入序列是1、2、3、4、5，则下列序列中不可能是栈的输出序列是（）。A）32541B）15432C）14523D）231457、二叉树的前序遍历为EFHIGJK，中序遍历序列为HFIEJKG。该二叉树根结点的右子树的根是（ ）A)E B)FC)G D)H8、下面几个符号串编码集合中，不是前缀编码的是（）A){0,10,110,1111} B){11,10,001,101,0001}C){00,010,0110,1000D){b,c,aa,ac,aba,abb,abc}9、

m阶B-树中所有的非终端（除根外）结点中的关键字的个数必须大于或等于（

）。A）mB）m/2C）m/2+1D）m/2-1

C）

D）10、

下列四个序列中，哪一个是堆（）A)16,72,31,23,94,53 B)16,53,23,94,31,72C)16,31,23,94,53,72 D)16,94,23,31,53,72三、简答题

1.用一维数组存放的一棵完全二叉树如图1所示： 图1写出前序、中序、后序遍历该二叉树时访问结点的顺序。前序序列：中序序列：后序序列：2.将图2所示的两棵树组成的森林转换为二叉树。

D）

3.

以序列（72，87，61，23，94，16，05，58）为输入，从空的优先权队列开始，依次插入这些元素，求结果优先权队列的状态。

4、已知结点权值：4，2，5，7，5。画出相应哈夫曼树并计算带权路径长度WPL。哈夫曼树中结点用结点的权值表示.5、设数据集合d={1，12，5，8，3，10，7，13，9}，试完成下列各题：5、设数据集合d={1，12，5，8，3，10，7，13，9}，试完成下列各题：（1）依次取d中各数据，构造一棵二叉搜索树bt。（2）画出在二叉树bt中删除12后的树结构。

6、对图3的3阶B-树，依次执行下列操作，画出各步操作的结果。（1）插入90 ；（2）插入25；（3）插入45；（4）删除60；

7.已知下图所示的无向带权图：

（1）从结点2出发，用prim算法求其最小代价生成树，并画出过程示意图。（2）时间复杂度为多少？

8、下图的邻接表表示一个给定的无向图。

（1）给出从顶点v1开始，用深度优先搜索法进行遍历时的顶点序列；（2）给出从顶点v1开始，用广度优先搜索法进行遍历时的顶点序列。

算法填空下面是在非空单链表(n个结点)中第k个结点之后插入一个元素值为x的算法。(如果k等于0，则在第1个结点之前插入x)。

template<classT>boolSingleList<T>::Insert(intk,constT&x){if(

){cout<<"OutOfBounds";returnfalse;}

;for(inti=1;i<k;i++)p=p->link;

;q->data=x;if(k){

；p->link=q;}else{q->link=first；first=q;}

;returntrue;}下面是二叉搜索树的搜索算法。

template<classE,classK>boolBSTree<E,K>::Search(constK&k,E&e)const{BTNode<E>*p=root;while(p){if(

)p=p->lchild;elseif(k>p->element)

;else{e=p->element;returntrue;}}returnfalse;}程序阅读题

类BinaryTree是指用二叉链表来存储二叉树，root表示其根结点，有程序如下：template<classT>intBinaryTree<T>::H()//定义为二叉树类的公有函数{ returnH(root);}template<classT>intBinaryTree<T>::H(BTNode<T>*t)//定义为二叉树类的私有函数{inthl,hr

; if(!t)return0;hl=H(t->lChild)

;hr=H(t->rChild)

;returnhl>hr?hl+1:hr+1;}问题：1）以上程序实现了二叉树类的什么