中国矿业大学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 GEDFBHA3 假定存在数据表：（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, ABCDEFGH8.。

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 102543453077287952463acbdhgfe25706617 5358 126056874.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 kC E A H B JGIF M5.请描述在循环队列中，（队列用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 14A B C D E F G H I J10. 有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 14A B C D E F G H I J10. 有n个结点的无向完全图和有向完全图的边数分别为___ n(n-1)/2 , n(n-1) ____。

11. 图的深度优先遍历算法类似于树的先序。

12. 要从序列{1，3，5，7，9，11，13}中查找11，若采用折半查找法，则在 2 次比较后，才找到该数据。

13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下______最快，其时间复杂度为_________。