数据结构习题

1、一、 单项选择题1. 下面程序段的时间复杂度为( C ) 。  for(int i=0; i<m; i+)   for(int j=0; j<n; j+)             aij=i*j;   A O(m2)        B O(n2)&

2、#160;        C O(m*n)         D O(m+n)2. 设有一个递归算法如下 int fact(int n)/n大于等于0 if(n<=0) return 1； else return n*fact(-n)； 则计算fact(n)需要调用该函数的次数为( D )次，不计fact(n)。 An Bn+1 Cn+2 Dn-l3. 评价排序算法好坏的标准主要是(D)。  A执行时间 

3、0; B辅助空间  C算法本身的复杂度   D执行时间和所需的辅助空间4. 在需要经常查找结点的前驱与后继的场合中，使用(   B   )比较合适。 A单链表           B双链表           C顺序表         &#

4、160; D循环链表5. 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行（ C ）。    Ap = q->next   p->next = q->next;    Bp = q->next   q->next = p;    Cp = q->next &

5、#160; q->next = p->next;    Dq->next = q->next->next;  q->next = q;6. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为( B ) 。 AO(1) BO(m) CO(n) DO(m+n)7. 链表不具有的特点是（ A ）。 A可随机访问任一元素 B插入删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比8. 若要在

6、单链表中的结点*p之后插入一个结点*s，则应执行的语句是( A )。As->next=p->next; p->next=s; Bp->next=s; s->next=p->next;Cp->next=s->next; s->next=p; Ds->next=p; p->next=s->next;9. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为 ( D )。 Afront=NULL Bfront!=NULLCrear!=NULL Dfront= =rear10. 栈和队列都是（C）。A链式

7、存储的线性结构 B顺序存储的线性结构C限制存取位置的线性结构 D限制存取位置的非线性结构11. 对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为（ A ）。Aabcfed Bcabfed Cabcfde Dcbafde12. 队列通常采用两种存储结构是(    A  )。 A顺序存储结构和链表存储结构    B散列方式和索引方式 C链表存储结构和数组          

8、60; D线性存储结构和非线性存储结构13. 若让元素1，2，3依次进栈，则出栈次序不可能出现（ C ）种情况。A3，2，1 B2，1，3 C3，1，2 D1，3，214. 若一个串非空，子串的定位操作通常称为( C )。A. 串的长度 B.原串的子串 C.串的模式匹配 D.串的连接15. 设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中( C )处。A(i+3)*i2 B(i+1)*i2 C(2n-i+1)*i2 D(2n-i-1)*i216. 在( C )运算中，使用顺序表比链表好。  A插入

9、   B删除   C根据序号查找  D根据元素值查找17. 带头结点的单链表head为空的判断条件是(  C   )。 Ahead= =NULL   Bhead->next= =NULLChead->next=head  Dhead!=NULL 18. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ C ）最节省时间。A）单链表  B）循环链单表  C）带尾指针的循环链单表 D）带头结点的双循环链表19. 栈的插入与删除

10、操作在（ A ）进行。A栈顶          B栈底          C任意位置      D指定位置20. 设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（ D ）。 AABCD BDCBA CACDB DDABC21. 在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是( C )。 &

11、#160;AR=F->next;   BR=R->next;   CF=F->next;  DF=R->next;22. 串是一种特殊的线性表，其特殊性体现在( B )。  A可以顺序存储   B数据元素是一个字符  C可以链接存储   D数据元素可以是多个字符 23. 以下说法正确的是（ C ）。A）空串与空格串是相同的 B）“fox”是“FoxBase”的子串C）空串是零个字符组成的串 D）空串长度等于124. 若n为主串长，m为子串长（m<n），则用简单模式匹配算法最坏情况下，需要比较字符

12、总数是（ C ）。Am         Bm(n-m+1)       Cn*m       D(n-m)*(m-1)25. 将一个A1.100,1.100的三对角矩阵，按行优先存入一维数组B1.298中，A中元素A66，65在B数组中的位置k为（ B ）。A）198 B）195 C）19726. 一个稀疏矩阵的转置矩阵应是（ B ）。A.下三角矩阵 B稀疏矩阵C非稀疏矩阵 D有时为稀疏矩阵27. 广义表（e）的表头

13、是（ C ）。A）e B）( ) C）(e) D）(e) 28. 深度为5的二叉树至多有(   C  )个结点。 A16           B32           C31          D1029. 具有10个叶子结点的二叉树中有（B）个度为2的结点。A8 B9 C10 D113

14、0. 在二叉树的中序遍历递归算法中，顺着搜索路径，在第( B )次经过结点时作访问操作。  A1   B2   C3   D431. 在中序线索二叉树中，若某结点有右孩子，则该结点的直接后继是( D )。  A 左子树的最右下结点   B 右子树的最右下结点  C 左子树的最左下结点   D 右子树的最左下结点 32. 按照二叉树的定义，具有3个结点的二叉树有( C   )种形态。 A3         &

15、#160; B4           C5          D633. 某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B）的二叉树。 A空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子34. 图的广度优先搜索类似于树的( D )次序遍历。A先根 B中根 C后根 D层次 35. n个顶点的强连通图中至少含有( B )。An-l条有向边 Bn条有向边 Cn(n-1)/2条有向边 D

16、n(n-1)条有向边36. 任何一个无向连通图的最小生成树（B）。 A只有一棵 B有一棵或多棵 C一定有多棵D可能不存在37. 设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V2包含V1，E2包含E1，则称( A )。  AG1是G2的子图   BG1是G2的连通分量  CG2是G1的连通分量   DG2是G1的子图 38. 下面关于图的存储的叙述中，哪一个是正确的。 ( A )  A用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,与边数无关  B用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,与结点个数无

17、关  C用邻接表存储图，占用的存储空间数只与图中结点个数有关，与边数无关  D用邻接表存储图，占用的存储空间数只与图中边数有关，与结点个数无关 39. ( D )适合用邻接表表示。  A稠密图   B有向完全图  C无向完全图   D稀疏图 40. 一般，图的DFS生成树的高度( C )BFS生成树的高度。  A小于   B等于   C大于   D小于或等于 41. 从一棵二叉排序树中查找一个元素时，其平均时间复杂度为( C )。 AO(1) BO(n) CO(1og2n) DO(n2)42.

18、二分查找法要求查找表中各元素的键值必须是( A )排列。 A递增或递减 B递增 C递减 D无序43. 向具有n个结点的、结构均衡的二叉排序树中插入一个元素的时间复杂度为 ( B )。 AO(1) BO(log2n) CO(n) DO(nlog2n)44. 线性表必须是( D )，才能进行二分查找。  A用向量存储的线性表   B用链表存储的有序表  C用链表存储的线性表   D用向量存储的有序表45. 按照不同的顺序输入4，5，6三个关键字，能建立（ B ）棵不同的二叉排序树。A）6 B）5 C）4 D）346. 在一棵m阶B-树中，若在某结点中插入一个

19、新关键字而引起该结点的分裂，则该结点中原有（ D ）个关键字。A）ëm/2û B）ëm/2û - 1 C）m D）m-1 E）ém/2ù F）ém/2ù - 1 47. 设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用(    C  )法。 A冒泡排序                &#

20、160;    B快速排序 C堆排序                        D基数排序48. 下列序列中( B )是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。 Ada,ax,eb,de,bbffba,gc Bcd,eb,ax,da,bbffha,gc Cgc,ax,cb,cd,bbffda,ba Dax,bb,c

21、d,daffeb,gc,ba49. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( B )。  AO(1)   B O(n)   C O(n2)   D O(log2n)50. 以下排序方法中，稳定的排序方法是( B )。  A直接插入排序和希尔排序   B直接插入排序和冒泡排序  C希尔排序和快速排序   D冒泡排序和快速排序 51. 在快速排序中，每次划分选择的基准元素为该区间的( D )时，得到的两个子区间是均匀的。  A最大值   B最小值   C任意

22、值   D中间值 52. 若从二叉树的任一结点出发到根的路径上所经过的结点序列按关键字有序，则该二叉树是下列树中的哪种?（ C ）A. 二叉排序树 B. 哈夫曼树 C. 堆。二、 填空题1. 在一个长度为n的顺序表中删除第i个元素，要移动_n-i_个元素。 2. 在顺序表中插入或删除一个元素，需要平均移动 表长的一半 元素，具体移动元素的个数与 元素所在的位置 有关。3. 若线性表采用顺序存储结构存放，那么在长度为n的线性表中删除第i（1in）个数据元素需要移动 n-i 个数据元素，在长度为n的线性表中第i（1in）个数据元素之前插入一个新的数据元素需要移动 n-i+1 个数据元素。

23、4. 在非空的单循环链表h中，某个结点p为尾结点的条件是 p->next = h 。5. 一个队列的入队序列是a、b、c、d，则队列的输出序列为_abcd_。6. 栈结构通常采用的两种存储结构是_顺序栈_和_链栈_。7. 设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是 3 。8. 设有一个n×n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中 (2n-i+1)*i2 处。9. 设有5对角矩阵A

24、 = (aij)20*20，按特殊矩阵压缩存储的方式将其5条对角线上的元素存于数组B0：m中，计算元素A10,10的存储位置 44 。10. 已知广义表L=（a,( ),b),(e)），利用取表头和取表尾的操作分离出原子e的运算是 GetHead(GetHead(GetHead(GetTail(GetTail(L) 。11. 设广义表B=( ) ,(a, (b, c), (e,f)，( )，表头为 ( ) ，表尾为 (a, (b, c), (e,f)，( ) 。12. 在空串和空格串中，长度不为0的是_空格串_。 13. 有n个结点的二叉链表中，其中空的指针域为n+1.指向孩子的指针个数为_n

25、-1_。 14. 中缀算术表达式5+6/(23-(6+15)*8 所对应的后缀算术表达式为_5,6,23,6,15,+,-,/,8,*,+_。15. 假定一棵二叉树的结点个数为50，则它的最小深度为_6_，最大深度为_50_。16. 一棵树的后根序列与其转换的二叉树的 中 序列相同,先根序列与其转换的二叉树的 先 序列相同。17. 具有400个结点的完全二叉树的深度为_9_。18. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_33_个。 19. 已知森林的先序访问序列为ABCDEFGHIJKL；中序访问序列为CBEFDGAJIKLH。则该森林有

26、_2_棵树。20. 当对字符集进行编码时，字符集中任一字符的编码都不是其他字符的编码的前缀，这种编码称_二进制前缀编码_。21. 高度为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为 2h-1+1 个结点，至多为 2h-1 个结点。22. 深度为k的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。23. 一个有30个结点的完全二叉树有 15 个叶子结点；有 14 个度为2的结点。24. 高度为i(i1)的完全二叉树按自上而下，从左到右的次序给结点编号（从1开始），则可能的编号最小的叶子结点的编号为 2k-2+1 。25. 设图G(V，E)，V1，2，3，4，E<

27、l，2>，<1，3>，<2，4>，<3，4>，从顶点1出发，对图G进行广度优先搜索的序列有_2_种。26. 有向图G用邻接矩阵A1.n,1.n存储，矩阵中元素值1代表有弧，0代表无弧，其第i行的所有元素之和等于顶点i的_出度_度。27. 一个连通图的生成树是该图的 极小 连通子图。若这个连通图有n个顶点，则它的生成树有_n-1_条边。28. n个顶点的无向连通图的邻接矩阵中至少有_2(n-1)_个非零元素，至多有_n(n-1)_个非零元素。29. PRIM算法与图的边数无关，适合求解 稠密图 的最小生成树。30. 一棵3阶B-树中每个结点最多有 3 棵

28、子树，每个结点最多有 2 个关键字。含有9个叶子结点的3阶B-树至少有 4 个非叶结点，至多有 7 个非叶结点。31. 从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为_1_和_3_。32. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左 子树上。33. 分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态递增序列按递增顺序排序，最省时间的是算法 插入排序 ，最费时间的是算法 快速排序 。三、 简答及图示说明题1. 广义表的基本概念，如A = (a,b),c,(d,e,f)，用GetGead和GetTail操作取元素d2. 根据给定二叉树的先序和中序序列，构造二叉树3. 根据给定树的先序和后序序列，构造树4. 已知二叉树，画出中序的线索。5. 森林和二叉树的相互转换6. 有7个带权结点