华东交通大学数据结构试卷

1、华东交通大学20112012 学年第一学期考试卷试卷编号：（A）卷数据结构课程题号一二题号一二三42四8五六七八九十题分得分2030总分累分人签名100课程类别：必考试日期：考生注意事项：一、本试卷共4 页，总分100分，考试时刻120二、考试终止后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案必需写在答题纸上，考试终止时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必需交回。得分评阅人一、选择题(每题2分，共20分)得分评阅人运算机算法必需具有输入、输出（）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;判别表达式中左、右括号是不是配对显现的算法，采纳（）数据结构最正确A队列B线性表C栈D双向链表包括2021个极点的连通图最少有（）条边。A.2020B.2012C.2013D.20146.在有序表4，15，26，27，38，64，81中折半查找38的比较次数为（。A1B2C3D4线索链表中，假设结点p的RTag=1，那么p-rchild指向（。左小孩B.右小孩C.前驱D.后

3、继对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（。左小孩B.右孩子C. 双亲D.根结点102426110242614196153115543C. 31D. 35顺序查找的时刻复杂度为（）AO(n/2)BO(n)CO(1)DO(log2n)得分评阅人二、填空题(每题2分，共30分)得分评阅人数据结构中评判算法的两个重要指标是算法的(1)和空间复杂度。链接存储的特点是利用(2)来表示数据元素之间的逻辑关系。假设有5行4列的二维数组每一个元素占用6个字节存储器按字节编址已知A00 的地址为1000，按行优先存储时元素A23的地址是(3)。带头结点的单链表L中，L-next-

4、next表示第（4）个数据元素。假设用一个大小为8的数组来实现循环队列且当前rear和front的值别离为0和当队列中删除一个元素，再加入两个元素后，rear的值为(5)，front的值为(6)。SubString(HAPPYNEWYEAR,6,3）=（7）。267(8) ，有(9) 个叶子结点。以下代码片段中，k+的执行次数为(10) 。BABACEDF72，31那么度为0的结点个数是_(11)。右图的一个拓扑排序序列为A（12）EF。带头结点的循环链表中最后一个结点的指针域指向（13）。顺序表第(14)个数据元素的存储位置称为基地址。具有3个结点的二叉树有（15）种不同形态。填空题10图得

5、分评阅人三、综合题 （每题 6 分，共 42 分）得分评阅人12345，4523132451push（X） IGDBEHFCA,DIGBAECFH,对应的丛林。2021变情形。A12BA12B20C4891215EFGD610写出用克鲁斯卡尔算法构造最小生成树进程中每一步选择的边。假设用于通信的电文由 6 个字母 A,B,C,D,E,F 组成，字母在电文中显现的频率别离为,。试为这6个字母设计哈夫曼树（权值小的作为左子树。v00320321465127718361735624得分评阅人四、算法题 （共 8 分）得分评阅人L ie返回其值。用编程语言概念单链表的存储结构（3分）用编程语言概念函数实现上述功能（5分）华东交通大学20112012 学年第一学期考试卷试卷编号：（A数据结构课程课程类别：必闭卷考试日期：题号一题分20得分三428五六七八九十总累分人签名一、选择题（2 20 分）12345678910得分评阅人二、填空题（每空 2 分，共 30 分）得分评阅人123456789101112131415三、综合题（6