资源描述：
《最新数据结构考试题6知识讲解.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、__________________________________________________要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题2分，共20分）1.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法2.下述函数中对应的渐进时间复杂度（n为问题规模）最小是。A.T1(n)=nlog2n+5000nB
2、.T2(n)=n2-8000nC.T3(n)=n-6000nD.T4(n)=7000log2n3.设线性表有n个元素，以下操作中，在顺序表上实现比在链表上实现效率更高。A.输出第i（1≤i≤n）个元素值B.交换第1个元素与第2个元素的值C.顺序输出这n个元素的值D.输出与给定值x相等的元素在线性表中的序号4.设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是1，2，3，…，n，若p3=3，则p1的值。A.可能是2B.一定是2C.不可能是1D.一定是15.以下各种存储结构中，最适合用作链队的
3、链表是。A.带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链表D.只带队首指针的循环单链表6.对于链串s（长度为n，每个结点存储一个字符），查找元素值为ch的算法的时间复杂度为。A.O(1)B.O(n)C.O(n2)D.以上都不对7.设二维数组A[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是。A.872B.860C.868D.8648.一个具有1025个结点的
4、二叉树的高h为。A.11B.10C.11～1025D.12～10249.一棵二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，则先序遍历序列为。A.ACBEDB.DECABC.DEABCD.CEDBA10.对图1所示的无向图，从顶点1开始进行深度优先遍历；可得到顶点访问序列。收集于网络，如有侵权请联系管理员删除__________________________________________________A.1243576B.1243567C.1245637D.1234576图1一个无
5、向图二、填空题（每题2分，共10分）1.顺序队和链队的区别仅在于的不同。2.在有n个顶点的有向图中，每个顶点的度最大可达。3.对有18个元素的有序表R[1..18]进行二分查找，则查找R[3]的比较序列的下标为。4.对含有n元素的关键字序列进行直接选择排序时，所需进行的关键字之间的比较次数为。5.已知关键字序列为{2,7,4,3,1,9,10,5,6,8}，采用堆排序法对该序列作升序排序时，构造的初始堆（大根堆）是。（不用画出堆，只需写出初始堆的序列）三、问答题（共40分）1.一棵完全二叉树上有10
6、01个结点，其中叶结点的个数是多少？（需写出推导过程，8分）2.给出如下各种情况下求任意一个顶点的度的过程（只需文字描述）：（8分）（1）含n个顶点的无向图采用邻接矩阵存储；（2）含n个顶点的无向图采用邻接表存储；（3）含n个顶点的有向图采用邻接矩阵存储；（4）含n个顶点的有向图采用邻接表存储。3.将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树。（要求画出每个元素插入过程，若需调整，还需给出调整后的结果，并指出是什么类型的调整，12分）4.当实现
7、插入直接排序过程中，假设R[0..i-1]为有序区，R[i..n-1]为无序区，现要将R[i]插入到有序区中，可以用二分查找来确定R[i]在有序区中的可能插入位置，这样做能否改善直接插入排序算法的时间复杂度?为什么?（8分）5.简述外排序的两个阶段。（4分）四、算法设计题（每小题10分，共30分）1.设计一个算法delminnode(LinkList*&L)，在带头结点的单链表L中删除所有结点值最小的结点（可能有多个结点值最小的结点）。2.假设二叉树采用二叉链存储结构存储，设计一个算法copy(BT
8、Node*b,BTNode*&t)，由二叉树b复制成另一棵二叉树t。3.假设一个无向图是非连通的，采用邻接表作为存储结构，试收集于网络，如有侵权请联系管理员删除__________________________________________________设计一个算法，输出图中各连通分量的节点序列。收集于网络，如有侵权请联系管理员删除__________________________________________________参 考 答 案一、单项选择题（每
