欢迎来到天天文库
浏览记录
ID:49070678
大小:798.50 KB
页数:27页
时间:2020-02-27
《考题解答0506年福建专升本数据结构.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、06年转升本数据结构考题一、单项选择题(共12小题,每小题2分,共24分)1、已知单链表结构为structnode{intdata;structnode*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、快速排
2、序O(n2)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解答:查询每个元素需要比较次数之和查询平均复杂度=-------------------------
3、---------------------元素个数1+2+3+...+nn+1=----------------------------=--------n2思考:如果查找不成功,计算结果如何?6、线性表采用链式存储时,结点的存储地址__B___A、必须是不连续的B、连续与否均可C、必须是连续的D、和头结点的存储地址项连续7、一棵非空的二叉树中,设根结点在第0层,在第i层上最多有___D__个结点。A、2(i+1)B、2iC、2(i-1)D、2i根层01个/AB层12个//ABCD层24个8、在下列的排序算法中,算法的时间复杂度是O(n*log2n)是___D__。A、冒泡排序B、简
4、单选择排序C、直接插入排序D、堆排序9、使用一个栈,每次限制进栈和出栈一个元素。假设进栈的元素序列依次是a、b、c、d;指出不可能的出栈序列___B____。A、abcdB、adbcC、acbdD、dcba解答:A、push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(),A、没办法B、push(a)、pop()、push(b)、push(c)、pop()、pop()、push(d)、pop()C、push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop()10、设数组queue[]作为
5、循环队列Q的存储空间,front作为队头指针,rear作为队尾指针,则执行出队操作后其头指针front的值为__A___。A、front=(front+1)%mB、front=(front+1)%(m-1)C、front=(front-1)%mD、front=front+1解答:与方案1、2无关。11、对图进行广度优先遍历时,通常采用__C__来实现A、字符串B、B树C、队列D、栈12、一个有n个结点k叉树,树中所有结点的度数之和是__B__。A、k+nB、n-1C、knD、n2解答:思路1:树中结点的度数=结点的儿子数n个结点k叉树,每个结点最多有k个儿子,叶子没有儿子,因此答案不是k*
6、n。思路2:正确的做法:树中所有结点的度数之和=树中所有边条数,每一条边指向一个结点,每个结点有一条天线,指向父亲结点,除了根结点之外。故答案是B,n-1一、填空题(共8小题,11空,每空2分,共22分)13、已知二叉树后序列表为CEDBA,中序列表为CBEDA,则它的前序列表为__ABCDE__。解答:后序列表为CEDBA,因此根是A,中序列表为CBEDA,因此根只有左子树CBED,没有右子树A/CEDB后序,根是BCBED中序,左子树C,右子树EDA/B/CED后序ED中序A/B/CD/E14、N个结点的有向图,最多有___N*(N-1)_____条边。15、存储图的最常用方法有两
7、种,它们是___邻接矩阵____和____邻接表____。16、设有一个闭散列表的容量为m,用线性探测法解决冲突,要插入一个键值,若插入成功,至多要进行______比较。17、一棵哈夫曼树有29个结点,其叶子的个数是___15____。解答:哈夫曼树没有度为1的结点,叶子数=内结点数+1结点总数=叶子数+内结点数=2*叶子数-1=2*内结点数+118、已知单链表的结点定义为structnode{intdata;struc
此文档下载收益归作者所有