数据结构(c)2007答案

《数据结构(c)2007答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2008—2009学年第一学期考试卷试卷编号：　　　　（A）卷数据结构(C)课程课程类别：必闭卷（√）考试日期：____________题号一二三四五六七八九十总分累分人签名题分20304010100得分考生注意事项：1、本试卷共8页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分评阅人一、

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.(bana

3、na,orange)D.((banana,orange))6．n×n阶对称矩阵压缩存储到（）个元的空间中。（考试范围之外）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,1

4、2,16,23)中折半查找关键字16的比较次数是（）A.2B.3C.4D.5第4页共4页得分评阅人二、填空题(每空2分，共30分)1．线性表的顺序表示称为___顺序表____。2．8个顶点的连通图最多有__28_条边，最少有__7___条边。3．含有9个叶子结点的3阶B-树中至少有_____个非叶子结点。（考试范围之外）4．广义表((()),a,((b,c),(),d))的深度为__3__。5．按低下标优先存储整数数组A9×3×5×8时，第1个元素a0000的存储地址是0，每个整数占4个字节，a3125的地址是____________

5、_。（考试范围之外）6．设串S=‘IAMAWORKER!’，T=‘GOOD’，Concat(SubString(S,6,2),Concat(T,SubString(S,7,6))=AGOODWORKE。7．总长为n的顺序循环队列中，队头指针为front，队尾指针为rear，队列满的条件为______(rear+1)modn=front____，队列空的条件为__front=rear__。8．下图中的AOE-网关键活动为__，____，________，。9．下图中的有向图，从顶点A出发进行广度优

6、先遍历的顶点序列为_ABCDEFGHI___。10．p是指向单链表L的中间结点的指针，补充下列删除p的后继结点的程序段。s=p->next;__p->nexet=s->next;____free(s);11．程序段for(i=0;i

7、森林对应的二叉树。参考答案：3．进栈序列为ABC，写出所有可能的出栈序列。参考答案：可以通过穷举所有可能性来求解：①A入A出，B入B出，C入C出，即ABC；②A入A出，B、C入C、B出，即ACB；③A、B入，B出，C入C出，A出即BCA；④A、B入，B、A出，C入C出，即BAC；⑤A、B、C入，C、B、A出，即CBA；合计有5种可能性。4．按照四则运算加、减、乘、除和幂运算(∧)的优先关系的惯例，将表达式A－B×C÷D＋E∧F转换为前缀和后缀表达式。（考试范围之外）5．画出3个结点的二叉树的所有形态。5种形态6．二叉树的先序序列为AB

8、CDEF，中序序列为CBAEDF，画出该二叉树。参考答案：第4页共4页7．按下表中关键字的顺序构造一棵二叉平衡树。（考试范围之外）(5,4,8,1,9,7,6,2,11,12,10,3)8．选取哈希函数H(k)=(3k)