《[高等教育]考题解答0506年福建专升本数据结构》由会员分享,可在线阅读,更多相关《[高等教育]考题解答0506年福建专升本数据结构(27页珍藏版)》请在金锄头文库上搜索。
1、06年转升本数据结构考题一、 单项选择题共12 小题,每题2分,共24分1、单链表结构为struct node int data; struct node *next;*p,*q,*r ;删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的选项是_C_A、 q=p-next; p-next=q-next;B、p-next=p-next-next;C、r=p-next; p-next=q-next;D、q=p-next; r=q-next; p-next=r;2、假设待排序对象序列在排序前已经按照关键字递增排列,那么采用_A_比拟次数最少。A、直接插入排序 O(n)B、快速排序 O(n2
2、)C、合并排序D、简单项选择择排序 O(n2)3、图的深度优先遍历类似于树的_C_A、后序遍历B、层次遍历C、前序遍历D、中序遍历4、求赋权有向图的最短路径常用的算法有_D_A、Prim算法和Kruskal算法B、Prim算法和Dijkstra算法C、Kruskal算法和Dijkstra算法D、Dijkstra算法和Floyd算法5、单链表中有n个结点,在其中查找值为x的结点,在查找成功时需要比拟的平均次数是_D_。A、nB、(n-1)/2C、n/2D、(n+1)/2解答: 查询每个元素需要比拟次数之和查询平均复杂度 = - 元素个数 1 + 2 + 3 +. +n n+1 = - = -n
3、2 思考:如果查找不成功,计算结果如何?6、线性表采用链式存储时,结点的存储地址_B_A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址项连续7、一棵非空的二叉树中,设根结点在第0层,在第i层上最多有_D_个结点。A、2(i+1)B、2iC、2(i-1)D、2i 根 层0 1个 / A B 层1 2个 / / A B C D 层2 4个8、在以下的排序算法中,算法的时间复杂度是O(n*log2n)是_D_。A、冒泡排序B、简单项选择择排序C、直接插入排序D、堆排序9、使用一个栈,每次限制进栈和出栈一个元素。假设进栈的元素序列依次是a、b、c、d;指出不可能的出栈序列_B_
4、。A、abcdB、adbcC、acbdD、dcba解答:A、 push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(),B、 没方法C、 push(a)、pop()、push(b)、 push(c)、pop()、pop()、push(d)、pop()D、 push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop()10、设数组queue作为循环队列Q的存储空间,front作为队头指针,rear作为队尾指针,那么执行出队操作后其头指针front的值为_A_。A、front=(front+1)%
5、mB、front=(front+1)%(m-1)C、front=(front-1)%mD、front=front+1解答:与方案1、2无关。11、对图进行广度优先遍历时,通常采用_C_来实现A、字符串B、B树C、队列E、 栈12、一个有n个结点k叉树,树中所有结点的度数之和是_B_。A、k+nB、n-1C、knD、n2解答:思路1:树中结点的度数=结点的儿子数n个结点k叉树,每个结点最多有k个儿子,叶子没有儿子,因此答案不是k*n。思路2:正确的做法:树中所有结点的度数之和=树中所有边条数,每一条边指向一个结点,每个结点有一条天线,指向父亲结点,除了根结点之外。故答案是B,n-1二、 填空题共
6、8 小题,11空,每空2分,共22分13、二叉树后序列表为CEDBA,中序列表为CBEDA,那么它的前序列表为_ABCDE_。解答:后序列表为CEDBA,因此根是A,中序列表为CBEDA,因此根只有左子树CBED,没有右子树A/CEDB后序,根是BCBED中序,左子树C,右子树EDA/B / C ED后序 ED中序A/B / C D /E14、N个结点的有向图,最多有_N*(N-1)_条边。15、存储图的最常用方法有两种,它们是_邻接矩阵_和_邻接表_。16、设有一个闭散列表的容量为m,用线性探测法解决冲突,要插入一个键值,假设插入成功,至多要进行_比拟。17、一棵哈夫曼树有29 个结点,其叶
7、子的个数是_15_。解答:哈夫曼树没有度为1的结点, 叶子数=内结点数+1 结点总数 =叶子数+内结点数 =2*叶子数-1 =2*内结点数+118、单链表的结点定义为struct node int data; struct node *next;在单链表中搜索结点p(由指向的结点)的后继结点的操作是_p=p-next_。19、双链表结点定义为struct node int data; struct node *left,*right;双链表中结点的left和right分别指向前驱和后继结点,在双链表中删除结点p(由指向的结点)的操作是:p-left-right=_p-right_;和p-rig
8、ht-left=_p-left_。20、对于队列,只能在_队尾_插入元素,在_队头_删除元素。三、 应用题共4小题,每题8分,共32分21、对图1所示的树(1) 结点A的度是_3_。(2) 树的度是_3_。(3) 画出其转换成相应二叉树的树形 A / | B C D/ / E F G H / I解答:一般树转换成二叉树步骤:将父亲管理儿子方式改为 父亲管理大儿子, 大儿子管理二儿子二儿子变成大儿子的右孩子二儿子管理三儿子三儿子变成二儿子的右孩子 A ABEFCDGIH 前 / EFBCIGHDA 中 B / FEIHGDCBA后 E C F D / G / I H22、参加排序的正整数序列是:
9、90、70、180、30、520、40、60、80、50、130。以第一个元素90作为基准元素,根据快速排序算法,写出完成第一趟划分后序列重新排列的情况。60、70、50、30、80、40、90、520、180、13023、一次输入如下序列中的各个整数,构造其相应的二叉搜索树,只需要画出最后生成的二叉搜索树的树形。整数序列是180、160、250、300、170、120、125、290、380。 180/ 160 250 / 120 170 300 / 125 290 38024、用Prim算法求图2所示的无向带权连通图的最小生成树。要求依次画出从顶点1出发的最小生成树的生成过程。 1 41/
10、 2 41/ 2 3 41/ 2 3 4/5四、 算法设计共2小题,第25小题10分,第26小题12分,共22分25、二叉树以二叉表为存储结构,结点结构的定义如下,请写出一个求二叉树中叶子结点个数的算法。typedef struct btnode *btlink;struct btnode TreeItem element; btlink left; btlink right;Btnode解答:与05年考题不一样int f(指向树根的指针)/f()计算树中叶子节点的个数 if(指向树根的指针=NULL)return 0; x=f(指向树根的左孩子指针); /左子树中叶节点数; y= f(指向树
11、根的右孩子指针);/右子树中叶节点数;if(root-left=NULL&root-right=NULL)return 1; else return x+y;/*或者 if( x=0&y=0)return 1; else return x+y;*/int f ( btlink root )/f()计算树中叶子节点的个数 if(root=NULL)return 0; x=f(root-left); /左子树中叶节点数; y= f(root-right);/右子树中叶节点数; if(x=0&y=0)return 1; else return x+y;T(n)=1+T(n1)+T(n2) n1+n2=n=1+1+T(n11)+T(n12)+1+T(n21)+T(n22) n1=n11+n12 n2=n21+n2225、二叉树以二叉表为存储结构,结点结构的定义如下,请写出一个求二叉树的高度算法。解答:int h(指向树根的指针)/f()计算树高度 if(指向树根的指针=NULL)return 0; x=h(指向树根的左孩子指针); /左子树高度; y= h(指向树根的右孩子指针);/右子树高度; if(xy)return x+1; else return y+1; /return (xy?x:y) +1;26、阅读以下程序,它是在的数组a中查找数值为x的元素,如果存在