一、填空题（每空1分 ）
1、组成数据的基本单位是（数据元素）。
2、栈和队列的共同点是（只允许在端点处插入和删除元素）。
3、算法设计的原则是（正确性）、（可读性）、（健壮性）及（效率和低存储要求）。
4、ADT（Abstract Data Type），即称为（抽象数据类型），是指一个数学模型及定义在该模型上的
一组操作（运算）；ADT只考虑数据的（一组逻辑特性）。 5、算法分析的两个主要方面是（空间复杂性）和（时间复杂性）。 6、所有能输入到计算机中去的描述客观事物的符号，称为（数据）。
7、线性表a是n 个类型相同数据元素的有限序列，通常记作（（a0,a1,...ai-1,ai,ai+1,...,an））。 8、若线性表第一个元素的存储地址是102，每个元素的长度为4，则第5个元素的地址是：(118) 9、在插入排序、选择排序、快速排序和归并排序等方法中，平均查找长度最小的是：（快速排序） 10、线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中
元素的先后关系，每个元素除了需要存储自身的信息外还需保存（指示其直接后继的信息）或（直接后继元素）的存储位置。
11、数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为： （节点）。
12、线性结构中元素之间存在（一对一）关系,树形结构中元素之间存在（一对多）关系,图形结构中
元素之间存在（多对多）关系。
13、数据结构是研究数据的（物理结构）与（逻辑结构）以及它们之间的相互关系。 14、线性的数据结构包括：（线性表）、（栈）、（队列）、（数组）和（串）。 15、在一棵高度为k的满二叉树中，结点总数为（2k-1）。
16、判定一个栈ST(最多元素为m0)为栈满的条件是（s.top-s.base>=s.stacksize）。 17、头结点是指：（在单链表的第一个结点之前附设一个结点），称为头结点。
18、在线性结构中,第一个结点（没有）前驱结点,其余每个结点有且只有（一个）个前驱结点；最后
一个结点（没有）后续结点,其余每个结点有且只有（一个）个后续结点。
19、在树形结构中,树根结点没有（前驱）结点,其余每个结点有且只有（一个）个前驱结点；叶子结
点没有（后继）结点,其余每个结点的后续结点可以（任意个）。
20、数据结构被形式地定义为（D, R），其中D是(数据元素)的有限集合，R是D上的 关系有限集合。 21．在各种查找方法中,平均查找长度与结点个数n无关的查法方法是（哈希表查找法）
第1页共 页
22、哈夫曼树是带权路径长度 最小 的二叉树，又称最优二叉树。 二、选择题（每题1分 ）
1、树是结点的集合，它的根结点数目是 A 。 A)有且只有1 B)1或多于 C)0或1 D)至少2
2、线性表L=(a1，a2，a3，?ai，?an)，下列说法正确的是 D 。
A) 每个元素都有一个直接前件和直接后件 B) 线性表中至少要有一个元素 C) 表中诸元素的排列顺序必须是由小到大或由大到小
D) 除第一个元素和最后一个元素外，其余每个元素都有一个且只有一个直接前件和直接后件 3、栈底至栈顶依次存放元素A、B、C、D，在第五个元素E入栈前，栈中元素可以出栈，则出栈序列
可能是 B 。
A) ABCED B) DCBEA C) DBCEA D) CDABE 4、 n个顶点的连通图中边的条数至少为 C 。 A) 0 B) 1 C) n-1 D) n
5、在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A 。 A) 冒泡排序 B) 选择排序 C) 快速排序 D) 归并排序 6、希尔排序属于 D 。
A) 交换排序 B) 归并排序 C) 选择排序 D) 插入排序 7、由３个结点所构成的二叉树有 D 种形态。 A）3 B）2 C） 1 D）5
8、非空的循环单链表head的尾结点(由p所指向)，满足 C 。 A) p→next==NULL B) p==NULL C) p→next=head D) P=head
9、数据结构作为计算机的一门学科，主要研究数据的逻辑结构、对各种数据结构进行的运算，以及
A 。
A)数据的存储结构 B)计算方法 C)数据映象 D)逻辑存储
10、 n个顶点的强连通图的边数至少有 C 。 A) n-1 B) n(n-1) C) n D) n+l 11、循环链表的主要优点是 B 。
A) 不再需要头指针了 B) 从表中任一结点出发都能访问到整个链表 C) 在进行插入、删除运算时，能更好的保证链表不断开
第 页 2 共 23 页
D) 已知某个结点的位置后，能够容易的找到它的直接前件 12、栈和队列的共同特点是 C 。 A)都是先进先出 B)都是先进后出 C)只允许在端点处插入和删除元素 D)没有共同点
13、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98)，当顺序查找值为29和90的元素
时，分别需要 A 次比较才能查找成功。
（A）5次和10次 （B）10次和5次 （C）5次和9次 （D）10次和4次
14、设一棵完全二叉树具有1000个结点，则此完全二叉树有 D 个叶子结点，度为2的结点有C
个。
（A）1000 （B）501 （C） 499 （D）500 （E）0 （F）1 15、用链表表示线性表的优点是 C 。
A)便于随机存取 B)花费的存储空间较顺序存储少 C)便于插入和删除操作 D)数据元素的物理顺序与逻辑顺序相同 16、下列叙述中正确的是 A 。
A) 线性表是线性结构 B) 栈与队列是非线性结构 C) 线性链表是非线性结构 D) 二叉树是线性结构 17、深度为5的满二叉树中，叶子结点的个数为 C 。 A)32 B)31 C)16 D)15
18、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 C 。 （A） edcba（B）decba（C）dceab （D）abcde 19、为了方便插入一个元素,数据结构宜用 B 结构。
（A）顺序存储 （B）链式存储 （C） 指针存储 （D）数组存储
20、拓扑排序算法是通过重复选择具有0个前驱顶点的过程来完成的。图的BFS生成树的树高比DFS
生成树的树高 A 。
（A）小或相等 （B）大或相等 （C）小或不相等 （D）大或不相等 21、数据结构的三要素是指_ B__。 （A）数据元素、顺序存储、存储结构
（B）数据元素、逻辑结构、存储结构
第 页 3 共 23 页
（C）顺序存储、链式存储、存储结构 （D）数据元素、逻辑结构、链式存储
22、己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需
要_ C __比较才能查找成功。
（A）4次和2次 （B）3次和4次 （C）4次和4次 （D）3次和5次
23、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ A __个
元素。
（A）n－i+1 （B）n+i+1 （C）n－i （D） n+1
24、 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行 B （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p;
25、设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过
PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_ B __。 （A）16 （B）23 （C） 28 （D）20
26、设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素，最好用_ B_ _ 排
序法。
（A）快速排序 （B）堆排序 （C）插入排序 （D）选择排序 27、设有一批数据元素,为了最快的存储某元素,数据结构宜用_ A__结构, （A）顺序存储 （B）链式存储 （C） 指针存储 （D）数组存储 28、一棵具有２５７个结点的完全二叉树，它的深度为_ D__。 （A）6 （B）7 （C） 8（D）9
29、一个有n个顶点的无向图最多有_C__条边。
（A）n(n-1) （B）n /2 （C） n(n-1)/2 （D） (n-1)/2 30、在计算机中，算法是指_B__
A)加工方法 B)解题方案的准确而完整的描述 C)排序方法 D)查询方法 31. 引入二叉线索树的目的是（A）
A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 32．设无向图的顶点个数为n，则该图最多有（B）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
第 页 4 共 23 页
33．下面哪一方法可以判断出一个有向图是否有环（B）：
A．广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径
34、设计一个判别表达式中左，右括号是否配对出现的算法，采用__D__数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈
35、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为__A__。 A．CBEFDA B． FEDCBA C． CBEDFA D．不定
36、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：__C___ A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构 37、 广度优先遍历类似于二叉树的__D____ 。
A．先序遍历 B. 中序遍历 C. 后序遍历 D. 层次遍历 38、以下与数据的存储结构无关的术语是__D___。
A．循环队列 B. 链表 C. 哈希表 D. 栈
39、 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 , 则T中的叶子数为__D___ A．5 B．6 C．7 D．8
三、判断题（ 正确在括号内打“√”，错的打“X”。 ）
1、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻（X） 2、对任何数据结构链式存储结构一定优于顺序存储结构。(X) 3、有向图的邻接矩阵必定不是对称矩阵。(X) 4、归并排序要求内存量比较大。(√)
5、栈和链表是两种相同的数据结构。(√) 6、线性表在物理存储空间中也不一定是连续的。(√) 7、数据的逻辑结构是指数据在计算机内的实际存储形式。(X) 8、树的后根遍历序列等同于该树对应的二叉树的中序遍历。(√ ) 9、栈是实现过程和函数等子程序所必需的结构。(√) 10、栈和队列的存储方式只能是链接方式。（X） 11、线性表在物理存储空间中也一定是连续的。（X ）
12、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。(√) 13、二叉树是一般树的特殊情形。(X ) 14、栈和队列是一种非线性数据结构。(X)
15、一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。(X ) 16、在中序线索二叉树中，每一非空的线索均指向其祖先结点。(√ )
第 页 5 共 23 页