数据结构复习题目.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(“%dn”,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) | xdata)s-next=head;head =s;elseq =head;p= (C) ;while(p!=NULL & x pdata) (D) ;p=p-next;snext=P;qnext= (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(%cn,x);运行结果是 stack 。 数组：1、 设二维数组a0m-10n-1按行优先顺序存储在首地址为loc(a00)的存储区域中，每个元素占d个单元，则aij的地址为_LOC(A00)+D*(n*i+j)_。二维数组Am*n的含义是：该数组有m行（0m-1第一维），有n列（0n-1，第二维），占用m*n个存储空间。假设每个数据元素占用L个存储单元（可理解为字节），则二维数组A中任意一个元素aij的存储位置为： 行优先： LOC(i，j) LOC(0,0) （nij）L 列优先： LOC(i，j) LOC(0,0) （mji）L二叉树1画出下列树对应的二叉树。树转二叉树：加线：将各个兄弟结点之间用虚线链接抹线：仅保留每个结点处与最左第一个孩子的连线旋转，将剩余水平线右转45度二叉树转树（必须为没有右子树的二叉树）：有右线的变水平，此时水平右线连接的皆为兄弟结点图：1、试画出下列图的邻接表。 图.2、 给定无向图G=,其中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-v3v4图的最小生成树：在遍历过程中把任意两点第一次经过的边连出来，多次经过的边不连，就形成一个类似树的结构。注意两种遍历所得生成树不同。排序：直接插入排序：一个数依次与其他数比较，大了跳过，小了放到自己前面=折半插入排序：在将一个新元素插入已排好序的数组的过程中，寻找插入点时，将待插入区域的首元素设置为alow，末元素设置为ahigh，则轮比较时将待插入元素与am，其中m=(low+high)/2相比较,如果比参考元素小，则选择alow到am-1为新的插入区域(即high=m-1)，否则选择am+1到ahigh为新的插入区域（即low=m+1），如此直至low=high不成立，即将此位置之后所有元素后移一位，并将新元素插入ahigh+1。1 希尔排序：已知一组无序数据a1、a2、an，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(dn)，将a1、a1+d、a1+2d列为第一组，a2、a2+d、a2+2d列为第二组，ad、a2d、a3d列为最后一组以次类推，在各组内用插入排序，然后取dd，重复上述操作，直到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。画出该二叉排序树。