西安交通大学《数据结构》在线作业

试卷总分:100  得分:100

一、单选题 (共 30 道试题,共 60 分)

1.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。

A.O(n)

B.O(1og2n)

C.O(nlog2n)

D.O(n)

 泽学网（www.zexuewang.net）

2.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。

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

B.q->next=s；s->next=p；

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

D.p->next=s；s->next=q；

3.字符串的长度是指（）

A.串中不同字符的个数

B.串中不同字母的个数

C.串中所含字符的个数

D.串中不同数字的个数

4.设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A.2n

B.n

C.n/2

D.n(n-1)

5.用链接方式存储的队列，在进行插入运算时（）

A.仅修改头指针

B.头、尾指针都要修改

C.仅修改尾指针

D.头、尾指针可能都要修改

6.下列程序段的时间复杂度为（）。i=0，s=0；while(s<n){s=s+i；i++；}

A.O(n)

B.O(n)

C.O(n)

D.O(n)

7.如果要求频繁的对线性表进行插入和删除操作，则线性表应该采用（ ）存储结构。

A.散列

B.顺序

C.链式

D.任意

8.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

A.8

B.7

C.6

D.5

9.设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。

A.单向链表

B.单向循环链表

C.双向链表

D.双向循环链表

10.以下数据结构中哪一个是非线性结构？（）

A.队列

B.栈

C.线性表

D.二叉树

11.每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为（ ）结构。

A.顺序结构

B.链式结构

C.索引结构

D.散列结构

12.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。

A.q=p->next；p->data=q->data；p->next=q->next；free(q)；

B.q=p->next；q->data=p->data；p->next=q->next；free(q)；

C.q=p->next；p->next=q->next；free(q)；

D.q=p->next；p->data=q->data；free(q)；

13.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

A.O(n)

B.O(nlog2n)

C.O(1)

D.O(n)

14.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）

A.24

B.71

C.48

D.53

15.对一棵二叉排序树进行( )遍历,可以得到该二叉树的多有结点按值从小到大排列的序列。

A.前序

B.中序

C.后序

D.按层次

16.若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（）

A.O（1）

B.O（n）

C.O（n^2)

D.O（n^3）

17.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,打印机依次从该缓冲区中取出数据打印,则该缓冲区的结构应该是( )。

A.线性表

B.数组

C.堆栈

D.队列

18.线性链表各结点之间的地址( )。

A.必须连续

B.一定不连续

C.部分地址必须连续

D.连续与否无所谓

19.在二叉排序树中插入一个结点的时间复杂度为（）。

A.O(1)

B.O(n)

C.O(log2n)

D.O(n)

20.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）

A.p->right=s；s->left=p；p->right->left=s；s->right=p->right；

B.s->left=p；s->right=p->right；p->right=s；p->right->left=s；

C.p->right=s；p->right->left=s；s->left=p；s->right=p->right；

D.s->left=p；s->right=p->right；p->right->left=s；p->right=s；

21.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

A.2，3，5，8，6

B.3，2，5，8，6

C.3，2，5，6，8

D.2，3，6，5，8

22.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）

A.O（1）

B.O（n）

C.O（m）

D.O（m+n）

23.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（）=K%9作为散列函数，则散列地址为1的元素有（）个

A.1

B.2

C.3

D.4

24.下列各个排序算法中,要求辅助空间最大的是( )。

A.希尔排序法

B.快速排序法

C.堆排序法

D.二路归并排序法

25.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（）

A.直接选择排序

B.直接插入排序

C.快速排序

D.起泡排序

26.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A.不确定

B.n-i+1

C.i

D.n-i

27.链式栈与顺序栈相比，一个比较明显的优点是（）

A.插入操作更加方便

B.通常不会出现栈满的情况

C.不会出现栈空的情况

D.删除操作更加方便

28.程序段如下:s=i=0； do {i=i+1； s=s+i；} while(i<=n)；其时间复杂度为（ ）。

A.O(n)

B.O(nlog2n)

C.O(n2)

D.O(n3/2)

29.一个具有n个顶点的无向图最多有（ ）条边。

A.n×(n-1)/2

B.n×(n-1)

C.n×(n+1)/2

D.n2

30.数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）。

A.55

B.45

C.36

D.16

二、判断题 (共 20 道试题,共 40 分)

31.{图}

32.快速排序是排序算法中平均性能最好的一种排序。

33.有向图的邻接表和逆邻接表中表结点的个数不一定相等。

34.顺序查找法适用于存储结构为顺序或链接存储的线性表。 ( )

35.对具有n个元素的序列来采用冒泡排序法进行排序，排序的趟数为n-1。（    ）

36.顺序表用一维数组作为存储结构，因此顺序表是一维数组。

37.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。

38.入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。

39.在B+树中查找和在B-树中查找的过程完全相同。

40.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。

41.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。

42.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。 ( )

43.磁带是顺序存取的外存储设备。 ( )

44.{图}

45.图可以没有边，但不能没有顶点。（ ）

46.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。

47.线性表中的每个结点最多只有一个前驱和一个后继。 ( )

48.线性表的顺序存储结构没有比链式存储结构更好。

49.设串S的长度为n,则S的子串个数为n(n+1)/2。

50.二维数组和多维数组均不是特殊的线性结构。