数据结构试卷A.doc

东莞理工学院城市学院（本科）试卷（A卷）2013-2014学年第一学期开课单位： 计算机与信息科学系 ，考试形式： 闭卷 ，允许带 入场科目：数据结构 班级：12软工 班 姓名： 学号：题序一二三四五六总 分得分评卷人一、 单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写下表中。1234567891011121314151. 在数据结构中，从逻辑上可以把数据结构分成（C）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D内部结构和外部结构2. 一个向量首元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。A110 B108 C100 D1203. 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（A）。A访问第i个结点（1in）和求第i个结点的直接前驱（2in） B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D将n个结点从小到大排序4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。A必须是连续的 B部分地址必须是连续的C一定是不连续的 D连续或不连续都可以5. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（A）。An B2n-1 C2n Dn-16. 在一个长度为n的顺序表中，在第i个元素（1in+1）之前插入一个新元素时须向后移动（B）个元素。An-i Bn-i+1 Cn-i-1 Di7. 在双向链表存储结构中，删除p所指的结点时须修改指针（A）。Ap-next-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;8. 若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（C）种情况。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，19. 对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（B）。AO(n) BO(n2) CO(nlog2n) DO(n3) 10. 从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（C）。A归并排序 B冒泡排序 C插入排序 D选择排序 11. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（C）。 A（100，80， 90， 60， 120，110，130） B（100，120，110，130，80， 60， 90）C（100，60， 80， 90， 120，110，130）D(100，80， 60， 90， 120，130，110)12. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。 A1/2 B1 C2 D4 13. 在下列存储形式中，（B）不是树的存储形式？A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法14. 广义表(a,b,c,d)的表头是（C），表尾是（B）。Aa B( ) C(a,b,c,d) D(b,c,d)15. 假设以行序为主序存储二维数组A=array1.100,1.100，设每个数据元素占2个存储单元，基地址为10，则LOC5,5=（B）。A808 B818 C1010 D1020二、 填空题(每空1分，共15分) 1. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J），则树中所含的结点数为_9 个，树的度为_ 3 _。2. 数据的物理结构主要包括 顺序结构 和 链式结构 两种情况。3. 为了能有效地应用HASH查找技术，必须解决的两个问题是 构建HASH树 和 解决冲突问题 。4. 一个算法的效率可分为 空间 效率和 时间 效率。5. 下面程序段的时间复杂度是 n2 。 s =0;for(i =0; in; i+) for(j=0;jkey=k)_return 1;_; else if (t-keyk) t=t-lchild; else_t=t-rchild;_;8. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。void bubble(int rn) for(i=1;i=n-1; i+)for(exchange=0,j=0; jrj+1)temp=rj+1;_;rj=temp;exchange=1;if (exchange=0) return；三、 判断题(下列各题，请在括号内对的打“”，错的打“”。每题1分，共5分) 1. 链表的物理存储结构具有同链表一样的顺序。（F）2. 一个广义表的表尾总是一个广义表。（T）3. 串是一种特殊的线性表，其特殊性体现在可以顺序存储。（F ）数据元素的类型是一个字符4. 二叉树中每个结点的两棵子树是有序的。（T）5. 抽象数据类型与计算机内部表示和实现无关。（T）四、 应用题（共6小题，共40分）1. （4分）在如下数组A中链接存储了一个线性表，表头指针为A 0.next，试写出该线性表。 A 0 1 2 3 4 5 6 7 data605078903440next35720412. （8分）已知一个AOV网如图所示。(1)试画出它的邻接矩阵和邻接链表。（顶点号递减出现在各邻接表中）(2)试写出按照拓扑排序算法得到的拓扑序列。V6V1V2 V4 V5 V3 3. （6分）请用克鲁斯卡尔算法构造下图所示网络的最小生成树。注：必须画出求解过程 14 V1 V4 V5 V2V3 V6 10 8 18 22 12 10 16 19 20 ，否则不给分。4. （6分）假设一棵二叉树的先序遍历序列为ABCDEFGHI，中序遍历序列为ADCEBFHIG。(1)画出该二叉树；（2）写出后序遍历结果序列。v0v1v2v3v4v5a1=3a2=2a5=4a7=2a4=2a8=3a6=2a3=35. （8分）AOE网G如下所示，求关键路径。（要求标明每个顶点和每个活动的最早发生时间和最迟发生时间，并写出关键路径）v1v2v3v4v5VeVla1a2a3a4a5a6a7a8ell-e关键路径：6. （8分）假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。(1)