C.强连通图 D.有向无环图
（ ）27．对n个关键字的序列进行快速排序，平均情况下的空间复杂度为_______
A.O（1） C.O（n）
B.O（logn） D.O（nlogn）
（ ）28．对于哈希函数H(key)=key，被称为同义词的关键字是_______
A．35和41 C.15和44
B.23和39
D.25和51
（ ）29. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。
A、 24 B、 48 C、 72 D、 53
（ ）30．对包含N个元素的散列表进行检索，平均检索长度 ________ A、为 o(log2N) B、为o(N) C、不直接依赖于N D、上述三者都不是 （ ）31. 向堆中插入一个元素的时间复杂度为________。
A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)
（ ）32．下面关于图的存储的叙述中，哪一个是正确的。 ________
A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关 B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关 C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关
（ ）33.输入序列为（A,B,C,D），不可能得到的输出序列是______.
A. (A,B,C,D) B.(D,C,B,A) C.(A, C,D,B) D.(C,A,B,D)
（ ）34.在长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次
前移____个元素。
A、n-i B、n-i+1 C、n-i-1 D、i
（ ）35.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____。
A、O(1) B、O(n) C、O(n2) D、O(log 2 n)
（ ）36.假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为 ____。
A、f+1==r B、r+1==f
C D F B E A 11
C、f==0 D、f==r （ ）37.从堆中删除一个元素的时间复杂以为____。
A、O(1) B、O(log 2 n) C、O(n) D、O(nlog 2 n)
（ ）38．若需要利用形参直接访问实参，则应把形参变量说明为____参数。
A.指针 B.引用 C.值
D.变量
（ ）39．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，
则执行____。
A. q一>next=p一>next；p一>next=q；C. q一>next=p一>next；p一>next=q； B. p一>next=q一>next；q=p； D. p一>next=q一>next；q一>next=p； （ ）40．在一个顺序队列中，队首指针指向队首元素的____位置。
A.前一个 B.后一个 C.当前 D.最后一个
（ ）41．向二叉搜索树中插入一个元素时，其时间复杂度大致力____。
A O（1） B O（1og2n） C O（n） D O（nlog2n） （ ）42.算法指的是________
A.计算机程序 C.排序算法
B.解决问题的计算方法 D.解决问题的有限运算序列
（ ）43.线性表采用链式存储时，结点的存储地址________
A.必须是不连续的 C.必须是连续的
B.连续与否均可
D.和头结点的存储地址相连续
（ ）44.将长充为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为________
A.O（1） C.O（m）
B.O（n）
D.O（m+n）
（ ）45.由两个栈共享一个向量空间的好处是：________
A.减少存取时间，降低下溢发生的机率 B.节省存储空间，降低上溢发生的机率 C.减少存取时间，降低上溢发生的机率 D.节省存储空间，降低下溢发生的机率
（ ）46.设数组DAtA[m]作为循环队列SQ的存储空间，front为队头指针，reAr为队尾指针，则
执行出队操作后其头指针front值为________
A. front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m
12
（ ）47.如下陈述中正确的是________
A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串
（ ）48.若目标串的长充为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的
时间复杂度是________ A.O（1） C.O（n2）
B.O（n） D.O（n3）
（ ）49.一个非空广义表的表头________
A.不可能是子表 C.只能是原子
B.只能是子表
0 2 3 3 5 D.可以是子表或原子
（ ）50. 从堆中删除一个元素的时间复杂度为________。
A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n)
（ ）51.一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为________
A.4 C.6
B.5
D.7
（ ）52. 从二叉搜索树中查找一个元素时，其时间复杂度大致为________。
A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)
（ ）53. 根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为________。
A、 O(n) B、 O(log2n ) C、 O(n2) D、 O(nlog2n)
（ ）54.用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况是如下________：
20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84
则所采用的排序方法是________ A.选择排序 C.归并排序
B.希尔排序 D.快速排序
（ ）55.适于对动态查找表进行高效率查找的组织结构是________
A.有序表
B.分块有序表
13
C.二叉排序树 D.线性链表
（ ）56. 若需要利用形参直接访问实参，则应把形参变量说明为________参数。
A 指针 B 引用 C 值 D 常量
（ ）57.链式栈与顺序栈相比，一个比较明显的优点是________。
A. 插入操作更加方便 B. 通常不会出现栈满的情况 C. 不会出现栈空的情况 D. 删除操作更加方便
（ ）58.设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直
接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作________ A. s->link = p->link; p->link = s; B. p->link = s; s->link = q; C. p->link = s->link; s->link = p; D. q->link = s; s->link = p; （ ）59．若让元素1,2,3依次进栈，则出栈次序不可能出现________种情况。
A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 （ ）60.线性链表不具有的特点是________。
A. 随机访问 B. 不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比
（ ）61．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。
Ａ．行号 Ｂ．列号 Ｃ．元素值 Ｄ．地址
（ ）62.假定一个顺序队列的队首和队尾指针分别为front和rear，存放该队列的数组长度为N，
则判断队空的条件为________。
A．（front+1）% N == rear C． front == 0 B．（rear+1）% N == front D． front == rear （ ）63．栈的插入和删除操作在＿＿＿进行．
(Ａ)．栈顶 (Ｂ)．栈底 (Ｃ)．任意位置 (Ｄ).指定位置
（ ）64. 在一个顺序循环队列中，队首指针指向队首元素的________位置。
A. 后两个 B. 后一个 C. 当前 D.前一个 （ ）65．下面算法的时间复杂度为＿＿。
int f（int n）{
if （n＝＝0）return 1；
14
else return n＊f（n-1）；}
A．O(1) B．O(n) C．O(n2) D．O(n!)
（ ）66.数据结构是一门研究非数值计算的程序设计问题中计算机的（ ① ）以及它们之间的（ ② ）和运算的学科
①Ａ、操作对象 Ｂ、计算方法 Ｃ、逻辑存储 Ｄ、数据映象 ②Ａ、结构 Ｂ、关系 Ｃ、运算 Ｄ、算法
（ ）67.数据结构被形式地定义为(K，R)，其中K是（ ① ）的有限集合，R是K上（ ② ）的有限集合
①Ａ、算法 Ｂ、数据元素 Ｃ、数据操作 Ｄ、逻辑结韵 ②Ａ、操作 Ｂ、映象 Ｃ、存储 Ｄ、关系 （ ）68.在数据结构中，从逻辑上可以把数据结构分为________
Ａ、动态结构和静态结构 Ｃ、线性结构和非线性结构
Ｂ、紧凑结构和非紧凑结构 Ｄ、内部结构和外部结构
（ ）69.线性表的顺序存储结构是一种_________的存储结构，线性表的链式存储结构是一种________的存储结构
Ａ、随机存取 Ｂ、顺序存取 Ｃ、索引存取 Ｄ、HASH存取
（ ）70.算法分析的目的是（ ① ），算法分析的两个主要方面是（ ② ）
①Ａ、找出数据结构的合理性 Ｃ、分析算法的效率以求改进 Ｂ、研究算法中的输入和输出的关系Ｄ、分析算法的易懂性和文档性
②Ａ、空间复杂性和时间复杂性 Ｃ、可读性和文档性 Ｂ、正确性和简明性 Ｄ、数据复杂性和程序复杂性
（ ）71.计算机算法指的是（ ① ），它必具备输入、输出和（ ② ）等五个特性
①Ａ、计算方法
Ｂ、排序方法 Ｄ、调度方法
Ｃ、解决莱一问题的有限运算序列
②Ａ、可执行性、可移植性和可扩充性 Ｃ、确定性、有穷性和稳定性 Ｂ、可执行性、确定性和有穷性 Ｄ、易谩性、稳定性和安全性 （ ）72.线性表若采用链表存储结构时，要求内存中可用存储单元的地址________
Ａ、必须是连续的 Ｂ、部分地址必须是连续的 Ｃ、一定是不连续的 Ｄ、连续不连续都可以 （ ）73.在以下的叙述中，正确的是__________
Ａ、线性表的线性存储结构优于链表存储结构 Ｃ、栈的操作方式是先进先出
15