一、单选题
1.线性表是具有n个（ C ）的有限序列（n≥0 ）.
Ａ.表元素 Ｂ.字符 Ｃ.数据元素 Ｄ.数据项 2.链式栈与顺序栈相比，一个比较明显的优点是（ B ）。 A．插入操作更加方便 B. 通常不会出现栈满的情况 C．不会出现栈空的情况 D. 删除操作更加方便
3.若让元素１，２，３依次进栈，则出栈次序不可能出现（ C ）种情况。 A.3,2,1 B.2,1,3 C.3,1,2 D.1,3,2 4.在一棵具有5层的满二叉树中结点总数为（ A ）。
A. 31 B. 32 C. 33 D. 16 5、在一个图中，所有顶点的度数之和等于所有边数的（ A ）倍。 A．2 B．1 C．3 D．4 6. 设有100个数据元素，采用折半搜索时，最大比较次数为（ B ）。 A. 6 B. 7 C. 8 D. 10
7、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（A ）排序
A．插入 B．交换 C．选择 D．归并
8.在需要经常查找结点的前驱与后继的场合中，使用( C )比较合适。
A.单链表 B.双链表 C.顺序表 D.循环链表 9.下面关于线性表的叙述中，错误的为( D )
A.顺序表使用一维数组实现的线性表 B.顺序表必须占用一片连续的存储单元 C.顺序表的空间利用率高于链表 D.在链表中，每个结点只有一个链域 10.带头结点的单链表head为空的判断条件是( B )
A. head=NIL B. head↑.next=NIL C. head↑.next=head D. head< >NIL 11.队列通常采用两种存储结构是( A )
A.顺序存储结构和链表存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 12.深度为5的二叉树至多有( C )个结点。
A.16 B.32 C.31 D.10
13.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( C )条边。 A.n B.n+1 C.n-1 D.n/2 14.静态查找表与动态查找表二者的根本差别在于( B ) A.它们的逻辑结构不一样 B.施加在其上的操作不同
C.所包含的数据元素的类型不一样 D.存储实现不一样
15.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的( D )方法是散列文件的关键。 A.散列函数 B.除余法中的质数 C.冲突处理 D.散列函数和冲突处理 16.计算机算法指的是( C )。
A.计算方法
B.排序方法
C.解决某一问题的有限运算序列 D.调度方法
17.栈和队列的共同特点是( C )。 A.都是先进后出 B.都是先进先出
C.只允许在端点处插入和删除元素 D.没有共同点
18.深度为n的二叉树中所含叶子结点的个数最多为( C )个。 A.2n B.n C.2n-1 D.2n-1 19.树最适合用来表示( C )。 A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
20.下面的二叉树中，( C )不是完全二叉树。
21.对线性表进行二分查找时，要求线性表必须( C )。 A.以顺序方式存储 B.以链接方式存储
C.以顺序方式存储，且结点按关键字有序排序 D.以链接方式存储，且结点按关键字有序排序
22.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为
( B )。
A.78、47、61、33、39、80 B.80、78、61、33、39、47 C.80、78、61、47、39、33 D.80、61、78、39、47、33 24．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（B ） A.无左、右孩子 B.有左孩子，无右孩子 C.有右孩子，无左孩子 D.有左、右孩子
25．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（ B ） A.完全图 B.连通图 C.有回路 D.一棵树 26．除根结点外，树上每个结点（ B ） A．可有任意多个孩子、任意多个双亲 B．可有任意多个孩子、一个双亲 C．可有一个孩子、任意多个双亲
D．只有一个孩子、一个双亲
27．下列关键码序列中，属于堆的是（ A ） A．（15，30，22，93，52，71）
B．（15，71，30，22，93，52）
C．（15，52，22，93，30，71） D．（93，30，52，22，15，71） 28．一个带权的无向连通图的最小生成树（ B ） A．有一棵或多棵 B．只有一棵 C．一定有多棵 D．可能不存在 29.下列说法中正确的是( D )
A.一个具有n个顶点的无向完全图的边数为n(n-1) B.连通图的生成树是该图的一个极大连通子图 C.图的广度优先搜索是一个递归过程
D.对于非连通图的遍历过程中每调用一次深度优先搜索算法都得到该图的一个连通分量 30.顺序查找法与二分查找法对存储结构的要求是( D ) A.顺序查找与二分查找均只适用于顺序表
B.顺序查找与二分查找既适用于顺序表，也适用于链表 C.顺序查找只适用于顺序表 D.二分查找只适用于顺序表
二、填空题
1、数据的存储结构被分为_顺序存储__、_链式存储__、__索引存储_和__散列存储_四种。 2、一个算法应具备的5个特性为 有穷性 、 确定性 、 可行性 、 输入 、 输出 。
3、从一个栈删除元素时，首先取出 栈顶元素 ，然后再前移一位 栈顶指针 。 4.设由字符串a=′data′、b=′structure′、c=′-′,则a与c连接然后与b连接的结果为：‘ data – structure’_。
5.一个队列的入队序列是a、b、c、d，则队列的输出序列为_a b c d 。 6.具有N个结点的完全二叉树的深度为___log2 N_____。
7.树的三种主要的遍历方法是：__中序______、_先序____、 后序___和层次遍历。 8.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于__1___。
9.设head为单链表的头结点，则判断单链表为空的条件是：__head_.next=null______。 10.在具有n个单元的循环队列中，队满时共有____n-1_____个元素。
11.树的三种常用存储结构是：孩子链表表示法、_双亲链表表示法______和_孩子双亲链表表示法。
12.深度为K的完全二叉树至少有__2k-1______个结点，至多有___2k-1______个结点。 13.图的主要存储结构有两种，分别为：__邻接矩阵_______和__邻接表_______。 14.直接插入排序需要__1_______个记录的辅助空间。
15．定义在线性表上的初始化、查找、插入和删除运算中， 查找 是引用型运算。 16．线性表(a0,a1,a2,„,an)(n≥1)中，每个元素占c个存储单元，m为a0的首地址，则按顺序存储方式存储线性表，an的存储地址是 m+n*c 。
17．在栈的顺序实现中，设栈顶指针为top，栈空的条件为 top=-1 。
18．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 n-1 次合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。
19．对有序表(25,30,32,38,47,54,62,68,90,95)用二分查找法查找32，则所需的比较次数为 2 。
20．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的 层次 关系。
21．第i趟在n-i+1(i=1,2,„,n-1)个记录中选取键值最小的记录作为有序序列的第i个记录。这样的排序方法称为 选择排序 。
22．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用 快速排序 。 23．在顺序存储的线性表（a1,a2„，an）中的第i (1≤i≤n)个元素之前插入一个元素，则需向后移动________n-i+1_____个元素。
24．在下列树中，结点H的祖先为___B__________。
25．顶点数为n、边数为n(n-1)/2的无向图称为__无向完全图___________。
26．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是__2,4, 7, 9______。
27.设有33个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有__65__个结点。
28.若要对某二叉排序树进行遍历，保证输出的所有结点键值序列按递增次序排列，应对该
二叉树采用____深度_____遍历法。
29.在插入排序、快速排列、堆排序、归并排序中，排序方法不稳定的有___快速排列、堆排
序______。
三、应用题：
1． 一组记录的键值为（12，38，35，25，74，50，63，90），按2路归并排序方法对该序
列进行排序，画出每一趟归并后的结果？
第一趟: 12 38 25 35 50 74 63 90 第二趟: 12 25 35 38 50 63 74 90 第三趟: 12 25 35 38 50 63 74 90 2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。（8分）
71 41 30 23 18 16 14 12 11 9 7
A:111 G:011 F:10 U:010 Y:00 Z:110
3．设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,
77},采用散列函数：H(key)=key MOD 13, 采用线性探测法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。
构造过程如下：
H(19)=19 MOD 13=6 H(01)=01 MOD 13=1 H(23)=23 MOD 13=10
H(14)=14 MOD 13=1(冲突) H(14)=(1+1) MOD 19=2 H(55)=55 MOD 13=3 H(20)=20 MOD 13=7
H(84)=84 MOD 13=6 (冲突)
H(84)=(6+1) MOD 19=7 (仍冲突) H(84)=(6+2) MOD 19=8 H(27)=27 MOD 13=1 (冲突) H(27)=(1+1) MOD 19=2 (冲突) H(27)=(1+2) MOD 19=3 (仍冲突) H(27)=(1+3) MOD 19=4 H(68)=68 MOD 13=3 (冲突)
H(68)=(3+1) MOD 19=4 (仍冲突) H(68)=(3+2) MOD 19=5
H(11)=11 MOD 13=11
H(10)=10 MOD 13=10 (冲突)
H(10)=(10+1) MOD 19=11 (仍冲突) H(10)=(10+2) MOD 19=12 H(77)=77 MOD 13=12 (冲突) H(77)=(12+1) MOD 19=13
因此，各关键字相应的地址分配如下： address(01)=1 address(14)=2 address(55)=3 address(27)=4 address(68)=5 address(19)=6 address(20)=7 address(84)=8 address(23)=10 address(11)=11 address(10)=12 address(77)=13 其余的地址中为空。
4．一棵高度为h的满2叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有2棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从１开始对全部结点进行编号，试问：
（１）第j层的结点个数是多少（j = 0,1,2,„,h）? (2分) （２）编号为i的结点的父结点（若存在）的编号多少？（2分）
（３）编号为i的结点的左孩子结点（若存在）的编号多少？（2分）
（４）编号为i的结点有右兄弟的条件是什么？它的右兄弟结点的编号是多少（2分）
j
(1) 2
(2) i/2 向下取整 (3) 2i
(4) i为偶数 , i+1
5．已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列按冒泡法进行按从小到大排序，画出每一趟冒泡排序后的序列？ 54 28 16 34 73 62 95 60 26 43 第1趟: 16 54 28 26 34 73 62 95 60 43 第2趟: 16 26 54 28 34 43 73 62 95 60 第3趟: 16 26 28 54 34 43 60 73 62 95 第4趟: 16 26 28 34 54 43 60 62 73 95
第5趟: 16 26 28 34 43 54 60 62 73 95
6、对以下图，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。（8分）
2 0 5
3
1 6
4
0 1 2 3 4 5 6 7 8 9
7.由下列三棵树组成转的森林换成一棵二叉树？
7 9 8 A B D C E F
8．已知无向图G的邻接表如下，请画出其所有的连通分量。（6分） 1
5 2 4 3
9．如图所示，输入元素为A，B，C，在栈的输出端得到一个输出序列ABC，求出在栈的输入端所有可能的输入序列。（5分）
(1)C B A (2) B A , C (3)A , B , C (4)A , C B (5)C A , B
10．分别写出下列二叉树的先根、中根、后根遍历序列。（6分） A B C E D F G H C E B D G F H A E C G H F D B A
11．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分） 2 1 3 4 5
1 5 2 4 3
12.如下图所示，设有两个栈s1和s2共亨同一数组存储空间stack［1..m］，其中栈s1的栈底
设在stack［1］处，而栈s2的栈底设在stack［m］处，请编写栈s1和s2的进栈操作push(i,x)和退栈操作pop(i)，其中i=1、2，分别表示栈s1和s2。要求：仅当整个空间stack［1..m］占满时才产生上溢。
PROCEDURE push(i, x: integer)；{进栈操作} BEGIN
if(top1=top2-1)them {判断是否出现上溢} writeln(′发生上溢′)；
else if (i=1) then {对栈s1进行进栈操作} BEGIN
top1 :=top1+1; stack［top1］:=x; END
else {对栈s2进行进栈操作} BEGIN
top2 :=top2-1;
stack［top2］:=x； END END;
PROCEDURE pop(i) {退栈操作} BEGIN
if (i=1) then {对栈s1进行退栈操作} if (top1=0) then {判断栈s1是否下溢} writeln(′栈s1出现下溢′)； else ｛栈s1退栈｝ BEGIN
pop:=stack［top1］; top1:=top1-1; END
else ｛对栈s2进行退栈操作｝ if(top2=m+1) then {判断栈s2是否下溢} writeln(′栈s2出现下溢′)； else {栈s2退栈} BEGIN
pop:=stack［top2］; top2:=top2+1; END
END；
根据共享栈stack［1。。m］的结构，设top1为栈s1的栈顶指针，top2为栈s2的栈顶指针。则当top2=top1+1时出现上溢，而当top1=0时，栈s1出现下溢，当top2=m+1时，栈s2出现下溢。
13.假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。
顺序实现：
const maxsize∶=100; ｛顺序表的容量｝ type datatype=record ｛档案数据类型｝ name∶string〔10〕;｛姓名｝ number∶integer;｛学号｝ sex∶boolean;｛性别｝ age∶integer;｛年龄｝ end;
type slist =record
data∶array 〔1..maxsize〕 of datatype; last∶integer; end; 链接实现：
type pointer=↑node; node=record
name∶string 〔10〕;｛姓名｝ number∶interger； ｛学号｝ sex∶ boolean;｛性别｝ age∶integer;｛年龄｝
next∶pointer;｛结点的后继指针｝ end;
list=pointer;
因篇幅问题不能全部显示，请点此查看更多更全内容