《数据结构》复习题

一、单项选择题数据结构复习题1 数据结构在计算机中的表示称为数据的（ ） 。A）存储结构 B）抽象结构2对于下面程序段的时间复杂度为（for（i=1;i=n;i+）for（j=1;jnext=p;p-next=q;B ） q-next=p-next;p-next=qC ） q-next=p-next;p=q;D ） p-next=q;q-next=p;16线性表的顺序存储结构具有的特点是（） 。A）可直接随机访问任一元素B）插入删除不需要移动元素C )不必26从一个具有头结点的单链表中查找数据元素值为x 的结点时，在查找成功的情况下，平均比较次数是( ) 。A) nB) n/2C) (n-1)/2D) (n+1)/227对于长度为n 的顺序线性表进行删除元素操作，如删除每个元素的概率相同，则删除一个元素移动元素的平均次数是( ) 。A) n/2B) (n-1)/2C) (n+1)/2 D) Dn28若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的平均时间复杂度为( ) 。A)A) abedB) 32lABC) abcABCD) 21AB38串是( ) 。A )不少于一个字符的序列B )有限个字符的序列C)不少于一个字母的序列D )任意个字母的序列39初始为空的堆栈中依次插入元素:f 、e、d、 c 、 b、 a 以后，连续进行了 3 次删除操作，此时的栈顶元素是( ) 。D) e)存储结构更为恰当。D )广义表A)cB)dC)b40当矩阵非零元素的位置或个数经常变动时，采用(A)顺序表B)三元组表C)十字链表41. 一个三对角矩阵Ann已按行压缩存储到一维数组B中，则B的长度至少为()。A) 3n+1B) 3nC) 3n-1D) 3n-242广义表 (a,b),(c,d) 的表尾是 ()。A) (c,d)B) (c,d)C) (d)D) d43.设某二叉树前序为abdcef,中序为dbaecf,则此二叉树的后序为()。A) dbefcaB) debfcaC) dfebcaD) dbfeca44设一棵二叉树中没有度为 1 的结点，已知叶子结点数为n ，此树的结点数为() 。A) 2n+2B) 2n+1C) 2nD) 2n-145.设二叉树中有n2个度为2的结点，ni个度为1的结点，no个叶子结点，则此二叉树 )。A) n0+n1+n2B) n2+n1+2n0C) 2n2+n1D) 2n0+n1)。46用权值分别为15， 2， 4， 5 的四个结点，构造出的哈夫曼树为(47 .由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度为（）。A） 50B） 60C） 52D） 6548 . A、B两个结点可以构成（）棵不等价的二叉树。A） 2B） 3C） 4D） 549 .设哈夫曼树的叶结点数为n,则它的结点总数为（）。A） 2n-1B） 2nC） 2n+1D）不确定50 .采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的（ ）。A）先序遍历B）中序遍历C）后序遍历D）层次遍历59 .快速排序执行一遍之后，已经到位的元素个数是（）。A） 1B） 3C）nD）n4260 .在下列算法中，操作时间不随文件的初始状态变化的排序算法是（）。A）堆排序 B）折半插入排序 C）基数排序D）快速排序61 .数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用（）排序算法最节省时间。A）快速排序B）希尔排序C）堆排序D）直接选择排序62 .快速排序在最坏情况下时间复杂度是O（n2）,比（）的性能差。A）堆排序B）起泡排序C）选择排序D）直接插入排序63 .下列排序算法中，一趟结束后未必能选出一个元素放在其最终位置上的算法是（）。A）快速排序B）冒泡排序C）树形选择排序D）归并排序64 .若需在O（nlogn）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排 序方法是（）。A）快速排序B）堆排序C）归并排序D）直接插入排序65 .初始文件中有两个关键字相同的记录，通过不稳定的排序方法排序后，（）。A）使得领先关系不发生变化B）领先关系一定发生变化C）两个位置都不会发生变化D）领先关系可能发生变化66 .如果只想得到 1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法平均时间最少。A）起泡排序 B）简单选择排序 C） Shell排序 D）堆排序67 .如77 . 一组记录的排序码为（48,24,18,53,16,26,40）,采用冒泡排序法进行排序，则第一趟排 序需要进行记录交换的次数是（）。A）3B） 4C）5D） 678 .在下列排序方式中，关键码比较次数与记录的初始排列无关的是（）。A）直接选择排序B）冒泡排序C）堆排序D）归并排序79 .倒排文件的最大优点是（）。A）便于进行文件的归并B）有利于文件的插入与删除C）能大大地提高主关键字的查找速度D）能大大地提高次关键字的查找速度80 .文件中可使用的数据的最小单位是（）。A）记录B）字符C）数据项D）数据元素81 . ISAM 文件和VASM文件属于（）。A）索引非顺序文件B）索引顺序文件 C）顺序文件 D）散列文件A）先序遍历B）中序遍历C）后序遍历D）按层遍历90 .对于如下图所示的二叉树，后序遍历结果序列为（）。91.已知某二叉树前序遍历序列为A） BDAEC B） BCADEABDCE ,它可能的中序遍历序列为（C） CBADE D） BEACDA)A,B,C,D,E,F,GB)A,B,D,F,C,E,GC)D,F,B,A,C,G,ED)F,D,B,G,巳C,A92 .具有127个结点的完全二叉树其深度为（）。A） 8B） 7C） 6D） 593 .有一棵非空的二叉树（假设第0层为根结点），其第i层上至多有（）个结点?A） 2iB） 2i-1C） 2i+1D） i94 .二叉树的先序遍历和中序遍历如下:D=1,2,3,4S=RR=, 1121 .要借助栈由输入序列是输入 是输试给出：1,2,3,n得到的输出序列为pi,p2,p3,pn（此输出序列(1)(2)(3)(4)G的邻接矩阵表示；从Vi开始的深度优先遍历;从Vi开始的广度优先遍历; 从Vi开始执行的普里姆（Prim）算法过程中所选边的序列。G试给出：(2)(3)173.逆邻接表；强连通分量。有如下数据结构的形式定义,试画出此结构的图形表示。（南方名校经典试题）DS=D,S,其中：D=1,2,3,4S=RR=,1181.使用散列函数hashf（x）=x MOD 11 ,把一个整数值转换成散列表下标，现要把数据 1、13、12、34、38、33、27、22 插入到散列表中。（1）使用线性探查再散列法来构造散列表并同时列出每个数据的比较次数。（2）使用链地址法来构造散列表。182 .已知二叉排序树采用二叉链表存储结构，根结点的指针为请写出递归算法，从小到大输出该二叉排序树中所有关键字值K的结点的关键字的值。183 .我们知道，待排序记录序列的初始排列状态会影响某些排序算法的时间量级（包 括记录的比软次数和移动次数两个方面）。请在表8-1的空格内，填上“是”或“否”，以表明使用相应的排序算法时记录的比较次数和移动次数之量级是否受影响，即当待排序记录序 列处于某种初始排列状态时排序时间是一个量级；当处于另一种初始排列状态时排序时间又 变成另一个量级。另外，在每行的最后一个空格中亦请标明相应的算法是否是稳定的排序算 法。（南方名校经典试题）填写表格005系主任教授006喃教员教授007刘光系主任教授008黄兵教员讲师009李民室主任教授010赵松教员副教授192 .简单比较文件的多重表和倒排表组织方式各有什么优缺点。193 .简述栈与队列的异同。194 .试说明用栈求表达式值的基本思想。195 .栈的定义及特性。196 .试列举出数据结构栈的至少五种基本操作。197 .栈的特点是什么？试举出栈的两个应用实例。198 .用一维数组sq0:m-1存储循环队列的元素时，怎样另设一个标志tag来区分尾指针(rear)和头指针(front)相等时队列的状态是空还是满？199 .何谓顺序队列的上溢现象？有哪些解决方法？200 .设有一个输入序列 ABCD ,元素经过一个栈到达输出序列，并且元素一旦离开输 入序列不再回到输入序列，试写出经过这个栈后可以得到各种输出序列。