安徽大学期末试卷
安徽大学20 07 —20 08 学年第 二 学期
《数据结构》考试试卷（A卷）
（闭卷 时间120分钟）
一、单项选择题（每小题1，共10分）
1．算法分析的目的是 。
A．找出数据结构的合理性 B．分析算法的正确性 C．分析算法的时间和空间效率 D．分析算法的可读性 2．带头结点的单链表head为空的条件是 。
A．head= =NULL B．head→next= =NULL C．head→next = =head D．head！=
NULL
3．栈和队列的共同点是 。
A．先进先出 B．后进先出
C．只能在一端进行插入和删除 D．限制存取点的线性表 4. 在数组A中,每个元素占3个字节,行下标i从1到8,列下标j从1 到 10,从首地址SA开始连续存放在存储器中,该数组按列存放时,元素 A[8][5]的起始地址为 。
A．SA+117 B．SA+120 C．SA+144 D．SA+141 5．广义表（（a,b），c,d）的表头是 。
A．a B． （a）C． （a,b） D． （（a）） 6．若某二叉树的 中序序列为 dgbaechf，后序序列为 gdbehfca，则先序序列是 。
A．abdgcefh B．gdbecfha C．adbehfcg D．abdgechf
7．若一棵哈夫曼树的结点总数为2001个，则它有（ ）叶子结点。
A．999 B．1000 C．1001 D．1002
8．已知有向图的邻接表如下所示，从顶点v1出发，得到的DFS序列为 。
A．V1，V2，V3，V4，V5 1 3 2 4 ∧
2 ∧ 3 4 2 B．V1，V2，V3，V5，V4
C．V1，V3，V4，V5，V2
5 ∧ 4 ∧ 5 D．V1，V4，V3，V5，V2
4 ∧ 9．折半查找法适合于存储结构为 的线性表。
A．顺序存储 B．散列存储 C．二叉树 D．链式存储
10．设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 。
A．冒泡排序法 B．快速排序法 C．堆排序法 D．插入排序法
二、填空题（每题1 分，共10 分）
1．下面程序段中语句 x++ 的执行次数是 。
for（i=1；i＜n；i++） { y=y+1；
for（j=0；j＜=2*（n+1）；j++）
x++；
}
小学数学经典测试卷 单元测
安徽大学期末试卷
2．在单链表L中设立头结点的作用是 。
3． 一个栈的输入序列为1，2，3，4，得到的输出序列4，1，2，3是 的。 4．引入循环队列的目的是 。
5．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置，这种说法是 。
6．广义表的表尾是广义表，这种说法是 。
7．根据二叉树的定义，n个结点的二叉树的不同形态有 。 8．图的DFS和BFS遍历得到的结点序列不唯一，与 有关。 9． 用二叉排序树查找，在最坏情形下的性能时间与 相同。
10．已知序列{54，38，96，23，15，72，60，45，83}，采用直接插入排序，将60插入到有序子区间时，为寻找插入位置需比较 次。
三、分析应用题 （每题5分，共20分） 得分
1．阅读以下算法，按要求回答问题。 func （int a[]，int n，int x）
{ int i，j；
if（x>=a[n-1]） a[n]=x； else {i=0；
while（x>=a[i]）i++；
for（j=n-1；j>=i；j--）a[j+1]=a[j]； a[i]=x； n++；}
return n； }
该算法的功能是 。
2． 写出以下程序段的输出结果（队列中的元素类型为char，EnQueue（Q，x）表示元素x进队Q，DeQueue（Q，x）表示队头元素出队后保存在x中） void main（）
{ char x=’e’, y=’c’ ;
EnQueue（Q，’h’）; EnQueue（Q，’r’）; EnQueue（Q，y）; DeQueue（Q，x）; EnQueue（Q，x）； DeQueue（Q，x）；EnQueue（Q，’a’）;
while (!QueueEmpty(Q) { DeQueue（Q，y）; printf (y);} Printf(x); }
3、对于如下的连通图，请给出从顶点0出发，利用普里姆（Prim）算法画出它的最小生成树。 12 5 0 6 8 13 15 16 4 1 6 4 12 9 20
10 5 2 3 小学数学经典测试卷 单元测
安徽大学期末试卷
4、设F={T1，T2，T3}是森林（如下图所示），试将它转换为二叉树，画出所对应的二叉树。 G C A I H J D E F B K M L T1 T2 T3
森林
四、 解答题（每题10分，共40分）
1．已知二叉树的顺序存储结构如下图所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b ⑴ 画出二叉树T的逻辑结构图；
⑵ 写出按先序、中序和后序遍历T所得到的结点序列；
⑶ 画出后序线索树。
2．已知一个无向图的顶点集为{a, b, c, d, e} ,其邻接矩阵如下所示
?01001??10010????00011???01101????10110??
(1) 画出该图的图形；
(2) 根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。
3．设下列关键字构造哈希表（hash）表，的地址范围为0~17，关键字序列为10，24，32，17，31，30，46，47，40，63，49， ⑴ 计算装填因子α；
小学数学经典测试卷 单元测
安徽大学期末试卷
⑵ 利用除留余法构造hash函数；
⑶ 利用线性探测再散列法解决冲突，构造hash表填入下表； 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
⑷ 查找关键字32，与哪些元素比较？
⑸ 计算在等概率情形下，查找成功的ASL。
4．设关键字序列为{503，087，512，061，908，170，897，275，653，426}手工执行shell排序（d1=5）和快速排序，请写出第一趟排序结束时关键字的状态填入下表。 初始 第一趟 503 503 087 087 512 512 061 061 908 908 170 170 897 897 275 275 653 653 426 426 初始 d1=5 五、设计题（每题10分，共20分）
1． 写出链式结构存储的两个有序表合并为一个有序表的算法。
2．试写出二叉树层次遍历算法。二叉树采用二叉链表存储，结构如下： typedef struct node {
int data;
struct node *lchild,*rchild; } bitree;
小学数学经典测试卷 单元测
相关推荐：
loading