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. frontrearB. frontNULL C. rearNULLD. frontNULL 表达式a*（bc）-d的后缀表达式是（ A. a b c d * - C・ a b c * d ・ 下面程序段的时间复杂度为 il； while（in） ii*3; A. 0（1） B. O（n*n） 6、 7、 8、 9、 10、 ）。 ）。 C. Olog3n D・ On 的关系。 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・n1C・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 0,25, 0,32, 1,56 ,2,325, 2,413, 2,612, 3,59, 3,610, 4,618, 5,720}; 按照克鲁斯卡尔算法求出最小生成树时所得到的各边的次序写出各 条边。 五、算法分析题本题共计16分 1、分析下面算法，回答问题。4分 已知程序段 int i, pl,sO; foril;in;i {p*i; sP； } 在上面程序段中 ssp语句的执行次数为 该程序段的时间复杂度为 2、程序填空4分 下面算法是应用栈把一个长整型数num转换为一个r进制数输出。 void trans long num, int r {struct stacksq a； initstack a； while num0 {int k pusha9k; num/r;} whilestackemptya printfW; } 3、分析下面算法，回答问题。4分 int functionint A[],int p { ifpO return 0; else return A[n-l]*functioiiA,p-l; } 该算法的功能是实现 4、分析下面算法，回答问题。4分 void bubblesortelemtype a[], int n {elemtype x; int i,j,flag; foril;in-1