中国矿业大学2011-2012学年
《数据结构》试卷（A卷）（考试时间：100分钟）
一. 填空（每空2分，共40分）
1. 数据结构式具有相同性质的数据元素的（1）。
2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。
4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。
5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。
6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。
7. 一棵二叉树为
则后序序列为（12），中序序列为（13），先序序列为__（14）____。
8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。
9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。
10. 有n个结点的无向完全图的边数分别为_______(18)_______。
11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。
12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。
二简答题：
1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。
2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。
C G
E
D
F
B
H
A
3 假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题：
假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态；
4 森林和二叉树的转换，画出和下列二叉树相应的森林
5
设要将序列（46,79,56,38,40,84）中的关键码按升序重新排列，写出快速排序的过程。(每一步过程)
三程序题(10分)
编写算法判别给定二叉树是否为完全二叉树
《数据结构》（A卷）答案
一．填空（每空2分，共40分）
1. 集合。
2. 递归工作栈。
3. 1270 , 1210 。
4. 2, 8, 1023 。
5. Q.front==Q.rear, Q.front==（Q.rear+1）% 10 。
6. 5 , “iak”。
7. DECBHGFA, BDCEAFHG, ABCDEFGH
8.
。
9. 231 或 213 , 312 。 10. n(n-1)/2 。 11. 2 。
12. 快速排序 。
二. 简答题（每题10分，共50分） 1. 图不唯一WPL=229 2.
3.
0 1 2 3 4 5 6 7 8 9 10 11 12 102
54
3
4
5
30
7
72
87
95
24
63
a
c
b
d
h
g
f
e
25
70
66
17 53
58 12
60
56
87
4.
5.
（46,79,56,38,40,84） （40,38,46,56,79,84） (38,40,46,56,79,84） 三. 程序题（10分）
int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 {
InitQueue(Q);
flag=0;
EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) {
DeQueue(Q,p);
if(!p) flag=1; //如果孩子为空，则说明左孩子为空 else if(flag) return 0; else {
EnQueue(Q,p->lchild);
EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree
中国矿业大学2011-2012学年
《数据结构》试卷（B 卷）（考试时间：100分钟）一．填空（每空2分，共40分）
1. 数据结构是指数据及其相互之间的______________。当结点之间存在M 对N （M ：N ）的联系时，称这种结构为_____________________。
2. 通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
3.有6行8列的二维数组A ，每个元素用相邻的6个字节存储，存储器按字节编址，已知A 的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_______,_________。
4. 设目标T=”abccdcdccbaa”，模式P=“cdcc ”，则第 次匹配成功。
D k
C E A H B J
G
I
F M
5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：_____________,________________。
6. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。
7.在具有n个单元的循环队列中，队满时共有个元素。
8. 深度为k 的二叉树的结点总数，最多为___个。最少为___个。
9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为。
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
10. 有n个结点的无向完全图和有向完全图的边数分别为________,________。
11. 图的深度优先遍历算法类似于树的。
12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在次比较后，才找到该数据。
13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。
二简答题：（每题10分，共50分）
1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。
2. 已知一个图的顶点集V和边集E分别为：
V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，试写出临界表。并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按拓朴排序算法进行排序，试给出得到的拓朴排序的序列。
3. int Prime(int n)
{ int i=1;
int x=(int) sqrt(n);
while (++i<=x)
if (n%i==0) break;
if (i>x) return 1;
else return 0; }
(1) 指出该算法的功能；
(2) 该算法的时间复杂度是多少？请说明。
4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题：
1)假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）
请画出存放状态；
2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；
5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则写出希尔（shell）排序的过程，初始步长为4
三程序题
请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：
1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；
2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1；
3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。
中国矿业大学2011-2012学年
《数据结构》试卷（B卷）（答案）
专业：班级：序号：姓名：
一．填空（每空2分，共40分）
1. 联系 , 图（或图结构）。
2. 通常程序在调用另一个程序时，都需要使用一个栈来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。
3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_1270 , 1210_。
4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6次匹配成功。
5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：___ Q.front==Q.rear, Q.front==（Q.rear+1）% MS __。
6. O（1） O（n）_。
7.在具有n个单元的循环队列中，队满时共有 n-1 个元素。
8. 深度为k 的二叉树的结点总数，最多为_2k-1__个。最少为_k__个。
9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为 3 。
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
10. 有n个结点的无向完全图和有向完全图的边数分别为___ n(n-1)/2 , n(n-1) ____。
11. 图的深度优先遍历算法类似于树的先序。
12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在 2 次比较后，才找到该数据。
13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。快速排序 , O(n lg n)
二简答题：（每题10分，共50分）
1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。
116
68 48
34 34 28 20
18 16 15 13
9 9 7 8
5 4
2. 拓朴排序为： 4 3 6 5 7 2 1
3. (1) 判断n是否是素数（或质数）
n）
（2）O（
4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题：
1)假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）
请画出存放状态；
0 1 2 3 4 5 6 7 8 9 10 11 12
102 54 3 4 5 30 7 72 87 95 24 63
24,63,102共计比较了3次
2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；
5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则
写出希尔（shell）排序的过程，初始步长为4
Shell P, A, C, S, Q, D, F, Y, R, H, M,
C, A, , F D, M, H, P, S, Q, Y, R,
A C D F H M P Q R S Y
三程序题
请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：
1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值；
2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1；
3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。
见课本
Int search(array ST, Key key)
Low =1; high<=high;
While(low Mid=(low+high)/2; If(key=array[mid].key) return mid; Else if (key Else low=mid+1;}return 0} 计算机学院2010-2011学年第一学期 《数据结构》试卷（A卷）（考试时间：100分钟） 专业：班级：序号：姓名： 一. 填空（每空2分，共40分） 1. 双向循环链表中，P指针所指向的结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其基本操作为_______ ,_______ ,free(p)。 2. 通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_______,_________。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 5. 请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：_____________,________________。 6. 字符串t=”a very cute child”，s=”I like coffee and cake”，请写出下列函数的结果：StrLength(t) =_____;Concat(SubString(s,3,15)，SubString(t,12,6))=_______。 7. 一棵二叉树的后序序列为DECBHGFA，中序序列为BDCEAFHG，请画出这棵树的结构________。 8. 请用数据序列{53，13，24，37, 18, 90 }构造一棵二叉排序树_____________。 9. 二叉树的中序遍历相当于对应树的_____遍历，或者对应森林的______遍历。 10. 二叉树中元素（完全序列）按照顺序存储方式存放在如下一维数组中，则结点G所在层次为。 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 11. 有n个结点的无向完全图和有向完全图的边数分别为________,________。 12. 要从数据：1，3，5，7，9，11，13查找11，若采用折半查找法，则在次比较后，才找到该数据。 13. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。 二. 简答题（每题10分，共50分） 1 假设9个字母为：A B C D E F G H I，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。（要求画出树、写出编码，计算WPL） 2请对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树。（要求使用图画出每一步过程） 3．试利用Dijkstra算法求图中从顶点V1到其他各顶点间的最短路径，写出执行算法过程中各步的状态。（G使用邻接矩阵表示，要求使用表描述算法中每一步顶点与状态的变化情况，即求解过程） 4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 3)假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测） 请画出存放状态； 4)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X）中的关键码按字母序的升序重新排列，则： （1）写出冒泡排序的过程；（每一步过程） （2）写出希尔（shell）排序的过程，初始步长为4。(每一步过程) 三. 程序题（10分） 编写算法判别给定二叉树是否为完全二叉树。要求： 1）函数为：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 2）不用写主函数； 3）如使用其他函数，请注释。 《数据结构》（A卷）答案 一．填空（每空2分，共40分） 1. p->prior->next=p->next , p->next->prior=p->prior。 2. 递归工作栈。 3. 1270 , 1210 。 4. 4-1 。 5. Q.front==Q.rear, Q.front==（Q.rear+1）% MS 。 6. 17 , “like coffee and child”。 7. 8. 。 9. 后序 , 中序 。 10. 3 。 11. n(n-1)/2 , n(n-1) 。 12. 2 。 13. 快速排序 , O(n lg n) 。 二. 简答题 1 先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32 （100） （40） （ 60） 19 21 32 （28） （17） （11） 7 10 6 （5） 2 3 编码为：A :1100 B:00 C:11110 D:1110 E:10 F: 11111 G:01 H:1101 2 请对下图的无向带权图：写出它的邻接矩阵，并按普里姆算法求其最小生成树 24 37 18 90 13 53 C G E D F B H A 0 1 0 1 0 1 19 21 32 0 1 0 1 0 1 7 10 6 0 1 2 3 解：设起点为a 。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!邻接矩阵为： 3 4 其后续序列为：BHECIGFAD 5 设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X ）中的关键码按字母序的升序重新排列，则： 冒泡排序一趟扫描的结果是 H C Q P A M S R D F X Y ； ???????? ????????? ?∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞06 4560252036307945670555505395504340 D A F I G C E B H 初始步长为4的希尔（shell）排序一趟的结果是 P A C S Q H F X R D M Y ； 二路归并排序一趟扫描的结果是 H Q C Y A P M S D R F X； 快速排序一趟扫描的结果是 F H C D P A M Q R S Y X ； 堆排序初始建堆的结果是 A D C R F Q M S Y P H X 。 三. 程序题（10分） int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0; EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { { DeQueue(Q,p); if(!p) flag=1; else if(flag) return 0; else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree 计算机学院2010-2011学年第一学期 《数据结构》试卷（B卷）（考试时间：100分钟） 专业：班级：序号：姓名： 一．填空（每空2分，共40分） 1.双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其基本操作为____ ,____。 2. 通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_______,_________。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。 5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：_____________,________________。 6.字符串t=”a very cute child”，s=”I like coffee and cake”，请写出下列函数的结果：StrLength(s) =_____;Concat(SubString(s,3,15)，SubString(t,12,6))=_______。 7.在具有n个单元的循环队列中，队满时共有个元素。 8. 深度为k 的二叉树的结点总数，最多为___个。最少为___ 个。 9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G 所在层次为 。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 10. 有n 个结点的无向完全图和有向完全图的边数分别为________,________。 11. 图的深度优先遍历算法类似于树的 。 12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在 次比较后，才找到该数据。 13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。 二简答题：（每题10分，共50分） 1. 假设9个字母为：A B C D E F G H ，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。 2. 森林和二叉树的转换，画出和下列二叉树相应的森林 3. 使用克鲁斯卡尔算法求下图中最小生成树，请写出步骤。 4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态； 2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X ）中的关键码按字母序的升序重新排列，则： （1）写出冒泡排序的过程； （2）写出希尔（shell ）排序的过程，初始步长为4 三 程序题 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的 b c d e h g f k i 2 3 6 2 5 4 3 1 1 3 值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 计算机学院2010-2011学年第一学期 《数据结构》试卷（B卷）(答案） 专业：班级：序号：姓名： 一．填空（每空2分，共40分） 1.双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其基本操作为_ p->prior->next=p->next , p->next->prior=p->prior。 2. 通常程序在调用另一个程序时，都需要使用一个栈来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3.有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为_1270 , 1210_。 4. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6次匹配成功。 5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS个存储空间），判断队空和队满的条件分别分：___ Q.front==Q.rear, Q.front==（Q.rear+1）% MS __。 6.字符串t=”a very cute child”，s=”I like coffee and cake”，请写出下列函数的结果：StrLength(s) =__22__;Concat(SubString(s,3,15)，SubString(t,12,6))=__ like coffee and child _。 7.在具有n个单元的循环队列中，队满时共有 n-1 个元素。 8. 深度为k 的二叉树的结点总数，最多为_2k-1__个。最少为_k__个。 9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为 3 。 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 10. 有n个结点的无向完全图和有向完全图的边数分别为___ n(n-1)/2 , n(n-1) ____。 11. 图的深度优先遍历算法类似于树的先序。 12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在 2 次比较后，才找到该数据。 13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。快速排序 , O(n lg n) 二简答题：（每题10分，共50分） 1. 假设9个字母为：A B C D E F G H，权值分别为5，13，7，4，20，34，16, 9，8。试为这9个字母设计哈夫曼编码。并计算其带权路径长度。 116 68 48 34 34 28 20 18 16 15 13 9 9 7 8 5 4 2. 森林和二叉树的转换，画出和下列二叉树相应的森林 a c f i B e m D h k G j 3. 使用Prim 算法求下图中最小生成树。 4．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 5) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态； 1 2 3 4 5 6 7 8 9 10 11 12 102 54 3 4 5 30 7 72 87 95 24 63 24,63,102共计比较了3次 6) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 5设要将序列（Q, H, C, Y, P, A, M, S, R, D, F, X ）中的关键码按字母序的升序重新排列，则： （1）写出冒泡排序的过程； （2）写出希尔（shell ）排序的过程，初始步长为4 Shell P, A, C, S, Q, D, F, Y, R, H, M, C , A, , F D, M, H, P, S, Q, Y, R, A C D F H M P Q R S Y 三 程序题 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的 b c d e h g f k i 2 3 6 2 5 4 3 1 1 3 值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 见课本 Int search(array ST, Key key) Low =1; high<=high; While(low Mid=(low+high)/2; If(key=array[mid].key) return mid; Else if (key Else low=mid+1;}return 0} 计算机学院2009-2010学年第一学期 《数据结构》试卷（A卷）（考试时间：100分钟） 一．单项选择（每小题2分，共20分） 1．下面程序段的时间复杂度是______。 for(i=0;i for(j=1;j A[i][j]=0； A．O(n) B．O(m+n+1) C．O(m + n) D．O(m*n) 2．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是______。 1)访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） 2)在第i个结点后插入一个新结点（1≤i≤n） 3)删除第i个结点（1≤i≤n） 4)将n个结点从小到大排序 3．在单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行_____。 A.s->next = p; p->next = s; B.s->next = p->next; p->next = s; C.s->next = p->next; p = s; D.p->next = s; s->next = p; 4．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为______。A．i B．n-i C．n-i+1 D．不确定 5．数组Q［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为______。 A．r－f B．（n＋f－r）% n C．n＋r－f D．（n＋r－f）% n 6．具有n(n>0)个结点的完全二叉树的深度为。 A．?log2(n)?B．? log2(n)?C．? log2(n) ?+1 D．?log2(n)+1? 7．图的深度优先遍历算法类似于树的。 A．前序遍历B．后序遍历C．中序遍历D．层次遍历 8．有 n个顶点的有向图最多有_______条边 A．n(n-1) B．n(n-1)/2 C．n(n+1) D．n(n+1)/2 9．对22个记录的有序表作折半查找，当查找失败时，至少需要比较__________次关键字。 A．3 B．4 C．5 D． 6 10．对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。 A．从小到大排列 B．从大到小排列 C．元素无序D．元素基本有序 二．填空（每空2分，共20分） 1．数据结构包括数据的、和数据的运算（算法）三个方面。 2．循环队列Q容量为Length，其队头位置和队尾位置分别用变量front ,rear表示，则判断队空的条件为，队满的条件为。 3．假设有二维数组A[6,8]，每个元素用6个字节存储。已知A的基址为1000，按行存储时，元素A[1,4]的第一个字节地址为；若按列存储时，元素A[4,7]的第一个字节地址为。 4．写出下图的拓扑序列。 v2 v5 v1 v4 v7 v3 v6 5．若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是。 6．n个节点的二叉树，其最小高度为___________ ，最大高度为_________。。 三．简答（每小题10分，共50分） 1．有如图所示的有向图，请给出该图的: 1)每个顶点的入/出度； 2)邻接矩阵； 3)逆邻接表。 2．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素54，需依次与哪些元素比较？ （3）若查找元素90，需依次与哪些元素比较？ 3．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 4．请写出用冒泡排序方法对序列21，25，49，25*，16，08的各趟排序过程。 5．假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率(即权值)分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出对应二叉树的带权路径长度。 四．算法（10分，共10分） 注：可直接调用已知的类或函数，例如算法中用到栈s，可直接调用出栈操作s.pop(). 编程计算二叉树T的结点总数，函数原型类似int BinTree::Count(……)。 数据结构例题（及答案） 项目一习题(答案) 一选择题 1. 算法的计算量的大小称为计算的(B )。 A( 效率 B. 复杂性 C. 现实性 D. 难度 2.算法的时间复杂度取决于(C ) A(问题的规模 B. 待处理数据的初态 C. A和B 3(从逻辑上可以把数据结构分为(C )两大类。 A(动态结构、静态结构 B(顺序结构、链式结构 C(线性结构、非线性结构 D(初等结构、构造型结构 4(连续存储设计时，存储单元的地址(A )。 A(一定连续 B(一定不连续 C(不一定连续 D(部分连续，部分不连续 5. 以下属于逻辑结构的是(C )。 A(顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题 1. 数据元素是数据的最小单位。(×) 2. 记录是数据处理的最小单位。(×) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(×) 4(程序一定是算法。(×) 5. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。(×) 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×) 7. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(?) 8. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×) 三、填空 1(数据的物理结构包括数据元素的表示和数据元素间关系的表示。 2. 对于给定的n个元素,可以构造出的逻辑结构有集合，线性结构，树形 结构，图状结构或网状结构四种。 3(数据的逻辑结构是指数据的组织形式，即数据元素之间逻辑关系的总体。而 逻辑关系是指数据元素之间的关联方式或称“邻接关系”。 4(一个数据结构在计算机中表示(又称映像) 称为存储结构。 5(抽象数据类型的定义仅取决于它的一组逻辑特性，而与在计算机内部如何表 示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响 其外部使用。 6(数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。 7. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互 关系，并对与这种结构定义相应的操作(运算)，设计出相应的算法。 ( 一个算法具有5个特性: 有穷性、确定性、可行性，有零个或多个输入、 有一个或多个输8 出。 四、应用题 1. 1. 数据结构是一门研究什么内容的学科, 答:数据结构是一门研究在非数值计算的程序设计问题中，计算机的操作对象 及对象间的关系和施加于对象的操作等的学科 2. 2. 数据元素之间的关系在计算机中有几种表示方法,各有什么特点, 答:四 种表示方法 中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 数据结构试卷1 一、单项选择题：(每小题2分，共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时，在等概率的情况下，搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。 A. first->next == NULL; B. first == NULL; C. first->next == first; D. first != NULL; 3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为__________。 A. front==rear B. front!=NULL C. rear!=NULL D. front==NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) )，运算Head (Head (Tail (A) ) ) 的执行结果为________。 A．y B．(a, b) C．(x,(a,b)) D．x 6. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重，生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n，则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为_______排序法。 A．选择B.二路归并C.交换 D.插入 二、填空题（每空1分，共20分） 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中，除了首元结点外，任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性 《数据结构》题库及答案 一、选择题 1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=p->next; p->next=s; b. p->next=s->next; s->next=p; c. q->next=s; s->next=p; d. p->next=s; s->next=q; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 一、选择题(20分) 1．下面关于线性表的叙述错误的是（D ）。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（A ）。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 3．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（C ）。 (A) 9 (B) 10 (C) 11 (D) 12 4．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（B ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 5．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（B ）方法可以达到此目的。 (A) 快速排序(B) 堆排序(C) 归并排序(D) 插入排序 第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 6.下列四种排序中（D ）的空间复杂度最大。 (A) 插入排序(B) 冒泡排序(C) 堆排序(D) 归并排序 7．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（C ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 8．设一棵二叉树的深度为k，则该二叉树中最多有（D ）个结点。 (A) 2k-1 (B) 2k(C) 2k-1(D) 2k-1 9．在二叉排序树中插入一个结点的时间复杂度为（B ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 10．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满(B) 必须判别栈是否为空 (C) 判别栈元素的类型(D) 对栈不作任何判别 11．下列四种排序中（A ）的空间复杂度最大。 (A) 快速排序(B) 冒泡排序(C) 希尔排序(D) 堆 12．设某二叉树中度数为0的结点数为N0，度数为1的结点数为N l，度数为2的结点数为N2，则下列等式成立的是（C ）。 (A) N0=N1+1 (B) N0=N l+N2(C) N0=N2+1 (D) N0=2N1+l 13.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不 超过（A ）。 (A) log2n+1 (B) log2n-1 (C) log2n (D) log2(n+1) 14．数据的最小单位是（A ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 15．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（D ）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 一、单项选择题 1 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i O(m+n) 6、算法是（D ）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（A ）。 i=s=0; while(s 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i B 卷 一、单项选择题 1、若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( )。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 2、在长度为n的顺序表的第i(1≤i≤n+1)位置上插入一个元素，元素的移动次数( )。 A. n-i+1 B. n-I C. i D. i-1 3、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )。 A. 顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 4、若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为( )。 A. 4 B. 5 C. 6 D. 7 5、为查找某一特定单词在文本中的出现的位置，可应用的串运算是( )。 A. 插入 B. 删除 C. 串联接 D. 子串定位 6、已知函数sub(s,i,j)的功能功能是返回串s中的从第i个字符起长度为j的子串，函数scopy(s,1)的功能为复制串t到s。若字符串S=”SCIENCESTUDY“，则调用函数scopy(P,sub(S,1,7)))后得到 A. P=”SCIENCE” B. P=“STUDY” C. S=”SCIENGE” D. S=”STUDY” 7、三维数组A[4][5][6]按行优先存储在内存中，若每个元素占2个存储 单元，且数组中第一个元素的存储地址为120，则元素A[3][4][5]的存储地址为( )。 A. 356 B. 358 C. 360 D. 362 8、如右图所示广义表是一种（）。 A. 线性表 B. 纯表 C. 结点共享表 D. 递归表 9、下列陈述中正确的是( )。 A. 二叉树是度为2的有序树 B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点 D. 二叉树中最多只有两棵子树，并且有若右之分 10、n个顶点的有向完全图中含有有有向边的数目最多为 ( ) A. n-1 B. n C. n(n-1)/2 D. n(n-1) 11、已知一个有向图如下所示，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为( )。 A. a d b e f c B. a d c e f b C. a d c b f e D. a d e f c b 12、在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )。 A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 13、不可能生成右图所示二叉排序树的关键字的序列是( )。 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998 三、1 （5分）】 LinkedList Union(LinkedList la,lb) { pa=la->next; pb=lb->next; la->next=null; while(pa!=null && pb!=null) ∥当两链表均不为空时作 if(pa->data<=pb->data) { r=pa->next; pa->next=la->next; ∥将pa结点链于结果表中，同时逆置。 la->next=pa; pa=r; } else {r=pb->next; pb->next=la->next; ∥将pb结点链于结果表中，同时逆置。 la->next=pb; pb=r; } while(pa!=null) ∥将la表的剩余部分链入结果表，并逆置。 {r=pa->next; pa->next=la->next; la->next=pa; pa=r; } while(pb!=null) {r=pb->next; pb->next=la->next; la->next=pb; pb=r; } } 1）设有两个无头结点的单链表,头指针分别为ha,hb,链中有数据域data,链域next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则hb中的数据不归并到ha中,hb的链表在算法中不允许破坏。【南京理工大学1997 四、3（15分）】 LinkedList Union(LinkedList ha, hb)∥ha和hb是两个无头结点的数据域值递增有序的单链 ｛LinkedList 表，本算法将hb中并不出现在ha中的数据合并到ha中，合并中不能破坏hb链表。 la; la=(LinkedList)malloc(sizeof(LNode)); la->next=ha; pa=ha; pb=hb; pre=la; while(pa&&pb) if(pa->data数据结构经典例题
数据结构-数据结构历年考题及答案2
数据结构试题库答案
数据结构试题及答案(免费)
经典数据结构面试题(含答案)
数据结构试卷及答案2套
《数据结构》题库及答案
数据结构试题及答案
大数据结构经典复习题(仅供参考)
经典数据结构面试题(含答案)
数据结构试题及答案(10套最新)
数据结构经典例题
算法与数据结构题库与答案
数据结构试题集(包含答案 完整版)
数据结构典型例题
数据结构期末试题2及答案
数据结构考试题库含答案
数据结构经典算法试题
相关主题
文本预览