清华大学《数据结构与算法》

数据结构与算法

一 选择题

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

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

2．下面说法正确的是（ C ）

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

（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低

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

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

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

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

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

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

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

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

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

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

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

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

8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D ）

2

n

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．下列排序算法中，其中（ D ）是稳定的。

A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序

10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 (4） 15 21 25 47 84 则采用的排序是 ( A )。

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

11．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ D）（链中结点数大于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，它的中序遍历序列可能是（ B ）

A)CABDEFG B) BCDAEFG C) DACEFBG D) ADBCFEG

13. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。

A) 5 1 2 3 4 B) 4 5 1 3 2 C) 4 3 1 2 5 D) 3 2 1 5 4

14. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

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

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分

16. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。

A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序

17．下面关于串的的叙述中，哪一个是不正确的？（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储

18．稳定的排序方法是（ B ）

A)直接插入排序和快速排序 B)折半插入排序和起泡排序 C)简单选择排序和堆排序 D)树形选择排序和shell排序

19．已知串S=‘aaab’,其Next数组值为（ A ）。 A．0123 B．1123 C．1231 D．1211

20．串的长度是指（ B ）

A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数

21. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。 A) a，c，b，d B) b, c，d，a C) c, d，b, a D) d, c，a，b

22．数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( A )。

A. 1175 B. 1180 C. 1205 D. 1210

23．A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1

24. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS))))

25．下面说法不正确的是( A )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

26．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A)(38,40,46,56,79,84) B) (40,38,46,79,56,84) C)(40,38,46,56,79,84) D) (40,38,46,84,56,79)

27. 已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( D )

A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE

-+A*BC/DE

28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B）

A．9 B．11 C．15 D．不确定

29. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用(C)遍历方法最 …… 此处隐藏：3919字，全部文档内容请下载后查看。喜欢就下载吧 ……