1、华东交通大学20112012 学年第一学期考试卷试卷编号：（A）卷数据结构课程题号一二三42四8五六七八九十题分得分2030总分累分人签名100闭卷课程类别：必考试日期：考生注意事项：一、本试卷共 4 页，总分100分，考试时刻120分钟。二、考试终止后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案必需写在答题纸上，考试终止时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必需交回。得分评阅人一、选择题(每题2分，共20分)1. 运算机算法必需具有输入、输出（）5 个 特 性 。A可行性、可移植性和可扩充性B. 有穷性、确信性、可行性C. 确信性、有穷性和稳固性D. 可读性、稳固性和平安性
2、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. 包括 2021 个极点的连通图最少有（）条边。A. 2020B. 2012C. 2013D. 20146. 在有序表4，15，26，27，38，64，81中折半查找 38 的比较次数为（）。A1B2C3D47. 线索链表中，假设结点 p 的
3、RTag=1，那么 p-rchild 指向（）。A. 左小孩B. 右小孩C.前驱D.后继8. 对完全二叉树按层序从 1 开始编号，编号为 100 的结点是编号为 50 的结点的（）。A. 左小孩B.右孩子C. 双亲D. 根结点1024261419615311559. 以下图 AOE 网络中，要完成该工程需要（）时刻。A. 43C. 31D. 3510. 顺序查找的时刻复杂度为（）AO(n/2)B O(n)CO(1)DO(log2n)得分评阅人二、填空题(每题2分，共30分)1. 数据结构中评判算法的两个重要指标是算法的(1)和空间复杂度。2. 链接存储的特点是利用(2)来表示数据元素之间的逻辑
4、关系。3. 假设有 5 行 4 列的二维数组 A，每一个元素占用 6 个字节，存储器按字节编址。已知 A00 的地址为 1000，按行优先存储时元素 A23的地址是(3)。4. 带头结点的单链表 L 中，L-next-next 表示第（4）个数据元素。5. 假设用一个大小为 8 的数组来实现循环队列，且当前 rear 和 front 的值别离为 0 和 3，当从队列中删除一个元素，再加入两个元素后，rear 的值为(5)，front 的值为(6)。6. SubString(HAPPYNEWYEAR, 6, 3）=（7）。7. 一棵具有 267 个结点的完全二叉树，它的深度为(8) ，有(9)
5、个叶子结点。8. 以下代码片段中，k+的执行次数为(10) 。BACEDFfor (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）。12. 顺序表第(14)个数据元素的存储位置称为基地址。13. 具有 3 个结点的二叉树有（15）种不同形态。填空题 10 图得分评阅人三、综合题 （每题 6 分，共 42 分）1. 进栈顺序为 12345，
6、问可否取得 45231 和 32451 的出栈序列？以 push（X） 表示进栈和以 pop（X）表示出栈的操作序列，说明什么缘故不能或如何能取得。2. 已知一棵二叉树的后序序列为 IGDBEHFCA,中序序列为 DIGBAECFH,直接画出此二叉树并画出对应的丛林。3. 用教材中给出的数值转换算法将十进制数 2021 转换成八进制数，并画出转换进程中栈的转变情形。A12B20C4891215EFGD6104. 给定以下网 G:写出用克鲁斯卡尔算法构造最小生成树进程中每一步选择的边。5. 假设用于通信的电文由 6 个字母 A,B,C,D,E,F 组成，字母在电文中显现的频率别离为, , , ,
7、 。 试为这 6 个字母设计哈夫曼树（权值小的作为左子树）。6. 记录的关键字序列为：56，90，27，67，56，10，88，试构造一棵二叉排序树，并写出其构造进程。7. 利用迪杰斯特拉算法依次求出下图中从极点 v0 到其他各极点间的最短途径。032146512771836173562420得分评阅人四、算法题 （共 8 分）1. 实现带头结点的单链表 L 中，删除第 i 个元素，并由 e 返回其值。（1） 用编程语言概念单链表的存储结构（3 分）（2） 用编程语言概念函数实现上述功能（5 分）华东交通大学20112012 学年第一学期考试卷试卷编号：（A）卷数据结构课程课程类别：必闭卷考试日期：题号一二题分2030得分三四428五六七八九十总分100累分人签名一、选择题（每题 2 分，共 20 分）12345678910得分评阅人二、填空题（每空 2 分，共 30 分）得分评阅人123456789101112131415三、综合题（每题 6 分，共 42 分）一、得分评阅人二、栈（左边为栈底）12343、(2021)10=()8边的顶点 1边的顶点 2权值1234564、5、六、路径1234567、得分评阅人四、算法题 （共 8 分）
