《数据结构与算法》期末练习题3.pdfVIP

数据结构与算法

一选择题

1．算法的计算量的大小称为计算的（）。

A．效率B.复杂性C.现实性D.难度

2．下面说法错误的是（）

(1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1)B.(1),(2)C.(1),(4)D.(3)

3.连续存储设计时，存储单的地址（）。

A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续

4.下述哪一条是顺序存储结构的优点？（）

A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示

5．若某线性表最常用的操作是存取任一指定序号的素和在最后进行插入和删除运算，则利用（）存储方式

最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表

6．下面的叙述不正确的是（）

A．线性表在链式存储时，查找第i个素的时间同i的值成正比

B.线性表在链式存储时，查找第i个素的时间同i的值无关

C.线性表在顺序存储时，查找第i个素的时间同i的值成正比

D.线性表在顺序存储时，查找第i个素的时间同i的值无关

7．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新素的算法的时间复杂度为（）(1=i=n+1)。

A.O(0)B.O(1)C.O(n)D.O(n2)

8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插

入结点，现要求在p前插入q，则正确的插入为（）(.相当于—)

A.p＾.llink:=q;q＾.rlink:=p;p＾.llink＾.rlink:=q;q.llink:=p.llink;

B.q＾.llink:=p.llink;p＾.llink.rlink:=q;q＾.rlink:=p;p.llink:=q.rlink;

C.q.rlink:=p;p.rlink:=q;p.llink.rlink:=q;q.rlink:=p;

D.p.llink.rlink:=q;q.rlink:=p;q.llink:=p.llink;p.llink:=q;

9．下列排序算法中，其中（）是稳定的。

A)堆排序，冒泡排序B)快速排序，堆排序

C)直接选择排序，希尔排序D)归并排序，冒泡排序

10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为

（1）8447251521（2）1547258421（3）1521258447(4）1521254784

则采用的排序是()。

A)选择B)冒泡C)快速D)插入

11．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p

所指结点，则正确的删除是（）（链中结点数大于2，p不是第一个结点）

A．p.llink.rlink:=p.llink;p.llink.rlink:=p.rlink;dispose(p);

B．dispose(p);p.llink.rlink:=p.llink;p.llink,rlink:=p.rlink;

C．p.llink.rlink:=p.llink;dispose(p);p.llink.rlink:=p.rlink;

D．以上A，B，C都不对。

12.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）

A)CABDEFGB)BCDAEFGC)DACEFBGD)ADB