资源描述：
《【精品】电大数据结构(本)期末复习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、单项选择题（每小题2分，共30分））结构。D.逻辑与物理D.顺序表1.数据结构小，与所使用的计算机无关的是数据的（A.逻辑B.物理C.存储2.下述各类表中可以随机访问的是（）。A.单向链表B.双向链表C.单向循坏链表3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。A.21B.20C.19D.254.元素2,4,6按顺序依次进栈，则该栈的不可能的输出序列是（）。A.642B.624C.426D.2645.—个队列的入队序列是5,6,7,8,则队列的输出序列是（
2、）oA.5678B.8765C.7865D.可能有多种情况6.串函数StrCmp（“d”，“D”）的值为（）。A.0B.1C.一1D.37.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。A.p=q->nextB.p->next=qC.p->next=q->nextD.q->next=NULL8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。D.2*(nT))oD・dbaefcgA.2*nTB.2*n+1C.2*n9.对如图1所示二叉
3、树进行中序遍历，结果是(A.dfebagcB.defbagcC.defbacg图110.任何一个无向连通图的最小生成树（）oA・至少有一棵B.只有一棵C.一定有多棵D.可能不存在11.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵小元素A"在一维数组B屮的下标是（）oA.33B.32C.85D.4112.一组记录的关键字序列为（37,70,47,29,31,85）,利用快速排序,以第一个关键字为分割元素，经过一次划分后结果为（）。A.31,2
4、9,37,85,47,70B.29,31,37,47,70,85C・31,29,37,70,47,85D.31,29,37,47,70,8512.对n个元素进行冒泡排序，要求按升序排列，程序中设定某--趟冒泡没有出现元素交换，就结束排序过程。对某n个元素的排序共进行了3n-6次元素间的比较就完成了排序，则（）oA.原序列是升序排列B.原序列是降序排列C.对序列只进行了2趟冒泡D.对序列只进行了3趟冒泡14.在一个栈顶指针为top的链栈屮删除一个结点时，用x保存被删除的结点，应执行（）oA.x二top->data;t
5、op=top->next;B.top二top->next;x=top;C.x二top;top二top->next;D.x=top->data;15.串函数StrCat（a,b）的功能是进行串（）。A.比较B.复制C.赋值D.连接二、填空题（每小题2分，共24分）1.在一个单向链表中P所指结点之后插入一个s所指的新结点，应执行s->next=p->next；和操作。2.根据数据元素间关系的不同特性，通常可分为、、、四类基本结构。3.在一个链队中，设f和「分别为队头和队尾指针，则删除一个结点的操作为。（结点的指针域为n
6、ext）4.遍历二叉排序树可得到一个有序序列。5.—棵有2n・l个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有个叶结点。6.如图1所示的二叉树，其中序遍历序列为ob丿图17.对稀疏矩阵进行压缩存储，矩阵中每个非零元素所对应的三元组包括该元素的、和三项信息。8.有一个有序表{2,3,9,13,33,42,45,63,74,77,82,95,110},用折半查找法查找值为82的结点，经次比较后查找成功。9.图的深度优先搜索和广度优先搜索序列不是唯一的。此断言是的。（回答正确或不正确）9.哈希法既是一种存储方法
7、，又是一种o10.44.在对一组记录（55,39,97,22,16,73,65,47,88）进行直接插入排序时,当把第7个记录65插入到有序表时，为寻找插入位置需比较次。11.栈和队列的操作特点分别是和c三、综合题(每小题10分，共30分)1.已知序列{11,19,5,4,7,13,2,10},(1)试给出用归并排序法对该序列作升序排序时的每一趟的结果。(2)对上述序列用堆排序的方法建立初始堆(要求小根堆，以二叉树描述建堆过程)。2.设有序表为(13,19,25,36,48,51,63,84,91,116,135,
8、200),元素的下标依次为1,2,……,12.(1)说出有哪儿个元素需要经过3次元素间的比较才能成功查到(2)画出对上述有序表进行折半查找所对应的判定树(树结点用下标表示)(3)设查找元素5,需要进行多少次元素间的比较才能确定不能查到.3.(1)设有查找表{5,14,2,6,18,7,4,16,3},依次取表中数据，构造一棵二叉排序树.(2)说明如何通过序列
