1、章节作业。
第一章概论。
1．设计算法在整型数组a[n]中查找值为k的元素，若找到，则输出其位置i(0≤i≤n-1)，否则输出-1作为标志，并分析算法的时间复杂度。
int search (int a,int n,int k)
int i;
i=0;while (i<=n-1)
if (a[i]!=k) i++;
else break;
if (i<=n-1) return i;
else return -1；
当查找成功时，a[i]与k比较次数≤n；当查找不成功时，a[i]与k比较n次，所以，算法时间复杂度t(n)=o(n)。
2．写出计算方阵a[n][n]与b[n][n]乘积c[n][n]的算法，分析算法的时间复杂度。
void matrixmultiply (int a[n],int b[n],int c[n],int n)
int i,j;
for (i=0;ifor (j=0;j
else else
else {
cq->quelen=cq->quelen-1;
x=cq->data[(cq->rear+m-cq->quelen)% m];
return 1;
取队列首元素：
datatype gethead(cycqueuetp *cq)
datatype x;
x=cq->data[cq->rear=m-cq->quelen]% m];
return x;
第四章树和二叉树。
1．算法设计题。
(1)以二叉链表作存储结构，试编写求二叉树叶子结点个数的算法。
typedef struct btnode
datatype data;
struct btnode *lchild,*rchild;
*bintree;
int leafnode_num(bintree bt )
if (bt==null) return 0 ;
elseif (bt->lchild==null) &bt->rchild==null）
return 1;
elsereturn leafnode_num (bt->lchild)+leafnode_num (bt->rchild);
(2)设计算法求二叉树的结点的个数。
typedef struct btnode
datatype data;
struct btnode *lchild,*rchild;
*bintree;
int node_num (bintree bt)
if (bt==null) return 0;
elsereturn node_num(bt->lchild)+node_num(bt->rchild)+1;
(3)设计算法按先序次序打印二叉树t中叶子结点的值。
typedef struct btnode
int data;
struct btnode *lchild,*rchild;
*bintree;
void preorder (bintree bt)
if (bt!=null)
if ((bt->lchild==null) &bt->rchild==null）)
printf(“%d”,bt->dta);
preorder(bt->lchild);
preorder(bt->rchild);
2．树的存储结构采用孩子兄弟链表，试编写树的按层次遍历算法。
typedef struct tnode
int data;
struct tnode *son,*brother;
*tree;
void tree_tr**el (tree root )
initqueue(q);
if (root1=null)
enqueue( q , root );
while (!emptyqueue(q))
p=gethead(q);
outqueue (q);
prinf(“%d” ,p->data);
p=p->son;
while (p!=null)
enqueue (q , p);
数据结构导论
7.不稳定的排序方法是 a.直接插入排序 b.冒泡排序。c.堆排序 d.二路归并排序。8.设散列表表长m 14，散列函数为h k k 11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是 a.3 b.5 c.8 d.9 9.若元素1，2，3依次进栈，则退栈不可能出现的次序...
数据结构导论试题
一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 二00一年下半年全国高等教育自学考试。数据结构导论试卷。一 单项选择题。1.若给定有n个元素的向量，则建立一个有序单向链表的时间复杂性的量级是 2.在一个具有n个结点的单链表达中查找值为m的某结点，若查找成功，则...
全国数据结构导论试题
全国2011年10月数据结构导论试题课程 02142 一 单项选择题 本大题共15小题，每小题2分，共30分 1.设栈s和队列q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈s，元素退栈后即进入队列q，若6个元素的出队序列是e2，e4，e3，e6，e5，e1，则栈s的容量至少为 a...