一、选择题
1、下列有关线性表的叙述中，正确的是（ ） A、 一个线性表是n个数据元素的有限序列
B、 线性表中任何一个元素有且仅有一个直接前驱 C、 线性表中任何一个元素有且仅有一个直接后继 D、 以上说法都不正确
2、对线性表进行二分查找时，要求线性表必须（ ） A、以顺序方式存储 B、以链接方式存储
C、以顺序方式存储，且数据元素有序 D、以链接方式存储，且数据方式有序
3、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是（ ） A、110 B、108 C、100 D、120
4、一个队列的入列序列是１，２，３，４，则队列的输出序列是（ ）
A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,1,4
5、从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时,需向前移动( )个元素.
A、n-i B、n-i+1 C、n-i-1 D、i
6、一棵二叉树如图所示，它的中序遍历的结果为（ ） A、abdgcefh B、dgbaechf C、gdbehfca D、abcdefgh a b c
f
d e
h g
1
7、按照二叉树的定义，具有3个结点的二叉树有（ ）种 A、3 B、4 C、5 D、6
8、已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（ ）
A、acbed B、decab C、deabc D、cedba
9、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（ ）
A、edcba B、decba C、dceab D、abcde 10、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（ ）个结点 A、n B、n/2 C、(n-1)/2 D、(n+1)/2 二、填空题（每个空1、5分，共18分）
1、 如图所示，删除元素b的语句为
______________________ q a b c
2、 下面树的先序、中序、后续遍历的结果依次为
______________、_______________、_________________
a
b c
d e f
3、 栈的特点是_____________，队列的特点是
_______________
4、 在一棵完全二叉树中，若编号为i的结点有右孩子，
2
5、
6、 7、 8、 则该右孩子结点的编号为___________
已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为_____ 二叉树的5种基本形态是___________________________________ 在二叉树的第i层上至多有______结点 a e 将左边的森林转换为二叉树为
c f b ______________
9、 V1 V2
左图中v1的出度为__________
V3 V4
三、判断题（每小题1分，共10分）
1、在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的（ ）
2、在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上是无关的（ ）
3、栈只能在栈顶进行插入和删除（ ）
4、队列只能在队首进行删除，在队尾进行插入（ ） 5、某无向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由m个头结点和n个表结点组成（ ）
6、有向图中，所有结点的出度之和等于入度之和（ ） 7、由二叉树的先根序列和后根序列可以唯一的确定一棵二叉树（ ）
8、二叉树中，任何一个结点的度为2（ ） 9、一棵赫夫曼树中不存在度为1的结点（ ）
3
10、平衡二叉树左子树和右子树的深度之差的绝对值不超过1
（ ）
四、应用题（共38分）
1、假定一个待散列存储的线性表为（32，75，63，48，94，25，36，18，70），散列地址空间为[0,1,…,10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表( H(key)=key MOD 11).
2、有一份电文中共使用五种字符：a,b,c,d,e,它们的出现频率依次为4，7，5，2，9，请画出对应的编码赫夫曼树（请按照左子树根结点的权小于等于右子树根结点的权的次序构造），求出每个字符的赫夫曼编码，并求出该树的带权路径长度
4
3、对于下图，（1）写出按深度优先搜索结果 （2）写出按广度优先搜索结果
v1 V6 V2
V3 V4 V7
V5
4、
V2 a4=1 a1=3 V5 V1 a2=5 a5=6 a7=3
V3 a8=3
V6 V7 a3=2 V4 a6=4 （1） 写出关键路径 （2） 写出活动a5的最早开始时间，最晚开始时间 （3） 写出活动a6的最早开始时间，最晚开始时间
5
5、求出从v0到其它顶点的最短路径
80 V2 120 V3 V0 30
10 20
V4 V1 20
6
《数据结构》试题一答案
一、 选择题
1、A 2、A 3、B 4、B 5、A 6、B 7、C 8、D 9、C 10、D 二、 填空题 1、q----next=q----next----next 2、abdcef bdaecf dbefca 3、先进后出 后进先出 4、2i+1 5、5 6、空二叉树、只有一个节点、带左子树、带右子树、左右子树有 7、2i-1 8、略 9、2
三、 判断题
1、 ν 2、ν 3、ν 4、ν 5、× 6、 ν 7、× 8、× 9、ν 10、ν 四、 应用题 1、
0 10 70 25 48 36 94 18 63 75 32 2、
1 0
1 0 1 0
b e c
1 0
d a
7
3、
V1、V2、V3、V5、V4、V6、V7 V1、V2、V6、V3、V4、V7、V5
4、V1---V3----V5----V6----V7
5、5 2、10
5、本题应有步骤 答案略
8
因篇幅问题不能全部显示，请点此查看更多更全内容