《2022年数据结构期末试卷A答案 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构期末试卷A答案 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、徐州工程学院试卷数据结构试卷第 1 页 共 6 页徐 州 工 程 学 院 数 据 结 构 期 末 试 卷 A 答 案2009 2010 学年第二学期课程名称数据结构试卷类型期末考试形式闭卷考试时间 100 分钟命 题 人鞠训光 2010 年 6 月 7 日使用班级 08电本教研室主任年月日教学院长年月日姓 名班 级学 号 .一、填空题（共8 小题，每空1 分，共计20 分）1栈和队列都是线性 _结构；对于栈只能在 _栈顶_ 插入和删除元素；对于队列只能在_队尾_插入元素和在 _ 队头 删除元素。2 假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为10和 17，则当前尾指针的
2、值为 _7_。3在进行直接插入排序时，其数据比较次数与数据的初始排列_ 有_关；而在进行直接选择排序时，其数据比较次数与数据的初始排列_ 无_关。5在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于 n+1、第 i 层上至多有个2i1 结点。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.在有序表（
3、12，24，36，48，60，72，84）中折半查找关键字60 时所需进行的关键字比较次数为_3_。10.一棵含 999个结点的完全二叉树的深度为_10_。含 n 个顶点的无向连通图中至少含有 _n-1_条边。11.已知一棵二叉树，分支数为5，度为 2 的结点 2，则该树中共有_6_ 个结点。题号一二三四五六七八总分总分20 15 15 10 40 得分名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -徐州工程学院试卷数据结构试卷第 2 页 共 6 页12.设二叉树结点的先根序列为ABEDCFGH，中根序列为EDBAFCHG,则二叉树中叶子结点是_ D,F,H _。13
4、若由 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）A3，2，6，1，4，5 B5，6，4，2，3，1 C1，2，5，3，4，6 D1，2，5，6，4，34 在一个单链表中，若 p 所指结点不是
5、最后结点，在 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 是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，
6、则应执行下列哪一个操作（D ）A s=rear；rear=rear-next；delete s；B rear=rear-next；delete rear；C rear=rear-next-next；delete rear；名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -徐州工程学院试卷数据结构试卷第 3 页 共 6 页Ds=rear-next-next；rear-next-next=s-next；delete s；9线性表采用链式存储时，结点的存储地址（B ）A 必须是不连续的 B连续与否均可 C 必须是连续的 D和头结点的存储地址相连续10线性链表不具有的特点是（A）
7、。A随机访问 B不必事先估计所需存储空间大小C 插入与删除时不必移动元素 D所需空间与线性表长度成正比11.含 n 个顶点和 e 条边的无向图的邻接矩阵中,零元素的个数为(D)A e B2e Cn2e Dn22e12.用某种排序方法对关键字序列（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.采用邻接表存储的图的广度优
8、先遍历算法类似于二叉树的 D 。A先序遍历；B中序遍历；C 后序遍历；D按层遍历。14.若一个图的边集为,则从顶点 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、在线性结构中，每个结点都有一
9、个直接前驱和一个直接后继。（）.名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -徐州工程学院试卷数据结构试卷第 4 页 共 6 页2、在堆中，以任何结点为根的子树仍然为堆。（）3、完全二叉树就是满二叉树。（）4、若将一棵树转换成二叉树，则该二叉树的根结点一定没有右子树（）。5、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。（）6、在 AOE 网中，关键路径是唯一的。()7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。()8、连通分量是无向图中的极小连通子图。（）9、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储
10、都适用。（）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
11、=_(low+high)/2_；(3)if(EQ(key,ST.elemmid.key)return mid；else if(LT(key,ST.elemmid.key)_ high=mid-1_；(4)else _low=mid+1_；(5)return 0；/Search_Bin 五、综合应用题（每题 10分，共计40 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -徐州工程学院试卷数据结构试卷第 5 页 共 6 页已知一个连通图的边集为（，），（，），（，），（，），（，），（，），（，），若从顶点V1出发,求出此图的深度和广度优先遍历序列，按照普里姆算法求最
12、小生成树并画出，写出依次得到的各条边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 算法的思想求出其nextj 函数值。j 1 2 3 4 5 6 7 8 模式串a b a a b c a c Nextj 0 1 1 2 2 3 1 2 算法编程：归并两个“其数据元素按值非递减有序排列的”顺序线性表LA 和 LB，求得线性表LC 也具有同样特性：设 La=(a1,ai,an)Lb=(b1,bj,bm)Lc=(c1,ck,cm+
13、n)则 Ck=k=1,2,m+n 1分别从LA 和 LB 中取得当前元素ai 和 bj；2若 aibj，则将 ai 插入到 LC 中，否则将bj 插入到 LC 中。3.不需要建初始顺序表La、Lb。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -徐州工程学院试卷数据结构试卷第 6 页 共 6 页void MergeList(List La,List Lb,List&Lc)/已知线性表 La 和 Lb 中的元素按值非递减排列。/归并 La 和 Lb 得到新的线性表Lc，/Lc 的元素也按值非递减排列。InitList(Lc);i=j=1;k=0;La_len=ListLe
14、ngth(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 页 -