福建师范大学数学与计算机学院计算机科学与技术
《数据结构与算法》期末练习
一 选择题
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(n2)
n
8．双向链表中有两个指针域，llink和rlink，分别指回前驱及后继，设p指向链表中的一个结点，q指向一待插入结点，现要求在p前插入q，则正确的插入为（D ）
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
28. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B）
A．9 B．11 C．15 D．不确定
29. 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用(C)遍历方法最合适。
A．前序 B．中序 C．后序 D．按层次
30. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A) i B) n-i C) n+1 D) n-i+1
31. 某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号为1，2，? ，n，且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树的结点中，其最小编号等于V左子树上结点的最大编号加1。这时是按( B )编号的。
A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次顺序
32. 线索二叉树是一种（ C ）结构。
A． 逻辑 B． 逻辑和存储 C． 物理 D．线性
33. 非空循环链表head 的尾结点 *p 满足下列( C )条件
A)head->next==p; B)head==p; C)p->next==head; D)p->next==0
34. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。
A) ecdab B)cebda C)daecb D)abcde
35. 设栈s的类型为sqstack ，判定栈空的条件是( C )。
A) s==NULL B)s->top==0 C)s.top==0 D) s.top==NULL
36. 深度为5 的二叉树至多有个( B )结点。
A) 12
37. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。 A)defbca
B)fedbca C) abcdef D)fedcba
38. 一个有n个顶点的有向图最多有( B )弧 。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/2
39. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。
A) n(n+1) B) n-1 C) n+1 D) n(n-1)
B) 31
C) 14
D) 15
40. 图中有关路径的定义是（ A ）。
A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列
C．由不同边所形成的序列 D．上述定义都不是
41. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则第五个元素的地址是( C )
A) 102 B) 110 C) 108 D) 120
42. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear，则队列中元素个数为( A )。（maxlen为循环顺序表的长度）
A) (rear-front+maxlen) % maxlen B) (rear-front) % maxlen C) rear-front+1
D) front-rear+1
43. 一个有n个顶点的图最少有( D )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0
44. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。
A) 4 B) 5 C) 6 D) 7
45. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定栈满的条件是( B )。
A) s==maxlen-1 B) s.top==maxlen-1 C) s->top==maxlen-1 D) s.top==0
46. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为front,rear，最多可容纳maxlen个元素，则队空的条件是( C )。
A) front==rear B) rear==0 C) q.front==q.rear D) rear==maxlen-1
47. 下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为（ 1 ），下面步骤重复n-1次: a：（ 2 ）；b：（ 3 ）；最后：（ 4 ）。 （1）．A．VT，ET为空 B．VT为所有顶点，ET为空 C．VT为网中任意一点，ET为空 D．VT为空，ET为网中所有边 （2）．A. 选i属于VT，j不属于VT，且（i，j）上的权最小 B．选i属于VT，j不属于VT，且（i，j）上的权最大 C．选i不属于VT，j不属于VT，且（i，j）上的权最小 D．选i不属于VT，j不属于VT，且（i，j）上的权最大
（3）．A．顶点i加入VT，（i,j）加入ET B. 顶点j加入VT，（i,j）加入ET C. 顶点j加入VT，（i,j）从ET中删去 D．顶点i,j加入VT，（i,j）加入ET
（4）．A．ET 中为最小生成树 B．不在ET中的边构成最小生成树 C．ET中有n-1条边时为生成树，否则无解 D．ET中无回路时，为生成树，否则无解
CABA