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

第1页共4页华东交通大学2011—2012学年第一学期考试卷试卷编号：（A）卷数据结构课程课程类别：必闭卷考试日期：2012.1题号一二三四五六七八九十总分累分人签名题分2030428100得分考生注意事项：1、本试卷共4页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必须交回。一、选择题(每题2分，共20分)1.计算机算法必须具备输入、输出（）5个特性。A．可行性、可移植性和可扩充性B.有穷性、确定性、可行性C.确定性、有穷性和稳定性D.可读性、稳定性和安全性2.在长度为n的顺序表的第i个元素（1=i=n）之前插入数据元素时，需向后移动（）个元素。A．n-i+1B.n-iC.iD.n3.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-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的比较次数为（）。A．1B．2C．3D．47.线索链表中，若结点p的RTag=1，则p-rchild指向（）。A.左孩子B.右孩子C.前驱D.后继8.对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（）。A.左孩子B.右孩子C.双亲D.根结点得分评阅人承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第2页共4页9．下图AOE网络中，要完成该工程需要（）时间。213456215101141965A.43B.18C.31D.3510．顺序查找的时间复杂度为（）A．O(n/2)B．O(n)C．O(1)D．O(log2n)二、填空题(每题2分，共30分)1．数据结构中评价算法的两个重要指标是算法的(1)和空间复杂度。2.链接存储的特点是利用(2)来表示数据元素之间的逻辑关系。3.假设有5行4列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A[0][0]的地址为1000，按行优先存储时元素A[2][3]的地址是(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)个叶子结点。8．以下代码片段中，k++的执行次数为(10)。for(inti=0;in;i++)for(intj=0;jn;j++)k++;9．若一棵二叉树具有7个度为2的结点，3个度为1的结点，则度为0的结点个数是_(11)。10．右图的一个拓扑排序序列为A（12）EF。11.带头结点的循环链表中最后一个结点的指针域指向（13）。12.顺序表第(14)个数据元素的存储位置称为基地址。13.具有3个结点的二叉树有（15）种不同形态。三、综合题（每题6分，共42分）1．进栈顺序为12345，问能否得到45231和32451的出栈序列？以push（X）表示进栈和以pop（X）表示出栈的操作序列，说明为什么不能或如何能得到。得分评阅人得分评阅人填空题10图BACDEF第3页共4页2.已知一棵二叉树的后序序列为IGDBEHFCA,中序序列为DIGBAECFH,直接画出此二叉树并画出对应的森林。3.用教材中给出的数值转换算法将十进制数2012转换成八进制数，并画出转换过程中栈的变化情况。4．给定下列网G:BACDEG12F489620121510写出用克鲁斯卡尔算法构造最小生成树过程中每一步选择的边。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，56，10，88，试构造一棵二叉排序树，并写出其构造过程。7．利用迪杰斯特拉算法依次求出下图中从顶点v0到其他各顶点间的最短路径。012346521773220676145318第4页共4页四、算法题（共8分）1.实现带头结点的单链表L中，删除第i个元素，并由e返回其值。（1）用编程语言定义单链表的存储结构（3分）（2）用编程语言定义函数实现上述功能（5分）得分评阅人第1页共4页华东交通大学2011—2012学年第一学期考试卷试卷编号：（A）卷数据结构课程课程类别：必闭卷考试日期：2012.1题号一二三四五六七八九十总分累分人签名题分2030428100得分一、选择题（每题2分，共20分）12345678910二、填空题（每空2分，共30分）123456789101112131415三、综合题（每题6分，共42分）1、得分评阅人得分评阅人得分评阅人承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：第2页共4页2、3、(2012)10=()8栈（左边为栈底）12344、边的顶点1边的顶点2权值123456第3页共4页5、6、7、路径123456第4页共4页四、算法题（共8分）得分评阅人