1、数据元素及其关系在计算机存储器内的表示，称为数据的 ( B）
A.逻辑结构 B.存储结构
C.线性结构 D.非线性结构

2、某带头结点的单链表的头指针为 head，判定该链表为非空的条件是(B ）
A.headNULL B.head->nextNULL
C.head!=NULL D.head->next!=NULL

3、导致栈上溢的操作是 ( A)
A.栈满时执行的出栈 B.栈满时执行的入栈
C.栈空时执行的出栈 D.栈空时执行的入栈

4、 设数组 A[m]为循环队列 Q 的存储空间， front 为队头指针， rear为队尾指针，则判定 Q为空队列的条件是 (B ）
A.(rear-front>%m= =1
B.front= =rear

C.(rear-front>%m= =m-1
D.front==(rear+1>%m

5、 假设 S=″I AM A STUDENT″，则运算 substr(S,4,8> 的结果为( D）
A.″M A S″
B.″M A STUD″
C.″A STUDEN ″
D.″STUD″

6、在执行简单的串匹配算法时，最坏的情况为每次匹配比较不等的字符出现的位置均为 ( ）
A.模式串的最末字符 B.主串的第一个字符
C.模式串的第一个字符 D.主串的最末字符

7、从广义表 L=(((d>,c,d>> 中分解得到 (d>的操作为 ( ）
A.head(head(head(L>>> B.head(tail(head(L>>>
C.tail(head(head(L>>> D.tail(tail(head(L>>>

8、假设一棵完全二叉树按层次遍历的顺序依次存放在数组 BT[m]
中，其中根结点存放在 BT[0] ，若 BT[i] 中的结点有左孩子，则左
孩子存放在 ( ）

A.BT[i/2]
B.BT[2i-1]
C.BT[2i]
D.BT[2*i+1]

9、右图所示二叉树的中序序列是
( ）

A.DHEBAFIJCG
B.DHEBAFJICG
C.DBHEAFCJIG
D.DBHEAFJICG

10、连通图是指图中任意两个顶点之间 ( ）
A.都连通的无向图 B.都不连通的无向图
C.都连通的有向图 D.都不连通的有向图

11、下图所示带权无向图的最小生成树的权为 ( ）

A.14
B.15
C.17
D.18

12、对记录序列 (314，298，508，123，486，145>依次按个位和十位进行两趟基数排序之后所得结果为 ( D)
A.123，145，298，314，486，508
B.508，314，123，145，

C.486，314，123，145，508，298
D.298，123，508，486，

13、在待排关键字序列基本有序的前提下，效率最高的排序方法是( A）
A.直接插入排序 B.快速排序
C.直接选择排序 D.归并排序

14、在下列各棵二叉树中，二叉排序树是 ( >

15、采用 ISAM或 VSAM组织的文件是 (C）
A.索引非顺序文件 B.顺序文件
C.索引顺序文件 D.散列文件

16、下列选项中，与数据存储结构直接相关的是 (B)

A.线性表 B.双向链表 C.二叉树 D.有向图

17、将12个数据元素保存在顺序表中，若第一个元素的存储地址是100，第二个元素的存储地址是105，则该顺序表最后一个元素的存储地址是 （C）
A.111 B.144 C. 155 D.156

18、设栈的初始状态为空，元素1,2,3,4,5,6依次入栈，栈的容量是3，能够得到的出栈序列是 ( B )
A.1,2,6,4,3,5 B.2,4,3,6，5,1 C.3,1,2,5,4,6 D.3,2,6,5,1,4

19、设指针变量head指向非空单循环链表的头结点，指针变量p指向终端结点，next是结点的指针域，则下列逻辑表达式中，值为真的是（B）
A.p-next->next == head
B.p->next == head
C.p-next->next == NULL
D.p->next == NULL

20、已知广义表LS=(((a,b))，((c,(d))) ,(e(f))),(g,h)) ,LS的深度是 ©
A.2 B.3 C.4 D.5

21、已知一颗高度为4的完全二叉树T共有5个叶结点，则T中结点个数最少是 （A）
A.9 B.10 C.11 D.12

22、在一颗非空二叉树的中序遍历序列中，所有列在根结点前面的是 ( B)
A.左子树中的部分结点 B.左子树中的全部结点 C.右子树中的部分结点 D.右子树中的全部结点

23、用领接矩阵表示有n个顶点和e条边的无向图，采用压缩方式存储，矩阵零元素的个数是 （A）
A.n(n+1)/2-e B.(n+1)/2-2e C.nxn-e D.nxn-2e

24、无向图G中所有顶点的度数之和是20，则G中的边数是 （A）
A.10 B.20 C.30 D.40

25、设有向图G含有n个顶点、e条边，使用领接表存储。对G进行广度优先遍历的算法的时间复杂度是 （C）
A.0(n) B.0(e) C.0(n+e) D.0(nxe)

26、对数据序列（25，15，7,18,10,0,4）采用直接插入排序进行升序排序，两趟排序后，得到的排序结果为 （D）
A.0,4,7,18,10,25,15 B.0，4,25,15，7,18,10 C.7,15,10,0,4,18,25 D.7,15,25,18,10,0,4

27、下列排序方法中，稳定的排序方法是 （B）
A.希尔排序 B.归并排序 C.堆排序 D.快速排序

28、一组记录的关键码为（45,68,57，13,24,89），利用堆排序算法进行升序排序，建立的初始堆 为 （B）
A.68,45,57,13,24,89

B.89,68,57,13,24,45
C.89,68,57,45,24,13

D.89,57,68,24,45,13

29、一颗二叉排序树中，关键字n所在结点是关键字m所在结点的祖先，则 （D）
A. n一定大于m
B. n一定小于m
C.n一定等于m
D.n与m的大小关系不确定

30、设散列表长m=14,散列函数H（key）=key%11。表中已保存4个关键字：addr(15)=4 , addr(38)=5 , addr(61)=6 , addr(84)=7 ,其余地址均为空。保存关键字49时存在冲突，采用线性探查法来处理。则查找关键字49时的探查次数是 （C）
A.1 B.2 C.4 D.8

31、若一个算法的时间复杂度用 T(n) 表示，其中 n 的含义是（ A ）

A．问题规模 B．语句条数
C．循环层数 D．函数数量

32、具有线性结构的数据结构是（ C ）
A．树 B．图
C．栈和队列 D．广义表

线性结构有：顺序表、栈和队列、串

33、将长度为 n 的单链表连接在长度为 m的单链表之后，其算法的时间复杂度为（ C ）
A．O(1) B． O(m)
C．O(n) D． O(m+n)

34、在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ D ）
A．2 个 B． 3 个
C．4 个 D． 6 个

35、假设以数组 A[60] 存放循环队列的元素， 其头指针是 front=47 ，当前队列有 50个元素，则队列的尾指针值为 （ D ）
A．3 B． 37
C．50 D． 97

36、若栈采用链式存储结构，则下列说法中正确的是（ B ）
A ．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C ．需要判断栈满但不需要判断栈空
D．不需要判断栈满也不需要判断栈空

37、若串 str= ”Software ”，其子串的数目是（ D ）
A．8 B． 9
C．36 D． 37

任意个连续字符组成的子序列称为该串的子串

38、设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式， a ll 为第一个元素，其存储地址为 1000，每个元素占
一个地址单元，则 a 85 的地址为 （ C ）
A．1012 B． 1017
C．1032 D． 1039

39、允许结点共享的广义表称为（ D ）P67
A．纯表 B．线性表
C．递归表 D．再入表

40、下列数据结构中，不属于二叉树的是（ B ）B树是一种平衡的多叉树
A．B树
B． AVL树 AVL树是自平衡二叉查找树
C．二叉排序树

D．哈夫曼树 哈夫曼树是最优二叉树

41、对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）辅导书中 P97 第 10 题

A．1， 5，2，6，3，4 B． 1，5，6，2，3，4
C．5， 1，6，3，4，2 D． 5，1，2，6，4，3

42、以 v1 为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

A．v1，v2，v3，v4，v5，v6， v7 B． v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5， v6 D． v1，v2，v5，v6，v7，v3，v4

43、下列排序算法中不稳定的是（ A ）P164
A．快速排序 B．归并排序
C．冒泡排序 D．直接插入排序
稳定：直接插入、冒泡、归并、基数
不稳定：直接选择、希尔、快速、堆

44、一个有序表为 (1 ， 3，9，12，32， 41，45，62，75，77，82，95，100) ，当采用 折半查找 方法查找值 32 时，查
找成功需要的比较次数是（ B ） mid 1 =45，mid 2 =9， mid 3 =32
A．2 B． 3
C．4 D． 8

45、采用 ISAM组织文件的方式属于（ D ）P211-212
A．链组织 B．顺序组织
C．散列组织 D．索引组织

46、若目标串的长度为 n，模式串的长度为 [n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ D）

47、假设以带行表的三元组表表示稀疏矩阵，则和下列行表 0 2 3 3 5
对应的稀疏矩阵是（B ）

48、假设一个有 n 个顶点和 e 条弧的有向图用邻接表表示 ,则删除与某个顶点 v i 相关的所有弧的时间复杂度是 (C )
A．O(n) B．O(e) C．O(n+e) D．O(n*e)

49、用某种排序方法对关键字序列（ 25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：
20，15， 21，25，47，27，68，35，84
15，20， 21，25，35，27，47，68，84
15，20， 21，25，27，35，47，68，84
则所采用的排序方法是（ ）
A．选择排序 B．希尔排序 C．归并排序 D．快速排序

50、下面程序段的时间复杂度是 ( D )
for(i=0;i<n;i++)
for(j=1;j<m;j++)
A[i][j]=0 ；

A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)

51、在单链表中，指针 p 指向元素为 x 的结点，实现“删除 x 的后继”的语句是 ( B )
A.p=p->next; B.p->next=p->next->next;
C.p->next=p; D.p=p->next->next;

52、在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若p->next->next= head,则( D )
A.p 指向头结点 B.p 指向尾结点
C.*p 的直接后继是头结点 D.*P 的直接后继是尾结点

53、判定“带头结点的链队列为空”的条件是 ( C )
A.Q.frontNULL B.Q.rearNULL
C.Q.front==Q.rear D.Q.front!=Q.rear

54、设有两个串 T 和 P，求 P 在 T 中首次出现的位置的串运算称作 ( D )
A.联接 B.求子串 C.字符定位 D.子串定位

55、广义表 A=(a,(b),(),(c,d,e)) 的长度为 ( A )
A.4 B.5 C.6 D.7

56、一棵含 18 个结点的二叉树的高度至少为 ( C )
A.3 B.4 C.5 D.6

57、已知二叉树的先序序列为 ABDECF ，中序序列为 DBEAFC ，则后序序列为 ( D )
A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA

58、无向图中一个顶点的度是指图中 ( B )
A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数
C.通过该顶点的回路数 D.与该顶点连通的顶点数

59、已知一个图如下所示，从顶点 a 出发进行广度优先遍历可能得到的序列为 ( C )

A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e

60、在下列排序方法中，平均时间性能为 O(nlogn)且空间性能最好的是 ( B )
A.快速排序 B.堆排序 C.归并排序 D.基数排序

61、已知一组关键字为 {25,48,36,72,79,82,23,40,16,35} ，其中每相邻两个为有序子序列。对这
些子序列进行一趟两两归并的结果是 ( A )
A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35}
C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82}

62、设顺序存储的线性表共有 123 个元素，按分块查找的要求等分成 3 块。若对索引表采用顺序查找来确定块， 并在确定的块中进行顺序查找， 则在查找概率相等的情况下， 分块查找成功时的平均查找长度为 ( B )
A.21 B.23 C.41 D.62

63、索引非顺序文件的特点是 ( A )
A.主文件无序，索引表有序 B.主文件有序，索引表无序
C.主文件有序，索引表有序 D.主文件无序，索引表无序

64、倒排文件的主要优点是 ( C )
A.便于进行插入和删除运算 B.便于进行文件的恢复
C.便于进行多关键字查询 D.节省存储空间

65、计算机识别、存储和加工处理的对象被统称为 ( b )

A.数据 B.数据元素
C.数据结构 D. 数据类型

66、 在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( b )
A.O(1) B.O(n)
C.O(nlogn) D.O(n2)

67、 队和栈的主要区别是 ( d )
A.逻辑结构不同 B. 存储结构不同
C.所包含的运算个数不同 D.限定插入和删除的位置不同

68、链栈与顺序栈相比，比较明显的优点是 ( d )
A.插入操作更加方便 B. 删除操作更加方
便
C.不会出现下溢的情况 D. 不会出现上溢的情况

69、采用两类不同存储结构的字符串可分别简称为 ( b )
A.主串和子串 B.顺序串和链串
C.目标串和模式串 D. 变量串和常量串

70、在目标串 T［ 0…n-1 ］=″xwxxyxy″中，对模式串 P［0…m-1 ］=″xy″进行子串定位操作的结
果是 ( c )
A.0 B.2
C.3 D.5

71、 已知广义表的表头为 a，表尾为 (b,c) ，则此广义表为 ( b )
A.(a,(b,c)) B.(a,b,c)
C.((a),b,c) D.((a,b,c))

72、二维数组 A 按行优先顺序存储，其中每个元素占 1 个存储单元。若 A［1］［1］的存储地址为420，A［3］［ 3］的存储地址为 446，则 A［ 5］［ 5］的存储地址为 ( c )
A.470 B.471
C.472 D.473

73、 二叉树中第 5 层上的结点个数最多为 ( d )
A.8 B.15
C.16 D.32

74、 下列编码中属前缀码的是 ( a )
A.{1,01,000,001} B.{1,01,011,010}
C.{0,10,110,11} D.{0,1,00,11}

75、如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 ( d )
A.有向完全图 B. 连通图
C.强连通图 D. 有向无环图

76、对 n 个关键字的序列进行快速排序，平均情况下的空间复杂度为 ( d )
A.O(1) B.O(logn)
C.O(n) D.O(n logn)

77、对表长为 n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( n/2 )
A. B.
C. D.n

78、. 对于哈希函数 H(key)=key%13, 被称为同义词的关键字是 ( d )
A.35 和 41 B.23 和 39
C.15 和 44 D.25 和 51

79、 稠密索引是在索引表中 ( )

A.为每个记录建立一个索引项 B.为每个页块建立一个索引项
C.为每组记录建立一个索引项 D.为每个字段建立一个索引项

80、若将数据结构形式定义为二元组 (K，R)，其中 K是数据元素的有限集合，则 R 是 K 上( )

A. 操作的有限集合 B. 映象的有限集合
C. 类型的有限集合 D. 关系的有限集合

81、在长度为 n 的顺序表中删除第 i 个元素 (1≤i ≤n)时，元素移动的次数为 ( )
A. n-i+1 B. i
C. i+1 D. n-i

82、若不带头结点的单链表的头指针为 head，则该链表为空的判定条件是 ( )
A. headNULL B. head->nextNULL
C. head!=NULL D. head->next==head

83、引起循环队列队头位置发生变化的操作是 ( )
A. 出队 B. 入队
C. 取队头元素 D. 取队尾元素

84、若进栈序列为 1，2，3， 4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是( )
A. 2，4，3，1，5，6 B. 3， 2，4，1，6，5
C. 4，3，2，1，5，6 D. 2， 3，5，1，6，4

85、字符串通常采用的两种存储方式是 ( )
A. 散列存储和索引存储 B. 索引存储和链式存储
C. 顺序存储和链式存储 D. 散列存储和顺序存储

86、设主串长为 n，模式串长为 m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为 ( )
A. m B. n-m
C. n-m+1 D. n

87、二维数组 A［12］［ 18］采用列优先的存储方法，若每个元素各占 3 个存储单元，且第 1 个
元素的地址为 150，则元素 A［9］［ 7］的地址为 ( )
A. 429 B. 432
C. 435 D. 438

88、对广义表 L=((a,b),(c,d),(e,f)) 执行操作 tail(tail(L)) 的结果是 ( )
A. (e,f) B. ((e,f))
C. (f) D. ( )

89、下列图示的顺序存储结构表示的二叉树是 ( A )

90、n 个顶点的强连通图中至少含有 ( )
A. n-1 条有向边 B. n 条有向边
C. n(n-1)/2 条有向边 D. n(n-1) 条有向边

91、对关键字序列 (56 ，23， 78，92，88，67，19，34) 进行增量为 3 的一趟希尔排序的结果为
( )
A. (19，23，56， 34，78，67，88，92)

B. (23，56，78，66，88，92，19，34)
C. (19，23，34， 56，67，78，88，92)
D. (19，23，67，56，34，78，92，88)

92、若在 9 阶 B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( )
A. 4 B. 5
C. 8 D. 9

93、由同一关键字集合构造的各棵二叉排序树 ( )
A. 其形态不一定相同，但平均查找长度相同
B. 其形态不一定相同，平均查找长度也不一定相同
C. 其形态均相同，但平均查找长度不一定相同
D. 其形态均相同，平均查找长度也都相同

94、ISAM文件和 VSAM文件的区别之一是 ( )
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者只能进行顺序存取，后者只能进行随机存取
C. 前者建立静态索引结构，后者建立动态索引结构
D. 前者的存储介质是磁盘，后者的存储介质不是磁盘

95、根据数据元素的关键字直接计算出该元素存储地址的存储方法是（ D ）

A．顺序存储方法 B．链式存储方法
C．索引存储方法 D．散列存储方法

96、2．下述程序段中语句①的频度是（ C ）
s=0;
for(i=1;i<m;i++)
for(j=0;j<=i;j++)
① s+=j;
A． B ．
C． D ．

97、求单链表中当前结点的后继和前驱的时间复杂度分别是（ C ）
A．O（n）和 O（1）
B．O（1）和 O（1）
C．O（1）和 O（n）
D．O(n) 和 O（n）

98、非空的单循环链表的头指针为 head,尾指针为 rear，则下列条件成立的是（ A ）
A．rear->next= =head B ．rear->next->next= =head
C． head->next= =rear D ．head->next->next= =rear

99、若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是（ A ）
A．栈 B ．线性表
C．队列 D ．二叉排序树

100、已知主串 s=″ ADBADABBAAB ″ ，模式串 t= ″ ADAB″，则应用朴素的串匹配算法进行模式匹配
过程中，无效位移的次数是（ B ）
A．2 B．3
C．4 D．5

101、串 s=″ Data Structure ″ 中长度为 3 的子串的数目是（ C ）
A．9 B ．11
C．12 D ．14

102、假设以行优先顺序存储三维数组 R[6][9][6] ，其中元素 R[0][0][0] 的地址为 2100，且每个元素
占 4 个存储单元，则存储地址为 2836 的元素是（ B ）
A．R[3][3][3] B ．R[3][3][4]
C． R[4][3][5] D ．R[4][3][4]

103、除第一层外，满二叉树中每一层结点个数是上一层结点个数的（ C ）
A．1/2 倍 B．1 倍
C．2 倍 D ．3 倍

104、对于含 n 个顶点和 e 条边的图，采用邻接矩阵表示的空间复杂度为（ D ）
A．O（n） B．O(e)
C．O(n+e) D ．O(n2)

105、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）
A．深度优先搜索算法 B ．广度优先搜索算法
C．求最小生成树的 prim 算法 D．拓扑排序算法

106、快速排序在最坏情况下的时间复杂度是（ B ）
A．O(n2log2n) B ．O(n2)
C．O(nlog2n) D ．O(log2n)

107、能进行二分查找的线性表 ,必须以（ A ）
A．顺序方式存储 ,且元素按关键字有序
B．链式方式存储 ,且元素按关键字有序
C．顺序方式存储 ,且元素按关键字分块有序
D．链式方式存储 ,且元素按关键字分块有序

109、为使平均查找长度达到最小 ,当由关键字集合 {05,11,21,25,37,40,41,62,84} 构建二叉排序树时 ,
第一个插入的关键字应为（ B ）
A．05 B ．37
C．41 D ．62

110、SAM 文件的周期性整理是为了空出（ D ）
A．磁道索引 B．柱面索引
C．柱面基本区 D．柱面溢出区

111、数据结构是（ D）

A．一种数据类型
B．数据的存储结构
C．一组性质相同的数据元素的集合
D．相互之间存在一种或多种特定关系的数据元素的集合

112、算法分析的目的是（B ）
A．辨别数据结构的合理性
B．评价算法的效率
C．研究算法中输入与输出的关系
D．鉴别算法的可读性

113、在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D）
A．插入 B．删除
C．排序 D．定位

114、若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行， 则可能出现的出栈序列为 （B）
A．3，2，6，1，4，5
B．3，4，2，1，6， 5
C．1，2，5，3，4，6
D．5，6，4，2，3， 1

115、设串 sl= ″Data Structures with Java″,s2= ″it ″，则子串定位函数 index(s1,s2) 的值为（D ）
A．15 B．16
C．17 D．18

116、二维数组 A[8][9] 按行优先顺序存储，若数组元素 A[2][3] 的存储地址为 1087，A[4][7] 的存
储地址为 1153，则数组元素 A[6][7] 的存储地址为（A ）
A．1207 B．1209
C．1211 D．1213

117、在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（A ）
A．队列 B．栈
C．线性表 D．有序表

118、在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ B）
A．不一定相同 B．都相同
C．都不相同 D．互为逆序

119、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（ C）
A．层次遍历算法 B．前序遍历算法
C．中序遍历算法 D．后序遍历算法

120、若用邻接矩阵表示一个有向图，则其中每一列包含的″ 1″的个数为（ A）
A．图中每个顶点的入度 B．图中每个顶点的出度
C．图中弧的条数 D．图中连通分量的数目

121、图的邻接矩阵表示法适用于表示（C ）
A．无向图 B．有向图
C．稠密图 D．稀疏图

122、在对 n 个关键字进行直接选择排序的过程中， 每一趟都要从无序区选出最小关键字元素， 则
在进行第 i 趟排序之前，无序区中关键字元素的个数为（ D）
A．i B．i+1
C．n-i D．n-i+1

123、下列排序算法中，其时间复杂度和记录的初始排列无关的是（ B）

A．插入排序 B．堆排序
C．快速排序 D．冒泡排序

124、若有序表的关键字序列为（ b,c,d,e,f,g,q,r,s,t ），则在二分查找关键字 b 的过程中，先
后进行比较的关键字依次为（A ）
A．f,c,b B．f,d,b
C．g,c,b D．g,d,b

125、若在文件中查询年龄在 60 岁以上的男性及年龄在 55 岁以上的女性的所有记录， 则查询条件
为（C ）
A．（性别 =“男”） OR(年龄 > 60)OR（性别 =“女”） OR（年龄 >55）
B．（性别 =“男”） OR(年龄 > 60)AND（性别 =“女”） OR（年龄 >55）
C．（性别 =“男”） AND(年龄 > 60)OR（性别 =“女”） AND（年龄 >55）
D．（性别 =“男”） AND(年龄 > 60)AND（性别 =“女”） AND（年龄 >55）

126、按值可否分解，数据类型一般可分为两类，它们是 ©
A. 静态类型和动态类型
B. 原子类型和表类型
C. 原子类型和结构类型
D. 数组类型和指针类型

127、

A. A f(n) 是0(g(n))
B. B g(n) 是0(f(n))
C. C h(n) 是0(nlogn)
D. D h(n) 是0(n2)

128、指针p、q和r 依次指向某循环链表中三个相邻的结点，交换结点 *q和结点 *r 在表中次序的程序段是 ()

129、若进栈次序为 a，b，c，且进栈和出栈能够穿插进行，则可能出现的含 3个元素的出栈序列
个数是 ()
A. 3
B. 5
C. 6
D. 7
答案： B

130、假设以数组 A［n］存放循环队列的元素，其头指针 front 指向队头元素的前一个位置、尾指
针rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ()
A. rearfront
B. (front+1) ％nrear
C. rear+1front
D. (rear+1) ％nfront
答案： D

131、串的操作函数 str 定义为：
A. 3
B. 4
C. 5
D. 6
答案： C

132、二维数组 A［10］［6］采用行优先的存储方法，若每个元素占 4个存储单元，已知元素
A［3］［4］的存储地址为 1000，则元素 A［4］［3］的存储地址为 ()
A. 1020
B. 1024
C. 1036
D. 1240
答案： A

133、对广义表 L= (a ，()) 执行操作 tail(L) 的结果是 ()
A. ()
B. (())
C. a
D. (a)
答案： B

134、已知二叉树的中序序列和后序序列均为 ABCDEF ，则该二叉树的先序序列为 ()
A. FEDCBA
B. ABCDEF
C. FDECBA
D. FBDCEA
答案： A

135、已知森林 F={T1，T2，T3，T4，T5}，各棵树 Ti(i=1 ，2，3，4，5)中所含结点的个数分别
为7，3，5，1，2，则与 F对应的二叉树的右子树中的结点个数为 ()
A. 2
B. 3
C. 8
D. 11
答案： D

136、若非连通无向图 G含有21条边，则 G的顶点个数至少为 ()
A. 7
B. 8
C. 21
D. 22
答案： B

137、如图所示的有向图的拓扑序列是 ()

A. c，d，b，a，e
B. c，a，d，b，e
C. c，d，e，a，b
D. c，a，b，d，e
答案： B

138、对关键字序列 (6 ，1，4，3，7，2，8，5)进行快速排序时，以第 1个元素为基准的一次划分的结果为 ()
A. (5，1，4，3，6，2，8，7)
B. (5，1，4，3，2，6，7，8)
C. (5，1，4，3，2，6，8，7)
D. (8，7，6，5，4，3，2，1)
答案： C

139、分块查找方法将表分为多块，并要求 ()
A. 块内有序
B. 块间有序
C. 各块等长
D. 链式存储
答案： B

140、便于进行布尔查询的文件组织方式是 ()
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
答案： D

141、若一个算法的时间复杂度用 T(n) 表示，其中 n 的含义是
（ A ）
A．问题规模 B．语句条数

C．循环层数 D．函数数量

142、具有线性结构的数据结构是（ C ）线性结构有：顺序表、栈和队列、串
A．树 B．图
C．栈和队列 D．广义表

143、将长度为 n 的单链表连接在长度为 m的单链表之后，其算法的时间复杂度为（ B ）
A．O(1) B．O(m)
C．O(n) D．O(m+n)
插入到长度为 m的单链表，需找到表尾， 时间复杂度为 o(m)，
连接的时间复杂度为 0(1), 因此总的时间复杂度为 0(m)

144、在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）
A．2 个 B．3 个
C．4 个 D．6 个

145、假设以数组 A[60] 存放循环队列的元素，其头指针是front=47 ，当前队列有 50 个元素，则队列的尾指针值为（ B ）
A．3 B．37

C．50 D．97

146、若栈采用链式存储结构， 则下列说法中正确的是 （ B ）
A ．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C ．需要判断栈满但不需要判断栈空
D ．不需要判断栈满也不需要判断栈空
因为链栈中的结点是动态分配的，能够不考虑上溢，因此无需定义 stackFull 运算。

147、若串 str= ”Software ”，其子串的数目是（ D ）
A．8 B．9
C．36 D．37

148、设有一个 10阶的下三角矩阵 A，采用行优先压缩存储方式，a ll 为第一个元素，其存储地址为 1000，每个元素占一个地址单元，则 a 85 的地址为 （ C ）
A．1012 B．1017
C．1032 D．1039

149、允许结点共享的广义表称为（ D ）
A．纯表 B．线性表
C．递归表 D．再入表

150、下列数据结构中，不属于二叉树的是（ A ）
A．B树 B树是一种平衡的多叉树
B．AVL树 AVL树是自平衡二叉查找树
C．二叉排序树
D．哈夫曼树 哈夫曼树是最优二叉树

151、对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ）

A．1，5，2，6，3，4 B．1，5，6，2，3，4
C．5，1，6，3，4，2 D ．5，1，2，6，4，3

152、以 v1 为起始结点对下图进行深度优先遍历， 正确的遍历序列是（ D ）

A．v1，v2，v3，v4，v5，v6，v7
B．v1，v2，v5，v4，v3，v7，v6
C．v1，v2，v3，v4，v7，v5，v6
D．v1，v2，v5，v6，v7，v3，v4
深度优先遍历类似于树的前序遍历。其特点是尽可能先对纵深方向进行搜索

153、下列排序算法中不稳定的是（ A ）
A．快速排序 B．归并排序
C．冒泡排序 D．直接插入排序
稳定：直接插入、冒泡、归并、基数 不稳定：直接选
择、希尔、快速、堆

154、一个有序表为 (1，3，9，12，32，41，45，62，75，77，82，95，100)，当采用折半查找方法查找值 32 时，查找成功需要的比较次数是（ B ）mid1=45，mid2=9，mid3=32
A．2 B．3
C．4 D．8

155、采用 ISAM组织文件的方式属于（ D ）
A．链组织 B．顺序组织

C．散列组织 D．索引组织

156、数据的四种存储结构是 ( A )

A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构
B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构
C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构
D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构

157、若对某线性表最常见的操作是在最后一个结点之后插入一个新结点或删除最后一个结点， 要使操作时间最少， 下列选项中，应选择的存储结构是 (C )
A.无头结点的单向链表 B.带头结点的单向链表
C.带头结点的双循环链表 D.带头结点的单循环链表

158、若带头结点的单链表的头指针为 head，则判断链表是否为空的条件是 (B )
A.head=NULL B.head->next=NULL
C.head!=NULL D.head->next!=head

159、若元素的入栈顺序为 1，2，3…，n，如果第 2个出栈的元素是n，则输出的第 i(1<=i<=n) 个元素是 ( D )
A.n-i B.n-i+l
C.n-i+2 D.无法确定

160、串匹配算法的本质是 (C )
A.串复制 B.串比较
C.子串定位 D.子串链接

161、设有一个 10阶的对称矩阵 A，采用行优先压缩存储方式， a 11为第一个元素， 其存储地址为 1，每个元素占一个字节空间，则a 85 的地址为 ( C )
A.13 B.18
C.33 D.40

162、若一棵二叉树的前序遍历序列与后序遍历序列相同， 则该二叉树可能的形状是 ( B )
A.树中没有度为 2的结点 B.树中只有一个根结点
C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树

163、若根结点的层数为 1，则具有 n个结点的二叉树的最大高度是(A )

164、在图G中求两个结点之间的最短路径能够采用的算法是( A )
A.迪杰斯特拉（ Dijkstra ）算法 B.克鲁斯卡尔（ Kruskal ）算法
C.普里姆 (Prim) 算法 D.广度优先遍历 (BFS)算法

165、下图G=(V,E) 是一个带权连通图， G的最小生成树的权为
( D )

166、在下图中，从顶点 1出发进行深度优先遍历可得到的序列是(B )

167、如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是 (B )
A.不稳定的 B.稳定的
C.基于交换的 D.基于选择的

168、设有一组关键字 (19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数 H(key)=key%13 构造散列表，用拉链法解决冲突，散列地址为 1的链中记录个数为 (C )
A.1 B.2
C.3 D.4

169、已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是 ( D )

170、若需高效地查询多关键字文件，能够采用的文件组织方式为( D )
A.顺序文件 B.索引文件
C.散列文件 D.倒排文件

171、下列选项中与数据存储结构无关的术语是（ ）

A.顺序表 B.链表
C.链队列 D.栈

172、将两个各有 n 个元素的有序表归并成一个有序表，最少的比较次数是（ ）
A.n-1 B.n
C.2n-1 D.2n

173、已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ ）
A.rear=(rear-1)%m; B.front=(front+1)%m;
C.front=(front-1)%m; D.rear=(rear+1)%m ;

174、递归实现或函数调用时， 处理参数及返回地址， 应采用的数据结构是（ ）
A.堆栈 B.多维数组
C.队列 D.线性表

175、设有两个串 p 和 q，其中 q 是 p 的子串，则求 q 在 p 中首次出现位置的算法称为（ ）
A.求子串 B.串联接
C.串匹配 D.求串长

176、对于广义表 A，若 head(A)等于 tail(A) ，则表 A （ ）
A.( ) B.(( ))
C.(( ),( )) D.(( ),( ),( ))

177、若一棵具有 n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ ）
A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树
C.高度为 n 的二叉树 D.存在度为 2 的结点的二叉树

178、若一棵二叉树中度为 l 的结点个数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是（ ）
A.4 B.5
C.7 D.8

179、下列叙述中错误的是（ ）
A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次
B.图的遍历能够采用深度优先遍历和广度优先遍历
C.图的广度优先遍历只适用于无向图
D.图的深度优先遍历是一个递归过程

180、已知有向图 G=(V ，E)，其中 V={V1 ，V2，V3，V4} ，E={<V1 ，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>} ，图 G 的拓扑序列是（ ）
A.V1,V2,V3,V4 B.V1,V3,V2,V4
C.V1,V3,V4,V2 D.V1,V2,V4,V3

181、平均时间复杂度为 O(n log n)的稳定排序算法是（ ）
A.快速排序 B.堆排序
C.归并排序 D.冒泡排序

182、已知关键字序列为 (51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（ ）
A.(18,22,30,46,51,68,75,83)
B.(30,18,22,46,51,75,83,68)
C.(46,30,22,18,51,75,68,83)
D.(30,22,18,46,51,75,68,83)

183、某索引顺序表共有元素 395 个，平均分成 5 块。若先对索引表采用顺序查找， 再对块中元素进行顺序查找， 则在等概率情况下，分块查找成功的平均查找长度是（ ）
[[(2+80)/2+(3+81)/2+(4+82)/2+(5+83)/2+(6+84)/2]*79]/395

A.43 B.79
C.198 D.200

184、在含有 10 个关键字的 3 阶 B-树中进行查找，至多访问的结点个数为（ ）
A.2 B.3
C.4 D.5

185、ISAM 文件系统中采用多级索引的目的是（ ）
A.提高检索效率 B.提高存储效率
C.减少数据的冗余 D.方便文件的修改

186、在数据的逻辑结构中，树结构和图结构都是（ A）

A.非线性结构 B.线性结构
C.动态结构 D.静态结构

187、在一个长度为 n 的顺序表中插入一个元素的算法的时间复杂度为（ C）

188、指针 p1 和 p2 分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（D ）

189、设栈的初始状态为空，入栈序列为 1，2，3，4，5，6，若出栈序列为 2，4，3，6，5，1，则操作过程中栈中元素个数最多时为（ B）
1 、4、6

A.2 个 B.3 个
C.4 个 D.6 个

190、队列的特点是（D ）
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入，在另一端进行删除

191、一个链串的结点类型定义为
﹟define NodeSize 6
typedef struct node{
char data[NodeSize];
struct node*next;
}LinkStrNode;
如果每个字符占 1 个字节，指针占 2 个字节， 该链串的存储
密度为（D ）
A.1/3 B.1/2
C.2/3 D.3/4

192、广义表 A=（a,B,(a,B,(a,B,⋯⋯）））的长度为（C）
A.1 B.2
C.3 D.无限值

193、已知 10×12 的二维数组 A，按“行优先顺序”存储，每个元素占 1 个存储单元，已知 A[1][1] 的存储地址为 420，则A[5][5] 的存储地址为（C ）
A.470 B.471
C.472 D.473

194、在一棵二叉树中，度为 2 的结点数为 15，度为 1 的结点数为 3，则叶子结点数为（B ）
A.12 B.16
C.18 D.20

195、在带权图的最短路径问题中，路径长度是指（D ）
A.路径上的顶点数 B.路径上的边数
C.路径上的顶点数与边数之和 D.路径上各边的权值之和

196、具有 n 个顶点、 e 条边的无向图的邻接矩阵中，零元素的个数为（C ）

197、要以 O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ A）
A.归并排序 B.快速排序
C.堆排序 D.冒泡排序

198、若希望在 1000 个无序元素中尽快求得前 10 个最大元素，应借用（A ）
A.堆排序 B.快速排序
C.冒泡排序 D.归并排序

199、对有序表进行二分查找成功时，元素比较的次数（B）
A.仅与表中元素的值有关
B.仅与表的长度和被查元素的位置有关
C.仅与被查元素的值有关
D.仅与表中元素按升序或降序排列有关

200、散列文件是一种（B ）
A.顺序存取的文件 B.随机存取的文件
C.索引存取的文件 D.索引顺序存取的文件

201、每个结点有且仅有一个直接前趋和多个 (或无 )直接后继 (A)

A.树状结构 B.网状结构
C.线性结构 D.层次结构

202、某线性表中最常见的操作是在最后一个元素之后插入元素和 删 除 第 一 个 元 素 ， 则 最 节 省 运 算 时 间 的 存 储 结 构 是（ D ）
A.单链表 B.双链表
C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表

203、已知一个栈的入栈序列是 1，2，3，⋯，n，其输出序列为p l ，p 2 ，p 3 ⋯.，p n ，若 p 1 是 n，则 p i 是（ C ）
A.i B.n-i
C.n-i+l D.不确定

204、下 面 关 于 串 的 叙 述 中 ， 正 确 的 是（ A ）
A.串是一种特殊的线性表 B.串中元素只能 是字母
C.空串就是空白串 D.串的长度必须大于零

205、无向完全图 G 有 n 个结点，则它的边的总数为（ C ）

206、若一棵二叉树有 10 个度为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点数是（ B ）
A.9 B.11
C.15 D.不确定

207、如图所示，在下面的 4 个序列中，不符合
．．． 深度优先遍历的序列是（ A ）
A.acfdeb
B.aebdfc
C.aedfbc
D.aefdbc

208、无论待排序列是否有序，排序算法时间复杂度都是 O(n2 )的排序方法是（ D ）
A.快速排序 B.归并排序
C.冒泡排序 D.直接选择排序

209、已知二叉排序树 G，要输出其结点的有序序列，则采用的遍历方法是（ C ）
A.按层遍历 B.前序遍历
C.中序遍历 D.后序遍历

210、用 ISAM 和 VSAM 组织的文件都属于（ B ）
A.散列文件 B.索引顺序文件
C.索引非顺序文件 D.多关键字文件

211、对序列 (15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为 (4，9，-1，8，20，7，15)，则用的排序方法是（ C ）
A.选择 B.快速
C.希尔 D.冒泡

212、当采用分块查找时，数据的组织方式为（ D ）
A.数据分成若干块，每块内数据有序

B.数据分成若干块，每块中数据个数必须相同
C.数据分成若干块，每块内数据有序，块间是否有序均可
D.数据分成若干块，每块内数据不必有序，但块间必须有序

213、下述编码中不是前缀码的是（ B ）
A.(00，01，10，11) B.(0，1，00，11)
C.(0，10，110，111) D.(1，01，000，001)

214、若一个栈以向量 V[1…n] 存储，初始栈顶指针 top 为 n+l，则 x 进栈的正确操作是（ A ）指针在最大下标以上
A.top=top-1 ；V[top]=x B.V[top]=x ；top=top+1
C.top=top+1 ；V[top]=x D.V[top]=x ；top=top-1

215、在一个以 head 为头结点指针的非空单循环链表中， p指针指向尾指针的条件是（ D)
A.p - > data = - 1 B.p - > next = NULL
C.p - > next - > next=head D.p - > next = head

216、一个算法的时间耗费的数量级称为该算法的 (D)

A．效率 B．难度
C．可实现性 D．时间复杂度

217、顺序表便于 (D)
A．插入结点 B．删除结点
C．按值查找结点 D．按序号查找结点

218、4．设以数组 A[0…m-1] 存放循环队列， front 指向队头元素，rear 指向队尾元素的下一个位置， 则当前队列中的元素个数为 (A )
A．(rear-front+m) ％m B．rear-front+1
C．(front-rear+m) ％m D．(rear-front) ％m

219、5．下列关于顺序栈的叙述中，正确的是 (A)
A．入栈操作需要判断栈满，出栈操作需要判断栈空
B．入栈操作不需要判断栈满，出栈操作需要判断栈空
C．入栈操作需要判断栈满，出栈操作不需要判断栈空
D．入栈操作不需要判断栈满，出栈操作不需要判断栈空

220、6．A 是一个 10×10 的对称矩阵， 若采用行优先的下三角压缩存储，第一个元素 a 0,0 的存储地址为 1，每个元素占一个存储单元，则 a 7,5 的地址为 (D)
A．25 B．26
C．33 D．34

221、树的后序遍历等价于该树对应二叉树的 ©
A．层次遍历 B．前序遍历
C．中序遍历 D．后序遍历

222、8．使用二叉线索树的目的是便于 (D)
A．二叉树中结点的插入与删除 B．在二叉树中查找双
亲
C．确定二叉树的高度 D．查找一个结点的前趋和后
继

223、9．设无向图的顶点个数为 n，则该图边的数目最多为 (B)

224、可进行拓扑排序的图只能是 ©
A．有向图 B．无向图
C．有向无环图 D．无向连通图

225、下列排序方法中稳定的是 (A)
A．直接插入排序 B．直接选择排序
C．堆排序 D．快速排序

226、12下列序列不为堆的是 ©
A．75,45,65,30,15,25 B．75,65,45,30,25,15
C．75,65,30,l5,25,45 D．75,45,65,25,30,15

227、13对线性表进行二分查找时，要求线性表必须是 ©
A．顺序存储 B．链式存储
C．顺序存储且按关键字有序 D．链式存储且按关键
字有序

228、14．分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是 (A)
A．(4,1,2,3,5) B．(4,2,3,l,5)
C．(4,5,2,1,3) D．(4,2,1,5,3)

229、下列关于 m 阶 B 树的叙述中，错误的是 (A)
A．每个结点至多有 m 个关键字
B．每个结点至多有 m 棵子树
C．插入关键字时，经过结点分裂使树高增加
D．删除关键字时经过结点合并使树高降低

230、数据的逻辑结构能够分为 ©

A．动态结构和静态结构 B.顺序结构和链式结构
C．线性结构和非线性结构 D.简单结构和构造结构

231、线性表是一个有限序列，组成线性表的基本单位是
A．数据项 B.数据元素 (B)
C．数据域 D.字符

232、栈中有 a、b 和 c 三个元素， a 是栈底元素， c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是 ©
A．dcba B.cbda
C．cadb D.cdba

233、稀疏矩阵的三元组表是 (A)
A．顺序存储结构 B.链式存储结构
C．索引存储结构 D.散列表存储结构

234、已知广义表 G，head(G)与 tail(G) 的深度均为 6，则 G 的深度是 ©
A．5 B.6
C．7 D.8

235、6．下列编码集合中，属于前缀编码的一组是 (B)
A.{11,10,001,101,0001} B.{00,010,0110,1000}
C.{11,01,001,0101,0001} D.{0,10,110,1011}

236、如题 7 图所示二叉树的中序序列为 (A)

237、8．有向图中所有顶点入度之和与所有顶点出度之和的比是 (B)
A．1/2 B.1
C．2 D.4

238、9．含有 n 个顶点和 e 条边的有向图的邻接矩阵中，零元素的个数是 (D)

239、n 个顶点的无向连通图，其生成树的边数为 (A)
A.n-l B.n
C.n+l D.nlogn

240、用自底向上的冒泡排序方法对序列 (8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为 C)
A．2 B.3
C．4 从大到下 自底向上排序 D.5

241、对序列 (8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是 (A)
A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)

242、采用分块查找时，要求数据 (B)
A．块内有序 B.分块有序
C．分块无序 D.每块中数据个数必须相同

243、下列关于散列函数的说法正确的是 (D)
A．散列函数越复杂越好
B.散列函数越简单越好
C．用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好

244、下列关于 m 阶 B 树的叙述中，错误的是
A．每个结点至多有 m 棵子树 (D)
B.每个结点至多有 m-1 个关键字
C．所有的叶结点均在同一层上

245、算法的时间复杂度表征的是 （C）

A．算法的可读性 B．算法的难易程度

C．执行算法所耗费的时间 D．执行算法所耗费的存储空间

246、对需要频繁插入和删除结点的线性表，适合的存储方式是 （B）
A．顺序储存 B．链式存储
C．索引存储 D．散列存储

247、4．迪杰斯特拉 (Dijkstra) 算法的功能是 （A）
A．求图中某顶点到其它顶点的最短路径 B．求图中所有顶点之间的最短路径
C．求图的最小生成树 D．求图的拓扑排序序列

248、5．若栈的进栈序列为 1， 2， 3，4，5，则经过出入栈操作不可能 获得的出栈序列是 （B）
A．4，5，3，2，1 B．4， 3，5，1， 2
C．1，2，3，4，5 D．5，4，3，2， 1

249、A 是 7×4 的二维数组， 按行优先方式顺序存储， 元素 A[0][0] 的存储地址为 1 000，若每个元素占 2 个字节，则元素 A[3][3]的存储地址为 （D）
A．1015 B．1016
C．1028 D．1030

250、7．深度为 4 的完全二叉树的结点数至少为 （B）
A．4 B．8
C．13 D．15

251、若采用邻接矩阵 A 存储有向图 G，则结点 k 的入度等于 A 中 （B）
A．结点 k 对应行元素之和 B．结点 k 对应列元素之和
C．结点 k 对应行和列元素之和 D．非零元素之和

252、9．无向图 G 的邻接矩阵一定是 （A）
A．对称矩阵 B．对角矩阵
C．三角矩阵 D．单位矩阵

253、10．下列关于有向带权图 G 的叙述中，错误的是 （D）
A．图 G 的任何一棵生成树都不含有回路
B．图 G 生成树所含的边数等于顶点数减 1
C．图 G 含有回路时无法得到拓扑序列
D．图 G 的最小生成树总是唯一的

254、11．在下列排序算法中，关键字比较次数与初始排列次序无关的是 （D）
A．冒泡排序 B．希尔排序
C．直接插入排序 D．直接选择排序

255、1 2．对下图进行拓扑排序，能够得到的拓扑序是 （B）

A．a b c d e B．b a c d e
C．b c a d e D．a b d c e

256、下列线性表中，能使用二分查找的是 （C）
A．顺序存储 (2,12,5,6,9,3,89,34,25)
B．链式存储 (2,12,5,6,9,3,89,34,25)
C．顺序存储 (2,3,5,6,9,12,25,34,89)
D．链式存储 (2,3,5,6,9,12,25,34,89)

257、14．在下列查找方法中，平均查找长度与结点数量无直接关系的是 （C）
A．顺序查找 B．分块查找
C．散列查找 D．基于 B 树的查找

258、下列排序算法中，时间复杂度为 O(nlog
2 n)的算法是 （A）
A．快速排序 B．冒泡排序
C．直接选择排序 D．直接插入排序

259、

260、下列选项中，不属于线性结构的是 （A）

A ．网 B ．栈 C ．队列 D ．线性表

261、长度为 n 的顺序表， 删除位置 i 上的元素 (0≤i ≤n 一 1) ，需要移动的元素个数为 （B）
A ．n—i B．n—i —l C ．i D ．i+1

262、栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 （Q）
A．顺序栈需要判定栈空，链栈也需要判定
B ．顺序栈需要判定栈空，而链栈不需要判定
C ．顺序栈不需要判定栈空，而链栈需要判定
D ．顺序栈不需要判定栈空，链栈也不需要判定

263、若一个栈以数组 V[0．．n-1] 存储，初始栈顶指针 top 为 n，则 x 入栈的正确操作是 （C）
A ．top=top+1 ； V[top]=x
B． V[top]=x ；top=top+1
C．top=top 一 1；V[mp]=x
D ． V[top]=x ；top=top —l

264、5．在二维数组 a[9][10] 中：每个数组元素占用 3 个存储空间，从首地址 SA开始按行优先连续存放，则元素 a[8][5] 的起始地址是 （D）
A ． SA+141
B． SA+144
C． SA+222
D．SA+255

265、广义表 A=(x，((y) ，((a)) ，A)) 的深度是 （D）
A ．2 B ．3 C ．4 D．∞

266、7一棵左子树为空的二叉树在前序线索化后，其空指针域个数为 （C）
A ．0 B ．1 C ．2 D ．不确定

267、8．下列关于哈夫曼树的叙述中，错误的是 （A）
A ．用 n 个结点构造的哈夫曼树是唯一的
B ．哈夫曼树中只有度为 0 或度为 2 的结点
C ．树中两个权值最小的结点可能是兄弟结点
D ．同一结点集构造的二叉树中，哈夫曼树的 WPL最小

268、9．6 个顶点的强连通图中，含有的边数至少是 （C）
A ．4 B ．5 C．6 D ．

269、

270、12有向图采用邻接矩阵存储，某一行中非零元素的个数等于 （B）
A ．对应顶点 v 的度
B．对应顶点 v 的出度

C ．对应顶点 v 的入度
D ．依附于对应顶点 v 的边数

271、下列选项中，符合堆定义的是 （C）
A ．{102，24，55，60，89，93}
B ．{24，89，55，60，93，102}
C．{102，93，55，60，89，24}
D ．{102，60。89，93，55，24}

272、14已知关键字序列为 {66，82，25，51，98，108}，利用快速排序方法，以第一个元素为基准得到的一趟排序结果为 （D）
A ．{25，51，66，82，98，108}
B ．{25，51，66，98，82，108}
C ．{51，25，66，108，98，82}
D．{51，25，66，82，98，108}

273、下列选项中，其平均查找性能与基于二叉排序树的查找相当的是 （A）
A．二分查找 B ．顺序查找 C ．分块查找 D ．索
引顺序查找

274、按值可否分解，数据类型通常可分为两类，它们是 ©
A. 静态类型和动态类型
B. 原子类型和表类型
C. 原子类型和结构类型
D. 数组类型和指针类型

275、

276、指针p、q和r 依次指向某循环链表中三个相邻的结点，交换结点 *q和结点 *r 在表中次序的程
序段是 ()
A. p->next=r ；q->next=r->next ；r->next=q ；
B. p->next=r ；r->next=q ；q->next=r->next ；
C. r->next=q ；q->next=r->next ；p->next=r ；
D. r->next=q ；p->next=r ；q->next=r->next ；
答案： A

277、若进栈次序为 a，b，c，且进栈和出栈可以穿插进行，则可能出现的含 3个元素的出栈序列个数是 (B)
A. 3
B. 5
C. 6
D. 7

278、假设以数组 A［n］存放循环队列的元素，其头指针 front 指向队头元素的前一个位置、尾指
针rear 指向队尾元素所在的存储位置，则在少用一个元素空间的前提下，队列满的判定条件为 ()
A. rearfront
B. (front+1) ％nrear
C. rear+1front
D. (rear+1) ％nfront
答案： D

279、

280、二维数组 A［10］［6］采用行优先的存储方法，若每个元素占 4个存储单元，已知元素
A［3］［4］的存储地址为 1000，则元素 A［4］［3］的存储地址为 ()
A. 1020
B. 1024
C. 1036
D. 1240
答案： A

281、对广义表 L= (a ，()) 执行操作 tail(L) 的结果是 ()
A. ()
B. (())
C. a
D. (a)
答案： B

282、已知二叉树的中序序列和后序序列均为 ABCDEF ，则该二叉树的先序序列为 ()
A. FEDCBA
B. ABCDEF
C. FDECBA
D. FBDCEA
答案： A

283、已知森林 F={T1，T2，T3，T4，T5}，各棵树 Ti(i=1 ，2，3，4，5)中所含结点的个数分别为7，3，5，1，2，则与 F对应的二叉树的右子树中的结点个数为 ()
A. 2
B. 3
C. 8
D. 1

284、若非连通无向图 G含有21条边，则 G的顶点个数至少为 ()
A. 7
B. 8
C. 21
D. 22
答案： B

285、

286、对关键字序列 (6，1，4，3，7，2，8，5) 进行快速排序时，以第 1个元素为基准的一次划分的结果为 ()
A. (5，1，4，3，6，2，8，7)
B. (5，1，4，3，2，6，7，8)
C. (5，1，4，3，2，6，8，7)
D. (8，7，6，5，4，3，2，1)
答案： C

287、分块查找方法将表分为多块，并要求 ()
A. 块内有序
B. 块间有序
C. 各块等长
D. 链式存储
答案： B

288、便于进行布尔查询的文件组织方式是 ()
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多关键字文件
答案： D

289、若一个算法的时间复杂度用 T(n) 表示，其中 n 的含义是（ A ）

A．问题规模 B．语句条数
C．循环层数 D．函数数量

290、具有线性结构的数据结构是（ C ）线性结构有：顺序表、栈和队列、串
A．树 B．图
C．栈和队列 D．广义表

291、将长度为 n 的单链表连接在长度为 m的单链表之后，其算法的时间复杂度为（ B ）
A．O(1) B． O(m)
C．O(n) D． O(m+n)
插入到长度为 m的单链表， 需找到表尾， 时间复杂度为 o(m)，连接的时间复杂度为 0(1), 所以总的时间复杂度为 0(m)

292、在带头结点的双向循环链表中插入一个新结点，需要修改的指针域数量是（ C ）
A．2 个 B． 3 个
C．4 个 D． 6 个

293、假设以数组 A[60] 存放循环队列的元素，其头指针是 front=47 ，当前队列有 50 个元素，则队列的尾指针值为（ B ）
A．3 B． 37
C．50 D． 97

294、若栈采用链式存储结构，则下列说法中正确的是（ B ）
A ．需要判断栈满且需要判断栈空
B．不需要判断栈满但需要判断栈空
C ．需要判断栈满但不需要判断栈空
D ．不需要判断栈满也不需要判断栈空
因为链栈中的结点是动态分配的，可以不考虑上溢，所以无需定义 stackFull 运算。

295、若串 str= ”Software ”，其子串的数目是（ D ）
A．8 B． 9
C．36 D． 37

296、设有一个 10 阶的下三角矩阵 A，采用行优先压缩存储方式， a ll 为第一个元素，其存储地址为 1000，每个元素占一个地址单元，则 a 85 的地址为 （ C ）
A．1012 B． 1017
C．1032 D． 1039

297、允许结点共享的广义表称为（ D ）
A．纯表 B．线性表
C．递归表 D．再入表

298、下列数据结构中，不属于二叉树的是（ A ）
A．B树 B树是一种平衡的多叉树 B． AVL树 AVL树是自平衡二叉查找树
C．二叉排序树 D．哈夫曼树 哈夫曼树是最优二叉树

299、

300、

301、
下列排序算法中不稳定的是（ A ）
A．快速排序 B．归并排序
C．冒泡排序 D．直接插入排序
稳定：直接插入、冒泡、归并、基数 不稳定：直接选择、希尔、快速、堆

302、一个有序表为 (1 ， 3，9，12，32， 41，45，62，75，77，82，95，100) ，当采用折半查找方法查找值 32 时，查找成功需要的比较次数是（ B ）mid1=45，mid2=9， mid3=32
A．2 B． 3
C．4 D． 8

303、采用 ISAM组织文件的方式属于（ D ）
A．链组织 B．顺序组织
C．散列组织 D．索引组织

304、数据的四种存储结构是 (A )

A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构
B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构
C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构
D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构

305、若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是 ( C )
A.无头结点的单向链表 B.带头结点的单向链表
C.带头结点的双循环链表 D.带头结点的单循环链表

306、4.若元素的入栈顺序为 1，2，3…，n，如果第 2个出栈的元素是 n，则输出的第 i(1<=i<=n) 个元素是 ( C )
A.n-i B.n-i+l
C.n-i+2 D.无法确定

307、5.串匹配算法的本质是 ( C )
A.串复制 B.串比较
C.子串定位 D.子串链接

308、6.设有一个 10阶的对称矩阵 A，采用行优先压缩存储方式， a 11 为第一个元素，其存储地址为
1，每个元素占一个字节空间，则 a 85 的地址为 ( C)
A.13 B.18
C.33 D.40

309、7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是 ( B )
A.树中没有度为 2的结点 B.树中只有一个根结点
C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树

400、A

401、在图 G中求两个结点之间的最短路径可以采用的算法是 ( A)
A.迪杰斯特拉（ Dijkstra ）算法 B.克鲁斯卡尔（ Kruskal）算法
C.普里姆 (Prim) 算法 D.广度优先遍历 (BFS)算法

402、D

403、B

404、12如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是 ( B )
A.不稳定的 B.稳定的
C.基于交换的 D.基于选择的

405、设有一组关键字 (19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数 H(key)=key%13 构造散列表，用拉链法解决冲突，散列地址为 1的链中记录个数为 ( C )
A.1 B.2
C.3 D.4

406、

407、15.若需高效地查询多关键字文件，可以采用的文件组织方式为 (D )
A.顺序文件 B.索引文件
C.散列文件 D.倒排文件

408、下列选项中与数据存储结构无关的术语是（ D）

A.顺序表 B.链表
C.链队列 D.栈

409、将两个各有 n 个元素的有序表归并成一个有序表，最少的比较次数是（B ）
A.n-1 B.n
C.2n-1 D.2n

410、3.已知循环队列的存储空间大小为 m，队头指针 front 指向队头元素，队尾指针 rear 指向队尾元素的下一个位置，则
向队列中插入新元素时，修改指针的操作是（ D）
A.rear=(rear-1)%m; B.front=(front+1)%m;
C.front=(front-1)%m; D.rear=(rear+1)%m ;

411、4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（A ）
A.堆栈 B.多维数组
C.队列 D.线性表

412、5.设有两个串 p 和 q，其中 q是 p 的子串，则求 q 在 p 中首次出现位置的算法称为（ ）C
A.求子串 B.串联接
C.串匹配 D.求串长

413、6.对于广义表 A，若 head(A)等于 tail(A) ，则表 A 为（B ）
A.( ) B.(( ))
C.(( ),( )) D.(( ),( ),( ))

414、7.若一棵具有 n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（C ）
A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树
C.高度为 n 的二叉树 D.存在度为 2 的结点的二叉树

415、若一棵二叉树中度为 l 的结点个数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是（B ）
A.4 B.5
C.7 D.8

416、9.下列叙述中错误的是（C ）
A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次
B.图的遍历可以采用深度优先遍历和广度优先遍历
C.图的广度优先遍历只适用于无向图
D.图的深度优先遍历是一个递归过程

417、已知有向图 G=(V ，E)，其中 V={V1 ，V2，V3，V4} ，E={<V1 ，V2> ，<V1，V3>，<V2，V3>，<V2，V4>，<V3，
V4>} ，图 G 的拓扑序列是（ A）
A.V1,V2,V3,V4 B.V1,V3,V2,V4
C.V1,V3,V4,V2 D.V1,V2,V4,V3

419、11.平均时间复杂度为 O(n log n)的稳定排序算法是（C ）
A.快速排序 B.堆排序
C.归并排序 D.冒泡排序

420、已知关键字序列为 (51， 22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（D ）
A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68)
C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83)

421、某索引顺序表共有元素 395 个，平均分成 5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在
等概率情况下， 分块查找成功的平均查找长度是 （ A）[[(2+80)/2+(3+81)/2+(4+82)/2+(5+83)/2+(6+84)/2]*79]/395
A.43 B.79
C.198 D.200

422、14在含有 10 个关键字的 3 阶 B-树中进行查找，至多访问的结点个数为（B ）
A.2 B.3
C.4 D.5

423、15.ISAM 文件系统中采用多级索引的目的是（A ）
A.提高检索效率 B.提高存储效率
C.减少数据的冗余 D.方便文件的修改

424、在数据的逻辑结构中，树结构和图结构都是（ A）

A.非线性结构 B.线性结构
C.动态结构 D.静态结构

425、在一个长度为 n 的顺序表中插入一个元素的算法的时间复杂度为（ C）

426、3.指针 p1 和 p2 分别指向两个无头结点的非空单循环链表中的尾结点，要将两个链表链接成一个新的单循环链表，应执行的操作为（ D）
A.p1 －＞ next=p2－＞ next;p2－＞ next=p1－＞ next;
B. p2－＞ next=p1－＞ next;p1－＞ next=p2－＞ next;
C. p=p2－＞ next; p1－＞ next=p;p2－＞ next=p1－＞ next;
D. p=p1 －＞ next; p1－＞ next= p2－＞ next；p2－＞ next=p;

427、4 设栈的初始状态为空，入栈序列为 1，2，3，4，5，6，若出栈序列为 2，4，3，6，5， 1，则操作过程中栈中元素个数最多时为（ B）
A.2 个 B.3 个
C.4 个 D.6 个

428、队列的特点是（D ）
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入，在另一端进行删除

429、6.一个链串的结点类型定义为
﹟define NodeSize 6
typedef struct node{
char data[NodeSize];
struct node*next;
}LinkStrNode;
如果每个字符占 1 个字节，指针占 2 个字节，该链串的存储密度为（D ）
A.1/3 B.1/2
C.2/3 D.3/4

430、广义表 A= （a,B,(a,B,(a,B,⋯⋯）））的长度为（ C）
A.1 B.2
C.3 D.无限值

431、8.已知 10×12 的二维数组 A，按“行优先顺序”存储，每个元素占 1 个存储单元，已知 A[1][1] 的存储地址为 420，
则 A[5][5] 的存储地址为（ C）
A.470 B.471
C.472 D.473

432、9.在一棵二叉树中，度为 2 的结点数为 15，度为 1 的结点数为 3，则叶子结点数为（ B）
A.12 B.16
C.18 D.20

433、10.在带权图的最短路径问题中，路径长度是指（ D）
A.路径上的顶点数 B.路径上的边数
C.路径上的顶点数与边数之和 D.路径上各边的权值之和

434、11.具有 n 个顶点、 e条边的无向图的邻接矩阵中，零元素的个数为（ C

435、要以 O（n log n）时间复杂度进行稳定的排序，可用的排序方法是（ A）
A.归并排序 B.快速排序
C.堆排序 D.冒泡排序

436、13.若希望在 1000 个无序元素中尽快求得前 10 个最大元素，应借用（A ）
A.堆排序 B.快速排序
C.冒泡排序 D.归并排序

437、14.对有序表进行二分查找成功时，元素比较的次数（ B）
A.仅与表中元素的值有关 B.仅与表的长度和被查元素的位置有关
C.仅与被查元素的值有关 D.仅与表中元素按升序或降序排列有关

438、散列文件是一种（ B）
A.顺序存取的文件 B.随机存取的文件
C.索引存取的文件 D.索引顺序存取的文件

439、每个结点有且仅有一个直接前趋和多个 (或无 )直接后继 (第一个结点除外 )的数据结构称为（ A ）

A.树状结构 B.网状结构
C.线性结构 D. 层次结构

439、某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是
（ D ）
A.单链表 B.双链表
C.仅有头指针的单循环链表 D. 仅有尾指针的单循环链表

440、.已知一个栈的入栈序列是 1，2，3，⋯，n，其输出序列为 p l ，p 2 ，p 3 ⋯.，p n ，若 p 1 是 n，则 p i 是（
C ）
A.i B.n-i
C.n-i+l D. 不确定

441、下面关于串的叙述中，正确的是（ A ）
A.串是一种特殊的线性表 B.串中元素只能是字母
C.空串就是空白串 D. 串的长度必须大于零

442、无向完全图 G 有 n 个结点，则它的边的总数为（ C ）

443、若一棵二叉树有 10 个度为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点数是（ B ）
A.9 B.11
C.15 D. 不确定

444、

445、无论待排序列是否有序，排序算法时间复杂度都是 O(n
2 )的排序方法是（D ）
A.快速排序 B.归并排序
C.冒泡排序 D. 直接选择排序

446、已知二叉排序树 G，要输出其结点的有序序列，则采用的遍历方法是（ C ）
A.按层遍历 B.前序遍历
C.中序遍历 D. 后序遍历

447、用 ISAM 和 VSAM 组织的文件都属于（ B ）
A.散列文件 B.索引顺序文件
C.索引非顺序文件 D. 多关键字文件

448、对序列 (15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为 (4， 9，-1， 8，20， 7，15)，则采用的排序方法是（ C ）
A.选择 B.快速
C.希尔 D. 冒泡

449、当采用分块查找时，数据的组织方式为（ D ）
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块中数据个数必须相同
C.数据分成若干块，每块内数据有序，块间是否有序均可
D.数据分成若干块，每块内数据不必有序，但块间必须有序

450、下述编码中不是前缀码的是（ B ）
A.(00 ，01，10， 11) B.(0， 1，00， 11)
C.(0，10，110，111) D.(1， 01，000，001)

451、若一个栈以向量 V[1…n] 存储，初始栈顶指针 top 为 n+l，则 x 进栈的正确操作是（ A ）指针在最大下标以上
A.top=top-1 ；V[top]=x
B.V[top]=x ；top=top+1
C.top=top+1 ；V[top]=x
D.V[top]=x ；top=top-1

452、数据的逻辑结构可以分为 （C）

A．动态结构和静态结构 B.顺序结构和链式结构
C．线性结构和非线性结构 D.简单结构和构造结构

453、2线性表是一个有限序列，组成线性表的基本单位是 （B）
A．数据项 B.数据元素
C．数据域 D.字符

454、3栈中有 a、b 和 c 三个元素， a 是栈底元素， c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是 （C）
A．dcba B.cbda
C．cadb D.cdba

455、4．稀疏矩阵的三元组表是 （A）
A．顺序存储结构 B.链式存储结构
C．索引存储结构 D.散列表存储结构

456、5．已知广义表 G，head(G)与 tail(G) 的深度均为 6，则 G 的深度是 （C）
A．5 B.6
C．7 D.8

457、6．下列编码集合中，属于前缀编码的一组是 （B）
A.{11,10,001,101,0001} B.{00,010,0110,1000}
C.{11,01,001,0101,0001} D.{0,10,110,1011}

458、A

459、有向图中所有顶点入度之和与所有顶点出度之和的比是 （B）
A．1/2 B.1
C．2 D.4

460、D

461、n 个顶点的无向连通图，其生成树的边数为 （A）
A.n-l B.n
C.n+l D.nlogn

462、11．用自底向上的冒泡排序方法对序列 (8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为 （C）
A．2 B.3
C．4 从大到下 自底向上排序 D.5

463、对序列 (8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是 （A）
A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)

464、13采用分块查找时，要求数据 （B）
A．块内有序 B.分块有序
C．分块无序 D.每块中数据个数必须相同

465、下列关于散列函数的说法正确的是 （D）
A．散列函数越复杂越好
B.散列函数越简单越好
C．用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好

466、15下列关于 m 阶 B 树的叙述中，错误 的是 （D）
A．每个结点至多有 m 棵子树
B.每个结点至多有 m-1 个关键字
C．所有的叶结点均在同一层上
D.根结点至少有 / 2 m棵子树

467、算法的时间复杂度表征的是 ©

A．算法的可读性 B．算法的难易程度
C．执行算法所耗费的时间 D．执行算法所耗费的存储空间

468、2对需要频繁插入和删除结点的线性表，适合的存储方式是 (B)
A．顺序储存 B．链式存储
C．索引存储 D．散列存储

469、4．迪杰斯特拉 (Dijkstra) 算法的功能是 (A)
A．求图中某顶点到其他顶点的最短路径 B．求图中所有顶点之间的最短路径
C．求图的最小生成树 D．求图的拓扑排序序列

470、5若栈的进栈序列为 1，2，3，4，5，则经过出入栈操作不可能 获得的出栈序列是 (A)
A．4，5，3，2， 1 B．4， 3，5，1， 2
C．1，2，3，4， 5 D．5，4，3，2， 1

471、6．A 是 7×4 的二维数组， 按行优先方式顺序存储， 元素 A[0][0] 的存储地址为 1 000，若每个元素占 2 个字节，则元素 A[3][3]的存储地址为 (D)
A．1015 B．1016
C．1028 D．1030

472、7．深度为 4 的完全二叉树的结点数至少为 (B)
A．4 B．8
C．13 D．15

473、若采用邻接矩阵 A 存储有向图 G，则结点 k 的入度等于 A 中 (B)
A．结点 k 对应行元素之和 B．结点 k 对应列元素之和
C．结点 k 对应行和列元素之和 D．非零元素之和

474、9．无向图 G 的邻接矩阵一定是 (B)
A．对称矩阵 B．对角矩阵
C．三角矩阵 D．单位矩阵

475、10．下列关于有向带权图 G 的叙述中，错误
．． 的是 (D)
A．图 G 的任何一棵生成树都不含有回路
B．图 G 生成树所含的边数等于顶点数减 1
C．图 G 含有回路时无法得到拓扑序列
D．图 G 的最小生成树总是唯一的

476、11．在下列排序算法中，关键字比较次数与初始排列次序无关的是 (D)
A．冒泡排序 B．希尔排序
C．直接插入排序 D．直接选择排序

477、B

478、下列线性表中，能使用二分查找的是 ©
A．顺序存储 (2,12,5,6,9,3,89,34,25) B．链式存储 (2,12,5,6,9,3,89,34,25)
C．顺序存储 (2,3,5,6,9,12,25,34,89) D．链式存储 (2,3,5,6,9,12,25,34,89)

479、在下列查找方法中，平均查找长度与结点数量无直接关系的是 ©
A．顺序查找 B．分块查找
C．散列查找 D．基于 B 树的查找

480、下列排序算法中，时间复杂度为 O(nlog 2 n)的算法是 (A)
A．快速排序 B．冒泡排序
C．直接选择排序 D．直接插入排序

481、D

482、B

483、12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是 (B )
A.不稳定的 B.稳定的
C.基于交换的 D.基于选择的

484、13.设有一组关键字 (19,14,23,1，6，20,4，27,5，11,10,9)，用散列函数 H(key)=key%13 构造散列表，用拉链法解决冲突，散列地址为 1的链中记录个数为 ( C )
A.1 B.2
C.3 D.4

485、

486、若需高效地查询多关键字文件，可以采用的文件组织方式为 ( D )
A.顺序文件 B.索引文件
C.散列文件 D.倒排文件

487、13.若希望在 1000 个无序元素中尽快求得前 10 个最大元素，应借用（）
A.堆排序 B.快速排序
C.冒泡排序 D.归并排序

488、10.在带权图的最短路径问题中，路径长度是指（）
A.路径上的顶点数 B.路径上的边数
C.路径上的顶点数与边数之和 D.路径上各边的权值之和

489、7.广义表 A= （a,B,(a,B,(a,B, ） ））的长度为（）
A.1 B.2
C.3 D.无限值

490、5.队列的特点是（D）
A.允许在表的任何位置进行插入和删除
B.只允许在表的一端进行插入和删除
C.允许在表的两端进行插入和删除
D.只允许在表的一端进行插入，在另一端进行删除

491、4.设栈的初始状态为空，入栈序列为 1，2，3，4，5，6，若出栈序列为 2，4，3，6，5， 1，则操作过程中栈中元素
个数最多时为（B）
A.2 个 B.3 个
C.4 个 D.6 个

492、1在数据的逻辑结构中，树结构和图结构都是（A）
A.非线性结构 B.线性结构
C.动态结构 D.静态结构

493、每个结点有且仅有一个直接前趋和多个 (或无 )直接后继 (第一个结点除外 )的数据结构称为（ A）
A.树状结构 B.网状结构
C.线性结构 D. 层次结构

494、某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素， 则最节省运算时间的存储结构（D）
A.单链表 B.双链表
C.仅有头指针的单循环链表 D. 仅有尾指针的单循环链表

495、.已知一个栈的入栈序列是 1，2，3，⋯，n，其输出序列为 p l ，p 2 ，p 3 ⋯.，p n ，若 p 1 是 n，则 p i 是（ C）
A.i B.n-i
C.n-i+l D. 不确定

496、下面关于串的叙述中，正确的是（ A）
A.串是一种特殊的线性表 B.串中元素只能是字母
C.空串就是空白串 D. 串的长度必须大于零

497、无向完全图 G 有 n 个结点，则它的边的总数为（ C）
A.n2
B.n(n-1)
C.n(n-1)/2 D.(n-1)

498、.若一棵二叉树有 10 个度为 2 的结点， 5 个度为 1 的结点，则度为 0 的结点数是（ B）
A.9 B.11
C.15 D. 不确定

499、

501、无论待排序列是否有序，排序算法时间复杂度都是 O(n
2 )的排序方法是（D）
A.快速排序 B.归并排序
C.冒泡排序 D. 直接选择排序

502、已知二叉排序树 G，要输出其结点的有序序列，则采用的遍历方法是（ C）
A.按层遍历 B.前序遍历
C.中序遍历 D. 后序遍历

503、用 ISAM 和 VSAM 组织的文件都属于（ B）
A.散列文件 B.索引顺序文件
C.索引非顺序文件 D. 多关键字文件

504、对序列 (15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为 (4， 9，-1， 8，20， 7，15)，则采用的排序方法是（ C）
A.选择 B.快速
C.希尔 D. 冒泡

505、当采用分块查找时，数据的组织方式为（ D）
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块中数据个数必须相同
C.数据分成若干块，每块内数据有序，块间是否有序均可
D.数据分成若干块，每块内数据不必有序，但块间必须有序

506、下述编码中不是前缀码的是（ B）
A.(00 ，01，10， 11) B.(0， 1，00， 11)
C.(0，10，110，111) D.(1， 01，000，001)

507、1．一个算法的时间耗费的数量级称为该算法的 （D）
A．效率 B．难度
C．可实现性 D．时间复杂度

508、2顺序表便于 （B）
A．插入结点 B．删除结点
C．按值查找结点 D．按序号查找结点

509、4．设以数组 A[0…m-1] 存放循环队列， front 指向队头元素， rear 指向队尾元素的下一个位置，则当前队列中的元素个数为 （A）
A．(rear-front+m) ％m B． rear-front+1
C．(front-rear+m) ％m D． (rear-front) ％m

510、5．下列关于顺序栈的叙述中，正确的是 （A）
A．入栈操作需要判断栈满，出栈操作需要判断栈空
B．入栈操作不需要判断栈满，出栈操作需要判断栈空
C．入栈操作需要判断栈满，出栈操作不需要判断栈空
D．入栈操作不需要判断栈满，出栈操作不需要判断栈空

511、6．A 是一个 10×10 的对称矩阵，若采用行优先的下三角压缩存储，第一个元素 a 0,0 的存储地址为
1，每个元素占一个存储单元，则 a 7,5 的地址为 （D）
A．25 B． 26
C．33 D． 34

512、7．树的后序遍历等价于该树对应二叉树的 （C）
A．层次遍历 B．前序遍历
C．中序遍历 D．后序遍历

513、使用二叉线索树的目的是便于 （D）
A．二叉树中结点的插入与删除 B．在二叉树中查找双亲
C．确定二叉树的高度 D．查找一个结点的前趋和后继

514、9设无向图的顶点个数为 n，则该图边的数目最多为 （B）
A．n-l B． n(n-1)／2
C．n(n+1)／2 D． n
2

515、10．可进行拓扑排序的图只能是 （C）
A．有向图 B．无向图
C．有向无环图 D．无向连通图

516、11．下列排序方法中稳定的是 （A）
A．直接插入排序 B．直接选择排序
C．堆排序 D．快速排序

517、12．下列序列不为 堆的是 （C）
A．75,45,65,30,15,25 B． 75,65,45,30,25,15
C．75,65,30,l5,25,45 D． 75,45,65,25,30,15

518、13．对线性表进行二分查找时，要求线性表必须是 （C）
A．顺序存储 B．链式存储
C．顺序存储且按关键字有序 D．链式存储且按关键字有序

519、分别用以下序列生成二叉排序树，其中三个序列生成的二叉排序树是相同的，不同的序列是 （A）
A．(4,1,2,3,5) B． (4,2,3,l,5)
C．(4,5,2,1,3) D． (4,2,1,5,3)

520、15．下列关于 m 阶 B 树的叙述中，错误 的是
A．每个结点至多有 m 个关键字 （A）
B．每个结点至多有 m 棵子树
C．插入关键字时，通过结点分裂使树高增加
D．删除关键字时通过结点合并使树高降低

521、1．数据的逻辑结构可以分为 ©

A．动态结构和静态结构 B.顺序结构和链式结构
C．线性结构和非线性结构 D.简单结构和构造结构

522、线性表是一个有限序列，组成线性表的基本单位是 (B)
A．数据项 B.数据元素
C．数据域 D.字符

523、3．栈中有 a、b 和 c 三个元素， a 是栈底元素， c 是栈顶元素，元素 d 等待进栈，则不可能的出栈序列是 ©
A．dcba B.cbda
C．cadb D.cdba

524、4．稀疏矩阵的三元组表是 (A)
A．顺序存储结构 B.链式存储结构
C．索引存储结构 D.散列表存储结构

525、已知广义表 G，head(G)与 tail(G) 的深度均为 6，则 G 的深度是 ©
A．5 B.6
C．7 D.8

526、6．下列编码集合中，属于前缀编码的一组是 (B)
A.{11,10,001,101,0001} B.{00,010,0110,1000}
C.{11,01,001,0101,0001} D.{0,10,110,1011}

527、 (A)

528、8．有向图中所有顶点入度之和与所有顶点出度之和的比是 (B)
A．1/2 B.1
C．2 D.4

529、 (D)

530、n 个顶点的无向连通图，其生成树的边数为 (A)
A.n-l B.n
C.n+l D.nlogn

531、11．用自底向上的冒泡排序方法对序列 (8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为 ©
A．2 B.3
C．4 从大到下自底向上排序 D.5

532、12．对序列 (8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是 (A)
A.(13,44,55,26,8,29) B.(13,26,55,44,8,29)
C.(8,13,26,29,44,55) D.(29,26,8,44,55,13)

533、13．采用分块查找时，要求数据 (B)
A．块内有序 B.分块有序
C．分块无序 D.每块中数据个数必须相同

534、14.下列关于散列函数的说法正确的是 (D)
A．散列函数越复杂越好
B.散列函数越简单越好
C．用除余法构造的散列函数是最好的
D.在冲突尽可能少的情况下，散列函数越简单越好

535、15.下列关于 m 阶 B 树的叙述中，错误 的是 (D)
A．每个结点至多有 m 棵子树
B.每个结点至多有 m-1 个关键字
C．所有的叶结点均在同一层上
D.根结点至少有 / 2 m棵子树

536、1算法的时间复杂度表征的是 ©

A．算法的可读性 B．算法的难易程度
C．执行算法所耗费的时间 D．执行算法所耗费的存储空间

537、4．迪杰斯特拉 (Dijkstra) 算法的功能是 (A)
A．求图中某顶点到其他顶点的最短路径 B．求图中所有顶点之间的最短路径
C．求图的最小生成树 D．求图的拓扑排序序列

538、5．若栈的进栈序列为 1，2，3，4，5，则经过出入栈操作不可能获得的出栈序列是 (B)
A．4，5，3，2， 1 B．4， 3，5，1， 2
C．1，2，3，4， 5 D．5，4，3，2， 1

539、6．A 是 7×4 的二维数组， 按行优先方式顺序存储， 元素 A[0][0] 的存储地址为 1 000，若每个元素占 2 个字节，则元素 A[3][3]的存储地址为 (D)
A．1015 B．1016
C．1028 D．1030

540、7深度为 4 的完全二叉树的结点数至少为 (B)
A．4 B．8
C．13 D．15

541、8\若采用邻接矩阵 A 存储有向图 G，则结点 k 的入度等于 A 中 (B)
A．结点 k 对应行元素之和 B．结点 k 对应列元素之和
C．结点 k 对应行和列元素之和 D．非零元素之和

542、13．下列线性表中，能使用二分查找的是 ©
A．顺序存储 (2,12,5,6,9,3,89,34,25) B．链式存储 (2,12,5,6,9,3,89,34,25)
C．顺序存储 (2,3,5,6,9,12,25,34,89) D．链式存储 (2,3,5,6,9,12,25,34,89)

543、14．在下列查找方法中，平均查找长度与结点数量无直接关系的是 ©
A．顺序查找 B．分块查找
C．散列查找 D．基于 B 树的查找

544、1.与数据存储结构无关的概念是

A.栈 B.链表
C.顺序表 D.二叉链表

545、2.顺序表中有 10 个数据元素，若第一个元素的存储地址是 1000，则最后一个元素地址是 1036，第 5 个元素的地址是
A．1010 B.1016
C.1018 D.1019

546、3.设栈的初始状态为空，元素 1、2、 3、4、5、6 依次入栈，得到的出栈序列是（ 2,4,3,6,5,1） ,则栈的容量至少是
A.2 B.3
C.4 D…6

547、5.对稀疏矩阵进行压缩存储的目的是
A.便于运算 B.节省存储空间
C.便于输入输出 D.降低时间复杂度

548、6.一棵二叉树的第 7 层上最多含有的结点数为
A.14 B.64
C.127 D.128

549、

551、8.用邻接表表示 n 个顶点 e 条边的无向图 ,其边表结点的总数是
A.n ×e B.e
C.2e D.n+e

552、9.无向图中所有顶点的度数之和与所有边数之比是
A.1/2 B.1
C.2 D.4

553、10.采用邻接矩阵存储图时 ,广度优先搜索遍历算法的时间复杂度为
A.O （n） B.O（n+e）
C.O（n
2 ）
D. O（n 3 ）

554、11.对序列（ 15,9,7,8,20,-1,4）进行排序 ,若一趟排序后的结果为（ - 1,15,9,7,8,20,4）,则采用的排序方法是
A.归并排序 B.快速排序
C.直接选择排序 D.冒泡排序

555、12.比较次数与待排序列初始状态无关的排序方法是
A.快速排序 B.冒泡排序
C.直接插入排序 D.直接选择排序

556、13.查找较快 ,且插入和删除操作也比较方便的查找方法是
A.分块查找 B.二分查找
C.顺序查找 D.折半查找

557、15.在散列查找中处理冲突时 ,可以采用开放定址法。下列不是开放定址法的是

A.线性探查法 B.二次探查法
C.双重散列法 D.拉链法

558、1.在顺序表中查找第 i 个元素，时间效率最高的算法的时间复杂度为 ( A)

559、树形结构中，度为 0 的结点称为 ( A)
A.树根 B.叶子
C.路径 D.二叉树
560、

561、4.有关图中路径的定义，表述正确的是 ( A)
A.路径是顶点和相邻顶点偶对构成的边所形成的序列
B.路径是不同顶点所形成的序列
C.路径是不同边所形成的序列
D.路径是不同顶点和不同边所形成的集合

562、5.串的长度是指 ( B )
A.串中所含不同字母的个数 B.串中所含字符的个数
C.串中所含不同字符的个数 D.串中所含非空格字符的个数

563、B

564、8.与串的逻辑结构不同的 数据结构是 (D)
A.线性表 B.栈
C.队列 D.树

565、C

566、10.设单链表中指针 p 指向结点 A，若要删除 A 的直接后继，则所需修改指针的操作为( A )
A.p->next=p->next->next B.p=p->next
C.p=p->next->next D.p->next=p

567、11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是 ( C)
A.堆排序 B.冒泡排序
C.直接插入排序 D.快速排序

568、12.设字符串 S1=″ ABCDEFG ″， S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后 S的结果为 ( D )
A.″ BCQR″ B.″BCDEF ″
C.″ BCDEFG ″ D.″BCDEFEF ″

569、13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并且 A 的左孩子的平衡因子为 -1，右孩子的平衡因子为 0，则使其平衡的调整方法为 ( B )
A.LL 型 B.LR 型
C.RL 型 D.RR 型

570、14.如果结点 A 有 3 个兄弟结点，而且 B 为 A 的双亲，则 B 的度为 ( C)
A.1 B.3
C.4 D.5

571、15.数据表 A 中每个元素距其最终位置较近，则最省时间的排序算法是 (B )
A.堆排序 B.插入排序
C.直接选择排序 D.快速排序

572、B

573、D

574、4．顺序存储的表中有 90000个元素， 已按关键字值升序排列， 假设对每个元素进行查找的概率相同， 且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为 ( C)
A．25000 B.30000
C.45000 D.90000

575、5．散列文件是一种 ( D )
A．顺序文件 B.索引文件
C.链接文件 D.计算寻址文件

576、B

577、常用于函数调用的数据结构是 ( A)
A.栈 B.队列
C.链表 D.数组

578、8．二维数组 A［n］［m］以列优先顺序存储，数组 A 中每个元素占用 1 个字节， A［1］［1］为首元素，其地址为 0，则元素 A［i］［j］的地址为 ( B)
A.（ i-1）× m+(j-1) B.(j-1)× n+(i-1)
C.(j-1)×n+i D.j×n+i

579、9.图的广度优先搜索使用的数据结构是 ( A )
A．队列 B.树
C.栈 D.集合

581、10．序列（ 21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为 ( A)
A．(19，21，37，5，2) B.(21，19，5，37，2)
C.(21，19，37，2，5) D.(2，21，19，37，5)

582、11．数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为 ( D)
A．索引存储方法 B.顺序存储方法
C.链式存储方法 D.散列存储方法

583、12．在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的 ( B )
A．直接前趋 B.直接后继
C.开始结点 D.终端结点

584、C

585、在链队列中执行入队操作， ( D)
A．需判别队是否空 B.需判别队是否满
C.限制在链表头 p 进行 D.限制在链表尾 p 进行

586、15．一整数序列 26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为 ( B)
A.31， 51，11，42，26，77，59，19 B.26，59，31，77，11，51，19，42
C.11， 19，26，31，42， 59，51，77 D.26，11，19，31，51，59，77，42

587、若要描述数据处理的变化过程，其正确的次序应为（A）

A.处理要求、基本运算和运算、算法
B.处理要求、算法 、基本运算和运算
C.基本运算和运算、处理要求、算法
D.算法、处理要求、基本运算和运算

588、从运算类型角度考虑，属于引用型的运算是 （C）
A.插入、删除
B.删除、修改
C.查找、读取
D.查找删除

589、3、若在长度为n的顺序表中插入一个结点，则其结点的移动次数 （A）
A.最少为0，最多为n
B.最少为1，最多为n
C.最少为0，最多为n+1
D.最少为1，最多为n

590、若有一串数字5,6,7，8人栈，则其不可能的输出序列为 （C）
A.5,6,7,8 B.8,7,6,5 C.8,7,5，6 D.5,6,8,7
591、B

592、B

593、B

594、C

595、B

596、B

597、D

598、C

599、A 、C

600、
1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（ C）
A.逻辑结构、存储结构、机外表示 B.存储结构、逻辑结构、机外表示
C.机外表示、逻辑结构、存储结构 D.机外表示、存储结构、逻辑结构

2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（B ）
A.对数阶量级复杂性大于线性阶量级
B.对数阶量级复杂性小于线性阶量级
C.对数阶量级复杂性等于线性阶量级
D.两者之间无法比较

3.下列关于线性表的基本操作中，属于加工型的操作是（B ）
A.初始化、求表长度、插入操作 B.初始化、插入、删除操作
C.求表长度、读元素、定位操作 D.定位、插入、删除操作

4.在一个单链表中， 若 p 所指结点不是最后结点， s指向已生成的新结点，则在 p 之后插入 s 所指结点的正确操作是（ A）
A.s–>next=p –>next; p –>next=s; B.p–>next=s –>next; s–>next=p;
C.s–>next=p; p –>next=s; D.s–>next=p –>next; p=s;

5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（ C）
A.3 种 B.4 种
C.5种 D.6 种

6.C语言对数组元素的存放方式通常采用（ A）
A.按行为主的存储结构 B.按列为主的存储结构
C.按行或列为主的存储结构 D.具体存储结构无法确定

7.根据定义，树的叶子结点其度数（B ）
A.必大于 0 B.必等于 0
C.必等于 1 D.必等于 2

8.二叉树若采用二叉链表结构表示，则对于 n 个结点的二叉树一定有（B ）
A.2n 个指针域其中 n 个指针为 NULL
B.2n 个指针域其中 n+1 个指针为 NULL
C.2n-1 个指针域其中 n 个指针为 NULL
D.2n-1 个指针域其中 n+1 个指针为 NULL

9.在一个无向图中，所有顶点的度数之和等于边数的（B ）
A.1 倍 B.2 倍
C.3倍 D.4 倍

10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（A ）
A.先根遍历 B.中根遍历
C.后根遍历 D.层次遍历

11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为（C ）
A.从第 0 个元素开始往后查找该数据元素
B.从第 1 个元素开始往后查找该数据元素
C.从第 n 个元素开始往前查找该数据元素
D.从第 n+1 个元素开始往前查找该数据元素

12.下列查找中，效率最高的查找方法是（B）
A.顺序查找 B.折半查找
C.索引顺序查找 D.分块查找

13.索引文件通常由索引表和主文件两部分构成，其中（ C）
A.索引表和主文件均必须是有序文件
B.索引表和主文件均可以是无序文件
C.索引表必须是有序文件
D.主文件必须是有序文件

14.直接插入排序算法，其时间复杂性为（D ）
A.O(1) B.O(n)
C.O(nlog 2 n) D.O(n2 )