数据结构 期末复习

数据结构•设n为正整数.下列程序段中前置以@的语句的频度为（A）。•i=1;k=0;•While(i=n-1){•@k+=10*i;•i++;•}•A)n–1B)nC)n+1D)n–2••高度为K的二叉树最大的结点数为（C）。•A)2kB)2k-1C)2k-1D)2k-1-1•以下数据结构中，哪一个是线性结构（D）？•A)广义表B)二叉树C)稀疏矩阵D)串•若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为：()•A.4B.5C.6D.7•abcacbbacbca•cabcba.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是：DＡ．BCDEFＢ．BCDEFGＣ．BCPQRSTＤ．BCDEFEF解：con(x,y)返回x和y串的连接串，即con(x,y)＝‘ABCDEFGPQRST’；subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，则subs(s1,2,len(s2))＝subs(s1,2,5)=’BCDEF’;subs(s1,len(s2),2)＝subs(s1,5,2)=’EF’;所以con(subs(s1,2,len(s2)),subs(s1,len(s2),2))＝con(’BCDEF’,’EF’)之连接，即BCDEFEF•向栈中压入元素的操作是先移动栈顶指针，后存入元素。•线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。•错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1个元素。图有邻接矩阵、邻接表等存储结构，遍历图有深度优先遍历、广度优先遍历等方法。设有一稀疏图G，则G采用邻接表存储较省空间。设有一稠密图G，则G采用邻接矩阵存储较省空间。若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔(Kruskal)算法来求解。在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。链表适用于A查找A．顺序B．二分法C．顺序，也能二分法D．随机对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？•答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。•二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是(B)。•A)1234B)1423•C)1324D)1432