数据结构-数据结构历年考题及答案2

1、中国矿业大学2011-2012学年数据结构试卷(A卷)(考试时间：100分钟)一.填空(每空2分，共40分)1.数据结构式具有相同性质的数据元素的(1)。2.通常程序在调用另一个程序时，都需要使用一个(2)来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址(基址)为1000,在行优先存储和列优先存贮情况下A5,5的存储地址分别为_ (3) ,(4)。4.完全二叉树第4个节点的父节点是第(5)节点,左孩子是第(6)个节点。如果该二叉树有10层,则共有(7)个节点。5.请描述在循环队列Q

2、中，队头和队尾指针分别由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为开头的输出序

3、列是(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请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。(要求使用图画出每一步过程)。3假定存在数据表：（3,4, 5, 7,24, 30, 54, 63, 72, 87, 95, 102）,请解决如下问题

4、：假设哈希函数为：H（key）=key mod 13，用该哈希函数将数据表存入长度为13的哈希表，（利用线性探测）请画出存放状态；4森林和二叉树的转换，画出和下列二叉树相应的森林设要将序列（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, BDCE

5、AFHG, ABCDEFGH（每一步过程）538.9.231或213 , 31210. n(n-1)/2。11. 2。12.快速排序。二. 简答题（每题10分，共50分）1.图不唯一WPL=2292.3.01234567891011121025434530772879524635.(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); /建立工

6、作队列while(!QueueEmpty(Q)(DeQueue(Q,p);if(!p) flag=1; /如果孩子为空，则说明左孩子为空else if(flag) return 0;else(EnQueue(Q,p-lchild);EnQueue(Q,p-rchild); /不管孩子是否为空，都入队列)/whilereturn 1;)/IsFull_Bitree中国矿业大学2011-2012学年数据结构试卷(B卷)(考试时间：100分钟)一.填空(每空2分，共40分)1.数据结构是指数据及其相互之间的 。当结点之间存在M对N (M N)的联系时，称这种结构为2.通常程序在调用另一个程序时，都需

7、要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储 空间以及返回地址。4.3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址(基址)为1000,在行优先存储和列优先存贮情况下A5,5的存储地址分别为,。4.设目标T= abccdcdccbaa”,模式P= cdcc”,则第 次匹配成功。5.请描述在循环队列中，(队列用Q表示，队头和队尾指针分别由front和rear表示，该队列有MS存储空间)，判断队空和队满的条件分别分： ,。6.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复 杂度为。7.在具有

8、n个单元的循环队列中，队满时共有 个元素。8.深度为k的二叉树的结点总数，最多为 =个。最少为个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为。01234567891011121314ABCDEFGHIJ10.有n个结点的无向完全图和有向完全图的边数分别为,。11.图的深度优先遍历算法类似于树的。12.要从序列1 , 3, 5, 7, 9, 11 ,13中查找11,若采用折半查找法，则在 次比较后，才找到该数据。13.在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下 最快，其时间复杂度为。二简答题：(每题10分，共50分)1.假设9个字母为：A B C D

9、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=,;若存储它采用邻接表，试写出临界表。并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的， 按拓朴排序算法进行排序，试给出得到的拓朴排序的序列。3.int Prime(int n) int i=1;int x=(int) sqrt(n);while (+ix) return 1;else return 0; (1)指出该算法的功能；(2)该算法的时间复杂度是多少？请

10、说明。4.假定存在数据表：(3, 4, 5, 7, 24, 30, 54, 63, 72, 87, 95, 102),请解决如下问题：1)假设哈希函数为：H(key)=key mod13，用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)请画出存放状态；2)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；5设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则写出希尔(shell )排序的过程，初始步长为4三程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：

11、1）函数名使用给出的函数名，参数SSTable表示序列，使用一维数组存放，下标从0开始，value表示要查找的 值；2）如果找到，则函数返回值为该数在序列中的位置，否则返回-1;3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。中国矿业大学2011-2012学年数据结构试卷（B卷）（答案）专业：班级：序号：姓名：一.填空（每空2分，共40分）1.联系，图（或图结构）。2.通常程序在调用另一个程序时，都需要使用一个栈 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基

12、址）为1000,在行优先存储和列优先存贮情况下A5,5的存储地址分别为_1270 , 1210_ o4.设目标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） _o7.在具有n个单元的循环队列中，队满时共有n-1个元素。8.深度为k的二叉树的结点总数，最多为2七1个。最少为_k_个。9二叉树中元素按照顺序存储方式存放在如下一

13、维数组中，则结点G所在层次为3。01234567891011121314ABCDEFGHIJ10.有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,

14、 16, 9 , 8。试为这9个字母设计哈夫 曼编码。并计算其带权路径长度。116684834342820997 85 42.拓朴排序为：4 3 6 5 7 2 13. (1)判断n是否是素数(或质数)I(2) 0(、n)4.假定存在数据表：(3,4,5,7,24,30,54,63,72, 87,95,102),请解决如下问题：1)假设哈希函数为：H(key)=key mod13，用该哈希函数将数据表存入长度为13的哈希表，(利用线性探测)请画出存放状态；012345678910111210254345307728795246324,63,102共计比较了3次2)请按比较顺序写出查找102的过

15、程中比较的数值，以及比较的次数；5设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则写出希尔(shell)排序的过程，初始步长为4ShellP, 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表示要查找的 值；

16、2)如果找到，则函数返回值为该数在序列中的位置，否则返回-1;3)不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。见课本Int search(array ST, Key key)Low =1; high=high;While(lowhigh)Mid=(low+high)/2;If(key=arraymid.key) return mid;Else if (keyprior-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

17、Vi6. 17like coffee andchild（利用线性探测）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),按哈夫曼规则：均码为:_A ：1100 B00 C：11110 IT1110 F10 F： 11111 G:01 H:11012请对下图的无向带权图：写出它的邻接矩 阵，并按普里姆算法求其最小生成树【(2,3 ), 6, (7,10)】，19, 21,32解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种(类)

18、！邻接矩阵为:0 4 34 0 5 5 93 5 0 555507 65 4970 36 3 02520 6其后续序列为：BHECIGFAD5设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则:冒泡排序_趟扫描的结果是HCQPAMSRDFXY ;34初始步长为4的希尔（shell ）排序一趟的结果是P A C S Q H F X R D M Y二路归并排序一趟扫描的结果是H Q CYAP M S D RFX快速排序_趟扫描的结果是FHCDPAMQRSYX堆排序初始建堆的结果是ADCRFQMSYPHX三.程序题（10分）int

19、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); /不管孩子是否为空，都入队列)/whilereturn 1;)/IsFull_Bitree计算机学院2010-2011学年第一学期数据结构试卷（B卷）（考试时间：100分钟）专业：班级：

20、序号：姓名：一.填空（每空2分，共40分）1.双向循环链表中，结点的前驱指针域和后继指针域分别用prior和next表示，删除P指针所指向的结点，则其 基本操作为,。2.通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储 空间以及返回地址。3.有6行8列的二维数组A,每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000,在行优先存储和列优先存贮情况下A5,5的存储地址分别为,。4.设目标T= abccdcdccbaa”,模式P= cdcc”,则第 次匹配成功。5.请描述在循环队列中，（队列用Q表示，队头和队尾指针分别由

21、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所在层次为01234567891011121314ABCDEFGHIJ10.有n个结点的无向完全

22、图和有向完全图的边数分别为,。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.森林和二叉树的转换，画出和下列二叉树相应的森林1)假设哈希函数为：H(key)=key mod13，用该哈希函

23、数将数据表存入长度为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)。要求：102),请解决如下问题:1)函数名使用给出的函数名，参数SSTable表示序列，使用一维数组存放，下标从0开始，value表示要查找的34342820值；2)如果

24、找到，则函数返回值为该数在序列中的位置，否则返回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,每个元素用相邻

25、的6个字节存储，存储器按字节编址，已知A的起始存储地址(基址)为1000,在行优先存储和列优先存贮情况下A5,5的存储地址分别为_1270 , 1210_ o4.设目标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”，请写出下列函数的结果

26、：StrLength(s)=_22_; Concat(SubString(s,3,15), SubString(t,12,6)= _ like coffee and child_。7.在具有n个单元的循环队列中，队满时共有n-1个元素。8.深度为k的二叉树的结点总数，最多为2七1个。最少为_k_个。9二叉树中元素按照顺序存储方式存放在如下一维数组中，则结点G所在层次为3。01234567891011121314ABCDEFGHIJ10.有n个结点的无向完全图和有向完全图的边数分别为n(n-1)/2 , n(n -1)。11.图的深度优先遍历算法类似于树的先序 。12.要从序列1 , 3, 5,

27、 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个字母设计哈夫 曼编码。并计算其带权路径长度。1166848-1；2.森林和二叉树的转换，画出和下列二叉树相应的森林G j3.使用Prim算法求下图中最小生成树。5)假设哈希函数为：H(key)=key mod13，用该哈希函数

28、将数据表存入长度为13的哈希表，(利用线性探测)请画出存放状态；012345678910111210254345307728795246324,63,102共计比较了3次6)请按比较顺序写出查找102的过程中比较的数值，以及比较的次数；5设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列，则：(1)写出冒泡排序的过程；(2)写出希尔(shell )排序的过程，初始步长为4ShellP, 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

29、 M P Q R S Y三程序题请写出折半查找方法的函数Search_Bin( SSTable S, value v)。要求：1)函数名使用给出的函数名，参数SSTable表示序列，使用一维数组存放，下标从0开始，value表示要查找的18161513B e95, 102),请解决如下问题:值；2)如果找到，则函数返回值为该数在序列中的位置，否则返回-1;3)不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。见课本Int search(array ST, Key key)Low =1; high=high;While(lowhigh)Mid=(low+high)/2;If(key=a

30、rraymid.key) return mid;Else if (keyarraymid.key) high=mid-1;Else low=mid+1;return 0计算机学院2009-2010学年第一学期数据结构试卷(A卷)(考试时间：100分钟)一.单项选择(每小题2分，共20分)1.下面程序段的时间复杂度是。for(i=0;in;i+)for(j=1;jm;j+)Aij=0;A.O(n)B. O(m+n+1)C. O(m + n)D. O(m*n)2.在n个结点的顺序表中，算法的时间复杂度是O (1)的操作是。1)访问第i个结点(1vi n)和求第i个结点的直接前驱(2vi n)2)在

31、第i个结点后插入一个新结点(1v i n)3)删除第i个结点(K i 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. iB. n-iC.n-i+1D.不确定5.数组Qn用来表示一个循环队列，f为当前队列头元素的前一位置，r为队尾素的位置，假定队列中元素的 个数小于n,计算队列中元素的公式为。A. r fB. (n + f r)