数据结构(C)2007答案.doc

承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业 班级 学号 学生签名： 华东交通大学20082009学年第一学期考试卷试卷编号：（A）卷 数据结构(C) 课程 课程类别：必 闭卷（） 考试日期：_题号一二三四五六七八九十总分累分人签名题分20304010100得分考生注意事项：1、本试卷共 8 页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分评阅人 一、选择题(每题2分，共20分)1以下不属于算法要素的是（ ）。A. 有穷性B. 可行性C. 可读性D. 输入2顺序表随机访问元素ak 基本操作的时间复杂度为（ ）。A. O( 1 )B. O( n )C. O( logn )D. O( k )3图的广度优先搜索算法中定义的辅助数据结构为（ ）A. 队列B. 栈C. 邻接表D. 二叉树4求串T在串S中首次出现位置的基本操作叫做（ ）A. 求子串B. 模式匹配C. 串替换D. 串连接5广义表L = ( ( apple, pear ), ( banana, orange ) ) 的表尾是（ ）A. ( apple, pear )B. ( ( apple, pear ) )C. ( banana, orange )D. ( ( banana, orange ) )6nn阶对称矩阵压缩存储到（ ）个元的空间中。（考试范围之外）A. n2B. n2/2C. n(n+1)D. n(n+1)/27在一棵含有2009个结点的完全二叉树中，叶子结点有（ ）个。A. 1001B. 1003C. 1005D. 10078由权值为7，19，2，6，32，3，21，10的结点构成的赫夫曼树的带权路径长度为（ ）A. 271B. 261C. 241D. 2319有向图中所有顶点的入度之和为n，则出度之和为（ ）A. n+1B. nC. n-1D.n/210在有序表( 1, 5, 8, 9, 12, 16, 23 )中折半查找关键字16的比较次数是（ ）A. 2B. 3C. 4D. 5得分评阅人二、填空题(每空2分，共30分)1线性表的顺序表示称为_顺序表_。28个顶点的连通图最多有_28_条边，最少有_7_条边。3含有9个叶子结点的3阶B-树中至少有_个非叶子结点。（考试范围之外）4广义表 ( ( ( ) ), a, ( ( b, c ), ( ), d ) ) 的深度为_3_。5按低下标优先存储整数数组A9358时，第1个元素a0000的存储地址是0，每个整数占4个字节，a3125的地址是_。（考试范围之外）6设串S = I AM A WORKER!，T = GOOD，Concat( SubString( S, 6, 2 ), Concat( T, SubString( S, 7, 6 ) ) = A GOOD WORKE 。7总长为n的顺序循环队列中，队头指针为front，队尾指针为rear，队列满的条件为_(rear+1) mod n =front_，队列空的条件为_front=rear_。8下图中的AOE-网关键活动为 _，_，_，。9下图中的有向图，从顶点A出发进行广度优先遍历的顶点序列为_ABCDEFGHI_。10p是指向单链表L的中间结点的指针，补充下列删除p的后继结点的程序段。s = p-next;_p-nexet=s-next;_free( s );11程序段for( i=0; in; i+ ) for( j=0; jnext;if(p!=NULL) q=p-next;p-next=NULL;while (q!=NUL