ch9 字符串字符串测验1、下面关于串的叙述，哪一个是不正确的（）
a、空串是由空格构成的串
b、串是字符的有限序列
c、模式匹配是串的一种重要运算
d、串既可以顺序存储，也可以链式存储
2、设两个串s1和s2，求s2在s1串中首次出现的位置的运算称作（）
a、模式匹配
b、求子串
c、判断是否相等
d、串连接
3、串s=”myself“，其子串的数目是（）
a、22
b、20
c、21
d、23
4、串是一种特殊的线性表，其特殊性体现在（）
a、数据元素是一个字符
b、可以顺序存储
c、可以链式存储
d、数据元素可以是多个字符
5、设目标串为‘abccdcdccbaa'，模式串为'cdcc'，则第（）次匹配成功。
a、6
b、7
c、8
d、9
6、串'ababaaababaa'的next数组为（）
a、-1 0 0 1 2 3 1 1 2 3 4 5
b、-1 0 1 2 3 4 5 6 7 8 8 8
c、0 1 2 1 2 1 1 1 1 2 1 2
d、0 1 2 3 0 1 2 3 3 2 2 3 4
7、串s='aaab'，其next数组为（）
a、-1 0 1 2
b、0 0 1 2
c、0 1 2 0
d、0 2 0 0
8、kmp算法相对于bf算法的优点是时间效率高
9、串是一种数据对象和操作都特殊的线性表
10、两个字符串相等的充分必要条件是 串的长度相等并且对应的字符相等
11、设主串t的长度为n，模式串p的长度为m，则bf算法的时间复杂度为o(n m)
12、kmp算法是无回溯的模式匹配算法
13、若串s='software'，其子串的数目为37
14、改进的kmp算法中，字符串'abaaaba'的next数组是'-1 0 -1 1 1 0 -1'
ch1 概述概述测验1、for（i=0；i
a、o(m×n）
b、
c、
d、o(m n）
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、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
a、连续或不连续都可以
b、必须是连续的
c、部分地址必须是连续的
d、一定是不连续的
8、算法评价标准包括正确性、可读性、健壮性和（）
a、高效性
b、有穷性
c、可行性
d、确定性
9、分析下面语句是时间复杂度为（） for(count = 0, i = 1; i <= n; i=i*2) count ;
a、
b、o(n)
c、o(2n)
d、
10、在数据结构中，从逻辑上可以把数据结构分成（）
a、线性结构和非线性结构
b、动态结构和静态结构
c、紧凑结构和非紧凑结构
d、内部结构和外部结构
11、下面程序段的时间复杂度是（）。 s=0; for (i=0;i a、o(n^{2})
b、o(n)
c、o(n^{1/2})
d、o(2n)
12、下面程序段的时间复杂度是（）。 for (i=0;i a、o(m*n)
b、o(m)
c、o(n)
d、o(n*n)
13、下面程序段的时间复杂度是（）。 for (i=0;i a、
b、o(n)
c、
d、o(2n)
14、下面程序段的时间复杂度是（）。 for(count = 0, i = 1; i <= n; i ) for(j = 1; j <=n; j=j*2) count ;
a、
b、
c、o(n)
d、
15、若一个算法中的语句频度之和是，则算法的时间复杂度为（）
a、
b、o(n)
c、
d、
ch4 树和二叉树
4.2 二叉树的数学性质随堂测验
1、将一棵有100个结点的完全二叉树从上到下，从左到右依次进行编号，根结点的编号为0，则度为2的结点有（ ）个
a、48
b、49
c、50
d、51
树和二叉树测验
1、3个结点可构成（）棵不同形态的二叉树。
a、5
b、6
c、7
d、8
2、对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ）
a、24
b、99
c、98
d、25
3、二叉树的第k(k>=1)层的结点数最多为( )
a、
b、2k 1
c、2k-1
d、
4、高度为h的完全二叉树最多有（）个结点(h>=1)
a、
b、2h-1
c、2h 1
d、
5、假设一棵完全二叉树按层次遍历的顺序依次存放在数组bt[m]中，其中根结点存放在bt[0]，若bt[i]中的结点有左孩子，则左孩子存放在（ ）
a、bt[2*i 1]
b、bt[i/2]
c、bt[2*i-1]
d、bt[2*i]
6、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域
a、2m
b、2m 1
c、2m-1
d、2m 2
7、设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ ）
a、n在m左方
b、n在m右方
c、n是m的祖先
d、n是m的子孙
8、树形结构是数据元素之间存在一种（ ）
a、一对多关系
b、多对多关系
c、多对一关系
d、多对多关系
9、树最适合用来表示（ ）
a、元素之间具有分支层次关系的数据
b、有序数据元素
c、无序数据元素
d、元素之间无联系的数据
10、已知二叉树的中序序列和后序序列均为abcdef，则该二叉树的先序序列为（ ）
a、fedcba
b、abcdef
c、fdecba
d、fbdcea
11、已知某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历的结点访问序列是( )
a、gdbehfca
b、bdgcefha
c、gdbecfha
d、bdgaechf
12、在线索化二叉树中，t所指结点没有左子树的充要条件是( )
a、t->ltag==1
b、t->leftchild==null
c、t->ltag==1且t->leftchild==null
d、以上都不对
13、下述编码中哪一个不是前缀码( )
a、（0, 1, 00, 11）
b、（00,01,10,,11）
c、（1,01,000,001）
d、（0,10,110,111)
14、设森林f中有三棵树，第一、第二和第三棵树的结点个数分别为m1,m2和m3，则与森林f对应的二叉树根结点的右子树上的结点个数是( )
a、m2 m3
b、m2
c、m3
d、m1 m2
15、关于二叉树性质的描述，正确的是（ ）
a、二叉树结点的个数可以为0
b、二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子
c、二叉树若存在两个结点，则必有一个为根，另一个为左孩子
d、二叉树至少含有一个根结点
16、在树中除根结点外，其余结点分成m (m≥0)个（ ）的集合t1,t2,t3...tm,每个集合又都是树，此时结点t称为ti的父结点，ti称为t的子结点(1≤i≤m)。
a、互不相交
b、可以相交
c、叶结点可以相交
d、枝结点可以相交
17、设一棵m叉树中度数为0的结点数为n0，度数为1的结点数为nl，……，度数为m的结点数为nm，则n0=（ ）。
a、l n2 2n3 3n4 …… (m-1)nm
b、n2 2n3 3n4 …… (m-1)nm
c、2nl 3n2 …… (m 1)nm
d、nl n2 …… nm
18、设二叉树的中序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（ ）。
a、任一结点无左孩子
b、空或只有一个结点
c、高度等于其结点数
d、任一结点无右孩子
19、由二叉树的（）遍历，可以惟一确定一棵二叉树
a、先序和中序
b、先序和后序
c、中序
d、后序
20、写出下面二叉树的中序遍历序列（）
a、bdagehcf
b、abcdefgh
c、bdaeghcf
d、dbagehfc
21、若一棵完全二叉树中某结点无左孩子，则该结点一定是（ ）。
a、叶子结点
b、度为1的结点
c、度为2的结点
d、分支结点
22、void preorder(bintree bt)//递归先序遍历算法 { if(bt==null) return; //递归出口 visit(bt); //访问根结点 inorder (leftchild(bt)); //中序遍历左子树 inorder (rightchild(bt)); //中序遍历右子树 } void inorder(bintree bt)//递归中序遍历算法 { if(bt==null) return; //递归出口 preorder (leftchild(bt)); //先序遍历左子树 visit(bt); //访问根结点 preorder (rightchild(bt)); //先序遍历右子树 } void main() { bt = createbintree(); //创建一棵二叉树 preorder(bt); //入口 } 对下面二叉树执行以上程序，则输出序列是（）
a、1，3，5，4，2
b、1，2，3，4，5
c、5，4，3，2，1
d、1，3，4，5，2
23、下列判断中，（ ）个是正确的。
a、二叉树中不存在度大于2的结点
b、对二叉树周游是指先根、中根和后根周游中的一种
c、完全二叉树中，任何一个结点的度或者为0或者为2
d、构造线索二叉树是为了方便找到每个结点的父结点
24、下面是二叉树的递归遍历算法，该算法是（） void preorder_recursion(bintree bt) { if (bt == null) return; printf("%c", bt->data); preorder_recursion(bt->leftchild); preorder_recursion(bt->rightchild); }
a、先序遍历
b、中序遍历
c、后序遍历
d、层次遍历
25、下面是二叉树的中序遍历算法，对空白处填空（） void inorder_recursion(bintree bt) //递归中序遍历 { if( ) return; inorder_recursion(bt->leftchild); printf("%c",bt->data); inorder_recursion(bt->rightchild); }
a、bt==null
b、bt=null
c、bt!=null
d、以上答案都不对
26、对n个结点二叉树进行中序遍历的非递归算法的时间复杂度为（）
a、o(n)
b、o(1)
c、
d、
27、下面是统计叶子结点数的递归算法，对空白处填空（） int countleafnode(bintree bt) //统计叶子结点数 { if (bt==null) return （）; else if((bt->leftchild==null)&&(bt->rightchild==null)) return （ ）; else return(countleafnode(bt->leftchild) countleafnode(bt->rightchild));
a、0，1
b、1，0
c、1，1
d、0，0
28、具有 n 个结点的二叉树，采用二叉链表存储，会存在多个空链域，为了利用这些空链域，可利用它们建立线索二叉树，左线索指向其( ) ,右线索指向其( ) 。
a、前驱,后继
b、后继，前驱
c、左孩子、右孩子
d、右孩子、左孩子
29、有5个字符，根据其使用频率设计对应的哈夫曼编码，则以下（）是不可能的哈夫曼编码
a、00, 100, 101, 110, 111
b、0000, 001, 010, 011, 1
c、0000, 0001, 001, 01, 1
d、000, 001, 01, 10, 11
30、一棵huffman树共有215个结点，对其进行huaffman编码，共能得到（）个不同的码字
a、108
b、107
c、214
d、215
31、设森林f对应的二叉树为b，它有m个结点，b的根为p，p的右子树结点个数为n，森林f中第一棵树的结点个数是（）
a、m-n
b、m-n-1
c、n 1
d、条件不足，不确定
ch3 栈和队列
栈和队列测验
1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）
a、dceab
b、edcba
c、decba
d、abcde
2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）
a、n-i 1
b、i
c、n-i
d、不确定
3、栈和队列的共同点是（）
a、只允许在端点处插入和删除元素
b、都是先进后出
c、都是先进先出
d、没有共同点
4、循环队列用数组a[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是（）
a、(rear-front m)%m
b、rear-front 1
c、rear-front-1
d、rear-front
5、已知其头尾指针分别是front和rear，判定一个循环队列qu（最多元素为m）为空的条件是（）
a、qu—>front= =qu—>rear
b、qu—>front！=qu—>rear
c、qu—>front= =（qu—>rear 1）%m
d、qu—>front！=（qu—>rear 1）%m
6、一个队列的入列序列是1，2，3，4，则队列的输出序列是（）
a、1，2，3，4
b、4，3，2，1
c、3，2，4，1
d、1，4，3，2
7、已知其头尾指针分别是front和rear，判定一个循环队列qu（最多元素为m）为满的条件是（）
a、qu—>front= =（qu—>rear 1）%m
b、qu—>front= =qu—>rear
c、qu—>front！=qu—>rear
d、qu—>front！=（qu—>rear 1）%m
8、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列（）
a、3，2，5，4，1，6
b、5，4，3，2，1，6
c、2，3，5，6，1，4
d、1，4，6，5，2，3
9、在计算机内实现递归算法时所需的辅助数据结构是( )
a、栈
b、队列
c、二叉树
d、线性表
10、设循环队列的元素存放在一维数组q［0‥30］中，队列非空时，front指示队头元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（ ）
a、q［5］
b、q［4］
c、q［14］
d、q［15］
11、设带有头结点链栈，其栈项指针为top，向链栈中插入一个s结点时，则执行（）
a、s->next=top->next; top->next=s
b、s->next=top->next; top=s
c、s->next=top; top->next=s
d、top->next=s; s->next=top->next
12、一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行空间效率来看，通常递归过程比非递归过程（ ）
a、浪费空间
b、节省空间
c、相同
d、不确定
13、用链接方式存储的队列，在进行插入运算时( )
a、头、尾指针可能都要修改
b、仅修改头指针
c、仅修改尾指针
d、头、尾指针都要修改
14、下面哪种数据结构不是线性结构（）
a、二叉树
b、栈
c、队列
d、线性表
15、在初始为空的栈中依次将元素f，e，d，c，b，a进栈之后，连续进行了三次出栈操作，则此时栈顶元素是（）
a、d
b、c
c、a
d、f
16、在初始为空的队列中依次将元素1，2，3，4，5，6进队之后，连续进行了三次出队操作，则此时队列的头元素是（）
a、4
b、3
c、5
d、6
17、下列描述，与物理存储无关的是（）
a、栈
b、循环队列
c、链表
d、链队列
18、设栈s和队列q的初始状态为空，元素1,2,3,4,5,6.依次通过栈s，一个元素出栈后即刻进入队列q。若这6个元素出队列的顺序是2,4,3,6,5,1，则栈的容量至少应该（ ）。
a、3
b、2
c、4
d、5
19、有5个元素（a，b，c，d，e）按照先后次序压入栈中，进栈后可停留、可出栈，则栈混洗中以d开头的序列个数是（）
a、4
b、3
c、5
d、6
20、表达式a*(b c)-d的后缀表达式是（）
a、abc *d-
b、abcd* -
c、abc* d-
d、- *abcd
21、一个递归算法必须包括（）
a、终止条件和递归部分
b、递归部分
c、迭代部分
d、终止条件和迭代部分
22、和顺序栈相比，链栈 有一个明显的优势是（）
a、通常不会出现栈满的情况
b、通常不会出现栈空的情况
c、插入删除更容易实现
d、删除操作更容易实现
23、下面更合适表示队列的链表结构是（）
a、单向循环链表
b、单向链表
c、双向链表
d、双向循环链表
24、设两个栈s1和s2共享同一空间数组a[0,1…max]，为了最大限度利用数组空间，两个栈采用相向增长的方式，top[1]是低端栈s1的栈顶指针，top[2]是高端栈s2的栈顶指针，则栈满的判断条件是（ ）
a、top[1] 1==top[2]
b、top[1]==0
c、top[1]==max
d、top[2]==max
ch2 线性表
线性表测验
1、从一个长度为n的顺序表中删除第i个元素（0 ≤ i ≤ n-1）时，需向前移动的元素的个数是（）
a、n-i-1
b、i
c、n-i 1
d、n-i
2、设指针变量p指向单链表中结点a，若删除单链表中结点a，则需要修改指针的操作序列为（）
a、q=p->next；p->data=q->data；p->next=q->next；free(q)；
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)；
3、链表不具有的特点是（）
a、可随机访问任一元素
b、插入和删除时不需要移动元素
c、不必事先估计存储空间
d、所需空间与线性表的长度成正比
4、在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针（ ）
a、((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;
b、((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink;
c、(p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;
d、p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;
5、对线性表进行二分查找时，要求线性表必须（）
a、以顺序方式存储，且结点按关键字有序排序
b、以顺序方式存储
c、以链接方式存储
d、以链接方式存储，且结点按关键字有序排序
6、在一个单链表中，若删除p所指结点的后续结点，则语句执行顺序为（）
a、q=p—＞next;p—＞next= q—＞next;free(q)
b、p—＞next= p—＞next;free(p->next)
c、p= p—＞next; p—＞next= p—＞next—＞next;free(p)
d、p= p—＞next—＞next;free(p->next)
7、带头结点的单链表head为空的判定条件是()
a、head—＞next= =nul
b、head= =null
c、head—＞next= =head
d、head!=null
8、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入结点s，则执行的操作序列是( )
a、q->next=s; s->next=p
b、s->next=p->next; p->next=s
c、p->next= s－>next; s->next=p
d、p->next = s; s->next=q
9、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
a、仅有尾指针的单循环链表
b、非循环的单链表
c、非循环的双链表
d、仅有头指针的单循环链表
10、一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（）
a、4
b、3
c、5
d、6
11、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）
a、用尾指针表示的单循环链表
b、顺序表
c、用头指针表示的单循环链表
d、单链表
12、顺序表具有的特点是（）
a、随机访问
b、不必事先估计所需存储空间大小
c、插入与删除时不必移动元素
d、顺序表的插入与删除时的时间复杂度比链式存储的要高
13、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）
a、o(n)
b、o(1)
c、
d、
14、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的( )
a、直接后继
b、直接前趋
c、开始结点
d、终端结点
15、设顺序表为{4，6，12，32，40，42，50，60，72},用折半查找法查找72，需要进行的键值比较次数为( )
a、4
b、2
c、3
d、5
16、若有18个元素的有序表存放在一维数组a[19]中，第一个元素放a[1]中，现进行二分查找，则查找a［3］的比较序列的下标依次为（）
a、9，4，2，3
b、1，2，3
c、9，5，2，3
d、9，5，3
17、若最常用的操作是读取线性表中某个位置元素的值，则采用（ ）存储方式最节省时间
a、顺序表
b、带尾指针的单链表
c、带尾指针的单循环链表
d、单链表
18、设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为( )
a、239
b、236
c、242
d、245
19、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）
a、o(n)
b、o(1)
c、
d、
20、在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）
a、指向后继元素的指针表示
b、数据元素的相邻地址表示
c、数据元素在表中的序号表示
d、数据元素的值表示
21、从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点
a、n/2
b、n
c、2n
d、1
22、在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上（）
a、不一定相邻
b、一定相邻
c、一定不相邻
d、以上答案都不对
23、使用双向链表存储数据，其优点是（）
a、很方便地插入和删除数据
b、提高检索速度
c、节约存储空间
d、很快回收存储空间
24、在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则可用下列两条语句实现该操作，它们依次是（）
a、s→link→link = p→link；p→link = s；
b、b→link = p→link；p→link = a；
c、p→link = s；s→link→link = p→link；
d、s→link = p→link；p→link = s；
25、对以下双链表分别执行如下程序段，说明执行结果中，各个结点的数据域分别是（） p = rear; while( p→llink != head ) { p→info = p→info * 3; p = p→llink; }
a、5，21，27
b、5，7，27
c、15，21，27
d、5，7，9
26、对以下单循环链表分别执行下列程序段，说明执行结果中，各个结点的数据域分别是（） p = tail→link→link; p→info = tail→info;
a、8，3，6，8
b、2，3，6，8
c、2，8，6，8
d、2，3，6，2
27、对以下单链表执行如下程序段，说明执行结果中，各个结点的数据域分别是（） void fun (linklist h) //h是带有头结点的单链表 { pnode p,q; p=h->link; h->link=null; while (p) { q=p; p=p->link; q->link=h->link; h->link=q; } }
a、8，6，4，2
b、2，4，6，8
c、2，8，6，4
d、2，4，8，6，
28、对以下链表执行如下程序段，说明执行结果中，各个结点数据域分别是（） void pur_linklist(linklist h) { pnode p, q, r ,s; p=h->link; if(p==null ) return; while (p->link) { s=p; q=p->link; while (q) { if (q->info==p->info) { s->link=q->link; free(q); q=s->link;} else {s=q;q=q->link;} } p=p->link; } }
a、10，20
b、10，20，10
c、10，20，20，10，10
d、10，20，20
29、对以下两个链表l1和l2执行如下程序段，说明执行结果中，链表中各个结点的数据域是什么。 void func(linklist l1, linklist l2) { pnode p, q, r; q = l2->next; while (q) { p = l1; while (p->next) { if (p->next->data == q->data) { r = p->next; p->next = r->next; free(r); } p = p->next; } q = q->next; } }
a、l1中的数据域分别是30，50；l2中的数据域分别是20，10
b、l1中的数据域分别是20，10；l2中的数据域分别是20，10
c、l1中的数据域分别是30，50；l2链表为空
d、l1链表为空；l2中的数据域分别是20，10
30、根据教科书中线性表的实现方法，线性表中的元素必须是（）
a、相同类型
b、整数类型
c、字符类型
d、结构类型
31、数据在计算机存储器内表示时，物理地址和逻辑地址不相同，称之为（）
a、链式存储结构
b、存储结构
c、逻辑结构
d、顺序存储结构
32、若线性表中最常用的操作是存取第i个元素及其前驱和后继元素的值，为了节省时间应采用的存储方式（）
a、顺序表
b、单链表
c、双向链表
d、单循环链表
33、对于双向链表，在两个结点之间插入一个新结点，需要修改的指针共（）个。
a、4
b、1
c、2
d、3
ch5 搜索树
搜索树测验
1、对一棵二叉排序树进行（）遍历可得到一个升序序列
a、中序
b、先序
c、后序
d、不确定
2、将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树t中，则t中平衡因子为0的分支结点个数是（）
a、3
b、0
c、1
d、2
3、下列选项中，不能构成折半查找中关键字比较序列的是（）
a、500，200，450，180
b、500，450，200，180
c、180，500，200，450
d、180，200，500，450
4、下列二叉排序树中查找效率最高的是（）
a、平衡二叉树
b、二叉判定树
c、没有左子树的二叉排序树
d、没有右子树的二叉排序树
5、在平衡二叉树中，进行查找的效率与（）有关
a、二叉树的高度
b、二叉排序树的结点数
c、后序线索树
d、多有线索树
6、分别以下列序列构造二叉排序树，与众不同的是（）
a、100，80，60，85，110，120，150
b、100，80，60，85，120，110，150
c、100，80，85，60，120，110，150
d、100，80，60，85，120，150，110
7、分别以下列序列构造二叉排序树，与其他三个序列所构造的结果不同的是（）
a、100，60，80，90，120，110，130
b、100，80，90，60，120，110，130
c、100，120，110，130，80，60，90
d、100，80，60，90，120，130，110
8、设二叉排序树中关键字由1到1000整数构成，现要查找关键字为363的结点，下述关键字序列中，不可能在二叉排序上查找的序列是（）
a、925，202，911，240，912，245，363
b、2，252，401，398，330，344，397，363
c、924，220，911，244，898，258，363
d、2，399，387，219，266，382，381，278，363
9、在n个结点的二叉排序上成功找到一个结点，在平均情况下的时间复杂度是（）
a、
b、o(1)
c、o(n)
d、不确定
10、在n个结点的二叉排序上成功找到一个结点，在最坏情况下的时间复杂度是（）
a、o(n)
b、o(1)
c、
d、不确定
11、高度为4的平衡二叉树中，其结点数最多是（）个
a、31
b、32
c、30
d、不确定
12、n个结点的用于折半查找的判定树中，表示查找失败的外部结点共有（）个。
a、n 1
b、n-1
c、n
d、n 2
13、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为a，并已知a的左孩子的平衡因子为0，右孩子的平衡因子为1，则应做（）型调整以使其平衡。
a、rl
b、ll
c、lr
d、rr
14、衡量查找效率的主要标准是平均检索长度，即asl
15、对二叉排序树进行先序遍历，能够得到一个递增的线性序列。
16、平衡二叉树一定是二叉排序树
17、同一组结点无论结点的顺序如何，一定会构成相同的二叉排序树。
18、平衡二叉排序是对二叉排序树的改进。
19、二叉排序树的定义是递归定义
20、在二叉排序树中插入的结点不一定是作为叶子结点插入的。
21、在avl中插入的结点一定是作为叶子结点插入的
22、最小不平衡子树是指离插入结点最近，且包含不平衡因子结点的子树
23、任何一棵二叉排序树的平均查找时间都小于顺序查找法查找同样结点的线性表的平均查找时间
24、如果完全二叉树从根结点开始按层次遍历的序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树
25、对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一致的。
26、avl树中的任意结点的平衡因子的绝对值不大于1
ch6 图
图测验
1、有n个结点，e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）
a、o(n e)
b、o(n)
c、o(e)
d、o(n*e)
2、设无向图的顶点个数为n，则该图最多有（ ）条边。
a、n(n-1)/2
b、n-1
c、n(n 1)/2
d、n*n
3、设有向图的顶点个数为n，则该图最多有（ ）条边。
a、n(n-1)
b、n(n-1)/2
c、n(n 1)/2
d、n(n 1)
4、一个n个顶点的连通无向图，其边的个数至少为 （ ）。
a、n-1
b、n
c、n 1
d、nlogn
5、一个有向图，共有n条弧，则所有顶点的度的总和为（ ）。
a、2n
b、n
c、n-1
d、n/2
6、无向网（加权图）的邻接矩阵是（ ）矩阵。
a、对称
b、上三角
c、下三角
d、稀疏
7、用邻接表存储图所用的空间大小（ ）。
a、与图的顶点和边的个数都有关
b、只与图的边数有关
c、只与图的顶点个数有关
d、只与边数的平方有关
8、执行（）操作时，需要使用队列作为辅助存储空间。
a、图的广度优先遍历
b、线性表的二分查找
c、图的深度优先遍历
d、先序遍历二叉树
9、下面哪一种方法可以判断一个有向图是否有环（回路）
a、拓扑排序
b、深度优先遍历
c、求最短路径
d、求关键路径
10、当各边的权值（ ）时，bfs算法可以用来解决单源最短路径问题。
a、均相等
b、均互不相等
c、不一定相等
d、权值都为1
11、关键路径是aoe网中（ ）。
a、从始点到终点的最长路径
b、从始点到终点的最短路径
c、从始点到终点的边数最多的路径
d、从始点到终点的边数最少的路径
12、在具有n个顶点的图g中，若最小生成树不唯一，则（）
a、g的边数一定大于n-1
b、g的权值最小的边一定有多条
c、g的最小生成树的代价不一定相等
d、以上选项都不对
13、在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（ ）。
a、顶点v的入度
b、顶点v的度
c、顶点v的出度
d、依附于顶点v的边数
14、已知图的邻接表如下所示，则从顶点0出发按深度优先遍历的结点序列是（ ）。
a、0，1，2，3
b、0，1，3，2
c、0，3，2，1
d、0，3，1，2
15、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ ）。
a、0，3，2，1
b、0，3，1，2
c、0，1，2，3
d、0，2，1，3
16、给定的无向图如下，下面不属于深度优先周游序列的是（ ）
a、adcfeb
b、adebcf
c、acebdf
d、afcbed
17、下面哪一种情况的图最适合采用邻接矩阵进行存储？（ ）
a、100个顶点，4000条边的图
b、1000个顶点，1200条边的图
c、10000个顶点，100000条边的图
d、10000个顶点，500条边的图
18、设有一个有向图如下所示，请指出下列（ ）序列不是该图的拓扑排序序列？
a、v0,v1,v2,v4,v5,v6,v3
b、v0,v2,v5,v1,v4,v3,v6
c、v0,v2,v5,v3,v1,v4,v6
d、v0,v2,v5,v1,v3,v4,v6
19、对以下无向图进行prim建立最小生成树的过程是（ ）
a、(v1,v2)(v2,v6)(v5,v6)(v6,v3)(v4,v3)
b、(v1,v2)(v3,v4)(v2,v6)(v2,v4)(v5,v4)
c、(v1,v2)(v2,v6)(v6,v5)(v5,v4)(v4,v3)
d、(v1,v2)(v2,v6)(v5,v6)(v4,v3)(v6,v3)
20、下列网中，（ )是边不带权值的图。
a、aov网
b、通信网
c、公路网
d、aoe网
ch7字典
字典测验
1、用哈希（散列）方法处理冲突（碰撞）时，可能会出现堆积（聚集）现象。下列选项中，会受到堆积现象直接影响的是（ ）
a、平均检索长度
b、存储效率
c、散列函数
d、负载因子
2、在理论上，散列表的平均比较次数为（ ）次
a、1
b、2
c、n
d、n/2
3、下面关于散列表方面，（ ）说法是正确的
a、散列函数选得好，可以减少冲突现象
b、双散列在处理冲突时不会产生“聚集”
c、散列表的负载因子越大，说明空间利用率越好，因此应该使负载因子尽量大
d、对于任何具体关键字都不可能找到不产生冲突的散列函数
4、散列表的地址空间是0~17，散列函数为h(k)= k mod 17. 采用线性探查法解决冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则元素59存放在散列表中的地址（ ）。
a、11
b、8
c、9
d、10
5、散列表的地址空间是0~17，散列函数为h(k)= k mod 17. 采用线性探查法解决冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则查找元素59需要比较的次数为（ ）。
a、4
b、2
c、3
d、5
6、在开地址法解决冲突的散列表中，发生聚集的原因主要是（ ）
a、解决冲突的算法选择不好
b、数据元素过多
c、负载因子过大
d、散列函数选择不当
7、在采用拉链法解决冲突构成的散列表中查找某一关键字，则在查找成功情况下，所探测的这些位置上的关键字 （ ）
a、一定是同义词
b、不一定是同义词
c、都相同
d、一定都不是同义词
8、下列选项中，查找低效的数据结构是（ ）
a、有序链表
b、散列表
c、二叉排序树
d、平衡二叉排序树
9、已知一个线性表（1，13，12，34，38，33，27，22），假定采用h(k) = k mod 11，计算散列地址进行散列存储，若采用拉链法解决冲突，则查找成功的平均检索长度（ ）
a、13/8
b、1
c、9/8
d、13/11
10、设散列地址空间为0 ~ m-1，k为关键字，散列函数为 h(k）= k mod p，为了减少冲突的概率，一般p为 （ ）
a、小于m的最大素数
b、小于m
c、小于m的最大偶数
d、m
11、采用拉链法解决冲突，散列函数为 h(k) = k mod 17 。则需要（ ）个链表
a、17
b、16
c、任意
d、不确定
12、散列函数有一个共同性质，即函数值应当以（ )尽量覆盖到散列地址空间。
a、同等概率
b、最大概率
c、最小概率
d、平均概率
13、“生日悖论”解释了散列表中的（ ）问题
a、冲突不可能完全避免
b、解决冲突的方法
c、散列函数的负载因子要够大
d、拉链法比开地址更优
14、散列表的地址空间是0~17，散列函数为h(k)= k mod 17. 采用线性探查法解决冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则查找成功的平均查找长度为（ ）。
a、13/7
b、11/7
c、12/7
d、以上都不正确
15、散列表的地址空间是0~17，散列函数为h(k)= k mod 17. 采用拉链法解决冲突，将关键字序列26，25，72，38，8，18，59依次存储到散列表中。则查找成功的平均查找长度为（ ）。
a、11/7
b、9/7
c、10/7
d、10/17
16、假定k个关键字互为同义词，若采用线性探查法解决冲突，把k个关键字存入散列表中，则至少要进行多少次探测（ ）
a、k*(k 1)/2
b、k-1
c、k
d、k 1
17、下列（ ）不是merkle树的应用场景。
a、学生信息管理系统
b、区块链技术应用系统
c、点对点网络bt下载
d、git版本控制系统
18、跳跃链表的查找效率为（ ）
a、
b、o(1)
c、o(n)
d、o(n*n)
19、下面哪种数据结构是以空间换取时间效率的（）
a、跳跃链表
b、二叉排序数
c、散列表
d、平衡二叉排序树
20、已知关键码key=582422241，经过散列函数后的散列地址h(key) = 1064，在采用的散列函数为（ ）
a、移位折叠法
b、数字分析法
c、边界折叠法
d、中平方法
ch8排序
排序测验
1、下面关于排序算法的描述，错误的是（ ）
a、冒泡排序的时间复杂度优于直接插入排序的时间复杂度
b、给定待排序元素集合，无论数据元素的初始位置如何，直接选择排序的比较次数不变
c、快速排序是不稳定的
d、二分法插入排序和直接插入排序具有相同的空间复杂度
2、就平均性能而言，目前最好的内排序方法是（ ）排序法。
a、快速
b、冒泡
c、希尔
d、直接选择
3、对关键码序列28，16，32，12，60，20进行希尔排序，增量为3的一趟排序后的序列为（ ）。
a、12，16，20，28，60，32
b、12，16，28，32，60，20
c、12，28，20，32，16，60
d、12，32，20，16，28，60
4、下列排序算法哪个是不稳定排序算法（ )
a、快速排序
b、直接插入排序
c、归并排序
d、冒泡排序
5、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为（ ）
a、10，15，14，18，20，36，40，21
b、10，15，14，18，20，40，36，21
c、10，15，14，20，18，40，36，2l
d、15，10，14，18，20，36，40，21
6、就平均时间而言，下列排序方法中最差的一种是（ ）
a、直接选择排序
b、堆排序
c、快速排序
d、希尔排序
7、在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）
a、直接选择排序
b、希尔排序
c、直接插入排序
d、冒泡排序
8、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）
a、40，38，46，56，79，84
b、38，40，46，56，79，84
c、40，38，46，79，56，84
d、40，38，46，84，56，79
9、快速排序方法是目前最快的排序方法，但是在（ ）情况下最不利于发挥其长处。
a、要排序的数据已基本有序
b、要排序的数据量太大
c、要排序的数据中含有多个相同值
d、要排序的数据个数为奇数
10、结若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用冒泡排序的第一趟结果是( )
a、46, 56, 38, 40, 79, 84
b、46, 79, 56, 38, 40, 84
c、79, 46, 56, 56, 79, 84
d、46, 79, 56, 84, 40, 38
11、按排序过程中依据的原则分类，快速排序属于( )
a、交换类排序
b、插入类排序
c、选择类排序
d、归并类排序
12、按排序过程中依据的原则分类，堆排序属于( )
a、选择类排序
b、插入类排序
c、交换类排序
d、基数类排序
13、对ｎ个不同的排序码按照升序进行冒泡排序，在下列哪种情况下比较的次数最多（ ）
a、从大到小排列好的
b、从小到大排列好的
c、元素无序
d、元素基本有序
14、将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（ ）
a、n
b、2n
c、2n-1
d、
15、某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：（20，15，21，25，47，27，68，35，84）（15，20，21，25，35，27，47，68，84）（15，20，21，25，27，35，47，68，84）所采用的排序方法是（ ）
a、快速排序
b、直接选择排序
c、希尔排序
d、堆排序
16、某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：（15，84，21，47，25，27，68，35，20）（15，20，21，47，25，27，68，35，84）（15，20，21，47，25，27，68，35，84）（15，20，21，25，47，27，68，35，84）所采用的排序方法是（ ）
a、直接选择排序
b、冒泡排序
c、直接插入排序
d、快速排序
17、若要从1000个元素中得到10个最小值元素，最好采用（ ）方法
a、直接选择排序
b、直接插入排序
c、二分插入排序
d、堆排序
18、若一个元素序列基本有序，则选用（ ）方法较快
a、冒泡排序
b、直接选择排序
c、堆排序
d、快速排序
19、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的
a、堆排序
b、快速排序
c、希尔排序
d、冒泡排序
20、设有以下四种排序方法，则（ ）的空间复杂度最大
a、快速排序
b、堆排序
c、希尔排序
d、冒泡排序
21、下列排序方法中，属于稳定的排序方法是（ ）
a、直接插入
b、希尔排序
c、快速排序
d、堆排序
22、下列排序算法中，（ ）在某些特殊情况可能只需一趟排序即可完成
a、冒泡排序
b、二分插入排序
c、堆排序
d、快速排序
23、一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ ）
a、希尔排序
b、快速排序
c、堆排序
d、直接插入排序
24、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（ ）
a、n-i 1
b、n
c、i
d、n-i
25、在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）趟
a、n-1
b、n
c、n/2
d、
26、在下列排序方法中，平均时间性能为o(nlogn)且空间性能最好的是（ ）
a、堆排序
b、快速排序
c、归并排序
d、基数排序
27、下面哪个（ ）可能是执行一趟快速排序能够得到的序列
a、[41，12，34，45，27] 55 [72，63]
b、[45，34，12，41] 55 [72，63，27]
c、[63，12，34，45，27] 55 [41，72]
d、[12，27，45，41] 55 [34，63，72]
28、下列排序算法中，第一趟排序结束后其最大或最小元素一定在其最终位置上的算法是( )
a、冒泡排序
b、归并排序
c、直接插入排序
d、快速排序
29、下列排序算法中,平均时间复杂度为o(nlog2n)的是( )
a、归并排序
b、直接插入排序
c、二分插入排序
d、希尔排序
期末考试
期末考试
1、算法分析的两个主要方面是（）
a、空间复杂性和时间复杂性
b、正确性和简明性
c、可读性和文档性
d、数据复杂性和程序复杂性
2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
a、必须是连续的
b、部分地址必须是连续的
c、一定是不连续的
d、连续或不连续都可以
3、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）
a、edcba
b、decba
c、dceab
d、abcde
4、判定一个循环队列qu（最多元素为m）为满队列的条件是（）
a、qu—>front= =qu—>rear
b、qu—>front！=qu—>rear
c、qu—>front= =（qu—>rear 1）%m
d、qu—>reart！=（qu—>fron 1）%m
5、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的先序遍历序列是（）
a、acbed
b、decab
c、deabc
d、cedba
6、以数据集{4，5，6，7，10，12，18}为结点权值所构造的huffman树，其带权路径长度之和是（）
a、165
b、160
c、164
d、154
7、对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )
a、2
b、3
c、4
d、5
8、假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为( )
a、n
b、n-1
c、n 1
d、n 2
9、采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ）
a、直接插入和快速排序
b、冒泡和快速排序
c、直接选择和直接插入
d、直接选择和堆排序
10、对关键码序列28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为（ ）
a、(2,5,12,16)28(60,32,72)
b、(5,16,2,12)28(60,32,72)
c、(5,16,2,12)28(32,60,72)
d、(2,5,12,16)28(32,60,72)
11、对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为（ ）
a、(19，23，56，34，78，67，88，92)
b、(23，56，78，66，88，92，19，34)
c、(19，23，34，56，67，78，88，92)
d、(19，23，67，56，34，78，92，88)
12、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的
a、快速排序
b、堆排序
c、直接选择排序
d、归并排序
13、分别以下列序列构造二叉排序树，与众不同的是（）
a、10，8，9，6，12，11，13
b、10，12，11，13，8，6，9
c、10，6，8，9，12，11，13
d、10，8，6，9，12，13，11
14、下面的二叉排序树中，是平衡二叉排序数的个数（ ）
a、1
b、2
c、3
d、4
15、对下图采用迪杰斯特拉算法求a到其他各个顶点的最短路径，得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续的其余各最短路径的目标顶点依次是（）
a、d , e, f
b、e, d, f
c、f, d, e
d、f, e, d
16、下图中的二叉树进行了（ ）线索化。
a、先序
b、中序
c、后序
d、二叉排序树
17、已知一个有向图g的邻接表（出边表）如图所示，则从v0出发的深度遍历序列是（）
a、v0,v1,v4,v6,v3,v2,v5
b、v0,v1,v2,v3,v4,v5,v6
c、v0,v3,v6,v2,v4,v5,v1
d、v0,v1,v4,v6,v2,v5,v3
18、（ ）不是下图g的拓扑序列
a、v0,v1,v2,v4,v5,v6,v3
b、v0,v1,v2,v4,v5,v3,v6
c、v0,v2,v5,v3,v1,v4,v6
d、v0,v2,v5,v1,v4,v3,v6
19、二叉树转换为森林后，得到的树有（ ）棵
a、2
b、3
c、4
d、5
20、已知模式串p=‘ababacdd'，其对应的next[]数组如下，请问？的地方应该是（）
a、0
b、1
c、2
d、3
21、链表不具备的特点是（ ）。
a、不必事先估计存储空间大小
b、可以随机访问任一结点
c、便于利用零散的存储器空间
d、插入删除不需要移动元素
22、串是一种特殊的线性表，其特殊性体现在（ ）。
a、可以顺序存储
b、可以链式存储
c、数据元素是一个字符
d、数据元素可以是多个字符
23、树最适合用来表示（）
a、有序数据元素
b、无序数据元素
c、元素之间具有分支层次关系的数据
d、元素之间具有先后次序之分的数据
24、设连通图g中的e={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(c，d)，(d，f)，(f，c)}，则从顶点a出发不能得到的一种广度优先遍历的顶点序列为（ ）。
a、acbedf
b、acebfd
c、abecfd
d、abcedf
25、对于哈希函数h(key)=key,被称为同义词的关键字是( )
a、35和41
b、23和39
c、15和44
d、25和51
26、已知某二叉树的先序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则其后序遍历的结点访问序列是( )
a、bdgcefha
b、gdbecfha
c、bdgaechf
d、gdbehfca
27、在有n个叶子结点的哈夫曼树中，其结点总数为（ ）
a、2n
b、2n 1
c、2n-1
d、不确定
28、下列排序算法中不稳定的是（ ）
a、直接选择排序
b、折半插入排序
c、冒泡排序
d、快速排序
29、有8个结点的有向完全图有（ ）条边
a、14
b、28
c、56
d、112
30、用邻接表表示图进行广度优先遍历时，通常是采用（ ）来实现算法的
a、栈
b、队列
c、二叉树
d、图
猜你喜欢
- 2022-12-05 21:48
- 2022-12-05 21:21
- 2022-12-05 21:07
- 2022-12-05 20:58
- 2022-12-05 20:28
- 2022-12-05 20:16
- 2022-12-05 20:16
- 2022-12-05 20:03
- 2022-12-05 19:31
- 2022-12-05 19:13