《《数据结构》自考同步习题》由会员分享，可在线阅读，更多相关《《数据结构》自考同步习题（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构习题集 1 概述 一、选择题： 1、下列算法的时间复杂度是（ ） for(i=0;i n;i+ +) ci=i； AO（1） BO（n） CO（log2n） DO（nlog2n） 2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ ） A索引存储方法 B顺序存储方法 C链式存储方法 D散列存储方法 3、以下哪一个术语与数据的存储结构无关？（ ） 。 A. 顺序表 B. 链表 C. 散列表 D. 队列 4、算法在发生非法操作时可以做出处理的特性称为（ ） 。 A正确性 B易读性 C健壮性 D高效性 5、逻辑结构是指数据元素的（ ） 。 A关联方式
2、B存储方式 C结构 D数据项 6、研究数据结构就是研究（ ） 。 A数据的逻辑结构 B数据的存储结构 C数据的逻辑结构和存储结构 D数据的逻辑结构、存储结构及其数据的运算 7、从逻辑上可以把数据结构分为（ ） 。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 8 、以下有关数据的叙述中错误的是（ ） 。 A计算机能够处理的数据包括整数、实数、字符、声音、图像等 B数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式 C数据存储结构的实现依赖于计算机语言 D数据的运算是定义在数据的逻辑结构上的 9 、数据的基本单位是（ ） 。
3、 A. 数据结构 B. 数据元素 C. 数据项 D. 文件 10、下列算法的时间复杂度是（ ） for(i=0;i m;i+ +) 1 for(j=0;jn;j+ +) aij=i*j； AO（m2） BO（n2） CO（mn） DO（m+n） 11、算法分析的两个主要方面是（ ） 。 A正确性和简明性 B数据复杂性和程序复杂性 C可读性和可维护性 D时间复杂性和空间复杂性 二、填空题： 1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、 （ ）和（ ） 。 2、数据的逻辑结构是从逻辑关系上描述数据，它与数据的（ ）无关，是独立于计算机的。
4、 3 、( )结构与数据元素本身的内容和形式无关。 4、 程序段 “for(i=1;i=n;i+) k+; for(j=1;jnext=P-next;P-next=S BP-next=S-next;S-next=P； CP-next=P;P-next=S； DP-next=S;S-next=P； 3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ） A（1） B（log2n） CO（n） DO（n2） 2 4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A顺序表 B用头指针表示的单循环链表 C用尾指针表示的单循环链表 D单链表 5、线性表
5、是（ ） A一个有限序列，可以为空 B一个有限序列，不能为空 C一个无限序列，可以为空 D一个无限序列，不能为空 6、在 n 个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ） AO（n） BO（1） CO（log2n） DO（n2） 7、线性表采用链式存储时，结点的地址（ ） A必须是连续的 B必须是不连续的 C连续与否均可 D必须有相等的间隔 8、在单链表中，增加头结点的目的是（ ） A使单链表至少有一结点 B标志表中首结点位置 C方便运算的实现 D说明单链表是线性表的链式存储实现 9、带头结点的单链表 head 为空的判定条件是（ ） Ahead = NULL； Bhead -
6、next = NULL； Chead - next = head； Dhead ! = NULL； 10、在一个具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ） A（1） B（n） C（n2） D（log2n） 11、下列有关线性表的叙述中，正确的是（ ） A线性表中的元素之间是线性关系 B线性表中至少有一个元素 C线性表中任何一个元素有且仅有一个直接前趋 D线性表中任何一个元素有且仅有一个直接后继 12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（ ） A直接前趋 B直接后继 C开始结点 D终端结点 13、将两个各有 n 个元素
7、的有序表归并成一个有序表，其最少的比较次数是（ ） 。 An B.2n-1 C.2n D.n-1 14、链表不具有的特点是（ ） 。 A随机访问 B不必事先估计存储空间 C插入删除时不需移动元素 D所需的空间与线性表成正比 15、在一个单链表中，已知 q所指结点是 p所指结点的直接前趋，若在 p ，q之间插入 s结点，则执行的操作是（ ） 。 As-next=p-next;p-next=s; Bq-next=s;s-next=p; Cp-next=s-next;s-next=p; Dp-next=s;s-next=q; 16、链表具有的特点是（ ） 。 A 可随机访问任一元素 B 插入、删除需
8、要移动元素 3 C 不必事先估计存储空间 D 存储空间是静态分配的 17、一个顺序表一旦说明，其中可用空间大小（ ） A已固定 B可以改变 C不能固定 D动态变化 18、 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素， 则采用 （ ）存储方式最节省时间。 A 顺序表 B单链表 C双向链表 D单循环链表 19、两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q 所指元素的前驱的条件是（ ） 。 AP-next=Q BQ-next=P CP=Q DP-next=Q-next 20、链表不具有的特点是（ ） 。 A可随机访问任一元素 B插入、删除不需要移动元
9、素 C不必事先估计存储空间 D所需空间与线性表长度成正比 21、下面关于线性表的叙述中，错误的是（ ） 。 A线性表采用顺序存储，必须占用一片连续的存储单元 B线性表采用顺序存储，便于进行插入和删除操作 C线性表采用链接存储，不必占用一片连续的存储单元 D线性表采用链接存储，便于进行插入和删除操作 22、在 n 个结点的顺序表中，算法的时间复杂度是 O(1)的操作是（ ） 。 A访问第 i 个结点（1 i n ）和求第 i 个结点的直接前趋（2 i n ） B在第 i 个结点后插入一个新结点（1 i n ） C删除第 i 个结点（1 i n ） D将 n 个结点从小到大排序 23、在一个单链表
10、中，若删除 p 指向结点的后继结点，则执行的操作为（ ） 。 Aq=p-next;p-next=p-next-next;free(q); Bp=p-next;q=p-next;p=q-next;free(q); Cq=p-next-next;p=p-next;free(q); Dp=p-next-next;q=p-next;free(q); 二、 填空题： 1、在双链表中要删除已知结点*p，其时间复杂度为（ ） 。 2、在仅有尾指针 R 指示的单循环链表 R 中，在表尾插入一个结点 S 的语句序列是（ ） 。 3、在带头结点的双链表中，指针所指结点是开始结点的条件是（ ） 。 4、在具有 n
11、个结点的双链表中做插入、删除运算，平均时间复杂度为（ ） 。 5、在一个长度为 n 的顺序表中第 i 个元素（1 i n）之前插入一个元素时，需向后移动（ ）个元素。 6、在双循环链表中，若要在指针 p所指结点之前插入指针 s所指的结点，则需执行下列语句：s-prior=p-prior;p-prior-next=s;( )和 p-prior=s;。 7、已知指针 p 指向双向链表中的一个结点（非首结点、非尾结点） ，则将结点 s 插入在 p 4 结点的直接后继位置的语句是 （ ） s-prior=p； s-next-prior=s； p-next=s; 8、已知带表头结点的单链表 L，指针 p
12、 指向 L 链表中的一个结点（非首结点、非尾结点） ，则删除结点p的直接后继结点的语句是 （ ） ；删除首结点的语句是（ ） 。 三、 判断题： 1、在有序的顺序表和有序的链表上，均可以使用折半查找法来提高查找速度。 （ ） 2、顺序存储的线性表可以随机存取。 （ ） 3、线性表采用顺序存储，必须占用一片连续的存储单元。 （ ） 4、线性表的顺序存储结构优于链式存储结构。 （ ） 四、 程序设计题： 1、已知带头结点的单链表 head中的结点是按整数值递增排序的，写一算法将值为 x 的结点插入到表 head中，使 head仍然有序。 2、用尾插入法建立带头结点的单链表。 3、写出将整数 i 插
13、入到无头结点的链栈中的算法。 4、对给定的单链表 L，编写一个删除 L 中值为 x 的结点的直接前趋结点算法。 5 3 栈和队列 一、选择题： 1、循环队列是空队列的条件是（ ） AQ - rear = = Q - front B （Q - rear + 1）%maxsize = = Q - front CQ - rear = = 0 DQ - front = = 0 2、链栈与顺序栈相比，比较明显的优点是（ ） A插入操作更加方便 B删除操作更加方便 C不会出现下溢的情况 D不会出现上溢的情况 3、若一个栈的输入序列是，n，输出序列的第一个元素是，则第个输出元素是（ ） An - i Bn
14、i + 1 Ci D不确定 4、栈与一般线性表的区别主要在（ ） A元素个数 B元素类型 C逻辑结构 D插入、删除元素的位置 5、一个链栈的栈顶指针是 top，则执行出栈操作时（栈非空） ，用 x 保存被删除结点，则执行（ ） Ax = top;top = top - next； Bx = top - data； Ctop = top - next;x = top - data； Dx = top - data;top = top - next； 6、对于一个栈，给定输入序列为 1，2，3，则下列不可能为输出序列的是（ ） A1，2，3 B3，2，1 C3，1，2 D2，1，3 7、在链接队列
15、执行入队操作（ ） A需判别队是否空 B需判别队是否满 C限制在链表头 p 进行 D限制在链表尾 p 进行 8、以下不属于栈的基本运算是（ ） 。 A删除栈顶元素 B删除栈底元素 C判断栈是否为空 D将栈置为空栈 9、一个栈的入栈序列是 a,b,c,d,e，则栈的不可能的输出序列是（ ） 。 Ae,d,c,b,a Bd,e,c,b,a Cd,c,e,a,b Da,b,c,d,e 10、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。 A线性表的顺序存储结构 B栈 C队列 D线性表的链式存储结构 11、循环队列的特点之一是不会产生（ ） 。 A上溢出 B下溢出 C队满
16、D假溢出 12、设数组 Datan作为循环队列 Q 的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句为（ ） 。 6 Arear=(rear+1)%(n+1) Bfront=(front+1)% n Crear=(rear+1)% n Dfront=(front+1)%(n+1) 13、一个栈的入栈序列是 1,2,3,4,5，则栈的不可能的输出序列是（ ） 。 A5 4 3 2 1 B4 5 3 2 1 C 4 3 5 1 2 D1 2 3 4 5 14、栈是限定在（ ）处进行插入或删除操作的线性表。 A端点 B栈底 C栈顶 D中间 15、 容量是 10 的循环队列的
17、队头位置 q-front 为 2， 则队的第一个数据元素的位置是 （ ） A2 B3 C1 D0 16、循环队列的出队操作是（ ） A q-front=(q-front+1)%maxsize; Bq-front=q-front+1; Cq-rear=(q-rear+1)%maxsize; Dq-rear=q-rear+1; 17、 当循环队列 q 是满队列时， 存放队列元素的数组 data 有 n 个元素， 则 data 中存放 （ ）个数据元素。 An B.n-1 C.n-2 D. 0 18、以下哪一个不是队列的基本运算（ ） 。 A从队尾插入一个新元素 B从队列中删除第 i 个元素 C判断
18、一个队列是否为空 D读取队头元素的值 19、从栈顶指针为 top 的链栈中删除一个结点，并将被删除结点的值保存到 x 中，其操作步骤为（ ） 。 Ax=top-data;top=top-next Btop=top-next;x=top-data; Cx=top;top=top-next Dx=top-data; 20、在一个链队列中，若 f,r 分别为队首、队尾指针，则插入 s 所指结点的操作为（ ） 。 Af-next=s;f=s Br-next=s;r=s; Cs-next=r;r=s; Ds-next=f;f=s 21、循环队列的入队操作应为（ ） 。 Aq-rear=q-rear+1;
19、q-dataq-rear=x; Bq-dataq-rear+=x; Cq-rear=(q-rear+1)%maxsize;q-dataq-rear=x; Dq-dataq-rear=x;q-rear=(q-rear+1)%maxsize; 22、栈和队列都是（ ） 。 A限制存取点的线性结构 B限制存取点的非线性结构 C顺序存储的线性结构 D链式存储的线性结构 23、实现递归调用属于（ ）的应用。 A队列 B栈 C 数组 D树 二、填空题： 1、循环队列用数组 datam存放其元素值，已知其头、尾指针分别是 front 和 rear，则当前队列中元素的个数是（ ） 。 2、栈顶的位置是随着（
20、）操作而变化的。 3、假设以 S 和 X 分别表示进栈和退栈操作，则对输入序列 a，b，c，d，e 进行一系列栈 7 操作 SSXSXSSXXX 之后，得到的输出序列为（ ） 。 4、队列的队尾位置随着（ ）而变化。 5、在（ ）的情况下，链队列的出队操作需要修改尾指针。 6、从栈顶指针为 top的链栈中删除一个结点，并将被删除的结点的值保存在 x中，其操作步骤为（ ） ；top=top-next;。 7、用数组 Am来存放循环队列 q 的元素，且它的头、尾指针分别为 front和 rear，队列满足条件(q.rear+1)%m=q.front,则队列中当前的元素个数为（ ） 。 8 、顺序栈
21、 s存储在数组 s-datamax中，对 s进行出栈操作，执行的语句序列是（ ） 。 9、以下运算实现在循环队列中的初始化操作 void initqueue(seqqueue *q)q-front=0;( ); 三、判断题： 1、循环队列中无上溢现象。 （ ） 2、循环队列只有下溢，没有上溢。 （ ） 3、对顺序栈而言，在栈满状态，如果此时再作进栈运算，则会发生“下溢” 。 （ ） 4、顺序队列和循环队列的队满和队空的条件是一样的。 （ ） 5、为解决队列“假满”问题，可以采用循环数组实现队列存储。 （ ） 6、队列是后进先出表。 （ ） 7、栈是后进先出表。 （ ） 四、应用题： 1、 设有
22、一个栈，元素进栈的次序为 A，B，C，D，E，写出下列出栈序列的操作序列。 （1）CBADE（2）ACBED，其中 I 为进栈操作，O 为出栈操作。 2、如果编号为 1、2、3 的三辆列车进入一个栈式结构的站台，那么可能得到的三辆列车出站序列有哪些？不可能出现的序列是什么？ 五、程序设计题： 1、写出循环队列入队操作的函数。 8 四、 树和二叉树 一、 选择题： 1、在具有 n 个结点的完全二叉树中，结点 i（i1）的父结点是（ ） A2i B不存在 C2i+1 D i/2 2、有 m 个叶结点的哈夫曼树所具有的结点数为（ ） Am Bm+1 C2m D2m - 1 3、下列陈述中正确的（ ）
23、 A二叉树是度为 2 的有序树 B二叉树中结点只有一个孩子时无左右之分 C二叉树中必有度为 2 的结点 D二叉树中最多只有两棵子树，并且有左右之分 4、以二叉链表作为二叉树的存储结构，在具有个结点的二叉链表中(n0)，空链域的个数为（ ） A2n - 1 Bn - 1 Cn + 1 D2n + 1 5、将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为 1，则编号为 49 的结点的左孩子编号为（ ） A99 B98 C50 D48 6、在一棵具有五层的满二叉树中，结点总数为（ ） A31 B32 C33 D16 7、在一棵二叉树中，第 5 层上的结点数最多
24、为（ ） A8 B15 C16 D32 8、由二叉树的（ ）遍历，可以惟一确定一棵二叉树 A前序和后序 B前序和中序 C后序 D中序 9、具有 35 个结点的完全二叉树的深度为（ ） 。 A.5 B.6 C.7 D.8 10、已知一棵二叉树的先序遍历序列为 EFHIGJK，中序遍历序列为 HFIEJGK，则该二叉树根的右子树的根是（ ） 。 AE B. F C. G D. J 11、由 4 个结点构造出的不同的二叉树个数共有（ ） 。 A8 B. 10 C12 D14 12、在完全二叉树中，如果一个结点是叶子结点，则它没有（ ） 。 A. 左孩子结点 B. 右孩子结点 C. 左、右孩子结点 D
25、. 左、右孩子结点和兄弟结点 13、深度为 6 的二叉树最多有（ ）个结点。 A64 B63 C32 D31 9 14、二叉树使用二叉链表存储，若 p 指针指向二叉树的一个结点，当 p-lchild=NULL 时，则（ ） 。 A p 结点左儿子为空 Bp 结点有右儿子 C p 结点右儿子为空 Dp 结点有左儿子 15、 在具有 n 个结点的完全二叉树中， 若结点 i 有左孩子， 则结点 i 的左孩子编号为 （ ） 。 A2i B不存在 C2i+1 D2i-1 16、 将含 100个结点的完全二叉树从根这一层开始， 按从上到下从左到右依次对结点编号，根结点的编号为。编号为 50 的结点 X 的
26、双亲的编号为（ ） 。 A25 B48 C100 D无法确定 17、三个结点可以构成（ ）种不同形状的二叉树。 A 2 C3 D5 18、若由树转化得到的二叉树是非空的二叉树，则二叉树形状是（ ） 。 A根结点无右子树的二叉树 B根结点无左子树的二叉树 C根结点可能有左子树和右子树 D各结点只有一个儿子的二叉树 19、哈夫曼树是访问叶结点的带权路径长度（ ）的二叉树。 A最短 B最长 C可变 D不定 20、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A空或只有一个结点 B高度等于其结点数 C任一结点无左孩子 D任一结点无右孩子 二、 填空题： 1、12 个结点的完全二叉
27、树的叶结点有（ ）个。 2、在任何一棵二叉树中，度为的结点 n0和度为的结点 n2之间的关系是（ ） 。 3、已知完全二叉树的第 4 层有 4 个结点，则其叶子结点数是（ ） 。 4、10 个结点的完全二叉树的叶结点有（ ）个。 5、深度为 6 的二叉树最多有（ ）个结点。 6、一个二叉树中，度为 2 的结点有 3 个，则叶结点有（ ）个。 7、若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的（ ）个结点。 8、 下图为某树的静态双亲表示， 则结点 D 、 E 的双亲结点分别为 （ ） 和 （ ） 。 0 1 2 3 4 9、具有 m 个叶结点的哈夫曼树
28、共有（ ）个结点。 10、二叉树通常有（ ）存储结构和（ ）存储结构两种。 11、二叉树在二叉链表表示方式下，p 指向二叉树的根结点，经运算 s=p；while(s-rchild) A -1 B 0 C 0 D 1 E 2 10 s=s-rchild 后，s 指针指向（ ）结点。 三、 判断题： 1、完全二叉树中，若一个结点没有左孩子，则它必须是叶子。 （ ） 2、由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。 （ ） 3、一般在哈夫曼树中，权值越大的叶子离根结点越近。 （ ） 4、二叉树中任何一个结点的度都是 2。 （ ） 5、一棵哈夫曼树中不存在度为 1 的结点。 （ ） 6、
29、若一个二叉树的叶结点是先根遍历序列的最后一个结点，则它必是中根遍历的序列中的最后一个结点。 （ ） 7、中序遍历二叉排序树的结点不能得到排好序的结点序列。 （ ） 8、完全二叉树一定是满二叉树。 （ ） 9、由二叉树的前序和中序遍历序列可以推导出此二叉树的后序遍历序列。 （ ） 10、满二叉树一定是完全二叉树。 （ ） 11、完全二叉树可采用顺序存储结构实现存储，非完全二叉树则不能。 （ ） 四、 应用题： 1、对给定的一组权值 W=5，2，9，11，8，3，7 ，试构造相应的哈夫曼树，并计算它的带权路径长度。 2、已知一棵二叉树的前序序列和中序序列分别如下，请画出该二叉树。 前序序列：A B
30、 D G J K L H C E I F 中序序列：B G J L K D H A E I C F 3、试找出分别满足下列条件的所有二叉树。 （1）前序序列和中序序列相同； （2）中序序列和后序序列相同； （3）前序序列和后序序列相同。 11 4、设有一组结点，其权值 W=1，4，9，16，25，36，49，64，81，100 ，画出由这些结点所构成的哈夫曼树，并计算带权路径长度。 5、画出下图所示森林经转换后所对应的二叉树。 6、给定权值 3 ，12，3 ，15，5 ，4 ，6 ，8 ，构造相应的哈夫曼树，并求出其 WPL。 7 、已知一棵二叉树的先根遍历序列和中根遍历序列分别是 ABDGH
31、ECFIJ及 GDHBEACIJF，画出这棵二叉树。 8、写出下图所示二叉树的先根遍历、中根遍历、后根遍历的结点序列，并将其转换为森林。 A B C D E F J G H I 12 9 、有五个叶子节点, 分别带权 8,3,2,1,10,构造哈夫曼树，并求其带权路径长度 WPL。 10、一棵二叉树的先序、中序和后序序列分别如下，其中一部分未给出，试求出空格处的内容，并画出二叉树。 先序：_ B _ F _ I C E H _ G 中序：D _ K F I A _ E J C _ 后序：_ K _ F B H J _ G _ A 五、程序设计题： 1、写出二叉树的建立及前序遍历递归算法。 A
32、B E C D F G H I 13 2 、写出二叉树的建立及后序遍历递归算法。 3、写出二叉树的建立及中序遍历递归算法。 五、 图 一、选择题： 1、在一个具有 n 个结点的无向图中，要连通全部结点至少需要（ ） An 条边 Bn+1 条边 Cn-1 条边 Dn/2 条边 2、最小生成树指的是（ ） A由连通图所得到的边数最少的生成树 B由连通图所得到的顶点相对较少的生成树 C连通图的所有生成树中权值之和最小的生成树 D连通图的极小连通子图 3、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ） A1/2 倍 B1 倍 C2 倍 D4 倍 4、有 n 个结点的无向图的边数最多为
33、（ ） An+1 Bn（n-1）/2 Cn（n+1） D2n（n+1） 5、若 n 个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个（ ） A一般矩阵 B对称矩阵 C对角矩阵 D稀疏矩阵 6、设有一个有向图如下所示，请指出下列（ ）序列不是该图的拓扑排序序列？ 14 A.EAFBGDC B.AEBCGFD C.ABCGEFD D.EBAGFCD 7、拓扑排序是对（ ）进行的。 A. 无向图 B. 有向图 C. 任意图 D. 有向图和无向图 8、下面哪一种图的邻接矩阵肯定是对称矩阵（ ） 。 A有向图 B. 无向图 C. AOV网 D. AOE网 9、设有向图 G 有 n 个顶点，它的邻接矩
34、阵为 A，G 中第 i 个顶点 Vi 的度为（ ） 。 A.njijA1, B. njjiA1, C. njijAjiA1),( D. 2njijA1, 10、深度优先遍历类似于二叉树的（ ） 。 A先序遍历 B中序遍历 C后序遍历 D层次遍历 11、有 n 个顶点的无向图的邻接矩阵是用（ ）数组存储。 An 行 n 列 B一维 C任意行 n 列 Dn 行任意列 12、最小生成树的构造可使用（ ） 。 Aprim 算法 B冒泡算法 C迪杰斯特拉算法 D哈夫曼算法 13、有 8 个结点的有向完全图有（ ）条边。 A14 B28 C56 D112 14、有 8 个结点的无向图最多有（ ）条边。 A
35、14 B28 C56 D112 15、广度优先遍历类似于二叉树的（ ） A先序遍历 B中序遍历 C后序遍历 D层次遍历 二、填空题： 1、已知一个图用邻接矩阵表示，计算第 i 个结点的入度的方法是（ ） 。 2 、在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 3、n ( n 0 )个顶点连通无向图的生成树恰有（ ）条边。 4、图的逆邻接表存储结构只适用于（ ）图。 5、若要求一个稀疏图的最小生成树，最好用（ ）算法来求解；若要求一 15 个稠密图 G 的最小生成树，最好用（ ）算法来求解。 三、判断题： 1、有回路的图不能进行拓扑排序。 （ ） 2、连通分量是无向图中的极小连通
36、子图。 （ ） 3、强连通分量是有向图中的极大强连通子图。 （ ） 4、任何一个有向图，其全部顶点可以排成一个拓扑序列。 （ ） 四、应用题： 1、写出下面有向图的邻接矩阵表示和拓扑排序序列。 v1 v2 v3 v6 v4 v5 2 、 写出下面有向图的邻接矩阵表示和拓扑排序序列。 3、 求下图的最小生成树，要求画出最小生成树的生成过程。 52 1 3461 362 16 16 21 11 5 19 6 33 14 6 4 4、 图 G= （V， E） ， V=0， 1， 2， 3， 4， 5， E=,。写出图 G 中顶点的所有拓扑排序。 六、 查找 一、选择题： 1、二叉排序树中，关键字值最
37、大的结点（ ） A左指针一定为空 B右指针一定为空 C左、右指针均为空 D左、右指针均不为空 2、顺序查找法适合于存储结构为 的线性表。 （ ） A散列存储 B顺序存储或链接存储 C压缩存储 D索引存储 3、在查找过程中，若同时还要做增、删工作，这种查找则称为（ ） A静态查找 B动态查找 C内查找 D外查找 4、对线性表进行二分查找时，要求线性表必须（ ） A以顺序方式存储 B以顺序方式存储且元素有序 C以链接方式存储 D以链接方式存储且元素有序 5、一棵二叉排序树 T，用（ ）方法进行遍历，可以得到各结点键值的递增序列 A先根遍历 B中根遍历 C层次遍历 D后根遍历 6、使用折半查找，线性
38、表必须（ ） 。 A以顺序方式存储 B以链式方式存储，且元素已按值排好序 C以链式方式存储 D以顺序方式存储，且元素已按值排好序 7、散列表的地址区间为 0 16，散列函数为 H1（K ）=K%17，采用线性探测法解决冲突，将关键字序列 26，25，72，38，1 ，18，59 依次存储到散列表中。元素 59 存放在散列表 17 中的地址为（ ） 。 A8 B. 9 C. 10 D. 11 8、索引顺序表的特点是顺序表中的数据（ ） 。 A有序 B无序 C块间有序 D散列 9、静态查找表与动态查找表两者的根本差别在于（ ） 。 A逻辑结构不同 B存储实现不同 C施加的操作不同 D数据元素的类型
39、不同 10、设有序表的关键字序列为1，4，6，10，18，35，42，53，67，71，78，84，92，99，当用二分查找法查找键值为 84 的结点时，经（ ）次比较后查找成功。 A2 B3 C4 D12 11、索引顺序表中包含（ ） 。 A顺序表 B索引表 C顺序表和索引表 D索引 12、与其他查找方法相比，散列查找法的特点是（ ） 。 A通过关键字比较进行查找 B通过关键字计算记录存储地址,并进行地址的比较。 C通过关键字计算记录存储地址，并进行一定的比较查找 D通过关键字比较进行查找，并计算记录存储地址 13、在散列函数 H(k)=k MOD m 中，一般来讲，m 应取（ ） 。 A奇
40、数 B偶数 C素数 D充分大的数 二、填空题： 1、对于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在该二叉树的（ ）上继续查找。 2、 （ ）查找法的平均查找长度与元素个数 n 无关。 三、判断题： 1、采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 （ ） 2、散列法中的冲突指的是具有不同关键字的元素对应于相同的存储地址。 （ ） 3 、中序遍历二叉排序树的结点不能得到排好序的结点序列。 （ ） 四、应用题： 1、已知散列函数为 H（k）=k mod 13，关键值序列为 19，01，23，14，55，20，84，27，68，11，10，77，处理冲突
41、的方法为线性探测法，散列表长度为 13，试画出该散列表。 2、画出对长度为 10 的有序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 18 3、已知序列， ，给出二叉排序树的构造过程。 4 、 已知散列函数为 H(K)=K mod 12，关键字序列为 25，37，52，43，84，99，120，15，26，11，70，82，采用拉链法处理冲突，构造开散列表。 5、 在地址空间为 016 的散列区域中，对给定表 （Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec） ，取散列函数为 H(x)
42、=i/2，其中 i 为键值中第一个字母在英语字母表中的序号，画出以线性探测法处理的闭散列表。 五、 程序设计题： 1、写出折半查找算法。 19 6 、 排序 一、选择题： 1、对 n 个不同的排序码进行冒泡排序，在元素无序的情况下的次数为（ ） An + 1 Bn Cn - 1 Dn（n - 1）/2 2、快速排序算法在最坏情况下的时间复杂度为（ ） A（n） B（n log2n） C（n2） D（log2n） 3、从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为（ ） A选择排序 B插入排序 C快速排序 D冒泡排序 4、堆排序是一种（ ）排序 A插入 B选择 C交换 D归并
43、 5、下列排序方法中，排序趟数与序列的原始状态有关的方法是（ ） A选择排序 B希尔排序 C堆排序 D冒泡排序 6、堆的形状是一棵（ ） A二叉排序树 B满二叉树 C完全二叉树 D平衡二叉树 7、在下列排序方法，不稳定的排序方法是（ ） A直接插入排序 B直接选择排序 C冒泡排序 D归并排序 8、快速排序在（ ）情况下最易发挥其长处 A被排序的数据中含有多个相同排序码 B被排序的数据已基本有序 C被排序的数据完全无序 D被排序的数据中的最大值和最小值相差悬殊 9、若用冒泡排序对关键字序列18，16，14，12，10，8进行从小到大的排序，所需进行的关键字比较总次数是（ ） A10 B15 C2
44、1 D34 10、就平均时间而言，下列排序方法中最差的一种是（ ） A堆排序 B快速排序 C归并排序 D选择排序 11、记录的关键字序列为（7,6,8,4,3,5） ，采用快速排序以第一个记录为基准得到的第一次划分结果是（ ） 。 A （5,3,6,4,7,8） B （3,5,6,4,7,8） C （6,4,3,5,7,8） D （5,6,3,4,7,8） 12、稳定的排序方法是（ ） 。 20 A直接插入排序和快速排序 B直接插入排序和冒泡排序 C简单选择排序和直接插入排序 D堆排序和归并排序 13、对以下几个关键字序列进行快速排序，以第一个元素为轴，一次划分效果不好的是（ ） 。 A4 ，
45、1 ，2 ，3 ，6 ，5 ，7 B4 ，3 ，1 ，7 ，6 ，5 ，2 C4 ，2 ，1 ，3 ，6 ，7 ，5 D1 ，2 ，3 ，4 ，5 ，6 ，7 14、堆排序属于（ ） 。 A归并排序 B. 选择排序 C. 快速排序 D. 直接插入排序 15、若待排序序列已基本有序，要使它完全有序，从关键字比较次数和移动次数考虑，应当使用的排序方法是（ ） 。 A直接插入排序 B. 快速排序 C. 直接选择排序 D. 归并排序 16、 若一组记录的排序码为（46，79，56，38，40，84） ，则利用堆排序的方法建立的初始堆为（ ） 。 A79，46，56，38，40，84 B84，79，56
46、，38，40，46 C84，79，56，46，40，38 D84，56，79，40，46，38 17、快速排序在最坏情况下的时间复杂度是（ ） 。 AO(log2n) BO(nlog2n) CO(n2) DO(n3) 18、以下稳定的排序方法是（ ） 。 A快速排序 B冒泡排序 C直接选择排序 D堆排序 19、用冒泡排序的方法对 n 个数据进行排序，第一趟共比较（ ）对元素。 A1 B2 Cn-1 Dn 20、一个记录的关键字为（46,79,56,38,40,84） ，采用快速排序以第一个记录为基准得到的第一次划分结果是（ ） 。 A （38,40,46,56,38,79,84） B （40,
47、38,46,79,56,84） C （40,38,46,56,79,84） D （40,38,46,56,79） 二、填空题： 1、 在选择排序、 堆排序、 快速排序、 直接插入排序中， 稳定的排序方法是 （ ） 。 2、快速排序在最坏情况下的时间复杂度是（ ） 。 3、 （ ）排序方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 4、 对于 n 个记录的集合进行冒泡排序， 其最坏情况下所需的时间复杂度是 （ ） 。 5、在对一组记录（54,38,96,23,15,72,60,45,83）进行直接插入排序时，当把第 7 个记录 60插入到有序表时，为寻找插入位置需比较（ ）次。
48、三、判断题： 1、 对于 n 个记录的集合进行冒泡排序， 所需要的平均时间是 （n） （ ） 2、快速排序是一种稳定的排序方法。 （ ） 3、冒泡排序是不稳定排序。 （ ） 21 4、在堆排序和快速排序中，若原始记录已基本有序，则较适合采用堆排序。 （ ） 四、应用题： 1、写出对关键字序列（40，24，80，39，43，18，20）进行冒泡排序的每一趟结果。 2 、有一组关键码序列（12,5,9,20,6,31,24） ，采用直接插入排序方法由小到大进行排序，请写出每趟排序的结果。 3 、有一组关键码序列（38,19,65,13,97,49） ，采用选择排序方法由小到大进行排序，请写出每趟排序的结果。 五、程序设计题： 1、 写出冒泡排序算法。 2、写出直接插入排序算法，采用高端监视哨。
