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