第一章 数据结构概述（二）数据结构的概念(5'42")随堂测验1、在数据结构中，从逻辑上可以把数据结构分成（ ）
a、动态结构和静态结构
b、逻辑结构和物理结构
c、线性结构和非线性结构
d、内部结构和外部结构
2、数据元素是数据的最小单位。( )
第二章 线性表——顺序表（总时长30'44''）（一）表结构的基本概念（5'52''）随堂测验1、线性表是 。
a、一个有限序列，可以为空
b、一个有限序列，不可以为空
c、一个无限序列，可以为空
d、一个无限序列，不可以为空
2、若数组m可存放10个元素，每个元素占4个字节，从首地址x开始按顺序连续存放，那么，元素m[8]的起始地址为_____。
a、x 8
b、x 28
c、x 32
d、x 64
第二章 线性表——链表（下）(总时长18'38''）第一、二章测验1、在数据结构中，从逻辑上可以把数据结构分为（ ）。
a、动态结构和静态结构
b、紧凑结构和非紧凑结构
c、线性结构和非线性结构
d、内部结构和外部结构
2、数据结构在计算机内存中的表示是指（ ）。
a、数据的存储结构
b、数据结构
c、数据的逻辑结构
d、数据元素之间的关系
3、在数据结构中，与所使用的计算机无关的是数据的（ ）结构。
a、逻辑
b、存储
c、逻辑和存储
d、物理
4、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
a、数据的处理方法
b、数据元素的类型
c、数据元素之间的关系
d、数据的存储方法
5、在决定选取何种存储结构时，一般不考虑（ ）。
a、各结点的值如何
b、结点个数的多少
c、对数据有哪些运算
d、所用的编程语言实现这种结构是否方便。
6、以下说法正确的是（ ）。
a、数据项是数据的基本单位
b、数据元素是数据的最小单位
c、数据结构是带结构的数据项的集合
d、一些表面上很不相同的数据可以有相同的逻辑结构
7、下面说法错误的是（ ） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度o(n)的算法在时间上总是优于复杂度o(2^n)的算法 （3）所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低
a、(1)
b、(1),(2)
c、(1),(4)
d、(3)
8、在下面的程序段中，对x的赋值语句的频度为（ ） for (i=1;i<=n;i ) for (j=1;j<=n;j ) x=x 1;
a、o(2^n)
b、o(n)
c、o(n^2)
d、o(log2n)
9、下面程序段的时间复杂度是 ( ) 。 i ＝ 0； while（i<=n） i = i * 3；
a、o(2^n)
b、o(n)
c、o(n^2)
d、o(log3n)
10、下面程序段的时间复杂度是( )。 for( i =0; i
a、o(2n)
b、o(n*m)
c、o(n^2)
d、o(logn)
11、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )。
a、数据元素具有同一特点
b、不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致
c、每个数据元素都一样
d、数据元素所包含的数据项的个数要相等
12、数据结构研究的内容是（ ）。
a、数据的逻辑结构
b、数据的存储结构
c、建立在相应逻辑结构和存储结构上的算法
d、包括以上三个方面
13、下列各种数据结构中属于线性结构的有（ ）。
a、集合
b、树
c、队列
d、图
14、采用链结构存储线性表时，其地址（ ）。
a、必须是连续的
b、连续不连续都可以
c、部分地址必须是连续
d、必须是不连续的
15、下面关于线性表的叙述中，错误的是哪一个？（ ）
a、线性表采用顺序存储，必须占用一片连续的存储单元。
b、线性表采用链接存储，便于插入和删除操作。
c、线性表采用链接存储，不必占用一片连续的存储单元。
d、线性表采用顺序存储，便于进行插入和删除操作。
16、链式存储的存储结构所占存储空间（ ）。
a、分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
b、只有一部分，存放结点值
c、只有一部分，存储表示结点间关系的指针
d、分两部分，一部分存放结点值，另一部分存放结点所占单元数
17、在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为( )
a、逻辑结构
b、顺序存储结构
c、链表存储结构
d、以上都不对
18、以下属于顺序存储结构优点的是（ ）。
a、存储密度大
b、插入运算方便
c、删除运算方便
d、可方便地用于各种逻辑结构的存储表示
19、一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（ ）。
a、确定性、可行性、有穷性
b、易读性、确定性、有效性
c、有穷性、稳定性、确定性
d、可行性、易读性、有穷性
20、算法的计算量的大小称为计算的（ ）。
a、效率
b、复杂性
c、现实性
d、难度
21、下面关于算法说法错误的是（ ）
a、算法最终必须由计算机程序实现
b、为解决某问题的算法同为该问题编写的程序含义是相同的
c、算法的可行性是指指令不能有二义性
d、以上几个都是错误的
22、程序段 for i:=n-1 downto 1 do for j:=1 to i do if a[j]>a[j 1] then a[j]与a[j 1]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（ ）
a、o（n）
b、o(nlogn)
c、o(n^3)
d、o(n^2)
23、以下属于逻辑结构的是（ ）。
a、顺序表
b、循环链表
c、有序表
d、单链表
24、对于顺序表，以下说法错误的是（ ）
a、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
b、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
c、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
d、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
25、以下说法错误的是 ( )
a、对于线性表来说，定位运算locateelem在顺序表和单链表上的时间复杂度均为o（n）
b、读表元运算在顺序表上只需常数时间o（1）便可实现，因此顺序表是一种随机存取结构
c、在链表上实现读表元运算的平均时间复杂度为o（1）
d、插入、删除操作在链表上的实现可在o（1）时间内完成
e、插入、删除操作在顺序表上的实现，平均时间复杂度为o（n）
26、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）
a、p->next=s;s->next=p->next
b、s->next=p->next;p->next=s
c、p->next=s;p->next=s->next
d、p->next=s->next;p->next=s
27、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）
a、head==null
b、head→next==null
c、head→next==head
d、head!=null
28、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
a、顺序表
b、单链表
c、双链表
d、单循环链表
29、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。
a、单链表
b、单循环链表
c、带尾指针的单循环链表
d、带头结点的双循环链表
30、在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（ ）。
a、rear和rear->next->next
b、rear->next 和rear
c、rear->next->next和rear
d、rear和rear->next
31、哪个选项不是线性表的链式存储结构（ ）
a、单链表
b、顺序表
c、循环链表
d、双向链表
第三章 栈和队（总时长24'53''）
第三章测验
1、在作进栈运算时,应先判别栈是否( )
a、空
b、满
c、上溢
d、下溢
2、在作退栈运算时应先判别栈是否( )
a、空
b、满
c、上溢
d、下溢
3、当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( )
a、n-1
b、n
c、n 1
d、n/2
4、若已知一个栈的进栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，...，pn，若p1＝3，则p2为( )。
a、可能是2
b、一定是2
c、可能是1
d、一定是1
5、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）
a、5 4 3 6 1 2
b、4 5 3 1 2 6
c、3 4 6 5 2 1
d、2 3 4 1 5 6
6、设有一顺序栈s，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（ ）
a、2
b、3
c、5
d、6
7、若栈采用顺序存储方式存储，现两栈共享空间v[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在v[m]，则栈满的条件是（ ）
a、|top[2]-top[1]|=0
b、top[1] 1=top[2]
c、top[1] top[2]=m
d、top[1]=top[2]
8、执行完下列语句段后，i值为：（ ） int f(int x) { return ((x>0) ? x* f(x-1):2);} int i ; i =f(f(1));
a、2
b、4
c、8
d、无限递归
9、表达式3* 2^(4 2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂。
a、3,2,4,1,1；(*^( *-
b、3,2,8；(*^-
c、3,2,4,2,2；(*^(-
d、3,2,8；(*^(-
10、用链接方式存储的队列，在进行删除运算时（ ）。
a、仅修改头指针
b、仅修改尾指针
c、头、尾指针都要修改
d、头、尾指针可能都要修改
11、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。
a、队列
b、多维数组
c、栈
d、线性表
12、设c语言数组data[m 1]作为循环队列sq的存储空间， front为队头指针，rear为队尾指针，则执行出队操作的语句为 （ ）
a、front=front 1
b、front=（front 1）% m
c、rear=(rear 1)%(m 1)
d、front=(front 1)%(m 1)
13、循环队列的队满条件为 ( )
a、(sq.rear 1) % maxsize ==(sq.front 1) % maxsize
b、(sq.front 1) % maxsize ==sq.rear
c、(sq.rear 1) % maxsize ==sq.front
d、sq.rear ==sq.front
14、栈和队列的共同点是（ ）。
a、都是先进先出
b、都是先进后出
c、只允许在端点处插入和删除元素
d、没有共同点
15、数组a[1..n]作为栈的存储空间，栈顶top的初值为n 1,在未溢出的情况表，以下（ ）完成入栈x操作。
a、top ; a[top]=x;
b、a[top]=x; top ;
c、top--; a[top]=x;
d、a[top]=x; top--;
16、元素a,b,c,d依次入栈，出栈无限制，则以下（ ）是可能的出栈序列。
a、c,a,b,d
b、b,a,d,c
c、b,d,a,c
d、a,d,b,c
17、设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); } 则计算fact(n)需要调用该函数的次数为（ ）。
a、n 1
b、n-1
c、n
d、n 2
18、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
a、队列
b、栈
c、线性表
d、有序表
19、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。
a、5，4，3，2，1
b、2，1，5，4，3
c、4，3，1，2，5
d、2，3，5，4，1
20、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。
a、i
b、n-i
c、n-i 1
d、不确定
21、数组ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。
a、r-f
b、(n f-r)%n
c、n r-f
d、（n r-f)%n
22、若一个栈以向量v[1..n]存储，初始栈顶指针top设为n 1，则元素x进栈的正确操作是( )。 a． b．v[top]=x; top ; c． d．v[top]=x; top--;
a、top ; v[top]=x;
b、v[top]=x; top ;
c、top--; v[top]=x;
d、v[top]=x; top--;
23、最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
a、(rear 1)%n==front
b、rear==front
c、rear 1==front
d、(rear-l)%n==front
24、一个递归算法必须包括（ ）。
a、递归部分
b、终止条件和递归部分
c、迭代部分
d、终止条件和迭代部分
25、栈和队列逻辑上都是线性结构。
26、栈是一种先进先出的线性表。
27、栈是一种特殊的线性表，它的插入和删除操作都是在表的同一端进行。
28、栈结构不会出现溢出现象。
29、队列中允许插入的一端叫队头，允许删除的一端叫队尾。
30、队列结构的顺序存储会产生假溢出现象。
31、栈和队列的插入和删除操作特殊，所以，栈和队列是非线性结构。
32、可以通过少用一个存储空间的方法解决循环队列假溢出现象。
33、两个栈共享一片连续空间，可以将两个栈的栈底分别设在这片空间的两端。
34、不论是入队还是入栈操作，在顺序存储结构下都应考虑溢出现象。
35、序列{1,2,3,4,5}依次入栈，则不可能得到{3,4，1,2,5}的出栈序列。
第五章 树和二叉树（总时长53'24"）
第五章测验
1、以下说法错误的是 ( )。
a、树形结构的特点是一个结点可以有多个直接前趋
b、线性结构中的一个结点至多只有一个直接后继
c、树形结构可以表达(组织)更复杂的数据
d、树(及一切树形结构)是一种"分支层次"结构
e、任何只含一个结点的集合是一棵树
2、下列说法中正确的是 ( )。
a、任何一棵二叉树中至少有一个结点的度为2
b、任何一棵二叉树中每个结点的度都为2
c、任何一棵二叉树中的度肯定等于2
d、任何一棵二叉树中的度可以小于2
3、讨论树、森林和二叉树的关系，目的是为了（ ）
a、借助二叉树上的运算方法去实现对树的一些运算
b、将树、森林按二叉树的存储方式进行存储
c、将树、森林转换成二叉树
d、体现一种技巧，没有什么实际意义
4、树最适合用来表示 ( )
a、有序数据元素
b、无序数据元素
c、元素之间具有分支层次关系的数据
d、元素之间无联系的数据
5、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
a、9
b、11
c、15
d、不确定
6、设森林f中有三棵树，第一，第二，第三棵树的结点个数分别为m1，m2和m3。与森林f对应的二叉树根结点的右子树上的结点个数是（ ）。
a、m1
b、m1 m2
c、m3
d、m2 m3
7、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ）
a、250
b、500
c、254
d、501
8、设给定权值总数有n 个，其哈夫曼树的结点总数为( )
a、不确定
b、2n
c、2n 1
d、2n-1
9、二叉树的第i层上最多含有结点数为（ ）
a、2^i
b、2^(i-1)-1
c、2^(i-1)
d、2^i-1
10、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点
a、2h
b、2h-1
c、2h 1
d、h 1
11、利用二叉链表存储树，则根结点的右指针是（ ）。
a、指向最左孩子
b、指向最右孩子
c、空
d、非空
12、已知一棵二叉树的前序遍历结果为abcdef,中序遍历结果为cbaedf,则后序遍历的结果为（ ）。
a、cbefda
b、fedcba
c、cbedfa
d、不定
13、已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。
a、acbed
b、decab
c、deabc
d、cedba
14、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
a、都不相同
b、完全相同
c、先序和中序相同，而与后序不同
d、中序和后序相同，而与先序不同
15、在完全二叉树中，若一个结点是叶结点，则它没（ ）。
a、左子结点
b、右子结点
c、左子结点和右子结点
d、左子结点，右子结点和兄弟结点
16、在下列情况中，可称为二叉树的是（ ）
a、每个结点至多有两棵子树的树
b、哈夫曼树
c、每个结点至多有两棵子树的有序树
d、每个结点只有一棵右子树
17、由3 个结点可以构造出多少种不同的二叉树？（ ）
a、2
b、3
c、4
d、5
18、下面几个符号串编码集合中，不是前缀编码的是（ ）。
a、{0,10,110,1111}
b、{11,10,001,101,0001}
c、{00,010,0110,1000}
d、{b,c,aa,ac,aba,abb,abc}
19、一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组a[1..n]中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组a中的位置是（ ）
a、a[2i](2i<=n)
b、a[2i 1](2i 1<=n)
c、a[i-2]
d、条件不充分，无法确定
20、以下说法错误的是 ( )
a、哈夫曼树是带权路径长度最短的二叉树，路径上权值较大的结点离根较近。
b、若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
c、已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
d、在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
21、在二叉树的二叉链表结构中，指针p所指结点为叶子结点的条件是（ ）。
a、p=null
b、p->lchild==null && p->rchlid==null
c、p->lchild==null
d、p->rchlid==null
22、深度为k的完全二叉树至少有__(1)____个结点，至多有___(2)____个结点。
a、(1)2k-1 (2)2k-1
b、(1)2k (2)2^k-1
c、(1)2^k (2)2^k 1
d、(1)2^(k-1) (2)2^k-1
23、高度为8的完全二叉树至少有______个叶子结点。
a、128
b、63
c、64
d、32
24、一个深度为k的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依此对结点编号，则编号最小的叶子的序号是（ ）
a、2^(k-2)
b、2^(k-2) 1
c、2^(k-1) 1
d、2^(k-1)
25、二叉树的先序序列和中序序列相同的条件是（ ）
a、任何结点至多只有左子女的二叉树
b、任何结点至多只有右子女的二叉树
c、右子树为空
d、左子树为空
26、将下列由三棵树组成的森林转换为二叉树，正确的结果是（ ）
a、
b、
c、
d、
27、设有正文addbcbdccbdcad,字符集为a,b,c,d,设计一套二进制编码，使得上述正文的编码最短。正确的哈夫曼树（要求左孩子权值小于等于右孩子）以及编码是（ ）
a、 a:010 b:011 c:1 d:00
b、 a:011 b:111 c:01 d:0
c、 a:00 b:01 c:0 d:1
d、 a:00 b:01 c:10 d:11
28、完全二叉树一定存在度为1的结点。
29、对于有n个结点的二叉树，其高度为log2n。
30、二叉树的遍历只是为了在应用中找到一种线性次序。
31、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
32、完全二叉树中，若一个结点没有左孩子，则它必是树叶。
33、二叉树只能用二叉链表表示。
34、给定一棵树，可以找到唯一的一棵二叉树与之对应。
35、用链表(llink-rlink)存储包含n个结点的二叉树，结点的2n个指针区域中有n-1个空指针。
36、树形结构中元素之间存在一个对多个的关系。
37、将一棵树转成二叉树，根结点没有左子树。
38、度为二的树就是二叉树。
39、哈夫曼树的结点个数不能是偶数。
40、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
41、如果结点a有 3个兄弟，而且b是a的双亲，则b的度是______。
42、若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。
43、若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的____ __遍历序列中的最后一个结点。
第六章 图结构（下）（总时长40'56''）
第六章测验
1、在一个图中，所有顶点的度数之和等于图的边数的（ ）倍。
a、1/2
b、1
c、2
d、4
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
a、1/2
b、1
c、2
d、4
3、具有n个顶点的有向图最多有（ ）条边。
a、n
b、n(n-1)
c、n(n 1)
d、
4、n个顶点的连通图用邻接距阵表示时，该距阵至少有（ ）个非零元素。
a、n
b、2(n-1)
c、n/2
d、
5、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（ ）图。
a、非连通
b、连通
c、强连通
d、有向
6、下面（ ）算法适合构造一个稠密图g的最小生成树。
a、prim算法
b、kruskal算法
c、floyd算法
d、dijkstra算法
7、用邻接表表示图进行广度优先遍历时，通常借助（ ）来实现算法。
a、栈
b、队列
c、树
d、图
8、用邻接表表示图进行深度优先遍历时，通常借助（ ）来实现算法。
a、栈
b、队列
c、树
d、图
9、深度优先遍历类似于二叉树的（ ）。
a、先序遍历
b、中序遍历
c、后序遍历
d、层次遍历
10、图中有关路径的定义是（ ）。
a、由顶点和相邻顶点序偶构成的边所形成的序列
b、由不同顶点所形成的序列
c、由不同边所形成的序列
d、上述定义都不是
11、下列哪一种图的邻接矩阵是对称矩阵？（ ）
a、有向图
b、无向图
c、aov网
d、aoe网
12、已知图的邻接表如图6.31所示，则从顶点v0出发按广度优先遍历的结果是（ ）。
a、0 1 3 2
b、0 2 3 1
c、0 3 2 1
d、0 1 2 3
13、下面（ ）方法可以判断出一个有向图是否有环。
a、深度优先遍历
b、拓扑排序
c、求最短路径
d、求关键路径
14、对于六度空间理论的证明，采用以下哪种算法更合适？
a、广度优先遍历
b、深度优先遍历
c、拓扑排序
d、关键路径
15、关键路径是事件结点网络中（ ）。
a、从源点到汇点的最长路径
b、从源点到汇点的最短路径
c、最长回路
d、最短回路
16、下列关于aoe网的叙述中，不正确的是（ ）。
a、关键活动不按期完成就会影响整个工程的完成时间
b、任何一个关键活动提前完成，那么整个工程将会提前完成
c、所有的关键活动提前完成，那么整个工程将会提前完成
d、某些关键活动提前完成，那么整个工程将会提前完成
第七章 查找（总时长57'13"）
第七章测验
1、顺序查找法适合于存储结构为（ ）的线性表。
a、散列存储
b、顺序存储或链式存储
c、压缩存储
d、索引存储
2、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度asl为( )。
a、(n-1)/2
b、n/2
c、(n 1)/2
d、n
3、适用于折半查找的表的存储方式及元素排列要求为( )
a、链接方式存储，元素无序
b、链接方式存储，元素有序
c、顺序方式存储，元素无序
d、顺序方式存储，元素有序
4、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
a、必定快
b、不一定
c、在大部分情况下要快
d、取决于表递增还是递减
5、二叉查找树的查找效率与二叉树的( )有关,
a、高度
b、结点的多少
c、树型
d、结点的位置
6、二叉查找树的查找效率在 ( )时其查找效率最低。
a、结点太多
b、完全二叉树
c、呈单枝树
d、结点太复杂
7、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。
a、（100，80， 90， 60， 120，110，130）
b、（100，120，110，130，80， 60， 90）
c、（100，60， 80， 90， 120，110，130）
d、(100，80， 60， 90， 120，130，110)
8、下图所示的4棵二叉树,( )是平衡二叉树。
a、
b、
c、
d、
9、散列表的平均查找长度（ ）
a、与处理冲突方法有关而与表的长度无关
b、与处理冲突方法无关而与表的长度有关
c、与处理冲突方法有关且与表的长度有关
d、与处理冲突方法无关且与表的长度无关
10、有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为h（key）=key mod 13,散列地址为1的链中有（ ）个记录。
a、1
b、2
c、3
d、4
11、关于哈希查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集
a、1
b、2
c、3
d、4
12、设哈希表长为14，哈希函数是h(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
a、8
b、3
c、5
d、9
13、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为( )次。
a、n
b、n 1
c、n 2
d、n-1
14、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为( )。
a、5
b、4
c、3
d、6
15、在哈希函数h（key）=key%p中，p值最好取( )。
a、只能等于表长
b、只能小于表长
c、小于等于表长的最大素数
d、任意值
16、假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（ ）次探测。
a、(k-1)/2
b、k/2
c、k(k 1)/2
d、k(k-1)/2
17、在散列存储中，装填因子α的值越大，则( )。
a、存取元素时发生冲突的可能性就越大
b、存取元素时发生冲突的可能性就越小
c、存取元素时不可能发生冲突
d、毫无影响
18、已知n元整型数组a存放n个学生的成绩，已按由大到小排序，以下算法是用对分（折半）查找方法统计成绩大于或等于x分的学生人数，请填空使之完善。 #define n /*学生人数*/ int uprx(int a[n],int x ) /*函数返回大于等于x分的学生人数*/ { int head=1,mid,rear=n; do { mid=(head rear)/2; if(x<=a[mid])___(1) else________(2) ; }while(____(3) ); if (a[head] a、(1)rear=mid (2)head=mid (3)head>rear
b、(1)head=mid 1 (2)head=mid 1 (3)head=rear
c、(1)rear=mid-1 (2)head=mid (3)head=rear
d、(1)rear=mid-1 (2)head=mid 1 (3)head>rear
19、设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：h（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法hi=(h(key) di) mod 10(di=12,22,32,…,)解决冲突。计算查找成功的平均查找长度为（ ）。
a、13/6
b、15/8
c、17/8
d、17/6
20、选取哈希函数ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。
a、15/10
b、15/8
c、17/10
d、15/6
21、输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），按次序构造一棵二叉排序树bs为（ ）
a、
b、
c、
d、
22、假定对有序表：(3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找，若查找元素54，需依次与哪些元素比较?（ ）
a、3,4,5,7,24,30,42,54
b、5,30,63,54
c、30,63,42,54
d、3,5,30,63,54
23、二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。
24、二叉搜索树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无 右孩子。
25、二叉搜索树一定是满二叉树。
26、从二叉搜索树的根结点一直沿右儿子向下找不一定能找到树中值最大的结点。
27、若二叉搜索树中关键码互不相同，则其中最小元素和最大元素一定是叶子结点。
28、在任意一棵非空二叉搜索树中，删除某结点后又将其插入，则所得二叉搜索树与原二叉 搜索树相同。
29、当向二叉搜索树中插入一个结点，则该结点一定成为叶子结点。
30、折半查找一定比顺序查找快。
31、折半查找可以在有序的顺序表或链表上进行查找。
32、哈希查找效率无法达到预期的o(1)，主要原因是由于出现了冲突。
第八章 排序 (总时长51'51"）
（四）选择排序(14'45'')随堂测验
1、元素比较次数与初始排列次序无关的是_____排序。
a、直接插入
b、冒泡
c、二分插入
d、简单选择
2、用简单选择排序方法对 n 个元素进行排序时，最坏情况下，比较的次数与移动次数分别是_____。
a、o(n)和 o(log n)
b、o(logn)和 o(n^2)
c、o(n^2)和 o(n^2)
d、o(nlogn)和 o(n)
3、一组记录的排序码为{46，79，56，38，40，84}，则利用堆排序（建立大根堆）的方法建立的初始堆为_____。
a、79，46，56，38，40，80
b、84，79，56，38，40，46
c、84，79，56，46，40，38
d、84，56，79，40，46，38
4、从 10000 个无序元素中选出前 10 个最大元素，最好采用_____排序方法。
a、冒泡
b、快速
c、堆
d、插入
5、如果原始数据已有序，那么，使用_____排序算法最快。
a、冒泡
b、直接插入
c、简单选择
d、堆
第8章测验
1、下列内部排序算法中，其比较次数与序列初态无关的算法是（ ）。
a、快速排序
b、直接插入排序
c、冒泡排序
d、简单选择排序
2、下列内部排序算法中，不稳定的排序算法是（ ）。
a、快速排序
b、直接插入排序
c、二路归并排序
d、冒泡排序
3、对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为 （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 ( )。
a、选择
b、冒泡
c、快速
d、插入
4、下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。
a、选择
b、冒泡
c、归并
d、堆
5、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。
a、(38,40,46,56,79,84)
b、(40,38,46,79,56,84)
c、(40,38,46,56,79,84)
d、(40,38,46,84,56,79)
6、下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序。
a、冒泡
b、希尔
c、快速
d、堆
7、就平均性能而言，目前最好的内排序方法是( )排序法。
a、冒泡
b、希尔插入
c、交换
d、快速
8、下列排序算法中，占用辅助空间最多的是：( )
a、归并排序
b、快速排序
c、希尔排序
d、堆排序
9、若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行 （ ）次比较。
a、3
b、10
c、15
d、25
10、快速排序方法在（ ）情况下最不利于发挥其长处。
a、要排序的数据量太大
b、要排序的数据中含有多个相同值
c、要排序的数据个数为奇数
d、要排序的数据已基本有序
11、下列内部排序算法中，在初始序列已基本有序（除去n个元素中的某k个元素后即呈有序，k< a、快速排序
b、直接插入排序
c、二路归并排序
d、冒泡排序
e、简单选择排序
f、堆排序
12、下列四个序列中，哪一个是堆（ ）。
a、75,65,30,15,25,45,20,10
b、75,65,45,10,30,25,20,15
c、75,45,65,30,15,25,20,10
d、75,45,65,10,25,30,20,15
13、有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为 （ ）
a、-1，4，8，9，20，7，15，7
b、-1，7，15，7，4，8，20，9
c、-1，4，7，8，20，15，7，9
d、其他几项都不对
14、从未排序序列中依次取出元素与已排序序列中的元素进行比较,将其放入已排序序列的正确位置上的方法,这种排序方法称为( )。
a、归并排序
b、冒泡排序
c、插入排序
d、选择排序
15、从未排序序列中挑选最大或最小元素,并将其依次放入已排序序列(初始时为空)的一端的方法,称为( )。
a、归并排序
b、冒泡排序
c、插入排序
d、选择排序
16、对n个不同的关键字由小到大进行冒泡排序,在下列( )情况下比较的次数最多。
a、从小到大排列好的
b、从大到小排列好的
c、元素无序
d、元素基本有序
17、对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数最多为( )。
a、n 1
b、n
c、n-1
d、n(n-1)/2
18、对n个关键字作快速排序,在最坏情况下,算法的时间复杂度是( )
a、o(n)
b、o(n^2)
c、o(nlog2(n))
d、o(n^3)
19、堆是一种( )排序。
a、插入
b、选择
c、交换
d、归并
20、堆的形状是一棵( )。
a、二叉排序树
b、满二叉树
c、完全二叉树
d、平衡二叉树
21、下述几种排序方法中,( )是稳定的排序方法。
a、希尔排序
b、快速排序
c、归并排序
d、堆排序
22、数据表中有10000个元素,如果仅要求求出其中最大的10个元素,则采用( )算法最节省时间。
a、冒泡排序
b、快速排序
c、简单选择排序
d、堆排序
23、对同一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（ ）。
a、排序的总趟数
b、元素的移动次数
c、使用辅助空间的数量
d、元素之间的比较次数
24、希尔排序的组内排序采用的是（ ）。
a、直接插入排序
b、折半插入排序
c、快速排序
d、归并排序
25、若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________的。
26、按照排序过程涉及的存储设备的不同，排序可分为________排序和外部排序。
27、直接插入排序可以通过设置 来避免在寻找插入位置的过程中数组下标越界。
28、对包含10个记录的表r[1..10]进行简单选择排序，所需进行的关键字间的比较次数为_______。
猜你喜欢
- 2022-12-05 21:38
- 2022-12-05 21:38
- 2022-12-05 21:05
- 2022-12-05 21:02
- 2022-12-05 20:56
- 2022-12-05 20:43
- 2022-12-05 19:45
- 2022-12-05 19:24
- 2022-12-05 19:14
- 2022-12-05 19:13