秋《数据结构》作业.docx

秋《数据结构》作业.docx

《秋《数据结构》作业.docx》由会员分享，可在线阅读，更多相关《秋《数据结构》作业.docx（16页珍藏版）》请在冰点文库上搜索。

秋《数据结构》作业

1．第1题

下列各式中，按增长率由小至大的顺序正确排列的是（  ）。

A．n1/2，n!

，2n，n3/2

B．n3/2，2n，nlogn，2100

C．2n，logn，nlogn，n3/2

D．2100，logn,2n,nn

A.A

B.B

C.C

D.D

您的答案：

D

题目分数：

2

此题得分：

2.0

2．第2题

串s=″DataStructure″中长度为3的子串的数目是（）。

A.9

B.11

C.12

D.14

您的答案：

C

题目分数：

2

此题得分：

2.0

3．第5题

给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是（）。

A.A

B.B

C.C

D.D

您的答案：

C

题目分数：

2

此题得分：

2.0

4．第6题

连通网的最小生成树是其所有生成树中（）。

A.顶点集最小的生成树

B.边集最小的生成树

C.顶点权值之和最小的生成树

D.边的权值之和最小的生成树

您的答案：

D

题目分数：

2

此题得分：

2.0

5．第7题

如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是（）。

A.有向完全图

B.连通图

C.强连通图

D.有向无环图

您的答案：

D

题目分数：

2

此题得分：

2.0

6．第18题

以下广义表关系正确的是（）。

A.线性表<再入表<纯表<递归表

B.线性表<纯表<递归表<再入表

C.纯表<线性表<再入表<递归表

D.线性表<纯表<再入表<递归表

您的答案：

D

题目分数：

2

此题得分：

2.0

7．第19题

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行（）次探侧。

A.k-1

B.k

C.k+1

D.k（k+1）/2

您的答案：

D

题目分数：

2

此题得分：

2.0

8．第20题

n个记录直接选择排序时所需的记录最多交换次数是（）。

A.n-1

B.n

C.n（n-1）/2

D.n（n+1）/2

您的答案：

A

题目分数：

2

此题得分：

2.0

9．第21题

线索二叉树中某结点为叶子的条件是（）。

A.p->lchild!

=NULL||p->rchild!

=NULL

B.p->ltag==0||p->rtag==0

C.p->lchild!

=NULL&&p->rchild!

=NULL

D.p->ltag==1&&p->rtag==1

您的答案：

D

题目分数：

2

此题得分：

2.0

10．第22题

设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（）。

A）O（nlog2n）

B）O（en）

C）O（elog2n）

D）O（n+e）

A.A

B.B

C.C

D.D

您的答案：

D

题目分数：

2

此题得分：

2.0

11．第23题

在下列排序方法中，空间复杂性为O（log2n）的方法为（）。

A.直接选择排序

B.归并排序

C.堆排序

D.快速排序

您的答案：

D

题目分数：

2

此题得分：

2.0

12．第27题

算法分析的目的是（）。

A.找出数据结构的合理性

B.研究算法中的输入/输出关系

C.分析算法的效率以求改进

D.分析算法的易读性

您的答案：

C

题目分数：

2

此题得分：

2.0

13．第28题

若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是（）。

A.s->next=p->next;p->next=s;

B.p->next=s;s->next=p->next;

C.p->next=s->next;s->next=p;

D.s->next=p;p->next=s->next;

您的答案：

A

题目分数：

2

此题得分：

2.0

14．第30题

在散列查找中，平均查找长度主要与（）有关。

A.散列表长度

B.散列元素的个数

C.装填因子

D.处理冲突方法

您的答案：

C

题目分数：

2

此题得分：

2.0

15．第31题

对n个元素进行冒泡排序，最好情况下的只需进行（）对相邻元素之间的比较。

A.n

B.n-1

C.n+1

D.n/2

您的答案：

B

题目分数：

2

此题得分：

2.0

16．第32题

设计一个判断表达式中左右括号是否配对出现的算法，采用（）数据结构最好。

A.顺序表

B.链表

C.队列

D.栈

您的答案：

D

题目分数：

2

此题得分：

2.0

17．第33题

以下叙述错误的是（）。

A.数据可分为数值型和非数值型

B.数据类型可分为原子类型和结构类型

C.运算可分为加工型和引用型

D.数据结构可分为逻辑结构和非逻辑结构

您的答案：

D

题目分数：

2

此题得分：

2.0

18．第34题

导致队列下溢的操作是（）。

A.队满时执行出队

B.队满时执行入队

C.队空时执行出队

D.队空时执行入队

您的答案：

C

题目分数：

2

此题得分：

2.0

19．第35题

若要在O

（1）的时间内将两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向（）。

A.各自的头结点

B.各自的尾结点

C.各自的第一个元素结点

D.一个表的头结点，另一个表的尾结点

您的答案：

B

题目分数：

2

此题得分：

2.0

20．第43题

设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（）。

s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;

A.结点*p与结点*s的数据域互换

B.在p所指结点的元素之前插入元素

C.在p所指结点的元素之后插入元素

D.在结点*p之前插入结点*s

您的答案：

D

题目分数：

2

此题得分：

2.0

21．第44题

下列编码中属前缀码的是（）。

A.{1,01,000,001}

B.{1,01,011,010}

C.{0,10,110,11}

D.{0,1,00,11}

您的答案：

A

题目分数：

2

此题得分：

2.0

22．第45题

设S=”abc”;T=”xyz”，则strcmp（S,T）的值为（）。

A.正数

B.负数

C.零

D.不确定

您的答案：

B

题目分数：

2

此题得分：

2.0

23．第46题

（）存储方式适用于折半查找。

A.键值有序的单链表

B.键值有序的顺序表

C.键值有序的双链表

D.键值无序的顺序表

您的答案：

B

题目分数：

2

此题得分：

2.0

24．第47题

单链表中增加头结点的目的是为了（）。

A.使单链表至少有一个结点

B.标识表结点中首结点的位置

C.方便运算的实现

D.说明单链表是线性表的链式存储

您的答案：

C

题目分数：

2

此题得分：

2.0

25．第48题

若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省运算时间（）。

A.单链表

B.顺序表

C.双链表

D.单循环链表

您的答案：

B

题目分数：

2

此题得分：

2.0

26．第49题

若下图表示某广义表，则它是一种（）。

A.线性表

B.纯表

C.再入表

D.递归表

您的答案：

D

题目分数：

2

此题得分：

0.0

27．第50题

要解决散列引起的冲突问题，常采用的方法有（）。

A.数字分析法、平方取中法

B.数字分析法、线性探测法

C.二次探测法、平方取中法

D.二次探测法、链地址法

您的答案：

D

题目分数：

2

此题得分：

2.0

28．第3题

若二叉树中没有度为1的结点，则为满二叉树。

您的答案：

错误

题目分数：

2

此题得分：

2.0

29．第4题

消除递归不一定需要使用栈。

您的答案：

正确

题目分数：

2

此题得分：

2.0

30．第8题

顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。

您的答案：

错误

题目分数：

2

此题得分：

2.0

31．第9题

线性表、树、图等都可以用广义表表示。

您的答案：

正确

题目分数：

2

此题得分：

2.0

32．第10题

基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。

您的答案：

错误

题目分数：

2

此题得分：

2.0

33．第11题

设串的长度为n，则其子串个数为n（n+1）/2。

您的答案：

错误

题目分数：

2

此题得分：

2.0

34．第12题

关键路径是指起点到终点的最短路径，它决定了整个工期的长短。

您的答案：

错误

题目分数：

2

此题得分：

2.0

35．第13题

开散列表和闭散列表的装填因子都可大于、等于或小于1。

您的答案：

错误

题目分数：

2

此题得分：

2.0

36．第14题

若算法的复杂性与数据集的状态无关，则最好、最坏和平均复杂性是相同的。

您的答案：

正确

题目分数：

2

此题得分：

2.0

37．第15题

由普通树转换来的二叉树，其根结点一定没有右子树。

您的答案：

正确

题目分数：

2

此题得分：

2.0

38．第16题

计算机的内、外存越大，算法的空间复杂性就越低。

您的答案：

错误

题目分数：

2

此题得分：

2.0

39．第17题

在拓扑序列中，若两点Vi和Vj相邻，则从Vi到Vj有路径。

您的答案：

错误

题目分数：

2

此题得分：

2.0

40．第24题

循环队列中入队和出队的节点位置可出现在数组的任一端，已不满足“一端进另一端出”的要求，故实际上已不是队列了。

您的答案：

错误

题目分数：

2

此题得分：

2.0

41．第25题

有向图的邻接表和逆邻接表中的结点数肯定是相同的。

您的答案：

正确

题目分数：

2

此题得分：

2.0

42．第26题

顾名思义，快速排序法是在所有情况下，速度最快的排序方法。

您的答案：

错误

题目分数：

2

此题得分：

2.0

43．第29题

缩短关键路径上活动的工期一定能够缩短整个工程的工期。

您的答案：

错误

题目分数：

2

此题得分：

2.0

44．第36题

线索二叉链表就是用结点的空指针域来存放某种遍历的前趋和后继线索，所以线索二叉链表中就没有空指针了。

您的答案：

错误

题目分数：

2

此题得分：

2.0

45．第37题

用线性探测法解决突出时，同义词在散列表中是相邻的。

您的答案：

错误

题目分数：

2

此题得分：

2.0

46．第38题

计算机的速度越快，算法的时间复杂性就越低。

您的答案：

错误

题目分数：

2

此题得分：

2.0

47．第39题

链表中逻辑上相邻的元素在物理位置上不一定相邻。

您的答案：

正确

题目分数：

2

此题得分：

2.0

48．第40题

稀疏矩阵压缩存储后会丧失随机存取特性。

您的答案：

正确

题目分数：

2

此题得分：

2.0

49．第41题

以中序方式遍历一个堆，则得到一个有序序列。

您的答案：

正确

题目分数：

2

此题得分：

2.0

50．第42题

若链队列的头指针为F，尾指针为R，则队列中元素个数为R-F。

您的答案：

错误

题目分数：

2

此题得分：

2.0

作业总得分：

98.0