数据结构模拟2.doc

系 专业 班级 姓名 考号 （密 封 线 内 不 要 答 题） 南阳理工学院 课程: 数据结构(A卷)评卷人（签名） 复核人（签名） 题号一（20）二（30）三（50）合 计得分 一、单项选择题：（每题2分，共20分）1、数据的四种基本逻辑结构是指( D ) A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 2.下列关于栈和队列的叙述中，不正确的是( C ) 。A.它们是n个结点的有穷序列 B.都可以为空。 C.每一个结点有且仅有一个前趋和一个后继 D.结点间的逻辑关系是1:1的联系 3、.若进栈序列为a,b,c,d,进栈过程每个元素只能进栈出栈一次，则不可能的一个出栈序列是（ B ）。A.c,d,b,a B. a,d,b,c C. b,d,c,a D. c,b,a,d 4利用二叉链表存储树，则根结点的右指针是（ C ）。A指向最左孩子 B指向最右孩子 C空 D非空5、一个有序表为9，12，34，45，62，75，82，95，100，利用折半查找查找key=100时需要_A_次比较后查找成功。A. 4 B. 3 C. 2 D. 56、已知有向图G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=,G的拓扑序列是（A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V77、假定一棵二叉树的结点数为200,它的最小高度 8_A_ 。A. 8 B. 10 C. 7 D. 118、 一个n*n的三角矩阵经过压缩后所占的空间是（C ）An+1/2 Bn*(nl)/2 Cn*(nl)/2 Dn*n/2 9、在对一组记录(20,40,96,100,15,72,140,45,68)按从小到大进行冒泡排序时，第一趟需进行相邻记录交换的次数为（D ） A.6 B.5 C.3 D.410. n个顶点，e条边的无向图采用邻接表存储时，所分配的弧结点数为（ C ）个。An B. n+e C. 2e D. e二、填空题（每空2分，共30分）1. 设a、b、c,d都是串名，akexue，bjiaoyu，cfangfa。则求联接操作CONCAT(&d,SUB(a,3,3)， SUB(c,3,2)结果为 _xueng_ 。2. 一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是_ 。3. 有一组叶子结点的权值为WG=7，19，2，6，32，3，21，10，则所建Huffman树的树高是_ 6 ，带权路径长度WPL为_ 。系 专业 班级 姓名 考号 （密 封 线 内 不 要 答 题） 8566101512781115bacdifegh4. n个顶点的强连通图，其弧的条数至少为_n_ 。n个顶点的连通无向图，其边的条数至少为_n-1_ 。5. 设二维数组A0.30,0.20, 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A25,18的存储地址为_2372 _。6. 广义表(a,(a,b),d,e,(i,j),k)的长度是 5 ，表尾是_ _ (a,b),d,e,(i,j),k) 。7. 串的两种最基本的存储方式是_定长存储_ 、_堆存储_ 。 8. 循环队列的引入，目的是为了克服_假溢出_ 。9. 最大容量为n的循环队列，队尾指针是rear，队头是front，则入队时rear=_(front+1)%n _ 。10.已知一无向图G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)现用某一种图遍历方法从顶点a开始遍历图，如要得到的序列为abecd，则需要采用的是_深度_ 遍历方法；如要得到的序列为abcde，需要采用的是_广度_ 遍历方法。三、应用题。（共50分）1、已知下面是一个工程的AOE网络，请按要求回答下面的问题。（10分）（1）若能顺利进行则请计算从工程开始到结束需要的时间（4分）（2）请画出此AOE网络工程图的关键路径。（6分）1、（1）416515acieh（2）15ABCDEFGHIVE08662118292641VL0116721193026412、已知一棵二叉树的先序遍历序列为：abcdefgh，。中序遍历序列为：cdfehgba请画出这棵二叉树并写出它的后序遍历的序列。（10分：其中画出树8分，写出序列2分）系 专业 班级 姓名 考号 （密 封 线 内 不 要 答 题）abdcegfh 后序序列为：f h g e d b a3、对下列关键字序列进行快速排序(从小至大)key= (48, 88, 65, 95, 50, 13, 27, 62)要求:（1）描述快速排序的算法思想。（4分）（2）画出排序过程示意图。（6分）（1）一次快速排序是通过选择一个支点，把一个无序的序列划分为两个序列，左侧序列小于支点，右侧序列大于支点，然后再分别对两个序列进行下一次快速排序，直至序列长度=1结束。基本思想正确为4分第一趟：（27，13），48，（95，50，65，88，62）第二趟：13，27，48，（62，50，65，88），95第三趟：13，27，48，50，62，（65，88），95第四趟：13，27，48，50，62，65，88，95排序过程正确为6分，无过程不得分。4、已知一组关键字为（19,14,23,01,68,20,84,27,55,11,28,78）按哈希函数 H(Key)=Key MOD 13和线性探测再散列处理冲突的方法在地址空间A0.15中构造哈希表。（10分）解：H(KEY)=KEY MOD 13 处理冲突方法为：H(KEY)=(H(KEY)+Di) MOD M (M=16)H(19)=6 H(14)=1 H(23)=10H (01)=1(冲突) H(01)=2 H(68)=3 H(20)=7H(84)=6(冲突) H(84)=7 H(27)=1(冲突) H(27)=4H(55)=3(冲突) H(55)=5 H(11)=11 H(28)=15 H(78)=078140168275