发布时间 : 星期三 文章05到09年福建专升本数据结构真题详解更新完毕开始阅读6de880d43186bceb19e8bb2a
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) 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 解答： 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)%m B、front=(front+1)%(m-1) C、front=(front-1)%m D、front=front+1
解答：与方案1、2无关。
11、对图进行广度优先遍历时，通常采用__C__来实现 A、字符串 B、B树 C、队列 E、 栈
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，因此根只有左子树CBED，没有右子树
A /
CEDB后序，根是B
CBED中序，左子树C，右子树ED
A / B
/ \\
C ED后序
ED中序 A / B
/ \\
C D
/ E
14、N个结点的有向图，最多有___N*(N-1)_____条边。
15、存储图的最常用方法有两种，它们是___邻接矩阵____和____邻接表____。 16、设有一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个键值，若插入成功，至多要进行______比较。
17、一棵哈夫曼树有29 个结点，其叶子的个数是___15____。 解答：哈夫曼树没有度为1的结点， 叶子数=内结点数+1 结点总数
=叶子数+内结点数 =2*叶子数-1 =2*内结点数+1
18、已知单链表的结点定义为 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->right->left=___p->left_____。