西华大学数据结构综合期未试题.doc

西华大学数据结构综合期未试题.doc

《西华大学数据结构综合期未试题.doc》由会员分享，可在线阅读，更多相关《西华大学数据结构综合期未试题.doc（7页珍藏版）》请在冰点文库上搜索。

年级专业：

教学班号：

学号：

姓名：

装订线

课程名称：

数据结构考试时间：

110分钟

课程代码：

8401801试卷总分：

100分

一、选择题（在每个小题四个备选答案中选出一个正确答案）（本大题共20小题，每小题1.5分，总计30分）

1、数据的基本单位是（B）。

A.数组元素B.数据元素

C.数据项D.数据对象

1、性质相同的数据元素的集合是（D）。

A.数组元素B.数据元素

C.数据项D.数据对象

2、下列选项中哪个不属于算法重要特性？

（D）

A.有穷性和确定性B.可行性

C.输入和输出D.可视化和模块化

2、算法的效率一般是指（A）。

A.算法的执行时间B.算法所需要存储空间

C.算法的可读性D.算法处理的数据量

3、如一个线性表中的数据元素是由若干个数据项组成，人们通常把这样的数据元素又称为（A）。

A.记录B.字段

C.属性D.数据项集合

3、在线性表的抽象数据类型定义中，下列哪个是其数据关系的描述？

其中ai指数据元素，D指数据对象。

（B）

A.R={|ai,an∈D,i=1,2…,n}B.R={|ai,an∈D,i=1,2…,n-1}

C.R={|ai,an∈D,i=1,2…,n}D.R={|ai,an∈D,i=2,3…,n-1}

4、与数组相比，用链表表示线性表的主要优点是（C）。

A.便于随机存取B.花费的存储空间比顺序表少

C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同

4、与链表相比，采用数组表示性线表的主要优点是（A）。

A.便于随机存取B.花费的存储空间比顺序表少

C.便于插入与删除D.数据元素的物理顺序与逻辑顺序不一定相同

5、下列关于栈说法正确的是（A）。

A.栈是限定在表尾部进行插入和删除操作的线性表B.一般使用链作栈存储结构，不可使用数组C.栈是先进先出的一种结构D.栈有栈顶和栈底，可从栈顶或栈底开始取元素

5、下列关于栈的说法正确的是（C）

A.在顺序栈中，栈底指针是可随意移动的B.空栈时，栈顶和栈底指针只相差1.C。

非空栈时，栈顶指针始终是指向栈顶元素的下一个位置上D.删除栈顶元素时，栈顶指针加1

6、如果入栈的序列为（A,B,C,D），则不可能的出栈序列为（）。

A.（A,B,C,D）B.（D,C,B,A）C.（A,C,D,B）D.（C,A,B,D）

7、下列哪种情况不使用队列作存储结构（C）。

A.操作系统中的作业管理B.打印时的多个任务输出C.数制转换D.模拟银行业务窗口客户等待状态

7、在用数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是（）。

A.front=maxSizeB.rear=maxSize

C.（rear+1）%maxSize=frontD.rear=front

8、下列关于串的说法正确的是（B）。

A.串是由n个字符组成的有限序列（n>0）B.串有任意个必须连续的字符组成的子序列称为原串的子串

C.截取子串的操作通常称为模式匹配D.串只能采用定长存储

8、下列关于串的说法正确的是（D）。

A.串一般记为s=’a1a2…an’（n>0）B.空串和空格串是同一个概念

C.串的堆分配存储表示中，存储单元是在程序执行之前分配好的

D.模式串中的每个字符必须与依次和主串中的一个连续字符序列相等才叫模式匹配成功

9、若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为（）。

A.BCDAGFEB.CDBFGEA

C.CDBAGFED.CDBGFEA

9、若度为m的广义哈夫曼树中，总叶子个数为n，其非叶子结点的个数有（A）个。

A.（n-1）/（m-1）B.（n-1）/（m）

C.（n）/（m-1）D.无法确定

10、下列存储形式中，（）不是树的存储形式。

A.广义表表示法B.顺序存储表示法

C.双亲表示法D.左子女右兄弟表示法

10、向一个有51个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

    A．8  B。

25.5  C。

25  D。

51

11、n个顶点的无向完全图有（ ）条边。

A．n*（n-1 ）/2          B.n                 C.n+1             D.2N

11、要连通n个顶点至少需要（）条边

A、n B、n+1 C、n-1 D、n/2

12、下列有关图的概念中，不正确的是（）。

A、与图的边或孤相关的数字叫做权 B、任何图中与某顶点相连的边或孤叫出度 C、在图中，起点与终点相同的路径称为回路 D、连通分量是指无向图中的极大连通子图

12、下列有关图的概念中，不正确的是（）。

A、在图中常用（w,v）表示一条边 B、一个连通图的生成树是一个极小连通子图 C、一般情况下，图是可以用数据元素在存储区中的物理位置来表示元素之间的关系的 D、在无向图中，第i个链表中的结点数就是顶点vi的度。

13、下列什么情况下适合采用顺序查找法（C）。

A、数据元素事前基本有序 B、数据元素呈非递减顺序 C、数据元素无序 D、数据元素分块时，块间有序，块内无序

13、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）

A、插入排序 B、选择排序 C、快速排序 D、归并排序

14、下面程序段的时间复杂性为（C）。

y=0;

while（n>=（y+1）*（y+1））{y++;}

A、O（n）B、O（n2）C、O（sqrt（n））D、O

（1）

14、下面程序段的时间复杂性为（）。

m=0

for（I=1;I<=n;I++）

for（j=1;j<=I;j++）{m++;}

A、O（n）B、O（n2）C、O（sqrt（n））D、O

（1）

15、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是（C）

A、二叉排序树B、哈夫曼树C、堆D、AVL树

15、如果一个二叉树满足堆的条件且任意一个非叶子结点的关键字天于其孩子的关键字，则此时的n个元素的序列满足的条件是（B）。

A、ki<=k2i且ki<=k2i+1B、ki>=k2i且ki>=k2i+1

C、ki+1<=k2i且ki+1<=k2i+1D、ki<=k2i+1且ki+1<=k2i+1

15、下列关于选择排序中，说法不正确的是（B）。

A、简单选择排序一趟只能完成从序列中选出关键字最大（或最小）的记录B、简单选择排序的时间复杂度为O（n）C、锦标赛排序法的思想同源于简单选择排序D、堆排序可解决锦标赛排序法的辅助存储空间过多和多余的比较的不足

16、以下排序方式中占用O（n）辅助存储空间的是（D）

A、简单排序 B、快速排序 C、堆排序 D、归并排序

16、从任意节点开始不能访问所有节点数据的存储结构是（）

A、单链表 B、双链表 C、循环单链表 D、循环双链表

17、在线索化二叉树中，节点t没有左子树的充要条件是（B）

A、t->lchild==NULL B、t->ltag==1

C、t->ltag==1且t->lchild==NULL D、以上答案都不对

17、在线索化二叉树中，节点t没有右子树的充要条件是（B）

A、t->rchild==NULL B、t->rtag==1

C、t->rtag==1且t->rchild==NULL D、以上答案都不对

18、采用折半查找方法进行查找，数据文件应为（），且限于（）。

A.有序表顺序存储结构B.有序表链式存储结构

C.随机表顺序存储结构D.随机表链式存储结构

 18、就平均查找速度而言，下列几种查找速度从慢至快的关系是（）。

A.顺序折半哈希分块B.顺序分块折半哈希

C.分块折半哈希顺序D.顺序哈希分块折半

19、将递归算法转换为非递归算法时，一般要设置一个（）辅助结构。

A、堆栈或队列 B、数组 C、堆栈 D、队列

19、在广度优先遍历树时，需要设置一个（C）辅助结构。

A、 数组 B、 堆栈或队列 C、 队列 D、堆栈

20、由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为（）。

A.60B.66C.67D.50

20、有一文件的关键字序列为：

[9][5][7][2][3][8][4][6][11][43]，如采用二路归并排序算法，则第二趟归并结果为:

（）

A.[257934][681143]

B.[25][79][34][68][1143]

C.[2579][3468][1143]

D.[95][72][38][46][1143]

二、填空题（本大题共10题，每空2分，总计20分）

1、数据元素相互之间的关系存在四种基本结构，它们是集合、线性结构、树结构、图。

1、数据元素在计算机内的两种不同的存储结构是：

顺序存储结构和链式。

2、线性表中的一个结点包括：

数据域和指针域。

2、若二叉树有m个叶子结点，则度为2的结点有m-1个.

3、栈和队列都是限制存取点的线性结构。

3、在用栈实现表达式求值的过程中，使用了两个栈，一个用来寄存操作数或运算结果，另一个用来寄存运算符.

4、树中某结点的子树的数目称为：

叶子结点。

4、树内各结点的度的最大值称为：

树的度。

5、深度为k的二叉树最大结点数为:

2^k-1。

5、如果一棵二叉树终端结点数为n0,度为2的结点数为n2，则n0和n2满足的数学关系式为：

N0=n2+1。

6、中缀表达式a*b-c对应的前缀表达式为-*abc.

6、中缀表达式a*b-c对应的后缀表达式为ab*c-.

7、对二叉树以某种次序遍历使其变为线索二叉树的过程叫线索化.

7、用一维数组存放一颗完全二叉树：

ABCDEFGHIJKL，则后序遍历该二叉树的结点序列为

。

8、若一棵二叉树的任意非叶子结点值大于其左子树上所有结点值，同时小于其右子树上所有结点值，则此二叉树是一棵排序二叉树树。

8、若一棵二叉树的任意结点的左子树和右子树的深度之差不超过1，则此二叉树是平衡二叉树。

9、设图G有n个顶点和e条边，则进行深度优先的时间复杂性为__O（n+e）____。

9、设图G有5个顶点，若采用邻接矩阵存储结构，则此矩阵有25个元素。

10、如果查找表内的各子表的最大关键字呈有序状态，则最适合的查找算法是分块。

10、能使用折半查找方法的线性表的前提条件是有序。

三、判断题（本大题共10题，每小题1分，总计10分

1.每一种数据的逻辑结构和物理结构总是一致的.（N）

1.      顺序结构存储方式只能用于存储线性结构。

（N）

2.      消除递归不一定要使用栈.（Y  ）

2.      中序遍历二叉排序树就可以得到排好序的结点序列。

（Y）

3.      图的深度优先遍历类似于树的中序遍历。

（N  ）

3．图的广度优先遍历类似于树的层次遍历（Y）

4．栈通常有两种存储表示方法，即顺序栈和链式栈（Y）

4．二叉树的左右子树不能随意颠倒（Y）

5．在树中，其双亲在同一层的结点相互称为堂兄弟结点（Y）

5．二叉树的第I层上至少有2I-1个结点（N）

6．完全二叉树中，叶子结点只可能出现在层次最大的最后一层上。

（N）

6．具有n个结点的完全二叉树的深度为[log2n]+1。

（Y）

7．二叉树的线索化的目的是尽可能方便地直接访问结点的前驱和后继。

（Y）

7．任何一棵和树对应的二叉树的右子树不一定为空（N）

8．图的邻接矩阵中，第I列上的数字1的个数表示第I个顶点的出度（N）

8．图的邻接矩阵中，第I行上的数字1的个数表示第I个顶点的入度（N）

9．赫夫曼树又叫最优二叉树（Y）

9．树的双亲表示法中，从任意一结点出发，可方便地找到根结点，但查找孩子结点则要遍历整个树（Y）。

10．堆排序涉及到的两个核心问题，一是如何把一无序序列建立一个堆，二是在输出堆顶后再调整成一个新堆。

（Y）

10．由于排序过程中涉及到的存储器不同，可将排序方法分为内部排序和外部排序两大类（Y）。

四、算法及应用（本大题共3小题，共40分）

求线性表的长度：

请分别编写一个计算单链表的长度的递归和非递归算法

1已知两个有序（非递减）的带头指针的单链表La和Lb,其结点结构相同,数据域为整形data。

请实现把La和Lb合并成Lc。

（本小题共15分）

具体要求：

（1）写出本题所用单链表的存储结构；（3分）

（2）合并过程中，不增加额外的存储空间（提示：

修改La和Lb中结点指针，使其最终成为一个链）；

（3）写出合并的详细算法,Lc中要求无重复值。

（2，3共12分）

（1）TypedefstructLnode{

Intdata;

StructLnode*next;

}Lnode,*LinkList;//3分

（2）voidUniList（LinkList&La,LinkList&Lb,LinkList&Lc）{//UniList结构正确2分

pa=La->next;

pb=Lb->next;

Lc=pc=La;//准备工作2分

While（pa&&pb{

If（pa->datadata）{Pc->next=pa;pc=pa;pa=pa->next;}//2分

Elseif（pa->data=pb->data）{Pc->next=pa;pc=pa;pa=pa->next;pb=pb->next;}//2分

else{Pc->next=pb;pc=pb;pb=pb->next;}//2分

}

pc->next=pa?

Pa:

pb;//2分

free（Lb）}

1求无头结点单链表的长度。

具体要求：

（本小题共15分）

（1）写出本题所用单链表的存储结构；（3分）

（2）写出计算单链表的长度的递归算法（6分）

（3）写出计算单链表的长度的非递归算法（6分）

（1）TypedefstructLnode{

ElemTypedata;

StructLnode*next;

}Lnode,*LinkList;//3分

（2）递归算法（//6分）

staticListlen1（p）

{if（p=NULL）len=0;//1分

else

len=1+Listlen1（p->next）;//3分

retrun（len）;}//整体结构正确2分

（3）非递归算法（//6分）

staticListlen1（p）

{intlen=0;//1分

while（p!

=NULL）

{len++;p=p->next;}//3分

retrun（len）;}//2分

2请写出先序遍历二叉树的非递归算法（提示：

利用栈）。

（本小题共15分）

voidPreBT（BiTreeT）

{InitStack（S）;//2分

p=T;

WHILE（p!

=NULL||!

stackEmpty（s））//循环结构3分

{if（p!

=NULL）

{visit（p->data）;//2分

push（s,p）;p=p->lchild;}//4分

else

{pop（s,p）;//出栈//2分

p=p->rchild;}//2分

}}

2请写出按层次顺序遍历二叉树的算法（提示：

利用队列）。

（本小题共15分）

voidlayorder（treeT）

{initqueue（q）//2分

if（T!

=NULL）

{enqueue（q,T）;//2分

while（notemptyqueue（q））//循环整体结构5分

{outqueue（q,p）;

visit（p->data）;//出队及访问2分

if（p->lchild!

=NULL）

enqueue（q,p->lchild）;//2分

if（p->rchild!

=NULL）

enqueue（q,p->rchild）;//2分

}}}

3排序应用。

（本小题共10分）

已知一待排序的记录序列为：

45525479108

要求：

（1）根据您掌握的排序方法写出2种详细的排序算法

（2）分别描述出排序的动态过程。

（3）分析2种算法各自己的时间复杂度。

3查询应用。

（本小题共10分）

已知一有序序列（非递减）记录序列为：

58121520232838

要求：

（1）根据您掌握的查询方法写出2种详细的查询算法，

（2）分别描述出查询的过程。

（3）分析2种算法各自己的时间复杂度。

1、二叉排序树及二叉排序树的遍历：

设数据集合d={1，12，5，8，3，10，7，13，9}，完成一次从完成依次从d中取数，构造一棵二叉排序树。

（10分）

2、写出利用头插法建立一个含有头结点的非循环单链表的算法。

（15分）

3、写出下图的邻接矩阵。

（10分）

0

1

3

2

4

5

6

5

1

3

6

6

4

2

5

5

图1

 4、二叉树的先序遍历序列为ABCDEFGHI，中序遍历序列为BCAEDGHFI，画出这棵二叉树。

（10分）

5、如图1是无向连通完全图，请完成下列2题。

（1）画出对图1，用普里姆算法构造一棵MST树（5分）

（2）完成图1，从顶点点0开始的递归深度优先遍历算法，并写出遍历所得的一种结果。

（10分）

提示：

遍历算法定义为：

voidDFS（GraphG,intv）;其中Graph表示图的定义。

可以直接使用函数有：

FirstAdjVex（G,V）;NextAdjVex（G,V,W）;VisitFunc（V）.

第7页共7页