数据结构 期末复习

1、数据结构 设n为正整数.下列程序段中前置以的语句的频度为（ A ）。 i = 1; k = 0; While(i = n-1) k+= 10*i; i+; A) n 1 B) n C) n + 1 D) n 2 高度为 K的二叉树最大的结点数为（ C ）。 A)2k B)2k-1 C)2k -1 D)2k-1-1 以下数据结构中，哪一个是线性结构（ D ）？ A)广义表 B) 二叉树 C) 稀疏矩阵 D) 串 若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为：( ) A.4 B.5 C.6 D.7 abc acb bac bca cab cba.设串s1=ABCDE

2、FG，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 BCDEFBCDEFGBCPQRSTBCDEFEF解：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),

3、2)subs(s1, 5, 2)= EF;所以con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)con( BCDEF, EF)之连接，即BCDEFEF 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。向一个长度为n的向量的第i个元素(1in+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 图有 邻接矩阵 、 邻接表 等存储结构，遍历图有 深度优先遍历 、 广度优先遍历 等方法。 设有一稀疏图

4、G，则G采用 邻接表 存储较省空间。 设有一稠密图G，则G采用 邻接矩阵 存储较省空间。 若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔(Kruskal) 算法来求解。 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 链表适用于 A 查找A顺序 B二分法 C顺序，也能二分法 D随机对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？ 答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。 二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。已知有向图的正邻接链表的存储结构如下，从