06计算机——数据结构期末复习试卷
一、选择题
1. 在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行____ B ____。 A. HL=p; p->next=HL; B. p-next=HL; HL=p;
C. p->next=HL; p=HL; D. p->next=HL->next; HL->next=p; 2. 从二叉排序树中查找一个元素时，其时间复杂度大致为____ C ____。 A. O(n) A. O(n)
B. O(1) B. O(n/2) B. 叶结点 B. 出度
C. O(log2n)
D. O(n)
2
2
3. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为____ A ______。
C. O(1)
D. O(n) D. 空结点
D. 入度与出度之差
4. 在一棵树中，_____ D ____没有前驱结点。 A. 分支结点 A. 入度
C. 树根结点
5. 在有向图中每个顶点的度等于该顶点的_____ C ____。
C. 入度与出度之和
6. 在一个单链表中，若删除p所指结点的后继结点不是最后结点，则执行：__ A __ A.p?next=p?next?next; C.p?next=p?next; 是：__ B __ A.110
B.108
C.100
D.120
8. 判断一个循环队列QU（最多元素为m0），为满队列的条件是：__ A __ A.QU?front==QU?rear
B.QU?front!=QU?rear D.QU?front!=(QU?rear+1)%m0
C.QU?front==(QU?rear+1)%m0
B.p=p?next;p?next=p?next?next; D.p=p?next?next;
7. 一个顺序存储的线性表第一个元素的存储地址是100，每个元素的长度为2，则第5个数据元素的地址
9. 二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素___ B ___的起始地址相同。 A.M[2][4] A. O(n)
2
B.M[3][4]
C.M[3][5] D.M[4][4]
D. O(log2n)
10. 采用二分查找方法(即折半搜索)查找长度为n的线性表时，每个元素的平均查找长度为: __ D __
B. O(nlog2n)
C. O(n)
11. 数据结构是研究数据的物理结构和逻辑结构以及他们之间的相互联系，并对这种结构定义相应的____ A ____，设计相应的算法，而确保经过这些运算后所得到的新结构是原来的结构类型。 A. 运算 B. 算法 C. 结构 D. 规则
12．X、Y、Z三个元素顺序入栈，下面不可能产生的出栈序列是_____ D ___。 A. XYZ B. ZYX C. XZY D.ZXY 13. 一个深度为L的完全二叉树至少有___ B _____个结点。 A. 2*L B. 2 C. 2 D. 2
14. 在基于排序码比较的排序算法中，______ C ______算法的最坏情况下的时间复杂度不高于O(nlog2n)。 A. 起泡排序 ___ A _____。 A. (rear-front+m)%m A. abcd*+-
B. rear-front+1
C. rear-front–1 D. rear-front
D. -+*abcd
16. 表达式a*(b+c)-d的后缀表达式是 B __ 。
B. abc+*d-
C. abc*+d-
17. 一个二叉树按顺序方式存储在一个一维数组中，如图
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G H I J B. 希尔排序
C. 归并排序
D. 快速排序
15. 循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头及队尾，则当前队列中的元素数是
L-1
L
L+1
第1页，共17页
06计算机——数据结构期末复习试卷
则结点E在二叉树的第_____ C ___层。 A. 4
B. 3
C. 2
D. 1
D. （（ ））
18. 若广义表S满足 Head(S)=Tail(S)，则S为____ D ____。 A. （ ）
B. （（）、（））
C （（），（），（））
19. 在数据结构中，从逻辑上可以把数据结构分为___ C _____。 A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 20. 下面程序段的时间复杂度是_____ D ___。 s=0;
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) s+=b[i][j]; A. O(n) C __。 A. i
B. n-i
C.n-i+1
D. 不确定
22. 若某线性表中最常用的操作是删除第i个元素和找第i个元素的前趋元素，则采用______ B _______存贮方式最节省运算时间。 A.单链表 A.130
B.双链表 B.129
C.单循环链表 D. 向量 C.131
D.不确定
D. 可能不存在
23. 已知二叉树叶子数为50，仅有一个孩子的结点数为30，则总结点数为_____ B _______。 24. 任何一个无向连通图的最小生成树____ B _____。 A. 只有一棵 A. 起泡排序 A. 14
B.有一棵或多棵
C. 一定有多棵 D. 快速排序
D. 24
25. 下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（nlog2n）的是______ C ______。
B. 希尔排序
B. 8
C. 堆排序
C. 12
26．利用关键码分别为10，20，30，40的四个结点，能构造出___ A ____种不同的二叉搜索树。
B. O(1)
C. O(log2n)
D. O(n)
2
21. 若已知一个栈的入栈序列为1,2,3,...,n，其输出序列为p1,p2,p3,...,pn，若p1=n，则pi为______
27. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，．．．则元素A[5，5]的地址是____ A ______。 A. 1175
B. 1180
C. 1205
D. 1210
28. 有六个元素6，5，4，3，2，1 按顺序进栈，问下列哪一个不是合法的出栈序列？_ C __ A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
29. 在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是____ C ____。 A. 80
B. 100
C. 240 C. *a+ｉ
D. 270
30. 一个数组元素a[i]与____ A ____的表示等价。 A. *（a+i）
B. a+ｉ
D. &a+ｉ
31. 设有一个递归算法如下： int fact (int n ) { if (n<=0) return 1; else return n*fact(n-1);} 下面正确的叙述是___ B _____。
第2页，共17页
06计算机——数据结构期末复习试卷
A. 计算fact(n) 需要执行n次递归
B. fact(7)=5040 D. 以上结论都不对
B. 求最短路径的Dijkstra方法 D. 广度优先遍历算法
D. 5
D. n+1
C. 此递归算法最多只能计算到fact(8) A. 求关键路径的方法 C. 深度优先遍历算法 A. ∞ A. n-2
32. 判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用____ C ____。
33. 设有广义表D(a,b,D),其深度为_____ A ___。
B. 3 B. n-1
C. 2 C. n
34. 当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为____ B ____。 35. 采用线性链表表示一个向量时，要求占用的存储空间地址___ D _____。 A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的 A. 起泡排序 A. 栈
D. 可连续可不连续
C. 锦标赛排序
D. 快速排序
D. 优先队列 D. 4,3,2,1
36. 如果想在4092个数据中只需要选择其中最小的5个，采用_____ C ____方法最好。
B. 堆排序 B. 队列 B. 3,2,4,1
37. 将一个递归算法改为对应的非递归算法时，通常需要使用____ A _____。
C. 循环队列 C. 1,2,3,4
38. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为___ C ______。 A. 2,3,4,1
39. 若需要利用形参直接访问实参，则应把形参变量说明为____ B _____参数。 A. 指针 A. n
B. 引用 B. n+1
C. 值 C. n-1
D. 变量 D. n+e
40. 对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为__ A _______。 41. 对包含n 个元素的散列表进行搜索，平均搜索长度为______ C ___。 A. O（log2n） 二、填空题
1．一个广义表中的元素分为___单（或原子项）_____元素和____表（广义表）____元素两类。 2．从一个链栈中删除一个结点时，需要把栈顶结点的____指针____域的值赋给___栈顶指针____。 3．对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的右孩子结点的编号为____2i+1____。
4．设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(sub(s1,2,len(s2)),subs(s1,len(s2),2))的结果是__________ BCDEFEF __________。
5．对于一个具有n个顶点和e条边的有向图，若采用边集数组表示，则存于数组中的边数为___ e ____条。
6．以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为____37/12____。 7．在快速排序、归并排序和堆排序中，所需辅助存储量最少的是________堆排序___________。 8．带有一个头结点的单链表head为空的条件是_____ head?next==NULL ____。
9．对于一个具有n个结点的单链表，在给定值为x的结点后插入一个新结点的时间复杂度为_____ O(n)___。 10．设s=’I#AM#A#TEACHER’，其长度是____14____。（其中“#”表示空格） 11．广义表((a),((b),c),(((d))))的表尾是_____(((b),c),(((d))))______。
12．深度为k的完全二叉树，若按自上而下，从左至右的次序给结点编号（从1开始），则编号最小的叶子结点的编号是___2+1____。
13．已知一个图的邻接矩阵表示，计算第i个结点的入度的方法是_求矩阵第i行非0元素之和_。
k-2
B. O（n） C. 不直接依赖于n D. 上述都不对
第3页，共17页
06计算机——数据结构期末复习试卷
14．在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_ 哈希表查找法___。
15．在数据结构中，与所使用的计算机无关的数据叫___逻辑____结构，与所使用的计算机有关的数据叫____ 物理___结构。
16．快速排序是一种____ 起泡____排序，对含有n个元素的序列进行排序时，快速排序的时间复杂度是____ O(nlogn)____，所需要的辅助空间是____ O(logn) ____。
17． 一个深度为n的满k叉树有如下性质：第n层的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点编号，总共的结点数目是____ k+k+?+K____，编号为n的结点的父结点（若存在）的编号为___(n+k-2)/k _____，编号为n的结点的右兄弟的条件是____ (n-1)%k≠0____，其右兄弟的编号为____n+1____。
18. 稀疏矩阵一般的压缩存储方法有两种，它们是用 __三元组__和_ 十字链表 表示。 19. 无向图G=（V，E），其中：V={ a,b,c,d,e,f} ,
E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}
对该图进行深度优先遍历，得到的顶点序列正确的是 a,e,d,f,c,b 。
20. 在一棵B-树中，所有叶子结点都处在___同一层___上，所有叶子结点中空指针数等于该树中所有___关键字___总数加1。
21. 有一个有序表为{ 3,12,24,37,45,53,61,78,90,100 }，当二分查找值为24的数据时____3___次比较成功。
22. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为___e ___和___2e ___个。
23. 若一棵度为3的树中，有2个结点的度为1，1个结点的度为2，2个结点的度为3，则该树中度为0的结点个数是___6___。
24. 广义表A=（c, d, e），取出A中原子e的操作是____ head ( tail ( tail ( A ) ) )_____。 25．有n个叶子的哈夫曼树，其总结点数为______2n-1_____。
26．在单链表中，若要在指针P所指结点后插入S所指结点，则需执行下列两条语句： _____ S->next=P->next ______ ；P->next=S。
27．算法具有输入，输出，有穷性，可行性以及______正确性_____等五大特性。 28．对于长度为n的线性表，若进行二分法查找，则时间复杂度为____ O(log2n)____。 29. 高度为K的完全二叉树，至少有_____2_______个结点。
30. 检测有向图中是否有回路（即有向环）的方法是_构造拓扑有序序列（或进行拓扑排序）_。 31. 锦标赛排序算法总的时间复杂度为_______ O(nlog2n)_______。
32. 根据AVL树的定义，任意一个结点的平衡因子balance的值只能取__ 1__，__ －1__和__0__。 33. 队列是一种只允许_________在表头插入、表尾删除________的线性表。
34. 对于有n个顶点的无向连通图至少有___n-1____条边，最多有___n(n-1)/2____条边。 35. 在求解递归问题时，称分解－求解的策略为_____分治法____。
36. 静态搜索时，在等概率的情形下搜索到所需对象的平均搜索长度ASL=___(n+1)/2____。 37.设A={1,2,3,4,5}，B={3,4,6}，求A+B=____{1,2,3,4,5,6}_____，A-B=____{1,2,5}____。
38. 数据的逻辑结构被分为_____集合结构______、______线性结构_____、_____树形结构_____、____图形结构_____四种。
39. 一种抽象数据类型包括____数据_______和_____操作______两个部分。 40. 对于一棵具有n个结点的树，该树中所有结点的度数之和为____ n-1_______。
41. 在散列存储中，装载因子α又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则α等于_____ n/m ______。
42. 算法是对特定问题的求解步驟的一种描述，它是___指令___（用来表示一个或多个操作）的有限序列。 43. 设高度为h的空二叉树的高度为-1，只有一个结点的二叉树的高度为0，若设二叉树只有度为2上度
k-1
0
1
n-1
第4页，共17页
06计算机——数据结构期末复习试卷
为0的结点，则该二叉树中所含结点至少有____2h+1____个。
44. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为____n ____、边数为____(n-1____。 45. 线性结构反映结点间的逻辑关系是一对一的，图中的数据元素之间的关系是____多对多____的，树形结构中数据元素间的关系是___一对多_____的。
46. 在霍夫曼编码中，若编码长度只允许小于等于4,则除掉已对两个字符编码为0和10外，还可以最多对_____4___个字符编码。
三、判断题：对的打“√”，错的打“×”
1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。× 2.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。√ 3.通常递归的算法简单、易懂、容易编写，而且执行的效率也高。√ 4.一个广义表的表尾总是一个广义表。×
5.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。× 6.直接选择排序是一种稳定的排序方法。×
7.二叉树中除叶子结点外，任一结点x，其左子树根结点的值小于该结点（x）的值；其右子树根结点的值大于等于该结点（x）的值，则此二叉树一定是二叉排序树。× 8. 线性表的长度是线性表占用的存储空间的大小。× 9. 在顺序表中取出第i个元素所花费的时间与i成正比。×
10. 数组可以看成是线性表的一种推广，但是不可以进行插入、删除等运算。√ 11. 树（或森林）转化为对应的二叉树后，两者的分支数相等。× 12. 队列只能采用链式存储方式。×
13. 对n个元素的有序表用快速排序方法进行排序，时间复杂是O(n)。× 14.顺序存储的线性表可以随机存取。×
15.存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。× 16.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。× 17. 算法可以没有输入，但是必须有输出。√
18. 一个树中的叶子数一定等于其对应的二叉树中的叶子数。×
19. 求图的最小生成树有两种算法，其中kruskal算法适合于求稀疏图的最小生成树。√ 20. AOE网中，完成工程的最短时间等于从源点到汇点的最短路径的长度。× 21. B-树是一种动态索引结构，它既适用于随机搜索，也适用于顺序搜索。× 22. 如果一个串中的所有字符均在另一个串上出现，则说明前者是后者的子串。× 22. 对二叉排序树遍历的结果是一个有序序列。× 26. 数据元素是数据的最小单位。×
30. 采用线性探测法处理冲突的散列表中，所有同义词（其冲突的元素）在表中相邻。× 31. B-树是平衡的 m 路搜索树，但一棵平衡的 m 路搜索树不一定是B-树。√ 32. 希尔排序是一种稳定的排序方法。×
33. 对于无向图的生成树，从同一顶点出发所得的生成树相同 。× 34. 在排序算法中，就平均时间而言，直接选择排序最好。×
35. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2)的算法。√ 36. 由一棵二叉树的前序序列和后序序列可以唯一确定它。×
37. 在排序算法中，就平均时间而言，希尔排序比直接选择排序要好。√ 38. 线性表若采用链式存储表示时所有存储单元的地址可连续也可不连续。√ 39. 线性表的逻辑顺序与物理顺序总是一致的。× 40 空串与由空格组成的串没有区别。×
41. 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍
n
2
第5页，共17页