数据结构程序设计题答案

void insert(sqlist l,datatype x) { }

2． 线性表以顺序结构存储，写一算法将两个有序表归并为一个新的有序表。

void merge(sqlist l1,sqlist l2,sqlist l3) {

int i=1,j=1,k=1;

while((i<=l1.len)&&(j<=l2.len)) i=1,j;

while ((x>l.v[i])&& (i<=l.len))i++; for (j=l.len;j>=i;j--)

l.v[j+1]=l.v[j];

l.v[i]=x l.len++;

{ if(l1.v[i]<=l2.v[j]) l3.v[k]=l1.v[i++]；

else

l3.v[k]=l2.v[j++]； k++； } while(i<=l1.len)

l3.v[k++]=l1.v[i++]； while(j<=l2.len) l3.v[k++]=l2.v[j++]; }

3． 在顺序表中删除所有值为X的元素。

void delete(sqlist l, datatype x) {

i=1,j;

while (i<=l.len)

if(l.v[i]==x)

{ for(j=i;j}

l.len--;

l3.len=l1.len+l2.len;

4．设计算法求二叉树的叶子结点的数目

int i=0;

void postorder (struct node *p) { if (p!=NULL)

{ postorder(p->llink); postorder(p->rlink);

if((p->llink==NULL)&&(p->rlink==NULL)) {printf(\"%c\ i++;} } }

5．设计算法求二叉树的深度。 int depth(struct node *p) {int l,r; if (p==NULL) return 0; else {

l= depth(p->llink); r=depth(p->rlink)； return (l>r)?(l+1):(r+1) }

}

6．以二叉链为存储结构，设计算法按后序次序打印二叉树T中所有叶子结点的值，并返回其结点数。

int i=0;

void postorder (struct node *p) { if (p!=NULL)

{ postorder(p->llink); postorder(p->rlink);

if((p->llink==NULL)&&(p->rlink==NULL)) printf(\"%c\ i++; } }

查找与排序

1．下列排序方法中，______是稳定的。

A． 希尔排序

C．堆排序

B． 快速排序 D．直接插入排序 答案：D

2．折半查找有序表（16，20，30，35，40，46，60，80），若查找元素80，需依次与表中元素______进行比较。

C． 5，46，80 C．40，60，80 D． 0，60 D．35，46，60，80 答案：D 3．下列排序算法中，稳定的排序算法是______________。

（选择排序，堆排序，快速排序，直接插入排序）。

4．二分查找法要求查找表中各元素的键值必须是（ ）排列。

A．递增或递减 C．递减 B．递增 D．无序 答案：A

5．在有序表A[1，20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为（ ）。 答案：10，15，12

6．设数组R的初始状态为

1 2 3 4 5 6 7 R 40 10 60 20 25 45 15 对R进行“从小到大”的排序，采用2路归并排序法，请画出经过一趟归并后，数组R的状态。

1 2 3 4 5 6 7 R 答案：

10 40 20 60 25 45 15

7．设散函数为H（K）=K mod 7，开始时散列表为空，用线性探测法解决冲突，请画出依次插入键值23，14，9，6，30，12，18后的散列表。 答案： 0 1 2 3 4 5 6 14 18 23 9 30 12 6 1 5 1 2 3 1 1 8．已知哈希表地址空间为0．．8，哈希函数为H(k)=k % 7，采用线性探查法处理冲突。将下面数据序列依次存入该散列表中，并求出在等概率下的平均查找长度。(6分) 100，20，21，35，3，78，99，45

0 1 2 3 4 5 6 7 8 答案： 散列表如下：

0 1 2 3 4 5 6 7 8 21 35 100 3 78 99 20 45 1 2 1 1 4 5 1 5 平均查找长度ASL：(4*1+1*2+1*4+2*5)／8=2.5

9．对下列数据表，写出采用快速排序算法排序的每一趟的结果。 (60，20，31，1，5，44，55，61，200，30，80，150，4，29)

答案：

快速排序各趋结果如下，其中括号中为待排序列，括号外为最终结果。 (60 20 31 1 5 44 55 61 200 30 80 150 4 29) (29 20 31 1 5 44 55 4 30) 60 (80 150 200 61) (4 20 5 1) 29(44 55 31 30) 60 (61)80 (200 150) (1)4 (5 20)29(30 31) 44 (55)60 61 80 150 (200) l 4 5 (20)29 30 (31) 44 55 60 61 80 150 200 1 4 5 20 29 30 31 44 55 60 61 80 150 200 10．基数排序的基本思想是什么？该排序的时间复杂度是多少？对下列数据表，写出采用基数排序算法排序的每一趟的结果。

(60，20，31，1，5，44，55，61，200，30，80，150，4，29)