数据结构期末考试试题及答案-向日葵屋

2009-01-04 11:22

期末样卷参考答案

一．是非题（每题1分共10分）

1. 线性表的链式存储结构优于顺序存储结构。 F

2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。F

3．字符串是数据对象特定的线性表。T

4．在单链表P指针所指结点之后插入S结点的操作是：P->next= S ; S-> next = P->next; F

5．一个无向图的连通分量是其极大的连通子图。T

6．邻接表可以表示有向图，也可以表示无向图。T

7．假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。 T

8．通常，二叉树的第i层上有2i-1个结点。F

9．对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有ém/2ù个关键字。F

10．对于任何待排序序列来说，快速排序均快于起泡排序。F

二．选择题（每题2分共28分）

1．在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。

a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序

2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。

a.不定 b.n+1 c.n d.n-1

3. 下列二叉树中，（ a ）可用于实现符号不等长高效编码。

a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树

4. 下列查找方法中，（ a ）适用于查找有序单链表。

a.顺序查找 b.二分查找 c.分块查找 d.哈希查找

5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（ a ）方法。

a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找

6. 在下列数据结构中，（ c ）具有先进先出特性，（ b ）具有先进后出特性。

a．线性表 b．栈 c．队列 d．广义表

7．具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。

a. log 2 m b. └ log2 m ┘ +1 c. m/2

d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m

8．已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。

下列选择中（ c ）是快速排序一趟排序的结果。

（ b ）是希尔排序（初始步长为4）一趟排序的结果。

（ d ）是基数排序一趟排序的结果。

（ a ）是初始堆（大堆顶）。

a. 84，79，64，37，57，52，58，26，28，34，56。

b. 28，34，57，26，56，52，58，37，79，84，64。

c. 28，34，37，26，52，56，64，79，58，84，57。

d. 52，34，64，84，56，26，37，57，58，28，79。

e. 34，56，26，58，52，64，37，28，79，57，84。

f. 34，56，26，58，52，79，37，64，28，84，57。

三．填空题（每题2分共20分）

1．有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。

2．已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。

其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。

3．设有二维数组A 5 x 7 ,每一元素用相邻的4个字节存储，存储器按字节编址。已知A00的存储地址为100。则按行存储时，元素A14的第一个字节的地址是（144）；按列存储时，元素A14的第一个字节的地址是（184）。

4．请在下划线上填入适当的语句，完成以下法算。

Status Preordertraverse(Bitree T,Status(Visit)(Telemtype e)){

//先序非递归遍历二叉树。

Initstack ( S );   Push ( S,T );

While ( !stackempty( S ) )

{ While ( gettop( S, p )&& p ) { visit (p->data ) ; push(S, p->lchild ;}

     Pop ( S , p );

     If ( !stackempty(s) ) { pop(S, p) ;   push( S, p->rchild ); }

}

return ok;

四．简答题（每题5分共25分）

1．将图示森林转换为二叉树，并对该二叉树中序全序线索化。



h

d

a







j

i

b

f

e

c





m

l

k

g

2．已知Hash函数为 H（K）=K mod 13 ，散列地址为0 —14，

用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49, 52，36，92，06，55）在散列

地址的分布。

0   1   2    3   4   5   6   7   8   9   10 11 12 13 14





      3. 右图为一棵3阶B 树。                            （20，25）

a. 画出在该树上插入元素15后的B 树。             ／ │ ＼

b. 接着，再删除元素35，画出删除后的B 树。    (10,14)（21）（35）

   4.已知某无向图的邻接表存储结构如图所示。

       a.请画出该图。

b.根据存储结构给出其深度优先遍历序列及广度优先遍历序列。

c.画出其深度优先生成树及广度优先生成树。

0 a            2            4    //

1 b            2            3             4   //

2 c              0            1             4   //

3 d            1   //

4 e            0               1               2    //

5. 设在某通信系统中使用了八个字符，它们出现的频率分别为0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07，试构造一棵赫夫曼树，并给出赫夫曼编码。

五．算法设计题（共17分）

1. 单链表结点的类型定义如下：

typedef struct LNode {

        int data;

struct LNode next;

} LNode, Linklist;

写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。

(注:不破坏A和B的原有结构.)

Merge(Linklist A, Linklist B, Linklist &C )

void Merge(Linklist A, Linklist B, Linklist &C)

{ C=(Linklist)malloc(sizeof(LNode));

pa=A->next; pb=B->next; pc=C;

while(pa&&pb)

{ pc->next=(Linklist)malloc(sizeof(LNode));

pc=pc->next;

if(pa->data<=pb->data)

{ pc->data=pa->data; pa=pa->next;}

else

{ pc->data=pb->data; pb=pb->next;}

}

if(!pa) pa=pb;

while(pa)

{ pc->next=(Linklist)malloc(sizeof(LNode));

pc=pc->next;

pc->data=pa->data; pa=pa->next;

}

pc->next=NULL;

}

2. 二叉树用二叉链表存储表示。

typedef struct BiTNode {

TelemType data;

Struct BiTNode lchild, rchild;

} BiTNode, BiTree;

编写一个复制一棵二叉树的递归算法。

BiTree CopyTree(BiTree T) {

if (!T ) return NULL;

if (!(newT = (BiTNode*)malloc(sizeof(BiTNode))))

exit(Overflow);

newT-> data = T-> data;

newT-> lchild = CopyTree(T-> lchild);

newT-> rchild = CopyTree(T-> rchild);

return newT;

再分享一下我老师大神的人工智能教程吧。零基础！通俗易懂！风趣幽默！还带黄段子！希望你也加入到我们人工智能的队伍中来！https://blog.csdn.net/jiangjunshow