数据结构考试试题

数据结构复习资料
1．数据结构作为一门学科，它研究的是（ c ）。
A、数据的逻辑结构
B、数据的逻辑结构和物理结构
C、数据的逻辑结构、物理结构及操作算法
D、数据的组成成份、类型及操作算法
2．向一个有n个元素的顺序表中插入一个新元素，假设在表中任何位置上插入元素都是等概率的，平均要移动（ ）个元素。
A、n B、n/2 C、( n+1)/2 D、( n-1)/2
3．设S为顺序栈，栈顶指针为S.top 。已知栈未满，则将新元素e进栈的操作序列是（ ）
A、*S.top=e；S.top++； B、S.top++；*S.top=e；
C、*S.top=e；S.top--； D、S.top--；*S.top=e；
4．设Q为循环队列，其空间大小为m，则队满条件为（ ）。
A、Q.rear＝＝m B、Q.rear＝＝Q.front
C、Q.rear+1＝＝Q.front D、（Q.rear+1）% m＝＝Q.front
5．若一棵二叉树的总结点数n = 16，度为1的结点数n1 = 3，则该二叉树中，叶子结点数n0和度为2的结点数n2分别为（ ）。
A、n0 = 4，n2 = 9 B、n0 = 5，n2 = 8
C、n0 = 7，n2 = 6 D、n0 =6，n2 = 7
6．深度为k的满二叉树中，分支结点总数为（ ）。
A、2k B、2k-1 C、2k-1 D、2k-1-1
7．具有n（n>1）个顶点的强连通图，其弧数e必满足（ ）。
A、e=n B、e=n-1 C、n≤e≤n(n-1) D、n-1≤e≤n(n-1)/2
8．下面是某无向图G的邻接矩阵。该无向图的边数为（ ）。
0 1 0 1 A、8
1 0 1 1 B、4
0 1 0 0 C、16
1 1 0 0 D、12
9．一线性有序表（2，3，7，10，16，20，25，28）以顺序表表示，若以折半查找法在该表中查找元素25，其查找长度为（ ）。
A、7 B、2 C、3 D、4

1．数据结构的存储表示包括数据元素的表示和 关系 的表示。
2．任何一个算法的设计取决于选定的 数据逻辑 结构。
3．设单链表表长为n，则访问表中某个元素的时间复杂度是 。
4．若入栈序列是1,2,3,4，写出两种不可得到的出栈序列： 。
5．一循环队列Q，其最大空间为20。若Q.front＝15，Q.rear＝2，则队列长度为 。
6．在二叉树第i层上的结点数至多为 。
7．带权路径长度最小的二叉树是 树。
8．n个顶点的无向图，其边数最少为 。

名词解释：
1．线性结构
2．满二叉树
3．完全图
4．动态查找表

分析题：
1．已知一棵二叉树的中序遍历序列为ACEBHFDG，先序遍历序列为ABCEDFHG。试画出该二叉树，并给出其后序遍历序列。

2．设某计算机有10条指令I1 ~ I10，其使用频率依次为0.25，0.20，0.15，0.10，0.08，0.08，0.05，0.04，0.03，0.02。试为这10条指令设计赫夫曼编码，并画出赫夫曼树。

3．对下图所示的连通网，试从顶点A开始，用普里姆算法构造其最小生成树。要求给出完整的构造过程。
A 5 E
4 4
1 F 6
3 5 8
B 6 D
7 2
C

4．试对下表中的关键字按表中顺序构造一棵二叉排序树
（14，6，18，21，4，5，30，23，20，12，48）
并计算其在等概率的前提下，查找成功时的平均查找长度。

算法设计：
编写算法，在带头结点的单链表L中，删除元素值等于x的第一个结点，并释放被删结点。