数据结构试题A.docx

数据结构试题A.docx

《数据结构试题A.docx》由会员分享，可在线阅读，更多相关《数据结构试题A.docx（11页珍藏版）》请在冰点文库上搜索。

数据结构试题A

一、单项选择题（在每小题的4个备选答案中，选出1个正确的答案，并将其号码填在题干的括号内。

每小题2分，共30分）

1．若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用（）存储方式最节省时间。

A）单链表B）双链表C）单向循环链表D）顺序表

2．串是任意有限个（）

A）符号构成的序列B）符号构成的集合C）字符构成的序列D）字符构成的集合

3．设矩阵A的任一元素

满足：

现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中，每个元素占有4个单元，则元素A[9,5]的首地址为（）。

A）2340B）2336C）2164D）2160

4．如果以链表作为栈的存储结构，则退栈操作时（）

A）必须判别栈是否满B）对栈不作任何判别C）必须判别栈是否空D）判别栈元素的类型

5．设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）

A）front=front+1B）front=（front+1）%mC）rear=（rear+1）%mD）front=（front+1）%（m+1）

6．深度为6（根的层次为1）的二叉树至多有（）结点。

A）64B）32C）31D）63

7．将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。

则编号为49的结点X的双亲的编号为（）。

A）24B）25C）23D）无法确定

8．设有一个无向图G=（V,E）和G’=（V’,E’），如果G;G的生成树，则下面不正确的说法是（）。

A）G’为G的子图B）G’为G的连通分量C）G’为G的极小连通子图且V’=VD）G’为G的一个无环子图

9．下列序列中，（）是执行第一趟快速排序后得到的序列。

（排序的关键字类型是字符

串）

A）[da，ax，eb，cd，bb]ff[ha，gc]B）[ge，ax，eb，cd，bb]ff[da，ha]

C）[cd，eb，ax，da]ff[ha，gc，bb]D）[ax，bb，cd．da]ff[eb，gc，ha]

10．二分查找要求被查找的表是（）。

A）键值有序的链接表B）链接表但键值不一定有序

C）键值有序的顺序表D）顺序表但键值不一定有序

11．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）。

A）n2B）nlog2nc）log2nD）n-1

12．堆是一个键值序列（k1，k2，…，kn），对i=1，2，…，

，满足（）。

A）ki≤k2i≤k2i+1B）ki

C）ki≤k2i且ki≤k2i+1（2i+l≤n）D）ki≤k2i或ki≤k2i+1（2i+1≤n）

13．使用双向链表存储数据，其优点是可以（）。

A）提高检索速度B）很方便地插入和删除数据

C）节约存储空间D）很快回收存储空间

14．设计一个判别表达式中左右括号是否配对出现的算法，采用（）数据结构最佳。

A）线性表的顺序存储结构B）栈

C）队列D）线性表的链式存储结构

15．设高度为k的二叉树上只有度为0和2的结点，则此类二叉树中所含的结点数至少为（）。

A）k+lB）2kC）2k-1D）2k+1

二、填空题（每空2分，共28分）

1．设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是r=s；r->next=NULL。

2．在单链表中，指针p所指结点为最后一个结点的条件是。

3．设一个链栈的栈顶指针是ls，栈中结点格式为

，栈空的条件是____________。

如果栈不为空，则退栈操作为p=ls；；free（p）。

4．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树中有个叶子结点。

5．树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和。

6．n个顶点的连通图的生成树有条边。

7．一个有向图G中若有弧、和，则在图G的拓扑序列中，顶点vi，vj和vk的相对位置为________。

8．设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序、冒泡排序和归并排序方法对其进行排序（按递增顺序），__最省时间，__最费时间。

9．下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。

typedefstructnode

{intkey；

structnode*left,*right；

}

voidsearchinsert（intx;pnodet）

/*t为二叉排序树根节点的指针*/

{if（_____）

{p=malloc（suze）；

p->key=x;p->left=NULL；

p->right=NULL；

t=p；

}

else

if（xkey）searchinsert（x,t->left）

else_____

}

10.线性表的___主要有点是从表中任一结点出发能访问到所有结点。

而使用____________，可根据需要在前后两个方向上方便地进行查找。

三、应用题（本题共28分）

1.树的后根遍历方法是：

若树非空，则

1）依次后根遍历根的各个子树T1，T2，……，Tm；

2）访问根节点。

对图1所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。

（4分）

图1树

2.将图2的森林转换成二叉树。

（4分）

图2森林

3.图3表示一个地区的交通网，顶点表示城市，边表示连接城市间的公路，边上的权表示修建公路花费的代价。

怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。

（4分）

图3网

4．已知一个无向图的邻接表如图4所示。

V1

2

4

∧

V2

5

4

1

∧

V3

4

5

∧

V4

3

2

1

∧

V5

3

2

∧

图4邻连表

1）画出这个图。

2）以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。

（本题4分，每小题2分）

5．设n个元素的有序表为R，K为一个给定的值，二分查找算法如下：

intbinswarth（sqlistR；keytypeK）

{L=1；h=n；suc=0；

while（（L<=h）＆＆（!

suc）

{mid=（L+h）／2；

switch

{K=R[mid].key：

suc=L；break；

k

h=mid-l；break；

K>R[mid].key：

L=mid+1

}

}

if（suc）return（mid）elsereturn（0）；

}

将上述算法中划线语句改为：

K

h=mid。

1）改动后，算法能否正常工作?

请说明原因。

2）若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能正常工作，请给出一个查找序列和查找某个键值的比较次数。

（本题6分，每小题3分）

6．有一组键值25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序，请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。

（本题6分）

四、设计题（共14分）

1.设一颗二叉树以二叉链表为存储结构，结点结构为

。

设计一个算法，求在先根序列中处于第k个位置的结点。

（本题6分）

2.设某个单链表L的结点结构为

，试画出该链表的结构图，并用C语言编写算法，判断该链表的元素值是否是递增的。

（本题8分）

数据结构导论模拟试卷

（一）分析与解答

一、单项选择题

1，D．2，C．3，D．4，C．5，D．6，D．7，A．8，B．9，A．10，C．11，D．12，C．13，A．14，B．15，C。

二、填空题

1.分析：

在r所指链尾插入了所指结点，需执行的三步操作是：

1）r->next=s；

2）r=s；

3）r->next=NULL

答案：

r->next=s。

2.分析：

单链表最后一个结点的指针域为空，所以可用p->next==NULL作为判断最后一个结点的条件。

3.分析：

当栈空时，栈顶指针为空，故判栈空条件为ls==NULL。

栈非空时，退栈操作步骤为：

1）p=ls；

2）ls=ls->link；

3）free（p）

答案：

ls==NULL，ls=ls->link。

4.分析：

设n1=2,n2=3,n3=4,

树的总结点数为n=n0+n1+n2+n3。

（1）

树的分支树为n-1=n1+2n2+n3。

（2）

（2）-

（1）：

-1=n2+2n3-n0

有n0=n2+2n3+1=3+2×4+1=12

答案：

12。

5.答案：

双亲表示法。

6.分析：

n个顶点的连通图，其生成树有且仅有n-1条边。

答案：

n-1。

7.分析：

按题意画出图5所示示意图。

由此知，在拓扑序列中i,j,k的相对位置是i,j,k。

图5有向图G的局部示意图

答案：

i,j,k。

8.分析：

对冒泡排序来讲，由于哨兵的作用，经一趟排序后，就能判断出当前无序区已经自然有序，终止算法。

故它最省时间。

对快速排序来讲，由于待排序空间是有序的，每趟排序后，中间元素的左边总是一个空区域，而右边区域长度仅比上一趟少1。

因此当在最坏情况下，占用时间最长。

答案：

冒泡排序、快速排序。

9.答案：

t==NULL,searchinsert（x,t->right）。

10.分析：

线性表的存储方式有多种，其中循环链表的主要优点是从表中任一结点出发，都能访问到所有其它的结点。

而如果采用双向链表，则可以按前后两个方向进行查找。

答案：

循环链表、双向链表。

三、应用题

1.答案：

EBFGCKHIJDA。

2.分析：

先将每棵树转换成二叉树，然后再将各二叉树的根结点作为兄弟连接在一起。

而树转换成二叉树的方法是，先将兄弟结点连在一起，然后除最左边的孩子外，断开其它双亲到孩子的连线。

答案：

如图6所示。

（a）先将各树转换成二叉树

（b）以结点为中心旋转45°

（c）将各二叉树组合在一起

图6森林转换成二叉树

3.分析：

本题实际上是求最小生成树问题。

由于图中有两条权值为6的边，故可以得到两种方案。

答案：

如图7所示。

图7由网络得到的最小生成树

4.答案：

（1）如图8所示。

图8图4所示邻接表所对应的图

（2）v1v2v4v5v3和v1v4v2v3v5。

5．分析：

经过改动以后，有可能出现死循环，比如当查找的键值k小于有序表中的最小键值时，就会出现死循环。

答案：

（1）算法不能正常运行。

（2）假设有序表的查找序列为（7，10，12，16，24，39，42），当待查的键值为k=5时，出现死循环。

6．答案：

25842l471527683520

第一趟[201521]25[4727683584]

第二趟[15]20[21]25[3527]47[6884]

第三趟15202125[27]354768[84]

得到：

15202l252735476884

第一趟排序过程中键值的移动情况如图9所示。

图9键值移动示意图

四、设计题

1．分析：

因为是求前根序列中处于第k个位置的结点，所以本算法是按前根遍历来实现的。

在这当中，访问根结点的操作就是计算器count加1，然后判断count是否等于k，等于k就退出并返回指向对应结点的指针，否则继续按前根遍历往下查找。

答案：

Viodsearch（bitreptrt；integerk）

{if（t!

=NULL）

{count++；

if（count==k）return（t）；

else{search（t->lchild,k）；

search（t->rehild，k）；

}

}

}

2．分析：

判断一个单链表是否递增，只要从起始结点开始，依次向后比较前一个结点的键值是否小于后一个结点的键值。

答案：

单链表L的结构如图10所示。

图10单链表L的结构

参考答案：

intisviset（lklistL）//1分

{p=L;//1分

while（p->next!

=NULL）//1分

if（p->datanext->data）//1分

p=p->next;//1分

else

return（0）;//1分

return

（1）;//1分

}

另：

整个函数结构1分。