1、数据结构期末考试试题及答案 期末样卷参考答案 一是非题（每题1 分共 10 分） 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要， 可对它们中的任一 元素进行操作。F 3 字符串是数据对象特定的线性表。T 4在单链表P指针所指结点之后插入S结点的操作是： P-next= S ; S- next = P-next; F 5 一个无向图的连通分量是其极大的连通子图。T 6 邻接表可以表示有向图，也可以表示无向图。T 7 假设 B 是一棵树， B是对应的二叉树。则B 的后 根遍历相当于B的中序遍历。T 8 通常，二叉树的第i 层上有 2i-1 个结点。 F 9 对
2、于一棵 m 阶的 B-树,树中每个结点至多有m 个关 键字。除根之外的所有非终端结点至少有m/2个关键 字。 F 10对于任何待排序序列来说，快速排序均快于起泡排 序。 F 二选择题（每题2 分共 28 分） 1在下列排序方法中，（c ）方法平均时间复杂度为 0(nlogn)，最坏情况下时间复杂度为0(n2)； （ d ）方法 所有情况下时间复杂度均为0(nlogn)。 a. 插入排序b. 希尔排序c. 快速排序d. 堆排 序 2. 在有 n 个结点的二叉树的二叉链表表示中，空指针数 为（b ） 。 a. 不 定b.n+1 c.n d.n-1 3. 下列二叉树中，（ a ）可用于实现符号不等长
3、高效编 码。 a.最优二叉树b.次优查找树c.二叉平衡树 d.二叉排序树 4. 下列查找方法中， （ a ）适用于查找有序单链表。 a.顺序查找b.二分查找c.分块查找 d.哈希查找 5. 在顺序表查找中， 为避免查找过程中每一步都检测整 个表是否查找完毕，可采用（a ）方法。 a.设 置监视哨b.链 表存贮c.二分查找 d.快速查找 6. 在下列数据结构中， （ c ）具有先进先出特性， （ b ） 具有先进后出特性。 a线性表b栈c队列d广 义表 7具有 m 个结点的二叉排序树，其最大深度为（f ） ， 最小深度为（b ） 。 a. log 2 m b. log2 m +1 c. m/2
4、d . m/2 -1 e. m/2 f. m 8已知一组待排序的记录关键字初始排列如下： 56,34,58,26,79,52,64,37,28,84,57 。 下列选择中（c ）是快速排序一趟排序的结果。 （ b ）是希尔排序（初始步长为4）一趟排序的结果。 （ d ）是基数排序一趟排序的结果。 （ a ）是初始堆（大堆顶） 。 a. 84， 79，64，37，57，52，58，26， 28，34，56。 b. 28， 34，57，26，56，52，58，37，79，84，64。 c. 28，34，37，26，52，56，64，79， 58，84，57。 d. 52， 34，64，84， 56
5、，26，37，57，58，28，79。 e. 34，56，26，58，52，64，37，28，79，57，84。 f. 34，56， 26，58，52， 79，37，64，28，84，57。 三填空题（每题2 分共 20 分） 1有向图的存储结构有（邻接矩阵）、 （邻接表） 、 （十 字链表）等方法。 2已知某二叉树的先序遍历次序为afbcdeg，中序遍历 次序为 cedbgfa。 其 后 序 遍 历 次 序 为 （ edcgbfa ） 。 层 次 遍 历 次 序 为 （afbcgde） 。 3设有二维数组A 5 x 7 ,每一元素用相邻的4 个字节存 储，存储器按字节编址。已知A00 的存储
6、地址为100。 则按行存储时， 元素 A14 的第一个字节的地址是（144） ； 按列存储时，元素A14 的第一个字节的地址是（184） 。 4请在下划线上填入适当的语句，完成以下法算。 Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) / 先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) ) While ( gettop( S, p ) push(S, p-lchild ; Pop ( S , p ); If ( !stackempty
7、(s) ) pop(S, p) ; push( S, p-rchild ); return ok; 四简答题（每题5 分共 25 分） 1将图示森林转换为二叉树，并对该二叉树中序全序 线索化。 2已知 Hash函数为H（K）=K mod 13 ，散列地址为0 -14， 用二次探测再散列处理冲突，给出关键字 （ 23，34，56， 24，75，12，49, 52，36，92，06，55）在散列 地址的分布。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3. 右图为一棵3阶B 树。 （20，25） a. 画 出 在 该 树 上 插 入 元 素15后 的B 树 。 b. 接
8、着， 再删除元素35， 画出删除后的B 树。(10,14) （21） （35） 4.已知某无向图的邻接表存储结构如图所示。 a.请画出该图。 b.根据存储结构给出其深度优先遍历序列及广度优先遍 历序列。 c.画出其深度优先生成树及广度优先生成树。 0 a 2 4 / 1 b 2 3 4 / 2 c 0 1 4 / 3 d 1 / 4 e 0 1 2 / 5. 设在某通信系统中使用了八个字符，它们出现的频率 分别为 0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07， 试构造一棵赫夫曼树，并给出赫夫曼编码。 五算法设计题（共17 分） 1. 单链表结点的类型定义如下：
9、typedef struct LNode int data; struct LNode *next; LNode, *Linklist; 写一算法， 将带头结点的有序单链表A 和 B合并成一新 的有序表C。 (注:不破坏 A 和 B 的原有结构 .) Merge(Linklist A, Linklist B, Linklist pa=A-next; pb=B-next; pc=C; while(pa pc=pc-next; if(pa-datadata) pc-data=pa-data; pa=pa-next; else pc-data=pb-data; pb=pb-next; if(!pa)
10、 pa=pb; while(pa) pc-next=(Linklist)malloc(sizeof(LNode); pc=pc-next; pc-data=pa-data; pa=pa-next; pc-next=NULL; 2. 二叉树用二叉链表存储表示。 typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 编写一个复制一棵二叉树的递归算法。 BiTree CopyTree(BiTree T) if (!T ) return NULL; if (!(newT = (BiTNode*)malloc(sizeof(BiTNode) exit(Overflow); newT- data = T- data; newT- lchild = CopyTree(T- lchild); newT- rchild = CopyTree(T- rchild); return newT;
