数据结构试题及答案.doc

数据结构试题1总分数：100总时间：120一、单选题15道,共30分。1、二叉树是非线性数据结构，所以（ ）。（）它不能用顺序存储结构存储; （）它不能用链式存储结构存储; （）顺序存储结构和链式存储结构都能存储; （）顺序存储结构和链式存储结构都不能使用2、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ） （A）选择排序 （B）希尔排序 （C）归并排序 （D）快速排序3、在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。(A) 3 (B) 2 (C) 1 (D) 1/24、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （ ） （A）110 （B）108 （C）100 （D）1205、请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用二分法查找关键码17需做（ ）次关键码比较。 （A）2 （B） 3 （C）4 （D）56、在一个单链表中，若删除p所指结点的后续结点，则执行（ ）（A）p=p-next; p-next=p-next-next;（B）p-next=p-next-next;（C）p-next=p-next; （D）p =p-next-next;7、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ ） (A) 0 2 4 3 1 5 6 (B) 0 1 3 6 5 4 2(C) 0 4 2 3 1 6 5 (D)0 3 6 1 5 4 28、在一个长度为n的顺序存储线性表中，向第i个元素(1in+1)之前插入一个新元素时，需要从后向前依次后移( )个元素。 (A)n-i (B)n-i+1 (C) n-i-1 (D) i9、若让元素1，2，3依次进栈，则出栈次序不可能出现( )情况。 (A) 3，2，1 (B) 2，1，3 (C) 3，1，2 (D) 1，3，210、在一个循环顺序队列中，队首指针指向队首元素的( )位置。 (A) 前一个 (B) 后一个 (C) 当前 (D) 后面11、根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为( )。 (A) O(n) (B) O(log2n ) (C) O(n2) (D) O(nlog2n)12、下列关于二叉树遍历的叙述中，正确的是( ) 。(A)若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点(B)若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点(C)若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点(D)若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点13、对n个记录的文件进行快速排序，所需要的辅助存储空间为( )。(A) O（1）(B) O（1og2n）(C) O（n） (D) O（n2）14、下列算法的时间复杂度是（ ）for （i0；iN；i）for（j0；jn；j）cijij；(A) O（1） (B)O（n） (C) O（log2n） (D) o（n2）15、设S3=IAM，S4A TERCHER，则 StfCmp（S3，S4）( )(A) IAM (B) IAM A TERCHER(C) IAMATERCHER (D) ATERCHER二、填空题10道,共20分。1、对某二叉树进行前序遍历的结果为EBADCFHGIKJ，中序遍历的结果为ABCDEFGHIJK,则后序遍历的结果为_。2、在树形结构中，树根结点没有_结点，其余每个结点有且只有_个前驱结点；叶子结点没有_结点，其余每个结点的后续结点数可以_。3、设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第_次匹配成功。4、拓扑排序算法是通过重复选择具有_个前驱顶点的过程来完成的。5、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素_比较大小。6、已知以二维数组表示的图的邻接矩阵如下：那么针对该邻接矩阵的从顶点1进行深度编历所得的顶点访问序列为 _。广度编历所得的顶点访问序列为_。7、在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_，整个堆排序过程的时间复杂度为_。8、在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为_参数。9、假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)，则度为3、2、1、0的结点数分别为_、_、_和_个。10、假定一棵二叉树顺序存储在一维数组a中，则ai元素的左孩子元素为_，右孩子元素为_，双亲元素(i1)为_。三、叙述题5道,共25分。1、设二叉树的顺序存储结构如下：1). 根据其存储结构，画出该二叉树。2). 写出按前序、中序、后序编历该二叉树所得的结点序列。2、考虑下图：）从顶点出发，求它的深度优先生成树。）从顶点出发，求它的广度优先生成树。）根据普里姆（rim）算法，求它的最小生成树。3、假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10. (1)为这8个字母设计哈夫曼编码。 (2)若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?4、用三元组表表示下列稀疏矩阵：5、将一棵二叉树（如下图）转化成相应森林。四、分析题2道,共10分。1、假设两个队列共享一个循环向量空间（参见下图），其类型Queue2定义如下 ：Typedef structDataType dataMaxSize;int front2,rear2;Queue2;对于i0或1，fronti和reari分别为第i个队列的头指针和尾指针。请对一下算法填空，实现第i个队列的入队操作。int EnQueue(Queue2*Q,int i,DateType x)/若第i个队列不满，则元素x入队列，并返回1；否则返回0if(i1)return 0;if(Q-reari=Q-front )return 0;Q-data =x; Q-reari= ;Return 1;2、阅读下面的算法LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针If(L&L-next)q=L;L=L-next;p=L;S1:while(p-next)p=p-next;S2:p-next=q;q-next=NULL; Return L;请回答下列问题：1）说明语句S1的功能；2）说明语句组S2的功能；3）设链表表示的线性表为（a1,a2,an），写出算法执行后的返回值所表示的线性表。五、设计题2道,共15分。1、以二叉链表为存储结构， 写一算法交换各结点的左右子树。 要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。2、已知线性表中的元素以值递增有序排列并以单链表作为存储结构，试写一算法实现删除表中所有值相同的多余元素（使得操作后的线性表中所有的值均不为相同），同时释放被删除结点的空间，并分析你的算法的时间复杂度。答案1一、单选题答案如下。1、C 2、D 3、B 4、B 5、B 6、B 7、c 8、B 9、C 10、A 11、D 12、D 13、B14、D 15、D 二、填空题答案如下。1、ACDBGJKIHFE 2、前驱 ,1,后续,任意多个 3、答案：6 4、0 5、28，6，12，20 6、1、6、2、3、4、5、10、9、7、8 , 1、6、7、9、2、3、10、5、4、8 7、O(log2n),O(nlog2n) 8、引用 (或指针) 9、2、1、1、6 10、a2*i、a2*i+1、ai/2 三、叙述题答案如下。1、(1)见图片(2):前序:EADCDFHGI中序:ABCDEFGHI后序:BCDAGJHFE2、nu3、(1)根据上图可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000 (2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87% 其平均码长是等长码的87%。 所以平均压缩率为13%。4、nu5、nu四、分析题答案如下。1、答案：（i+1）%2(或1-i) 2分Q-reari 1分(Q-reari+1)%MaxSize 2分2、1）查询链表的尾结点（1分）2）将第一个结点链接到链表的尾部，作为新的尾结点（2分）3）返回的线性表为（a2,a3,an,a1）（2分）五、设计题答案如下。1、#include #include bintree.h void ChangeBinTree(BinTree *T) /交换子树 if(*T) /这里以指针为参数使得交换在实参的结点上进行 /后序遍历 BinTree temp; ChangeBinTree(&(*T)-lchild); ChangeBinTree(&(*T)-rchild); temp=(*T)-lchild; (*T)-lchild=(*T)-rchild; (*T)-rchild=temp; void PrintNode(BinTree T) /以前序序列打印结点数据 if(T) printf(%c,T-data); PrintNode(T-lchild); PrintNode(T-rchild); void main() /测试程序 BinTree root; CreatBinTree(&root);/建立二叉链表 PrintNode(root); /输出原表 printf(n); ChangeBinTree(&root);/交换子树 PrintNode(root); /输出新表 printf(n); /可输入abc d ef g 来测试(注意空格)，看看对不对?2、答案Status Delete_Equal(Linklist &L)/删除元素递增排列的链表L中所有值相同的元素 p=L-next;q=p-next; /p,q指向相邻两元素 while(p-next) if(p-data!=q-data) p=p-next;q=p-next; /当相邻两元素不相等时,p,q都向后推一步 else while(q-data=p-data) free(q); q=q-next; p-next=q;p=q;q=p-next; /当相邻元素相等时删除多余元素 /else /while/Delete_Equal试卷 1 分析一、单选题分析如下。试卷内编号 试题难度 考察知识点 1 3 二叉树的定义和性质 2 5 各种排序方法的比较和综合应用 3 2 图的定义和特点 4 2 基本概念 5 3 折半查找(二分查找) 6 2 线性表的链式存储 7 1 图的存储结构 8 4 线性表的顺序存储 9 4 栈的定义和特点 10 3 队列的定义和特点 11 3 线索二叉树 12 3 遍历二叉树 13 4 快速排序 14 2 算法及算法分析 15 4 串的基本操作的实现二、填空题分析如下。试卷内编号 试题难度 考察知识点 1 4 遍历二叉树 2 1 树的定义和特点 3 4 串的基本操作的实现 4 3 简单排序 5 2 折半查找(二分查找) 6 2 图的