《数据结构》试题及答案-文华学院

《数据结构提高》试卷考查复习题面①单选题②判断题③填空题④简答题⑤画图题⑥计算题⑦算法设计题目录《数据结构提高》试卷考查复习题 1一、单项选择题（抽考10小题，每小题2分，共20分） 1二、判断题（共10小题，每小题1分，共10分） 4三、填空题（每小题1分，共12分） 4四、简答题（共2小题，每小题5分，共10分） 5五、画图题（抽考2小题，每小题6分，共12分） 6六、计算题（共3小题，每小题12分，共36分） 7七、算法设计题（抽考1题，共12分） 9第第PAGE9页《数据结构提高》试卷考查复习题一、单项选择题（10220分）1i的右孩子结点的编号为（C。2iA2i+1 B2i Ci/2 D2i-1下面程序段的时间复杂度是（Cfor（i＝0；i＜ni＋＋）for（j＝0；j＜n；j＋＋）A[i][j]＝0；AO(n) BO(nlog2n) CO(n2) DO(n3/2)设带有头结点的单向循环链表的头指针变量为hea，则其判空条件是（CAhead==null Bhead->next==nullChead->next==head

Dhead!=null设某棵二叉树的高度为8，则该二叉树上叶子结点最多有（B。A64 B128 C512 D1024设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为 。**********注意：是链式栈选D，顺序栈选B**********Atop=top+1; Btop=top-1;Ctop->next=top; Dtop=top->next;以下数据结构中哪一个是线性结构？ B A树 B栈 C图 D二叉树设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出列中第i个输出元素是 C 。An-i Bn-1-i Cn+1-i D不能确定一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 D 。Aedcba B．decba C．abcde D．dceab线性表是具有n个 B 的有限序列。字符 B．数据元素 C．数据项 D．表元素一个非空广义表的表尾 D 。*****非空广义表,除表头外,其余元素构成的表称为表尾,所以非空广义表尾一定是个表*****A．不可能是子表B．只能是原子C．可以是子表或原子D．只能是子表数据的最小单位是 D 。数据元素 B.记录 C.数据对象 D.数据项对于一个具有n个结点和e条边的无向图，若采用邻接表表示，所有边链表中边结点总数为 C 。A.e/2 B.e C.2e D.n+e13.数组a[1..6,1..5]（无0行0列）以列序为主序顺序存储，a[1][1]的地址为1000，个元素占2个存储单元，则a[3][4]的地址是 A 。A.1026 B.1040 C.1042 D.1046某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用 D 的存储结构，能使其存储效率和时间效率最高。A．单链表 B．仅用头指针的循环链C．双向循环链表 D．仅用尾指针的循环链表qpqpss->next=p->next;p->next=s;p->next=s->next;s->next=p;q->next=s;s->next=p;p->next=s;s->next=q;

C_。若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指rear指向尾元素后的空单元，则当前队列中的元素个数为 A 。A.(rear-front+m)%m B.rear-front+1C.rear-front D.rear-front-1栈和队列的共同点是 C 。A.先进先出 B.后进先出C.只允许在端点处插入和删除元素 D.运算受限的线性表一棵深度为5的完全二叉树，叶结点数最大值和最小值分别为 B A.10，5 B.16，8 C.8，4 D.32，1619.折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90),若查找元素75,需依次与表中元素 A 进行比较。A.65,80,70,75B.65,85,75 C.65,80,75 D.70,85,7520.算法suanfa的时间复杂度为 A intsuanfa(intn){inti=1；while(pow(2,i)<=n) /*pow(2,i2ii=i+1；returni；}A.O(logn) B.O() C.O(n2) D.O(n)二、判断题（10110分）（×）（×）（×）（×）√)（×）Huffman20（√）nn+1（√）（×）（×）三、填空题（每小题1分，共12分）线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多形结构中元素之间存在多对多关系。评价算法的优劣通常主要考虑算法的时间复杂度和 空间复杂度 这两方面。若对一个线性表经常进行查找操作，而很少进行插入和删除操作时，则采用顺序结构为宜，相反，若经常进行的是插入和删除操作时，则采用链式存储结构为宜。栈顶位置插入和删除元素。设s1='Good',s3='Luck!',则s1和s2连接的结果是GoodLuck 。4层上最少有8152^(n-1)和最多2^n-1】顺序查找、折半查找、分块查找都属于静态查找。四、简答题（2510）1.6层(1层)8多和最少分别是多少？答：分析图如右侧图所示完全二叉树分析图2.R1500250750条记录的空R答：第一步，每次将三个记录块即750个记录有外存读到内存，进行内部排序，整个文件被分成完全二叉树分析图2.R1500250750条记录的空R答：第一步，每次将三个记录块即750个记录有外存读到内存，进行内部排序，整个文件被分成2个有序子序列，然后分别把它们写到外存上去。第二步，两两归并有序子文件，进行了一趟，最终成为了一个有序文件。五、画图题（2612）DPrimN答：最小生成树如图所示网N的最小生成树各边权值之和为：DC+CA+AB+CG+GE+EF=5+1+3+5+6+4=24已知一棵二叉树的中序序列和后序序列分别为BCDEAFHG和答：二叉树如图所示对给定的关键字序列（52，48，67，92，23，7，12）增的序列，写出排序过程示意图。（6分）答：排序过程示意图步骤步骤线性表初始52，48，67，92，23，7，1217，48，|67，92，23，52，1227，12，67，|92，23，52，4837，12，23，92，|67，52，4847，12，23，48，67，|52，9257，12，23，48，52，67，|9267，12，23，48，52，67，92|…..…….六、计算题（六、计算题（31236）1.18(1)假定每个元素的查找概率相等,试计算查找成功时的平均查找长度。答：折半查找判定树如图所示。ASL

=（1*1+2*2+4*3+8*4+3*5）/18=64/18=32/9成功2.给定一组权值{12，4，5，6，1，2}WPL答：哈弗曼树如图所示。带权路径长度为：WPL=4*（1+2）+3*（4+5+6）+1*12=693.(39,25,24,50,12,14,20,19,37,6),(Hash),为:H(key)=key%13,key为关键字,%为求余运算符；用开放定址法处理冲突,再散列法查找空位,A[15](1)素的查找概率相等,计算查找成功及查找失败时的平均查找长度。答：线性探测法如下图所示。01234578910111239121437205062425等概率情况下查找成功的平均查找长度为：ASL成功=（1+1+1+1+3+2+1+1+6+4）/10=21/10等概率情况下查找失败的平均查找长度为：ASL不成功=（5+4+3+2+1+1+5+4+3+2）/10=30/10七、算法设计题（112）1.a[]（11527976822549a[0>> for(i=0,d=1;i<3;i++,d*=10)>> {>> for(j=0;j<10;j++) count[j]=0;>> for(j=0;j<6;j++) count[a[j]/d%10]++;>> for(j=1;j<10;j++) count[j]=count[j-1]+count[j];>> for(j=5;j>=0;j--) b[--count[a[j]/d%10]]=a[j];>> for(j=0;j<6;j++) a[j]=b[j];>>