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

一单选题（共38题，总分值76）

1.以下说法正确的是（D）

A.数据元素是数据的最小单位

B,数据项是数据的基本单位

C.数据结构是带有结构的各数据项的集合

D.一些表面上很不相同的数据可以有相同的逻辑结构

2.n个顶点的连通图用邻接距阵表示时，该距阵至少

有（B）个非零元素

A.n

B.2（n-l）

C.n/2

D.nA2

3.下面（D）方法可以判断出一个有向图是否有

环。

A.深度优先遍历

B.求关键路径

C.求最短路径

D.拓扑排序

4.在一个有127个元素的顺序表中插入一个新元素并

保持原来顺序不变，平均要移动的元素个数为

B)

A.8

B.63.5

C.63.7

5.在长度为n的顺序表的第i（lWiWn+l）个位置上插

入一个元素，移动元素的个数为（D）

A.i-1

B.n-i

C.i

D.n-i+1

6.n（n〉=2）个权值均不相同的字符构成哈夫曼树，关于

该树的叙述中，错误的是（）

A.该树一定是一颗完全二叉树

B.树中一定没有度为1的结点

C.树中两个权值最小的结点一定是兄弟结点

D.树中任一非叶结点的权值一定不小于下一层任一结

点的权值

7.设哈希表长为14,哈希函数是H（key）=key机1,表中

已有数据的关键字为15,38,61,84共四个，现

要将关键字为49的结点加到表中，用二次探测再

散列法解决冲突，则放入的位置是（A）

A.9

B.3

C.5

D.8

8.若让元素1,2,3,4,5依次进栈，则出栈次序不

可能出现在（B）种情况

A.5,4,3,2,1

B.4,3,1,2,5

C.2,1,5,4,3

D.2,3,5,4,1

9.某二叉树的前序序列和后序序列正好相反，则该二

叉树一定是（C）的二叉树。

A.空或只有一个结点

B.任一结点无左子树

C.高度等于其结点数

D.任一结点无右子树

10.一个递归算法必须包括（B）

A.递归部分

B.终止条件和递归部分

C.迭代部分

D.终止条件和迭代部分

11.下列（A）数据结构是操作受限的线性表。

A.队列

B.数组

C.线索二叉树

D.集合

12.以下与数据的存储结构无关的术语是（C）

A.顺序队列

B.链表

C.有序表

D.链栈

13.对于一棵具有n个结点的树，分支个数为

（I））

A.n

B.不确定

C.n+1

D.n-1

14.若一个栈的输入序列为1,2,3,…,n,输出序列的

第一个元素是i,则第j个输出元素是（B）

A.i-j-1

B.不确定的

C.j-i+1

D.i-j

15.下面程序段的时间复杂度为（B）

for（inti=0;i<m;i++）

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

a[i][j]=i*j;

A.0(m2)

B.O(m*n)

C.0(n2)

D.O(m+n)

16.单链表的存储密度(C)

A.大于1

B.等于1

C.小于1

D,不能确定

17.在数据结构中，从逻辑上可以把数据结构分成

(C)

A.动态结构和静态结构

B.紧凑结构和非紧凑结构

C.线性结构和非线性结构

D,内部结构和外部结构

18.算法的时间复杂度取决于(D)

A.问题的规模

B.待处理数据的初态

C.计算机的配置

D.A和B

19.以下哪一个术语与数据的存储结构无关？

(A)

A.栈

B.哈希表

C.线索树

D.双向链表

20.一个向量第一个元素的存储地址是100,每个元素

的长度为2,则第5个元素的地址是(B)

A.110

B.108

C.100

D.120

21.若某线性表最常用的操作是存取任意指定序号的元

素和在最后进行插入和删除运算，则利用

(B)存储方式最节省时间。

A.双链表

B.顺序表

C.带头结点的双循环链表

D.单循环链表

22.通常要求同一逻辑结构中的所有数据元素具有相同

的特性，这意味着(B)

A.数据具有同一特点

B.不仅数据元素所包含的数据项的个数要相同，而且

对应数据项的类型要一致

C.每个数据元素都一样

D.数据元素所包含的数据项的个数要相等

23.以下陈述错误的是（D）

A.求表长、定位这两种运算在采用顺序存储结构时实

现的效率不比采用链式存储结构时实现的效率低

B.顺序存储的线性表可以随机存取

C.由于顺序存储要求连续的存储区域，所以在存储管

理上不够灵活

D.线性表的链式存储结构优于顺序存储结构

24.数据结构的存储结构可以分为（D）类。

A.初等结构、构造型结构

B.顺序结构、链式结构

C.动态结构、静态结构

D.线性结构、树形结构、图形结构、集合

25.以下数据结构中，（A）是非线性数据结

构。

A.树

B.字符串

C.对列

D.栈

26.算法是指(A)

A.解决问题的有限运算序列

B.解决问题的计算方法

C.计算机程序

D.排序算法

27.适用于折半查找的表的存储方式及元素排列要求为

(D)

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

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

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

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

28.设栈S和队列Q的初始状态为空，元素el、e2、

e3、e4、e5和e6依次进入栈S,一个元素出栈后

即进入Q，若6个元素出队的序列是e2、e4、e3、

e6、e5和el,则栈S的容量至少应该是

(D)

A.2

B.6

C.4

D.3

29.线性表L=(al,a2,……an),下列说法正确的是

D)

A.每个元素都有一个直接前驱和一个直接后继

B.线性表中至少有一个元素

C.表中诸元素的排列必须是由小到大或由大到小

D.除第一个和最后一个元素外，其余每个元素都有一

个且仅有一个直接前驱和直接后继

30.n个顶点的连通图中至少含有（B）条边。

A.n

B.n-1

C.n（n-l）/2

D.n（n-l）

31.在下列存储形式中，（B）不是树的存储形

式？

A.双亲表示法

B.顺序存储表示法

C.孩子兄弟表示法

D.孩子链表表示法

32.下列陈述中正确的是（A）

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

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

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

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

33.完全二叉树的结点个数11,则它的叶子结点个数

为(A)

A.6

B.3

C.4

D.5

34.在一个具有n个单元的顺序栈中，假设以地址低端

作为栈底，以top作为栈顶指针，则当作进栈处理

时，top的变化为(D)

A.top不变

B.top=0

C.top-

D.top++

35.在单链表中，要将s所指结点插入到p所指结点之

后，其语句应为(D)

A.s->next=p+l

B.p->next=s

C.(*p).next=s

D.(*s).next=(*p).next

E.s->next=p->next

F.p->next=s->next

G.s->next=p->next

H.p->next=s

36.图的深度优先遍历类似于二叉树的（A）

A.先序遍历

B.中序遍历

C.后序遍历

D.层序遍历

37.AVL树是一种平衡的二叉排序树，树中任一结点的

（A）

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

B.左、右子树的高度均相同

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

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

38.在n个结点的顺序表中，算法的时间复杂度是0（1）

的操作是（A）

A.访问第i个结点（lvivn）和求第i个结点的直接前驱

（2<i<n）

B.在第i个结点后插入一个新结点（lSiSn）

C.删除第i个结点（BiSn）

D.将n个结点从小到大排序

二判断（共20题，总分值40）

39.算法的优劣与算法描述语言无关，但与所用计算机

有关。（）（F）

40.连通分量指的是有向图中的极大连通子图。

（）（F）

41.顺序存储方式的优点是存储密度大，且插入、删除

运算效率高。（）（F）

42.在n个结点的无向图中，若边数大于nT,则该图

必是连通图。（）（F）

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

（T）

44.树形结构的特点是一对多。（）（T）

45.图形结构的特点是一对多,树形结构的特点是多对

多。（）（F）

46.无向图的邻接矩阵一定是对称的。（）

（T）

47.完全二叉树一定存在度为1的结点。（)

（F）

48.冒泡法排序排序趟数与序列的原始状态有关。

()(T)

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

()(F)

50.栈和队列的存储方式，既可以是顺序方式，又可以

是链式方式。()(T)

51.查找相同结点的效率折半查找总比顺序查找高。

()(F)

52.队列和栈都是操作受限的线性表。()

(T)

53.随机稀疏矩阵压缩存储后，必会失去随机存取功

能。()(T)

54.队列是一种插入与删除操作分别在表的两端进行的

线性表，是一种先进后出型结构。()

(F)

55.二叉排序树是一种动态查找树。()

(T)

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

（F）

57.完全二叉树中，若一个结点没有左孩子，则它必是

树叶。（）（T）

58.堆肯定是一棵平衡二叉树。（）（T）

三计算题（共10题，总分值20）

59.设一棵二叉树的先序序

歹U：ABDFCEGH,中序序

歹（J：BFDAGEHC

（1）画出这棵二叉树。

（2）写出这棵二叉树的后序序列和层次遍历序

列。

答案：FDBGHECA（4分）

ABCDEFGH（4分）

60.阅读下列算法，并回答下列问题：

voidInsertSort（SqList&L）{

for（i=2;i<=L.length;++i）

if(L.r[i].key<L.r[i-l].key){

L.r[0]=L.r[i];

for(j=i-

1；L.r[0].key<L.r[j].key;-j)

L.r[j+1]=L.r[jJ;

L.r[j+1]=L.r[0];

)

}//InsertSort

(1)该算法采用何种策略进行排序？

(2)这种排序方法的稳定性如何？

(3)写出用此种排序方法对关键字序列{49,38,

65,97,76,13,27}排序的过程。

答案：(1)直接插入排序(3分)

(2)稳定(3分)

(3)(6分)

初始：(49),38,65,97,76,13,27

第一趟：(38)(38,49),65,97,76,13,

27

第二趟：(65)(38,49,65),97,76,13,

27

第三趟：(97)(38,49,65,97)，76,13,

27

第四趟：(76)(38,49,65,76,97),13,

27

第五趟:(13)(13,38,49,65,76,97),

27

第六趟：(27)(13,27,38,49,65,76,

97）

结果：13,27,38,49,65,76,97

61.回答下列问题：（1）什么是数据结构？（2）对于

数据结构一般包含哪三个方面的讨论？（3）在编

制管理通讯录的程序时，通讯录数据采用什么样的

数据结构合适？（4）对于第（3）问，存储结构采

用什么样的结构合适？为什么？

答案：（1）数据结构就是数据之间存在着一种或多种特

定关系的数据元素的集合（4分）。（2）逻辑结

构、存储结构和操作（运算）。（3分）（3）线性

结构。（2分）（4）要分情况而定，如果仅仅进行查

询操作，那么可以采用顺序表，如果经常进行插入

和删除操作，那么采用链式存储结构。（3分）

62.写出用按层次顺序遍历二叉树的方法，统计树中叶

子结点数目的算法。

答案：•intLevel(BiTree*bt)

•{intnum=O;

〃num统计度为1的结点的个数

•if(bt){

•Queuelnit(Q);Queuein(Q,bt)；〃Q是以二

叉树结

•点指针为元素的队列

while(!QueueEmpty(Q))

•{p=QueueOut(Q);printf(p-

>data);〃出队,访问结点

•if(p->lchild&&!p->rchildI|!p-

>lchild&&p->rchild)

•num++;

〃度为1的结点

•if(p->lchild)Queuein(Q,p->lchild);//

非空左子女入队

•if(p->rchild)Queuein(Q,p->rchild);//

非空右子女入队

•}}//if(bt)

,return(num);

63.写出将两个递增的有序链表合并为一个递增的有序

链表的算法。要求结果链表仍使用原来两个链表的

存储空间，不另外占用其它的存储空间，表中不允

许有重复的数据

答案：(1)合并后的新表使用头指针Lc指向，pa和

pb分别是链表La和Lb的工作指针,初始化为相应

链表的第一个结点，从第一个结点开始进行比较，

当两个链表La和Lb均为到达表尾结点时，依次摘

取其中较小者重新链接在Lc表的最后。如果两个

表中的元素相等，只摘取La表中的元素，删除Lb

表中的元素，这样确保合并后表中无重复的元素。

当一个表到达表尾结点，为空时.，将非空表的剩余

元素直接链接在Lc表的最后。

(2)voidMergeList(LinkList&La,LinkLi

st&Lb,LinkList&Lc)

{〃合并链表La和Lb,合并后的新表使用头指针

Lc指向pa=La->next;pb=Lb->next;

//pa和pb分别是链表La和Lb的工作指针，

初始化为相应链表的第一个结点Lc=pc=La;//

用La的头结点作为Lc的头结点while(pa&&pb)

{if(pa->data<pb->data){pc-

>next=pa;pc=pa;pa=pa->next;}

//取较小者La中的元素，将pa链接在pc的

后面，pa指针后移elseif(pa->data>pb-

>data){pc->next=pb;pc=pb;pb=pb->next;)

//取较小者Lb中的元素，将pb链接在pc

的后面，pb指针后移else〃相等时取La中的元

素，删除Lb中的元素{pc->next=paRLpaipHpa-

Anext;

qz:pb->next;deletepb;pb=q;

}

}

pc->next=pa?pa:pb;〃插入剩余段

deleteLb;〃释放Lb

的头结点}

64.数据结构是什么？算法是什么？试分析下列程序段

的渐近时间复杂度：

x=90;y二100;

while(y>0)

if(x>100)

{x=xT0;y—;}

elsex++;

答案：数据结构就是数据之间存在着一种或多种特定关

系的数据元素的集合(4分)。算法是为了解决某

类问题而规定的一个有限长的操作序列(4分)。0

(1)(4分)。

65.写出创建一个的单链表的算法。

答案：

voidCreateList_L(LinkList&L,intn){

//逆序输入n个数据元素，建立带头结点

的单链表

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

L->next=NULL;//先建立一个带头

结点的单链表

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

p二(LinkList)malloc(sizeof(LNod

e));

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

值

p->next=