大学数据结构复习题

数据结构复习题

1、数据结构1-1,须知E数值计算州翡设计I'碉中计算机的a以及他们之间的包和运算的

刮

a操作对象；b.计算方法；c逻辑存储；d.数据映像

a结构；b.关系；c.运算；d算法

2、数据结构被形式化地定义为(DR〉，其中D是_b的有限集合，R是D上包的有限集

4口。

a.算法；b.数据元素：c.数据操作；d.逻辑结构

a.操作：b.映像；c.存储；d关系

3、线性表的顺序存储结构是一种_3_的存储结构，线性表的链式存储结构是一种」_的存

储结构。

a.随机存储；b顺序存储；c.索引存取；d.HASH存取

4、一个栈的入栈序列是4b,cde,则栈的不可能的输出序列是J。

a.edcba:b.decba;c.dceab:d.abcde

5、一个队列的入队序列是1,2,3,4,则队列的愉出序列是b。

a.4,32/；b.1,23,4;c.1,43,2；d.32,4,1

6、广义表((a),((b),c),<«d))))的长度是3,深度是」________。

7、深度为k的完全二叉树至少有_2、_个结点，至多有_2<1____个结点，若按自上而下,

从左到右的次序给结点编号(从1开始)，则编号最小的叶子结点的编号是_2卜」1_。

8、现有中序遍历二叉树的结果为羯则有种不同形态的二叉树可以得到这一遍历

结果。

9、有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100),当二分查找

值为82的元素时，需要经过工次比较就找到。

10、在线索二叉树中，结点P没有左子树的充要条件是-->蛔=1_。

11s数据集｛4,5,6,730,1238｝为结点权值构造Hufftnan树，请给出构造所得的Huffman

树，并求其带权路径长度。

解答：

WPL=4*4+5*4Y*3+7*3+10*3+12*2+18*2

=9*4+23*3+30*2

=3169+60

=165

12、已知一棵度为k的树中有m个度为1的结点，m个度为2的结点，…，眩个度为k的

结点，问该树中有多少个叶子结点？

解答：设该树的总结点数是：〃；分支数目是：3。则有：

〃=%+"1+“2"!-----F+3

另外，每个非叶子结点都产生分支，度为1的每个结点产生一个分支，度为2的每个结点产

生2个分支，…，度为左的每个结点产生上个分支；每个分支都进入某一结点，在〃个

结点中，除根外，每个结点都有一个分支进入。因此，有：

5=%+2n2+3n3+（左一l）9_i+knk

〃=3+1③

k

由①、②和③得到：勿0=%+2内+34+…（左一1）%+1=N（j-l）%+1

13、假设一棵二叉树的先序序列是EBADCFHGIKJ,中序序列是ABCDEFGHIJK。请画出

该二叉树。

和已知序列对应的二叉树是:

14、设线性表，试写一按下列规则和并为线性表的算法，即

使得

当时;

或者当时。

线性表和均以单链表作存储结构，且表利用表和表中的结

点空间构成。

注意：单链表的长度值和均未显示存储。

本题涉及的存储结构描述如下：

单链表存储结构:

typedefstructLnode*LinkList;

typedefstructLnode

(

DataTypedata;

LinkListnext;

}Lnode,*LinkList;

voidmergelinklist(LinkList&lc,LinkListla,LinkListlb)

(

lc=la;

pa=la->next;pb=lb->next;pc=lc;

lc->next=NULL;

while(pa&&pb)

(

pc->next=pa;

pc=pa;

pa=pa->next;

pc->next=pb;

pc=pb;

pb=pb->next;

)

if(pa)pc->next=pa;

delete(lb);

)

15、试完成二叉树按层次(同一层自左至右)遍历的算法。

解答：本题涉及的存储结构描述如下：

树的二叉链表存储结构：

typedefstrcutbitreenode*bitree;

typedefstructbitreenode{

datatypedata;

bitreeIch,rch;

}bitreenode,*bitree;

队列的链式存储结构：

typedefstructlinkquenode*linkqueptr;

typedefstructlinkquenode{

bitreequelem;

linkqueptrnext;

}linkquenode,*linkqueptr;

typedefstructlinkque{

linkqueptrfront,rear;

}linkque;

voidlayertraverse(bitreebt)

(

cout<<endl〈v”按层次遍历的结果如下：”《endl;

initqueue(Q);

if(bt)

(

enterqueueu(Q,bt);

while(!