与逆波兰式ab+-c*d-对应的中缀表达式是（）。

A．a-b-c*d
B．-(a+b)*c-d
C．-a+b*c-d
D．(a+b)*(-c-d)

你可能感兴趣的试题

单项选择题
广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是（）。
A．链表
B．静态数组
C．动态数组
D．散列表
单项选择题
对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（）。
A．n
B．(n+1)/2
C．log₂n
D．n²
单项选择题
将一个无序序列中的元素依次插入到一棵（），并进行中序遍历，可得到一个有序序列。
A．完全二叉树
B．最小生成树
C．二叉排序树
D．最优二叉树
单项选择题
设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如图1-9所示（队列长度为3，队头元素为e）。设队列的存储空间容量为M，则队头元素的指针为（）。

A．(Q．rear+Q．len-1)
B．(Q．rear+Q．1en-1+M)％M
C．(Q．rear-Q．1en+1)
D．(Q．rear-Q．1en+1+M)％M
单项选择题
以比较为基础的排序算法在最坏情况下的计算时间下界为（）。
A．O(n)
B．O(n²)
C．O(log₂n)
D．O(nlog₂n)
单项选择题
若将某有序树丁转换为二叉树T1，则T中结点的后（根）序序列就是T1中结点的（）遍历序列。例如，如图1-8a所示的有序树转化为二叉树后如图1-8b所示。

A.先序
B.中序
C.后序
D.层序
单项选择题
已知某二叉树的中序序列为CBDAEFI，先序序列为ABCDEFI，则该二叉树的高度为（）。
A．2
B．3
C．4
D．5
单项选择题
若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）时，（）。
A．插入和删除操作的时间复杂度都为O(1)
B．插入和删除操作的时间复杂度都为O(n)
C．插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
D．插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
单项选择题
设商店有10元、5元、2元和1元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零29元：先选2张10元币，然后选择1张5元币，再选择两张2元币。以上的找零钱方法采用了（）策略。
A．分治
B．贪心
C．动态规划
D．回溯
单项选择题
对n个元素的数组进行（），其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。
A．希尔排序
B．快速排序
C．堆排序
D．选择排序
单项选择题
一个具有n(n＞0)个顶点的连通无向图至少有（）条边。
A．n+1
B．n
C．n/2
D．n-1
单项选择题
表达式“X=（A+B）×（C-D/E）”的后缀表示为（）。
A．XAB+CDE/-x=
B．XAB-C-DE/x=
C．XAB+CDE-/x=
D．NAB-CD-E/x=
单项选择题
（）不能保证求得0-1背包问题的最优解。
A．分支限界法
B．贪心算法
C．回溯法
D．动态规划策略
单项选择题
由权值为9，2，5，7的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。
A．23
B．37
C．44
D．46
单项选择题
表达式a*（b+c）-d的后缀表达式为（）。
A．abcd*+-
B．abc+*d-
C．abc*+d-
D．-+*abcd
单项选择题
栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，（）必须用栈。
A．实现函数或过程的递归调用及返回处理时
B．将一个元素序列进行逆置时
C．链表结点的申请和释放
D．可执行程序的装入和卸载
单项选择题
对于关键字序列（26，25，72，38，8，18，59），采用散列函数H（Key）=Key mod 13构造散列表（哈希表）。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则关键字59所在散列表中的地址为（）。
A．6
B．7
C．8
D．9
单项选择题
设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边），则该矩阵中的非零元素数目为（）。
A．N
B．E
C．2E
D．N+E
单项选择题
某双向链表中的结点如图1-4所示，删除t所指结点的操作为（）。

A．t-＞prior-＞next=t-＞next；t-＞next-＞prior=t-＞prior；
B．t-＞prior-＞prior=t-＞prior；t-＞next-＞next=t-＞next；
C．t-＞prior-＞next=t-＞prior；t-＞next-＞prior=t-＞next；
D．t-＞prior-＞prior=t-＞next；t-＞next-＞prior=t-＞prior；
单项选择题
若一个问题既可以用迭代方式也可以用递归方式求解，则（）方法具有更高的时空效率。
A．迭代
B．递归
C．先递归后迭代
D．先迭代后递归
单项选择题
无向图中一个顶点的度是指图中（）。
A．通过该顶点的简单路径数
B．通过该顶点的回路数
C．与该顶点相邻的顶点数
D．与该顶点连通的顶点数
单项选择题
对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（）。
A．若入栈和入队的序列相同，则出栈序列和出队序列可能相同
B．若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序
C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1:n(n≥1)
D．入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是1:n(n≥1)
单项选择题
某算法的时间复杂度表达式为T（n）=an²+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为（）。
A．O(n²)
B．O(n)
C．O(nlgn)
D．O(1)
单项选择题
设某算法的计算时间可用递推关系式T（n）=2T（n/2）+n表示，则该算法的时间复杂度为（）。
A．O(lgn)
B．O(nlgn)
C．O(n)
D．O(n²)
单项选择题
利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时，设有向图G=＜V,E＞共有n个结点，结点编号1～n，设C是G的成本邻接矩阵，D_k(i,j)即为图G中结点i到j并且不经过编号比k还大的结点的最短路径长度(D_n(i,j)即为图G中结点i到j的最短路径长度)，则求解该问题的递推关系式为（）。
A．D_k(i,j)=D_k-1(i,j)+C(i,j)
B．D_k(i,j)=minD_k-1(i,j),D_k-1(i,j)+C(i,j)
C．D_k(i,j)=D_k-1(i,k)+D_k-1(k,j)
D．D_k(i,j)=minD_k-1(i,j),D_k-1(i,k)+D_k-1(k,j)
单项选择题
给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（）个元素。
A．(n+1)/2
B．n/2
C．(n-1)/2
D．1
单项选择题
为了便于存储和处理一般树结构形式的信息，常采用孩子一兄弟表示法将其转换成二又树（左子关系表示父子，右子关系表示兄弟），与图1-3所示的树对应的二叉树是（）。

A.A
B.B
C.C
D.D
单项选择题
下面C程序段中“count++”语句执行的次数为（）。
for(int i=1；i＜=11；i*=2)
for(int j=1；j＜=I；j++)
count++；
A．15
B．16
C．31
D．32
单项选择题
在平衡二叉树中，（）。
A．任意结点的左、右子树结点数目相同
B．任意结点的左、右子树高度相同
C．任意结点的左、右子树高度之差的绝对值不大于1
D．不存在度为1的结点
单项选择题
对于二维数组a[0..4，1..5]，设每个元素占1个存储单元，且以列为主序存储，则元素a[2，2]相对于数组空间起始地址的偏移量是（）。
A．5
B．7
C．10
D．15
单项选择题
邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，（）。
A．进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关
B．进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关
C．采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)
D．采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n²)
单项选择题
对于n（n≥0）个元素构成的线性序列L，在（）时适合采用链式存储结构。
A．需要频繁修改L中元素的值
B．需要频繁地对L进行随机查找
C．需要频繁地对L进行删除和插入操作
D．要求L存储密度高
单项选择题
要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用（）来实现。
A．分治法
B．动态规划法
C．贪心法
D．回溯法
单项选择题
在（）存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。
A．顺序(Sequence)
B．链表(Link)
C．索引(Index)
D．散列(Hash)
单项选择题
（）算法策略与递归技术的联系最弱。
A．动态规划
B．贪心
C．回溯
D．分治
单项选择题
己知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key % 7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）。
A．1.5
B．1.7
C．2.0
D．2.3
单项选择题
具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（）。
A．O(n²)
B．O(e²)
C．O(n*e)
D．O(n+e)
单项选择题
利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行（）次元素间的比较。
A．4
B．5
C．6
D．7
单项选择题
分治算法设计技术（）。
A．一般由三个步骤组成：问题划分、递归求解、合并解
B．一定是用递归技术来实现
C．将问题划分为k个规模相等的子问题
D．划分代价很小而合并代价很大
单项选择题
对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，（）。
A．装填因子的值随冲突次数的增加而递减
B．装填因子越大发生冲突的可能性就越大
C．装填因子等于1时不会再发生冲突
D．装填因子低于0.5时不会发生冲突
单项选择题
表达式“（a+b）*（c-d）”的后缀表示为（）。
A．ab+cd-*
B．abcd+-*
C．ab+*cd-
D．abcd*+-
单项选择题
设L为广义表，将head（L）定义为取非空广义表的第一个元素，tail（L）定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=（x，y，z），a，（u，t，w）），则从L中取出原子项y的运算是（）。
A．head(tail(tail(L)))
B．tail(head(head(L)))
C．head(tail(head(L))
D．tail(tail(head(L)))
单项选择题
以下的算法设计方法中，（）以获取问题最优解为目标。
A．回溯法
B．分治法
C．动态规划
D．递推
单项选择题
由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为（）。
A．27
B．38
C．51
D．75
单项选择题
若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为（）。
A．O(n)
B．O(n²)
C．O(logn)
D．O(nlogn)
单项选择题
在如图1-7所示的平衡二叉树（树中任一结点的左右子树高度之差不超过1）中，结点A的右子树AR高度为h，结点B的左子树BL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加l，则该二叉树（）。

A. 以B为根的子二叉树变为不平衡
B. 以C为根的子二叉树变为不平衡
C. 以A为根的子二叉树变为不平衡
D. 仍然是平衡二叉树
单项选择题
下面关于图（网）的叙述，正确的是（）。
A．连通无向网的最小生成树中，顶点数恰好比边数多1
B．若有向图是强连通的，则其边数至少是顸点数的2倍
C．可以采用AOV网估算工程的工期
D．关键路径是AOE网中源点至汇点的最短路径
单项选择题
对n个元素的有序表A[1..n]进行二分（折半）查找（除2取商时向下取整），查找元素A[i]（1≤i≤n）时，最多与A中的（）个元素进行比较。
A．n
B．[log₂n]-1
C．n/2
D．[log₂n]+1
单项选择题
若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况下的时间复杂度为（）。
A．O(log₂n)
B．O(n)
C．O(nlog₂n)
D．O(n²)
单项选择题
若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。（）排序是稳定的。
设求解某问题的递归算法如下：
F(int n)
if (n==1)
Move(1)；
else
F(n-1)；
Move(n)；
F(n-1)；
A．归并
B．快速
C．希尔
D．堆
单项选择题
求单源点最短路径的迪杰斯特拉（Dijkstra）算法是按（）的顺序求源点到各顶点的最短路径的。
A．路径长度递减
B．路径长度递增
C．顶点编号递减
D．顶点编号递增
单项选择题
表达式“X=A+B×（C-D）/E”的后缀表示形式可以为（）（运算符优先级相同时，遵循左结合的原则）。
A．XAB+CDE/-x=
B．XA+BC-dE/x=
C．XABCd-xE/+=
D．XABCDE+x-/=
单项选择题
设某算法的计算时间表示为递推关系式T（n）=T（n-1）+n（n＞0）及T（0）=1，则该算法的时间复杂度为（）。
A．O(lgn)
B．O(nlgn)
C．O(n)
D．O(n²)
单项选择题
某一维数组中依次存放了数据元素15，23，38，47，55，62，88，95，102，123，采用折半（二分）法查找元素95时，依次与（）进行了比较。
A．62，88，95
B．62，95
C．55，88，95
D．55，95
单项选择题
在最好和最坏情况下的时间复杂度均为O（nlog₂n）且稳定的排序方法是（）。
A．基数排序
B．快速排序
C．堆排序
D．归并排序
单项选择题
在11个元素的有序表A[1..11]中进行折半查找()，查找元素A[11]时，被比较的元素的下标依次是（）。
A．5，7，9，8
B．5，9，7，8
C．6，9，7，8
D．6，9，10，8
单项选择题
若用n个权值构造一棵最优二叉树（哈夫曼树），则该二叉树的结点总数为（）。
A．2n
B．2n-1
C．2n+1
D．2n+2
单项选择题
字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替换等串的基本运算中，（）。
A．进行串的比较运算最不方便
B．进行求子串运算最不方便
C．进行串连接最不方便
D．进行串替换最不方便
单项选择题
迪杰斯特拉（Diikstra）算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了（）算法策略。
A．贪心
B．分而治之
C．动态规划
D．试探+回溯
单项选择题
与逆波兰式ab+-c*d-对应的中缀表达式是（）。
A．a-b-c*d
B．-(a+b)*c-d
C．-a+b*c-d
D．(a+b)*(-c-d)
单项选择题
在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1），那么（）时采用顺序存储更节省空间。

A.A
B.B
C.C
D.D
单项选择题
若有数组声明a[0..3，0..2，1..4]，设编译时为a分配的存储空间首地址为base_a，且每个数组元素占据一个存储单元。当元素以行为序存放（即按a[0，0，1]，a[0，0，2]，a[0，0，3]，a[0，0，4]，a[0，1，1]，a[0，1，2]，…，a[3，2，4]顺序存储）时，则数组元素a[2，2，2]在其存储空间中相对base_a的偏移量是（）。
A．8
B．12
C．33
D．48
单项选择题
某一维数组中依次存放了数据元素12，23，30，38，41，52，54，76，85，在用折半（二分）查找方法（向上取整）查找元素54时，所经历“比较”运算的数据元素依次为（）。
A．41，52，54
B．41，76，54
C．41，76，52，54
D．41，30，76，54
单项选择题
（）在其最好情况下的算法时间复杂度为O（n）。
A．插入排序
B．归并排序
C．快速排序
D．堆排序
单项选择题
用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行（）次数组元素之间的比较。
A．12，14
B．10，14
C．12，16
D．10，16
单项选择题
若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（）。
A．DEBAFC
B．DEFBCA
C．DEBCFA
D．DEBFCA
单项选择题
（）的邻接矩阵是一个对称矩阵。
A．无向图
B．AOV网
C．AOE网
D．有向图
单项选择题
表达式（a-b）*（c+5）的后缀表示是（）。
A．a b c 5+*-
B．a b-c+5*
C．a b c-*5+
D．a b-c 5+*
单项选择题
下面关于二叉排序树的叙述，错误的是（）。
A．对二叉排序树进行中序遍历，必定得到结点关键字的有序序列
B．依据关键字无序的序列建立二叉排序树，也可能构造出单支树
C．若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树结点数的差值一定不超过1
D．若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高度的值一定不超过1
单项选择题
在常用的描述二叉排序树的存储结构中，关键字值最大的结点（）。
A．左指针一定为空
B．右指针一定为空
C．左、右指针均为空
D．左、右指针均不为空
单项选择题
下面关于哈夫曼树的叙述中，正确的是（）。
A．哈夫曼树一定是完全二叉树
B．哈夫曼树一定是平衡二叉树
C．哈夫曼树中权值最小的两个结点互为兄弟结点
D．哈夫曼树中左孩子结点小于父结点，右孩子结点大于父结点
单项选择题
输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图1-5所示。若有8，1，4，2依次进入输入受限的双端队列，则得不到输出序列（）。

A．2、8、 1、4
B．1、4、8、2
C．4、2、 1、8
D．2、1、4、8
单项选择题
下面关于栈和队列的叙述，错误的是（）。
A．栈和队列都是操作受限的线性表
B．队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)
C．若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高
D．利用两个栈可以模拟一个队列的操作，反之亦可
单项选择题
拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点v_i到v_j有一条路径，则在该线性序列中，顶点v_i必然在顶点v_j之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定（）。
A．包含回路
B．是强连通图
C．是完全图
D．是有向树
单项选择题
单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是（）。
A．若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)
B．在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理
C．加入头结点后，代表链表的头指针不因为链表为空而改变
D．加入头结点后，在链表中进行查找运算的时间复杂度为O(1)
单项选择题
己知一棵度为3的树（一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值）中有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为（）。
A．10
B．9
C．8
D．7
单项选择题
用关键字序列10，20，30，40，50构造的二叉排序树（二叉查找树）为（）。

A.A
B.B
C.C
D.D
单项选择题
一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现。这句话说明算法具有（）特性。
A．有穷性
B．可行性
C．确定性
D．健壮性
单项选择题
在（）中，任意一个结点的左、右子树的高度之差的绝对值不超过1。
A．完全二叉树
B．二叉排序树
C．线索二叉树
D．最优二叉树
单项选择题
循环链表的主要优点是（）。
A．不再需要头指针了
B．已知某个结点的位置后，能很容易找到它的直接前驱结点
C．在进行删除操作后，能保证链表不断开
D．从表中任一结点出发都能遍历整个链表
单项选择题
下面关于二叉树的叙述，正确的是（）。
A．完全二叉树的高度h与其结点数n之间存在确定的关系
B．在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构
C．完全二叉树中一定不存在度为1的结点
D．完全二叉树中必定有偶数个叶子结点
单项选择题
已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为（）。
A．BCDEAF
B．ABDCEF
C．DBACEF
D．DABECF
单项选择题
下面关于查找运算及查找表的叙述，错误的是（）。
A．哈希表可以动态创建
B．二叉排序树属于动态查找表
C．二分查找要求查找表采用顺序存储结构或循环链表结构
D．顺序查找方法既适用于顺序存储结构，也适用于链表结构
单项选择题
拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，（）为图1-2所示有向图的一个拓扑序列。

A．1526374
B．1526734
C．5123764
D．5126374
单项选择题
对以下4个序列用直接插入排序方法由小到大进行排序时，元素比较次数最少的是（）。
A．89，27，35，78，41，15
B．27，35，41，16，89，70
C．15，27，46，40，64，85
D．90，80，45，38，30，25
单项选择题
由权值为29，12，15，6，23的5个叶子结点构造的哈夫曼树为 (57) ，其带权路径长度为 (58) 。

（57）处填（）。

A.A
B.B
C.C
D.D
单项选择题
以下关于快速排序算法的描述中，错误的是 (104) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (105) 时，排序效率最高(令序列的第一个元素为基准元素)。
（104）处填（）。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为O(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
单项选择题
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (70) ，在该散列表上进行等概率成功查找的平均查找长度为 (71) (为确定记录在查找表中的位置，需和给定关键字值进行比较的次数期望值称为查找算法在查找成功时的平均查找长度)。
（70）处填（）。
A．(1)
B．(2)
C．(3)
D．(4)
单项选择题
利用贪心法求解0-1背包问题时， (27) 能够确保获得最优解。用动态规划方法求解0-1背包问题时，将“用前i个物品来装容量是X的背包”的0-1背包问题记为KNAP(1，i，X)，设f_i(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W_j和p_j(j=1～n)。则依次求解f₀(X)4，f₁(X)，…，f_n(X)的过程中使用的递推关系式为 (28) 。
（27）处填（）。
A．优先选取重量最小的物品
B．优先选取效益最大的物品
C．优先选取单位重量效益最大的物品
D．没有任何准则
单项选择题
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n，1..n]，且压缩存储在B[1..k]中，则k的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[ (21) ]中。

（20）处填（）。
A．
A.A
B.B
C.C
D.D
单项选择题
求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为 (25) ；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 (26) 。
（25）处填（）。
A．T(n)=T(n-1)+1
B．T(n)=2T(n-1)
C．T(n)=2T(n-1)+1
D．T(n)=2T(n+1)+1
单项选择题
对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用 (47) ，使用分治(Divide and Conquer)策略的是 (48) 算法。
（47）处填（）。
A．希尔排序
B．直接插入排序
C．快速排序
D．堆排序
单项选择题
对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 (64) 遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，在最坏情况下的算法复杂度为 (65) 。
（64）处填（）。
A．先序
B．中序
C．后序
D．层序
单项选择题
由权值为29，12，15，6，23的5个叶子结点构造的哈夫曼树为 (57) ，其带权路径长度为 (58) 。
（58）处填（）。
A．85
B．188
C．192
D．222
单项选择题
给定一组长度为n的无序序列，将其存储在一维数组a[0…n-1]中。现采用如下方法找出其中的最大元素和最小元素：比较a[0]和a[n-1]，若a[0]较大，则将二者的值进行交换；再比较a[1]和a[n-2]，若a[1]较大，则交换二者的值；然后依次比较a[2]和a[n-3]、a[3]和a[n-4]、…，使得每一对元素中的较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小元素中在后n/2个元素中查找最大元素，从而得到整个序列的最小元素和最大元素。上述方法采用的算法设计策略是（）。
A．动态规划法
B．贪心法
C．分治法
D．回溯法
单项选择题
已知一个线性表(16，25，35，43，51，62，87，93)，采用散列函数H(Key)=Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲突(顺序地探查可用存储单元)，则构造的哈希表为 (70) ，在该散列表上进行等概率成功查找的平均查找长度为 (71) (为确定记录在查找表中的位置，需和给定关键字值进行比较的次数期望值称为查找算法在查找成功时的平均查找长度)。
（71）处填（）。
A．(5*1+2+3+6)/8
B．(5*1+2+3+6)/9
C．(8*1)/8
D．(8*1)/9
单项选择题
利用贪心法求解0-1背包问题时， (27) 能够确保获得最优解。用动态规划方法求解0-1背包问题时，将“用前i个物品来装容量是X的背包”的0-1背包问题记为KNAP(1，i，X)，设f_i(X)是KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为W_j和p_j(j=1～n)。则依次求解f₀(X)4，f₁(X)，…，f_n(X)的过程中使用的递推关系式为 (28) 。
（28）处填（）。
A．fi(X)=min{fi-1(X)，fi-1(X)+pi}
B．fi(X)=max{fi-1(X)，fi-1(X-Wi)+pi}
C．fi(X)=min{fi-1(X-Wi)，fi-1(X-Wi)+pi}
D．f_i(X)=max{f_i-1(X-W_i)，f_i-1(X)+p_i
单项选择题
以下关于快速排序算法的描述中，错误的是 (104) 。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素(12，25，30，45，52，67，85)构成，则初始排列为 (105) 时，排序效率最高(令序列的第一个元素为基准元素)。
（105）处填（）。
A．45，12，30，25，67，52，85
B．85，67，52，45，30，25，12
C．12，25，30，45，52，67，85
D．45，12，25，30，85，67，52
单项选择题
求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为 (25) ；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 (26) 。
（26）处填（）。
A．14k
B．15k
C．16k
D．17k
单项选择题
简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1..n，1..n]，且压缩存储在B[1..k]中，则k的值至少为 (20) 。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[ (21) ]中。
（21）处填（）。
A．18
B．19
C．20
D．21
单项选择题
对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行 (64) 遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，在最坏情况下的算法复杂度为 (65) 。
（65）处填（）。
A．O(n²)
B．O(nlog₂n)
C．O(log₂n)
D．O(n)
单项选择题
为了在状态空间树中 (11) ，可以利用LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该 (12) 。
（11）处填（）。
A．找出任一个答案结点
B．找出所有的答案结点
C．找出最优的答案结点
D．进行遍历
单项选择题
对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用 (47) ，使用分治(Divide and Conquer)策略的是 (48) 算法。
（48）处填（）。
A．冒泡排序
B．插入排序
C．快速排序
D．堆排序
单项选择题
某算法的时间复杂度可用递归式表示，若用表示，则正确的是（）。

A.A
B.B
C.C
D.D
单项选择题
某工程计划如图1-6所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是 (52) 天，作业J最迟应在第 (53) 天开工。

（52）处填（）。
A．11
B．13
C．14
D．16
单项选择题
设栈S和队列Q的初始状态为空，元素按照a，b，c，d，e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c，d，b，a，e，则元素的出栈顺序是 (61) ，栈S的容量至少为 (62) 。
（61）处填（）。
A．a，b，c，d，e
B．e，d，c，b，a
C．c，d，b，a，e
D．e，a，b，d，c
单项选择题
一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (80) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (81) 。
（80）处填（）。
A．m+2
B．m+1
C．m
D．m-1
单项选择题
为了在状态空间树中 (11) ，可以利用LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该 (12) 。
（12）处填（）。
A．使用精确的成本函数c(.)来做LC-检索
B．使用广度优先检索
C．使用深度优先检索
D．在成本估计函数中考虑根结点到当前结点的成本(距离)
单项选择题
某工程计划如图1-6所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是 (52) 天，作业J最迟应在第 (53) 天开工。

（53）处填（）。
A．11
B．13
C．14
D．16
单项选择题
设栈S和队列Q的初始状态为空，元素按照a，b，c，d，e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c，d，b，a，e，则元素的出栈顺序是 (61) ，栈S的容量至少为 (62) 。
（62）处填（）。
A．2
B．3
C．4
D．5
单项选择题
斐波那契(Fibonacci)数列可以递归地定义为：

用递归算法求解F(6)时需要执行 (61) 次“+”运算，该方法采用的算法策略是 (62) 。
（61）处填（）。
A．6
B．7
C．12
D．13
单项选择题
已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97) 。对于任意一棵二叉树，叙述错误的是 (98) 。
（97）处填（）。
A．②、③、①、⑤、④
B．①、②、③、④、⑤
C．②、④、⑤、③、①
D．④、⑤、③、②、①
单项选择题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用 (35) 策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n²)的正确算法。串＜1，0，0，1，0，1，0，1＞和＜0，1，0，1，1，0，1，1＞的最长公共子序列的长度为 (36) 。
（35）处填（）。
A．分治
B．贪心
C．动态规划
D．分支限界
单项选择题
一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (80) 个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (81) 。
（81）处填（）。
A．s-＞right指向的结点一定是s所指结点的直接后继结点
B．s-＞left指向的结点一定是s所指结点的直接前驱结点
C．从s所指结点出发的right链可能构成环
D．s所指结点的left和right指针一定指向不同的结点
单项选择题
结点数目为n的二叉查找树(二叉排序树)的最小高度为 (40) ，最大高度为 (41) 。
（40）处填（）。
A．n
B．n/2
C．[log₂n]
D．
单项选择题
MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（53）处填（）。
A．电视图像和伴音信息的通用编码
B．高数据速率数字存储媒体的电视图像和伴音编码
C．一套多媒体内容描述符接口标准
D．一套多媒体通信标准
单项选择题
设下三角矩阵（上三角部分的元素值都为0）A[0..n，0..n]如图1-10所示，将该三角矩阵的所有非零元素（即行下标不小于列下标的元素）按行优先压缩存储在容量足够大的数组M[]中（下标从1开始），则元素A[i，j]（0≤i≤n，j≤i）存储在数组M的（）中。

A.A
B.B
C.C
D.D
单项选择题
斐波那契(Fibonacci)数列可以递归地定义为：

用递归算法求解F(6)时需要执行 (61) 次“+”运算，该方法采用的算法策略是 (62) 。
（62）处填（）。
A．动态规划
B．分治
C．回溯
D．分支限界
单项选择题
设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。
（73）处填（）。
A．E²
B．N²
C．N²-E²
D．N²+E²
单项选择题
关于编码有下述说法：
①对字符集进行编码时，如果字符集中任一字符的编码都是其它字符的编码的前缀，则称这种编码称为前缀编码。
②对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的后缀，这种编码称为后缀编码。
⑧不存在既是前缀编码又是后缀编码的编码。
④哈夫曼编码属于前缀编码。
⑤哈夫曼编码属于后缀编码。
⑥哈夫曼编码对应的哈夫曼树是正则二叉树。其中正确的是（）。
A．①③④⑥
B．②④⑥
C．②③④⑥
D．①④⑥
单项选择题
对于求取两个长度为n的字符串的最长公共子序列(LCS)问题，利用 (35) 策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为O(n²)的正确算法。串＜1，0，0，1，0，1，0，1＞和＜0，1，0，1，1，0，1，1＞的最长公共子序列的长度为 (36) 。
（36）处填（）。
A．3
B．4
C．5
D．6
单项选择题
已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97) 。对于任意一棵二叉树，叙述错误的是 (98) 。
（98）处填（）。
A．由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列
B．由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列
C．由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列
D．由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列
单项选择题
MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（54）处填（）。
A．对象基表达
B．场景描述
C．合成编码
D．描述符接口
单项选择题
结点数目为n的二叉查找树(二叉排序树)的最小高度为 (40) ，最大高度为 (41) 。
（41）处填（）。
A．n
B．n/2
C．[log₂n]
D．
单项选择题
设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。
（74）处填（）。
A．N
B．N+E
C．E
D．N-E
单项选择题
MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（55）处填（）。
A．非可分等级编码模式和可分等级编码模式
B．合成数据对象和自然数据对象
C．传输关系和媒体关系
D．具有特殊品质服务(QoS)的信道和面向每个基本流的带宽

与逆波兰式ab+-c*d-对应的中缀表达式是（）。

你可能感兴趣的试题

广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是（）。

对n个元素的有序表A[1..n]进行顺序查找，其成功查找的平均查找长度（即在查找表中找到指定关键码的元素时，所进行比较的表中元素个数的期望值）为（）。

将一个无序序列中的元素依次插入到一棵（），并进行中序遍历，可得到一个有序序列。

设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如图1-9所示（队列长度为3，队头元素为e）。设队列的存储空间容量为M，则队头元素的指针为（）。

以比较为基础的排序算法在最坏情况下的计算时间下界为（）。

若将某有序树丁转换为二叉树T1，则T中结点的后（根）序序列就是T1中结点的（）遍历序列。例如，如图1-8a所示的有序树转化为二叉树后如图1-8b所示。

已知某二叉树的中序序列为CBDAEFI，先序序列为ABCDEFI，则该二叉树的高度为（）。

若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表（不含头结点）时，（）。

设商店有10元、5元、2元和1元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零29元：先选2张10元币，然后选择1张5元币，再选择两张2元币。以上的找零钱方法采用了（）策略。

对n个元素的数组进行（），其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。

一个具有n(n＞0)个顶点的连通无向图至少有（）条边。

表达式“X=（A+B）×（C-D/E）”的后缀表示为（）。

（）不能保证求得0-1背包问题的最优解。

由权值为9，2，5，7的4个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（）。

表达式a*（b+c）-d的后缀表达式为（）。

栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此，（）必须用栈。

对于关键字序列（26，25，72，38，8，18，59），采用散列函数H（Key）=Key mod 13构造散列表（哈希表）。若采用线性探测的开放定址法解决冲突（顺序地探查可用存储单元），则关键字59所在散列表中的地址为（）。

设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构（矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无边），则该矩阵中的非零元素数目为（）。

某双向链表中的结点如图1-4所示，删除t所指结点的操作为（）。

若一个问题既可以用迭代方式也可以用递归方式求解，则（）方法具有更高的时空效率。

无向图中一个顶点的度是指图中（）。

对于长度为m(m＞1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（）。

某算法的时间复杂度表达式为T（n）=an2+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为（）。

设某算法的计算时间可用递推关系式T（n）=2T（n/2）+n表示，则该算法的时间复杂度为（）。

给定一个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（）个元素。

为了便于存储和处理一般树结构形式的信息，常采用孩子一兄弟表示法将其转换成二又树（左子关系表示父子，右子关系表示兄弟），与图1-3所示的树对应的二叉树是（）。

下面C程序段中“count++”语句执行的次数为（）。 for(int i=1；i＜=11；i*=2) for(int j=1；j＜=I；j++) count++；

在平衡二叉树中，（）。

对于二维数组a[0..4，1..5]，设每个元素占1个存储单元，且以列为主序存储，则元素a[2，2]相对于数组空间起始地址的偏移量是（）。

邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，（）。

对于n（n≥0）个元素构成的线性序列L，在（）时适合采用链式存储结构。

要在8×8的棋盘上摆放8个“皇后”，要求“皇后”之间不能发生冲突，即任何两个“皇后”不能在同一行、同一列和相同的对角线上，则一般采用（）来实现。

在（）存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。

（）算法策略与递归技术的联系最弱。

己知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key % 7计算散列地址，并散列存储在散列表A[0，…，6]中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为（）。

具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（）。

利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对应的二叉排序树以后，查找元素30要进行（）次元素间的比较。

分治算法设计技术（）。

对于哈希表，如果将装填因子定义为表中装入的记录数与表的长度之比，那么向表中加入新记录时，（）。

表达式“（a+b）*（c-d）”的后缀表示为（）。

设L为广义表，将head（L）定义为取非空广义表的第一个元素，tail（L）定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=（x，y，z），a，（u，t，w）），则从L中取出原子项y的运算是（）。

以下的算法设计方法中，（）以获取问题最优解为目标。

由元素序列（27，16，75，38，51）构造平衡二叉树，则首次出现的最小不平衡子树的根（即离插入结点最近且平衡因子的绝对值为2的结点）为（）。

若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为（）。

下面关于图（网）的叙述，正确的是（）。

对n个元素的有序表A[1..n]进行二分（折半）查找（除2取商时向下取整），查找元素A[i]（1≤i≤n）时，最多与A中的（）个元素进行比较。

若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况下的时间复杂度为（）。

若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。（）排序是稳定的。 设求解某问题的递归算法如下： F(int n) if (n==1) Move(1)； else F(n-1)； Move(n)； F(n-1)；

求单源点最短路径的迪杰斯特拉（Dijkstra）算法是按（）的顺序求源点到各顶点的最短路径的。

表达式“X=A+B×（C-D）/E”的后缀表示形式可以为（）（运算符优先级相同时，遵循左结合的原则）。

设某算法的计算时间表示为递推关系式T（n）=T（n-1）+n（n＞0）及T（0）=1，则该算法的时间复杂度为（）。

某一维数组中依次存放了数据元素15，23，38，47，55，62，88，95，102，123，采用折半（二分）法查找元素95时，依次与（）进行了比较。

在最好和最坏情况下的时间复杂度均为O（nlog2n）且稳定的排序方法是（）。

在11个元素的有序表A[1..11]中进行折半查找()，查找元素A[11]时，被比较的元素的下标依次是（）。

若用n个权值构造一棵最优二叉树（哈夫曼树），则该二叉树的结点总数为（）。

字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则在串比较、求子串、串连接、串替换等串的基本运算中，（）。

迪杰斯特拉（Diikstra）算法按照路径长度递增的方式求解单源点最短路径问题，该算法运用了（）算法策略。

与逆波兰式ab+-c*d-对应的中缀表达式是（）。

某一维数组中依次存放了数据元素12，23，30，38，41，52，54，76，85，在用折半（二分）查找方法（向上取整）查找元素54时，所经历“比较”运算的数据元素依次为（）。

（）在其最好情况下的算法时间复杂度为O（n）。

用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行（）次数组元素之间的比较。

若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为（）。

（）的邻接矩阵是一个对称矩阵。

表达式（a-b）*（c+5）的后缀表示是（）。

下面关于二叉排序树的叙述，错误的是（）。

在常用的描述二叉排序树的存储结构中，关键字值最大的结点（）。

下面关于哈夫曼树的叙述中，正确的是（）。

输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图1-5所示。若有8，1，4，2依次进入输入受限的双端队列，则得不到输出序列（）。

下面关于栈和队列的叙述，错误的是（）。

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定（）。

单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是（）。

己知一棵度为3的树（一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值）中有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为（）。

用关键字序列10，20，30，40，50构造的二叉排序树（二叉查找树）为（）。

一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行有限次来实现。这句话说明算法具有（）特性。

在（）中，任意一个结点的左、右子树的高度之差的绝对值不超过1。

循环链表的主要优点是（）。

下面关于二叉树的叙述，正确的是（）。

已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为（）。

某算法的时间复杂度表达式为T（n）=an²+bnlgn+cn+d，其中，n为问题的规模，a、b、c和d为常数，用O表示其渐近时间复杂度为（）。

下面C程序段中“count++”语句执行的次数为（）。
for(int i=1；i＜=11；i*=2)
for(int j=1；j＜=I；j++)
count++；

若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。（）排序是稳定的。
设求解某问题的递归算法如下：
F(int n)
if (n==1)
Move(1)；
else
F(n-1)；
Move(n)；
F(n-1)；

在最好和最坏情况下的时间复杂度均为O（nlog₂n）且稳定的排序方法是（）。

拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点v_i到v_j有一条路径，则在该线性序列中，顶点v_i必然在顶点v_j之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定（）。

由权值为29，12，15，6，23的5个叶子结点构造的哈夫曼树为 (57) ，其带权路径长度为 (58) 。

（57）处填（）。

求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为 (25) ；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 (26) 。
（25）处填（）。

对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用 (47) ，使用分治(Divide and Conquer)策略的是 (48) 算法。
（47）处填（）。

由权值为29，12，15，6，23的5个叶子结点构造的哈夫曼树为 (57) ，其带权路径长度为 (58) 。
（58）处填（）。

求解该算法的计算时间时，仅考虑算法Move所做的计算为主要计算，且Move为常数级算法。则算法F的计算时间T(n)的递推关系式为 (25) ；设算法Move的计算时间为k，当n=4时，算法F的计算时间为 (26) 。
（26）处填（）。

为了在状态空间树中 (11) ，可以利用LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该 (12) 。
（11）处填（）。

对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用 (47) ，使用分治(Divide and Conquer)策略的是 (48) 算法。
（48）处填（）。

某工程计划如图1-6所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是 (52) 天，作业J最迟应在第 (53) 天开工。

（52）处填（）。

设栈S和队列Q的初始状态为空，元素按照a，b，c，d，e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c，d，b，a，e，则元素的出栈顺序是 (61) ，栈S的容量至少为 (62) 。
（61）处填（）。

为了在状态空间树中 (11) ，可以利用LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该 (12) 。
（12）处填（）。

某工程计划如图1-6所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是 (52) 天，作业J最迟应在第 (53) 天开工。

（53）处填（）。

设栈S和队列Q的初始状态为空，元素按照a，b，c，d，e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c，d，b，a，e，则元素的出栈顺序是 (61) ，栈S的容量至少为 (62) 。
（62）处填（）。

斐波那契(Fibonacci)数列可以递归地定义为：

用递归算法求解F(6)时需要执行 (61) 次“+”运算，该方法采用的算法策略是 (62) 。
（61）处填（）。

已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97) 。对于任意一棵二叉树，叙述错误的是 (98) 。
（97）处填（）。

结点数目为n的二叉查找树(二叉排序树)的最小高度为 (40) ，最大高度为 (41) 。
（40）处填（）。

MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（53）处填（）。

斐波那契(Fibonacci)数列可以递归地定义为：

用递归算法求解F(6)时需要执行 (61) 次“+”运算，该方法采用的算法策略是 (62) 。
（62）处填（）。

设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。
（73）处填（）。

已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97) 。对于任意一棵二叉树，叙述错误的是 (98) 。
（98）处填（）。

MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（54）处填（）。

结点数目为n的二叉查找树(二叉排序树)的最小高度为 (40) ，最大高度为 (41) 。
（41）处填（）。

设一个包含Ⅳ个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为 (73) ，其中非零元素数目为 (74) 。
（74）处填（）。

MPEG-4是 (53) ，MPEG-4主要由音频编码、视频编码、数据平面、 (54) 、缓冲区管理和实时识别等部分构成，其中数据平面包括 (55) 两部分。
（55）处填（）。