青岛科技大学数据结构与算法分析期末考试复习题及参考答案

青岛科技大学数据结构与算法分析复习题

卷面满分：100分考核方式：闭卷超越高度

一、选择题(共10小题,每小题2分，共20分)。

1、在长度为n的顺序表的第i(lWiWn+l)个位置上插入一个元素，移动元素

的个数为()。

A.i-1B.n-iC.iD.n-i+l

2、以下哪一个术语与数据的存储结构无关？()

A.栈B.哈希表C.线索树D.双向链表

3、下面程序段的时间复杂度为o

for(inti=0;i<m;i++)

for(intj=0;j<n;j++)

a[i][j]=i*j；

A.0(m")B.0(m*n)C.0(/)D.0(m+n)

4、下列陈述中正确的是()。

A.二叉树中最多只有两棵子树，并且有左右之分

B.二叉树中结点只有一个孩子时无左右之分

C.二叉树中必有度为2的结点

D.二叉树是度为2的有序树

5、n个顶点的连通图中至少含有()条边。

A.nB.n-1C.n(nT)/2D.n(n-1)

6、在一棵具有k层(k>=l)的满三叉树中，结点总数为()。

A.3kB.3-1C.(3-1)/3D.(3-1)/2

7、AVL树是一种平衡的二叉排序树，树中任一结点的()。

A.左、右子树高度差的绝对值不超过1B.左、右子树的高度均相同

C.左子树的高度均大于右子树的高度D.左子树的高度均小于右子树

的高度

8、若一个栈的输入序列为l,2,3,i,n,输出序列的第一个元素是i,则第j

个输出元素是()o

A.i-j-1B.不确定的C.j-i+1D.i-j

9、适用于折半查找的表的存储方式及元素排列要求为()。

A.链接方式存储，元素无序B.链接方式存储，元素有序

C.顺序方式存储，元素无序D.顺序方式存储，元素有序

10、设哈希表长为14,哈希函数是H(key)=key%ll,表中已有数据的关键字为

15,38,61,84共四个，现要将关键字为49的结点加到表中，用二次探测再

散列法解决冲突，则放入的位置是()。

A.9B.3C.5D.8

二、判断题(共10小题,每小题2分，共20分)。

1.数据元素是数据的基本单位。（）

2.算法的优劣与算法描述语言无关，但与所用计算机有关。（）

3.链表中的头结点仅起到标识作用。（）

4.集合与线性表的区别在于是否按关键字排序。（）

5.二叉排序树是一种动态查找树。（）

6.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出

型结构。（）

7.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）

8.图形结构的特点是一对多,树形结构的特点是多对多。（）

9.完全二叉树中，若一个结点没有左孩子，则它必是树叶。（）

10.在n个结点的无向图中，若边数大于nT,则该图必是连通图。（）

三、算法和应用题（共5小题,每小题12分,共60分）。

1、（12分）树与二叉树有什么区别？将下图树形结构转化为相应的二叉树，并

画出该树形结构的双亲表示法和孩子链表表示法的存储结构。

F

2、（12分）设哈希表的地址范围为0〜17,哈希函数为：H（key）=key机6。用

线性探测法处理冲突，输入关键字序列：（10,24,32,17,31,30,46,47,

40,63,49）,构造哈希表，试回答下列问题：

（1）若查找关键字63,需要依次与哪些关键字进行比较？

（2）若查找关键字60,需要依次与哪些关键字比较？

（3）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

3、（12分）对于以下关键字序列（52,49,80,36,14,58,61,97,23,75）

写出进行直接插入排序和归并排序的过程（写明步骤）。

4.（12分）写出创建一个的单链表的算法。

5.（12分）写出用按层次顺序遍历二叉树的方法，统计树中叶子结点数目的算

法。

数据结构与算法分析试题答案

一、选择题（共10小题,每小题2分，共20分）。

1-5：DABAB6-10：DABDA

二、判断题（共10小题,每小题2分，共20分）。

1-5VXXXV6-10XVXVX

三、算法和应用题（共5小题,每小题12分,共60分）。

1、（12分）

（1）二叉树的一个结点至多有两棵子树，树则不然。（2分）

（2）二叉树一个结点的子树有左右之分，树则没有此要求。（2分）

二叉树如下图：（4分）

存储结构（略）（4分）

2、（12分）

得到的哈希表为：（6分）

填入比较次数后的HT值

1012345678g

-Ke-_1401923_84275520

y11123412

M

查找成功时的平均长度为：ASL=(1+1+1+2+3+4+1+2)/8=1.875(6分)

3、(12分)

结果是(23,49,14,36,52,58,61,97,80,75),将步骤写明白。各6

分。

4、(12分)

voidCreateList_L(LinkList&.L,intn){//逆序输入n个数据元素，建

立带头结点的单奏表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一个带头结点的单链表

for(i=n;i>0;-i){

p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入

}

)

5、(12分)

intLevel(BiTree*bt)

{intnum=0;〃nuni统计度为1的结点的个数

if(bt){

Queuelnit(Q);Queuein(Q,bt)；〃Q是以二叉树结

点指针为元素的队列

while(!QueueEmpty(Q))

{p=QueueOut(Q);printf(p->data);〃出队，访问结点

if(p->lchild&&!p->