【题型】单选题 【题干】 下列说法中错误的是（ ）。 【选项】 A. 栈是一种非线性结构 B. 一个数据元素由一或多个数据项构成 C. 在顺序存储结构中，结点间的逻辑关系由存储单元的邻
【题型】单选题
【题干】
下列说法中错误的是（ ）。
【选项】
A.
栈是一种非线性结构
B.
一个数据元素由一或多个数据项构成
C.
在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现
D.
语句的频度就是语句的执行次数
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在树形结构中，数据元素间存在（ ）的关系。
【选项】
A.
一对一
B.
一对多
C.
多对多
D.
除同属一个集合外别无关系
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
【选项】
A.
顺序表
B.
双链表
C.
带头结点的双向循环链表
D.
单循环链表
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（ ）。
【选项】
A.
不变
B.
top=n
C.
top++
D.
top--
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（ ）。
【选项】
A.
rear=front-＞next
B.
rear=rear-＞next
C.
front=front-＞next
D.
front=rear-＞next
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ ）。
【选项】
A.
S
B.
S-＞next
C.
S-＞next==NULL
D.
!S
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
串的长度是指（ ）。
【选项】
A.
串中所含不同字母的个数
B.
串中所含字符的个数
C.
串中所含不同字符的个数
D.
串中所含非空格字符的个数
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（ ）。
【选项】
A.
b
B.
c
C.
(c)
D.
(c,d,e)
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（ ）。
【选项】
A.
gedhfbca
B.
dgebhfca
C.
abcdefgh
D.
acbfedhg
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
由树的先序遍历序列和后序遍历序列可以惟一确定一棵树
B.
二叉树不同于度为2的有序树
C.
深度为k的二叉树上最少有k个结点
D.
在结点数目相同的二叉树中，最优二叉树的路径长度最短
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中的元素A[66，65]在数组B中的位置K=（ ）。
【选项】
A.
195
B.
196
C.
197
D.
198
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵二叉树中第６层上最多有（ ）个结点。
【选项】
A.
２
B.
31
C.
32
D.
64
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由树转换而得的二叉树，根结点（ ）。
【选项】
A.
没有左子树
B.
没有右子树
C.
左右子树都有
D.
视树的形态而定
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵高为k的二叉树最少有（ ）个结点。
【选项】
A.
k-1
B.
k
C.
k+1
D.2k-1
E.2k-1
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设对下图从顶点a出发进行深度优先遍历，则（ ）是可能得到的遍历序列。
【选项】
A.
acfgdeb
B.
abcdefg
C.
acdgbef
D.
abefgcd
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
具有n个顶点的有向强连通图最少有（ ）条弧。
【选项】
A.
n-1
B.
n
C.
n(n-1)
D.
n(n-1)/2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
适用于折半查找的表的存储方式及元素排列要求为（ ）。
【选项】
A.
链接方式存储，元素无序
B.
链接方式存储，元素有序
C.
顺序方式存储，元素无序
D.
顺序方式存储，元素有序
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（ ）。
【选项】
A.
79,46,56,38,40,84
B.
84,79,56,38,40,46
C.
84,79,56,46,40,38
D.
84,56,79,40,46,38
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】m阶Ｂ树中的一个分支结点最多含（）个关键字。（ ）
【选项】
A.
m-1
B.
m
C.
[m/2]
D.
[m/2]+1
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（ ）。
【选项】
A.
2
B.
3
C.
4
D.
7
E.
8
F.
以上都不对
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
将两个各有n个元素的有序表归并成一个有序表，最少进行（ ）次比较。
【选项】
A.
n
B.
2n-1
C.
2n
D.
n-1
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一组关键字值（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
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下述文件中适合于磁带存储的是（ ）。
【选项】
A.
顺序文件
B.
索引文件
C.
散列文件
D.
多关键字文件
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
【选项】
A. 688
B.678
C.692
D.696
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
二叉树的第k层的结点数最多为
【选项】
A.2k-1
B.2K+1
C.2K-1
D. 2k-1
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为
【选项】
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
【答案】
D
【解析】
【难度】3
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。
【选项】
A.n
B.n-1
C.m
D.m-1
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。
【选项】
A.3
B.4
C.5
D.8
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是
【选项】
A.N0=N1+1
B.N0=Nl+N2
C.N0=N2+1
D.N0=2N1+l
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
链式存储结构表示的线性表也称为（ ）。
【选项】
A.链表
B.顺序表
C.双链表
D.物理表
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
线性表若采用顺序结构时，要求内存中可用存储单元的地址（ ）。
【选项】
A.一定是不连续的
B.部分地址是连续的
C.一定是连续的
D.连续不连续都可以
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列关于栈的叙述中，正确的是（ ）。
【选项】
A.栈底元素一定是最后入栈的元素
B.栈操作遵循先进后出的原则
C.栈顶元素一定是最先入栈的元素
D.以上三种说法都不对
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__________。
【选项】
A.10
B.11
C.12
D.13
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
n个结点的线索二叉树上含有的线索数为__________。
【选项】
A.0
B.n-1
C.n+1
D.2n
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
栈和队列的共同特点是( )。
【选项】
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
用链接方式存储的队列，在进行插入运算时( ).
【选项】
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ ）
【选项】
A.p->next=HL->next;HL->next=p
B.p->next=HL;HL=p
C.p->next=HL;p=HL
D.HL=p;p->next=HL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
采用开放定址法处理散列表的冲突时，其平均查找长度（ ）
【选项】
A.低于链接法处理冲突
B.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
快速排序在最坏情况下的时间复杂度为（ ）
【选项】
A.O（log2n）
B.O（nlog2n）
C.O（n）
D.O（n2）
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 （ ）
【选项】
A.11
B.35
C.19
D.53
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
所谓静态链表就是一直不发生变化的链表。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
在顺序表中，最后一个元素有一个后继。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
线性表就是链式存储的表。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
对稀疏矩阵进行压缩存储的目的是便于输入和输出。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
任意一棵二叉树中的度可以小于2。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
树形结构最适合用来表示元素之间具有分支层次关系的数据。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
当采用分块查找时，数据的组织方式为：数据分成若干块，每块内数据必须有序。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
顺序表中数据元素的存取方式为（ ）。
【选项】
A.
随机存取
B.
顺序存取
C.
索引存取
D.
连续存取
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
【选项】
A.
1和5
B.
2和4
C.
4和2
D.
5和1
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
串是一种特殊的线性表，其特殊性体现在（ ）。
【选项】
A.
可以顺序存储
B.
数据元素是一个字符
C.
可以链接存储
D.
数据元素可以是多个字符
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列不属算法特性的是（ ）。
【选项】
A.
有穷性
B.
确定性
C.
零或多个输入
D.
健壮性
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有无向图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)}。对G进行深度优先遍历，正确的遍历序列是（ ）。
【选项】
A.
a,b,e,c,d,f
B.
a,c,f,e,b,d
C.
a,e,b,c,f,d
D.
a,e,d,f,c,b
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（ ）。
【选项】
A.
4条
B.
5条
C.
6条
D.
无法确定
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
含n个顶点的有向图最多有（ ）条弧。
【选项】
A.
n
B.
n(n-1)
C.
n(n+1)
D.
n2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对二叉排序树进行（ ）遍历所得的遍历序列中，关键字值是按升序排列的。
【选项】
A.
前序
B.
中序
C.
后序
D.
层序
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
【选项】
A.
快速排序
B.
堆排序
C.
归并排序
D.
直接插入排序
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在待排元素序列基本有序的前提下，效率最高的排序方法是（ ）。
【选项】
A.
插入
B.
选择
C.
快速
D.
归并
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列排序算法中（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
【选项】
A.
快速排序
B.
shell排序
C.
堆排序
D.
冒泡排序
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（ ）次探测。
【选项】
A.
k-1
B.
k
C.
k+1
D.
k(k-1)/2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
用链接方式存储的队列，在进行插入运算时
【选项】
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下数据结构中哪一个是非线性结构？
【选项】
A.队列
B.栈
C.线性表
D.二叉树
【答案】
D
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
树最适合用来表示
【选项】
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
【答案】
C
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有( )个
【选项】
A.1
B.2
C.3
D.4
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列四种排序中（ ）的空间复杂度最大。
【选项】
A.快速排序
B.冒泡排序
C.希尔排序
D.堆
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过
【选项】
A.log2n+1
B.log2n-1
C.log2n
D.log2(n+1)
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
银行业务叫号系统采用了__________数据结构。
【选项】
A.栈
B.广义表
C.队列
D.图
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个，
【选项】
A.1
B.2
C.3
D.4
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（ ）
【选项】
A.231
B.321
C.312
D.123
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）
【选项】
A.冒泡排序
B.简单选择排序
C.希尔排序
D.直接插入排序
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。（ ）
【选项】
A.25
B.10
C.7
D.1
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）
【选项】
A.11
B.35
C.19
D.53
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对一个算法的评价，不包括如下（ ）方面的内容。
【选项】
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为 （ ）
【选项】
A.O(log2n)
B.O(1)
C.O(n2)
D.O(n)
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 （ ）
【选项】
A.25
B.10
C.7
D.1
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列说法中错误的是（ ）。
【选项】
A.
数据对象是数据的子集
B.
数据元素间关系在计算机中的映象即为数据的存储结构
C.
非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系
D.
抽象数据类型指一个数学模型及定义在该模型上的一组操作
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在长为n的顺序表中删除一个数据元素，平均需移动（ ）个数据元素。
【选项】
A.
n
B.
n-1
C.
n/2
D.
(n-1)/2
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（ ）。
【选项】
A.
front-＞next
B.
rear-＞next
C.
front==rear
D.
front!=rear
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对稀疏矩阵进行压缩存储的目的是（ ）。
【选项】
A.
便于进行矩阵运算
B.
便于输入和输出
C.
节省存储空间
D.
降低运算的时间复杂度
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（ ）。
【选项】
A.
S+66
B.
S+60
C.
S+33
D.
S+30
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
对数组一般不做插入和删除操作
B.
顺序存储的数组是一个随机存取结构
C.
空的广义表没有表头和表尾
D.
广义表的表尾可能是原子也可能是子表
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（ ）。
【选项】
A.
5个
B.
6个
C.
7个
D.
8个
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设无向图的顶点个数为n，则该图最多有（ ）条边。
【选项】
A.
n-1
B.
n(n-1)/2
C.
n(n+1)/2
D.
n2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
广义表(a,(b,(),c))的深度为（ ）。
【选项】
A.
1
B.
2
C.
3
D.
4
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
树的度与该树中结点的度的最大值相等
B.
二叉树就是度为2的有序树
C.
有5个叶子结点的二叉树中必有4个度为2的结点
D.
满二叉树一定是完全二叉树
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设图Ｇ的邻接矩阵A=，则图Ｇ中共有（ ）个顶点。
【选项】
A.
1
B.
3
C.
4
D.
9
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若查找每个元素的概率均相等，则在具有n个元素的静态查找表中采用顺序查找法查找一个记录，其平均查找长度ASL为（ ）。
【选项】
A.
(n-1)/2
B.
n/2
C.
(n+1)/2
D.
n
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下面关于m阶B树说法正确的是（ ）。①每个结点至少有两棵非空子树； ②树中每个结点至多有m-1个关键字；③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一层。
【选项】
A.
①②③
B.
②③
C.
②③④
D.
③
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下面给出的四种排序法中（ ）排序法是不稳定的排序法。
【选项】
A.
插入
B.
冒泡
C.
二路归并
D.
堆
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列关于文件的说法，错误的是（ ）。
【选项】
A.
选择文件的组织方式时应考虑外存的性质和容量
B.
不定长文件指的是总长度可变的文件
C.
对文件的操作主要是维护和检索
D.
文件的存储结构指的是文件在外存上的组织方式
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（ ）。
【选项】
A.
50
B.
25
C.
10
D.
7
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
直接插入排序在最好情况下的时间复杂度为（ ）。
【选项】
A.
O(logn)
B.
O(n)
C.
O(n*logn)
D.
O(n2)
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
外部排序是指（ ）。
【选项】
A.
在外存上进行的排序方法
B.
不需要使用内存的排序方法
C.
数据量很大，需要人工干预的排序方法
D.
排序前后数据在外存，排序时数据调入内存的排序方法
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
ISAM文件和VSAM文件属于（ ）。
【选项】
A.
索引非顺序文件
B.
索引顺序文件
C.
顺序文件
D.
散列文件
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
栈和队列的共同特点是
【选项】
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
【答案】
A
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
【选项】
A. O（1）
B.O（n）
C.O（1og2n）
D.O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
【选项】
A.5
B.6
C.7
D.8
【答案】
A
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
【选项】
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(n2)
【答案】
C
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为
【选项】
A.n
B.e
C.2n
D.2e
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在二叉排序树中插入一个结点的时间复杂度为
【选项】
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设用链表作为栈的存储结构，则退栈操作
【选项】
A.必须判别栈是否为满
B.必须判别栈是否为空
C.判别栈元素的类型
D.对栈不作任何判别
【答案】
B
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
不带头结点的单链表head为空的判定条件是
【选项】
A.head==NULL
B.head->next==NULL
C.head->next==head
D.head!=NULL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列程序段的时间复杂度为（ ）。
for(i=0;i<n;i++) x=x-2;
【选项】
A.O（2n）
B.O（n）
C.O（1）
D.O（n2）
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于单链表，在两个结点之间插入一新结点需要修改的指针共（ ）个。
【选项】
A.0
B.1
C.2
D.4
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
队列的删除操作是在（ ）进行。
【选项】
A.队首
B.队尾
C.队首前一单元
D.队尾后一单元
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
按照二叉树的定义，具有3个结点的不同形状的二叉树有__________种。
【选项】
A.3
B.4
C.5
D.6
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下数据结构中哪一个是非线性结构？( )
【选项】
A.队列
B.栈
C.线性表
D.二叉树
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
二叉树的第k层的结点数最多为( ).
【选项】
A.2k-1
B.2K+1
C.2K-1
D.2k-1
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( )
【选项】
A. O（1）
B. O（n）
C. O（1og2n）
D. O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
【选项】
A.5
B.6
C.7
D.8
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对线性表，在下列哪种情况下应当采用链表表示？（ ）
【选项】
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。（ ）
【选项】
A.值
B.函数
C.指针
D.引用
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）
【选项】
A.行号
B.列号
C.元素值
D.非零元素个数
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）
【选项】
A.O（n）
B.O（1）
C.O（log2n）
D.O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设连通图G中的边集E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）
【选项】
A.abedfc
B.acfebd
C.aebdfc
D.aedfcb
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对线性表，在下列哪种情况下应当采用链表表示 （ ）
【选项】
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行 （ ）
【选项】
A.p->next=HL->next;HL->next=p
B.p->next=HL;HL=p
C.p->next=HL;p=HL
D.HL=p;p->next=HL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 （ ）
【选项】
A.冒泡排序
B.简单选择排序
C.希尔排序
D.直接插入排序
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
采用开放定址法处理散列表的冲突时，其平均查找长度 （ ）
【选项】
A.低于链接法处理冲突
B.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是 （ ）
【选项】
A.231
B.321
C.312
D.123
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 （ ）
【选项】
A.行号
B.列号
C.元素值
D.非零元素个数
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
快速排序在最坏情况下的时间复杂度为 （ ）
【选项】
A.O(log2n)
B.O(nlog2n)
C.O(n)
D.O(n2)
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 （ ）
【选项】
A.值
B.函数
C.指针
D.引用
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
从二叉搜索树中查找一个元素时，其时间复杂度大致为 （ ）
【选项】
A.O(n)
B.O(1)
C.O(log2n)
D.O(n2)
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0= （ ）
【选项】
A.Nl+N2+……+Nm
B.l+N2+2N3+3N4+……+(m-1)Nm
C.N2+2N3+3N4+……+(m-1)Nm
D.2Nl+3N2+……+(m+1)Nm
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设连通图G中的边集E={(a，B.，(a，e)，(a，C.，(b，e)，(e，D.，(d，f)，(f，C.}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为 （ ）
【选项】
A.abedfc
B.acfebd
C.aebdfc
D.aedfcb
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？
for(x=0;x<n;++x)
for(y=0;y<n;++y)
a+=2;
【答案】
答：n2
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
【答案】
答：CDEBA CDBEA CDBAE
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=n;k++)
x++;
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。
【答案】
dabc dacb dbac dbca dcab cadb cabd cdab bdac adbc
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试将下图中的树转化为二叉树。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。
【答案】
ABCEGHFD
ABCEHGFD
ACBGHEDF
ACBHGEDF
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设给定关键字序列（68, 55, 27, 43, 58, 12），试构造平衡的二叉查找树。
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有3阶B-树如下，试画出对其依次执行下列操作后的结果。
(1)插入52；(2)删除11；(3)删除74。
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设用堆排序法对给定关键字序列（８５，６１，１５，３３，２４，９６，７６，４３）按升序进行排序，试画出初始堆。
【答案】
９６，６１，８５，４３，２４，１５，７６，３３
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。
【答案】
平均查找长度：。
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为（ ______ ）
【答案】
O(n);
【解析】
【难度】2
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
AOV网是一种（ ______ ）的图。
【答案】
有向无回路;
【解析】
【难度】2
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
通常从四个方面评价算法的质量：（ ______ ）、（ ______ ）、（ ______ ）和（ ______ ）。
【答案】
正确性;易读性;强壮性;高效率;
【解析】
【难度】2
【分数】12.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为（ ______ ），树的深度为（ ______ ），树的度为（ ______ ）。
【答案】
9;
3;
3;
【解析】
【难度】2
【分数】9.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
假定一个线性表为(12,23,74,55,63,40)，若按Key % 4的条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为（ ______ ）、（ ______ ）、（ ______ ） 和（ ______ ）。
【答案】
（12，40）;（ ）;（74）;（23，55，63）;
【解析】
【难度】3
【分数】12.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设有n个无序的记录关键字，则直接插入排序的时间复杂度为（ ______ ），快速排序的平均时间复杂度为（ ______ ）。
【答案】
O(n2);O(nlog2n);
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为（ ______ ）（设结点中的两个指针域分别为llink和rlink）。
【答案】
p->link->rlink=p->rlink;p->rlink->llink=p->llink;;
【解析】
【难度】4
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为（ ______ ）。
【答案】
3;
【解析】
【难度】3
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第（ ______ ）个元素开始进行筛选。
【答案】
n/2;
【解析】
【难度】3
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设哈夫曼树中共有99个结点，则该树中有（ ______ ）个叶子结点；若采用二叉链表作为存储结构，则该树中有（ ______ ）个空指针域。
【答案】
50;51;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储（ ______ ）个队列元素；当前实际存储（ ______ ）个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
【答案】
m-1;(R-F+M)%M;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中（ ______ ）个数据元素；删除第i个位置上的数据元素需要移动表中（ ______ ）个元素。
【答案】
n+1-i;n-i;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
有n个顶点的连通图至少有________________条边。
【答案】
n-1;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
数据结构是研究程序设计中计算机操作的 ________________以及它们之间的关系和运算的一门学科。
【答案】
对象;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
下列算法的运行结果是__________________ （栈的元素类型为char）(6分)
void main()
{ stack S;
char x=’a’,y=’b’;
initstack(S);
push(S,x); push(S,y);
printf(“%c”,x);
printf(“%c”,y);
pop(S,x); pop(S,y);
printf(“%c”,x);
printf(“%c”,y);}
【答案】
abba
【解析】
【难度】4
【分数】5.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
void AI（adjmatrrix GA,int i,int n）
{
cout<<i<<′′;
vistied（i）=true;
for（int j=0;j<n;j++）
if（GA（i）（j）! =0&& GA（i）（j）! =MaxValue&& ! visited（j））
AI（GA,j,n）;
}
该算法的功能为：
__________________________________________________________________________________________________________________________。
【答案】
从初始点vi出发深度优先搜索遍历由邻接距阵GA所表示的图
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
阅读下列算法，说明该算法的作用。
void Sqstack::push(ElemType x )
{ if ( top==MAX-1 )
cout<<＂\n 满！＂；
else { top++;
elem[top]=x;
}
} // push
【答案】
答：该算法是顺序栈类的进栈算法。
如果栈满返回“满”；否则X元素进栈。
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
有如下图所示单链表，经过output()算法处理后，
单链表发生了什么变化 ？画出处理后的单链表图示。
void Link :output()
{ p=Head->next;
while( p !=NULL)
{ cout<<＂\n data=＂<<p->data ;
p=p->next;
}
} //output
【答案】
答：该算法是将链表的数据元素输出算法。
输出结果：
a
b
c
d
【解析】
【难度】5
【分数】4.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知查找表的数据元素类型如下：
Typedef struct Rectype
{int num;
char name[8];
}Rectype;
假设查找表中有n个记录，并且是采用顺序存储
Typedef Rectype Sqlist[100];
要求：（1）写出对给定值K进行从前端开始顺序查找的算法和main函数。
（2）顺序查找算法的函数头部为“int search(Sqlist R,int n,int K) “
（3）在main函数中建立该查找表、调用顺序查找算法，并输出查找结果。
【答案】
int search(Sqlist R,int n,int K)
[int i;
for(i=0;i<n&&R[i].key!=K;i++);
return i; }
main() （5分）
{ Sqlist R ;
int n,k,i;
scanf(“%d”,&n);
for(i=0;i<n;i++) {scanf(“%d\n”,&R[i].num); gets(R[i].name); }
scanf(“%d”,&k);
i=search(R,n,k);
if(i>=n) printf(“nof found!”);
else printf(“found!”); }
【解析】
【难度】4
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】论述题
【题干】
已知哈希表地址空间为0..8，哈希函数为H（key）=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。
【答案】
哈希表及查找各关键字要比较的次数如下图所示：
【解析】
【难度】4
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知两个带头结点的单链表A和B分别表示两个集合，元素值递增有序，设计算法求出A，B的交集C，并同样以递增的形式存储。
【答案】
根据编程情况，酌情给分。
由于单链表A和B是递增有序的，可设置两个整型变量分别表示两个单链表的当前元素的位置，依次取出A与B的元素进行比较，当A的数据元素小于B的值时，将指向A的当前位置都后移；当A的数据元素大于B的值时，将指向B的当前位置都后移，否则复将A（或B）的当前元素制到C中，并同时将A与B的当前位置后移。具体算法如下：
用单链表la表示集合la，用单链表lb表示集合lb，用单链表lc表示集合lc，具体算法如下：
// 文件路径名:exam6\alg.h
template <class ElemType>
void Interaction（const LinkList<ElemType> &la, const LinkList<ElemType> &lb,
LinkList<ElemType> &lc）
// 初始条件: la和lb中数据元素递增有序
// 操作结果: lc返回la与lb表示的集合的交集，并使lc中数据元素仍递增有序
{
ElemType aItem, bItem;// la和lb中当前数据元素
int aLength = la.Length（）, bLength = lb.Length（）;// la和lb的长度
int aPosition = 1, bPosition = 1;// la和lb的当前元素序号
lc.Clear（）;// 清空lc
while （aPosition <= aLength && bPosition <= bLength ）
{// 取出la和lb中数据元素进行归并
la.GetElem（aPosition, aItem）;// 取出la中数据元素
lb.GetElem（bPosition, bItem）;// 取出lb中数据元素
if （aItem < bItem）
{// aItem插入到lc
aPosition++;// 指向la下一数据元素
}
else if （aItem > bItem）
{// lb后移
bPosition++;// 指向lb下一数据元素
}
else
{// aItem == bItem，la和lb同时后移
lc.Insert（lc.Length（） + 1, aItem）;// 插入aItem到lc
aPosition++;// 指向la下一数据元素
bPosition++;// 指向lb下一数据元素
}
}
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
画出下列树对应的二叉树，并写出其先根遍历序列。
【答案】
先根遍历序列： A B D E G F C (3分)
（图5分）
【解析】
【难度】5
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知关键字序列为：
{03, 87, 12, 61, 98, 70, 61*，97, 27, 53, 42，56，77， }
请采用 希尔(Shell)排序法对该序列作非递减排序.按5，3，1 分组， 写出下列标明的趟的结果。
初始 03 ， 87， 12 ， 61， 98 ，70， 97， 27， 53， 42， 56， 77
第一趟
第二趟
每三趟
【答案】
初 始 03 ， 87， 12 ， 61， 98， 70， 97， 27， 53， 42， 56， 77
第一趟 03， 77， 12， 53， 42， 56， 87， 27， 61， 98， 70， 97
第二趟 03， 27， 12， 53， 42， 56， 87， 70， 61， 98， 77， 97
每三趟 03, 12, 27, 42, 53, 56, 61, 70, 77, 87, 97, 98
【解析】
【难度】5
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】编程题
【题干】
编写一个算法，返回二叉查找树中的关键字最小的元素值。
【答案】
ElemType FindMax (BtreeNode *BST)
{
if (BST= =NULL)
{
cerr<<”不能在空树上查找最小值！”<<endl;
exit(1);
}
BtreeNode *t=BST;
while(t->left!=NULL)
t=t->left;
return t->data;
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】编程题
【题干】
试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如＇序列1＆序列2＇模式的字符序列。其中序列1和序列2中都不含字符＇＆＇，且序列2是序列1的逆序列。例如＇a+b＆b+a＇是属该模式的字符序列，而＇1+3＆3-1＇则不是。
【答案】
int IsReverse()//判断输入的字符串中'＆'前和'＆'后部分是否为逆串,是则返回1,否则返回0{ InitStack(s); while((e=getchar())!='＆') push(s,e); while((e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1;}//IsReverse
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。
⑴在p所指结点之前插入s所指结点； ⑵在L中最后一个结点之后插入s所指结点； ⑶删除p所指结点的直接后继； ⑷删除L中第一个结点。
【答案】
⑴q=L; while(q->next!=p)q=q->next; //q指向p的直接前驱
s->next=p;
q->next=s;
⑵q=L;
while(q->next)q=q->next;
s->next=NULL;
q->next=s;
⑶q=p->next; //q指向待删结点
p->next=q->next;
free(q);
⑷q=L->next;
L->next=q->next;
free(q);
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设a='colomn'，b='How are you!'，c='please'，试求：
⑴ StrLength(b)的返回值； ⑵ Index(a,'o',5)的返回值； ⑶ 执行StrInsert(a,3,c)后串a的值； ⑷ 执行Replace(c,'e','x')后串c的值； ⑸ 执行SubString(s,b,5,3)后串s的值。
【答案】
（1）12
（2）0
（3）’copleaselomn’
（4）’plxasx’
（5）’are’
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。
【答案】
#define MAXQSIZE 100
typedef struct{
ElemType base[MAXQSIZE];
int rear;
int length;
}Queue;
Status EnQueue(Queue &Q,ElemType e){
if(Q.length==MAXQSIZE) return ERROR;
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.base[Q.rear]=e;
Q.length++;
return OK;
}//EnQueue
Status DeQueue(Queue &Q,ElemType &e){
if(!Q.length) return ERROR;
front=(Q.rear-Q.length+1)%MAXQSIZE;
e=Q.base[head];
Q.length--;
}//DeQueue
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设单链表Ｌ如图所示：
画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。
p=L;
for(i=1;i<=3;i++){
q=(LinkList)malloc(sizeof(LNode));
q->data=i*3;
q->next=p->next;
p->next=q;
}
【答案】
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设a='data structure'，b='computer'，c='demo'，试求：
⑴ StrLength(a)的返回值； ⑵ 执行StrInsert(b,4,c)后串b的值； ⑶ Index(a,'u',10)的返回值； ⑷ 执行Replace(a,'structure',b)后串a的值； ⑸ 执行SubString(s,b,3,3)后串s的值。
【答案】
⑴14 ⑵'comdemoputer' ⑶12 ⑷'data computer' ⑸'mpu'
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。
【答案】
void partition(LinkList &L,LinkList &LC,LinkList &LN,LinkList &LO){
//L带头结点，LC为含字母字符的循环链表，LN为含数字字符的循环链表， //LO为含其他字符的循环链表
InitCL(LC);
InitCL(LN);
InitCL(LO); //对三个循环链表进行初始化 p=L->next; //p指向第一个结点
while (p){
q=p;
p=p->next; //q指向当前待处理结点，p指向剩余链表
if (q->data>=’A’ && q->data<=’Z’|| q->data>=’a’ && q->data<=’z’){
q->next=LC->next;
LC->next=q;
} //字母字符入循环链表LC
else if (q->data>=’0’ && q->data<=’9’){
q->next=LN->next;
LN->next=q;
} //数字字符入循环链表LN
else {
q->next=LO->next;
LO->next=q;
} //其他字符入循环链表LO
}//while
free(L); //释放单链表L的头结点
}//partition
void InitCL(LinkList &L){
//对循环链表进行初始化
L=(LinkList)malloc(sizeof(LNode));
if (!L) exit(OVERFLOW);
L->next=L;
}
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。
【答案】
编码：
0.02: 00100
0.03: 00101
0.05: 0011
0.08: 000
0.12: 100
0.17: 101
0.22: 01
0.31: 11
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有AOE网如下，要求：
⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间； ⑵求图中各弧代表的活动的最早开始时间和最晚开始时间； ⑶列出各条关键路径。
【答案】
关键路径１：v1→v2→v5→v7
关键路径２：v1→v3→v6→v7
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
【答案】
Status LevelOrderTraverse(Bitree T,Status (*visit)(TElemType e)){
if (!T) return OK; //空二叉树 InitQueue(Q); //初始化辅助队列 if (!visit(T->data)) return ERROR; //访问根结点 EnQueue(Q,T); //指向结点的指针入队 while (!QueueEmpty(Q)){ //若队列非空 DeQueue(Q,p); //队头指针出队 if (p->lchild){//先访问p所指结点的左孩子，再访问其右孩子
if (!visit(p->lchild->data)) return ERROR;
EnQueue(Q,p->lchild);
}//if
if (p->rchild){
if (!visit(p->rchild->data)) return ERROR;
EnQueue(Q,p->rchild);
}//if
}//while
return OK;
}//LevelOrderTraverse
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有向网如下，试用迪杰斯特拉算法求从顶点Ａ出发到其余各顶点的最短路径。
【答案】
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，则：
⑴第ｉ层上有多少个结点？ ⑵编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？ ⑶编号为ｐ的结点的双亲结点（若存在）的编号是多少？
【答案】
⑴第1层有1个结点，第i层结点数＝第i-1层结点数*k（2≤i≤H）=个 ⑵当根结点以及前面的p-1个结点的孩子都编了号之后，才开始为结点p的孩子编号。结点p的第i个孩子的编号为（１＋（ｐ－１）＊ｋ）＋ｉ。 ⑶若ｐ＝１，则为根结点，无双亲，否则可设双亲结点编号为ｓ，由⑵可知结点ｓ的孩子结点的编号范围为（ｓ－１）＊ｋ＋２～（ｓ－１）＊ｋ＋ｋ＋１，即，又由ｓ为整数，可得。
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。
【答案】
int depth(BiTree t){
if (!t) return 0;
if(t->lchild)//有左子树 if (t->rchild){ //左、右子树均有 hl=depth(t->lchild); //求左子树高度 hr=depth(t->rchild); //求右子树高度
return hl>hr?hl+1:hr+1;
}
else //只有左子树
return depth(t->lchild)+1;
else //无左子树
return depth(t->rchild)+1;
//有右子树，则返回右子树高度加1 //无右子树，即右子树高度为0，则返回1
}//depth
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设哈希函数H(key)=key%13，用公共溢出区法处理冲突，试在长度为18的散列地址空间中对关键字序列（71，28，46，14，2，20，85，58）构造哈希表，要求画出哈希表存储结构示意图，并求等概率下查找成功时的平均查找长度。
【答案】
H(71)=6 H(28)=2 H(46)=7 H(14)=1 H(2)=2 H(20)=7 H(85)=7 H(58)=6
ASL=(1+1+1+1+2+3+4+5)/8=9/4
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有关键字序列（87,43,28,91,12,62,55,26），用快速排序法进行排序，要求写出每趟排序结束时的关键字序列。
【答案】
第一趟：26,43,28,55,12,62,87,91
第二趟：12,26,28,55,43,62,87,91
第三趟：12,26,28,55,43,62,87,91
第四趟：12,26,28,43,55,62,87,91
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。
【答案】
void SelectSort(LinkList &L){
//单链表Ｌ带头结点
p=L;
while(p->next){
min=p->next; //min用以指向本趟排序中关键字值最小的结点
q=min->next;
while(q){
if LT(q->data.key,min->data.key) min=q; //q所指结点关键字值更小
q=q->next;
}//while
p=p->next;
if (min!=p) min->data←→p->data; //当前关键字值最小的记录到位
}//while
}//SelectSort
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设内存有大小为５个记录的区域可供内部排序之用，文件的关键字序列为：（18，32，56，40，23，11，8，99，58，36，21，7，4，15，19，87，73，52，82，63），要求用置换－选择排序求初始归并段。
【答案】
初始归并段１：18,23,32,40,56,58,99；
初始归并段２：7,8,11,15,19,21,36,52,63,73,82,87
初始归并段３：4
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设哈希函数H(key)=(3*key)%11，用开放定址法处理冲突，di=i*((7*key)%10+1)，i=1,2,3…。试在０～１0的散列地址空间中对关键字序列（２２，４１，５３，４６，３０，１３，０１，６７）造哈希表，并求等概率下查找成功时的平均查找长度。
【答案】
平均查找长度＝（１＋１＋１＋２＋２＋１＋６＋３）／８＝
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。
【答案】
void OutputNLT(BiTree T,KeyType x){
if (!T) return;
if (!LT(T->data.key,x)){ //根结点及右子树中所有结点的关键字值均不小于x
Output(T->rchild); //按关键字值从大到小的顺序输出右子树中所有结点 printf(T->data); //输出p所指结点 OutputNLT(T->lchild,x); //处理左子树
}
else OutputNLT(T->rchild,x);
}//OutputNLT
void Output(BiTree T){
Output(T->rchild);
printf(T->data);
Output(T->lchild);
}
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
（ ）是数据的不可分割的最小单位。
【选项】
A.
数据元素
B.
数据对象
C.
数据项
D.
数据结构
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若采用顺序映象，则数据元素在内存中占用的存储空间（ ）。
【选项】
A.
一定连续
B.
一定不连续
C.
可连续可不连续
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下属单链表优点的是（ ）。
【选项】
A.
顺序存取
B.
插入操作能在O(1)的时间复杂度上完成
C.
插入时不需移动数据元素
D.
节省存储空间
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设输入序列为ABC，输出序列为CBA，则经过的栈操作为（ ）。
【选项】
A.
push,pop,push,pop,push,pop
B.
push,push,push,pop,pop,pop
C.
push,push,pop,pop,push,pop
D.
push,pop,push,push,pop,pop
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设串s='abcdefgh'，则其子串数为（ ）。
【选项】
A.
8
B.
37
C.
36
D.
9
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（ ）。
【选项】
A.
ab
B.
cdefg
C.
abcdefg
D.
abcdefgab
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在数据结构中，数据的（ ）结构是独立于计算机的。
【选项】
A.逻辑
B.存储
C.散列
D.索引
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
不带头结点的单链表（头指针为head）为空的判定条件是（ ）。
【选项】
A.head==NULL
B.head->next==head
C.head->next==NULL
D.head!=NULL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于顺序表，访问结点和增加、删除结点的时间复杂度分别为（ ）。
【选项】
A.O(n)O(n)
B.O(1)O(n)
C.O(n) O(1)
D.O(1) O(1)
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若线性表中有n个元素，算法（ ）在单链表上实现要比在顺序表上实现效率更高。
【选项】
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换其中某两个元素的值
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S ,一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少是（ ）个。
【选项】
A.3
B.4
C.5
D.6
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
树最适合用来表示( )。
【选项】
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。( )
【选项】
A.688
B.678
C.692
D.696
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )
【选项】
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对一个算法的评价，不包括如下（ ）方面的内容。（ ）
【选项】
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）
【选项】
A.O（log2n）
B.O（1）
C.O（n2）
D.O（n）
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）
【选项】
A.Nl+N2+……+Nm
B.l+N2+2N3+3N4+……+（m-1）Nm
C.N2+2N3+3N4+……+（m-1）Nm
D.2Nl+3N2+……+（m+1）Nm
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
一棵深度为k的二叉树，最多有 ________________个结点。
【答案】
2k-1;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
广义表（a,b,c,d）的表尾是 ________________。
【答案】
（b,c,d）;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
图的存储常采用________________ 和 ________________两种方法。
【答案】
邻接矩阵;
邻接表（不分先后）;
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
下面是对二叉树进行操作的算法，其功能为__________________
Void unknown(Btree BT)
{Btree p=BT,temp;
If(p!=NULL)
{ temp=p->lchild;
p->lchild=p->rchild;
p->rchid=temp;
unknown(p->lchild);
unknown(p->rchild); }
【答案】
将二叉树中的左右子树交换
【解析】
【难度】4
【分数】5.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
void AD（Lnode* & HL）
{
Insert（HL,30）;
Insert（HL,50）;
Delete（HL,26）;
Delete（HL,55）;
}
假定调用该算法时以HL为表头指针的有序单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：
_____________________________________________________。
【答案】
（15，30，48，50）评分标准：有一处错扣4分，两处及以上错7分全扣。
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】论述题
【题干】
试列出如下图中全部可能的拓扑排序序列。
【答案】
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
【解析】
【难度】4
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。
【答案】
可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。
具体算法实现如下：
// 文件路径名:exam4\alg.h
#include "binary_sort_tree.h" // 二叉排序树类
template <class ElemType, class KeyType>
void InOrderHelp（BinTreeNode<ElemType> *r, const KeyType &key）
// 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值不小于key的元素值
{
if （r != NULL）
{ // 非空二叉排序树
InOrderHelp（r->leftChild, key）; // 遍历左子树
if（r->data < key） cout << r->data << " "; //输出根结点
else return;
InOrderHelp（r->rightChild, key）; // 遍历右子树
}
}
template <class ElemType, class KeyType>
void InOrder（const BinarySortTree<ElemType, KeyType> &t, const KeyType &key）
// 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于key的元素值
{
InOrderHelp（t.GetRoot（）, key）;
// 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题干】
下列说法中错误的是（ ）。
【选项】
A.
栈是一种非线性结构
B.
一个数据元素由一或多个数据项构成
C.
在顺序存储结构中，结点间的逻辑关系由存储单元的邻接关系来体现
D.
语句的频度就是语句的执行次数
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在树形结构中，数据元素间存在（ ）的关系。
【选项】
A.
一对一
B.
一对多
C.
多对多
D.
除同属一个集合外别无关系
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
【选项】
A.
顺序表
B.
双链表
C.
带头结点的双向循环链表
D.
单循环链表
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（ ）。
【选项】
A.
不变
B.
top=n
C.
top++
D.
top--
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（ ）。
【选项】
A.
rear=front-＞next
B.
rear=rear-＞next
C.
front=front-＞next
D.
front=rear-＞next
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（ ）。
【选项】
A.
S
B.
S-＞next
C.
S-＞next==NULL
D.
!S
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
串的长度是指（ ）。
【选项】
A.
串中所含不同字母的个数
B.
串中所含字符的个数
C.
串中所含不同字符的个数
D.
串中所含非空格字符的个数
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设广义表L=((a,()),b,(c,d,e))，则Head(Tail(Tail(L)))的值为（ ）。
【选项】
A.
b
B.
c
C.
(c)
D.
(c,d,e)
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
已知二叉树T的先序序列为abdegcfh，中序序列为dbgeachf，则T的后序序列为（ ）。
【选项】
A.
gedhfbca
B.
dgebhfca
C.
abcdefgh
D.
acbfedhg
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
由树的先序遍历序列和后序遍历序列可以惟一确定一棵树
B.
二叉树不同于度为2的有序树
C.
深度为k的二叉树上最少有k个结点
D.
在结点数目相同的二叉树中，最优二叉树的路径长度最短
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1..298]中，则A中的元素A[66，65]在数组B中的位置K=（ ）。
【选项】
A.
195
B.
196
C.
197
D.
198
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵二叉树中第６层上最多有（ ）个结点。
【选项】
A.
２
B.
31
C.
32
D.
64
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由树转换而得的二叉树，根结点（ ）。
【选项】
A.
没有左子树
B.
没有右子树
C.
左右子树都有
D.
视树的形态而定
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵高为k的二叉树最少有（ ）个结点。
【选项】
A.
k-1
B.
k
C.
k+1
D.2k-1
E.2k-1
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设对下图从顶点a出发进行深度优先遍历，则（ ）是可能得到的遍历序列。
【选项】
A.
acfgdeb
B.
abcdefg
C.
acdgbef
D.
abefgcd
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
具有n个顶点的有向强连通图最少有（ ）条弧。
【选项】
A.
n-1
B.
n
C.
n(n-1)
D.
n(n-1)/2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
适用于折半查找的表的存储方式及元素排列要求为（ ）。
【选项】
A.
链接方式存储，元素无序
B.
链接方式存储，元素有序
C.
顺序方式存储，元素无序
D.
顺序方式存储，元素有序
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一组关键字值（46,79,56,38,40,84），则用堆排序的方法建立的初始堆为（ ）。
【选项】
A.
79,46,56,38,40,84
B.
84,79,56,38,40,46
C.
84,79,56,46,40,38
D.
84,56,79,40,46,38
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】m阶Ｂ树中的一个分支结点最多含（）个关键字。（ ）
【选项】
A.
m-1
B.
m
C.
[m/2]
D.
[m/2]+1
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设哈希表地址范围为0~19，哈希函数H(key)=key%17，使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38、55的记录，则再放入关键字值为72的记录时，其存放地址应为（ ）。
【选项】
A.
2
B.
3
C.
4
D.
7
E.
8
F.
以上都不对
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
将两个各有n个元素的有序表归并成一个有序表，最少进行（ ）次比较。
【选项】
A.
n
B.
2n-1
C.
2n
D.
n-1
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一组关键字值（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
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下述文件中适合于磁带存储的是（ ）。
【选项】
A.
顺序文件
B.
索引文件
C.
散列文件
D.
多关键字文件
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
【选项】
A. 688
B.678
C.692
D.696
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
二叉树的第k层的结点数最多为
【选项】
A.2k-1
B.2K+1
C.2K-1
D. 2k-1
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为
【选项】
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
【答案】
D
【解析】
【难度】3
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。
【选项】
A.n
B.n-1
C.m
D.m-1
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。
【选项】
A.3
B.4
C.5
D.8
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是
【选项】
A.N0=N1+1
B.N0=Nl+N2
C.N0=N2+1
D.N0=2N1+l
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
链式存储结构表示的线性表也称为（ ）。
【选项】
A.链表
B.顺序表
C.双链表
D.物理表
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
线性表若采用顺序结构时，要求内存中可用存储单元的地址（ ）。
【选项】
A.一定是不连续的
B.部分地址是连续的
C.一定是连续的
D.连续不连续都可以
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列关于栈的叙述中，正确的是（ ）。
【选项】
A.栈底元素一定是最后入栈的元素
B.栈操作遵循先进后出的原则
C.栈顶元素一定是最先入栈的元素
D.以上三种说法都不对
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17，则当前尾指针的值为__________。
【选项】
A.10
B.11
C.12
D.13
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
n个结点的线索二叉树上含有的线索数为__________。
【选项】
A.0
B.n-1
C.n+1
D.2n
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
栈和队列的共同特点是( )。
【选项】
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
用链接方式存储的队列，在进行插入运算时( ).
【选项】
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ ）
【选项】
A.p->next=HL->next;HL->next=p
B.p->next=HL;HL=p
C.p->next=HL;p=HL
D.HL=p;p->next=HL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
采用开放定址法处理散列表的冲突时，其平均查找长度（ ）
【选项】
A.低于链接法处理冲突
B.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
快速排序在最坏情况下的时间复杂度为（ ）
【选项】
A.O（log2n）
B.O（nlog2n）
C.O（n）
D.O（n2）
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为 （ ）
【选项】
A.11
B.35
C.19
D.53
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
对于一个线性表，采用顺序存储方式进行插入和删除结点时效率太低，采用链式存储方式更好。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
所谓静态链表就是一直不发生变化的链表。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
在顺序表中，最后一个元素有一个后继。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
线性表就是链式存储的表。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
串是一种特殊的线性表，其特殊性体现在数据元素可以是多个字符。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
对稀疏矩阵进行压缩存储的目的是便于输入和输出。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
任意一棵二叉树中的度可以小于2。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
树形结构最适合用来表示元素之间具有分支层次关系的数据。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
当采用分块查找时，数据的组织方式为：数据分成若干块，每块内数据必须有序。（ ）
【答案】
F
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】判断题
【题干】
顺序查找法适合于存储结构为顺序存储或链式存储的线性表。（ ）
【答案】
T
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
顺序表中数据元素的存取方式为（ ）。
【选项】
A.
随机存取
B.
顺序存取
C.
索引存取
D.
连续存取
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（ ）。
【选项】
A.
1和5
B.
2和4
C.
4和2
D.
5和1
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
串是一种特殊的线性表，其特殊性体现在（ ）。
【选项】
A.
可以顺序存储
B.
数据元素是一个字符
C.
可以链接存储
D.
数据元素可以是多个字符
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列不属算法特性的是（ ）。
【选项】
A.
有穷性
B.
确定性
C.
零或多个输入
D.
健壮性
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有无向图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)}。对G进行深度优先遍历，正确的遍历序列是（ ）。
【选项】
A.
a,b,e,c,d,f
B.
a,c,f,e,b,d
C.
a,e,b,c,f,d
D.
a,e,d,f,c,b
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（ ）。
【选项】
A.
4条
B.
5条
C.
6条
D.
无法确定
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
含n个顶点的有向图最多有（ ）条弧。
【选项】
A.
n
B.
n(n-1)
C.
n(n+1)
D.
n2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对二叉排序树进行（ ）遍历所得的遍历序列中，关键字值是按升序排列的。
【选项】
A.
前序
B.
中序
C.
后序
D.
层序
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ ）。
【选项】
A.
快速排序
B.
堆排序
C.
归并排序
D.
直接插入排序
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在待排元素序列基本有序的前提下，效率最高的排序方法是（ ）。
【选项】
A.
插入
B.
选择
C.
快速
D.
归并
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列排序算法中（ ）不能保证每趟排序至少能将一个元素放到其最终的位置上。
【选项】
A.
快速排序
B.
shell排序
C.
堆排序
D.
冒泡排序
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表，至少要进行（ ）次探测。
【选项】
A.
k-1
B.
k
C.
k+1
D.
k(k-1)/2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
用链接方式存储的队列，在进行插入运算时
【选项】
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下数据结构中哪一个是非线性结构？
【选项】
A.队列
B.栈
C.线性表
D.二叉树
【答案】
D
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
树最适合用来表示
【选项】
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
【答案】
C
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有( )个
【选项】
A.1
B.2
C.3
D.4
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列四种排序中（ ）的空间复杂度最大。
【选项】
A.快速排序
B.冒泡排序
C.希尔排序
D.堆
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过
【选项】
A.log2n+1
B.log2n-1
C.log2n
D.log2(n+1)
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
银行业务叫号系统采用了__________数据结构。
【选项】
A.栈
B.广义表
C.队列
D.图
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个，
【选项】
A.1
B.2
C.3
D.4
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是（ ）
【选项】
A.231
B.321
C.312
D.123
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）
【选项】
A.冒泡排序
B.简单选择排序
C.希尔排序
D.直接插入排序
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。（ ）
【选项】
A.25
B.10
C.7
D.1
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（ ）
【选项】
A.11
B.35
C.19
D.53
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对一个算法的评价，不包括如下（ ）方面的内容。
【选项】
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为 （ ）
【选项】
A.O(log2n)
B.O(1)
C.O(n2)
D.O(n)
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（ ）次。 （ ）
【选项】
A.25
B.10
C.7
D.1
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列说法中错误的是（ ）。
【选项】
A.
数据对象是数据的子集
B.
数据元素间关系在计算机中的映象即为数据的存储结构
C.
非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系
D.
抽象数据类型指一个数学模型及定义在该模型上的一组操作
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在长为n的顺序表中删除一个数据元素，平均需移动（ ）个数据元素。
【选项】
A.
n
B.
n-1
C.
n/2
D.
(n-1)/2
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（ ）。
【选项】
A.
front-＞next
B.
rear-＞next
C.
front==rear
D.
front!=rear
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对稀疏矩阵进行压缩存储的目的是（ ）。
【选项】
A.
便于进行矩阵运算
B.
便于输入和输出
C.
节省存储空间
D.
降低运算的时间复杂度
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设二维数组A5×8按行优先顺序存储，每个数据元素占2个字节，首地址即元素A[0][0]的起始地址为S，则元素A[3][6]的起始地址为（ ）。
【选项】
A.
S+66
B.
S+60
C.
S+33
D.
S+30
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
对数组一般不做插入和删除操作
B.
顺序存储的数组是一个随机存取结构
C.
空的广义表没有表头和表尾
D.
广义表的表尾可能是原子也可能是子表
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一棵度为3的树中，度为3的结点有2个，度为2的结点有2个，度为1的结点有2个，则度为0的结点有（ ）。
【选项】
A.
5个
B.
6个
C.
7个
D.
8个
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设无向图的顶点个数为n，则该图最多有（ ）条边。
【选项】
A.
n-1
B.
n(n-1)/2
C.
n(n+1)/2
D.
n2
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
广义表(a,(b,(),c))的深度为（ ）。
【选项】
A.
1
B.
2
C.
3
D.
4
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列叙述中错误的是（ ）。
【选项】
A.
树的度与该树中结点的度的最大值相等
B.
二叉树就是度为2的有序树
C.
有5个叶子结点的二叉树中必有4个度为2的结点
D.
满二叉树一定是完全二叉树
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设图Ｇ的邻接矩阵A=，则图Ｇ中共有（ ）个顶点。
【选项】
A.
1
B.
3
C.
4
D.
9
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若查找每个元素的概率均相等，则在具有n个元素的静态查找表中采用顺序查找法查找一个记录，其平均查找长度ASL为（ ）。
【选项】
A.
(n-1)/2
B.
n/2
C.
(n+1)/2
D.
n
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下面关于m阶B树说法正确的是（ ）。①每个结点至少有两棵非空子树； ②树中每个结点至多有m-1个关键字；③所有叶子在同一层上； ④当插入一个数据项引起B树结点分裂后，树长高一层。
【选项】
A.
①②③
B.
②③
C.
②③④
D.
③
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下面给出的四种排序法中（ ）排序法是不稳定的排序法。
【选项】
A.
插入
B.
冒泡
C.
二路归并
D.
堆
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列关于文件的说法，错误的是（ ）。
【选项】
A.
选择文件的组织方式时应考虑外存的性质和容量
B.
不定长文件指的是总长度可变的文件
C.
对文件的操作主要是维护和检索
D.
文件的存储结构指的是文件在外存上的组织方式
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设表中含100个数据元素，用折半查找法进行查找，则所需最大比较次数为（ ）。
【选项】
A.
50
B.
25
C.
10
D.
7
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
直接插入排序在最好情况下的时间复杂度为（ ）。
【选项】
A.
O(logn)
B.
O(n)
C.
O(n*logn)
D.
O(n2)
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
外部排序是指（ ）。
【选项】
A.
在外存上进行的排序方法
B.
不需要使用内存的排序方法
C.
数据量很大，需要人工干预的排序方法
D.
排序前后数据在外存，排序时数据调入内存的排序方法
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
ISAM文件和VSAM文件属于（ ）。
【选项】
A.
索引非顺序文件
B.
索引顺序文件
C.
顺序文件
D.
散列文件
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
栈和队列的共同特点是
【选项】
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
【答案】
A
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为
【选项】
A. O（1）
B.O（n）
C.O（1og2n）
D.O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
【选项】
A.5
B.6
C.7
D.8
【答案】
A
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
【选项】
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(n2)
【答案】
C
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为
【选项】
A.n
B.e
C.2n
D.2e
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在二叉排序树中插入一个结点的时间复杂度为
【选项】
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设用链表作为栈的存储结构，则退栈操作
【选项】
A.必须判别栈是否为满
B.必须判别栈是否为空
C.判别栈元素的类型
D.对栈不作任何判别
【答案】
B
【解析】
【难度】1
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
不带头结点的单链表head为空的判定条件是
【选项】
A.head==NULL
B.head->next==NULL
C.head->next==head
D.head!=NULL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
下列程序段的时间复杂度为（ ）。
for(i=0;i<n;i++) x=x-2;
【选项】
A.O（2n）
B.O（n）
C.O（1）
D.O（n2）
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于单链表，在两个结点之间插入一新结点需要修改的指针共（ ）个。
【选项】
A.0
B.1
C.2
D.4
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
队列的删除操作是在（ ）进行。
【选项】
A.队首
B.队尾
C.队首前一单元
D.队尾后一单元
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
按照二叉树的定义，具有3个结点的不同形状的二叉树有__________种。
【选项】
A.3
B.4
C.5
D.6
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下数据结构中哪一个是非线性结构？( )
【选项】
A.队列
B.栈
C.线性表
D.二叉树
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
二叉树的第k层的结点数最多为( ).
【选项】
A.2k-1
B.2K+1
C.2K-1
D.2k-1
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对n个记录的文件进行快速排序，所需要的辅助存储空间大致为( )
【选项】
A. O（1）
B. O（n）
C. O（1og2n）
D. O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
【选项】
A.5
B.6
C.7
D.8
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对线性表，在下列哪种情况下应当采用链表表示？（ ）
【选项】
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。（ ）
【选项】
A.值
B.函数
C.指针
D.引用
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）
【选项】
A.行号
B.列号
C.元素值
D.非零元素个数
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）
【选项】
A.O（n）
B.O（1）
C.O（log2n）
D.O（n2）
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设连通图G中的边集E={（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f，c）}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（ ）
【选项】
A.abedfc
B.acfebd
C.aebdfc
D.aedfcb
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对线性表，在下列哪种情况下应当采用链表表示 （ ）
【选项】
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间
D.表中元素的个数不变
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行 （ ）
【选项】
A.p->next=HL->next;HL->next=p
B.p->next=HL;HL=p
C.p->next=HL;p=HL
D.HL=p;p->next=HL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是 （ ）
【选项】
A.冒泡排序
B.简单选择排序
C.希尔排序
D.直接插入排序
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
采用开放定址法处理散列表的冲突时，其平均查找长度 （ ）
【选项】
A.低于链接法处理冲突
B.高于链接法处理冲突
C.与链接法处理冲突相同
D.高于二分查找
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是 （ ）
【选项】
A.231
B.321
C.312
D.123
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的 （ ）
【选项】
A.行号
B.列号
C.元素值
D.非零元素个数
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
快速排序在最坏情况下的时间复杂度为 （ ）
【选项】
A.O(log2n)
B.O(nlog2n)
C.O(n)
D.O(n2)
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。 （ ）
【选项】
A.值
B.函数
C.指针
D.引用
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
从二叉搜索树中查找一个元素时，其时间复杂度大致为 （ ）
【选项】
A.O(n)
B.O(1)
C.O(log2n)
D.O(n2)
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0= （ ）
【选项】
A.Nl+N2+……+Nm
B.l+N2+2N3+3N4+……+(m-1)Nm
C.N2+2N3+3N4+……+(m-1)Nm
D.2Nl+3N2+……+(m+1)Nm
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设连通图G中的边集E={(a，B.，(a，e)，(a，C.，(b，e)，(e，D.，(d，f)，(f，C.}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为 （ ）
【选项】
A.abedfc
B.acfebd
C.aebdfc
D.aedfcb
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设n为正整数，则在下面的程序段中，语句“a+=2;”的频度为多少？
for(x=0;x<n;++x)
for(y=0;y<n;++y)
a+=2;
【答案】
答：n2
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
有5个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素C，D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
【答案】
答：CDEBA CDBEA CDBAE
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设ｎ为正整数，试确定如下程序段中语句“x++;”的频度。
for (i=1;i<=n;i++)
for (j=1;j<=i;j++)
for (k=1;k<=n;k++)
x++;
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设元素的入栈次序为a、b、c、d，且在入栈的过程中允许出栈，试写出所有不可能得到的出栈序列。
【答案】
dabc dacb dbac dbca dcab cadb cabd cdab bdac adbc
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有上三角矩阵(aij)n×n，将其上三角元素逐行存于数组B[m]中（m充分大），使得B[k]=aij，求用i和j表示k的下标变换公式。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设二叉树如下，试对其进行先序线索化，画出相应的先序线索二叉树存储结构示意图。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试将下图中的树转化为二叉树。
【答案】
答：
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试写出对如下无向图从顶点Ａ出发进行广度优先遍历可能得到的所有遍历序列。
【答案】
ABCEGHFD
ABCEHGFD
ACBGHEDF
ACBHGEDF
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设给定关键字序列（68, 55, 27, 43, 58, 12），试构造平衡的二叉查找树。
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有3阶B-树如下，试画出对其依次执行下列操作后的结果。
(1)插入52；(2)删除11；(3)删除74。
【答案】
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设用堆排序法对给定关键字序列（８５，６１，１５，３３，２４，９６，７６，４３）按升序进行排序，试画出初始堆。
【答案】
９６，６１，８５，４３，２４，１５，７６，３３
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
画出对长度为１７的有序表进行折半查找的判定树，并求等概率下查找成功时的平均查找长度。
【答案】
平均查找长度：。
【解析】
【难度】1
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为（ ______ ）
【答案】
O(n);
【解析】
【难度】2
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
AOV网是一种（ ______ ）的图。
【答案】
有向无回路;
【解析】
【难度】2
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
通常从四个方面评价算法的质量：（ ______ ）、（ ______ ）、（ ______ ）和（ ______ ）。
【答案】
正确性;易读性;强壮性;高效率;
【解析】
【难度】2
【分数】12.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为（ ______ ），树的深度为（ ______ ），树的度为（ ______ ）。
【答案】
9;
3;
3;
【解析】
【难度】2
【分数】9.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
假定一个线性表为(12,23,74,55,63,40)，若按Key % 4的条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为（ ______ ）、（ ______ ）、（ ______ ） 和（ ______ ）。
【答案】
（12，40）;（ ）;（74）;（23，55，63）;
【解析】
【难度】3
【分数】12.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设有n个无序的记录关键字，则直接插入排序的时间复杂度为（ ______ ），快速排序的平均时间复杂度为（ ______ ）。
【答案】
O(n2);O(nlog2n);
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为（ ______ ）（设结点中的两个指针域分别为llink和rlink）。
【答案】
p->link->rlink=p->rlink;p->rlink->llink=p->llink;;
【解析】
【难度】4
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为（ ______ ）。
【答案】
3;
【解析】
【难度】3
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第（ ______ ）个元素开始进行筛选。
【答案】
n/2;
【解析】
【难度】3
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设哈夫曼树中共有99个结点，则该树中有（ ______ ）个叶子结点；若采用二叉链表作为存储结构，则该树中有（ ______ ）个空指针域。
【答案】
50;51;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储（ ______ ）个队列元素；当前实际存储（ ______ ）个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
【答案】
m-1;(R-F+M)%M;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中（ ______ ）个数据元素；删除第i个位置上的数据元素需要移动表中（ ______ ）个元素。
【答案】
n+1-i;n-i;
【解析】
【难度】3
【分数】6.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
有n个顶点的连通图至少有________________条边。
【答案】
n-1;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
数据结构是研究程序设计中计算机操作的 ________________以及它们之间的关系和运算的一门学科。
【答案】
对象;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
下列算法的运行结果是__________________ （栈的元素类型为char）(6分)
void main()
{ stack S;
char x=’a’,y=’b’;
initstack(S);
push(S,x); push(S,y);
printf(“%c”,x);
printf(“%c”,y);
pop(S,x); pop(S,y);
printf(“%c”,x);
printf(“%c”,y);}
【答案】
abba
【解析】
【难度】4
【分数】5.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
void AI（adjmatrrix GA,int i,int n）
{
cout<<i<<′′;
vistied（i）=true;
for（int j=0;j<n;j++）
if（GA（i）（j）! =0&& GA（i）（j）! =MaxValue&& ! visited（j））
AI（GA,j,n）;
}
该算法的功能为：
__________________________________________________________________________________________________________________________。
【答案】
从初始点vi出发深度优先搜索遍历由邻接距阵GA所表示的图
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
阅读下列算法，说明该算法的作用。
void Sqstack::push(ElemType x )
{ if ( top==MAX-1 )
cout<<＂\n 满！＂；
else { top++;
elem[top]=x;
}
} // push
【答案】
答：该算法是顺序栈类的进栈算法。
如果栈满返回“满”；否则X元素进栈。
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
有如下图所示单链表，经过output()算法处理后，
单链表发生了什么变化 ？画出处理后的单链表图示。
void Link :output()
{ p=Head->next;
while( p !=NULL)
{ cout<<＂\n data=＂<<p->data ;
p=p->next;
}
} //output
【答案】
答：该算法是将链表的数据元素输出算法。
输出结果：
a
b
c
d
【解析】
【难度】5
【分数】4.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知查找表的数据元素类型如下：
Typedef struct Rectype
{int num;
char name[8];
}Rectype;
假设查找表中有n个记录，并且是采用顺序存储
Typedef Rectype Sqlist[100];
要求：（1）写出对给定值K进行从前端开始顺序查找的算法和main函数。
（2）顺序查找算法的函数头部为“int search(Sqlist R,int n,int K) “
（3）在main函数中建立该查找表、调用顺序查找算法，并输出查找结果。
【答案】
int search(Sqlist R,int n,int K)
[int i;
for(i=0;i<n&&R[i].key!=K;i++);
return i; }
main() （5分）
{ Sqlist R ;
int n,k,i;
scanf(“%d”,&n);
for(i=0;i<n;i++) {scanf(“%d\n”,&R[i].num); gets(R[i].name); }
scanf(“%d”,&k);
i=search(R,n,k);
if(i>=n) printf(“nof found!”);
else printf(“found!”); }
【解析】
【难度】4
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】论述题
【题干】
已知哈希表地址空间为0..8，哈希函数为H（key）=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。
【答案】
哈希表及查找各关键字要比较的次数如下图所示：
【解析】
【难度】4
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知两个带头结点的单链表A和B分别表示两个集合，元素值递增有序，设计算法求出A，B的交集C，并同样以递增的形式存储。
【答案】
根据编程情况，酌情给分。
由于单链表A和B是递增有序的，可设置两个整型变量分别表示两个单链表的当前元素的位置，依次取出A与B的元素进行比较，当A的数据元素小于B的值时，将指向A的当前位置都后移；当A的数据元素大于B的值时，将指向B的当前位置都后移，否则复将A（或B）的当前元素制到C中，并同时将A与B的当前位置后移。具体算法如下：
用单链表la表示集合la，用单链表lb表示集合lb，用单链表lc表示集合lc，具体算法如下：
// 文件路径名:exam6\alg.h
template <class ElemType>
void Interaction（const LinkList<ElemType> &la, const LinkList<ElemType> &lb,
LinkList<ElemType> &lc）
// 初始条件: la和lb中数据元素递增有序
// 操作结果: lc返回la与lb表示的集合的交集，并使lc中数据元素仍递增有序
{
ElemType aItem, bItem;// la和lb中当前数据元素
int aLength = la.Length（）, bLength = lb.Length（）;// la和lb的长度
int aPosition = 1, bPosition = 1;// la和lb的当前元素序号
lc.Clear（）;// 清空lc
while （aPosition <= aLength && bPosition <= bLength ）
{// 取出la和lb中数据元素进行归并
la.GetElem（aPosition, aItem）;// 取出la中数据元素
lb.GetElem（bPosition, bItem）;// 取出lb中数据元素
if （aItem < bItem）
{// aItem插入到lc
aPosition++;// 指向la下一数据元素
}
else if （aItem > bItem）
{// lb后移
bPosition++;// 指向lb下一数据元素
}
else
{// aItem == bItem，la和lb同时后移
lc.Insert（lc.Length（） + 1, aItem）;// 插入aItem到lc
aPosition++;// 指向la下一数据元素
bPosition++;// 指向lb下一数据元素
}
}
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
画出下列树对应的二叉树，并写出其先根遍历序列。
【答案】
先根遍历序列： A B D E G F C (3分)
（图5分）
【解析】
【难度】5
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
已知关键字序列为：
{03, 87, 12, 61, 98, 70, 61*，97, 27, 53, 42，56，77， }
请采用 希尔(Shell)排序法对该序列作非递减排序.按5，3，1 分组， 写出下列标明的趟的结果。
初始 03 ， 87， 12 ， 61， 98 ，70， 97， 27， 53， 42， 56， 77
第一趟
第二趟
每三趟
【答案】
初 始 03 ， 87， 12 ， 61， 98， 70， 97， 27， 53， 42， 56， 77
第一趟 03， 77， 12， 53， 42， 56， 87， 27， 61， 98， 70， 97
第二趟 03， 27， 12， 53， 42， 56， 87， 70， 61， 98， 77， 97
每三趟 03, 12, 27, 42, 53, 56, 61, 70, 77, 87, 97, 98
【解析】
【难度】5
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】编程题
【题干】
编写一个算法，返回二叉查找树中的关键字最小的元素值。
【答案】
ElemType FindMax (BtreeNode *BST)
{
if (BST= =NULL)
{
cerr<<”不能在空树上查找最小值！”<<endl;
exit(1);
}
BtreeNode *t=BST;
while(t->left!=NULL)
t=t->left;
return t->data;
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】编程题
【题干】
试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如＇序列1＆序列2＇模式的字符序列。其中序列1和序列2中都不含字符＇＆＇，且序列2是序列1的逆序列。例如＇a+b＆b+a＇是属该模式的字符序列，而＇1+3＆3-1＇则不是。
【答案】
int IsReverse()//判断输入的字符串中'＆'前和'＆'后部分是否为逆串,是则返回1,否则返回0{ InitStack(s); while((e=getchar())!='＆') push(s,e); while((e=getchar())!='@') { if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; } if(!StackEmpty(s)) return 0; return 1;}//IsReverse
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设单链表L带头结点且非空，指针变量p指向L中的一个结点，且该结点既不是L中的第一个结点，也不是L中的最后一个结点，指针变量s指向一个待插入L的新结点。试写出能完成下列操作的语句序列。
⑴在p所指结点之前插入s所指结点； ⑵在L中最后一个结点之后插入s所指结点； ⑶删除p所指结点的直接后继； ⑷删除L中第一个结点。
【答案】
⑴q=L; while(q->next!=p)q=q->next; //q指向p的直接前驱
s->next=p;
q->next=s;
⑵q=L;
while(q->next)q=q->next;
s->next=NULL;
q->next=s;
⑶q=p->next; //q指向待删结点
p->next=q->next;
free(q);
⑷q=L->next;
L->next=q->next;
free(q);
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设a='colomn'，b='How are you!'，c='please'，试求：
⑴ StrLength(b)的返回值； ⑵ Index(a,'o',5)的返回值； ⑶ 执行StrInsert(a,3,c)后串a的值； ⑷ 执行Replace(c,'e','x')后串c的值； ⑸ 执行SubString(s,b,5,3)后串s的值。
【答案】
（1）12
（2）0
（3）’copleaselomn’
（4）’plxasx’
（5）’are’
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数，试写出其入队和出队算法（在出队算法中要返回队头元素）。
【答案】
#define MAXQSIZE 100
typedef struct{
ElemType base[MAXQSIZE];
int rear;
int length;
}Queue;
Status EnQueue(Queue &Q,ElemType e){
if(Q.length==MAXQSIZE) return ERROR;
Q.rear=(Q.rear+1)%MAXQSIZE;
Q.base[Q.rear]=e;
Q.length++;
return OK;
}//EnQueue
Status DeQueue(Queue &Q,ElemType &e){
if(!Q.length) return ERROR;
front=(Q.rear-Q.length+1)%MAXQSIZE;
e=Q.base[head];
Q.length--;
}//DeQueue
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设单链表Ｌ如图所示：
画出执行如下程序段后，各指针变量及单链表Ｌ的示意图。
p=L;
for(i=1;i<=3;i++){
q=(LinkList)malloc(sizeof(LNode));
q->data=i*3;
q->next=p->next;
p->next=q;
}
【答案】
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设a='data structure'，b='computer'，c='demo'，试求：
⑴ StrLength(a)的返回值； ⑵ 执行StrInsert(b,4,c)后串b的值； ⑶ Index(a,'u',10)的返回值； ⑷ 执行Replace(a,'structure',b)后串a的值； ⑸ 执行SubString(s,b,3,3)后串s的值。
【答案】
⑴14 ⑵'comdemoputer' ⑶12 ⑷'data computer' ⑸'mpu'
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
已知单链表L中含有三类字符的数据元素，即字母字符、数字字符和其他字符，试编写算法将L分割为三个循环链表，其中每个循环链表只含一类字符。
【答案】
void partition(LinkList &L,LinkList &LC,LinkList &LN,LinkList &LO){
//L带头结点，LC为含字母字符的循环链表，LN为含数字字符的循环链表， //LO为含其他字符的循环链表
InitCL(LC);
InitCL(LN);
InitCL(LO); //对三个循环链表进行初始化 p=L->next; //p指向第一个结点
while (p){
q=p;
p=p->next; //q指向当前待处理结点，p指向剩余链表
if (q->data>=’A’ && q->data<=’Z’|| q->data>=’a’ && q->data<=’z’){
q->next=LC->next;
LC->next=q;
} //字母字符入循环链表LC
else if (q->data>=’0’ && q->data<=’9’){
q->next=LN->next;
LN->next=q;
} //数字字符入循环链表LN
else {
q->next=LO->next;
LO->next=q;
} //其他字符入循环链表LO
}//while
free(L); //释放单链表L的头结点
}//partition
void InitCL(LinkList &L){
//对循环链表进行初始化
L=(LinkList)malloc(sizeof(LNode));
if (!L) exit(OVERFLOW);
L->next=L;
}
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设用于通信的电文由8个字母组成，字母在电文中出现的频率分别为0.12、0.31、0.22、0.02、0.03、0.08、0.17、0.05。试为这8个字母设计哈夫曼编码，要求画出设计过程中所构造的哈夫曼二叉树。
【答案】
编码：
0.02: 00100
0.03: 00101
0.05: 0011
0.08: 000
0.12: 100
0.17: 101
0.22: 01
0.31: 11
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有AOE网如下，要求：
⑴求图中各顶点代表的事件的最早发生时间和最晚发生时间； ⑵求图中各弧代表的活动的最早开始时间和最晚开始时间； ⑶列出各条关键路径。
【答案】
关键路径１：v1→v2→v5→v7
关键路径２：v1→v3→v6→v7
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设二叉树以二叉链表存储，试设计算法，实现二叉树的层序遍历。
【答案】
Status LevelOrderTraverse(Bitree T,Status (*visit)(TElemType e)){
if (!T) return OK; //空二叉树 InitQueue(Q); //初始化辅助队列 if (!visit(T->data)) return ERROR; //访问根结点 EnQueue(Q,T); //指向结点的指针入队 while (!QueueEmpty(Q)){ //若队列非空 DeQueue(Q,p); //队头指针出队 if (p->lchild){//先访问p所指结点的左孩子，再访问其右孩子
if (!visit(p->lchild->data)) return ERROR;
EnQueue(Q,p->lchild);
}//if
if (p->rchild){
if (!visit(p->rchild->data)) return ERROR;
EnQueue(Q,p->rchild);
}//if
}//while
return OK;
}//LevelOrderTraverse
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有向网如下，试用迪杰斯特拉算法求从顶点Ａ出发到其余各顶点的最短路径。
【答案】
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
一棵深度为Ｈ的满ｋ叉树有如下性质：第Ｈ层上的结点都是叶子结点，其余各层上每个结点都有ｋ棵非空子树。若按层次顺序从１开始对全部结点编号，则：
⑴第ｉ层上有多少个结点？ ⑵编号为ｐ的结点的第ｉ个孩子结点（若存在）的编号是多少？ ⑶编号为ｐ的结点的双亲结点（若存在）的编号是多少？
【答案】
⑴第1层有1个结点，第i层结点数＝第i-1层结点数*k（2≤i≤H）=个 ⑵当根结点以及前面的p-1个结点的孩子都编了号之后，才开始为结点p的孩子编号。结点p的第i个孩子的编号为（１＋（ｐ－１）＊ｋ）＋ｉ。 ⑶若ｐ＝１，则为根结点，无双亲，否则可设双亲结点编号为ｓ，由⑵可知结点ｓ的孩子结点的编号范围为（ｓ－１）＊ｋ＋２～（ｓ－１）＊ｋ＋ｋ＋１，即，又由ｓ为整数，可得。
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
试设计算法，对以邻接矩阵存储的无向图进行深度优先遍历。
【答案】
int depth(BiTree t){
if (!t) return 0;
if(t->lchild)//有左子树 if (t->rchild){ //左、右子树均有 hl=depth(t->lchild); //求左子树高度 hr=depth(t->rchild); //求右子树高度
return hl>hr?hl+1:hr+1;
}
else //只有左子树
return depth(t->lchild)+1;
else //无左子树
return depth(t->rchild)+1;
//有右子树，则返回右子树高度加1 //无右子树，即右子树高度为0，则返回1
}//depth
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设哈希函数H(key)=key%13，用公共溢出区法处理冲突，试在长度为18的散列地址空间中对关键字序列（71，28，46，14，2，20，85，58）构造哈希表，要求画出哈希表存储结构示意图，并求等概率下查找成功时的平均查找长度。
【答案】
H(71)=6 H(28)=2 H(46)=7 H(14)=1 H(2)=2 H(20)=7 H(85)=7 H(58)=6
ASL=(1+1+1+1+2+3+4+5)/8=9/4
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设有关键字序列（87,43,28,91,12,62,55,26），用快速排序法进行排序，要求写出每趟排序结束时的关键字序列。
【答案】
第一趟：26,43,28,55,12,62,87,91
第二趟：12,26,28,55,43,62,87,91
第三趟：12,26,28,55,43,62,87,91
第四趟：12,26,28,43,55,62,87,91
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设以带头结点的单链表为存储结构，设计算法，实现简单选择排序。
【答案】
void SelectSort(LinkList &L){
//单链表Ｌ带头结点
p=L;
while(p->next){
min=p->next; //min用以指向本趟排序中关键字值最小的结点
q=min->next;
while(q){
if LT(q->data.key,min->data.key) min=q; //q所指结点关键字值更小
q=q->next;
}//while
p=p->next;
if (min!=p) min->data←→p->data; //当前关键字值最小的记录到位
}//while
}//SelectSort
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设内存有大小为５个记录的区域可供内部排序之用，文件的关键字序列为：（18，32，56，40，23，11，8，99，58，36，21，7，4，15，19，87，73，52，82，63），要求用置换－选择排序求初始归并段。
【答案】
初始归并段１：18,23,32,40,56,58,99；
初始归并段２：7,8,11,15,19,21,36,52,63,73,82,87
初始归并段３：4
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设哈希函数H(key)=(3*key)%11，用开放定址法处理冲突，di=i*((7*key)%10+1)，i=1,2,3…。试在０～１0的散列地址空间中对关键字序列（２２，４１，５３，４６，３０，１３，０１，６７）造哈希表，并求等概率下查找成功时的平均查找长度。
【答案】
平均查找长度＝（１＋１＋１＋２＋２＋１＋６＋３）／８＝
【解析】
【难度】1
【分数】15.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
设计递归算法，从大到小输出给定二叉排序树中所有关键字值不小于ｘ的数据元素。
【答案】
void OutputNLT(BiTree T,KeyType x){
if (!T) return;
if (!LT(T->data.key,x)){ //根结点及右子树中所有结点的关键字值均不小于x
Output(T->rchild); //按关键字值从大到小的顺序输出右子树中所有结点 printf(T->data); //输出p所指结点 OutputNLT(T->lchild,x); //处理左子树
}
else OutputNLT(T->rchild,x);
}//OutputNLT
void Output(BiTree T){
Output(T->rchild);
printf(T->data);
Output(T->lchild);
}
【解析】
【难度】1
【分数】20.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
（ ）是数据的不可分割的最小单位。
【选项】
A.
数据元素
B.
数据对象
C.
数据项
D.
数据结构
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若采用顺序映象，则数据元素在内存中占用的存储空间（ ）。
【选项】
A.
一定连续
B.
一定不连续
C.
可连续可不连续
【答案】
A
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
以下属单链表优点的是（ ）。
【选项】
A.
顺序存取
B.
插入操作能在O(1)的时间复杂度上完成
C.
插入时不需移动数据元素
D.
节省存储空间
【答案】
C
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设输入序列为ABC，输出序列为CBA，则经过的栈操作为（ ）。
【选项】
A.
push,pop,push,pop,push,pop
B.
push,push,push,pop,pop,pop
C.
push,push,pop,pop,push,pop
D.
push,pop,push,push,pop,pop
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设串s='abcdefgh'，则其子串数为（ ）。
【选项】
A.
8
B.
37
C.
36
D.
9
【答案】
B
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（ ）。
【选项】
A.
ab
B.
cdefg
C.
abcdefg
D.
abcdefgab
【答案】
D
【解析】
【难度】1
【分数】3.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
在数据结构中，数据的（ ）结构是独立于计算机的。
【选项】
A.逻辑
B.存储
C.散列
D.索引
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
不带头结点的单链表（头指针为head）为空的判定条件是（ ）。
【选项】
A.head==NULL
B.head->next==head
C.head->next==NULL
D.head!=NULL
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对于顺序表，访问结点和增加、删除结点的时间复杂度分别为（ ）。
【选项】
A.O(n)O(n)
B.O(1)O(n)
C.O(n) O(1)
D.O(1) O(1)
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若线性表中有n个元素，算法（ ）在单链表上实现要比在顺序表上实现效率更高。
【选项】
A.删除所有值为x的元素
B.在最后一个元素的后面插入一个新元素
C.顺序输出前k个元素
D.交换其中某两个元素的值
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S ,一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少是（ ）个。
【选项】
A.3
B.4
C.5
D.6
【答案】
A
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
树最适合用来表示( )。
【选项】
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。( )
【选项】
A.688
B.678
C.692
D.696
【答案】
C
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )
【选项】
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
对一个算法的评价，不包括如下（ ）方面的内容。（ ）
【选项】
A.健壮性和可读性
B.并行性
C.正确性
D.时空复杂度
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】
设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）
【选项】
A.O（log2n）
B.O（1）
C.O（n2）
D.O（n）
【答案】
D
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】单选题
【题干】设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（ ）
【选项】
A.Nl+N2+……+Nm
B.l+N2+2N3+3N4+……+（m-1）Nm
C.N2+2N3+3N4+……+（m-1）Nm
D.2Nl+3N2+……+（m+1）Nm
【答案】
B
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
一棵深度为k的二叉树，最多有 ________________个结点。
【答案】
2k-1;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
广义表（a,b,c,d）的表尾是 ________________。
【答案】
（b,c,d）;
【解析】
【难度】2
【分数】1.000
【课程结构】00537001
【关键词】Synchronization
【题型】填空题
【题干】
图的存储常采用________________ 和 ________________两种方法。
【答案】
邻接矩阵;
邻接表（不分先后）;
【解析】
【难度】2
【分数】2.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
下面是对二叉树进行操作的算法，其功能为__________________
Void unknown(Btree BT)
{Btree p=BT,temp;
If(p!=NULL)
{ temp=p->lchild;
p->lchild=p->rchild;
p->rchid=temp;
unknown(p->lchild);
unknown(p->rchild); }
【答案】
将二叉树中的左右子树交换
【解析】
【难度】4
【分数】5.000
【课程结构】00537001
【关键词】Synchronization
【题型】问答题
【题干】
void AD（Lnode* & HL）
{
Insert（HL,30）;
Insert（HL,50）;
Delete（HL,26）;
Delete（HL,55）;
}
假定调用该算法时以HL为表头指针的有序单链表中的内容为（15，26，48，55），则调用返回后该单链表中的内容为：
_____________________________________________________。
【答案】
（15，30，48，50）评分标准：有一处错扣4分，两处及以上错7分全扣。
【解析】
【难度】5
【分数】7.000
【课程结构】00537001
【关键词】Synchronization
【题型】论述题
【题干】
试列出如下图中全部可能的拓扑排序序列。
【答案】
全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364
【解析】
【难度】4
【分数】8.000
【课程结构】00537001
【关键词】Synchronization
【题型】计算题
【题干】
试写一递归算法，从大到小输出二叉排序树中所有的关键字值小于key的元素值。
【答案】
可按先遍历右子树，遍历根结点，再遍历左子树进行中序遍历，这样可实现由大到小遍历一棵二叉排序树。
具体算法实现如下：
// 文件路径名:exam4\alg.h
#include "binary_sort_tree.h" // 二叉排序树类
template <class ElemType, class KeyType>
void InOrderHelp（BinTreeNode<ElemType> *r, const KeyType &key）
// 操作结果: 从大到小输出以r为根的二叉排序树中所有的关键字值不小于key的元素值
{
if （r != NULL）
{ // 非空二叉排序树
InOrderHelp（r->leftChild, key）; // 遍历左子树
if（r->data < key） cout << r->data << " "; //输出根结点
else return;
InOrderHelp（r->rightChild, key）; // 遍历右子树
}
}
template <class ElemType, class KeyType>
void InOrder（const BinarySortTree<ElemType, KeyType> &t, const KeyType &key）
// 操作结果: 从大到小输出二叉排序树中所有的关键字值不小于key的元素值
{
InOrderHelp（t.GetRoot（）, key）;
// 调用辅助函数实现从大到小输出二叉排序树中所有的关键字值不小于key的元素值
}
【解析】
【难度】5
【分数】10.000
【课程结构】00537001
【关键词】Synchronization
