考题解答0506年福建专升本数据结构.doc

06年转升本数据结构考题 单项选择题（共12 小题，每小题2分,共24分） 1、已知单链表结构为 struct node{ int data; struct node *next; }*p,*q,*r ; 删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是__C__ 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) 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、n B、(n-1)/2 C、n/2 D、(n+1)/2 解答： 查询每个元素需要比较次数之和 查询平均复杂度 = ---------------------------------------------- 元素个数 1 + 2 + 3 +... +n n+1 = ---------------------------- = -------- n 2 思考：如果查找不成功，计算结果如何？ 6、线性表采用链式存储时，结点的存储地址__B___ A、必须是不连续的 B、连续与否均可 C、必须是连续的 D、和头结点的存储地址项连续 7、一棵非空的二叉树中，设根结点在第0层，在第i层上最多有___D__个结点。 A、2(i+1) B、2i C、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____。 A、abcd B、adbc C、acbd D、dcba 解答： push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)、pop(), 没办法 push(a)、pop()、push(b)、 push(c)、pop()、pop()、push(d)、pop() push(a)、push(b)、push(c)、push(d)、pop()、pop()、pop()、pop() 10、设数组queue[]作为循环队列Q的存储空间，front作为队头指针，rear作为队尾指针，则执行出队操作后其头指针front的值为__A___。 A、front=(front+1)%m B、front=(front+1)%(m-1) C、front=(front-1)%m D、front=front+1 解答：与方案1、2无关。 11、对图进行广度优先遍历时，通常采用__C__来实现 A、字符串 B、B树 C、队列 栈 12、一个有n个结点k叉树，树中所有结点的度数之和是__B__。 A、k+n B、n-1 C、kn D、n2 解答： 思路1：树中结点的度数=结点的儿子数 n个结点k叉树，每个结点最多有k个儿子，叶子没有儿子，因此答案不是k*n。 思路2：正确的做法： 树中所有结点的度数之和=树中所有边条数， 每一条边指向一个结点，每个结点有一条天线，指向父亲结点，除了根结点之外。故答案是B，n-1 填空题（共8 小题，11空，每空2分,共22分） 13、已知二叉树后序列表为CEDBA，中序列表为CBEDA，则它的前序列表为__ABCDE__。 解答：后序列表为CEDBA，因此根是A， 中序列表为CBEDA，