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

《华东交通大学2011-2012.1 数据结构试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2011—2012学年第一学期考试卷　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（A）卷数据结构课程课程类别：必闭卷　　考试日期：2012.1题号一二三四五六七八九十总分累分人签名题分2030428100得分考生注意事项：1、本试卷共4页，总分　100　分，考试时间　120　分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。3、答案

2、必须写在答题纸上，考试结束时请将答题纸与试卷分开上交，试卷、答题纸、草稿纸都必须交回。得分评阅人一、选择题(每题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->nex

3、t=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

4、.后继8.对完全二叉树按层序从1开始编号，编号为100的结点是编号为50的结点的（）。A.左孩子B.右孩子C.双亲D.根结点第4页共4页9．下图AOE网络中，要完成该工程需要（）时间。A.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][

5、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;i

6、(intj=0;j

7、2.已知一棵二叉树的后序序列为IGDBEHFCA,中序序列为DIGBAECFH,直接画出此二叉树并画出对应的森林。3.用教材中给出的数值转换算法将十进制数2012转换成八进制数，并画出转换过程中栈的变化情况。4．给定下列网G:写出用克鲁斯卡尔算法构造最小生成树过程中每一步选择的边。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，试构造一棵二叉

8、排序树，并写出其构造过程。7．利用迪杰斯特拉算法依次求出下图中从顶点v0到其他各