《数据结构》题库及答案.docx

数据结构题库及答案一、选择题1. 线性表的顺序存储结构是一种的存储结构，线性表的链式存储结构是一种的存储结构。a.随机存储；b.顺序存储；c.索引存取；d.HASH存取2. 一个栈的入栈序列是a,bed,e,则栈的不可能的输出序列是oa.edcba;b.decba;c.dceab;3. 一个队列的入队序列是1,2,3,4,则队列的输出序列是。a.4,3,2；b.1,2,3,4;c.1,4,3,2;,2,4,14 .在一个单链表中，已知P结点是q结点的直接前驱结点，若在P和q之间插入结点s,则执行的操作是。a. s->nxet=p->next;p->next=s;b. Ic. p->next=s->next;s->next=p;d. q->next=s;s->next=p;e. p->next=s;s->next=q;5 .设有两个串p,q,求q在P中首次出现的位置的运算称作。a.联接b.模式匹配c.求子串d.求串长6 .二维数组M的成员是6个字符(每个字符占一个存储单元)组成的串，行下标i的范围从。到8,列下标j的范围从1至U10,则存放M至少需要个字节。a.907 .在线索二叉树中，结点P没有左子树的充要条件是oa. p->1ch=NU11b. p->1tag=1c.a.p->1tag=1且p->1ch=NU11e.以上都不对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是一个对称矩阵,为了节省存储空间,将其下三角部分(见下图)按行序存放在一维数组B1.n(n-1)2中，对任一上三角部分元素为/),在一维数组B的存放位置是.D、11.图G中有n个顶点，n1条边，那么图G一定是一棵树吗如下:(20,15,21,25,47,27,68,35,8415,20,21,25,35,27,47,68,84则所采用的排序方法是.A、快速排序B、希尔排序C、归并排序D、选择排序13 .表达式a*(b+c)-d的后缀表示式是。a.abed-*+;b.abc+*d-;c.abc*+d-;d.-*a+bcd;14 .在双向循环链表中的结点P之后插入结点S的操作是ca. 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 .如下图所示循环队列，其中的数据元素个数是n-1串是i种特殊的线性表，其特殊性体现在Oa.可以顺序存储b.数据元素是一个字符C,可以链接存储d. e. 数据元素可以是多个字符17 .数组A中，每个元素Aij的长度是3个字节，行下标i从1到8,列下标j从1到10,从首地址SA开始连续存放在存储器内，存放该数组的单元数是Oa. 80b. 100c. 240d. 27018 .已知某二叉树的先序遍历序列是abdgcefh,中序遍历序列是dgbaechf,则其后序遍历的结点访问顺序序列是Oa. bdgcefhab. gdbecfhac. bdgaechfd.：d. gdbehfca19 .线索二叉树是一种结构。a.逻辑b.逻辑和存储c.物理d.线性20 .在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。a. 1/2b. 1c. 2d.：e.321.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定元素所在的块时，则每块应分为个元素的块时，查找效率最佳。a. 10b. 25d.62522 .一个栈的输入序列是12345,则栈的不可能输出序列是a. 54321b. 45321c. 43512d. 1234523 .完全二叉树一定是满二叉树吗oa.一定是b.不是c.不一定24 .线性表采用链式存储结构时其地址oa.必须是连续的b.部分地址必须是连续的c.一定是不连续的d.连续不连续都可以25 .具有线性结构的数据结构是oa.树b.图c.广义表d.栈26 .下图为顺序队列的初始情况，设a,b,c相继出队列，e,f相继入队列，则指针和分别为a.b. 2,5c. 3,5d. 3,6e. 4,6二、填空题1 .设n行n列的下三角阵A已经压缩存储到一维数组S0当山-1中，若按行序为主序存储，则Aij对应的在S中的存储位置是02 .广义表(a),(b),c),(d)的长度是,深度是o3 .深度为k的完全二叉树至少有一个结点，至多有个结点，若按自上而下，从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号是。4 .根据有向图的宽度优先遍历算法，对下图2所示有向图从顶点V1出发进行搜索，所得到的顶点遍历序列是O图25 .有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,100),当二分查找值为82的元素时，需要经过一次比较就找到。6 .是数据的最小单位。7 .在双向链表中，每个结点有两个指针域，一个是指向另一个指向。8 .设栈ST用顺序存储结构表示，则栈ST为空的条件是o9 .两个串相等的充分必要条件是和对应位置上的字符相等。10 .对于深度为h的二叉树至多有个结点。11 .将一个A15115的对称矩阵压缩存储到一个一维数组中，该数组的长度至少为o三、算法应用题12 数据集4,5,6,7,10,12,18)为结点权值构造HUffman树，请给出构造所得的HUffman树，并求其带权路径长度。13 假设一棵二叉树的先序序列是EBADCFHG1KJ,中序序列是ABCDEFGH1JK。请画出该二叉树。14 已知一颗二叉排序树如下图所示，若依次删除93、19、87、48结点，试分别画出每删除一个结点后得到的二叉排序树。15 已知关键字序列19,O123,14,55,20,84,27,68,11,10,77),采用哈希函数：H(key)=key%13,2和开放地址法的线性探测再散列方法解决冲突，已知其装填因子。=一，试对该关键字序列构造哈希表,3并求其查找成功时的平均查找长度。16 画出和下列已知序列对应的森林F:森林的先序遍历序列是：ABCDEFGHIJK1；森林的中序遍历序列是：Cbefdgajik1Ho17 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为,，。请给这8个字母设计哈夫曼编码。18 对下图所示的无向带权图，给出其邻接矩阵，并按Prim算法求其最小生成树；给出其邻接表，并按KrUSka1算法求其最小生成树。19 我们己经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。试问：n=7时在最好情况下需进行多少次比较请说明理由。对n=7给出一个最好情况的初始排列实例。20 下列算法为斐波那契查找算法：intFibSearch(Sq1istr,KeyTypek)(j=1;whi1e(fib(j)<n+1)j=j+1;mid=n-fib(j-1)÷1;ey):fund=true;break;case(k<rfmid.key):if(!f2)mid=O;e1semid=mid-f2;t=f1-f2;f1=f2;f2=t;break;case(k>rmid.key):if(f1=1)mid=0;e1semid=mid+f2;f1=f1-f2;f2=f2-f1;)break;)iffoundreturnmid;456 .解答：本题涉及的存储结构描述如下:单链表存储结构：typedefstruct1node*1ink1ist;typedefstruct1nodeDataTypedata;1ink1istnext;1node,*1ink1ist;voidmerge_two_asceding_1ink1ist_to_one_desceding_1ink1ist(1ink1ist&1c,1ink1ist1a,1b)(pa=1a->next;pb=1b->next;1c=1a;pc=1c;pc->next=NU11;whi1e(pa&&pb)(if(pa->data<pb->data)>(u=pa->next;pa->next=pc->next;pc->next=pa;pa=u;)e1se(u=pb->next;pb->next=pc->next;¥pc->next=pb;Pb=u;)whi1e(pa)(u=pa->next;pa->next=pc->next;pc->next=pa;pa=u;whi1e(pb)u=pb->next;pb->next=pc->next;pc->next=pb;Pb=u;)de1ete(1b)7 .解答：本题涉及的存储结构描述如下:顺序存储结构：constmaxsize=100;typedefintE1emType;typedefstructE1emTypermaxsize+1;int1ength;实际长度Sq1ist;Voidinert_x_into(Sq1ist&va,intx)(j=；whi1e(x<j)&&(j>=0)(U+1=U;j-;)U+i=;=+1;五、简答题1.存储图：2.树:二叉树:六、证明题1 .证明：反证法。设存在iYjYk使得pjYPkYPie则由iYjYk得出栈序列pi,Pj,pk；由PjYPkYPi得知入栈序列为巳,0t,P;由知Pi最先出栈，则由知出栈的序列将是P,PqPj。此出栈序列与由得到的出栈序列矛盾。因此假设错误。从而若借助栈由输入序列1,2,得到的输出序列为外死，2(它是输入序列的一个排列)，则在输出序列中不可能存在iYjYZ使得pjYPkYpiO证毕2 .证明：设总结点数为，则：n=n0+n1；又该满k叉树上的每个结点出根之外都一个分支进入，这些分支是由非叶子结点产生的，因此有:n=kn+1；由和得：w0+n1=kn+1%=A4+1勺=(21)n1+1证毕