河南财大成教《数据结构》专升本课程原题及答案
1、在数据结构中，从逻辑上可以把数据结构分成（ ）。
A.线性结构和非线性结构
B.内部结构和外部结构
C.动态结构和静态结构
D.紧凑结构和非紧凑结构
答案：A
2、抽象数据类型的三个组成部分分别为（ ）。
A.数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C.数据项、数据元素和数据类型
D.数据元素、数据结构和数据类型
答案：A
3、顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的。
A.线性结构
B.非线性结构
C.存储位置
D.指针
答案：C
4、算法具有的五个重要特性是：有穷性，确定性，（ ），输入和输出。
A.可行性
B.健壮性
C.可维护性
D.可读性
答案：A
5、算法分析的两个主要方面是（ ）。
A.数据复杂性和程序复杂性
B.正确性和简明性
C.空间复杂度和时间复杂度
D.可读性和文档性
答案：C
6、以下（ ）是一个线性表。
A.由n个实数组成的集合
B. 由100个字符组成的序列
C.所有整数组成的序列
D.由100个整数组成的集合
答案：B
7、线性表若采用顺序存储结构时，要求内存中可用存储单元的地址（ ）。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续不连续都可以
答案：A
8、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。
A.8
B.63.5
C.63
D.72
答案：B
9、单链表中，增加一个头结点的目的是为了（ ）。
A.使单链表至少有一个结点
B.标识表结点中首结点的位置
C.方便运算的实现
D.说明单链表是线性表的链式存储
答案：C
10、链表不具有的特点是（ ）。
A.插入、删除不需要移动元素
B.所需空间与线性长度成正比
C.不必事先估计存储空间
D.可随机访问任一元素
答案：D
11、线性表L在（ ）情况下适用于链式结构实现。
A.需经常修改L中的结点值
B.需不断对L进行删除插入
C.L中含有大量的结点
D.L中结点结构复杂
答案：B
12、以下哪种数据结构比较适合于一元多项式的表示（ ）。
A.单链表
B.顺序表
C.树
D.图
答案：A
13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。
A.n
B.2n-1
C.2n
D.n-1
答案：A
14、单链表的存储密度（ ）。
A.大于1
B.等于1
C.小于1
D.不能确定
答案：C
15、栈操作数据的原则是（ ）。
A.先进先出
B.后进先出
C.后进后出
D.不分顺序
答案：B
16、链式栈结点为（data,link），top指向栈顶，若想摘除栈顶结点，并将删除的结点的值保存到x中，则应执行操作（ ）。
A.x=top->data; top=top->link;
B.top=top->link; x=top->link;
C.x=top; top=top->link;
D.x=top->link;
答案：A
17、栈和队列都是（ ）。
A.顺序存储的线性结构
B.链式存储的非线性结构
C.限制存取点的线性结构
D.限制存取点的非线性结构
答案：C
18、循环队列Q存储在数组A中，则入队时的操作为（ ）。
A.rear=rear+1
B.rear=(rear+1)%(m-1)
C.rear=(rear+1)%m
D. rear=(rear+1)%(m+1)
答案：D
19、设计一个表达式求值算法，采用（ ）数据结构最佳。
A.线性表的顺序存储结构
B. 队列
C.线性表的链式存储结构
D.栈
答案：D
20、栈在（ ）中有所应用。
A.递归调用
B.函数调用
C.表达式求值
D.前三个选项都有
答案：D
21、栈和队列的共同点是（ ）。
A.都是先进先出
B.都是先进后出
C.只错误!超链接引用无效。允许在端点处插入和删除元素
D.没有共同点
答案：C
22、后缀abc-*d+表达式对应的中缀表达式是（ ）。
A. (a-b)*c+d
B. a*(b-c)+d
C. (a*b)-c+d
D.(a*b)-(c+d)
答案：B
23、两个串相等的充分必要条件是（ ）。
A.两串长度相等
B.两串所包含的字符集合相等
C.两串长度相等且对应字符相等
D.两串长度相等且所包含的字符集合相等
答案：C
24、设主串的长度为m，子串的长度为n，那么KMP模式匹配算法的时间复杂度为（ ）。
A.O（m）
B.O（n）
C.O（m*n）
D.O（m+n）
答案：D
25、设赫夫曼树中有199个结点，则该赫夫曼树中有（ ）个叶子结点。
A.99
B.100
C.101
D.102
答案：B
26、给定权值的集合｛4，30，19，16，24，7｝，用这些权值构造的哈夫曼树的带权路径长度为（ ）。
A.268
B.316
C.238
D.158
答案：C
27、5个字符有如下4种编码方案，不是前缀编码的是（ ）。
A. 01，0000，0001，001，1
B.011，000，001，010，1
C.000，001，010，011，100
D. 0，100，110，1110，1100
答案：D
28、对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点的单链表中结点数为（ ）。
A. k1
B. k2
C. k1-k2
D.kl+k2
答案：B
29、下面（ ）算法适合构造一个稠密图G的最小生成树。
A.Prim算法
B.Kruskal算法
C.Floyd算法
D.Dijkstra算法
答案：A
30、下面（ ）算法适合构造一个稀疏图G的最小生成树。
A.Prim算法
B.Kruskal算法
C.Floyd算法
D.Dijkstra算法
答案：B
31、顺序查找适合于存储结构为（ ）的线性表。
A.顺序存储结构或链式存储结构
B.散列存储结构
C.索引存储结构
D.压缩存储结构
答案：A
32、适用于折半查找的表的存储方式及元素排列要求为（ ）。
A.链接方式存储，元素无序
B.链接方式存储，元素有序
C.顺序方式存储，元素无序
D.顺序方式存储，元素有序
答案：D
33、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ ）次关键字。
A.3
B.4
C.5
D.6
答案：B
34、具有12个关键字的有序表作折半查找，设每个关键字的查找概率相同，折半查找成功的平均查找长度为（ ）。
A.37/12
B.35/12
C.39/13
D.49/13
答案：A
35、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（ ）。
A.归并排序
B.冒泡排序
C.插入排序
D.选择排序
答案：C
36、对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是（ ）。
A.8
B.10
C.15
D.25
答案：B
37、折半插入排序算法的时间复杂度为（ ）。
A.O(n)
B.O(nlog2n)
C.O(n2)
D.O(n3)
答案：C
38、下列排序算法中，（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
A.希尔排序
B.快速排序
C.冒泡排序
D.堆排序
答案：A
39、对n个不同的关键字由小到大进行冒泡排序，在下列（ ）情况下比较的次数最多。
A.从小到大排列好的
B.从大到小排列好的
C.元素无序
D.元素基本有序
D.元素基本有序
答案：B
40、快速排序在下列（ ）情况下最易发挥其长处。
A.被排序的数据中含有多个相同排序码
B.被排序的数据已基本有序
C.被排序的数据完全无序
D.被排序的数据中的最大值和最小值相差悬殊
答案：C
41、下列关键字序列中，（ ）是堆。
A.16，72，31，23，94，53
B.94，23，31，72，16，53
C.16，53，23，94，31，72
D.16，23，53，31，94，72
答案：D
42、堆是一种（ ）排序。
A.插入
B.选择
C.交换
D.归并
答案：B
43、下述几种排序方法中，（ ）是不稳定的排序方法。
A.冒泡排序
B.直接插入排序
C.归并排序
D.堆排序
答案：D
第一章 绪论
一、单选题
1、在数据结构中，从逻辑上可以把数据结构分成（）。
A.线性结构和非线性结构
B.内部结构和外部结构
C.动态结构和静态结构
D.紧凑结构和非紧凑结构
答案：A
2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。
A.算法
B.关系
C.结构
D.运算
答案：B
3、抽象数据类型的三个组成部分分别为（）。
A.数据对象、数据关系和基本操作
B.数据元素、逻辑结构和存储结构
C.数据项、数据元素和数据类型
D.数据元素、数据结构和数据类型
答案：A
4、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A.存储结构
B.存储实现
C.逻辑结构
D.运算实现
答案：C
5、通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。
A.数据具有同一特点
B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
C.每个数据元素都一样
D.数据元素所包含的数据项的个数要相等
答案：B
6、以下说法正确的是（）。
A.数据元素是数据的最小单位
B.数据项是数据的基本单位
C.数据结构是带有结构的各数据项的集合
D.一些表面上很不相同的数据可以有相同的逻辑结构
答案：D
7、顺序存储结构中数据元素之间的逻辑关系是由（）表示的。
A.线性结构
B.非线性结构
C.存储位置
D.指针
答案：C
8、链式存储结构中数据元素之间的逻辑关系是由（）表示的。
A.线性结构
B.非线性结构
C.存储位置
D.指针
答案：D
9、在决定选取何种存储结构时，一般不考虑（）。
A.所用编程语言实现这种结构是否方便
B.结点个数的多少
C.对数据有哪些运算
D.各结点的值如何
答案：D
10、计算机算法指的是（）。
A.计算方法
B.调度方法
C.解决问题的有限运算序列
D.排序方法
答案：C
11、算法分析的两个主要方面是（）。
A.数据复杂性和程序复杂性
B.正确性和简明性
C.空间复杂度和时间复杂度
D.可读性和文档性
答案：C
12、算法分析的目的是（）。
A.分析算法的易懂性和文档性
B.找出数据结构的合理性
C.研究算法中的输入和输出的关系
D.分析算法的效率以求改进
答案：D
13、下列叙述中正确的是（）。
A.一个算法的空间复杂度大，则其时间复杂度也必定大
B.一个算法的空间复杂度大，则其时间复杂度必定小
C.一个算法的时间复杂度大，则其空间复杂度必定小
D.上述三种说法都不对
答案：D
14、下面算法的时间复杂度为（）。
for(i=0;i<n;i++)
for(j=0;j<m;j++)
a<i>=0;
A.O(m)
B.O(n)
C.O(n*m)
D.O(n+m)
答案：C
15、算法具有的五个重要特性是：有穷性，确定性，（），输入和输出。
A.可行性
B.健壮性
C.可维护性
D.可读性
答案：A
第二章 线性表
一、单选题1、以下（）是一个线性表。A.由n个实数组成的集合B.由100个字符组成的序列C.所有整数组成的序列D.由100个整数组成的集合答案：B
2、关于线性表的下列说法正确的是（）。A.每个元素都有一个直接前驱和一个直接后继B.线性表中至少有一个元素C.表中诸元素的排列顺序必须是由小到大或由大到小D.除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前驱和直接后继答案：D
3、关于线性表的长度，以下论述正确的是（）。A.线性表的长度必须大于0B.线性表的长度必须大于或等于0C.线性表的长度必须大于1D.线性表的长度必须大于或等于1答案：B
4、线性表中第i个元素ai的直接前驱是（）。A.ai-1B.ai+1C.aiD.a1答案：A
5、线性表是具有n个（）的有限序列。A.表元素B.字符C.数据元素D.数据项答案：C
6、线性表若采用顺序存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以答案：A
7、下述哪一条是顺序存储结构的优点（）。A.存储密度大B.插入运算方便C.删除运算方便D.方便地运用于各种逻辑结构的存储表示答案：A
8、一个顺序表所占用的存储空间大小与（）无关。A.表的长度B.数据元素的存放顺序C.数据元素的类型D.数据元素中各字段的类型答案：B
9、顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A.110B.108C.100D.120答案：B
10、在顺序表中插入一个元素的时间复杂度为（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)答案：C
11、若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（）。A.1<=i<=nB.1<=i<=n+1C.0<=i<=n-1D.0<=i<=n答案：B
12、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。A.8B.63.5C.63D.72答案：B
13、在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时须向前移动（）个元素。A.n-iB.n-i+1C.n-i-1D.i答案：A
14、单链表中，增加一个头结点的目的是为了（）。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储答案：C
15、设一个单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。A.head==0B.head->next==0C.head->next==headD.head!=0答案：A
16、链式存储的存储结构所占存储空间（）。A.分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B.只有一部分，存放结点值C.只有一部分，存储表示结点间关系的指针D.分两部分，一部分存放结点值，另一部分存放结点所占单元数答案：A
17、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以答案：D
18、链表不具有的特点是（）。A.插入、删除不需要移动元素B.所需空间与线性长度成正比C.不必事先估计存储空间D.可随机访问任一元素答案：D
19、用链表表示线性表的优点是（）。A.便于随机存取B.花费的存储空间较顺序存储少C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同答案：C
20、设线性表中有n个数据元素，则在在链式存储结构上实现顺序查找的平均时间复杂度为（）。A.O(1)B.O(log2n)C.O(n)D.O(n2)答案：C
21、判断带头结点的单链表head为空的条件是（）。A.head==NULLB.head->next==NULLC.head->next==headD.head!=NULL答案：B
22、在单链表指针为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;答案：B
23、创建一个包括n个结点的有序单链表的时间复杂度是（）。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)答案：C
24、线性表L在（）情况下适用于链式结构实现。A.需经常修改L中的结点值B.需不断对L进行删除插入C.L中含有大量的结点D.L中结点结构复杂答案：B
25、将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度采用大O形式表示应该是（）。A.O(1)B.O(n)C.O(m)D.O(m+n)答案：C
26、以下哪种数据结构比较适合于一元多项式的表示（）。A.单链表B.顺序表C.树D.图答案：A
27、用单链表存储稀疏一元多项式时，（）。A.可以只存储各个系数B.可以只存储各个指数C.系数和指数都要存储D.只能选择带头结点的单链表答案：C
28、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.nB.2n-1C.2nD.n-1答案：A
29、以下说法错误的是（）。A.求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B.顺序存储的线性表可以随机存取C.由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D.线性表的链式存储结构优于顺序存储结构答案：D
30、线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。A.O（i）B.O（1）C.O（n）D.O（i-1）答案：C
31、单链表的存储密度（）。A.大于1B.等于1C.小于1D.不能确定答案：C
第三章 栈和队列
一、单选题1、栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序答案：B
2、在做出栈运算时，应先判断栈是否（）。A.空B.满C.上溢D.下溢答案：A
3、设栈的输入序列是为1、2、3，4，则（）不可能是其出栈序列。A.1243B.2134C.1432D.4312答案：D
4、若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现（）情况。A.5，4，3，2，1B.2，1，5，4，3C.4，3，1，2，5D.2，3，5，4，1答案：C
5、一个栈的输入序列为1，2，3，……，n，若输出序列的第一个元素是n，则输出序列的第i(1<=i<=n)个元素是（）。A.不确定B.n-i+1C.iD.n-i答案：B
6、链式栈结点为（data,link），top指向栈顶，若想摘除栈顶结点，并将删除的结点的值保存到x中，则应执行操作（）。A.x=top->data;top=top->link;B.top=top->link;x=top->link;C.x=top;top=top->link;D.x=top->link;答案：A
7、向一个栈顶指针为top的链栈中插入一个p所指向的结点时，其操作步骤为（）。A.top->next=p;B.p->next=top->next;top->next=p;C.p->next=top;top=p;D.p->next=top;top=top->next;答案：C
8、若一个栈的输入序列为1，2，3，……，n，输出序列的第一个元素是i，则第j个输出元素是（）。A.i-j+1B.i-jC.j-i+1D.不确定答案：D
9、输入序列为A，B，C，输出变为C，B，A时，经过的栈操作为（）。A.push,pop,push,pop,push.popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push，pop,pop答案：B
10、（）不是栈的基本操作。A.判断栈是否为空B.将栈置为空栈C.删除栈顶元素D.删除栈底元素答案：D
11、栈和队列都是（）。A.顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构答案：C
12、为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A.队列B.栈C.线性表D.有序表答案：A
13、设队列的输入序列是为1、2、3，4，则（）可能是其出队序列。A.1243B.1234C.1432D.4312答案：B
14、设栈S和队列Q的初始状态为空，元素1，2，3，4，5和6依次进入栈S，一个元素出栈后立即进入Q，若6个元素的出队序列是2，4，3，6，5，1，则栈S的容量至少应用是（）。A.2B.3C.4D.6答案：B
15、循环队列Q存储在数组A中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)答案：D
16、最大容量为Maxsize的循环队列，队尾指针是rear,队头指针是front，则队空的条件是（）。A.(rear+1)%Maxsize==frontB.rear==frontC.rear+1==frontD.(rear-1)%Maxsize==front答案：B
17、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。A.r-fB.(f-r+n)%nC.r-f+nD.(r-f+n)%n答案：D
18、设栈S元素和队列Q的初始状态均为空，元素abcde依次通过栈S，若每个元素出栈后立即进入队列Q，且5个元素的出队顺序是bdcae，则栈S的容量至少是（）。A.6B.4C.3D.2答案：C
19、设计一个表达式求值算法，采用（）数据结构最佳。A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈答案：D
20、栈在（）中有所应用。A.递归调用B.函数调用C.表达式求值D.前三个选项都有答案：D
21、一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分答案：B
22、栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只错误!超链接引用无效。允许在端点处插入和删除元素D.没有共同点答案：C
23、若一个栈以向量V存储，初始栈顶指针top设为0，则元素x进栈的正确操作是（）。A.top++;V=x;B.V=x;top++;C.top--;V=x;D.V=x;top--;答案：B
24、表达式(a-b*d)/e的后缀表达式是（）。A.abd*-e/B.ab*d-e/C.abde*-/D.a-b*d/e答案：A
25、后缀abc-*d+表达式对应的中缀表达式是（）。A.(a-b)*c+dB.a*(b-c)+dC.(a*b)-c+dD.(a*b)-(c+d)答案：B
第四章 串和数组
一、单选题1、串是一种特殊的线性表，其特殊性体现在（）。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符答案：B
2、下面关于串的叙述中，（）是不正确的。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储答案：B
3、若串S=“software”，其非空子串的数目是（）。A.8B.37C.36D.9答案：C
4、串的长度是指（）。A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数答案：B
5、一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为（）。A.不确定B.8C.5D.6答案：C
6、假设以行序为主序存储二维数组A=array，设每个数据元素占2个存储单元，基地址为10，则LOC=（）。A.808B.818C.1010D.1020答案：B
7、设有一个10阶对称矩阵A，采用压缩存储方式，以行序为主序存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.32C.33D.40答案：C
8、二维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（）。A.数据的元素处在行和列两个关系中B.数组的元素必须从左到右顺序排列C.数组的元素之间存在次序关系D.数组是多维结构，内存是一维结构答案：D
9、广义表（a,b,(c,d))的表尾是（）。A.(c,d)B.((c,d))C.b,(c,d)D.(b,(c,d))答案：D
10、有两个串p和q，求q在p中首次出现的位置的运算称为（）。A.连接B.模式匹配C.求子串D.求串长答案：B
11、两个串相等的充分必要条件是（）。A.两串长度相等B.两串所包含的字符集合相等C.两串长度相等且对应字符相等D.两串长度相等且所包含的字符集合相等答案：C
12、设主串的长度为m，子串的长度为n，那么KMP模式匹配算法的时间复杂度为（）。A.O（m）B.O（n）C.O（m*n）D.O（m+n）答案：D
13、设主串的长度为m，子串的长度为n，那么简单的模式匹配算法的时间复杂度为（）。A.O（m）B.O（n）C.O（m*n）D.O（m+n）答案：C
第五章 树和二叉树
一、单选题1、由3个结点可以构造出（）种不同的二叉树。A.2B.3C.4D.5答案：D
2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。A.250B.500C.254D.501答案：D
3、具有2022个结点的二叉树，其深度至少为()。A.9B.10C.11D.12答案：C
4、若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）。A.9B.11C.15D.不确定答案：B
5、将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为37的双亲结点编号为（）。A.17B.18C.19D.20答案：B
6、设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。A.空或只有一个结点B.任一结点无左孩子C.任一结点无右孩子D.任一结点都无左孩子或者任一结点都无右孩子答案：D
7、已知一个二叉树的先序序列是ABCDEFG，中序序列是BDCAFEG，则后序序列是（）。A.DCBFGEAB.BCDFGEAC.BCDFEGAD.BDCFEGA答案：A
8、已知一个二叉树的先序序列是ABCDEFG，后序序列是DCBFGEA，则中序序列是（）。A.BDCAEFGB.BCDAFEGC.BDCAFEGD.BCDAFGE答案：C
9、若一棵二叉树的后序DABEC，中序序列为DEBAC，则先序序列为（）。A.ACBEDB.DECABC.DEABCD.CEDBA答案：D
10、利用二叉链表存储树，则根结点的右指针是（）。A.指向最左孩子B.指向最右孩子C.空D.非空答案：C
11、把一棵树转换为二叉树后，这棵二叉树的形态是（）。A.唯一的B.有多种C.有多种，但根结点都没有左孩子D.有多种，但根结点都没有右孩子答案：A
12、在下列存储形式中，（）不是树的存储形式。A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法答案：D
13、若森林F有15条边，25个结点，则F包含的树的个数是（）。A.8B.9C.10D.11答案：C
14、设赫夫曼树中有199个结点，则该赫夫曼树中有（）个叶子结点。A.99B.100C.101D.102答案：B
15、n(n>=2)个权值均不相同的字符构成赫夫曼树，关于该树的叙述中，错误的是（）。A.该树是一棵完全二叉树B.树中一定没有度为1的结点C.树中两个权值最小的结点一定是兄弟结点D.树中任一非叶子结点的权值一定不小于下一层任一结点的权值答案：A
16、给定权值的集合｛4，30，19，16，24，7｝，用这些权值构造的哈夫曼树的带权路径长度为（）。A.268B.316C.238D.158答案：C
17、假定用于通信的电文仅由8个字母组成，各个字母在电文中出现的频率分别为15，3，14，2，6，9，16，17,用这些权值构造的哈夫曼树的带权路径长度为（）。A.229B.157C.245D.163答案：A
18、5个字符有如下4种编码方案，不是前缀编码的是（）。A.01，0000，0001，001，1B.011，000，001，010，1C.000，001，010，011，100D.0，100，110，1110，1100答案：D
19、设赫夫曼编码的长度不超过4，若已对两个字符编码为1和01，则还最多可对（）个字符编码。A.2B.3C.4D.5答案：C
第六章 图
一、单选题1、在一个图中，所有顶点的度数之和等于图的边数的（）倍。A.1/2B.1C.2D.4答案：C
2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A.1/2B.1C.2D.4答案：B
3、具有n个顶点的有向图最多有（）条边。A.nB.n(n-1)C.n(n+1)D.n2答案：B
4、n个顶点的连通图用邻接矩阵表示时，该矩阵至少有（）个非零元素。A.nB.2(n-1)C.n/2D.n2答案：B
5、若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点，则该图一定是（）图。A.非连通B.连通C.强连通D.有向答案：B
6、用邻接表表示图进行广度优先遍历时，通常借助（）来实现算法。A.栈B.队列C.树D.图答案：B
7、用邻接表表示图进行深度优先遍历时，通常借助（）来实现算法。A.栈B.队列C.树D.图答案：A
8、深度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历答案：A
9、广度优先遍历类似于二叉树的（）。A.先序遍历B.中序遍历C.后序遍历D.层次遍历答案：D
10、对于一个有向图，若一个顶点的入度为k1、出度为k2，则对应邻接表中该顶点的单链表中结点数为（）。A.k1B.k2C.k1-k2D.kl+k2答案：B
11、无向图G=（V，E），其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，以顶点a为源点，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b答案：D
12、下面（）算法适合构造一个稠密图G的最小生成树。A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法答案：A
13、用Prim算法构造的最小生成树（）。A.肯定是唯一的B.肯定是不唯一的C.可能唯一也可能不唯一D.以上都不对答案：C
14、下面（）算法适合构造一个稀疏图G的最小生成树。A.Prim算法B.Kruskal算法C.Floyd算法D.Dijkstra算法答案：B
15、用Prim算法和Kruskal算法构造图的最小生成树，所得到的最小生成树。A.相同B.不相同C.可能相同，可能不同D.无法比较答案：C
第七章 查找
一、单选题1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。A.(n-1)/2B.n/2C.(n+1)/2D.n答案：C
2、顺序查找适合于存储结构为（）的线性表。A.顺序存储结构或链式存储结构B.散列存储结构C.索引存储结构D.压缩存储结构答案：A
3、适用于折半查找的表的存储方式及元素排列要求为（）。A.链接方式存储，元素无序B.链接方式存储，元素有序C.顺序方式存储，元素无序D.顺序方式存储，元素有序答案：D
4、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。A.20，70，30，50B.30，88，70，50C.20，50D.30，88，50答案：A
5、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。A.3B.4C.5D.6答案：B
6、折半查找过程所对应的二叉树是一棵（）。A.最小生成树B.平衡二叉树C.完全二叉树D.满二叉树答案：B
7、具有12个关键字的有序表作折半查找，设每个关键字的查找概率相同，折半查找成功的平均查找长度为（）。A.37/12B.35/12C.39/13D.49/13答案：A
8、具有12个关键字的有序表作折半查找，设每个关键字的查找概率相同，折半查找失败的平均查找长度为（）。A.37/12B.35/13C.39/14D.49/14答案：D
第八章排序
一、单选题1、从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，这种排序方法称为（）。A.归并排序B.冒泡排序C.插入排序D.选择排序答案：C
2、从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为（）。A.归并排序B.冒泡排序C.插入排序D.选择排序答案：D
3、对5个不同的数据元素进行直接插入排序，最多需要进行的比较次数是（）。A.8B.10C.15D.25答案：B
4、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）。A.归并排序B.快速排序C.直接插入排序D.简单选择排序答案：C
5、折半插入排序算法的时间复杂度为（）。A.O(n)B.O(nlog2n)C.O(n2)D.O(n3)答案：C
6、下列排序算法中，（）不能保证每趟排序至少能将一个元素放到其最终的位置上。A.希尔排序B.快速排序C.冒泡排序D.堆排序答案：A
7、希尔排序属于（）。A.插入排序B.交换排序C.选择排序D.归并排序答案：A
8、对n个不同的关键字由小到大进行冒泡排序，在下列（）情况下比较的次数最多。A.从小到大排列好的B.从大到小排列好的C.元素无序D.元素基本有序答案：B
9、对n个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数最多为（）。A.n+1B.nC.n-1D.n(n-1)/2答案：D
10、快速排序在下列（）情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊答案：C
11、对n个关键字作快速排序，在最坏情况下，算法的时间复杂度是（）。A.O(n)B.O(nlog2n)C.O(n2)D.O(n3)答案：C
12、若一组记录的排序码为（46,79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.38，40，46，56，79，84B.40，38，46，79，56，84C.40，38，46，56，79，84D.40，38，46，84，56，79答案：C
13、下列关键字序列中，（）是堆。A.16，72，31，23，94，53B.94，23，31，72，16，53C.16，53，23，94，31，72D.16，23，53，31，94，72答案：D
14、堆的形状是一棵（）。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树答案：C
15、堆是一种（）排序。A.插入B.选择C.交换D.归并答案：B
16、若一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为（）。A.79，46，56，38，40，84B.84，79，56，38，40，46C.84，79，56，46，40，38D.84，56，79，40，46，38答案：B
17、下述几种排序方法中，（）是不稳定的排序方法。A.冒泡排序B.直接插入排序C.归并排序D.堆排序答案：D
18、将关键字6，9，1，5，8，4，7依次插入到初始为空的大根堆H中，得到的H是（）。A.9，8，7，6，5，4，1B.9，8，7，5，6，1，4C.9，8，7，5，6，4，1D.9，6，7，5，8，4，1答案：B
简答练习
一、 简答题1、画出其邻接表；答案：没表
2、画出该二叉树。答案：没题
二、 填空题3、对如下无向图G，从结点V1出发，写出一个按深度优先遍历图的结点序列：（ ），按广度优先遍历图的结点序列：（ ）。
答案：V1−V2−V3−V5−V4−V6−V7−V8
4、设哈夫曼树中共有99个结点，则该树中有（ ）个叶子结点。
答：50
5、具有7个顶点的无向图至少应有（ ）条边才能确保是一个连通图。
答：6
6、设有二维数组Ａ[８]，其每个元素占2个字节，数组按行序为主序存储，第一个元素的存储地址为200，则元素A的存储地址为（ ）。
答：288
7、起泡排序算法在最好情况下的元素交换次数为（ ）。
答：0
8、设某棵完全二叉树中有100个结点，则该二叉树中有（ ）个叶子结点。
答：50
9、 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是（ ）。
答案：12,24,27,35,18,26
10、设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是（ ）。
答案：12,24,27,35,18,26
11、设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列（ ）。
答案：
1
/ \
3 2
/ \ /
5 4
/
5
12、设循环队列中数组的下标范围是0～n–1，其头尾指针分别为f和r，则其元素个数为（ ）。
答案：(r−f+n)%n
综合作业一
1、设计一个计算二叉树中所有结点值（设为整型）之和的算法。答案：在先序遍历二叉树bt的过程中，边访问结点边计算结点的和。先访问根结点，计算结点的和，遍历左子树，遍历右子树
2、试编写一个计算二叉树深度的算法，要求二叉树采用链式存储结构。答案：0|1
3、设计在无头结点单链表L的第i个元素之前插入元素的算法。答案：在无头结点链表L的第i个元素之前插入元素e
4、设计一个在二叉链表存储结构上统计二叉树中结点个数的算法。答案：0|1
页:
[1]