【学历类职业资格】数据结构-1及答案解析.doc
《【学历类职业资格】数据结构-1及答案解析.doc》由会员分享,可在线阅读,更多相关《【学历类职业资格】数据结构-1及答案解析.doc(9页珍藏版)》请在麦多课文档分享上搜索。
1、数据结构-1 及答案解析(总分:100.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.设数组 data0m作为循环队列 SQ的存储空间,front 为队头指针,rear 为队尾指针,则执行出队操作的语句为( )(分数:2.00)A.front:=front+1B.front:=(front+1)mod mC.rear:=(rear+1)mod mD.front:=(front+1)mod(m+1)2.在 Hash函数 H(k)=k MOD m中,一般来讲,m 应取( )(分数:2.00)A.奇数B.偶数C.素数D.充分大的数3.实现任意二叉树的后序遍历的
2、非递归算法而不使用栈结构,最佳方案是二叉树采用( )存储结构。(分数:2.00)A.二叉链表B.广义表C.三叉链表D.顺序4.向一个栈顶指针为 Top的链栈中插入一个 s所指结点时,其操作步骤为( )(分数:2.00)A.Topnext=s;B.snext=Topnext;Topnext=s;C.snext=Top;top=s;D.snext=Top; Top=Topnext;5.快速排序在最坏情况下的时间复杂度是( )(分数:2.00)A.O(nlogB.O(n2)C.O(n3)D.都不对6.内部排序的方法有许多种,( )方法是从未排序序列中依次取出元素,与已排序序列中的元素作比较,将其放入
3、已排序序列的正确位置上。(分数:2.00)A.归并排序B.插入排序C.快速排序D.选择排序7.对于一个具有 N个顶点的图,如果我们采用邻接矩阵法表示,则此矩阵的维数应该是( )(分数:2.00)A.(N-1)(N-1)B.NNC.(N+1)(N+1)D.不确定8.在一个长度为 n的顺序表(顺序存储的线性表)中,向第 i个元素(1in+1)之前插入一个新元素时,需向后移动( )个元素。(分数:2.00)A.n-iB.n-i+1C.n-i-1D.i9.下面四种排序方法中,平均查找长度最小的是( )(分数:2.00)A.插入排序B.选择排序C.快速排序D.归并排序10.如果我们采用二分查找法查找一个
4、长度为 n的有序表,则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。(分数:2.00)A.大于B.小于C.等于D.无法确定11.在下图中,从顶点 V1出发,按广度优选遍历图的顶点序列是( )(分数:2.00)A.V1 V5 V3 V4 V2 V6 V7B.V1 V5 V3 V4 V2 V7 V6C.V1 V7 V2 V6 V4 V5 V3D.V1 V2 V4 V7 V6 V5 V3 12.线性表 L=(a1,a 2,a 1,a n),下列说法正确的是( )(分数:2.00)A.每个元素都有一个直接前趋和直接后继B.线性表中至少要有一个元素C.表中诸元素的排列顺序必须是由
5、小到大或由大到小的D.除第一个元素和最后一个元素外,其余每个元素都有一个且仅有一个直接前趋和直接后继13.散列表的目的是( )(分数:2.00)A.插入B.删除C.快速查找D.排序14.设有一个无向图 G=(V,E)和 G=(V,E),如果 G是 G的生成树,则下面不正确的说法是( )(分数:2.00)A.G为 G的子图B.G为 G的连通分量C.G为 G的极小连通子图且 V=VD.G是 G的一个无环子图15.树最适合用来表示( )(分数:2.00)A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据二、B填空题/B(总题数:10,分数:20.00)16.对
6、于一个具有 n个结点的单链表,在已知 p结点后插入一个新结点的事件的时间复杂性为_,在给定值为 x的结点后插入一个新结点的时间复杂性为_。(分数:2.00)填空项 1:_17.设有两个串 p和 q,求 q在 p中首次出现的位置的运算叫 1。(分数:2.00)填空项 1:_18.对于一个长度为 n的线性表,假设表中各结点的查找概率相同,则在查找成功的情况下,平均查找长度为 1,如果 k不在表中,则需要进行 2 次比较后才能确定查找失败。(分数:2.00)填空项 1:_填空项 1:_19.在二叉排序树中,其左子树中任何一个结点的关键字一定 1 其右子树的各结点的关键字。(分数:2.00)填空项 1
7、:_20.数组 01n表示一个环形队列,设 f的值为队列中第一个元素的位置,r 的值为队列中实际队尾元素的位置加 1,并假定队列中至多只有 n-1个元素,则计算队列中元素个数的公式为 1。(分数:2.00)填空项 1:_21.一般来说,数组中的元素具有_的数据类型,并且数组元素的下标的上界和下界都是_的。(分数:2.00)填空项 1:_22.一个 nn的对称矩阵,如果以行为主序或以列为主序存入内存,则其容量为 1。(分数:2.00)填空项 1:_23.在线性表的顺序存储中,假设每个结点所占用的存储空间为 c,且第一个单元的存储地址则是该结点的存储地址,设开始结点 a1的存储地址是 LOC(a1
8、),则结点 a1存储地址 LOC(a1)可以通过下式得到 1。(分数:2.00)填空项 1:_24.在具有 n个单元的循环队列中,队满时共有 1 个元素。(分数:2.00)填空项 1:_25.查找表按其所包括的运算的不同分为_查找表和_查找表。(分数:2.00)填空项 1:_三、B解答题/B(总题数:4,分数:20.00)26.已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59),假设用散列函数为h(key)=key%13,现在如果采用拉链法解决冲突问题,请画出这组关键字的散列表。(分数:5.00)_27.已知有一关键字序列为486,7
9、9,596,34,900,120,789,179,703,307),如果我们采用基数排序方法对此序列进行排序(按照升序排列),请给出每一趟的排序结果。(分数:5.00)_28.写出二分查找的递归算法。(分数:5.00)_29.已知连通图如下: (分数:5.00)_四、B算法阅读题/B(总题数:4,分数:20.00)30.以下运算实现在循环队上取队头,请在_处用适当的语句予以填充。 int GetHead(CycqueueTp sq,DataType*x) if(sq.rear=_return(0); else*x=sq.data_; return(1); (分数:5.00)填空项 1:_31.
10、以下是图的广度优先搜索算法,请在_处填充适当的语句。 Bfs(GraphTp g,int v) QueptrTp Q; ArcNodeTp*P; InitQueue( printf(“%“”,v); visitedv=1; _ while(!EmptyQueue(Q) _; p=g.adjlistv.firstarc; while(p! =NULL) if(! visitedpadjvex) printf(“%“”,padjvex); visitedpadjvex=1); EnQueue( _; (分数:5.00)填空项 1:_32.以下为单链表的定位运算,分析算法,请在_处填上正确的语句。
11、int locate_iklist(1klist head,datatype x) /*求表 head中第一个值等于 x的结点的序号。不存在这种结点时结果为 0*/ p=head;j=O; while(_)p=pnext;j+; if(pdata=x)return(j); elsereturn(0); (分数:5.00)填空项 1:_33.下列算法用于判断带头结点的循环双链表 A是否对称相等,请在算法中的一填上正确的语句。 int dlink_symmetry(dlklist s) j=true; p=snext; q=sprior; while(p!=q) (_); else j=false
12、; return(j); (分数:5.00)填空项 1:_五、B算法设计题/B(总题数:1,分数:10.00)34.设计一个用链表表示的直接选择排序算法。(分数:10.00)_数据结构-1 答案解析(总分:100.00,做题时间:90 分钟)一、B单项选择题/B(总题数:15,分数:30.00)1.设数组 data0m作为循环队列 SQ的存储空间,front 为队头指针,rear 为队尾指针,则执行出队操作的语句为( )(分数:2.00)A.front:=front+1B.front:=(front+1)mod mC.rear:=(rear+1)mod mD.front:=(front+1)m
13、od(m+1) 解析:2.在 Hash函数 H(k)=k MOD m中,一般来讲,m 应取( )(分数:2.00)A.奇数B.偶数C.素数 D.充分大的数解析:3.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用( )存储结构。(分数:2.00)A.二叉链表B.广义表C.三叉链表 D.顺序解析:4.向一个栈顶指针为 Top的链栈中插入一个 s所指结点时,其操作步骤为( )(分数:2.00)A.Topnext=s;B.snext=Topnext;Topnext=s;C.snext=Top;top=s; D.snext=Top; Top=Topnext;解析:5.快速排序在
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学历 职业资格 数据结构 答案 解析 DOC
