必看！！！！！数据结构期末复习题及部分答案解析

号为i (i>1)的结点的父结点编号为( i/2向下取整 )；所有编号（ i>n/2）的结点为叶子结点。 12 n个顶点的连通图至少有 条边，至多有 n*(n-1)/2条边，此时即是完全图 条边。

13 对于图的存储结构有（ 数组表示法 ）、（ 邻接表法 ）( 十字链表法 ) ( 邻接多重表法 )等方法。 14 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____m/2________条。 15 若有序表中关键字序列为：12，22，33，44，55，66，77，88，99对其进行折半查找， 则在等概率情况下，查找成功时的平均查找长度是（ ）。查找99时需进行（ ）次比 较。

16 在哈希表中，处理冲突的方法有开放定址法， 再哈希表法 ， 链地址法 等。

17 在二叉树的第i层上至少有_____个结点, 至多有_____个结点 ,深度为k的二叉树至多有 个结点.

18 对于一棵高度为K的二叉排序树，结点数最少可有 个，最多可有 个。 19 用 中序遍历 遍历对二叉排序树进行访问可得到有序序列。

20 已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14，用二次探测再散列 处理冲突，关键字（23，34，56，24，75，12，49, 52，36，92） 的分布如图，则平均成功的查找长度为（ ）、平均失败的查找长度为（ ）。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 52 36 92 56 34 23 24 75 12 49 21 一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点， 除根之外的所有非终端结点至少有（ ）棵子树， 树中每个结点至多有（ ）棵子树。

22 在哈希表中，处理冲突的方法有开放定址法， ， , 。

23 哈希表的查找效率取决于（ ① 哈希函数是否均匀； ② 处理冲突的方法；

③ 哈希表的装填因子 ）。

24高度为4 (包含不带关键字的叶子结点层)的7?阶?B?树最少有 个关键字，最多 有_________个关键字；如果其中的某结点正好有2个儿子，那么，该结点必定是 结点。

25 对n个元素的序列进行内部排序，若用起泡排序法，最少的比较次数是 n-1 ，最多的比较次数是 n(n-1)/2 。

25 (算法填空)

Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)) { //先序非递归遍历二叉树。 Initstack ( S ); Push ( S,T ); While ( !stackempty( S ) )

{ While ( gettop( S, p )&& ________p_________ )

{ if (!Visit (p->data ) ) return ERROR;

___________push(s,p->lchild)__________ ; }

Pop ( S , p );

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

return ok; }

26 (算法填空)

下列算法试图完成在数组A中搜索有无关键字key，若有，返回数组下标,若无，返回-1。在“ ”处填上合适的内容,完成该算法。

int BinarySearch (keytype A [], int low,int high, keytype key ) {

while ( low <= high) middle = (low+high) /2;

if ( A[middle] == key ) return middle; if (key < A[middle]) high = middle -1 ; else

low = middle + 1 ; }

return -1;

} //end of BinarySearch

27 (算法填空)

下列函数为堆排序中的堆调整过程（调整H.r[s]的关键字，使H.r[s..m]成为一小顶堆）。请在“ ”处填上合适的内容,完成该算法。 Void heapadjust( heaptype @ H , int s , int m ) { rc=H.r[s];

for (j=2*s;j<=m;j*=2) {

if (jr[j] ) ++j; if ( rc > H.r[j] ) break; H.r[s]=H.r[j]; s=j; }

H.R[s] = rc ; }//heapadjust

图示结构题

1 已知在电文中只出现频率为 ( 5,26,7,23,20,19 )的６个字符， 画出你建的哈夫曼树，并给出其哈夫曼编码。

2.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG

请画出该二叉树，并为之建立先序线索没有左子树，则建立该节点的前驱，若没有右子树，这指向该节点的后继。

3 已知某二叉树的先序遍历次序为：a,b,c,d,e,f,g.中序遍历次序为：b,a,d,f,e,g,c 画出该二叉树，并在该二叉树上建立中序线索。

4 某二叉树的中序遍历次序为BEGFDAC， 先序遍历次序为ABDEFGC。 试画出该二叉树，并为之建立中序线索（图示之）。

5 已知某二叉树的后序遍历和中序遍历次序分别为FBEDGCA和FBADECG， 请构造并画出该二叉树。

6 设某一电文只出现a,b,c,d,e,f,g 7个字母；出现频率分别为30%,10%,05%,04%,13%,18% 及20%，请给出各字母的哈夫曼编码。

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

a d h

b c e f i j

g k l m

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

1 5 6

2 3 7 8 9

4

9 某二叉树的结点数据采用顺序存储表示如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

A B C D E F G H I （1）试画出此二叉树的图形表示。

（2）将此二叉树看作森林的二叉树表示，试将它还原为森林。

10 已知某有向图如图所示：

1）给出其十字链表存储结构 a 2）给出其深度优先遍历次序。 3）给出其广度优先遍历次序。

b 4）给出各强连通分量。

d e c

11 设输入序列为20,45,30,89,70,38,62,19，依次插入到一棵2-3树中(初始状态为空)，请画出该B-树。

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

1)画出在该树上插入元素15 ／ │ ＼ 后的B－树。 (10，14)（21）（35） 2)接着，再删除元素35，画出删除后的B－树。

13 已知Hash函数为 H（K）=K mod 13 ，散列地址为0 --14，用线性探测再散列处理 冲突，给出关键字（56，34，68，23，16，70，48，35，83，12，14，57） 在散列地址的分布。并指出平均成功的查找长度是多少?

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

14 根据插入次序（20，30，70，60，10，100，110，90，80。）建立平衡的二叉排序树。 15 设哈希表长为16，哈希函数为H(key)=key mod 13，用开放定址法的二次探测再散列 处理冲突（di=12，-12，22，-22，32，-32……）。依次存入12个元素：56，82，17,24, 36,21,83,96,13,34,57,50。请画出它们在表中的分布情形。

16 已知待排序序列为：25,12,9,20,7,31,24,35,17,10，试写出： (1). 堆排序初始建堆(大顶堆)的结果；

(2). 以第一个元素为枢轴的快速排序一趟扫描的结果； (3). 希尔排序第一趟(增量为5)的结果。

算法设计题

1 设有一个带头结点、元素按值递增有序的单链表，结点的类型定义如下： typedef struct LNode { int data;

struct LNode *next; } LNode, *LinkList;

编写算法，删除其中所有值相同的多余元素结点

2 某线性表中元素以降序排列，现要插入一个元素X，插入后该线性元素仍保持降序。线性表采用带头结点单链表方式存贮。?请编写该插入算法。

3 编写在一有序顺序表中插入数据元素X的算法 INSERT（Ｌ，Ｘ）。 4 写一算法，Delete(linklist &L，X) ,删除单链表中所有值为X的结点。 单链表结点的类型定义如下： typedef struct LNode { int data;

struct LNode *next;