——
五 六 2006 学年度第 二 学期考试卷(A)
份,
八 年
月 日 九 十 —
考试，任课教师 范、王 拟题
十二 总 分 软件教研室 备 注 …………….……………..装……………………订………………..线…………….……………..
计算机
系
05专升本,03职 一 班级 二 数据结构 课程 期末 考试，共 2 页，第1页，共印刷
三 四 七 学号 题 号 得 分 阅卷教师签名 十一 一、选择题（本题的每一备选答案中，只有一个是正确的，请把你认为正确的答案的题号填入题干的括号内，多选不给分，每小题3分，共30分）
1. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ） A．head==NULL B．head→link==NULL C．head→link==head D．head!=NULL 2. 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进后出 C.后进先出 D. 不分顺序 3. 具有10个叶结点的二叉树中有（ ）个度为2的结点. A．8 B．9 C．10 D．ll 4. 树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B.层次序列 C. 后序序列 D．中序序列
二、填空题（每题2分，共10分）
1. 某线性表采用顺序存储结构,每个元素占据2个字节,首地址为100,则下标为11的(第12个)元
素的存储地址为
2. 采用左右指针法存储N个结点的二叉树,该二叉树中共有 个指针域, 其中非空指
针 个. 3. 如果树中某结点A有 3个兄弟，而且B是A的双亲，则B的度是_ ____ 4. 在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ _______个元素。 5. 二分法检索有序表（4，6，12，20，28，38，50，70，88，100），若检索表中元素20，它将依
次与表中元素 比较大小。
班 姓名 级 5. 对N个元素的表做顺序检索时，若检索每个元素的概率相同（不考虑失败的情况下），则平三、判断题（下列各题，你认为正确的，请在后面的括号内打√，错误的打×。 每题1分，共10
均检索长度为( ) 分） A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2
6. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 7. 数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( )的两趟排序后
的结果。
A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 8. 要连通具有n个顶点的有向图，至少需要（ ）条边。 A．n-l B．n C．n+l D．2n 9. 下面给出的四种排序法中( )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 快排 10. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针
1. 在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（ ）
2. 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。（ ） 3. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.（ ） 4. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 5. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ） 6. 在待排数据基本有序的情况下，快速排序效果最好。（ ）
7. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ） 8. 对于非强连通的有向图，一定不存在一个顶点能到达其他所有顶点（ ） 9. 在具有n个单元的循环队列中，队满时共有 n个元素（ ） 10. 堆排序是选择排序的一种，而且是不稳定的排序算法。（ ）
系
C. 头、尾指针都要修改 D. 头、尾指针可能都要修改
…………….……………..装……………………订………………..线…………….…………….. 计算机 系 05专升本,03职 班级 数据结构 课程 期末 考试，共 2 页，第2页，共印刷 四、解答题（每题7分，共35分）
1. 已知一组记录的关键码为（46，79，56，38，40，80,95，24），写出对其进行shell排序(增量取
4、2、1)、二路归并排序的每一趟排序结果。 2. 已知一棵二叉树的先根周游序列为A，B，D，E，G，C，F，H，I，J，对称序周游序列为：D，
B，G，E，A，H，F，I，J，C，试画出这棵二叉树，并给出该二叉树的后根次序周游序列。 3. 一个线性表为 B= （ 12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，
散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表。 4. 请将图一所示的二叉树转换成对应的树林。
份, 年 月 日 — 考试，任课教师 范、王 拟题 软件教研室
5.
A B D E J H I K L F 2 C G 1 3 3 1 2 5 2 4 4 2 1 6 2 7 3 4 8 图二
图一
请用克鲁斯卡尔（Kruskal）算法构造出图二的一棵最小生成树（只写结果）。
五、算法设计题（共15分）
1. 编写一算法，删除带头结点的单链表中值相同的多余结点，即若链表中有多个结点具有相同的
数据域，只保留其中一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同。单链表结点结构如下：(8分) struct Node;
typedef struct Node *PNode; struct Node{ DataType info; PNode link;}
2. 写出计算二叉树的叶子结点个数的算法。二叉树的结点结构如下：（7分） struct BinTreeNode;
typedef struct BinTreeNode *PBinTreeNode; struct BinTreeNode{ DataType info;
PBinTreeNode llink,rlink;}
因篇幅问题不能全部显示，请点此查看更多更全内容