数据结构题库

1、2013-2014学年二学期数据结构期末考试模拟试卷(16卷)一、应用题(3小题,共24分)1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用0，1进行前缀编码，问该字符串的编码至少有多少位。【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。2已知关键码序列为（Jan, Feb, Mar, Apr, May, Ju

2、n, Jul, Aug, Sep, Oct, Nov, Dec），散列表的地址空间为016，设散列函数为H(x)= i/2 (取下整数) ，其中i为关键码中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。【解答】H(Jan)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0H(May)=13/2=6, H(Jun)=10/25, H(Jul)=10/25, H(Aug)=1/2=0H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/

3、2=2采用链地址法处理冲突，得到的开散列表如下：平均查找长度=(1×7+2×4+3×1)/12=18/123分析下面各程序段的时间复杂度（1） s1(int n) int p=1,s=0;  for (i=1;i<=n;i+)     p*=i;s+=p; return(s); O(n)（2） s2(int n)x=0;y=0; For (k=1;k<=n;k+) x+; For (i=1;i<=n;i+) For (j=1;j<=n;j+)y+; O(n2)1下述算法的功能是什么?（1）（

4、1）返回结点*p的直接前趋结点地址。  （2）交换结点*p和结点*q（p和q的值不变）。1对给定的一组权值W（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2=1202已知散列函数H(k)=k mod 12，键值序列为(25, 37, 52, 43, 84, 99, 120, 15, 26, 11, 70, 82)，采用链表法处理冲突，试构造散列表。【解答】H(25)=1, H(37)=1,

5、 H(52)=4, H(43)=7, H(84)=0, H(99)=3,H(120)=0, H(15)=3, H(26)=2, H(11)=11, H(70)=10, H(82)=10构造的开散列表如下：3分析下面各程序段的时间复杂度（1）      for (i=0;i<n;i+)         for (j=0;j<m;j+)          &#

6、160; Aij O(n*m)（2） s=0;       for (i=0;i<n;i+)         for (j=0;j<n;j+)            s+=Bij;         sum=s; O(n2)  （

7、3） A=B; B=C; C=A; O(1)3设无向图G（所下图所示），要求给出从1出发对该图进行深度优先和广度优先遍历的序列。   深度：125364，广度：123456   （不唯一）4已知无向图G的邻接表如图所示，分别写出从顶点1出发的深度遍历和广度遍历序列。【解答】深度优先遍历序列为：1，2，3，4，5，6   广度优先遍历序列为：1，2，4，3，5，6二、判断正误(7小题,共14分)1线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。（ ）2一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，

8、A，B，D。（ ）3稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）4如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（  ）5用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。（ ）6向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（  ）7  逻辑结构与数据元素本身的内容和形式无关。（ ）1对链表进行插入和删除操作时不必移动链表中结点。(  )3如果两个串含有相同的字符，则说明它们相等。(   )4在线索二叉树中，任一结点均有指向其前趋和后继的线索。(

9、0;)5带权无向图的最小生成树是唯一的。（   ）6稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（  ）7无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的。(   )8分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（  ）1由树转化成二叉树，该二叉树的右子树不一定为空。（  ）2稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（  ）4分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（  ）5设初始记录关键字基本有序，则

10、快速排序算法的时间复杂度为O(nlog2n)。（  ）6每种数据结构都具备三个基本操作：插入、删除和查找。（  ）1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（×） 2在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。3链表的每个结点都恰好包含一个指针域。（×）4有向图的邻接表和逆邻接表中表结点的个数不一定相等。（×）5对连通图进行深度优先遍历可以访问到该图中的所有顶点。（  ）6当装填因子小于1时，向散列表中存储元素时不会引起冲突。（×）2  线性表的逻辑顺

11、序和存储顺序总是一致的。（×）3非空的双向循环链表中任何结点的前驱指针均不为空。（  ）4子串“ABC”在主串“AABCABCD”中的位置为2。（  ）5数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。（×）7用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。（×）9当装填因子小于1时，向散列表中存储元素时不会引起冲突。（×）10散列技术的查找效率主要取决于散列函数和处理冲突的方法。（×）1线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。（ 

12、; ）2稀疏矩阵压缩存储后，必会失去随机存取功能。（  ）5对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。（  ）6当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（  ）7数据的逻辑结构和数据的存储结构是相同的。（ ）8数据的存储结构是数据的逻辑结构的存储映像。（  ）三、单项选择题(8小题,共16分)1下面关于线性表的叙述错误的是（  D ）。A 线性表采用顺序存储必须占用一片连续的存储空间 B 线性表采用链式存储不必占用一片连续的存储空间 C 线性表采用链式存储便于插入和删除操作

13、的实现 D 线性表采用顺序存储便于插入和删除操作的实现 2单链表的存储密度（  C  ）。   A 大于1            B 等于1        C小于1            D 不能确定 3  设输入序列为1、2、3、4、5、

14、6，则通过栈的作用后可以得到的输出序列为（ B ）。A  5，3，4，6，1，2                         B  3，2，5，6，4，1 C  3，1，2，5，4，6           

15、              D  1，5，4，6，2，34若串S="SOFTWARE"，其子串的数目最多是：（   C ） 。    A35         B36           C37

16、0;          D38 5二叉排序树中，最小值结点的（A ）。A 左指针一定为空          B 右指针一定为空C 左、右指针均为空        D 左、右指针均不为空6在散列函数H(k)= k mod m中，一般来讲，m应取（C ）。A 奇数      B 偶数 

17、0;   C 素数     D 充分大的数7用直接插入排序对下面四个序列进行由小到大排序，元素比较次数最少的是（  B ）。 A 94, 32, 40, 90, 80, 46, 21, 69         B 21, 32, 46, 40, 80, 69, 90, 94C 32, 40, 21, 46, 69, 94, 90, 80        

18、0;D 90, 69, 80, 46, 21, 32, 94, 401使用双链表存储线性表，其优点是可以（B ）。A 提高查找速度     B 更方便数据的插入和删除C 节约存储空间     D 很快回收存储空间2链表不具有的特点是（B ）A.不必事先估计存储空间              B.可随机访问任一元素 C.插入删除不需要移动元素    

19、        D.所需空间与线性表长度成正比  3下面关于线性表的叙述错误的是（ D  ）。A 线性表采用顺序存储必须占用一片连续的存储空间 B 线性表采用链式存储不必占用一片连续的存储空间 C 线性表采用链式存储便于插入和删除操作的实现 D 线性表采用顺序存储便于插入和删除操作的实现 4从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（  D ）个结点。 A n    &

20、#160;    B n/2          C (n-1)/2         D (n+1)/2 5在C或C+语言中，一个顺序栈一旦被声明，其占用空间的大小（  A  ）。   A已固定    B不固定       C可以改变 

21、60; D动态变化 6  两个字符串相等的充要条件是（C  ）。A  两个字符串的长度相等      B  两个字符串中对应位置上的字符相等C  同时具备(A)和(B)两个条件    D  以上答案都不对 8设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（ C ）。A  N0=N1+1     B  N0=Nl+

22、N2      C  N0=N2+1       D  N0=2N1+l9在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(  D  )Ae     B2e      Cn2e    Dn22e10设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则

23、二叉树B的根结点的左子树的结点数为（ A  ）。A  N1-1      B  N2-1     C  N2+N3     D  N1+N3 11设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（D  ）。A  空或只有一个结点         B  高度等于

24、其结点数C  任一结点无左孩子         D  任一结点无右孩子 12在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择（ 快速  ）排序，如果从节省存储空间的角度来考虑则最好选择（ 堆  ）排序。 13设有以下四种排序方法，则（ B  ）的空间复杂度最大。 A  冒泡排序  B  快速排序    

25、 C  堆排序     D  希尔排序14数据结构中，与所使用的计算机无关的是数据的（C ）A存储结构  B物理结构  C逻辑结构  D物理和存储结构15数据的基本单位是（  B  ）。A.  数据结构     B.  数据元素  C.  数据项      D.  文件1已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一

26、个结点的地址为B，则第i个结点的地址为（  A  ）。A B+(i-1)*m        BB+i*m           C B-i*m           D B+(i+1)*m 3若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（D ）存储方法最节省时间。 A 单链表 B 带头指针的

27、单循环链表 C 双链表 D 带尾指针的单循环链表4在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（ B  ）结构。A 栈            B队列        C 数组         D线性表 5用链接方式存储的队列，在进行插入运算时(  D

28、 ).   A. 仅修改头指针            B. 头、尾指针都要修改   C. 仅修改尾指针              D.头、尾指针可能都要修改 6以下论述正确的是（   C ）。   A空串与空格串是相同的    

29、  B"tel"是"Teleptone"的子串   C空串是零个字符的串         D. 空串的长度等于1 7对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（C ）。 A h          B h+1         C h

30、或h+1           D 任意 9设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（B  ）个空指针域。     A  2m-1                  B  2m   &

31、#160;             C  2m+1              D  4m 10设某有向图中有n个顶点，则该有向图对应的邻接表中有（ B ）个表头结点。     A  n-1      

32、               B  n                    C  n+1             &#

33、160;  D  2n-1 11二叉排序树中左子树上所有结点的值均（ A ）根结点的值。     A  <                        B  >        

34、            C  =                    D  != 12静态查找与动态查找的根本区别在于（B ）。A 它们的逻辑结构不一样 B 施加在其上的操作不同C 所包含的数据元素的类型不一样   D 存储实现不一样13散列技术中的冲突指的

35、是（ D）。A 两个元素具有相同的序号                 B 两个元素的键值不同，而其他属性相同C 数据元素过多                            

36、;D 不同键值的元素对应于相同的存储地址14一组记录的关键码为46, 79, 56, 38, 40, 84，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ A  ）。A 40, 38, 46, 56, 79, 84        B 40, 38, 46, 79, 56, 84C 40, 38, 46, 84, 56, 79        D 84, 79, 56, 46, 40, 3815对一个算法的评价，不包括如下（

37、 B ）方面的内容。    A健壮性和可读性   B并行性     C正确性     D时空复杂度1单链表的存储密度（  C  ）。   A 大于1            B 等于1        C小于1   

38、0;        D 不能确定 2设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。     A  O(log2n)              B  O(1)        &

39、#160;      C  O(n2)              D  O(n) 3在下列链表中不能从当前结点出发访问到其余各结点的是（ C   ）。A双向链表        B单循环链表    C单链表     

40、60;    D双向循环链表 4从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 (   D )命令。   Ax=top;top=top->next;      Btop=top->next;x=top->data;   Cx=top->data;            &#

41、160; Dx=top->data;top=top->next; 5设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（  D）。     A  top=top+1;            B  top=top-1;       C  top->next=top;   

42、0;     D  top=top->next; 6字符串的长度是指（  C ）。         A  串中不同字符的个数                  B  串中不同字母的个数      

43、;   C  串中所含字符的个数                  D  串中不同数字的个数 7数组的逻辑结构不同于下列（ D ）的逻辑结构。       A  线性表           B

44、60;栈                C 队列                 D  树 8设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ D ）。       A  空或只

45、有一个结点                       B  高度等于其结点数       C  任一结点无左孩子               

46、60;       D  任一结点无右孩子  10下图为由7个顶点组成的无向图。从顶点1出发，对它进行广度优先遍历得到的顶点序列是_C_。    A、1534267     B、1726453   C、1354276     D、1247653 11下列各种排序算法中平均时间复杂度为O(n2)是（  D ）。   &#

47、160; A  快速排序           B  堆排序            C  归并排序               D  冒泡排序 = 2对线性表，在下列哪种情况下应当采用链表表示

48、？(  B )      A.经常需要随机地存取元素         B.经常需要进行插入和删除操作      C.表中元素需要占据一片连续的存储空间    D.表中元素的个数不变 3若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( 

49、0; B )。  A5和1        B4和2         C2和4             D1和5  5  设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（ C ）个度数为0的结点。  

50、60;      A  5                     B  6                    C  7

51、60;                   D  8 6任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A）。A 肯定不发生改变         B 肯定发生改变        C 不能确定    &#

52、160;    D 有时发生变化7设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ A ）。      A  O(n+e)               B  O(n2)             

53、C  O(ne)              D  O(n3) 8下面关于工程计划的AOE网的叙述中，不正确的是（B ） A 关键活动不按期完成就会影响整个工程的完成时间B 任何一个关键活动提前完成，那么整个工程将会提前完成C 所有的关键活动都提前完成，那么整个工程将会提前完成D 某些关键活动若提前完成，那么整个工程将会提前完9下列命题正确的是（ B）。A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一B 一个图的邻接矩阵表示是

54、唯一的，邻接表表示不唯一C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一10  设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ B ）。         A  99                    

55、; B  97                 C  91                  D  93 11设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是

56、（  D ）。A   F，H，C，D，P，A，M，Q，R，S，Y，X B   P，A，C，S，Q，D，F，X，R，H，M，Y C   A，D，C，R，F，Q，M，S，Y，P，H，X D   H，C，Q，P，A，M，S，R，D，F，X，Y =1线性表的链式链式存储结构是一种（ B   ）的存储结构。             

57、60;                       A、随机存取             B、顺序存取        C、索引存取     

58、        D、HASH存取    3设计一个判别表达式中左右括号是否配对的算法，采用（B ）数据结构最佳A 顺序表      B 栈     C 队列     D 链表4设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C

59、）。A 6  B 4  C 3  D 25设数组datam作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（  D ）   Afront=front+1                 Bfront=(front+1)%(m-1)   Cfront=(front-1)%m 

60、60;           Dfront=(front+1)%m 7广义表(a, b, (c, (d)的表尾是（ D  ）。A (d)          B (c,(d)         C b        D (b,(c,(d

61、)  9线索二叉树中某结点R没有左孩子的充要条件是（ C）。A R.lchild=NULL      B R.ltag=0       C R.ltag=1       D R.rchild=NULL10  设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（ B ）。         A  8 

62、;                    B  7                    C  6        

63、60;           D  5  12G是一个非连通无向图，共有28条边，则该图至少有（ D）个顶点。A 6     B 7     C 8     D 9 14设有6个结点的无向图，该图至少应有(   A   )条边才能确保是一个连通图。A.5    

64、   B.6          C.7       D.815散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（  C）A、  2         B、  3  

65、60;      C、  4        D、   516  设有5000个元素，希望用最快的速度挑选出前10个最大的，采用（  B  ）方法最好。A快速排序       B堆排序        C希尔排序     

66、 D 归并排序四、算法设计题(2小题,共24分)1设计在顺序存储结构上实现求子串算法。void substring(char s , long start, long count, char t )  long i,j,length=strlen(s);  if (start<1 | start>length) printf("The copy position is wrong");else if (start+count-1>length) printf("Too characters to be copied&

67、quot;); else for(i=start-1,j=0; i<start+count-1;i+,j+) tj=si; tj= '0'2编写算法，要求输出二叉树后序遍历序列的逆序。void  Postordern(BiTree  *H)  if (H) visit(H->data);  Postordern(H->rchild);  Postordern(H->lchild);1设计判断一棵二叉树是否是二叉排序树的算法。int minnum=-32768, flag=1;typedef struct

68、nodeint key;   struct node *lchild,*rchild;bitree;void inorder(bitree *bt)  if (bt!=0)    inorder(bt->lchild); if(minnum>bt->key) flag=0; minnum=bt->key; inorder(bt->rchild); 2设计顺序查找算法，将哨兵设在下标高端。【解答】将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下：1设计

69、判断单链表中元素是否是递增的算法。int isriselk(lklist *head)if(head=0|head->next=0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0);return(1);3设计一个在链式存储结构上统计二叉树中结点个数的算法。void countnode(bitree *bt,int &count)   if(bt!=0) count+; countnode(bt->

70、;lchild,count); countnode(bt->rchild,count);1  对给定的带头结点的单链表L，编写一个删除L中值为X的结点的直接前趋结点的算法。解：void delete(ListNode *L)  ListNode *p=L,*q;    if (L->next->data=X)    printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”);      return;   

71、;     for (;p->next->data!=X; q=p; p=p->next);     / 删除指针p所指向的结点        q->next=p->next;    delete p;1  已知一个有向图的邻接表，编写算法建立其逆邻接表。【解答】在有向图中，若邻接表中顶点vi有邻接点vj，在逆邻接表中vj一定有邻接点vi，由此得到本题算法思路：首先将逆邻接表的表头结点f

72、irstedge域置空，然后逐行将表头结点的邻接点进行转化。五、填空题(6小题,共12分)1在单链表中要在已知结点*P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为（ O(n)  ）。2设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有（ m=2e  ）关系。3顺序查找技术适合于存储结构为（顺序存储和链接存储 ）的线性表4对n个元素进行起泡排序，在（ 正序 ）情况下比较的次数最少，其比较次数为（ n-1   ）。5快速排序算法的空间复杂度平均情况下为（ &

73、#160;O(nlog2n)  ），最坏的情况下为（ O(n)   ）。6树形结构结构中的元素之间存在（ 一对多  ）的关系1在双向链表中，每个结点都有两个指针域，它们一个指向其（ 前趋  ）结点，另一个指向其（ 后继  ）结点。 2由两个栈共享一个存储空间的好处是（ 节省存储空间，降低上溢发生的机率）3设循环队列存放在向量sq.data0:M中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为（ (sq.rear+1)%(M+1)

74、=sq.front； ）。4设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是（   p->lchild=0&&p->rchild=0   ）。5深度为k的完全二叉树中最少有（  2k-1 ）个结点。6设一棵二叉树的前序序列为ABC，则有（ 5  ）种不同的二叉树可以得到这种序列。 7对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为（ 2n ）个，其中（ n-1 ）个用于指向孩子，

75、（ n+1 ）个指针是空闲的。8度不为（ 零 ）的结点称为分支结点或非终端结点。树中各结点度的（ 最大值）称为树的度。9设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的（  出度 ），第i列上所有元素之和等于顶点i的（  入度）。10N个顶点的强连通图的边数至少有（ N ）11  数据的物理结构主要包括（ 顺序存储结构 ）和（  链式存储结构  ）两种情况。12假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次

76、数为（ n(n-1)/2 ）13算法的空间复杂度是指（执行过程中所需要的辅助存储空间）14顺序存储结构中数据元素之间的逻辑关系是由（  存储位置  ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（  指针     ）表示的。15若算法中的语句执行次数之和为 T ( n )= 525 n +4 n log n ，则算法的时间复杂度是（    O （ n log n ）   ）。1可由一个尾指针唯一确定的链表有（循环链表 ）、（双链表）。 2在

77、有n个元素的栈中，进栈操作的时间复杂度为（ O（1）  ），出栈操作的时间复杂度为（  O（1） ）。 3在串 S="structure" 中，以 t 为首字符的子串有（   12  ）个。4设有一个10阶的对称矩阵A采用压缩存储，A00为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A85的存储地址为（d+41. 元素A85的前面共存储了(1+2+8)+5=41个元素）。5广义表(a,(a,b),d,e,(i,j),k)的长度是（ 5   ），深度是（ 3   ）。  6一棵二叉树的第i（i1）层最多有（2i-1）个结点；一