资源描述：
《国家开放大学电大《数据结构(本)》期末题库及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最新国家开放大学电大《数据结构（本）》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。做考题时，利用本文档中的查找工具，把考题屮的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。本文库还有其他网核及教学考一体化答案，敬请查看。《数据结构》题库及答案一一、单项选择题（每小题3分，共30分）1.设有头指针为head的带有头结点的非空单向循环链表，指针p指向其尾结点，要删除头结点，并使其仍
2、为单向循环链表，则可利用下述语句head=head->next；（）。B.p=NULL；D・head=p；A・p=head；C・p—>next=head；2.以下说法不正确的是（）oA.线性表的链式存储结构不必占用连续的存储空间B.一种逻辑结构只能有唯一的存储结构C.一种逻辑结构可以有不同的存储结构D.线性表的顺序存储结构必须占用连续的存储空间）称为物理结构。B.数据的处理方法D.数据的运算B.需要占用连续的存储空间D.删除元素的操作需要移动元素3.把数据存储到计算机中，并具体体现（A.数据元素间的逻辑关系C.数据
3、的性质4.链表所具备的特点之一是（〉。A.可以随机访问任一结点C.插入元素的操作不需要移动元素5.图状结构中数据元素的位置之间存在（）的关系。A.一对一B.多对多C.—对多D.每一个元素都有一个直接前驱和一个直接后继6.元素15,9,11,13按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替进行）。A.13.11,9,15C.13,11,15,9B.15,9,11,13D.9,15,13,111.设有一个14阶的对称矩阵A（第一个元素为altl）,采用压缩存储的方式，将其下三角部分以行序为主序存储到一
4、维数组B中（数组下标从1开始），则矩阵中元素a4.3在一维数组B中的下标是（）oA.9B.10A.11D.8&在一棵二叉树中，若编号为8的结点存在右孩子，则右孩子的顺序编号为（）。A.18B.16C.15D・179.设一棵哈夫曼树共有14个非叶结点，则该树总共有（）个结点。A.29B.27C.30D.2810.如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（）。图1A.abecdfC.aebcfdB・acfebdB.aedbfc得分评卷人二、填空题（每小题2分，共24分）1
5、1.队列的特点之一是:元素进、岀队的次序是:先进。12.结构中，数据元素间存在一对多的关系。13.对稀疏矩阵进行压缩存储,矩阵中每个非零元素对应的三元组包括该元素的三项信息是O14.在对11个记录的序列（12,35,9,7,2,11,56,95,37,58,60）进行直接插入排•序时，当把第6个记录11插入到有序表时，为寻找插入位置，元素间需比较次。（由小到大排列）15.哈希函数是记录关键字的值与该记录之间所构造的对应关系。16.20个元素进行冒泡法排序，通常需要进行19趟冒泡，其中第10趟冒泡共需要进行次元素间的
6、比较。9.一棵有19个结点的二叉树，采用链式结构存储，该树结构中有个指针域为空。1&中序遍历一棵树可得到一个有序序列。19.二叉排序树插入操作中，新插入的结点总是以树的结点被插入的。20.广义表的(a,(d,a,b),h,(e,((i,j),k)))深度是。21•序列4,2,5,3,8,6,7,9,采用归并排序算法(升序)，经一趟归并后，序列的结果:。22.字符串al=uteijingw,a2=“tef”,a3=“teifang”，a4=“tefi”最小的是。得分评卷人三、综合题(每小题中每问6分，共30分)23・
7、设査找表为序号1234567891011序列4121819375565778586117(1)画出对上述査找表进行折半査找所对应的判定树(树中结点用下标表示)。(2〉说明成功査找到元索86需要经过多少次比较？(3)求在等概率条件下，成功査找的平均比较次数？24.(1)一组记录的关键字序列为(26,59,36,18,20,25),给出利用堆排序(堆顶元素是最小元素)的方法建立的初始堆(要求以完全二叉树描述)o(2)对关键字序列(26,59,36,18,20,64)采用快速排序，给出以第一个关键字为分割元素，经过一次划
8、分后的结果。得分评卷人四、程序填空题(毎空2分，共16分)25・以下函数在a[0]到a[n-l]中，用折半査找算法査找关键字等于k的记录，査找成功返回该记录的下标，失败时返回一1，完成程序中的空格typedefstruct{intkey;}NODEjintBinary_Search(NODEa[1，intn,intk)intlow,mid,high?low=
