2010数据结构期末试卷A答案

徐州工程学院试卷

徐州工程学院数据结构期末试卷A答案

2009 — 2010 学年第 二 学期 课程名称 数据结构

试卷类型 期末 考试形式 闭卷 考试时间 100 分钟 命 题 人 鞠训光 2010 年 6 月 7 日 使用班级 08电本

教研室主任 年 月 日 教学院长 年 月 日 姓 名 班 级 学 号 .

题号 总分 得分

一 20 二 15 三 15 四 10 五 40 六 七 八 总分 一、填空题 （共 8 小题，每空 1 分，共计 20 分）

1．栈和队列都是线性_结构；对于栈只能在_栈顶_ 插入和删除元素；对于队列只能在_队尾_插入元素和在_ 队头 删除元素。

2．．假设为循环队列分配的向量空间为Q[20]，若队列的长度和队头指针值分别为10和17，则当前尾指针的值为___7___。

3．在进行直接插入排序时，其数据比较次数与数据的初始排列__ 有_______关；而在进行直接选择排序时，其数据比较次数与数据的初始排列 ____ 无_______关。 5．在一棵具有n个结点的二叉树中，所有结点的空子树个数等于 n+1 、第i层上至多有个 2i－1 结点。

6．若一个图的顶点集为{a,b,c,d,e,f},边集为{（a,b）,(a,c),(b,c),(d,e)},则该图含有___3____个连通分量。 7．开放定址法、 链地址法 。

8．若对关键字序列（49，38，65，97，76，13，27，48，55，04）进行一趟增量为5的希尔排序，则得到的结果为（13，27，48，55，04，49，38，65，97，76）。 9. 在有序表（12，24，36，48，60，72，84）中折半查找关键字60时所需进行的关键字比较次数

为__3___。

10. 一棵含999个结点的完全二叉树的深度为___10____。含n个顶点的无向连通图中至少含有__n-1____条边。

11. 已知一棵二叉树，分支数为5，度为2的结点2，则该树中共有______6______ 个结点。

《数据结构》试卷 第 1 页 共 6 页

徐州工程学院试卷

12. 设二叉树结点的先根序列为ABEDCFGH，中根序列为EDBAFCHG,则二叉树中叶子结点是_

D,F,H ___。

13．若由3，6，8，13，10作为叶子结点的值生成一棵哈夫曼树，则该树的高度为 4 ,带权路径长度为 89 。

二、选择题 （共 15小题，每题 1 分，共计 15 分） 1．算法指的是（ D ）

A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2．如下陈述中正确的是（A ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

3．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ D ）

A．3，2，6，1，4，5 B．5，6，4，2，3，1 C．1，2，5，3，4，6 D．1，2，5，6，4，3

4．在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( B ) A． s->next=p；p->next=s B． s->next=p->next；p->next=s C． s->next=p->next；p=s D． p->next=s；s->next=p 5．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（ A ） A．队列 B．栈 C．线性表 D．有序表 6．图的邻接矩阵表示法适用于表示（ C ）

A．无向图 B．有向图 C．稠密图 D．稀疏图 7．深度为5的二叉树其结点数最多为 C 。 A、16； B、30； C、31； D、32。

8．设单循环链表中结点的结构为（data,next）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作（ D ）

A． s=rear； rear=rear->next； delete s； B． rear=rear->next； delete rear； C． rear=rear->next->next； delete rear；

《数据结构》试卷 第 2 页 共 6 页

徐州工程学院试卷

D．s=rear->next->next； rear->next->next=s->next； delete s； 9．线性表采用链式存储时，结点的存储地址（ B ） A．必须是不连续的 B．连续与否均可

C．必须是连续的 D．和头结点的存储地址相连续 10．线性链表不具有的特点是（A ）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 11. 含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A．e B．2e C．n2－e D．n2－2e

12. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的

变化情况如下：

20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（B ）

A．选择排序 B．快速排序 C．归并排序 D．希尔排序

13. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D 。 A．先序遍历； B．中序遍历； C．后序遍历； D．按层遍历。

14. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>},则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为 D 。 A、1，2，5，4，3； B、1，2，3，4，5； C、1，4，3，2，5； D、1，2，5，3，4。

15. 假定对元素序列（2，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为 C 。

A、1，3，5，2，9，12； B、1，3，5，9，2，12； C、1，2，5，9，3，12； D、1，5，3，9，12，2。

三、 判断题 （对的打√，错的打× 共 15 小题，每题 1 分，共计 15 分） 1、在线性结构中，每个结点都有一个直接前驱和一个直接后继。（×）.

《数据结构》试卷 第 3 页 共 6 页

徐州工程学院试卷

2、在堆中，以任何结点为根的子树仍然为堆。（√ ） 3、完全二叉树就是满二叉树。（ × ）

4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（√ ）。 5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（× ）

6、在AOE网中，关键路径是唯一的。(×)

7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 (√ ) 8、连通分量是无向图中的极小连通子图。（ × ）

9、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（ × ）

10、在散列法中，一个可用散列函数必须保证绝对不产生冲突。（╳） 11、完全二叉树的某结点若无左孩子，则它必是叶结点。 (√ )

12、在采用线性探测法处理冲突的散列表中，所有的同义词在表中相邻。（×） 13、栈和队列逻辑上都是线性表。 (√) 14、快速排序是一种稳定的排序方法。(× ) 15、15、树中结点的最大层次称为树的高度（√）。

四、算法填空题： 将折半查找的非递归算法中的空白处进行正确填写。

（每空2分，共计 10分）

int Search_Bin(SSTable ST,KeyType key)

{ int low=1； high=_ST.length_________； （1） While (__low<=high _____________) { (2) mid=_(low+high)/2________________； (3) if (EQ(key,ST.elem[mid].key ) return mid；

else if (LT(key,ST. elem[mid].key)) _ high=mid-1___________； (4) else __low=mid+1________________； (5) }

return 0； }// Search_Bin

五、 综合应用题 （每题10分，共计 40 分）

《数据结构》试卷 第 4 页 共 6 页

徐州工程学院试卷

１．已知一个连通图的边集为｛（１，２）３，（１，３）６，（１，４）８，（２，３）４， （２，５）１０，（３，５）１２，（４，５）２｝，若从顶点V1出发, 求出此图的深度和广度优先遍历序列，按照普里姆算法求最小生成树并画出，写出依次得到的各条边． 1. 深度优先:1 2 3 5 4 广度优先: 1 2 3 4 5

普里姆算法依次得到的各边(1,2)3, (2,3)4, (1,4)8, (4,5)2 最小生成树如图所示：

２．设有一个模式串为abaabcac，如图。试根据KMP算法的思想求出其next[j]函数值。

j 模式串 Next[j] 1 2 3 4 5 6 7 8 a b a a b c a c 0 1 1 2 2 3 1 2 ３．算法编程：归并两个“其数据元素按值非递减有序排列的”顺序线性表LA和LB，求得线性表LC也具有同样特性： 设 La = (a1, ?, ai, ?, an) Lb = (b1, …, bj, …, bm) Lc = (c1, …, ck, …, cm+n) 则 Ck = k = 1, 2, ?, m+n

1．分别从LA和LB中取得当前元素ai和bj；

2．若ai≤bj，则将ai插入到LC中，否则将bj插入到LC中。 3.不需要建初始顺序表La、 Lb。

《数据结构》试卷 第 5 页 共 6 页

徐州工程学院试卷

void MergeList(List La, List Lb, List &Lc) { // 已知线性表La和Lb中的元素按值非递减排列。 // 归并La和Lb得到新的线性表Lc， // Lc的元素也按值非递减排列。InitList(Lc); i = j = 1; k = 0;

La_len = ListLength(La); Lb_len = ListLength(Lb);

while ((i <= La_len) && (j <= Lb_len)) { // La和Lb均非空 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } }

while (i <= La_len) { GetElem(La, i++, ai);

ListInsert(Lc, ++k, ai);} while (j <= Lb_len) { GetElem(Lb, j++, bj);

ListInsert(Lc, ++k, bj);} } // merge_list

《数据结构》试卷 第 6 页 共 6 页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2010数据结构期末试卷A答案在线全文阅读。