《数据结构2013B试卷2new》由会员分享，可在线阅读，更多相关《数据结构2013B试卷2new（13页珍藏版）》请在金锄头文库上搜索。
1、 学院 姓名 学号 任课老师 考场教室_选课号/座位号 密封线以内答题无效 电子科技大学 2012-2013 学年第 2 学期期 末 考试 数据结构 卷 课程名称： 数据结构 考试形式：闭卷 考试日期： 2013 年 月 日 考试时长：120 分钟课程成绩构成：平时 0 %， 期中 0 %， 实验 %， 期末 100 % 本试卷试题由_ 五 _部分构成，共 6 页。 题号 一 二 三 四 五 六 七 八 九 十 合计 得分 得 分 一、 选择题（共 20 分，共 10 题，每题 2 分） 1. 设某数据结构的二元组形式表示为 A=(D，R)，D=01，02，03，04，05，06，07，08，
2、09，R=r， r=，则数据结构 A 是（ ）。 (A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构 2. 下面程序的时间复杂为（ ）。 for（i=1，s=0； i=n； i+） t=1；for(j=1；jnext=0 (C) head-next=head (D) head!=0 5 设用链表作为栈的存储结构则退栈操作（ ）。 (A) 必须判别栈是否为满 (B) 必须判别栈是否为空 (C) 判别栈元素的类型 (D) 对栈不作任何判别 6. 设指针变量 front 表示链式队列的队头指针，指针变量 rear 表示链式队列的队尾指针，指针变量 s 指向将要入队列的结点 X，则
3、入队列的操作序列为（ ）。 (A) front-next=s；front=s； (B) s-next=rear；rear=s； (C) rear-next=s；rear=s； (D) s-next=front；front=s； 7设某二叉树中度数为 0 的结点数为 N0，度数为 1 的结点数为 Nl，度数为 2 的结点数为 N2，则下列等式成立的是（ ）。 (A) N0=N1+1 (B) N0=Nl+N2 (C) N0=N2+1 (D) N0=2N1+l 8设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i 结点的左孩子结点的编号为（ ）。 (A) 2i+1 (B
4、) 2i (C) i/2 (D) 2i-1 9. 设完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边。 (A) n(n-1)/2 (B) n(n-1) (C) n(n+1)/2 (D) (n-1)/2 10. 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字 90 需要比较的关键字个数为（ ）。 (A) 1 (B) 2 (C) 3 (D) 4 得 分 二、 填空（共 20 分，共 20 空，每空 1 分） 1. 通常从四个方面评价算法的质量：_正确性_、_易读性_、_强壮性_和_高效性_。 2. 设指针 p 指向
5、单链表中结点 A，指针 s 指向被插入的结点 X，则在结点 A 的前面插入结点 X 时的操作序列为： 1) s-next=_p-next_；2) p-next=s；3) t=p-data； 4) p-data=_x_；5) s-data=t； 3. 在计算机内实现递归算法时所需的辅助数据结构是_栈_。 4. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_o(1)_。 5. 子串“ABC”在主串“AABCABCD”中的位置为_2_. 6. 设有一个 10 阶的下三角矩阵 A（包括对角线），按照从上到下、从左到右的顺序存储到连续的 55 个存储单元中，每个数组元素占
6、 1 个字节的存储空间，则A54地址与 A00的地址之差为_28_。 7. 设某棵完全二叉树中有 100 个结点，则该二叉树中有_50_个叶子结点。 8. 设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树得到序列为_BADC_。 9. 设二叉排序树的高度为 h，则在该树中查找关键字 key 最多需要比较_2h-1_次。 10. 设完全有向图中有 n 个顶点，则该完全有向图中共有_n(n-1)_条有向条。 3 1 2 4 5 7 6 8 11. 设有向图 G 中有向边的集合 E=，则该图的一种拓扑序列为_1423_。 12. 已知一有向图 G7 的邻接表存储结
7、构如下：从顶点 1 出发，深度优先遍历的输出序列是_12485367_，广度优先遍历的输出序列是_12345678_13. 解决散列表冲突的两种方法是_链接法 _开放定址法 得 分 三、 计算题（ 共 33 分） 1. 有三个元素按 a、b、c 的次序依次进栈，且每个元素只允许进一次栈，列出任意可能的两种出栈序列。(6 分) Abc cba 2. 最小生成树构造问题：设无向图 G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。(9 分) 3. 画出由权值为 9, 2, 5, 7 的四个结点(分别由 A、B、C、D 表示四个结点)构造的哈夫曼树（最优树），并给出
8、ABCD 的哈夫曼编码。(10 分) T 4. 试计判断单链表中元素是否是递增的算法。(8 分) 得 分 四、算法题（ 共 12 分） 1. 试阐述下列算法的功能。(6 分) void algo3(Queue &Q) Stach S; int d; InitStack (S); while (!QueueEmpty(Q) DeQueue(Q,d); Push(S,d); while(!StackEmlpty(S) /若栈非空 Pop(S,d); EnQueue(Q,d); 2. 试试填写完成下列算法，对单链表实现就地逆置，并分析该算法复杂度。(6 分) Status LinkConvert(L
9、inkList &h) /假设有头结点，h 为指向头结点的指针, p = h-next; h-next=NULL; while (p) _q=p_；_p=p-next_; /让 q 指向 p，调整 p 到后一个结点 q-next = h-next; h-next = q; return OK; /LinkConvert 得 分 五、论述题（ 共 15 分） 设有如图 1 所示的一个可以停放 n 辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车场时间的早晚，依次从停车场最里面向大门口处停放（最先到达的第一辆车放在停车场的最里面）。如果停车场已停放 n 辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆次序。试设计一个方案以实现对该停车场的计算机管理。(15 分) 进出南候车场停车场图1 停车场示意图北第 12 页 共 12 页
