10年数据结构期末考试a卷.doc

专业________________学号__________________姓名__________________班级____________________ 密 封 线 北京电子科技学院2009～2010学年第二学期 0821~0822 班 数据结构 期 末 考 试 试 卷（闭卷）（Ａ卷） 题 目 一 二 三 四 五 六 七 八 九 十 十一 十二 总分数 分 数 评卷人 一、选择题（每小题2分，共10分） 1．在数据结构中，从逻辑上可以把数据结构分为 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 2．对于顺序表的优缺点，以下说法错误的是 。 A．无需为表示结点间的逻辑关系而增加额外的存储空间 B．插入和删除操作较方便 C．可以方便的随机存取表中的任一结点 D．由于顺序表要求占用连续的空间，存储分配只能预先分配 3．设有一顺序栈已经含有3个元素，如下图所示，元素a4正等待入栈。以下序列中不可能出现的出栈序列是 。 a1 a2 a3 A．a3, a2, a4, a1 B．a3, a1, a4, a2 C．a3, a4, a2, a1 D．a4, a3, a2, a1 4．对采用折半查找法进行查找操作的查找表，要求按 方式进行存储。 A．顺序存储 B．链式存储 C．顺序存储且结点按关键字有序 D．链式存储且结点按关键字有序 5．以下不属于选择排序方法的是 。 A．冒泡排序 B．树形选择排序 C．堆排序 D．直接选择排序 二、填空题（每小2分，共10分） 1．数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容： ， 和对数据施加的操作。 2．下列程序段的时间复杂度是 。 s=0; for (i=1;i=n; i++) for (j=1;j=i; j++) s=s+B[i,j]; sum=s; 3．在具有n个单元的循环队列中，队满时共有 个元素。 4．一个n(n的对称矩阵，如果以行或者列为主序存入内存，则其需要的存储空间容量为 。 5．广义表运算式 Head(Tail( (a,b,c),(x,y,z) ) ) 的结果为 。 三、简答题（每小题8分，共48分） 1．已知一棵非空二叉树，其中序遍历和后序遍历的结果分别为： 中序： CGBAHEDJFI 后序： GBCHEJIFDA 请确定该二叉树的结构。 2．无向图邻接表表示，然后写出对其分别进行深度、广度优先遍历的结果。 3．已知下图中二叉排序树的各结点的值依次为 32~40 ，请在树中相应位置标出各结点的值。 4． 给定一个关键字序列（24，19，32，43，38，6，13，22）， (1) 请写出快速排序第一趟的结果； (2) 构造堆排序时所建的初始小顶堆。 5．已知如下图所示的AOE网，填写表格，并求出关键路径。 顶点 Ve Vl 活动 e l V1 a1 V2 a2 V3 a3 V4 a4 V5 a5 V6 a6 a7 a8 6．已知哈希表空间大小为0~10，对11，78，10，1，3，2，4，21进行相应函数的哈希散列，并计算该哈希表成功查找的平均查找长度。 哈希函数： 冲突解决方法：线性探测开放定址法 四、代码阅读题（每空3分，共12分） 已知如下代码要实现链表中个结点，阅读并填写其中空白，使得算法功能实现。int ListInsert_L( LinkList L, int i, Lnode *s ) { p=L; j=0; while (p ji-1) { ( ; ++j；} if (!p || ji-1) return -1; s=(LinkList)malloc( ( ); s-data=e; ( ; ( ; return 0; } 五、