福建师范大学数学与计算机学院计算机科学与技术
《数据结构与算法》期末练习
一 选择题
1．以下与数据的存储结构无关的术语是（ D ）。
A)循环队列 B) 链表 C) 哈希表 D) 栈
2．下面关于线性表的叙述中，错误的是哪一个？（ B ）
A)线性表采用顺序存储，必须占用一片连续的存储单元。 B)线性表采用顺序存储，便于进行插入和删除操作。 C)线性表采用链接存储，不必占用一片连续的存储单元。
D)线性表采用链接存储，便于插入和删除操作。
3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。 A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2
4. 设n为正整数.下列程序段中前置以@的语句的频度为（ A ）。 i = 1; k = 0;
While(i <= n-1){ @ k+= 10*i; i++;
}
A) n – 1 B) n C) n + 1 D) n – 2
5．对于有n 个结点的二叉树, 其高度为（ D ）
A)nlog2n B)log2n C)?log2n?|+1 D)不确定
6．从下列有关树的叙述中,选出正确的叙述（ C ）
A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B)当K≥1时高度为K的二叉树至多有2k-1个结点。
C)哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 D)在二叉树中插入结点,该二叉树便不再是二叉树。
7．设无向图的顶点个数为n，则该图最多有（ B ）条边。
A)n-1 B)n(n-1)/2 C) n(n+1)/2 D)0 E．n
8．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A)V1,V3,V4,V6,V2,V5,V7 B)V1,V3,V2,V6,V4,V5,V7
2
C)V1,V3,V4,V5,V2,V6,V7 D)V1,V2,V5,V3,V4,V6,V7
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．以下数据结构中，哪一个是线性结构（ D ）？
A)广义表 B) 二叉树 C) 稀疏矩阵 D) 串
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. 设n为大于1的正整数.下列程序段中前置以@的语句的频度为（ A ）。
i = 1; k = 0;
do{
@ k+= 10*i; i++;
}While(i <= n-1);
A) n – 1 B) n C) n + 1 D) n - 2
15. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）
A)?logn?+1 B)logn+1 C)?logn? D)logn-1
16. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A) 快速排序 B) 堆排序 C) 归并排序 D) 直接插入排序
17．n个结点的完全有向图含有边的数目（ D ）。
A)n*n Ｂ．n（n＋１） C)n／2 D)n*（n－l）
18．稳定的排序方法是（ B ）
A)直接插入排序和快速排序 B)折半插入排序和起泡排序
C)简单选择排序和四路归并排序 D)树形选择排序和shell排序
19．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数
据的排序为 ( A )（按递增序）。
A)下面的B，C，D都不对。 B)9，7，8，4，-1，7，15，20 C)20，15，8，9，7，-1，4，7 D) 9，4，7，8，7，-1，15，20
20．以下那一个术语与数据的存储结构无关？（ A ）
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．高度为 K的二叉树最大的结点数为（ C ）。
A)2 B)2 C)2 -1
k
k-1
k
D)2-1
k-1
23．从下列有关树的叙述中,选出正确的叙述（ C ）
A)二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B)当K≥1时高度为K的二叉树至多有2个结点。
C)用树的前序遍历和中序遍历可以导出树的后序遍历。
D)哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。
24. 关键路径是事件结点网络中（ A ）。
A)从源点到汇点的最长路径 B)从源点到汇点的最短路径
C)最长回路 D)最短回路
25．下列排序方法中，哪一个是稳定的排序方法？（ B ）
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. 一个向量的第一个元素的地址是begin，每个元素的长度是k ，则第i个元素的地址是( D )
A) begin+(k-1)i B) begin+(k-2)i C) begin+ki D) begin+(i-1)k
28. 有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过( C )次与63比较。
A) 12 B) 6 C) 4 D) 5
29. 一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为( D )。
A)（31，46，70，53，77，82） B)（46，77，53，31，70，82）
k-1
C)（46，31, 82，53，77，70）
D) (46 ，53，31，70，77，82)
30. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A) i B) n-i C) n+1 D) n-i+1
31. 不带表头的单链表，头指针为head ，判断其是否为空的条件是( A )
A) head== null B) head->next==null C) head==head D) head->next==head
32. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是( A )。
A)q->next=s; s->next =p B) s->next=p->next; q->next=s; C) p->nexr=s; s->next=p ; D) p->next=s; s->next=q;
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 B) 31 C) 14 D) 15
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)
40. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( B )。
A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 2
1 2 3 4
4 ^ 3 ^ 2 ^ 2 ^ 4 ^ 4 ^ 3 ^
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. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B )
A)O(1) B)O(n) C)O(nlogn) D)O(n*n)
48. 链栈与顺序栈相比，比较明显的优点是( D )
A)插入操作更加方便 B)删除操作更加方便
C)不会出现下溢的情况 D)不会出现上溢的情况
49. 二叉树中第5层上的结点个数最多为( C )
A)8 B)15 C)16 D)32