05到09年福建专升本数据结构真题详解

第第页05到09年福建专升本数据结构真题详解这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

06年转升本数据结构考题

一、单项选择题〔共12小题，每题2分,共24分〕1、已知单链表结构为structnode{intdata;

structnode*ne*t;}*p,*q,*r;

删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的选项是__C__A、

q=p-ne*t;p-ne*t=q-ne*t;

B、p-ne*t=p-ne*t-ne*t;

C、r=p-ne*t;p-ne*t=q-ne*t;

D、

q=p-ne*t;r=q-ne*t;p-ne*t=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个结点，在其中查找值为*的结点，在查找胜利时需要比较的平均次数是___D___。A、n

B、(n-1)/2C、n/2D、(n+1)/2解答：

查询每个元素需要比较次数之和查询平均繁复度=

元素个数

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、简约选择排序C、径直插入排序D、堆排序

9、运用一个栈，每次限制进栈和出栈一个元素。假设进栈的元素序列依次是a、b、c、d；指出不可能的出栈序列___B____。A、abcdB、adbc

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

C、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)%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

二、填空题〔共8小题，11空，每空2分,共22分〕

13、已知二叉树后序列表为CEDBA，中序列表为CBEDA，那么它的前序列表为__ABCDE__。

解答：后序列表为CEDBA，因此根是A，

中序列表为CBEDA，因此根只有左子树CBED，没有右子树

A/

CEDB后序，根是B

CBED中序，左子树C，右子树ED

A/B

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

/\

CED后序

ED中序A/B

/\

CD

/E

14、N个结点的有向图，最多有___N*(N-1)_____条边。

15、存储图的最常用方法有两种，它们是___邻接矩阵____和____邻接表____。16、设有一个闭散列表的容量为m，用线性探测法解决冲突，要插入一个键值，假设插入胜利，至多要进行______比较。

17、一棵哈夫曼树有29个结点，其叶子的个数是___15____。解答：哈夫曼树没有度为1的结点，叶子数=内结点数+1结点总数

=叶子数+内结点数=2*叶子数-1=2*内结点数+1

18、已知单链表的结点定义为structnode{intdata;

structnode*ne*t;};

在单链表中搜寻结点p(由指向的结点)的后继结点的操作是____p=p-ne*t___。19、已知双链表结点定义为structnode{intdata;

structnode*left,*right;};

双链表中结点的left和right分别指向前驱和后继结点，在双链表中删除结点p(由指向的结点)的操作是：p-left-right=___p-right______；和p-right-left=___p-left_____。

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

20、对于队列，只能在__队尾___插入元素，在___队头____删除元素。三、应用题〔共4小题，每题8分，共32分〕21、对图1所示的树

〔1〕结点A的度是_____3______。〔2〕树的度是______3_____。

〔3〕画出其转换成相应二叉树的树形A

/|\BCD

/\/\EFGH/

I

解答：一般树转换成二叉树步骤：

将父亲管理儿子方式改为父亲管理大儿子，

大儿子管理二儿子〔二儿子变成大儿子的右孩子〕

二儿子管理三儿子〔三儿子变成二儿子的右孩子〕

AABEFCDGIH前

/EFBCIGHDA中B

/\FEIHGDCBA后EC\\FD

/G/\IH

22、已知参与排序的正整数序列是：90、70、180、30、520、40、60、80、50、130。以第一个元素90作为基准元素，依据快速排序算法，写出完成第一趟划分后序列重新排列的状况。

60、70、50、30、80、40、90、520、180、130

23、一次输入如下序列中的各个整数，构造其相应的二叉搜寻树，只需要画出最末生成的二叉搜寻树的树形。整数序列是180、160、250、300、170、120、125、290、380。

180

/\160250/\\120170300

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

\/\

125290380

24、用Prim算法求图2所示的无向带权连通图的最小生成树。要求依次画出从顶点1出发的最小生成树的生成过程。

四、算法设计〔共2小题，第25小题10分，第26小题12分，共22分〕25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树中叶子结点个数的算法。

typedefstructbtnode*btlink;structbtnode{

TreeItemelement;btlinkleft;btlinkright;}Btnode

解答：与05年考题不一样

intf(指向树根的指针){//f()计算树中叶子节点的个数if(指向树根的指针==NULL)return0;

*=f(指向树根的左孩子指针);//左子树中叶节点数；y=f(指向树根的右孩子指针);//右子树中叶节点数；if(root-left==NULLroot-right==NULL)return1;

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

elsereturn*+y;/*或者

if(*==0y==0)return1;elsereturn*+y;*/}

intf(btlinkroot){//f()计算树中叶子节点的个数if(root==NULL)return0;

*=f(root-left);//左子树中叶节点数；y=f(root-right);//右子树中叶节点数；if(*==0y==0)return1;elsereturn*+y;}

T(n)=1+T(n1)+T(n2)n1+n2=n

=1+1+T(n11)+T(n12)+1+T(n21)+T(n22)n1=n11+n12n2=n21+n22

25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树的高度算法。解答：

inth(指向树根的指针){//f()计算树高度if(指向树根的指针==NULL)return0;

*=h(指向树根的左孩子指针);//左子树高度；y=h(指向树根的右孩子指针);//右子树高度；if(*y)return*+1;elsereturny+1;

//return(*y?*:y)+1;}

26、阅读以下程序，它是在已知的数组a中查找数值为*的元素，假如存在那么输出“found”，否那么输出“notfound”。试问它是什么方法实现的？并请完善程序。

用__________查找法。#defineN10

voidbs(inta[],int*){intl,r,m;l=0;r=N-1;

m=___(l+r)/2______;

while((_____l=r_______)(*!=a[m])){if(*a[m])l=_____m+1______;elser=m-1;m=(l+r)/2;}

if(___l=r____)

printf(notfound);else

printf(found);}

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

main(){

inta[N]={10,20,30,40,50,60,70,80,90,100};int*;

printf(input*:=);scanf(%d,*);bs(____a,*_______);}

05专升本数据结构考题

一、单项选择题：〔每题2分，共24分〕

1、双向链表的一个结点有(B)个指针。A、1B、2C、0D、3

2、在n个结点的顺次表中，算法的时间繁复度都是O(1)的操作是(A)。A、访问第i个结点(1≤i≤n)和求第i个结点的径直前趋(2≤i≤n)B、在第i个结点后插入一个新结点(1≤i≤n)C、删除第i个结点(1≤i≤n)D、将n个结点从小到大排序

3、在队列中存取数据的原那么是(A)。A、先进先出B、后进后出?C、先进后出D、不进不出

4、在栈中，出栈操作的时间繁复度为(A)。A、O(1)B、O(logn)C、O(n)D、O(n*n)

5、设长度为n的链队列用单循环链表表示，假设只设头指针，那么人队操作的时间繁复度为(C)。A、O(1)B、0(logn)C、0(n)D、O(n*n)

6、假如二叉树的叶结点数为n0，那么具有双分支的结点数n2等于(D)。A、nO+lB、n0C、2*n0D、n0-1

7、一棵二叉树满意以下条件：对任一结点，假设存在左、右子树，那么其值都小于它的左子树上全部结点的值，而大于右子树上全部结点的值。现采纳(B)遍历方式就可以得到这棵二叉树全部结点的递增序列。A、先根B、中根

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

C、后根D、层次

8、用邻接表表示图进行深度优先遍历时，其非递归算法通常采纳(A)来实现算法。

A、栈B、队列C、树D、图

9、广度优先遍历类似于二叉树的(D)。A、先序遍历B、中序遍历C、后序遍历D、层次遍历

10、在一个有向图中，全部顶点的人度之和等于全部顶点的出度之和的(B)。A、1／2倍B、1倍C、2倍D、4倍

11、任何一个带权无向连通图的最小生成树(B)。A、只有一棵B、一棵或多棵C、肯定有多棵D、可能不存在

12、设非空单链表的数据域为data，指针域为ne*t，指针P指向单链表的第i个结点，s指向生成的新结点，现将s结点插入到单链表中，使其成为第i结点，以下算法段能正确完成上述要求的是(C)。A、s-ne*t=p-；p-ne*t=s

B、p-ne*t=s；s-ne*t=p-ne*t；

C、S-ne*t=p-ne*t；p-ne*t=s；交换p-data和s-dataD、p=s；s-ne*t=p

二、填空题〔每空2分，共20分〕

1、数据的规律结构反映_____成分数据规律关系______。

2、对于队列，只能在___队尾_____插入元素，在____队头_____删除元素。3、算法是一运算序列，它应有：有限性、____确定性____、可行性、可以无任何输入，但需要___有输出____。

4、由一棵二叉树的前序序列和____中序序列____可唯一确定这棵二叉树的结构。

5、假如图的存储结构用____邻接表/邻接矩阵___表示，从某指定顶点作为初始点进行广度优先搜寻，得到的广度优先搜寻序列唯一。

6、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度____递增___的次序来得到最短路径的。

7、线性表(a1，a2，a3，an)(n=1)中，每个元素占c个存储单元，m为a1首地址，那么按顺次存储方式存储线性表，ai存储地址是_____m+(i-1)*c___。8、n个结点的无向图，最多有___n*(n-1)/2__条边。三、应用题(本大题共4小题，每题8分，共32分)

1、用Prim算法求下列图连通的带权图的最小代价生成树，在算法执行的某一刻，已选取的顶点集合U=[1，2，3]，边的集合TE=[(1，2)，(2，3)]，要选取下一条权值最小的边，应当从哪些边中选择?

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

2、假设用插入排序方法对线性表(25，84，21，47，]5，27，68，35，20)进行排序时，请给出前四趟排序结点序列的改变状况。答：25

2584212584212547843、已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出该二叉树。

A/\

BDCEFHG中DECBHGF后

4、设将整数a，b，c，d依次进栈，请回答：假设入、出栈次序为Push(a)，Pop()，Push(b)，Push(c)，Pop()，Push(d)，Pop()，那么出栈的字符序列是什么?答：acd

四、算法设计(本大题共3小题，每题8分，共24分)

1、二叉树以二叉链表为存储结构，类型声明如下，请写出一个求二叉树中结点个数的算法。

typedefstructnode{datatypedata；

structnode*Lchild；structnode*Rchild；}BinaTree；

答：intf(BinaTree*t){

if(t==NULL)return;else

returnf(t-left)+f(t-right)+1;

}

2、设线性表用顺次结构实现，声明如下：typedefstructsqlist{chardata[ma*size]；intn；

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

请写一个算法，判断其是否回文?(顺读与倒读一样如：“ababbaba为回文)答：

解法1：形参和实参径直传递结构变量#includestdio.h

#defineMA*LENGTH100

typedefstructsqlist{

chardata[MA*LENGTH];intn;}Sqlist;

voidf(Sqlista){inti;

if(a.n=0)return;

for(i=0;i(a.n)/2;i++){

if(a.data[i]!=a.data[a.n-i]){

printf(No);return;

}

printf(Yes);}}

voidmain(){Sqlists;

printf(输入n:);scanf(%d,s.n);

printf(输入字符串:);scanf(%s,s.data);f(s);}

解法2：形参是指针变量，实参是结构变量地址值voidf(Sqlist*a){inti;

if(a-n=0)return;for(i=0;i(a-n)/2;i++)

if(a-data[i]!=a-data[a-n-i-1]){printf(No);return;}

printf(Yes);}

voidmain(){

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

printf(inputn:);scanf(%d,(s.n));printf(inputdata:);scanf(%s,s.data);f(s);}

解法3：类似解法2，为指针变量定义了类型List#includestdio.h

#defineMA*LENGTH100

typedefstructsqlist*List;

typedefstructsqlist{

chardata[MA*LENGTH];intn;}Sqlist;

voidf(Lista){inti;

if(a-n=0)return;for(i=0;i(a-n)/2;i++)

if(a-data[i]!=a-data[a-n-i-1]){printf(No);return;}

printf(Yes);}

voidmain(){Sqlists;

printf(inputn:);scanf(%d,(s.n));printf(inputdata:);scanf(%s,s.data);f(s);}

3、阅读以下程序，判断它是用什么方法实现排序(升序)的?并完善以下程序。#includestdio.h

voidbubble(int[],int);

main(){

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

intarray[]={55，2，6，4，32，12，9，73，26，37};intsize=sizeof(array)/sizeof(int)；bubble(_array,10___)；}

voidbubble(inta[]，intsize){inti，temp；

intend_____=0__________；intpass=1；

//=======================while(!endpasssize){end=1；

for(i=0，isize-pass；i++)if(—a[i]a[i+1]—){temp=a[i]；a[i]=a[i+1]；a[i+1]=temp；

end=___0__________；}

__pass++__________________;}

//=======================for(i=0；isize；i++)printf(%d，a[i])；}

第二部分数据结构〔共100分〕

一、单项选择题〔本大题共12小题，每题2分，共24分〕

在每题列出的四个备选项中只有一个符合题目要求，请将正确答案代码填写在答题纸相应的位置上。写在试卷上不得分。

1．在待排序记录已基本有序的前提下,下述排序方法中效率最高的是：

A)径直插入排序B)简约选择排序C)快速排序D)归并排序

2．以下哪一个术语与数据的存储结构无关？

A)栈B)闭散列表C)线索二叉树D)双向链表

3．有6个元素6,5,4,3,2,1的顺次进栈，问以下哪一个不是合法的出栈序列：

A)5,4,3,6,1,2B)4,5,3,1,2,6C)3,4,6,5,2,1D)2,3,4,1,5,64．下述哪一条是顺次存储方式的优点？

A)存储密度大B)插入运算方便

C)删除运算方便D)可方便地用于各种规律结构的存储表示5．对于只在表的首、尾进行插入操作的线性表，宜采纳的存储结构为:

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

A)顺次表B)用头指针表示的单循环链表C)用尾指针表示的单循环链表D)单链表6．对包含n个元素的散列表进行查找，平均查找长度

A)为O(log2n)B)为O(n)C)为O(nlog2n)D)不径直依靠于n7．以下哪一种图的邻接矩阵是对称矩阵？

A)有向图B)无向图C)AOV网D)AOE网

8.设表(a1,a2,a3,,a32)中的元素已经按递增顺次排好序，用二分法检索与一个给定的值k相等的元素，假设a1ka2，那么在检索过程中比较的次数是：A)3B)4C)5D)69.具有3个结点的二叉树最多可有多少种不同的形态。

A〕2B〕3C〕4D〕5

10．对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，那么可采纳的编号方法是：

A、先序遍历B、中序遍历C、后序遍历D、从根开始进行层次遍历

11.在长度为n的顺次表的第i(1≤i≤n+1)个位置上插入一个元素，元素的

移动次数为：

A)n-i+1B)n-iC)iD)i-112.对于一个无向图，以下说法正确的选项是

A)每个顶点的入度大于出度；

B)每个顶点的度等于其入度与出度之和；C)无向图的邻接矩阵肯定是对称矩阵；

D)有向图中全部顶点的入度之和大于全部顶点的出度之和；

二、填空题〔本大题共10小题，每空2分，共22分〕

请在答题纸相应的位置上填写正确答案。写在试卷上不得分。

13.设一哈希表表长M为100，用除留余数法构造哈希函数，即H〔K〕=K%P

〔P=M〕,为使函数具有较好性能，P应选97

14.N个结点的二叉树采纳二叉链表存放，共有空指针域个数为15.假设一个算法中的语句频度之和为T(n)=3720n+4nlogn，那么算法的时间繁复

度为_______O(nlogn)_________。

16.已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将累加。

17.深度为6〔根深度为1〕的二叉树至多有18.一棵具有n个叶子结点的哈夫曼树中，结点总数为。

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

19.设单链表结点的定义如下：

structnode{

intdata,

structnode*ne*t;};

要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最末一个结点的地址为t,那么应执行操作：________和_________。

20.设单链表结点的定义如19题，现有一个含头结点的单链表，头指针为head,

那么判断该单链表是否为空表的条件为head-ne*t==NULL。

21.n个顶点的连通无向图至少有条边。

22.在顺次存储结构的线性表中插入一个元素，平均需要移动素.

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

三、应用题：〔本大题共4小题，每题8分，共32分〕请在答题纸相应的位置上填写正确答案。写在试卷上不得分。

23．已知有向图如图1所示：

〔1〕写出顶点B的度〔2分〕；

〔2〕写出从结点D开始的两个广度优先搜寻序列〔2分〕；〔3〕画出该图的邻接表〔4分〕。解答:

〔1〕顶点B的度:_______3________(2分)

〔2〕_________DBCA______和_____DCBA______(2分)〔3〕(4分

)

图1

或

24.已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，画出对应的二叉树。解答:

A/\

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

BC

/\/DEF/G

25.图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请画出该图的最小代价支撑树，并计算最小代价支撑树的权。

图2

解答:

〔每条边1分，画方框的两条边任选一条〕

最小代价支撑树的权=56〔3分〕

26.设一个闭散列表具有10个桶，散列函数H〔*〕=*%7，假设元素输入顺次为：

{50，42，85，22，76，19，34，68}，解决冲突用线性重新散列技术，要求画出构造好的散列表。

解答:〔8分，第二行每个数字1分〕

四、算法设计〔本大题共2小题，第27小题10分，第28小题12分，共22分〕请在答题纸相应的位置上填写正确答案。写在试卷上不得分。

27.二叉搜寻树T用二叉链表存储结构表示，其中各元素的值均不相同。编写算

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

法，按递减顺次打印T中各元素的值。结点结构定义如下：typedefintTreeItem;

typedefstructbtnode*btlink;typedefstructbtnode{TreeItemdata;btlinkleft,right;}BTNODE;解答:

voidf(btlinkt){//或voidf(BTNODE*t)if(t){

f(t-right);

printf(%d,t-data);f(t-left);}}

28.阅读下面程序，其功能是调整线性表中的元素，将全部奇数放在表的左边，将全部偶数放在表的右边。请填空完成该程序。〔每空1分，共12分〕

#defineMA*SIZE100typedefintElemType;typedefstruct{

ElemTypeelem[MA*SIZE];intlast;/*末元素下标*/

}SeqList;

voidAdjustSqlist(SeqList*L){

ElemTypetemp;inti=0,while(ij){

]%2!=0

i++;

]%2==0)

j--;

)break;

temp=L-elem[i];

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

}

}

voidmain(){

SeqList;

intr,i;}

解答:〔每空1分，共12分，大小写不能错〕

⑴、_______L-last_____________⑶、_______iL-last或ij______⑸、_______j0或ij_____________⑺、_______L-elem[j]__________⑼、_______*sq_________________⑾、_______r-1_________________

⑵、_______i______________________⑷、_______j______________________⑹、_______i=j___________________⑻、______temp__________________⑽、_______SeqList*_____________⑿、_______sq-elem[i]____________

)malloc(sizeof(SeqList));printf(请输入线性表的长度:);scanf(%d,r);

sq-last=printf(请输入线性表的各元素值:\n);

);AdjustSqlist(sq);

08专升本数据结构考题解答

一、单项选择题〔共12小题，每题2分，共24分〕1．用非递归方法实现递归算法时通常要运用A．循环队列B．栈

C．二叉树

D．双向队列

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

06年转升本数据结构考题

一、单项选择题〔共12小题，每题2分,共24分〕1、已知单链表结构为structnode{intdata;

structnode*ne*t;}*p,*q,*r;

删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的选项是__C__A、

q=p-ne*t;p-ne*t=q-ne*t;

B、p-ne*t=p-ne*t-ne*t;

C、r=p-ne*t;p-ne*t=q-ne*t;

D、

q=p-ne*t;r=q-ne*t;p-ne*t=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个结点，在其中查找值为*的结点，在查找胜利时需要比较的平均次数是___D___。A、n

B、(n-1)/2C、n/2D、(n+1)/2解答：

查询每个元素需要比较次数之和查询平均繁复度=

元素个数

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、简约选择排序C、径直插入排序D、堆排序

9、运用一个栈，每次限制进栈和出栈一个元素。假设进栈的元素序列依次是a、b、c、d；指出不可能的出栈序列___B____。A、abcdB、adbc

这是我自己整理的福建省专升本数据结构历年真题的具体答案,盼望对学弟学妹们有所援助,那些去补习的都是没什么用的!

C、acbdD、dcba解答：A、push(a)、pop()、push(b)、pop()、push(c)、pop()、push(d)