数据结构试卷12—01-9().doc

承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业 班级 学号 学生签名： 华东交通大学20112012学年第一学期考试卷试卷编号：（ ）卷 数据结构（C） 课程 课程类别：必 闭卷 考试日期： 2012.1 题号一二三四五六七八九十总分累分人签名题分2030428100得分考生注意事项：1、本试卷共 3 页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必须交回。得分评阅人 一、选择题(每题 2 分，共 20 分) 1. 计算机算法必须具备输入、输出（ ）5个特性。A可行性、可移植性和可扩充性B. 有穷性、确定性、可行性 C. 确定性、有穷性和稳定性D. 可读性、稳定性和安全性2.在长度为n的顺序表的第i个元素（1=inext=s; s-next=p-next; Bs-next=p-next; p-next=s;Cp-next=s; p-next=s-next; D. p-next=s-next; p-next=s;4. 判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。A队列 B线性表 C栈 D双向链表5包含2012个顶点的连通图最少有（ ）条边。A. 2011B. 2012C. 2013D. 20146. 在有序表4，15，26，27，38，64，81中折半查找38的比较次数为（ ）。A1 B2 C3 D4 7. 线索链表中，若结点p的LTag=1，则p-rchild指向（ ）。A. 左孩子 B. 右孩子 C. 前驱 D. 后继8. 对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（ ）。A. 左孩子 B. 右孩子C. 双亲D. 根结点9下图AOE网络中，要完成该工程需要（ ）时间。A. 43 B.18 C. 31 D. 3510顺序查找的时间复杂度为（ ）A O(n/2) BO(n) CO(1) DO(log2n) 得分评阅人二、填空题(每题 2 分，共 30 分)1数据结构中评价算法的两个重要指标是算法的 (1) 和空间复杂度。2. 链接存储的特点是利用 (2) 来表示数据元素之间的逻辑关系。3. 假设有5行4列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，按行优先存储时元素A23的地址是 (3) 。（行列下标均从0开始？）49阶对称矩阵采用压缩存储占用_(4)_个元的存储空间。（我没讲压缩存储！）5若用一个大小为8的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear的值为 (5) ，front的值为 (6) 。6. SubString(HAPPYNEWYEAR, 6, 3）= （7） 。7一棵具有267个结点的完全二叉树，它的深度为 (8) ，有 (9) 个叶子结点。8以下代码片段中，k+的执行次数为 (10) 。for (int i=0; in; i+) for (int j=0; jn; j+) k+;9若一棵二叉树具有7个度为2的结点，3个度为1的结点，则度为0的结点个数是_ (11) 。10右图的一个拓扑排序序列为A （12） EF。11. 循环链表中最后一个结点的指针域指向 （13） 。（有头结点吗？）填空题10图12. 顺序表第 (14) 个数据元素的存储位置称为基地址。13. 具有3个结点的二叉树的有 （15） 种不同形态。得分评阅人三、综合题 （每题6分，共42分）1进栈顺序为12345，问能否得到45231和32451的出栈序列，以push（X）表示进栈和以pop（X）表示出栈的操作序列，说明为什么不能得到或如何能得到。2. 已知一棵二叉树的后序序列为IGDBEHFCA,中序序列为DIGBAECFH,直接画出此二叉树并画出对应的森林。3. 用数值转换算法将十进制数2012转换成八进制数，并画出转换过程中栈的变化情况。（这个算法是什么？就是书上那个例题的算法吗？）4已知一个无向图的邻接表1）画出该无向图。(4分)2）根据邻接表，写出用广度优先遍历算法从结点v0开始遍历该图得到的遍历序列。（2分）5给定下列网G: 用克鲁斯卡尔算法找出网G的最小生成树，并画出构造过程中每一步的逻辑结构图。（6分）5假设用于通信的电文由6个字母A,B,C,D,E,F组成，字母在电文中出现的频率分别为0.17, 0.12, 0.05, 0.28, 0.35, 0.03。 试为这6个字母设计哈夫曼树（权值小的作为左子树）。6记录的关键字序列为：56，90，27，67，55，10，88，27，42，45，56，86,试构造一棵二叉排序树，并写出其构造过程。7利用迪杰斯特拉算法求下图中从顶点v0到其他各顶点间的最短路径，写出其执行算法过程中各步的状态。（6分写详细步骤，那么多结点，是不是太耗时间了？我觉得题量有点大，是不是可以简化这题？）得分评阅人四、算法题 （共8分）1. 实现带头结点的单链表L 中，删除第i个元素，并由e返回其值。 （1）用编程语言定义单链表的存储结构（3分） （2）用编程语言定义函数实现上述功能（5分）第 4 页 共4页承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业 班级 学号 学生签名： 华东交通大学20112012学年第一学期考试卷试卷编号：（ ）卷 数据结构（C） 课程 课程类别：必 闭卷 考试日期：2012.1 题号一二三四五六七八九十总分累分人签名题分2030428100得分得分评阅人 一、选择题（每题2 分，共20分）12345678910得分