数据结构地理信息0812(B).doc

学院： 专业班级： 姓名： 学号： 装 订 线 内 不 要 答 题 浙江林学院 2009 2010 学年第 一 学期考试卷（B卷）课程名称： 数据结构 课程类别： 必修 考试方式： 闭卷 注意事项：1、本试卷满分100分。2、考试时间 120分钟。题号一二三四五六七八得分得分评阅人一、单项选择题（在每小题的四个备选答案中，选出一个正确答案，每小题1分，共10分）1. 数据在计算机中的存储结构有两种，即_.A.顺序存储结构和链式存储结构 B.顺序表和链表C. 数组和链表 D.数组和指针2. 数据结构的要素有 。 A. 数据定义，数据关系定义，处理数据的方法定义。 B. 数据定义，数据关系定义。 C. 数据定义。 D. 处理数据的方法定义。3. 算法的特性有:_ A. 有穷性、确定性、可行性、输入、输出。B. 有穷性、确定性C. 输入、输出D. 确定性、可行性、输入4. 队列的操作特点是 。 A. 同数组一样 B. 同栈一样 C. 同树一样 D. 队首删除队尾插入5. 由权值分别为13，28，10，42，86的叶子结点生成一棵哈夫曼树，则其中非终端结点数为( )。A. 2 B. 3C. 4 D. 56. 二叉树有几种基本形态 。 A. 3种 B. 4种 C. 2种 D. 5种7. 下面程序的时间复杂度为_ int i=1;k=0;n; dok=k+10*i;i=i+; while(i!=n); A. O(n) B. O(n*n)C. O(nlogn) D. O(n*n+2n)8. 深度为5的二叉树至多有_个节点 A. 32 B. 31 C. 16 D.329一二叉树，如果其终端节点数为5，则度为2的节点数为_ A. 2 B. 3 C. 4 D.510. 在一个单链表中，已知 q 指向 p 所指向结点的前驱结点，若在 q，p 所指结点之间插入一个 s所指向的新结点，则执行的操作是_ A. q - next=s- next ；s- next=p；B. q - next=s；s- next=p；C. p - next=s；s- next=q； D. s- next=p - next；p - next=s；二、判断(对的打,错误打, 101 = 10 分)1、 类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。( )2、 往顺序表中插人一个元素，平均要移动大约一半的元素。( )3、 结点的指针域为空，说明该字段中没有存放任何信息。( )4、 在n个元素进栈后，它们的出栈顺序和进栈顺序一定正好相反。( )5、 链表是一种线性结构。( )6、 赫夫曼树一定是满二叉树。( )7、 对队列进行删除操作，只能在队首进行. ( )8、 对二叉排序树进行中序遍历可对树中的数据排序。( )9、 一般情况下，在第i(1= i =n) 个元素之前插入一个元素，需要将第n个到第i个元素向后移动一个位置，移动元素的个数为n-i+1( )10、快速排序算法是不稳定的( )三、数据结构设计（10分）问题描述：我校拟开发在校人员信息管理系统，主要管理学生成绩信息，老师工资课程信息，行政人员工资信息等,请设计合适的数据结构四、数据结构概念问题分析（10分）已知如图所示的图，请给出该图的14625 每个顶点的入/出度；（2分）3 邻接矩阵；（4分） 邻接表；（4分）五简答（每题2分，共10分） 1、数据结构的基本类型 2、栈 3、中序遍历二叉树 4、广度优先搜索 5、哈夫曼树六、综合（每问题10分，共50分）问题一：一无向图的邻接矩阵用二维数组表示为0，1，0，1，0；1，0，1，0，1；0，1，0，1，1；1，0，1，0，0；0，1，1，0，01、 请画出该图（按顺序给图顶点编号）2、对该图从顶点v1（顶点序号同矩阵中的行序号相同）进行深度优先遍历，遍历结果是3、若对图中各边依次赋予权值：= 5, = 9,=3,=7，V2，V5=6，V3，V5=4，试画出该带权图的最小生成树 问题二：给定4个权值 7，5，2，41、以此权值构造哈夫曼树 2、将该树各节点进行标记，然后分别进行前序、中序遍历问题三：一整数顺序表的存储结构为： typedef int ElemType;typedef int Status;typedef struct ElemType *elem;/储存数据 int length;/线性表长度 int listsize;/最大值SqList; 顺序表初始化函数为： Void InitList(SqList &L)L.elem = (ElemType *)malloc(sizeof(ElemType)*LIST_INIT_SIZE);L.length = 0;L.listsize = LIST_INIT_SIZE; /初始化线性表若顺序表中已经生成数据，试设计一算法将顺序表中的整数打印在屏幕上问题四：一系列整数存放在单链表中，单链表的存储结构如下： typedef int elemtype;typedef struct LNODEelemtype data;struct LNODE *next;LNODE,*linklist;生成链表节点数据的算法为： void creatlist_l(linklist &L,int n) int i;linklist p;L=(linklist)malloc(sizeof(LNODE);L-next=NULL; printf(请输入链表的n个数据 n/);for(i=n; i0; -i)p=(linklist)malloc(sizeof(LNODE);scanf(%d,&p-data);p-next =L-next ;L-next=p;设计一算法，统计链表中大于3的数据的个数问题五：一二叉树采用链式存储，其数据结构为： typede