数据结构复习题目.doc

线性表：
1、在一个单链表head中，若要在指针p所指结点后插入一个q指针所指结点，则执行___d__。
A. p->next=q->next; q->next=p;
B. q->next=p->next; p=q;
C. p->next=q->next; p->next=q;
D. q->next=p->next; p->next=q;

2、完成下列打印带头单链表的各元素的算法.
typedef struct List
{ int data;
struct List *next;
} Node，*Link;
void printlk(Link head)
{Link p=head->next;
while( （1） p->next )
{ printf(“%d\n”,p->data);
（2） p=p->next ;
}

3、有一个有序单链表(从小到大排列), 表头指针为head, 请完成向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序的程序。
typedef struct node{
Elemtyoe data;
struct node *next;}node;
node *insertorder(head,x)
node *head;
int x;
{
node *s, *p, *q;
s = (node* )mallloc(sizeof(node));
s->data= (A)x ;
s->next=NULL;
if (head== (B) || x<head->data)
{
s->next=head;
head =s;
}
else
{
q =head;
p= (C) ;
while(p!=NULL && x > pàdata)
{
(D) ;
p=p->next;
}
sànext=P;
qànext= (E) ;
}
return(head);
}

栈：
1.___a_又称为FIFO表。
A.队列 B.散列表 C.栈 D.哈希表
2．栈是一种 b 的线性表。
A. 只允许在一端进行插入和在另一端进行删除
B. 只允许在一端进行插入和删除
C. 只允许在两端进行插入和删除
D. 允许在中间部位进行插入和删除
3．写出下列程序段的运行结果（栈中的元素类型是char）：
main(　)
{ SEQSTACK s,*p;
char x, y;
p = &s;
initstack(p);
x = ‘c’; y = ‘k’;
push(p,x); push(p,’a′); push(p,y);
x = pop(p);
push(p,’t′);
push(p,’s′);
while(!empty(p))
{ y = pop(p);
printf(″%c″,y);}
printf(″%c＼n″,x);
}
运行结果是 stack 。

数组：

1、 设二维数组a[0…m-1][0…n-1]按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，则aij的地址为____LOC(A00)+D*(n*i+j)____。
二维数组Am*n的含义是：该数组有m行（0~m-1第一维），有n列（0~n-1，第二维），占用m*n个存储空间。假设每个数据元素占用L个存储单元（可理解为字节），则二维数组A中任意一个元素aij的存储位置为：

行优先： LOC(i，j) ＝ LOC(0,0) ＋ （n×i＋j）×L

列优先： LOC(i，j) ＝ LOC(0,0) ＋ （m×j＋i）×L

二叉树

1．画出下列树对应的二叉树。

树转二叉树：
加线：将各个兄弟结点之间用虚线链接
抹线：仅保留每个结点处与最左第一个孩子的连线
旋转，将剩余水平线右转45度
二叉树转树（必须为没有右子树的二叉树）：
有右线的变水平，此时水平右线连接的皆为兄弟结点

图：

1、试画出下列图的邻接表。

图

.2、 给定无向图G=<V,E>,其中V={a,b,c,d,e},E={(a,b),(a,e),(b,e),(b,c),(c,e),(e,d)}.请画出图G的邻接矩阵,邻接表。从结点a出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

邻接矩阵：图中有边或者弧用1，无就用0；而网中则顶点间有边/弧用权值，无用无限号00。

邻接表：从一个顶点，向其他所有顶点发出箭头，有边或者弧则连箭头，否则在当前顶点的链域中放 倒V符号。

图的深度优先遍历：类似于树的先根遍历，不断访问违背访问的邻接点

图的广度优先遍历：类似树的层次遍历，先从v0出发，访问相连的v1v2,然后一次访问v1的邻接点v3v4v5，和v2的邻接点v6v7，然后访问v3的邻接点v8v9，其余点类似。
V1->v2->v3>v4》》》》》》

图的最小生成树：在遍历过程中把任意两点第一次经过的边连出来，多次经过的边不连，就形成一个类似树的结构。注意两种遍历所得生成树不同。

排序：
直接插入排序：一个数依次与其他数比较，大了跳过，小了放到自己前面==
折半插入排序：
在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为a[low]，末元素设置为a[high]，则轮比较时将待插入元素与a[m]，其中m=(low+high)/2相比较,如果比参考元素小，则选择a[low]到a[m-1]为新的插入区域(即high=m-1)，否则选择a[m+1]到a[high]为新的插入区域（即low=m+1），如此直至low<=high不成立，即将此位置之后所有元素后移一位，并将新元素插入a[high+1]。[1]
希尔排序：
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。
冒泡排序：每两个对比一次，经历多次
选择排序：N个数字，先找到最小的放最前，然后次小的，依次
堆排序：
归并排序：先将所有元素两两分组，然后组内排序，然后合并相邻组再排序，类推之。

基数排序：按数字位数排序，相同位数再排序

查询
1、 哈希表长m=11，哈希函数H（key）=key%11。表中已有4个结点：addr（15）=4， addr（38）=5，addr（61）=6，addr（84）=7，其余地址为空，如果线性探测再散列处理冲突，关键字为49的结点地址是 。
2、 从空的二叉排序树开始依次插入30，18,11,17,7,5,13,41,29,37,23,19。画出该二叉排序树。