数据结构试题及答案Word文件下载.docx

数据结构试题及答案Word文件下载.docx

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

C.任一结点无左孩子D.任一结点无右孩子

5.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（A）个元素。

A.n-iB.n+l-iC.n-1-iD.i

6.判定一个栈ST（最多元素为m0）为空的条件是（B）。

A.ST→TOP!

=0B.ST→TOP==0

C.ST→TOP!

=m0D.ST→TOP==m0

7.非空的循环单链表head的尾结点（由P所指向）满足（C）。

A.p->

next=NULLB.p=NULLC.p->

next=headD.p=head

8.在线性结构中，所有结点都有（B）个直接后继。

A.0B.0或1C.1D.不确定

9.设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作时修改指针的语句是C。

A、sq.front=（sq.front+1）%m

B、sq.front=（sq.front+1）%（m+1）

C、sq.rear=（sq.rear+1）%m

D、sq.rear=（sq.rear+1）%（m+1）

二、填空题

1.已知一棵二叉树的中序序列和后序序列分别为：

DBGEACHF和DGEBHFCA，则该二叉树的前序序列是（ABDEGCFH）。

2.在（循环）链表中，从任何一结点出发都能访问到表中的所有结点。

3.以下函数的时间复杂度为（O（n））。

fact（intn）

{

if（n<

=1）

return1;

else

return（n*fact（n-1））;

}

4.在线索化二叉树中，t所指结点没有左子树的充要条件是t->

Ltag==（1或true）。

5.现有按中序遍历二叉树的结果为abc，问有（5）种不同形态的二叉树可以得到这一遍历结果。

6.如图所示，删除元素b的语句为（q->

next=q->

next->

next）．

三、应用题

1.给出下面森林对应的二叉树及二叉树的后序序列。

2.已知二叉树的先序、中序和后序序列如下:

前序序列：

*BC***G*

中序序列：

CB*EAGH*

后序序列：

*EDB**FA

，其中有一些看不清的字母用*表示。

（1）请先补充*处的字母.

（2）再构造一棵符合条件的二叉树

（3）最后画出带头结点的中序线索链表。

答案：

3.有一个含头结点的单链表，头指针为A,另有一个不含头结点的单链表，头指针为B。

（1）分别写出判断A为空和B为空的条件。

（2）假设S指向一个新结点，分别写出在A的表头插入S，和在B的表头插入S的语句。

4.设A～H8个字符出现的概率为:

W={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25}。

设计最优二进制编码（用0,1编码）

（1）画出最优二叉树

（2）计算平均码长（二叉树的带权路径长度）。

5.线性表有两种存储结构一是顺序表，二是链表。

试问

（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。

在此情况下，应选用哪种存储结构？

为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？

为什么？

答：

（1）选链式存储结构。

它可动态申请内存空间，不受表长度（即表中元素个数）的影响，插入、删除时间复杂度为O

（1）。

（2）选顺序存储结构。

顺序表可以随机存取，时间复杂度为O

（1）。

6.循环队列的优点是什么？

如何判别它的空和满？

优点：

循环队列克服了“假上溢”现象。

　　判别空和满：

设有循环队列sq，以（sq->

rear+1）%MaxSize=＝sq->

front或sq->

count=＝MaxSize来判别队满；

以sq->

rear=＝sq->

front来判别队空

四、编程题

1、已知顺序表结构体定义如下：

#defineMAXLEN100

typedefstruct{

intdata[MAXLEN];

intlast;

}SeqList;

在顺序表L的第i个位置上插入值为x的元素的函数定义如下：

intInsList（SeqList*L,inti,intx）{

……//

（1）函数代码空缺部分

}

要求：

将“

（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中顺序表满，返回-1；

插入位置错误，返回0；

正常完成数据插入返回1。

2、已知链队列元素的结构体定义如下：

typedefstructNode{

intdata;

structNode*next;

}QNode;

链队列头结点定义为：

QNode*front,*rear;

}LQueue;

在队列中，完成入队操作的函数定义如下：

voidIn_LQueue（LQueue*q,intx）{

……//

（2）函数代码空缺部分

依据题目条件，将“

（2）函数代码空缺部分”的内容，在下面空白处填写完整。

3、已知线性单链表结构体定义如下：

}LNode,*LinkList;

在单链表L的第i个位置上插入值为x的元素的函数定义如下：

intInsert_LinkList（LinkListL,inti,intx）{

…………//

（1）函数代码空缺部分

假设LNode*Get_LinkList（LinkListL,inti）函数已经定义完成，该函数的功能为“在单链表L中查找第i个元素结点，找到后返回其指针；

否则返回空指针”。

将“

（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中插入位置错误，返回值为0；

正常完成数据插入返回值为1。

4、已知栈的结构体定义如下：

#defineMAXLEN100

chardata[MAXLEN];

inttop;

}SeqStack;

在栈中，完成“出栈”操作的函数定义如下：

intPop_SeqStack（SeqStack*s,char*x）{

//

（2）函数代码空缺部分

将“

（2）函数代码空缺部分”的内容，在下面填写完整，因空栈导致无法正常出栈，返回值为0；

正常出栈返回值为1。