资源描述：
《南昌大学 数据结构 2010～2011学年第一学期期末试卷与答案a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、南昌大学2010～2011学年第一学期期末考试试卷试卷编号：(A)卷课程编号：课程名称：数据结构考试形式：闭卷适用班级：姓名：学号：班级：学院：专业：考试日期：题号一二三四五六七八九十总分累分人签名题分20303020100得分考生注意事项：1、本试卷共8页，请查看试卷中是否有缺页或破损。如有立即举手报告以便更换。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。一、选择题(每题1分，共20分)得分评阅人1.算法必须具备输入、输出和 ___________。 A.计算方法 B.排序方法C．解决问题的有限运算步骤 D.程序设
2、计方法2.设将整数1,2,3,4,5依次进栈，最后都出栈，出栈可以在任何时刻（只要栈不空）进行，则出栈序列不可能是 ___________。 A．23415 B.54132C．23145D.154323.用链表表示线性表的优点是___________。A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4.若某线性表的常用操作是取第i个元素及其前趋元素，则采用___________。存储方式最节省时间 A.顺序表 B.单链表C.双链表 D.单向循环第11页共11页5.串是任
3、意有限个___________。 A.符号构成的序列 B.字符构成的序列C.符号构成的集合 D.字符构成的集合6.设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a85地址为___________。A.23B.33C.18D.407．在一个单链表中，若p结点不是最后一结点。在p结点之后插入s结点的正确是。A.s->next=p;p->next=s;B.s->next=p;p=pC.s->next=p->next;p->next=s;D.p->next=s;s->next=p;8.将含1
4、00个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为。 A.24 B.25 C.23 D.无法确定9.在一棵二叉树中有30个叶子结点，仅有一个孩子的结点有20个，则该二叉树共有个结点A、79B、76C、56D、8110.深度为5的二叉树至多有个结点。A.16B.32C.31D.1011．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是_________。A.直接选择排序B.直接插入排序C.
5、快速排序D.起泡排序12．二分查找要求节点。A．有序、顺序存储 B.有序、链接存储C．无序、顺序存储 D.无序、链接存储13．在一个无向图中，所有顶点的度数之和等于图的边数的倍A．1/2B.1C.2D.414.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为（35，51，24，13，68，56，42，77，93）（35，24，13，51，56，42，68，77，93）所采用的排序方法是_________________A.插入排序B.冒泡排序C.快速排序D.归
6、并排序15．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有______________个A.33B.34C.32D.30第11页共11页16．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为_______________。A.60B.66C.67D.5017.对一棵二叉排序树进行____________遍历得到的结点序列是一个有序序列。 A.前序B.中序C.后序D.层序18．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值8
7、2为的结点时，______________次比较后查找成功。A.1B.2C.4D.819．就平均查找速度而言，下列几种查找速度从慢至快的关系是___________。A.顺序折半哈希分块B.顺序分块折半哈希C.分块折半哈希顺序D.顺序哈希分块折半20.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用______________排序法。A.冒泡排序B.快速排序C.堆排序D.选择排序二、填空题(每空2分，共30分)得分评阅人1.设r指向单链表最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是 r->next
8、=s;r=s;____【1】_______。2.数据的逻辑结构分为两大类，它们是
