发布时间 : 星期日 文章数据结构复习题与答案更新完毕开始阅读7a1359e459fafab069dc5022aaea998fcc2240c9
.
}
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 (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
c e 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，用开放定址法的二次探测再散列
222222
处理冲突(di=1，-1，2，-2，3，-3……)。依次存入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; } LNode, *Linklist;
5 写一算法，Contrary(linklist &L) ,对一带头结点且仅设尾指针L的循环单链表就地逆置。(即表头变表尾，表尾变表头。) 6 已知线性表中的元素以值递增有序排列，并以带头结点的单链表作存储结构。试写一高效 的算法，删除表中所有值大于mink且小于maxk的元素(若表中存在这样的元素)同时释 放被删结点空间，并分析你的算法的时间复杂度。 单链表结点的类型定义如下： typedef struct LNode { int data;
struct LNode *next; } LNode, *Linklist;
7 写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注:不破坏A和B 的原有结构.)Merge(Linklist A, Linklist B, Linklist &C ) 8 写一算法Oplinklist(linklist L,int i;int j )
删除单链表中第i个元素,并将之插入至原表中的第j个元素之前. 9 写出求单链表长度算法 int length(linklist L) 10 若将循环队列Q的结构定义为： #define m 100 //最大队列长度 typedef struct
{ QElemType *base; //存储空间基址
int rear; //尾指针，若队列不空，指向队尾元素 int length; //当前队列的长度，即元素个数 } SqQueue;
试写出相应初始化、入队列和出队列的三个函数。
.
.
11二叉树用二叉链表存储表示。 typedef struct BiTNode { TelemType data;
Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;
试编写销毁二叉树T的算法DestroyBiTree ( BiTree &T)。
12二叉树用二叉链表存储表示。 typedef struct BiTNode { TelemType data;
Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree;
试编写算法，求元素值为x的结点的左孩子(返回x的左孩子的指针)。 13 设计一算法，计算给定二叉树T中度为2的结点个数。 14编一算法：按层序遍历二叉树T。
15试编写先序遍历二叉树T的递归算法PreorderBiTree ( BiTree &T)。 16 写出一个将树中每个结点的左右孩子对换的算法 SWAPTREE(T) 即如:
原二叉树 转换后 T SWAPTREE(T) ↓ ↓
(A) (A)
/ \\ / \\ (B) (C) (C) (B) / \\ / \\ / \\ (D) (E) (F) (F) (E) (D) \\ \\ / /
(G) (H) (H) (G)
17 二叉树用二叉链表存储表示。
试编写后序遍历二叉树T的递归算法PostorderBiTree ( BiTree T)。 18 写一个计算二叉树中叶子结点个数的递归算法。
.