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

《数据结构提高》试卷考查复习题面《数据结构提高》试卷考查复习题面②判断题①单选题⑦算法设计题⑤②判断题①单选题⑦算法设计题⑤画图题⑥计算题④简答题③填空题目录TOC\o"1-3"\h\u5939《数据结构提高》试卷考查复习题 页29463《数据结构提高》试卷考查复习题 一、单项选择题（抽考10小题，每小题2分，共20分）1．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的右孩子结点的编号为（C）。左孩子节点编号为2i A2i+1 B2i Ci/2 D2i-12．下面程序段的时间复杂度是（C）。for（i＝0；i＜n；i＋＋）for（j＝0；j＜n；j＋＋）A[i][j]＝0； AO(n)BO(nlog2n)CO(n2)DO(n3/2)3．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（C）。 Ahead==null Bhead->next==null Chead->next==head Dhead!=null4．设某棵二叉树的高度为8，则该二叉树上叶子结点最多有（B）。2^(8-1) A64 B128 C512 D10245.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为__D__。**********注意：是链式栈选D，顺序栈选B********** Atop=top+1; Btop=top-1; Ctop->next=top; Dtop=top->next;6.以下数据结构中哪一个是线性结构？__B__A树B栈C图D二叉树7.设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是__C__。 An-i Bn-1-i Cn+1-i D不能确定8.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是__D__。AedcbaB．decbaC．abcdeD．dceab9.线性表是具有n个__B__的有限序列。A．字符B．数据元素C．数据项 D．表元素10.一个非空广义表的表尾__D__。 *****非空广义表,除表头外,其余元素构成的表称为表尾,所以非空广义表尾一定是个表*****

A．不可能是子表B．只能是原子C．可以是子表或原子D．只能是子表11．数据的最小单位是__D__。A．数据元素B.记录C.数据对象D.数据项12.对于一个具有n个结点和e条边的无向图，若采用邻接表表示，所有边链表中边结点的总数为__C__。A.e/2B.eC.2eD.n+e13.数组a[1..6,1..5]（无0行0列）以列序为主序顺序存储，a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是__A__。A.1026B.1040C.1042D.104614.某线性表常发生的操作为删除第一个数据元素和在最后一个元素后添加新元素，采用__D__的存储结构，能使其存储效率和时间效率最高。A．单链表 B．仅用头指针的循环链表C．双向循环链表 D．仅用尾指针的循环链表15.在一个单链表中，已知q所指向的结点是p指向的结点的直接前驱结点，若在q所指向的结点和p指向的结点间插入s所指向的结点，则执行__C_。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;16.若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指针rear指向尾元素后的空单元，则当前队列中的元素个数为__A__。A.(rear-front+m)%mB.rear-front+1C.rear-frontD.rear-front-117.栈和队列的共同点是__C__。A.先进先出 B.后进先出C.只允许在端点处插入和删除元素 D.运算受限的线性表18.一棵深度为5的完全二叉树，叶结点数最大值和最小值分别为__B__。A.10，5B.16，8C.8，4D.32，1619.折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90),若查找元素75,需依次与表中元素__A__进行比较。A.65,80,70,75B.65,85,75C.65,80,75D.70,85,7520.算法suanfa的时间复杂度为__A__。 intsuanfa(intn){inti=1；while(pow(2,i)<=n)/*pow(2,i)表示2i*/i=i+1；returni；}A.O(logn)B.O()C.O(n2)D.O(n)

二、判断题（共10小题，每小题1分，共10分）1．中序遍历一棵二叉排序树得到的结点序列一定是有序的序列。（×）2．由树转化成二叉树，该二叉树的右子树不一定为空。（×）3．线性表中的所有元素都有一个前驱元素和后继元素。（×）4.顺序存储方式只能用于存储线性结构。（×）5.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。(√)6.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（×）7.在Huffman树中只有度为2和度为0的节点。（√）8.在n个节点的二叉链表中有n+1个空的指针域。（√）9.最小代价生成树的形状不唯一，但各边权值之和必相等。（×）10.算法的时间复杂度与计算机硬件有关。（×）三、填空题（每小题1分，共12分）1.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。2.评价算法的优劣通常主要考虑算法的时间复杂度和空间复杂度这两方面。3.若对一个线性表经常进行查找操作，而很少进行插入和删除操作时，则采用顺序存储结构为宜，相反，若经常进行的是插入和删除操作时，则采用链式存储结构为宜。5.对于栈只能在栈顶位置插入和删除元素。6.设s1='Good',s3='Luck!',则s1和s2连接的结果是GoodLuck。7.完全二叉树中第4层上最少有8个结点，最多有15个结点。【最少2^(n-1)和最多2^n-1】8.顺序查找、折半查找、分块查找都属于静态查找。

四、简答题（共2小题，每小题5分，共10分。）1.已知一棵完全二叉树的第6层(设根为第1层)有8个叶结点，则该完全二叉树的结点个数最多和最少分别是多少？答：分析图如右侧图所示完全二叉树的结点个数最多有（27-1）-（2*8）=127-16=111个完全二叉树的结点个数最少有（25-1）+8=31+8=39个完全二叉树分析图2.设文件R共有1500条记录，磁盘的读、写单位为250条记录，内存可提供750条记录的空间，试简要说明对文件R的排序过程。答：第一步，每次将三个记录块即750个记录有外存读到内存，进行内部排序，整个文件被分成2个有序子序列，然后分别把它们写到外存上去。第二步，两两归并有序子文件，进行了一趟，最终成为了一个有序文件。

五、画图题（抽考2小题，每小题6分，共12分。）1.从顶点D出发,用Prim算法求网N的一棵最小生成树并计算各边权值之和。答：最小生成树如图所示 网N的最小生成树各边权值之和为：DC+CA+AB+CG+GE+EF=5+1+3+5+6+4=242.已知一棵二叉树的中序序列和后序序列分别为BCDEAFHG和DECBHGFA,画出这棵二叉树。答：二叉树如图所示对给定的关键字序列（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|…..…….六、计算题（共3小题，每小题12分，共36分。）1.设对18个记录的表作折半查找，(1)画出折半查找过程的判定树；(2)假定每个元素的查找概率相等,试计算查找成功时的平均查找长度。答：折半查找判定树如图所示。查找成功的平均查找长度为：ASL成功=（1*1+2*2+4*3+8*4+3*5）/18=64/18=32/92.给定一组权值{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)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等,计算查找成功及查找失败时的平均查找长度。答：线性探测法如下图所示。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

七、算法设计题（抽考1题，共12分。）题1.设a[]的初值为（119，527，9，768，22，549），a[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];>>}（1）当i=0时，给出循环体执行完后a[]的值。（6分）（2）说明该程序段的功能。（6分）答：（1）a[]={22,527,768,119,9,549}（2）实现基数排序功能题2.intSearch_Bin(SSTableST,KeyTypekey){//在有序表ST中折半查找其关键字等于key的数据元素。//如果找到，则函数值为该元素在表中的位置，否则为0。>> low=1;high=ST.length;//置区间初值>> while(low<=high){>> mid=(low+high)/2;>> if（EQ(key,ST.elem[mid].key))>>