《数据结构》复习题

1、学习文档 仅供参考一、单项选择题数据结构复习题1 数据结构在电脑中的表示称为数据的。A存储结构B抽象结构C顺序结构D逻辑结构2对于下面程序段的时间复杂度为。for(i=1;i<=n;i+)for(j=1;j<=i;j+)x=x+1;AO(n)BO(n2)CO(n*i)DO(n+i)9数据类型为B 值的集合及定义在其上的一组操作的总称D 关键字的集合A数据项的集合C数据元素的集合10网状结构的特征是A结D正确性、可读性、健壮性及确定性12在以下序列中，不是线性表的是A ('a','b','c') B ('AB','

2、;CD')13线性链表中各链结点之间的地址A 必须连续B 部分地址必须连续。C ('a',true,'c') D (a,b,c,d)。C 不一定连续D 连续与否无所谓14如某链表中最常用的操作是在最后一个结点后插入一个结点和删除最后一个结点，则存储方式最节省运行时间。A单链表B带头结点的单链表C单循环链表D带头结点的双循环链表15在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作。Aq->next=p;p->next=q;Bq->next=p->next;p->next=qCq->next

3、=p->next;p=q;Dp->next=q;q->next=p;16线性表的顺序存储结构具有的特点是。A可直接随机访问任一元素B插入删除不需要移动元素x 的结点时，在查找成功C不必26从一个具有头结点的单链表中查找数据元素值为的情况下，平均比较次数是。AnBn/2C(n-1)/2D(n+1)/227对于长度为n的顺序线性表进行删除元素操作，如删除每个元素的概率相同，则删除一个元素移动元素的平均次数是。An/2B(n-1)/2C(n+1)/2DDn28假设长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的平均时间复杂度为。AA abedB32lABC&q

4、uot;abcABC"D"21AB"作，此时的栈顶元素是38串是 。A不少于一个字符的序列C不少于一个字母的序列39初始为空的堆栈中依次插入元素B 有限个字符的序列D 任意个字母的序列:f 、e、d、 c 、 b、 a 以后，连续进行了 3 次删除操AcBdCb40当矩阵非零元素的位置或个数经常变动时，采用A顺序表B三元组表C十字链表D e存储结构更为恰当。D 广义表41. 一个三对角矩阵Ann已按行压缩存储到一维数组B中，则B的长度至少为A 3n+1B 3nC 3n-142广义表(a,b),(c,d) 的表尾是 ()。A (c,d)B (c,d)C (d)D 3

5、n-2D d43设某二叉树前序为abdcef,中序为dbaecf,则此二叉树的后序为)。A dbefca B debfcaC dfebcaD dbfeca44设一棵二叉树中没有度为 1 的结点，已知叶子结点数为 n ，此树的结点数为A 2n+245设二叉树中有中空指针域个数为A n0+n1+n2B 2n+1C 2nn2个度为2的结点，ni个度为。B n2+n 1+2n0C 2n2+n1D 2n-11 的结点，n0 个叶子结点，则此二叉树D 2n0+n146用权值分别为15， 2， 4， 5 的四个结点，构造出的哈夫曼树为47 .由带权9、1、3、5、6的五个叶子结点生成的哈夫曼树的带权路径长度

6、为A50B60C52D6548 .A、B两个结点可以构成棵不等价的二叉树。A2B3C4D549 .设哈夫曼树的叶结点数为n,则它的结点总数为。A2n-1B2nC2n+1D不确定50 .采用邻接表存储的图按深度优先搜索方法进行遍历的算法类似于二叉树的。A先序遍历B中序遍历C后序遍历D层次遍历59 .快速排序执行一遍之后，已经到位的元素个数是。A1B3C9Dn4260 .在以下算法中，操作时间不随文件的初始状态变化的排序算法是A堆排序B折半插入排序C基数排序D快速排序61 .数据表中有10000个元素，如果仅需求出其中最大的10个元素，则采用排序算法最节省时间。A快速排序B希尔排序C堆排序D直接选

7、择排序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个最小元素之

8、前的部分排序的序列，用方法平均时间最少。A起泡排序B简单项选择择排序CShell排序D堆排序67 .如77 .一组记录的排序码为(48,24,18,53,16,26,40),采用冒泡排序法进行排序，则第一趟排序需要进行记录交换的次数是。A3B4C5D678 .在以下排序方式中，关键码比较次数与记录的初始排列无关的是。A直接选择排序B冒泡排序C堆排序D归并排序79 .倒排文件的最大优点是。A便于进行文件的归并B有利于文件的插入与删除C能大大地提高主关键字的查找速度D能大大地提高次关键字的查找速度80 .文件中可使用的数据的最小单位是。A记录B字符C数据项D数据元素81 .ISAM文件和VASM文

9、件属于。A索引非顺序文件B索引顺序文件C顺序文件D散列文件A先序遍历B中序遍历C后序遍历D按层遍历。90 .对于如以下图所示的二叉树，后序遍历结果序列为AA, B, C, D, E, F, GCD, F, B, A, C, G, EBA,B,D,F,C,E,GDF,D,B,G,巳C,A91.已知某二叉树前序遍历序列为A BDAEC B BCADEABDCE ,它可能的中序遍历序列为C CBADE D BEACD。92 .具有127个结点的完全二叉树其深度为。A8B7C6D593 .有一棵非空的二叉树假设第0层为根结点，其第i层上至多有个结点?A2iB2i-1C2i+1Di94 .二叉树的先序遍

10、历和中序遍历如下:D=1,2,3,4S=RR=<1,2>,<1,3>,<2,3>,<2,4>,<3,4>1121.要借助栈由输入序列是输入是输试给出：1G的邻接矩阵表示；2从V1开始的深度优先遍历;3从V1开始的广度优先遍历;4从V1开始执行的普里姆1,2,3,n得到的输出序列为p1,p2,p3,pn(此输出序列Prim算法过程中所选边的序列。G试给出：172 .对如图6-10所示的有向图学习文档仅供参考1各顶点的入/出度；2逆邻接表；3强连通分量。试画出此结构的图形表示。南方名校经典试题173 .有如下数据结构的形式定义,DS=D,

11、S,其中:D=1,2,3,4S=RR=<1,2>,<1,3>,<2,3>,<2,4>,<3,4>174181 .使用散列函数hashf(x)=xMOD11,把一个整数值转换成散列表下标，现要把数据1、13、12、34、38、33、27、22插入到散列表中。1使用线性探查再散列法来构造散列表并同时列出每个数据的比较次数。2使用链地址法来构造散列表。182 .已知二叉排序树采用二叉链表存储结构，根结点的指针为请写出递归算法，从小到大输出该二叉排序树中所有关键字值K的结点的关键字的值。183 .我们知道，待排序记录序列的初始排列状态会影响某

12、些排序算法的时间量级包括记录的比软次数和移动次数两个方面。请在表8-1的空格内，填上“是”或“否”，以说明使用相应的排序算法时记录的比较次数和移动次数之量级是否受影响，即当待排序记录序列处于某种初始排列状态时排序时间是一个量级；当处于另一种初始排列状态时排序时间又变成另一个量级。另外，在每行的最后一个空格中亦请标明相应的算法是否是稳定的排序算法。南方名校经典试题填写表格005系主任教授006喃教员教授007刘光系主任教授008黄兵教员讲师009李民室主任教授010赵松教员副教授192 .简单比较文件的多重表和倒排表组织方式各有什么优缺点。193 .简述栈与队列的异同。194 .试说明用栈求表达式值的基本思想。195 .栈的定义及特性。196 .试列举出数据结构栈的至少五种基本操作。197 .栈的特点是什