资源描述：
《数据结构期末复习总结题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、选择题1、线性表采用链表存储地址时OA.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以2、设循环队列中数组的下标范围是0..n-1,其头指#front指向队首元素,rear指向队尾元素，则队列的长度为oA.rear—frontB.rear—front+1C.(rear—front+l)%(n+1)D.(rear—front+n+1)%n3、一个栈的输入序列为A,B,C,D,E,则下列序列屮不可能是栈的输出序列的是A.BCDAEB.EDACBC.BCADED.AEDCB4、将一个A[1..20][1..20](注：下标均从1开始计)的矩阵，按行序为主存放，每个
2、元素占4个存储单元，并且A[1,2]的存储地址是1004,则A[20,2]的地址是A.1004B.1380C.1520D.25245、在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依相同次序从该缓冲区中収出数据打印。该缓冲区作为数据结构是一个结构。A.栈B.队列C.表D.线性表6、在有「个叶子结点的哈夫曼树屮，英结点总数为oA.nB.2nC.2n+lD.2nT7、某二叉树的前序序列和中序序列正好相反，则该二叉树一定具有的特征。A.二叉树为空或只有一个结点B.若二叉树不为空，则任一结点不能同时拥有左孩子和右孩子C.若二叉
3、树不为空，则任一结点没有左孩子D.若二叉树不为空，则任一结点没有右孩子8、下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费吋间反而最多。A.堆排序B.冒泡排序C.快速排序D.直接插入排序9、对于一个具有n个顶点的无向图，若釆用邻接矩阵表示，该矩阵的大小是A.nB.(n-1)2C.n~lD.n2BCD11＞假设有10个关键字，它们具有相同的Hash函数值,用线性探测法把这10个关键字存入Hash地址空间中至少要做次探测。A.110B.100C.55D.4512、在有向图的邻接表存储结构屮,顶点v在表结点中出现的次数等于A.顶点v的度B.顶点v的出度C.顶点v的入度D.依附于顶点v
4、的边数13、请指岀在顺序表｛2、5、7、10、14、15、18、23、35、41、52｝中,用二分法查找关键码12需做—A.2关键码的比较。B.3C.5D.414、对线性表进行二分查找时，要求线性表必须。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且节点按关键字有序排序D.以链接方式存储，且节点按关键字有序排序15、将一株有100个结点的完全二叉树从上到下，从左到右依次进行编号，根节点编号为1，则编号为49的结点的右孩子编号为oA.98B.99C.50D.没有右孩子二、填空题1、设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f将依次入栈S,—个元素出栈后即进入队列Q。若
5、这6个元素出队列的顺序是b、d、c、f、e、a,则栈S的容量至少应该是,上述过程才不会错。2、某表达式二叉树按先序遍历的结果为+a*+bcd,令a=6,b=3,c=4,d=2,则该表达式的值等于o3、设有一空队列Q,经Q.EnQueue(l),Q.DoQueue(),Q.EnQueue(2),Q.EnQueue(3),Q.EnQueue(4),Q.DeQueue()；Q.EnQueue(5)—系列操作后。队列中从队首到队尾的元素依次是o4、写出下图所示二叉树按后序遍历的结杲o5、由三个结点组成的二叉树共有不同的结构形态。6、一个无向图有n个顶点，e条边，则所有顶点的度数之和为。7、n个元素
6、的线性表，釆用顺序存储结构，插入一个元素要平均移动表中个元素。8、用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234,为了得到1342出栈顺序，相应的S,X操作串为o9、在单链表中设置头结点的作用是。10、含12个结点的平衡二叉树的最大深度是(设根节点的深度是1)□11、在一棵二叉树中，度为2的结点有50个，度为1的结点有20个，度为0的结点有个12、有n(n^l)个结点的有向强连通图最少有条边。13、判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用14、空字符串与空格串的区别在于□15、已知某二叉树的后序遍历序列是BEDCA,屮序遍历序列是BADCE,那么它的前序遍
7、历序列是o四、算法设计1、假设用于通信的电文由字符集｛A,B,C,D,R｝中的字母构成，这5个字母在电文中出现的频率依次为｛40,20,10,10,20｝。请画出对应的编码哈夫曼树(Huffman)；求出每个字符的哈夫曼编码。2、简要说明快速排序的排序思想.根据所给序列(49,38,65,97,76,13,27,50),设选第一个元素为支点/参考值(pivot),写出快速排序的第一趟排序的结果。3、图G各顶点的连接关系及
