06A数据结构试卷
蚯级《数据结构》期末试卷(A卷) 2007〜2008学年度 第一学期 此卷使用班级:计算机科学与技术系06级科学技术本科 系班 姓名: 学号: 装订 说明:I、本试卷共4页,六道大题。 II、请认真填写班级、姓名、学号。 IIL请将试卷的答案填写在答题卡上,写在试卷或其它载体上无效。 一、单项选择题(12小题,每小题2分,共24分) 1、数据的()包括查找、插入、删除、更新、排序等操作类型。 A.存储结构B.逻辑结构 C.基本运算 常见数据的存储结构包括顺序、索引、散列和( A.向量B.数组C.集合 队列的删除操作在()进行。 A.队首B.队尾C.任意位置 若让元素a, b, c, d依次进栈,则出栈次序不可能出现( A.c,b,a,dB.b,a,d,cC.d,c,b,aD. 2、 3、 4、 D. )。 D. 算法描述 链接 指定位置 )种情况。 a,d,b,c 5、假定一个链队的对首和对尾指针分别为front和rear,则判断队空的条 件为( A. front==rearB. front!=NULL C. rear!=NULLD. front==NULL 表达式a*(b+c)-d的后缀表达式是( A. a b c d * + - @ C・ a b c * + d ・@ 下面程序段的时间复杂度为 i=l; while(i<=n) i=i*3; A. 0(1) B. O(n*n) 6、 7、 8、 9、 10、 )° )。 )。 C. O(log3n)) D・ O(n) )的关系。 D・ m :] 在数据的线性结构中,数据元素之间为( A. 0 : 0 B. 1 : 1 C. 1 : n 有一个具有35个结点的完全二叉树,则该树的深度为( A. 6B. 7C. 5D. 8 从二叉搜索树中查找一个元素时,其时间复杂度大致为( A. O(n)B. 0(1)C. O(log2n)D. O(n2) 对于一个有向图,下面()说法是正确的。 A.每个顶点的入度等于出度B.每个顶点的度等于其入度与出度和 n )o )° C.每个顶点的入度为零D.每个顶点的出度为零 12、若要把n个顶点连接为一个连通图,则至少需要()条边。 A・nB・n+1C・D・2n 二、填空题:(每空1分,共20分) 1、数据的逻辑结构被分为:()、()、()、 和()四种。 2、已知广义表 L=((a,b),(c,(d,(e))),f) 则表达式:head(tail(head(tail(L))))的运算结果是:()。 3、线性表是具有相同特性数据元素的一个(),该表中所含元 素的个数叫做线性表的()。 4、若经常需要对线性表进行插入和删除运算,则最好采用()存储 结构,若经常需要对线性表进行查找运算,则最好采用()存 储结构。 5、()又称为后进先出表,()又称为先进先出表。 6、设元素a, b, c, d依次进栈,若要在输出端得到序列c, b, d, a,则 应进行的操作序列为 push(S,a) , push(S,b) , push(S,c), (),(),(),pop(S), pop (S)o 7、按照二叉树的定义,具有三个结点的二叉树有()种。 8、常用表示图的三种存储结构为:(),()和边集数组。 9、图的()优先搜索遍历算法是一种递归算法,图的()优先 搜索遍历算法需要使用队列。 10、若排序过程需要不断地进行内存和外存之间的数据交换,则称为()。 三、判断题:(每小题1分,共10分) 1、时间复杂度是一个算法运行时间的相对量度。 2、顺序存储的线性表可以随机存取元素。 3、使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 4、广义表(((a) ,b) ,c)的表头是((a) ,b),表尾是(c)。 5、二叉树的遍历是指按照一定次序访问树中所有结点。 6、在哈夫曼树中,权值最小的结点离根结点最近。 7、已知一棵二叉数的前序和后序序列,可惟一确定一颗二叉树。 8、邻接矩阵适合用来表示稠密图。 9、折半查找只能在有序的顺序表上进行,而不能在有序链表上进行。 10、内部排序是指排序过程在内存中进行的排序。 四、运算题:(每小题5分,共计20分) 1、假定一颗二叉树的广义表表示为a(b(,d(g)),c(e,f)).分别写出对它进行先 根、中根、后根、按层遍历的结果。 先根:中根: 后根:按层: 2、已知一组元素为(10, 7, 38, 32, 20, 50, 45, 60) ⑴试画出按元素排列顺序输入生成的一棵二叉搜索树的图示; ⑵试画出按元素排列顺序输入生成的一个大根堆的图示。 3、六个带权结点,其权值分别为4, 5, 6, 9, 10, 11,试以它们为叶子 结点构造一颗哈夫曼树(请按照每个节点的左子树根结点的权小于等 于右子树根结点的权的次序构造),并计算带权路径长度WPLO 4、已知一个带权图的顶点集V和边集G分别为: V={0,l,2,3,4,5,6,7}; G={(0,l) 按照克鲁斯卡尔算法求出最小生成树时所得到的各边的次序写出各 条边。 五、算法分析题:(本题共计16分) 1、分析下面算法,回答问题。(4分) 已知程序段: int i, p=l,s=O; for(i=l;i<=n;i++) {p*=i; s+=P; } 在上面程序段中: s=s+p语句的执行次数为: 该程序段的时间复杂度为: 2、程序填空:(4分) 下面算法是应用栈把一个长整型数num转换为一个r进制数输出。 void trans (long num, int r) {struct stacksq a; initstack ( num/=r;} while(!stackempty(a)) printfW ); } 3、分析下面算法,回答问题。(4分) int function(int A[],int p) { if(p==O) return 0; else return A[n-l]*functioii(A,p-l); } 该算法的功能是实现: 4、分析下面算法,回答问题。(4分) void bubblesort(elemtype a[], int n) {elemtype x; int i,j,flag; for(i=l;i<=n-1