大数据结构习题及问题详解

1、第 1 章 数据结构一、选择题1. 算法指的是() 。A 计算机程序B 解决问题的计算方法C 排序方法D 解决问题的有限运算序列2. 在数据的树形结构中，数据元素之间为()的关系。A 0:0 B 1:1 C 1:n D m:n3. 数据的存储结构包括顺序、 、散列和( ) 4 种基本类型。A 索引 B 数组 C 集合 D 向量4. 一个数组元素 ai 与( )的表示等价。A &a+i B *(a+i) C *a+i D a+i5. 若只需要利用形参间接访问实参指针所指向的对象，而形参本身具有相应的存储空间，则 应把形参变量说明为( )参数。A 指针 B 引用 C 值 D 指针引用6. 若只需要

2、利用形参实现对实参值的拷贝，函数体操作形参时与实参无关，则应把形参变量 说明为( )参数。A 指针 B 引用 C 值 D 指针引用7. 下面程序的时间复杂性的量级为() 。int i=0 ， s1=， s2=0； while ( i+n )if (i%2) s1+=i;else s2+=i;A. O(1) B.O(1bn) C.O( n) D.O(2n)8. 下面程序段的时间复杂度为()。for(int i=0;im;i+)for(int j=0;jn;j+)aij=i*j;A. O(m2) B.O(n2) C.O(m+n) D.O(m*n)9. 执行下面程序段时， S 语句的执行次数为()

3、。for(int i=1;i=n;i+)for(int j=1,jnext=ph; B. p-next=ph; ph=p;C. p-next=ph; p=ph; D. p-next=ph-next; ph-next=p;21. 在一个表头指针为 ph 的单链表中， 若要在指针 q 所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. q-next=p-next; p-next=q; D. p-next=q-next; q-next=p;22. 在一个单链表 HL 中，若要删除由指针

4、q 所指向结点的后继结点（若存在的话） ，则执行 （）操作。A. p=q-next; p-next=q-next; B. p=q-next; q-next=p;C. p=q-next; q-next=p-next; D. q-next=q-next-next; q-next=q;23. 在一个带头结点的循环双向链表中，若要在指针p 所指向的结点之后插入一个 q 指针所指向的结点，则需要对 q-next 赋值为（）。A. P-priorB. p-nextC. p-next-nextD.p-prior-prior24. 在一个带头结点的循环双向链表中，若要在指针p 所指向的结点之前插入一个 q 指

5、针所指向的结点，则需要对 p-prior-next 赋值为（） 。A. q B. p C. p-next D. p-prior25. 在一个带头结点的循环双向链表中，若要删除指针 p 所指向的结点则执行（）操作。A. p-prior-next=p-next; p-next-prior=p-prior;B. p-next-prior=p; p-next=p-next-next;C. p-prior-next=p; p-next=p-next-prior;D. p=p-next; p-prior-next=p-prior;26. 栈的插入和删除操作在（）进行。A. 栈顶 B. 栈底 C. 任意位置

6、 D. 指定位置27. 当利用大小为 N 的数组顺序存储一个栈时，假定用 top=N 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top 指针。A.top+ B.top- C.top=0 D.top=N-128. 假定利用数组 aN顺序存储一个栈，用 top 表示栈顶指针，用 top=N+1 表示栈空，该数 组所存储的栈的最大长度为 N，则表示栈满的条件为（） 。A.top=1 B.top=-1 C.top=0 D.top=N-129. 假定利用数组 aN顺序存储一个栈，用 top 表示栈顶指针，用 top=-1 表示栈空，并已 知栈未满， 当元素 x 进栈时所执行的操作为（）

7、。A.a-top=xB.atop-=x C.a+top=x D.atop+=x30. 假定利用数组 aN顺序存储一个栈，用 top 表示栈顶指针，用 top=-1 表示栈空，并已 知栈未空，当退栈并返回栈顶元素时所执行的操作为（） 。A return a-top B return atop- C return a+top D return atop+31. 假定一个链式栈的栈顶指针用top 表示，该链式栈为空的条件（） 。A.top ！ =NULL; B. top=top-next; C. top= NULL;D. top！ = top-next;32. 假定一个链式栈的栈顶指针用top 表示

8、，每个结点结构为 ,当 p 所指向的结点进栈时，执行的操作为（） 。A. p-next=top; top=top-next;B. top=p; p-next=top;C. p-next=top-next; top-next=p; D. p-next=top; top=p;33. 假定一个链式栈的栈顶指针用top 表示，每个结点结构为 ,退栈时所执行的操作为（） 。A.top-next=top ； B.top=top-data;C.top=top-next; D. top-next=top-next-next;34. 若让元素 1，2，3，4 依次进栈，则出栈次序不可能出现（）的情况。A.3 ，

9、 2，1， 4 B.2 ，1， 4， 3 C.4，3，2， 1 D.1 ，4， 2， 3.35. 在一个顺序循环队列中，队首指针指向队首元素的（）位置。A 前一个 B 后一个 C 当前 D 最后36. 当利用大小为 N 的数组循环存储一个队列时，该队列的最大长度为（） 。 A.N-2 B.N-1 C.N D.N+137. 从一个顺序循环队列中删除元素时，首先需要（）。A. 前移队首指针B.后移队首指针C.取出队首指针所指位置上的元素D. 取出队尾指针所指位置上的元素38. 假定一个顺序循环队列的队首和队尾指针分别用f 和 r 表示，则判断队空的条件为（） 。A.f+1=r B.r+1=f C.

10、f=0 D.f=r39. 假定一个顺序循环队列存储于数组aN ，其队首和队尾指针分别用 f 和 r表示，则判断队满的条件为（） 。A.（ r-1） %N=f B.（r+1）%N=f C.（f-1）%N=r D. （ f+1） %N=r40. 假定利用数组 aN循环顺序存储一个队列， 其队首和队尾指针分别用 f 和 r表示，并已知 队列未满， 当元素 x 入列时所执行的操作为（） 。A.a+r%N=x B.ar+%N=x C.a-r%N=xD.ar-%N=x41. 假定利用数组 aN循环顺序存储一个队列， 其队首和队尾指针分别用 f 和 r表示，并已知 队列未空，当出列并返回队首元素时所执行的操

11、作为（） 。A.return a+r%NB.return a-r%N C.return a+f%N D.return af+%N42. 假定一个链式队列的队首和队尾指针分别为front 和 rear，则判断队空的条件为（）A.front=rear B.front ！ =NULLC.rear！ =NULL D.front=NULL43. 假定一个链式队列的队首和队尾指针分别为front 和 rear，每个结点结构为 , 当出列时所进行的操作为（） 。A.front=front-next B.rear=rear-nextC.front-next =rear ； rear=rear-nextD.fr

12、ont=front-next ； front-next =rear ；44. 假定一个带头结点的循环链式队列的队首和队尾指针分别用front 和 rear 表示，则判断对空的条件为（） 。A.front=rear-next B.rear=NULL C. front=NULL D. front =rear45. 假定一个链式队列的队首和队尾指针分别为front 和 rear，每个结点结构为包含值域 data和指针域 next,则使 p 所指结点入列所执行的操作为（） 。A.p-next=NULL ； rear=rear-next=p ；B. p-next=rear-next ； rear=rea

13、r-next=p ；C. p-next=front ； front=p ；D. p-next=front-next ； front-next=p ；46. 在一个长度为 N 的数组空间中，循环顺序存储着一个队列，该队列的队首和队尾指针分 别用 front 和 rear 表示，则该队列中数组元素个数为（） 。A. （ rear-front ） %NB. （ rear-front+N ）%NC.（ rear+N ）%ND.（ front+N ）%N47. 二维数组 A12,10 采用行优先存储，每个数据元素占用4 个存储单元，该数组的首地址（即 A0 ， 0的地址）为 1200，则 A6 ，5的地

14、址为（）。A.1400 B.1404 C.1372 D.146048. 有一个 MN 的矩阵 A，若采用行优先进行顺序存储，每个元素占用8 个字节，则 Aij（1iM,1jN） 元素的相对字节地址（相对首元素地址而言）为（）。A.（i-1） N+j） 8 B. （i-1 ） N+j-1 ）8C.（ iN+j-1 ） 8D. （i-1 ） N+j+1 ）849. 有一个 N N 的下三角矩阵 A，若采用行优先进行顺序存储，每个元素占用 k 个字节， 则 Aij（1 iN,1 ji）元素的相对字节地址（相对首元素地址而言）为（）。A. （ i（ i+1 ） /2+j-1 ） 4 B.（ii/2+j

15、） 4C.（ i（ i-1） /2+j-1 ） 4 D. （ i（ i-1）/2+j ） 450. 树中所有结点的度等于所有结点数加（） 。A.0 B.1 C.-1 D.251. 在一棵树中， （）没有前驱结点。A. 树枝结点 B.叶子结点 C.树根结点 D.空结点52. 在一棵树中，每个结点最多有（）个前驱结点。A.0 B.1 C.2 D.任意多个53. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A.2 B.1 C.0 D.-154. 在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（）。A.n B.n-1 C.n+1 D.2n55. 在一棵具有 n 个结点的二叉

16、树的第 i 层上，最多具有（）个结点。A.2i B.2i+1 C.2i-1 D.2n56. 在一棵深度为 h 的完全二叉树中，所含结点个数不小于（） 。A.2h B.2h+1 C.2h-1 D.2h-157. 在一棵深度为 h 的完全二叉树中，所含结点个数不大于（） 。A.2h B.2h+1 C.2h-1 D.2h-158. 在一棵具有 35 个结点的完全二叉树中，该树的深度为（）59.在一棵完全二叉树中，若编号为A.2i B.2i-1 C.2i+1 D.2i+260.在一棵完全二叉树中，若编号为A.2i B.2i-1 C.2i+1 D.2i+261.在一棵完全二叉树中，对于编号为A.（ i+

17、1）/2 B.（ i-1 ） /2 C.i%2A.6 B.7 C.5 D.8 i 的结点存在左孩子，则左孩子结点编号为（）i 的结点存在右孩子，则右孩子结点编号为（）i （ i1 ）的结点其双亲结点的编号为（）D.i/262. 有如图 1.1 所示的一棵二叉树，则该二叉树所含单支结点数为（）A.2 B.3 C.4 D.5A. ABCDEFG B. CDBGFEAC. CBDAEGF D. ABECDFG63. 有如图 1.2 所示的一棵二叉树，则该二叉树的中序遍历序列为（）64. 有如图 1.2 所示的一棵二叉树，则该二叉树的先序遍历序列为（）A.ABCDEFG B.CDBGFEAC.CBDA

18、EGF D.ABECDFG65. 有如图 1.2 所示的一棵二叉树，则该二叉树的后序便利序列为（）A.ABCDEFG B.CDBGFEAC.CBDAEGF D.ABECDFG66. 利用 n 个值生成的哈夫曼树中共有（）个结点。A.n B.n+1 C.2n D.2n-167. 利用 3，6，8， 12这 4个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路径长 度为（）。A.55 B.29 C.58 D.3868. 在一个具有 n 个顶点的有向图中， 若所有顶点的出度数之和为 s，则所有的入度数之和为 （）。A.s B.s-1 C.s+1 D.n69. 在一个具有 n 个顶点的有向图中， 若

19、所有顶点的出度数之和为 s，则所有的度数之和为 （）。 A. s B. s -1 C. s +1 D.2s70. 在一个具有 n 个顶点的无向图中，若具有 e 条边，则所有顶点的度数为（） 。A.n B.e C.n+e D.2e71. 在一个具有 n 个顶点的无向完全图中，所含的边数为（） A.nB.n （n-1） C.n（ n-1）/2 D.n（n+1）/272. 在一个具有 n 个顶点的有向完全图中，所含的边数为（）A.nB.n （n-1） C.n（n-1）/2D.n （n+1）/273. 在一个具有 n 个顶点的无向连通图中，它包含的连通分量的个数为（）A.0 B.1 C.n D.n+1

20、74. 若有一个图中包含 k 个连通分量，若按照深度优先搜索的方法访问所有顶点，则必须调 用（）次深度优先搜索遍历的算法。A.k B.1 C.k-1 D.k+175. 若要把 n 个顶点连接为一个连通图，则至少需要（）条边。A.n B.n+1 C.n-1 D.2n76. 在一个具有 n 个顶点和 e 条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效 元素）的个数为（） 。A.n B.ne C.e D.2e77. 在一个具有 n 个顶点和 e 条边的有向图的邻接矩阵中，表示边存在的元素的个数为（） A.n B.ne C.e D.2e78. 在一个具有 n 个顶点和 e 条边的无向图的邻接矩

21、阵中，边结点的个数为（）。A.n B.ne C.e D.2e79. 对于一个有向图，若一个顶点的度为k1，出度为 k2，则对应邻接表中该顶点单链表的边数结点为（） 。A.k1 B.k2 C.k1-k2 D.k1+k280. 对于一个有向图，若一个顶点的度为k1，出度为 k2，则对应逆邻接表中该顶点单链表的边数结点为（） 。A.k1 B.k2 C.k1-k2 D.k1+k281. 对于一个无向图，下面（）的说法是正确的。A. 每个顶点的入度等于出度B.每个顶点的度等于入度和出度之和C.每个顶点的入度为 0D.每个顶点的出度为 082. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点

22、的（）。A.出边数 B.入边数 C.度数 D. 度数减一83. 若一个图的边集为 （A，B）（A，C）（B，D）（C，F）（D，E）（D，F） ，则从顶点 A 开始对该图进行深度优先搜索，得到的顶点序列可能为（） 。A. ABCFDEB. ACFDEB C. ABDCFE D. ABDFEC84. 若一个图的边集为 （A，B）（A，C）（B，D）（C，F）（D，E）（D，F） ，则从顶点 A 开始对该图进行广度优先搜索，得到的顶点序列可能为（） 。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE85. 若一个图的边集 （1，2）（1，4）（2，5）（3，1）（3，5）（4

23、，3），则从顶点 1 开始对 该图进行深度优先搜索，得到的顶点序列可能为（） 。A.1 ， 2，5， 4，3 B.1，2，3，4，5 C.1，2，5，3，4 D.1，4，3，2，586. 若一个图的边集 （1，2）（1，4）（2，5）（3，1）（3，5）（4，3），则从顶点 1 开始对 该图进行广度优先搜索，得到的顶点序列可能为（） 。A. 1，2，3，4，5 B. 1，2，4，3，5 C. 1，2，4，5，3 D. 1，4，2，5，387. 由一个具有 n 个顶点的连通图生成的最小树中有（）条边。A.n B.n-1 C.n+1 D.2n88. 若查找每一个元素的概率相等，则在长度为n 的顺序

24、表上查找任一元素的平均查找长度为（）。A. n B. n+1 C. （n-1）/2 D. （n+1）/289. 对长度为 n 的单链有序表，若查找每个元素的概率相等，则查找任一个元素的平均查找 长度为（）。A. n/2 B.（n+1）/2 C. （n-1）/2 D.n/490. 对于长度为 9 的顺序存储的有序表，若采用二分查找，在等概率情况下的平均查找长度 为（）的值除以 9。A.20 B.18 C.25 D.2291. 对于长度为 18 的顺序存储的有序表，若采用二分查找，则查找第 15 个元素的查找长度 为（）。A.2 B.3 C.4 D.692. 对于顺序存储的有序表（ 5，12， 2

25、0，26，37，42，46，50，64），若采用二分查找，则 查找元素 26 的查找长度为（） 。A.2 B.3 C.4 D.593. 在分块查找中， 若用于保存数据元素的主表长度为n，它被分为 k 个子表， 每个子表的长度均为 n/k，若用顺序查找确定块，则分块查找的平均查找长度为（）。A.n+k B.k+n/k C.（k+n/k ）/2 D.（k+n/k ）/2+194. 在分块查找中，若用于保存数据元素的主表长度为 144，它被分为 12 个子表，每个子表 的长度均为 12，若用顺序查找确定块，则分块查找的平均查找长度为（） 。A.13 B.24 C.12 D.7995. 在一棵深度为

26、h的具有 n 个元素的二叉排序树中，查找所有元素的最长查找长度为（）。A.n B.lbn C.（h+1） /2 D.h96. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值围是（）。A.-11 B.-22 C.12 D.0197. 若根据查找表 （ 23，44，36，48，52，73，64，58）建立线性哈希表， 采用 H（K ）=K%13 计算哈希地址，则元素 64 的哈希地址为（） 。A.4 B.8 C.12 D.1398. 若根据查找表 （ 23，44，36，48，52，73，64，58）建立线形哈希表， 采用 H（K ）=K%13 计算哈希地址，则哈希地址为 3 的元素个数为（） 。

27、A.1 B.2 C.3 D.499. 若根据查找表建立长度为 m 的线性哈希表，采用线性探测再哈希法处理冲突，假定对一 个元素第一次计算的哈希地址为 d，则下一次的哈希地址为（） 。A.d B.d+1 C.（ d+1） /m D. （d+1） %m100. 在采用线性探测再哈希法处理冲突的线性哈希表上，假定装填因子a 的值为 0.5，则查找任一个元素的平均查找长度为（） 。A.1 B.1.5 C.2 D.2.5101. 在哈希查找中，平均查找长度主要与（）有关。A. 哈希表长度 B.哈希元素个数 C.装填因子D. 处理冲突方法102. 若对 n 个元素进行直接插入排序， 则进行第 i 趟排序过

28、程前， 有序表中元素的个数为 （）。 A.i B.i+1 C.i-1 D.1103. 若对 n个元素进行直接插入排序，在进行第i 趟排序时，为寻找插入位子最多需要进行（）次元素的比较，假定第 0 号元素放有待查的键值。A. i B.i-1 C.i+1 D.1104. 若对 n个元素进行直接插入排序， 在进行第 i趟排序时 ,假定元素 ri+1 的插入位置为 rj， 则需要移动元素的次数为（） 。A.j-i B.i-j-1 C.i-j D.i-j+1105. 若对 n 个元素进行直接插入排序，在进行任意一趟排序的过程中，为寻找插入位置而需 要的时间复杂度为（） 。A.O（1） B.O （ n）

29、C.O（n2） D. O（lbn）106. 在对 n 个元素进行直接插入排序的过程中，共需要进行（）趟。A.n B.n+1 C.n-1 D.2n107. 对 n 个元素进行直接插入排序的时间复杂度为（） 。A.O（1） B.O （ n） C.O（n2） D. O（lbn）108. 在对 n 个元素进行冒泡排序的过程中， 第一趟排序至多进行 （）对相邻元素之间的交换。 A .n B.n-1 C.n+1 D.n/2109. 在对 n 个元素进行冒泡排序的过程中，最坏情况下的时间复杂度为（）。A.O（1） B.O（lbn） C.O（n2） D.O（ n）110. 在对 n 个元素进行冒泡排序的过程中

30、，至多需要（）趟完成。A .1 B.n C.n-1 D.n/2111. 在对 n 个元素进行快速排序的过程中，最好情况下需要进行（）趟。A.n B.n/2 C.lbn D.2n112. 在对 n 个元素进行快速排序的过程中，最坏情况下需要进行（）趟。A.n B.n-1 C.n/2 D.lbn113. 对下列 4 个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分 过程中需要移动元素次数最多的序列为（） 。A.1 ， 3，5， 7，9 B.9，7，5，3，1 C.5，3，1，7，9 D.5 ，7， 9， 1，3114. 假定对元素序列（ 7， 3，5，9，1， 12，8，15）

31、进行快速排序，则进行第一次划分后， 得到的左区间中元素的个数为（） 。A.2 B.3 C.4 D.5115. 在对 n 个元素进行简单选择排序的过程中，在第i 趟需要从（）个元素中选择出最小值A.n-i+1 B.n-i C.i D.i+1116. 若对 n 个元素进行简单选择排序，则进行任一趟排序的过程中，为寻找最小值元素所需 要的时间复杂度为（） 。A.O（1） B.O （ lbn） C.O（n2） D. O（n）117. 假定一个初始堆为（ 1，5，3，9，12， 7，15，10），则进行第一趟堆排序后得到的结果 为（）。A.3 ， 5，7， 9，12，10，15，1 B.3，5，9，7，

32、12，10，15，1C.3，7，5， 9，12， 10，15，1 D.3，5，7，12，9，10，15，1118. 若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序 B. 简单选择排序 C.堆排序 D.快速排序119. 若要从 1000 个元素中得到 10 个最小元素，最好采用（）方法。A. 直接插入排序 B. 简单选择排序 C.堆排序 D. 快速排序120. 在平均情况下速度最快的排序方法为（） 。A.简单选择排序 B. 冒泡排序 C.堆排序D.快速排序二填空题1. 数据的逻辑结构可分为 和 两大类。2. 数据的存储结构被分为 ， ，和4 种。3. 在下面的程序段中， s=s+p

33、 语句被执行次数为 ，p*=j 语句的执行次数为 ,该程序的复杂度为 。int i=0， s=0； while （ +i=n ） int p=1;for（int j=1;j=i;j+）p*=j;s=s+p;4. 一种数据结构的元素集合 K 和它的二元关系 R 为： K=a,b,c,d,e,f,g,h R=a,b ，b,c，c,d，d,e，e,f，f,g ，g,h 则该数据结构具有 结构。5. 线性表的两种存储结构分别为 和 。6. 线性表的顺序存储结构称为 ，链式存储结构称为 。7. 若经常需要对线性表进行插入和删除运算，则最好采用_存储结构，若经常需要对线性表进行查找运算，则最好采用 存储结

34、构。8. 对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为 。9. 对于一个单链表存储的线性表，在表头插入结点的时间复杂度为 ，在表尾插入结点的时间复杂度为 。10. 在线性表的单链表存储中，若一个元素所在结点的地址为p，则其后的断结点的地址为。11. 在以 HL 为头指针的带头结点的单链表和循环单链表中，链表为空的条件分别为 和。12. 在链表中，既可以通过设定一个头指针，也可以通过设定一个尾指针来确定它，即通过头指针或尾指针可以访问到该链表的每个结点。13. 在一个单链表中删除指针 p所指向结点的后继结点时， 需要把的值赋给 p-next 指针域。14. 在一个单链表中

35、指针 p 所指向结点的后面插入一个指针 q 所指向的节点时，首先把 的值赋给 p-next ，然后把 的值赋给 p-next 。15. 假定指向单链表中第一个结点的头指针为head，则像该单链表的表头插入指针p 所指向的新结点时，首先执行 赋值操作，然后执行 赋值操作。16. 访问一个顺序表和一个单链表中第i 个元素的时间复杂度分别为 和 。17. 在一个带头结点的循环单链表中，在表头插入或删除与在其它位置插入和删除，其操作 过程是否相同？ 。18. 在双向链表中每个结点包含有两个指针域，一个指向其 结点，另一个指向其 结点。19. 在一个双向链表中指针p 所指向的结点之后插入一个指针 q 所

36、指向的结点时，需要对p-next-prior 指针域赋值为 。20. 在一个双向链表中删除指针 p所指向的结点时， 需要对 p-next-prior 指针域赋值为 。21. 栈又称为 表，队列又称为 表。22. 在一个用一维数组 aN表示的顺序栈中， 该栈所含元素的个数最少为 个，最多为 个。23. 像一个顺序栈插入一个元素时，首先使 后移一个位置，然后把新元素 到这个位子。24. 从一个栈删除元素时，首先取出 ，然后再使 减一。25. 一个顺序栈存储一个一维数组 aM 中，栈顶指针用 top 表示，当栈顶指针等于 时为空栈，栈顶指针为 时为满栈。26. 假定一个链栈的栈顶指针为 top，每个

37、结点包含值域 data 和指针域 next，当 p 所指向的结 点入栈时，则首先执行 操作，然后执行 操作。27. 假定一个链栈的栈顶指针为 top，每个结点包含值域 data 和指针域 next ，当进行出栈运 算时(假定栈非空) ，需要把栈顶指针修改为 的值。28. 设元素 1，2，3，4，5 依次进栈，若要在输出端得到序列34251 ，则应进行的操作序列为Push(s,1),Push(s,2),Pop(s),Push(s,4),Pop(s),Pop(s),Pop(s)。29. 设元素 a， b，c，d 依次进栈，若要在输出端得到序列cbda，则应进行的操作序列为push(s,a),pus

38、h(s,b),push(s,c),，pop(s),pop(s)。30. 队列的插入操作在 进行，删除操作在 进行。31. 一个顺序循环队列存在于 aM 中 ,假定队首和队尾指针分别为 front 和 rear，则判断对空的 条件为 ，判断对满的条件为 。32. 一个顺序循环队列存在于 aM 中 ,假定队首和队尾指针分别为 front 和 rear，则求出队首和队尾指针的下一个位置的计算公式分别为 和 33.在一个用一维数组aN 存储的顺序循环队列中，该队列中的元素个数最少为 _个，最多为 个。34.向一个顺序循环队列中插入元素时，需要首先移动 素。，然后再向它所指位置新元35.在一个空链队列中

39、，假定队首和队尾指针分别为f 和 r ，当向他插入一个新结点*p 时，则首先执行 操作，然后执行 操作。36. 在一个带头结点的循环链队列中，假定队首和队尾指针分别为f 和 r，当向它插入一个新结点 *p 时，则首先执行 操作，然后执行 操作。37. 假定 front 和 rear 分别为一个链队列的对首和队尾指针，则该链队列中只有一个结点的条件为 。38. 在一个链栈中，若栈顶指针等于NULL 则为 ；在一个链队列中，若对首和队尾的指针相同，则表示该队列为 或该队列 。39. 一个二维数组 A15 ，10采用行优先方式存储，每个数据元素占用4 个存储单元， 以该数组第 3 列第 0 行的地址

40、（即 A3 ， 0的地址） 1000 为首地址，则 A12 ， 9的地址为 。40. 在二维数组 a10,20 中，每个元素占 8 个存储单元，假定该数组的首地址为2000，则数组元素 a6,15 的字节地址为 。41. 有一个 88的下三角矩阵 A ，若将其进行顺序存储于一维数组aN中，则 N的值为 。42. 有一个 1010 的下三角矩阵 A ，若将其进行顺序存储于一维数组aN中，则 Aij （1i10,1ji）存储于 a 中的下标位置为 。43. 有一个 88 的下三角矩阵 A ，若将其进行顺序存储，每个元素占用4 个字节，则 A5，4元素的相对字节地址为（相对首元素地址而言） 。44.

41、 一种数据结构的元素集合 K 和它的二元关系 R 为：K=a,b,c,d,e,f,g,hR= ， ， ， ， ， 则该数据结构具有 结构。45. 对于一棵具有 n 个结点的树，则该树中所有结点的度数之和为 。46. 在一棵树中， 结点没有前驱结点，其余每个结点有并且只有一个 ，可以有人以多个 结点。47. 如图 1.3 所示为一棵树， 该树的叶子结点数为 个，单支结点数为 个，双分支结点数为 个，三分支结点数为 个。48. 如图 1.3 所示的一棵树，结点 K 的所有祖先的结点数为 个，结点 B 的所有子结点数为个。49. 如图 1.3所示的一棵树，结点 D 和X 的层数分别为 和。50. 如

42、图 1.4 所示的一棵树， 则树中所含的结点数为 个，树的深度为 ，树的度为 。51. 如图 1.4所示的一棵树，则度为 3，2，1，0 的结点数分别为 ， ， 。52. 如图 1.4所示一棵树，则结点 H 的双亲为 ，孩子结点为 。53. 在一棵二叉树中， 假定双分支结点数为 5 个，单分支结点数为 6 个，则叶子结点数为 。54. 对于一棵二叉树，若一个结点的编号i ，若它的左孩子结点存在，则其编号为 ，若右孩子结点存在，则其编号为 ，若双亲结点存在，则其编号为 。55. 在一棵二叉树中，第 5 层上的结点数最多为 。56. 假定一棵二叉树的结点数为 18，则它的最小深度为 ，最大深度为

43、。57. 如图 1.5 所示为一棵二叉树，则 E 结点的双亲结点数为 ，左孩子结点为 ，右孩子结点为 。58. 如图 1.5 所示为一棵二叉树， 它含有双支结点 个，单分支结点 个，叶子结点 个。59. 假定一棵二叉树顺序存储在一维数组a 中，若 a5 元素的左孩子存在则对应的元素为，若右孩子存在则对应的元素为 ，双亲元素为 。60. 若对一棵二叉树从 0 开始进行结点编号，并按此编号把它存储到一维数组a 中，即编号为 0 的结点存储到 a0中，依次类推，则 ai 元素的左孩子为 ，右孩子为 ，双亲元素（ i0 ）为 。61. 对于一棵具有 n 个结点的二叉树，对应 二叉链表中指针总数为 个，

44、其中 个用于指向孩子结点， 个指针空闲。62. 在一棵深度为 h 的完全平衡二叉树中，最少含有 个结点，最多含有 个结点。63. 一棵深度为 5 的完全二叉树中的结点数最少为 个，最多为 个。64. 如图 1.6 所示为一棵二叉树，对它进行先序遍历结果为 。65. 若将如图 1.7 所示为一棵树转换为二叉树， 该二叉树中双支结点的个数为 个，单支结点的个数为 个，叶子结点个数为 。66. 一棵树转换为二叉树后如图 1.8 所示，则原树中分支结点数为 ，叶子结点数为 。67. 一个树林转换成二叉树后如图 1.9 所示，则该素林中包含 棵树。68. 若由 3，6，8， 12，10 作为叶子结点的值

45、生成一棵哈夫曼树，则该树的深度为 ，带权路径长度为 。69. 一种数据结构的元素集合 K 和它的二元关系 R 为： K=1 ，2，3，4，5，6R= （1，2）（2， 3）（2， 4）（3，4）（3，5）（3，6）（ 4，5）（4，6） 则该数据结构具有 数据结构。70. 在一个图中，所有顶点的度数之和等于所有边数的 倍。71. 在一个具有 n 个顶点的无向完全图中，包含有 条边，在一个具有 n 个顶点的有向完全图中，包含有 条边。72. 已知一个连通图的边集为 （1，2），（1，3），（1，4），（ 2，3），（2，5），（3，5），（4，5）， 则度为 3 的顶点的个数有个。73. 假定一

46、个有向图的顶点的集为 a,b,c,d,e,f, 边集a,c ，a,e，c,f ，d,c ，e,b，e,d, 则出度为 0 的顶点个数为，入度为 1 的顶点个数为。74. 在一个具有 n 个顶点的无向图中，要连通所有顶点则至少需要条边。75. 表示图的两种存储结构为和。76. 在一个连通图中存在着个连通分量。77. 若一个图的顶点集为 a,b,c,d,e,f, 边集为 （ a,b），（ a,c），（ b,c），（ d,e） ，则该图含有 个连通分量。78. 若一个图的边集为 0,1，0,2，0,3，0,4，1,2，2,4，3,4 ，则从顶点 V0 到顶点 V4 共有条简单路径。79. 如图 1.

47、10 所示为一个带权有向图，从顶点 V0 到顶点 V4 的最短路径长度为。80. 对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为。81. 对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点 的个数分别为和。82. 在有向图的邻接表和逆邻接表表示中， 每个顶点邻接表分别着该顶点的所有和。83. 有一个图的边集为 （ a,c），（ a,e），（ b,e），（ c,d），（ d,e） ，从顶点 a出发进行深度优先搜 索遍历得到的顶点序列为， 从顶点 a 出发进行广度优先搜索遍历得到的顶点序列为。84. 一个图的边集为 （a,c），（a,e），（c

48、,f），（d,c），（e,b），（e,d）,从顶点 a 出发出发进行深 度优先搜索遍历得到的顶点序列为， 从顶点 a 出发进行广度优先搜索遍历得到的顶点序列为。85. 图的优先搜索遍历算法是一种递归算法，图的优先搜索遍历算法需要使用队列。86. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是（唯一/不唯一）。87. 以顺序查找方法从长度为 n 的顺序表或单链表中查找一个元素时， 平均查找长度为。88. 对长度为 n的查找表进行查找时，假定查找第i 个元素的概率为 P，查找长度（即在查找过程中依次同有关元素比较的总次数） 为 C，则在查找成功的情况下的平均查找长度的计算 公式为。89.

49、 假定一个顺序表的长度为 40，并假定查找每个元素的概率都相同，则在查找成功的情况 下的平均查找长度，则在查找不成功的情况下的平均查找长度。90. 以折半查找方法从长度为 n 的有序表中查找一个元素时， 平均查找长度约等于减一。91. 以折半查找方法从长度为 50 的有序表中查找一个元素时，其查找长度不超过。92. 从有序表（ 12，18，30，43， 56，78，82， 95）中分别折半查找 43 和 56 元素时，其查 找长度分别为和。93. 假定对长度 n=50 的有序表进行折半查找， 则对应的判定树深度为， 最后一层的结点 数为。94. 在分块查找中，假定查找表（即主表）的长度为96，

50、被等分为 8 个子表，则进行分块查找的平均查找长度为。95. 假定对长度为 n 的有序表进行分块查找，并假定每个子表的长度为，则进行分块查找的 平均查找长度为。96. 在一棵二叉树排序中，每个分支结点的左子树上所有结点的值一定该结点的值，右 子树上所有结点的值一定该结点的值。97. 从一棵二叉排序树中查找某个元素时，若元素的值等于根结点的值，则表明，若元 素的值小于根结点的值， 则继续向查找， 若元素的值大于根结点的值， 则继续向查 找。98. 向一棵二叉排序树种插入一个元素时，若元素的值小于根结点的值，则接着向根结点的 插入，若元素的值大于根结点的值，则接着向根结点的插入。99. 在一棵平衡

51、二叉排序树中，每个结点的左子树深度与右子树深度之差的绝对值不超过。100. 假定对线性表（ 38，25，74，52，48），进行散列存储，采用 H（K） =K%7 作为哈希函 数，采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到次冲突。101. 假定对线性表（ 38， 25，74，52，48）进行散列存储，采用 H（ K） =K%7 作为哈希函 数，采用线性探测再散列法处理冲突，则平均查找长度为。102. 在线性表的散列存储中，装填因子a又称装填系数，若用 m 表示散列表的长度， n 表示散列存储的元素个数，则 a 等于。103. 对线性表（ 18，25， 63，50，42，32，

52、90）进行散列存储时，若选用 H（K）=K%9 作 为哈希函数，则散列地址为 0 的元素有个，则散列地址为 5 的元素有个。104. 每次从无序子表中取出一个元素，把它插入到有序子表的适当位置，此种排序方法叫做 排序； 每次从无序子表中挑选出一个最小或最大元素， 把它交换到有序表的一段， 此种 排序方法叫做排序。105. 若对一组记录（ 46， 79，56，38，40，80，35，50，74）进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较次。106. 排序方法能够每次使无序表中的第一个记录插入到有序表中。107. 对 n 个记录进行冒泡排序时，最少的比较次数为，最