资源描述：
《06A数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、系班姓名：学号：一、单项选择题（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・算法描述）oD・链接指定位置）种情况。a,d,b,c吆级《数据结构》期末试卷（A卷）2007〜20
2、08学年度第一学期此卷使用班级：计算机科学与技术系06级科学技术本科装订说明：I、本试卷共4页，六道大题。II、请认真填写班级、姓名、学号。III、请将试卷的答案填写在答题卡上，写在试卷或其它载体上无效。)°5、假定一个链队的对首和对尾指针分别为front和rem*,则判断队空的条件为（B.front!二NULLA・front==rearC.rear!=NULLD・front==NULL6^表达式a*（b+c）・d的后缀表达式是（）oA.abcd*+・@B.abc+*d・@C.abc*+d・@D・・
3、+*abcd@7、下面程序段的时间复杂度为（）oi=l；while（i<=n）i二i*3;A.0（1）B・O（n*n）C・O（log3n））D.O（n）8、在数据的线性结构中，数据元素之间为（）的关系。A.0：0B・1：1C・1：nD・m：n9、有一个具有35个结点的完全二叉树，则该树的深度为（）oA.6B.7C・5D・810、从二叉搜索树中查找一个元素时，其时间复杂度大致为（）。A・O（n）B・0（1）C・Odogz"）D・O（i?）11、对于一个有向图，下面（）说法是正确的。A.每个顶点的入度等
4、于出度B.每个顶点的度等于其入度与出度和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、进行插入和删除运算，则最好采用()存储结构，若经常需要对线性表进行查找运算，则最好采用()存储结构。5、()又称为后进先出表，()又称为先进先出表。6、设元素3,b,c,d依次进栈，若要在输出端得到序列c,b,d,a,则应进行的操作序列为push(S,a),push(S,b),push(S,c),(),(),(),pop(S),pop(S)o7、按照二叉树的定义，具有三个结点的二叉树有()种。8、常用表示图的三种存储结构为：(),()和边集数组。9、图的()优先搜索遍历算法是一种递归算法，图的()优
6、先搜索遍历算法需要使用队列。10、若排序过程需要不断地进行内存和外存之间的数据交换，则称为()。三、判断题：(每小题1分，共10分)1、吋间复杂度是一个算法运行吋间的相对量度。2、顺序存储的线性表可以随机存取元素。3、使用三元组表示稀疏矩阵中的非零元素能节省存储空间。4、广义表(((a),b),c)的表头是((a),b),表尾是(c)o5、二叉树的遍历是指按照一定次序访问树中所有结点。6、在哈夫曼树中，权值最小的结点离根结点最近。7、已知一棵二叉数的前序和后序序列，可惟一确定一颗二叉树。8、邻接矩阵
7、适合用来表示稠密图。9、折半查找只能在有序的顺序表上进行，而不能在有序链表上进行。10、内部排序是指排序过程在内存中进行的排序。四、运算题：(每小题5分，共计20分)1、假定一颗二叉树的广义表表示为a(b(,d(g)),c(e,f)),分别写出对它进行先根、中根、后根、按层遍历的结果。先根：中根：后根：按层：2、已知一组元素为(10,7,38,32,20,50,45,60)⑴试画出按元素排列顺序输入生成的一棵二叉搜索树的图示；⑵试画出按元素排列顺序输入生成的一个大根堆的图示。3、六个带权结点，其权值
8、分别为4,5,6,9,10,11,试以它们为叶子结点构造一颗哈夫曼树(请按照每个节点的左子树根结点的权小于等于右子树根结点的权的次序构造)，并计算带权路径长度WPLo4、已知一个带权图的顶点集V和边集G分别为：V二{0,1,2,3,4,5,6,7};G二{(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(2,6)12,(3,5)9,(3,6)10,(4,6)18,(5,7)20};按照克鲁斯卡尔算法求出最小生成树时所得到的各边的
