数据结构习题

一、 单项选择题1. 下面程序段的时间复杂度为( C ) 。for(inti=0;im;i+) for(intj=0;jn;j+)aij=i*j; AO(m2) BO(n2) CO(m*n) DO(m+n)2. 设有一个递归算法如下 int fact(int n)/n大于等于0 if(nnext;p-next=q-next;Bp=q-next;q-next=p;Cp=q-next;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. 若要在单链表中的结点*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链式存储的线性结构 B顺序存储的线性结构C限制存取位置的线性结构 D限制存取位置的非线性结构11. 对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为（ A ）。Aabcfed Bcabfed Cabcfde Dcbafde12. 队列通常采用两种存储结构是(A )。 A顺序存储结构和链表存储结构 B散列方式和索引方式 C链表存储结构和数组 D线性存储结构和非线性存储结构13. 若让元素1，2，3依次进栈，则出栈次序不可能出现（ C ）种情况。A3，2，1 B2，1，3 C3，1，2 D1，3，214. 若一个串非空，子串的定位操作通常称为( C )。A. 串的长度 B.原串的子串 C.串的模式匹配 D.串的连接15. 设有一个nn的对称矩阵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插入 B删除 C根据序号查找 D根据元素值查找17. 带头结点的单链表head为空的判断条件是(C )。 Ahead= =NULL Bhead-next= =NULLChead-next=head Dhead!=NULL 18. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ C ）最节省时间。A）单链表B）循环链单表C）带尾指针的循环链单表D）带头结点的双循环链表19. 栈的插入与删除操作在（ A ）进行。A栈顶B栈底C任意位置D指定位置20. 设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（ D ）。 AABCD BDCBA CACDB DDABC21. 在一个链队中，假设F和R分别是队首和队尾指针，则删除一个结点的运算是( C )。 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为子串长（mnext = 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. 设有一个nn的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A00存放于B0中，那么第i行的对角元素Aii存放于B中 (2n-i+1)*i2 处。9. 设有5对角矩阵A = (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-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。则该森林有_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，从顶点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 棵子树，每个结点最多有 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个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点生成一棵哈夫曼树，画出相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，并写出哈夫曼编码，计算带权路径长度。7. 给出图的顶点集合和边的集合，能画出图的邻接矩阵、邻接表，或者给出图的存储结构，能够画出对应的图8. 用普里姆（prim）算法或克鲁斯卡尔（Kruskal）算法构造最小生成树。9. 从某个顶点出发，画出图的深度优先生成树和广度优先生成树。10. 设图G=（V，E），V=1，2，3，4，5，6，E=，。请写出图G中顶点的所有拓扑序列。11. 已知一个图的顶点集V和边集G分别为：V=0，1，2，3，4，5，6，7；G=(0,1)3,(0,3)5,(0,5)18,(1,3)7,(1,4)6,(2,4)10,(2,7)20,(3,5)15,(3,6)12,(4,6)8,(4,7)12;按照普里姆算法从顶点2出发得到最小生成树，试写出在最小生成树中依次得到的各条边。12. 设a1、a2、a3是不同的关键字，且a1a2a3,可组成六种不同的输入序列。问其中哪几种输入序列所构造的二叉排序树的高度为3？13. 构造二叉排序树，在查找每个结点概率相等情况下的平均查找长度，二叉排序树的插入和删除算法14. 画出用线性探测再散列（线性探查法）处理冲突时生成的哈希表及计算平均查找长度15. 画出用外链法处理冲突时生成的哈希表及计算查找成功时的平均查找长度16. 对