数据结构综合习题集含答案_资格考试-建造师考试.pdf

.I .r .数据结构习题集 一、选择题 1数据结构中所定义的数据元素，是用于表示数据的 。（C）A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2从逻辑上可以把数据结构分为 （C ）A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A)A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 4关于串的的叙述，不正确的是(B)A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5带表头结点链队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为（A）A.front=rear B.front!=NULL C.rear!=NULL D.front=NULL 6若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（B）A.n/2 B.n C.(n+1)/2 D.n+1 7将两个各有 n 个元素的有序表合并成一个有序表，其最少的比较次数为（A）A.n B.2n-1 C.2n D.n2 8设顺序表有 19 个元素，第一个元素的地址为 200，且每个元素占 3 个字节，则第 14 个元素的存储地址为(B)A.236 B.239 C.242 D.245 9一个栈的入栈序列是 a,b,c,d,e，则栈的输出序列不可能是(A)A.dceab B.decba C.edcba D.abcde 10元素大小为 1 个单元，容量为 n 个单元的非空顺序栈中，以地址高端为栈底，以 top作为栈顶指针，则出栈处理后，top 的值应修改为(D)A.top=top B.top=n-1 C.top=top-1 D.top=top+1 11设有一个 10 阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为 0，每个元素占有 1 个存储地址空间，则 a45的地址为（B）A.13 B.35 C.17 D.36 12栈和队列(C )A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作 .I .r .D.没有共同之处 13含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为(C)A.n-1 B.n C.n+1 D.n+2 14对一棵有 100 个结点的完全二叉树按层序编号，则编号为 49 的结点，它的左孩子的编号为（B）A.99 B.98 C.97 D.50 15在一个图中，所有顶点的度数之和与图的边数的比是(C)A.12 B.11 C.2 1 D.41 16在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要的边数为(A)A.n-1 B.n C.n+1 D.n/2 17在一个具有 n 个顶点的无向图中，每个顶点度的最大值为（B ）A.n B.n-1 C.n+1 D.2(n-1)18若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（D）A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 19对线性表进行二分查找时，要求线性表必须(C)A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以方式存储，且结点按关键字有序排列 20二分查找算法的时间复杂度是（D）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)21采用排序算法对 n 个元素进行排序，其排序趟数肯定为 n-1 趟的排序方法是（C）A.插入和快速 B.冒泡和快速 C.选择和插入 D.选择和冒泡 22.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是(B)A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的 23在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于(B)A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表 24排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是(B)A.选择排序 B.插入排序 C.冒泡排序 D.快速排序 25下列程序段的时间复杂度为 。（C）for（i=0；im；i+）单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .for（j=0；jt；j+）c ij=0；for（i=0；im；i+）for（j=0；jt；j+）for（k=0；kn；k+）c ij=c ij+a ik*bkj；A.O(m+nt)B.O(m+n+t)C.O(mnt)D.O(mt+n)26数据的四种基本逻辑结构是指（D ）A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表 C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构 27在表长为 n 的顺序表上做插入运算，平均要移动的结点数为（C ）。A.n/4 B.n/3 C.n/2 D.n 28含有 10 个结点的二叉树中，度为 0 的结点数为 4，则度为 2 的结点数为（A ）。A.3 B.4 C.5 D.6 29定义二维数组 A1 8，010，起始地址为 LOC，每个元素占 2L 个存储单元，在以行序为主序的存储方式下，某数据元素的地址为 LOC+50L，则在以列序为主序的存储方式下，该元素的存储地址为（D）。A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L 30下列程序段的时间复杂度为_。（D ）for(i=1；i=n；i+)for(j=1；j=n；j+)for(k=1；k=n；k+)s=i+j+k；A.O(m2)B.O(m3)C.O(n2)D.O(n3)31排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是(B )。A.选择排序 B.插入排序 C.冒泡排序 D.快速排序 32设有一个栈，按 A、B、C、D 的顺序进栈，则可能为出栈序列的是(A)。A.DCBA B.CDAB C.DBAC D.DCAB 33对一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点，它的父结点的编号为（A）。A.24 B.25 C.98 D.99 34对一棵二叉排序树采用中序遍历进行输出的数据一定是（D ）。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列 35散列表中由于散列到同一个地址而引起的“堆积”现象，是(B )。A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表“溢出”引起的 36要解决散列引起的冲突问题，常采用的方法有（D ）。A.数字分析法、平方取中法 B.数字分析法、线性探测法 C.二次探测法、平方取中法 D.二次探测法、链地址法 37下列程序段的时间复杂度为_。（A ）k=1;for（i=0；in；i+）for（j=0；jnext；p-data=q-data；p-next=q-next；free(q)；单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .B q=p-next；q-data=p-data；p-next=q-next；free(q)；C q=p-next；p-next=q-next；free(q)；D q=p-next；p-data=q-data；free(q)；67.设某强连通图中有 n 个顶点，则该强连通图中至少有（C）条边。A n(n-1)B n+1 C n D n(n+1)68设用链表作为栈的存储结构则出栈操作时（B）。A 必须判别栈是否为满 B 必须判别栈是否为空 C 判别栈元素的类型 D 对栈不作任何判别 69数据的最小单位是（A）。A 数据项 B 数据类型 C 数据元素 D 数据变量 70若入栈顺序为 1、2、3、4、5、6，则出栈序列为（B）。A 5，3，4，6，1，2 B 3，2，5，6，4，1 C 3，1，2，5，4，6 D 1，5，4，6，2，3 71.下列关键码序列中，属于堆的是（A）A（15，30，22，93，52，71）B（15，71，30，22，93，52）C（15，52，22，93，30，71）D（93，30，52，22，15，71）二、填空题 1在栈结构中，允许插入的一端称为_栈顶_。2从一个长度为 n 的顺序表中删除第 i个元素(1in)时，需向前移动 _n-i_个元素。3深度为 k 的二叉树，结点数最多有_2k-1_个。4在图中，第一个顶点和最后一个顶点相同的路径称为_回路或环_。5 对于具有 n 个元素的数据序列，采用顺序查找法，其平均查找长度为_（n+1）/2_。6快速排序算法的时间复杂度为_O（nlogn）_。7若图的邻接矩阵不是一个对称矩阵，则该图一定是一个_有向图_。8若一个无向完全图具有 n 个顶点，则该图的边的条数为_n(n-1)/2_。9有 m 个叶子结点的哈夫曼树，其结点总数是_2m-1_。10堆排序需_1_个记录大小的辅助存储空间。11在队结构中，允许插入的一端称为 队尾 ;在栈结构中，允许插入的一端称为 。12在数据结构中，数据的存储结构有 存储、存储、存储和 存储四种方式。13若某二叉树中度为 1 的结点数为 4，度为 2 的结点数为 6，则该树叶子结点数为 7 。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .14树在数据结构中常采用 、三种存储结构表示 15设一个顺序栈 S，元素 s1，s2，s3，s4，s5，s6 依次进栈，如果 6 个元素的退栈顺序为 s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为 3 。16对一棵深度为 10 的满二叉树按层编号，则编号为 51 的结点，它的双亲结点编号为 25 。17一个具有 10 个顶点的完全无向图中有 45 条边。18在无向图 G 的邻接矩阵 A 中，若 Aij 等于 0，则 Aji 等于 0 。19对二叉排序树进行 遍历，可得到排好序的递增结点序列。20设顺序表的表长为 n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为 。21实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是 的。22对顺序表执行删除操作，其删除算法的平均时间复杂性为 O（n）。23对于具有 n 个元素的有序序列，若采用冒泡排序，最多需要进行 1 趟起泡。24在图中，第一个顶点和最后一个顶点相同的路径称为 。25在栈结构中，允许插入的一端称为_，另一端称 为_。26从一个长度为 n 的顺序表中删除第 i 个元素(1in)时，需向前移动 _n-i_个元素。27一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素为_n-i+1_。28深度为 k 的二叉树，结点数最多有_个。29二路归并排序算法的时间复杂度为_。30含有 n 个顶点和 n-1条边的连通图 G 采用_邻接表_存储结构较省空间。31在图中，第一个顶点和最后一个顶点相同的路径称为_。32对于具有 n 个元素的数据序列，采用顺序查找法，其平均查找长度为_。33索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用_查找法在块中找到具体的元素值。34对 n 个元素进行冒泡排序时，最少的比较次数为_n-1_。35快速排序法在待排序数据_基本有序_的情况下最不利于发挥其长处。36快速排序算法的时间复杂度为_O(nlogn)_。37在一棵二叉排序树上按_遍历得到的结点序列是一个有序序列。38若图的邻接矩阵不是一个对称矩阵，则该图一定是一个_。39若一个无向完全图具有 n 个顶点，则该图的边的条数为_。40有 m 个叶子结点的哈夫曼树，其结点总数是_。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .41对一棵深度为 10 的满二叉树按层编号，则编号为 51 的结点，它的双亲结点编号 为_25_。42具有 n 个顶点的连通图至少需有_条边。43堆排序需_1_个记录大小的辅助存储空间。44.队列是一种 _ 线性表。45算法的特性有：输入、_、_、可行性、输出。46对任意非空二叉树，若叶子结点数为 n0，度为 1 的结点数为 n1，度为 2 的结点数为n2，则 n0_ 47中序遍历二叉树步骤是：若二叉树非空，1)中序遍历左子树，2）_，3)中序遍历右子树 48.n 阶上三角矩阵采用一维数组存放时，可压缩存储到_个元素中。49连通图的最小生成树中有 n 个顶点，_条边，并不能存在_。50n 个结点的完全二叉树，结点按从上到下从左到右编号，其中序号为 i结点的左孩子序号_2i_ 三、应用题 1有一字符串序列为 5*-x-y/x+2，利用栈的运算将其输出结果变为 5x-*yx+/-2，描述栈的操作特点，试写出该操作的入栈和出栈过程（用 push(a)表示 a 入栈，pop(a)表示 a出栈）。特点自己从书上找。Push(5)pop(5)push(*)push(-)push(x)pop(x)pop(-)pop(x)push(-)push(y)pop(y)push(/)push(x)pop(x)push(+)pop(+)pop(/)pop(-)push(2)pop(2)2在栈的输入端有 6 个元素，输入顺序为 A，B，C，D，E，F。请描述栈的操作特点，并判断能否在栈的输出端得到序列 DCFEBA，若能，给出入栈、出栈操作的过程，若不能，简述其理由。（push（A）表示入栈，pop（A）表示出栈）栈的操作特点自己查找 能 Push（A）Push（B）Push（C），Push（D），Pop（D），Pop（C）Push（E），Push（F）Pop（F），Pop（E），Pop（B），Pop（A）3.有一字符串的次序为-3*y+ay！2，试利用栈将输出次序改变为 3y*-ay！2+，描述栈的操作特点，写出该输出序列对应的进栈和退栈的操作步骤。(用push(x)表示x进栈，pop(x)表示 x 退栈)Push(-)push(3)pop(3)push(*)push(y)pop(y)pop(*)pop(-)push(+)push(a)单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .pop(a)push(/)push(y)pop(y)push(!)pop(!)push(2)pop(2)pop(/)pop(+)4已知一棵二叉树的先根遍历序列为 ABCDEGHF，中根遍历序列为 CBEDAGFH，画出该二叉树，并写出后序遍历序列。后序遍历序列：CEDBFHGA 5已知无向图 G 的邻接矩阵如图所示。请画出该无向图，并写出 v0 出发按深度优先遍历时的访问序列。6 已知散列函数为 H(key)=key%7，散列表长度为 7(散列地址空间为 0.6)，待散列序列为：(25，48，32，50，68)。根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；若要用该散列表查找元素 68，给出所需的比较次数。H（25）=25%7=4 H（50）=50%7=1 H（48）=48%7=6 H（68）=68%7=5 H（32）=32%7=4 68502532012345486 查找 68：首先计算：H（68）=68%7=5，68 与 32 比较，68 与 48 比较，68 与 68 比较查找成功，共比较 3 次。7给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，描述二叉排序树的定义，画出插入完成后的二叉排序树。定义自己从书上找 单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .8用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行升序排序，写出整个冒泡排序的各趟排序过程。第一趟排序结果：38,49,65,76,97,27,49,134 第二趟排序结果：38,49,65,76,27,49,97,134 第三趟排序结果：38,49,65,27,49,76,97,134 第四趟排序结果：38,49,27,49,65,76,97,134 第五趟排序结果：38,27,49,49,65,76,97,134 第六趟排序结果：27,38,49,49,65,76,97,134 9某通讯电文由 A，B，C，D，E，F六个字符编码组成，每个字符编码在电文中出现的次数分别是 6，5，9，10，20，1，请描述哈夫曼树的特点，并画出这六个字符编码所用的哈夫曼树，写出每个字符的哈夫曼编码。哈夫曼树特点从教材上找。602090110105611211913105101ABCDEF 10已知一棵二叉树的前序序列是 ABCDEFG，中序序列是 CBDAEGF。请构造出该二叉树，描述后序遍历过程，给出该二叉树的后序序列。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .ABDEFGC 后序遍历过程：若根不为空，则执行如下操作，否则结束 1）后序访问根的左子树；2）后序访问根的右子树；3）访问根；后序遍历序列：CDBGFEA 11已知无向网的邻接矩阵 A 如图，试画出该网，描述最小生成树算法，并画出该网的最小生成树。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .V1V21V312V46V5108924 最小生成树：V1V21V3V46V524 最小生成树算法描述：可以使用普利姆算法或者克鲁斯卡尔算法；普利姆算法描述：从指定顶点开始将它加入集合中,然后将集合内的顶点与集合外的顶点所构成的所有边中选取权值最小的一条边作为生成树的边,并将集合外的那个顶点加入到集合中,表示该顶点已连通.再用集合内的顶点与集合外的顶点构成的边中找最小的边,并将相应的顶点加入集合中,如此下去直到全部顶点都加入到集合中,即得最小生成树.克鲁斯卡尔算法描述：将图中边按其权值由小到大的次序顺序选取,若选边后不形成回路,则保留作为一条边,若形成回路则除去.依次选够(n-1)条边,即得最小生成树.(n 为顶点数)12设散列表容量为 7（散列地址空间 0.6），给定表（30，36，47，52，34）,散列函数 H（K）=K%6，采用线性探测法解决冲突。要求：（1）构造散列表；（2）求查找数 34 需要比较的次数。单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .13用冒泡排序算法对数据序列（49，38，65，97，76，134，27，49）进行升序排序，写出整个冒泡排序的各趟排序过程。第一趟排序结果：38,49,65,76,97,27,49,134 第二趟排序结果：38,49,65,76,27,49,97,134 第三趟排序结果：38,49,65,27,49,76,97,134 第四趟排序结果：38,49,27,49,65,76,97,134 第五趟排序结果：38,27,49,49,65,76,97,134 第六趟排序结果：27,38,49,49,65,76,97,134 14.已知一棵二叉树的中根遍历序列和后根遍历序列分别为 BDAFEHGC 和 DBFHGECA，试画出这棵二叉树，描述前序遍历过程，并写出前序遍历序列。前序遍历过程：若根不为空，则执行如下操作，否则结束 1）访问根结点；2）前序访问根的左子树；3）前序访问根的右子树；前序遍历序列：abdcefgh 单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .15.设散列表容量为 7（散列地址空间 0.6），给定表（30，36，47，52，34），散列函数 H（k）=k mod 6，采用线性探测法解决冲突。要求：（1）构造散列表；（2）求查找数 34 需要的比较次数。16.已知某图的邻接表存储结构如图所示，画出该图，描述深度优先遍历过程，并根据该邻接表写出从顶点 A 出发按深度优先遍历序列。深度优先遍历序列：ABCDEFGH 遍历过程描述从教材上找 17.已知一组键值序列（33，37，26，43，55，67，42，38），试采用堆排序法对该组序列作排序，描述堆排序过程，给出建立的初始最小堆，以及第一次输出堆顶元素后调整的堆。初建堆 单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .输出堆顶后调整堆 堆排序过程描述：1，将待排序关键字建成一个堆 2，取走堆顶元素，将最后一个元素送入堆顶位置 3，调整成为新的堆 4，直到只剩余一个元素为止 18试写出直接插入排序算法的代码，并给出该算法时间复杂度和稳定性结论。已给出相关结构体定义如下：typedef struct stable elemtype key;Othertype otherinfo；stable;直接插入排序代码按课本或者当时 ppt 上写 19.单链表的结点结构定义如下：typedef struct node int data;struct node*next;Node,*LinkList;试编写在带头结点的单链表 head中查找第 1 个元素值小于 x 的结点的实现算法 Node*GetLinklist(LinkList head，int x)，若找到，则返回指向该结点的指针，否则返回 NULL。Node*GetLinklist(LinkList head,int x)Node*p;p=head-next;while(p-data=x)&(p!=null)单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则.I .r .p=p-next;return(p);20请写出折半查找算法（给出相关结构体定义）。struct ssTable ElemType *elem;int length;int Search_Bin(elem ,key)low=1;high=length;/置区间初值 while(low=high)mid=(low+high)/2;if（key=elemmid)return mid;/找到待查元素 else if(key elemmid)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0;/顺序表中不存在待查元素 21.已知二叉树中序遍历序列是：BGEHACF，先序遍历序列是：ABEGHCF，请完成如下操作：1）画出该二叉树的二叉链表存储结构图。2）写出该二叉树的后序遍历序列。3）画出二叉树的中序线索二叉树存储结构图。22.画出下图的最小生成树，用 prim 算法。v2v1v3v7v6v5v41661241573548 单位从逻辑上可以把数据结构分为动态结构静态结构顺序结构链式结构线性结构非线性结构初等结构构造型结构当待排序序列中记录数较少或基本有序时最适合的排序方法为直接插入排序法快速排序法堆排序法归并排序法关于串的可以采用链式存储带表头结点链队列的队头和队尾指针分别为和则判断队空的条件为若构造一棵具有个结点的叉排序树最坏的情况下其深度不会超过将两个各有个元素的有序表合并成一个有序表其最少的比较次数为设顺序表有个元是元素大小为个单元容量为个单元的非空顺序栈中以地址高端为栈底以作为栈顶指针则出栈处理后的值应修改为设有一个阶的对称矩阵采用压缩存储方式以行序为主序存储为第一个元素其存储地址为每个元素占有个存储地址空间则