《《数据结构》题库及答案.docx》由会员分享，可在线阅读，更多相关《《数据结构》题库及答案.docx（14页珍藏版）》请在三一办公上搜索。
1、数据结构题库及答案一、选择题1. 线性表的顺序存储结构是一种 _的存储结构，线性表的链式存储结构是一种的存储结构。a. 随机存储：b.顺序存储：c.索引存取：d. HASH存取2. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输岀序列是a. edcba; b decba; c. dceab;3. 一个队列的入队序列是1, 2, 3, 4,则队列的输出序列是a. 43,2,1； b 1,23,4; c. 143,2;,2,4,14. 在一个单链表中，已知p结点是q结点的直接前驱结点，若在p和q之间插入结点s,则执行的操作是oa. s-nxet=p-next; p-next=s;b.cp-
2、next=s-next; s-next=p;d qnext二s;snext 二 p;e. 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至少需要个字节。a907. 在线索二叉树中，结点p没有左子树的充要条件是 oa. p-lch=NULLb p-ltag=lCa p-ltag=l 且 p-lch=NULLe.以上都不对&在栈操作中，输入序列为(A, B. C, D),不可能得到
3、的输出序列为：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 cedba 10设矩阵A是一个对称矩阵，为了节省存储空间，将其下三角部分(见下图)按行序存放在一维数组Bl.n(n-l)/2中，对任一上三角部分元素在一维数组B的存放位置是11nnnlA、诧一1)2+丿一1B、c、D、图G中有n个顶点，nJ条边，那么图G定是一棵树吗B、一泄不是C、不_定12.用某种排序方法对关键字序列25,84,21,如
4、下：25,84.21.47,15,27,68,35,2020,15.21,25,47,27.68,35,8415 20.21,2535,27,47,68,8415,20,21,25.27,35,47,68,84A、一定是则所采用的排序方法是47, 15. 27, 68, 35, 20进行排序时，元素序列的变化情况A、快速排序B、希尔排序a.p-next=s;s-prior=p;p-next-prior=s;sn ext=p-next;b.pn ext=s;pn ext-prior=s;s-prior=p;sn ext=p-next;c.s-prior=p;sn ext=p-n ext;pn e
5、xt=s;pn ext-prior=s;d.s-prior=p;s-next=p-next;pn ext-prior=s; p-next=s;C.归并排序D、选择排序13. 表达式a*(b+c)-d的后缀表示式是oa. abcd-*+; b. abc+*d-; c. abc*+d-; d. -*a+bcd;14. 在双向循环链表中的结点P之后插入结点S的操作是 15.如下图所示循环队列，其中的数据元素个数是a.可以顺序存储b.数据元素是一个字符C可以链接存储d. 23, 14, 55, 20, 84, 27, 68, 11, 10, 77,采用哈希函数：H(key)=key%13 和 2开放地
6、址法的线性探测再散列方法解决冲突，已知英装填因子 = -,试对该关键字序列构造哈希表，并 3求其査找成功时的平均査找长度。5.画岀和下列已知序列对应的森林F:森林的先序遍历序列是：ABCDEFGHIJKL；森林的中序遍历序列是：CBEFDGAJIKLHo6 假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为 请给这8个字母设计哈夫曼编码。7.对下图所示的无向带权图， 给岀其邻接矩阵，并按Prim算法求苴最小生成树: 给出其邻接表，并按Kruskal算法求其最小生成树。&我们已经知道对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。 试问： n=7时
7、在最好情况下需进行多少次比较请说明理由。 对n=7给岀一个最好情况的初始排列实例。9.下列算法为斐波那契查找算法：int FibSearch (SqList r, KeyType k)j=l；while (fib(j)n+l) j=j+l;mid=n-fib(jey): found二true; break;case (krmid.key):if (fl=l) mid=O;else mid=mid+f2; fl=fl-f2; f2=f2-fl; break;if found return mid; else return 0; A = (q,dC = (abaPj Y pk Y621912I)
8、+ 1PiA、B C C =(5片皿2上2,上皿上卄小、b) mn ext;pb=lb-n ext;lc=la;pc=lc;pc-next=NULL;while ( pa & pb )if (pa-data data)u=pa next;pan ext=pc-next;pc-next=pa;pa=u;elseu=pb-next;pb-next=pc- n ext;Ypc-next=pb;pb 二 u;while (pa )u=pa-n ext;pan ext=pc-next;pcn ext=pa;pa=u;while (pb )u=pb-next;pb-next=pc-n ext;pcn ex
9、t=pb;pb=u;delete(lb)5.解答：本题涉及的存储结构描述如下: 顺序存储结构： const maxsize=100;typedef int ElemType;typedef structElemType rmaxsize+l;int length;/实际长度SqList;Void inert_xJnto(SqList& va, int x)j=;while (x=0)U+1=U;j-;j+l=X；=+l;五.简答题1. 存储图：2树:二叉树:六、证明题1. 证明：反证法。设存在，Y j Yk使得门Y Pk Y Pi。贝IJ由jYk得出栈序列门，厂，几；由PjY 兀Y H得知入栈序列为Pj、Pk , Pi ；由知戸最先出栈，则由知出栈的序列将是，几，厂。此岀栈序列与由得到的岀栈序列矛盾。因此假 设错误。从而若借助栈由输入序列1,2,”得到的输出序列为门，“2,卩”（它是输入序列的一个排列），则 在输出序列中不可能存在iY JYk使得厂 Y几VP, 证毕2. 证明：设总结点数为”，贝IJ:n = n0 +：又该满k叉树上的每个结点出根之外都一个分支进入，这些分支是由非叶子结点产生的，因此有：n = k叫+1：由和得：川（）+ 坷=kn +1n0 = k 叫 +1 _ n = （ _ l）q +1证毕
