《数据结构》题库及答案

第1页共21页《数据结构》题库及答案一、选择题1．线性表的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。a.随机存储；b.顺序存储；c.索引存取；d.HASH存取2．一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是。a.edcba;b.decba;c.dceab;d.abcde3．一个队列的入队序列是1，2，3，4，则队列的输出序列是。a.4,3,2,1;b.1,2,3,4;c.1,4,3,2;d.3,2,4,14．在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s，则执行的操作是。a.s-nxet=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;5．设有两个串p,q，求q在p中首次出现的位置的运算称作。a.联接b.模式匹配c.求子串d.求串长6．二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要个字节。a.90b.180c.240d.5407．在线索二叉树中，结点p没有左子树的充要条件是。a.p-lch==NULLb.p-ltag==1c.p-ltag==1且p-lch=NULLd.以上都不对8．在栈操作中，输入序列为（A，B，C，D），不可能得到的输出序列为：______A、（A，B，C，D）B、（D，C，B，A）C、（A，C，D，B）D、（C，A，B，D）9．已知某二叉树的后序序列是dabec，中序序列是debac，则它的先序序列是。A、acbedB、decabC、deabcD、cedba10．设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(jiaij，在一维数组B的存放位置是。第2页共21页nnnnaaaaaaA21222111A、12)1(jiiB、12)1(ijjC、ijj2)1(D、jii2)1(11．图G中有n个顶点，n-1条边，那么图G一定是一棵树吗？。A、一定是B、一定不是C、不一定12．用某种排序方法对关键字序列{25，84，21，47，15，27，68，35，20}进行排序时，元素序列的变化情况如下：①{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、选择排序13．表达式a*(b+c)-d的后缀表示式是。a.abcd-*+;b.abc+*d-;c.abc*+d-;d.-*a+bcd;14．在双向循环链表中的结点P之后插入结点S的操作是。a.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;b.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;c.s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;d.s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;15．如下图所示循环队列，其中的数据元素个数是0Q.rearQ.front…m-11…第3页共21页b.(Q.rear-Q.front+m)%mc.Q.rear-Q.frontd.Q.rear-Q.front+1e.(Q.rear-Q.front)%m16．串是一种特殊的线性表，其特殊性体现在。a.可以顺序存储b.数据元素是一个字符c.可以链接存储d.数据元素可以是多个字符17．数组A中，每个元素A[i][j]的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组的单元数是。a.80b.100c.240d.27018．已知某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历的结点访问顺序序列是。a.bdgcefhab.gdbecfhac.bdgaechfd.gdbehfca19．线索二叉树是一种结构。a.逻辑b.逻辑和存储c.物理d.线性20．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。a.1/2b.1c.2d.321．采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块时，则每块应分为个元素的块时，查找效率最佳。a.10b.25c.6d.62522．一个栈的输入序列是12345，则栈的不可能输出序列是。a.54321b.45321第4页共21页c.43512d.1234523．完全二叉树一定是满二叉树吗？。a.一定是b.不是c.不一定24．线性表采用链式存储结构时其地址。a.必须是连续的b.部分地址必须是连续的c.一定是不连续的d.连续不连续都可以25．具有线性结构的数据结构是。a.树b.图c.广义表d.栈26．下图为顺序队列的初始情况，设a,b,c相继出队列，e,f相继入队列，则指针Q.front和Q.rear分别为。54d3c2b1a0a.2,5b.3,5c.3,6d.4,6二、填空题1．设n行n列的下三角阵A已经压缩存储到一维数组S[0..12)1(nn]中，若按行序为主序存储，则A[i][j]对应的在S中的存储位置是。2．广义表（（a），（（b），c），（（（d））））的长度是，深度是。3．深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，从左到右的次序给结点Q.front=0Q.rear=4第5页共21页编号（从1开始），则编号最小的叶子结点的编号是。4．根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点v1出发进行搜索，所得到的顶点遍历序列是。图25．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的元素时，需要经过次比较就找到。6．_____________是数据的最小单位。7．在双向链表中，每个结点有两个指针域，一个是指向_____________,另一个指向_________。8．设栈ST用顺序存储结构表示，则栈ST为空的条件是____________________。9．两个串相等的充分必要条件是_____________________和对应位置上的字符相等。10．对于深度为h的二叉树至多有___________个结点。11．将一个A1515的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为__________。三、算法应用题1．数据集{4，5，6，7，10，12，18}为结点权值构造Huffman树，请给出构造所得的Huffman树，并求其带权路径长度。2．假设一棵二叉树的先序序列是EBADCFHGIKJ，中序序列是ABCDEFGHIJK。请画出该二叉树。3．已知一颗二叉排序树如下图所示，若依次删除93、19、87、48结点，试分别画出每删除一个结点后得到的二叉排序树。0V11V2NULL2V33V4NULL4V5213NULL34NULL13NULL第6页共21页4．已知关键字序列{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key%13，和开放地址法的线性探测再散列方法解决冲突，已知其装填因子32，试对该关键字序列构造哈希表，并求其查找成功时的平均查找长度。5．画出和下列已知序列对应的森林F:森林的先序遍历序列是：ABCDEFGHIJKL；森林的中序遍历序列是：CBEFDGAJIKLH。6．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。请给这8个字母设计哈夫曼编码。7．对下图所示的无向带权图，①给出其邻接矩阵，并按Prim算法求其最小生成树；②给出其邻接表，并按Kruskal算法求其最小生成树。8．我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。试问：①n=7时在最好情况下需进行多少次比较?请说明理由。②对n=7给出一个最好情况的初始排列实例。9．下列算法为斐波那契查找算法：intFibSearch(SqListr,KeyTypek){j=1;while(fib(j)n+1)j=j+1;mid=n-fib(j-1)+1;//若fib(j)=n+1,则mid=fib(j-1)f1=fib(j-2);f2=fib(j-3);found=false;while((mid!=0)&&(!found))switch{62463551V1V2V3V4V5V665第7页共21页case(k==r[mid].key):found=true;break;case(kr[mid].key):if(!f2)mid=0;else{mid=mid-f2;t=f1-f2;f1=f2;f2=t;}break;case(kr[mid].key):if(f1==1)mid=0;else{mid=mid+f2;f1=f1-f2;f2=f2-f1;}break;}iffoundreturnmid;elsereturn0;}//FibSearch其中fib(i)为斐波那契序列。试画出对长度为20的有序表进行斐波那契查找的判定树，并求其等概率时查找成功的平均查找长度。10．对下图所示的AOE网络，计算各活动的最早开始时间e(i)和最迟开始时间l(i)，各事件的最早发生时间ve(i)和vl(i)；并列出各条关键路径。四、算法设计题1．设线性表),,,(),,,,(2121nmbbbBaaaA，试写一按下列规则和并BA,为线性表C的算法，即使得),,,,,,,,,(12211nmmmbbbababaC当nm时；或者),,,,,,,,,(12211mnnnaabababaC当nm时。线性表BA,和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显示存储。2．试完成二叉树按层次（同一层自左至右）遍历的算法。3．试完成求无向图的连同分量个数的算法。4．试写一算法将两个递增有序的带头结点的单链表合并为一个非递增有序的带头结点的单链表。(利用原表结点空间)5．设顺序表va中的数据元素递增有序（数据元素的类型是整型）。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。a9=4a8=7a7=9a5=1a4=1a3=5a2=4a1=6V11V21V31V41V51V61V71V81V91a6=2a10=2a11=4第8页共21页五、简答题1．画出广义表（a,(b,(c,())),(d,e),((f))）的存储图。（链式）2．分别画出具有3个结点的树和具有3个结点的二叉树的所有形态。六、证明题1．试证明：若借助栈由输入序列n,,2,1得到的输出序列为nppp,,,21(它是输入序列的一个排列)，则在输出序列中不可能出现这样的情况：存在kji使得ikjppp。2．试证明：在一棵满k叉树上的叶子结点数0n和非叶子结点数1n之间满足一下关系：1)1(10nkn《数据结构》作业参考答案一、选择题1．ab2．c3．b4．a,d5．b第9页共21页6．d7．b8．D9．D10．B11．C12．C13．c14．d15．a16．b17．c18．d19．c20．b21．b22．c23．c24．d25．d26．c二、填空题1．jii2)1(2．343．2k-1,2k-1,2k-2+14