数据结构(本)试题

《数据结构(本)试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、试卷代号:1252座位号中央广播电视大学20102011学年度第一学期"开放本科"期末考试数据结构(本)试题2011年1月题号一-四总分一一一分数得分

2、评卷人一、单项选择题{每小题2分，共30分}1.数据元素是数据的基本单位，它()。A.只能有一个数据项组成B.至少有二个数据项组成c.可以是一个数据项也可以由若干个数据项组成D.至少有一个数据项为指针类型2.线性表的顺序结构中，()。A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的c.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高3.以下表中可

3、以随机访问的是()。A.单向链表B.双向链表c.单向循环链表D.顺序表4.设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的，则删除一个元素平均移动元素的次数为()。A.(n十1)/2B.nC.2nD.n-i13615.设top是-个链钱的战顶指针，战中每个结点由一个数据域data和指针域next组成，设用x接收钱顶元素，则出战操作为()。A.x=top一>data;top=top->next;B.top=top一>next;x=top->data;C.x=top->next;top=top->data;D.top->next

4、=top;x=top->data;6.以下说法正确的是()。A.队列是后进先出B.桔的特点是后进后出C.战的删除和插人操作都只能在战顶进行D.队列的删除和插入操作都只能在队头进行7.串函数StrCmp("b"，"cd勺的值为()。A.1B.aC."bcd"LD.-18.设有→个12阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中(矩阵A的第一个元素为旬，1，数组b的下标从1开始)，则矩阵A中第4行的元素在数组b中的下标i)定有()。A.7ζig二10B.11ζi~15C.9~i~14D.6~i~99.已知→个图

5、的边数为m，则该图的所有顶点的度数之和为()。A.2mB.mC.2m十1D.m/210.以下说法不正确的是()。A.连通图G一定存在生成树B.连通图G的生成树中…定包含G的所有顶点c.连通图G的生成树中不一定包含G的所有边D.连通图G的生成树可以是不连通的136211.散列查找的原理是()。A.在待查记录的关键字值与该记录的存储位置之间建立确定的对应关系B.按待查记录的关键字有序的顺序方式存储c.按关键字值的比较进行查找D.基于二分查找的方法12.排序过程中，每一趟从元序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适

6、当位置，直到全部排好序为止，该排序算法是()。A.直接插入排序B.快速排序c.冒泡排序D.选择排序13.采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法).最坏的情况下要进行()次元素间的比较。A.n十2B.nC.n-lD.n/214.如图若从顶点a出发按广度优先搜索法进行遍历，则可能得到的顶点序列为()。A.acebdfghB.aebcghdfC.aedfbcghgD.abecdfgh图115.一棵哈夫曼树总共有23个结点，该树共有()个叶结点(终端结点)。A.10B.13C.llD.121363得分

7、评卷人二、填空题

8、{每小题2分，共24分}1.通常数据的逻辑结构包括一一----，一一一一、一一一一、-一一-一四种类型。2.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句3.设有一个单向循环链表，头指针为head，链表中结点的指针域为next，p指向尾结点的直接前驱结点，若要删除尾结点，得到→个新的单向循环链表，可执行操作4.在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，则插入一个s所指结点的操作为;r=s。5.循环队列的队头指针为f，队尾指针为r，当时表明队列为

9、空。6.串函数StrCat(a，b)的功能是进行串7.一棵二叉树没有单分支结点，有6个叶结点，则该树总共有个结点。8.按照二叉树的递归定义，对二叉树遍历的常用算法有、、三种。9.把数据存储到计算机中，并具体体现数据之间的逻辑结构称为结构。10.如图2所示的二叉树，其后序遍历序列为。h国211.二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是的。(回答正确或不正确〉12.根据搜索方法的不同，图的遍历有、两种方法。1364得分

10、评卷人三、综合题(每小题10分，共30分)1.(1)已知某二叉树的后序

11、遍历序列是debca，中序遍历序列是dbeac，试画出该二叉树。(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出a、b、c、d，e