16．下列程序段的时间复杂度为_O(n^2)_ product = 1;
for (i = n;i>0; i--) for (j = i+1; j 17．已知指针p指向单链表中某个结点，则语句p -> next =p -> next -> next的作用是________________。 删除*P的直接后继结点 18．假设元素只能按a,b,c,d的顺序依次进栈，且得到的出栈序列中的第一个元素为c，则可能得到的出栈序列为________________，不可能得到的出栈序列为________________ 1)cbad, cbda, cdba 2)cabd, cadb, cdab 19．若链串结点中的指针占4个字节，每个字符占1个字节，则结点大小为2的链串的存储密度为________________。 2 / ( 4 + 2 ) = 1/3 20．右图表示的广义表为________________。[img]/0046615335847449.jpg[img] 21．若一棵满三叉树中含有121个结点，则该 树的深度为________________。 5 // ( 3^5 - 1 ) / ( 3 - 1 ) = 121 22．若以邻接矩阵表示有向图，则邻接矩阵上 第i行中非零元素的个数即为顶点vi的________________。 出度 23．若希望只进行8趟排序便能在4800个元素中找出其中值最小的8个元素，并且要求排序过程中所进行的关键字比较次数尽可能少，则应该选用________________排序方法。 24．在含20个关键字的3阶B树（2－3树）上查找一个关键字，至多需要访问___________次外存。 25．文件上的两类主要操作为________________和________________。 检索 和 维护 三、解答题（本大题共4小题，每小题5分，共20分） 26．设栈S1的入栈序列为1 2 3 4（每个数字为13个元素），则不可能得到出栈序列3142。但可通过增设栈S2来实现。例如，按下图中的箭头指示，依次经过栈S1和S2，便可得到序列3 1 4 2。 http://www.ezikao.com.cn/uploadimages/2 ( ( e ), ( ( e ), ( b, c ) ), ( L ) ) 如果用H1和H2分别表示栈S1和S2的进栈操作，用P1和P2分别表示两个栈的出栈操作，则得到3 1 4 2的一个操作步骤为 H1，H1，H1，P1，H2，P2，P1，H2，P1，H2，P2，H1，P1，H2，P2，P2 请仿照上例写出利用两个栈从1 2 3 4得到4 1 3 2的操作步骤。 H1,P1,H2,H1,H1,H1,P1,H2,P2,P2,P1,H2,P2,P1,H2,P2 27．已知树如右图所示，（1）写出该树的后序序列； （2）画出由该树转换得到的二叉树。 1) EBJKFGHICDA 2) 树变二叉树:兄弟相连,保留长子的连线 . A . / . B . / \\\\ . E C . / \\\\ . F D . / \\\\ . J G . \\\\ \\\\ . K H . \\\\ . I 28．为关键字（17，33，31，40，48）构造一个长度为7的散列表，设散列函数为h(key)=key%7,用开放定址法解决冲突的探查序列是 hi = (h(key) + i(key%5+1))%7 0≤i≤6 （1）画出构造所得的散列表； （2）求出在等概率情况下查找成功时的平均查找长度。 1) . 0 1 2 3 4 5 6 . 31 17 48 33 40 2) ( 1 + 1 + 3 + 2 + 4 ) / 5 = 11 / 5 29．已知R［1..8］中的元素依次为（12，5，9，20，6，31，24，27），写出按算法MergeSortDC 对R进行自顶向下的二路归并排序过程中，前5次调用函数Merge(R, low, mid, high)时参数 low, mid 和high的值。 void MergeSortDC (int R[], int low, int high ) { int mid if (low mid = (low +high)/2; MergeSortDC (R, low, mid); MergeSortDC (R, mid+1, high); Merge (R, low, mid, high); } } // MergeSortDC （1）第一次调用时的参数值； （2）第二次调用时的参数值； （3）第三次调用时的参数值； （4）第四次调用时的参数值； （5）第五次调用时的参数值； //此题有一定的难度,涉及到递归调用时,系统堆栈的情况 . low mid high 1) 1 1 2 2) 3 3 4 3) 1 2 4 4) 5 5 6 5) 7 7 8 6) 5 8 6 7) 1 8 4 四、算法阅读题（本大题共4小题，每小题5分，共20分） 30．下列函数的功能是，对以带头结点的单链表作为存储结构的两个递增有序表（表中不存在值相同的数据元素）进行如下操作：将所有在Lb表中存在而La表中不存在的结点插入到La中，其中La和Lb分别为两个链表的头指针。请在空缺处填入合适内容，使其成为一个完整的算法。 void union (LinkList La, LinkList Lb) { //本算法的功能是将所有Lb表中存在而La表中不存在的结点插入到La表中 LinkList pre = La, q; LinkList pa = La -> next; LinkList pb = Lb -> next; free (Lb); while (pa && pd) { if (pa -> data (1) ; pre = pb; pb = pb -> next; (2) ; } else { q = pb; pb = pb -> next; free (q); } } if (pb) (3) ; } (1) pre->next = pb (2) pre->next = pa (3) pre->next = pb 31．已知串的存储结构为动态存储分配的顺序串。阅读下列算法，并回答问题： （1）写出执行函数调用 strc (s, r)的返回结果，其中s=〃aba〃, r=〃abababa〃; （2）简述函数strc的功能。 int strc (HString * sub, HString * str) { int i=0, j, k, count =0; while (i < str -> length – sub -> length +1) { j=i; k=0; while (k length && str -> ch[j] = =sub -> ch[k] ) { j++; k++; } if (k = = sub -> length) {count ++; i=j-sub -> length +1;} else i++; } return count; } (1) 3 (2) 求串str中子串sub的个数 32．下列函数MDFSForest的功能是，对一个采用邻接矩阵作存储结构的图进行深度优先搜索遍历，输出所得深度优先生成森林中各条边。请在空缺处填入合适内容，使其成为一个完整的算法。 #define MaxMun 20 //图的最大顶点数 typedef struct { char vexs [MaxNum]; //字符类型的顶点表 int edges [MaxNum][MaxNum]; //邻接矩阵 int n, e; //图的顶点数和边数 }MGraph; //图的邻接矩阵结构描述 typedef enum {FALSE, TRUE} Boolean; Boolean visited [MaxNum]; void MDFSTree (MGraph *G, int i); void MDFSForest (MGraph *G) { int i, k; for (i=0; i visited [i] = (1) for (k = 0; k void MDFSTree (MGraph *G, int i) { int j; visited [i]=TRUE; for (j=0; j if ( (2) { printf (〃<%c, %c>〃G -> vexs [i], G (3) ; } } ｝ 1) FALSE //初始化,所有结点未访问 2) !visited[ j ] && G->edge[ i ][ j ] == 1 边 3) MDFSTree( G, j ) //从j结点继续,深度优先搜索 ; ) -> vexs [j]); // 结点j未访问且i到j有