B．中序线索树中查找*p的中序后继 C．中序线索树中查找*p的中序前继 D．后序线索树中查找*p的后序前继
6．假定有k个关键字互为同义词，若用线性探测法将这k个关键字存入散列表中，至少需要进行( )次探测。
A．k-1 B．k C．k+l D．k(k+1)/2
7．若待排序元素基本有序，则下列排序中平均速度最快的排序是( )；若要求辅助空间为O(1)，则平均速度最快的排序是( )；若要求排序是稳定的，且关键字为实数，则平均速度最快的排序是( )。
A．直接插入排序 B．直接选择排序 C．Shell排序 D．冒泡排序 E．快速排序 F．堆排序 C．归并排序 H．基数排序
8．对于多关键字而言，( )是一种方便而又高效的文件组织文式。 A．顺序文件 B．索引文件 C．散列文件 D．倒排文件 二、问答题(共25分)
1．设A[-2：6；-3：6]是一个用行主序存储的二维数组，已知A[-2，-3]的起始存储位置为loc(-2，-3)=1000，每个数组元素占用4个存储单元，求：(6分) 1)A[4，5]的起始存储位置loc(4，5)； 2)起始存储位置为1184的数组元素的下标。
2．给定二叉树的先序和后序遍历序列，能否重构出该二叉树?若能，试证明之，否则给出反例。(6分)
3．在含有n个关键字的m阶B-树中进行查找，至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?(设两种树中的每个节点均是一个存储块)。(8分)
4．用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。(5分) 三、阅读程序题(共10分)
1．设G是一个有向无环图，试指出下述算法的功能，输出的序列是G的什么序列?(10分)
void Demo (ALGraph G)
{//G是图的逆邻接表，向量outdegree的各分量初值为0。 for(i=0；i for(p=G.adjlist[i].firstedge；p；p=p->next) //扫描i的入边表 outdegree[p->adjvex]++； //设p->adjvex=j，则将 j的出度加1 initStack(&s)； //设置空栈s for(i=0；i 46 if(outdegree[i]==0) Push(&s，i)； //出度为0的顶点i入栈 while(!StackEmpty(s)) //栈s非空 { i=Pop(&Q)； //出栈，相当于删去顶点i prinft(“%c”，G.adjlist[i].vertex)；//输出顶点i for(p=G.adjlist[i].firstedge；p；p=p->next) { //扫描i的入边表 j=p->adjvex； //j是i的入边 outdegree[j]--； //j的出度减1，即删去i的入边 Push(&s?，j)； //若j的出度为0，则令其入栈 }//endfor }//endwhile }//endDemo 四、算法题(每题15分，共45分) 1．试设计算法在O(n)时间内将数组A[1．．n]划分为左右两个部分，使得左边的所有元素值均为奇数，右边的所有元素值均为偶数，要求所使用的辅助存储空间大小为O(1)。 2．试写一递归算法，从大到小输出二叉排序中所有的值不小于x的关键字，要求算法的时间为O(h+m)，其中h为树的高度，m为输出的关键字个数。 3．设G是以邻接表表示的无向图，v0是G中的一个顶点，k是一个正的常数。要求写一算法打印出图中所有与v0有简单路径相通，且路径长度小于等于k的所有顶点(不含v0)，路径长度由路径上的边数来定义。 47 参考答案 第一章 1．(a)是线性结构，对应的数据逻辑结构图见图1-2。 (b)是树形结构，对应的数据逻辑结构图见图1-3。 (c)是有向图，其数据逻辑结构图见图1-4。 2．(a)O(m×n) (b)s+=b[i][j]的重复执行次数是n(n+1)／2，时间复杂度是O(n) (c)O(log2n) 3．D 4．D 5．D 第二章 一、单项选择题 (1) ～(5) DACAA (6)～(10) BAAAD 二、填空题 (1)链域 (2)插入 (3)删除 (4)n-i+1 (5)n-I (6)n／2 (7)(n-1)／2 (8)h=NULL (9)h->next=NULL (10)p->next=h (11) p->next->prior=s (12)p->next=s (13)p->prior->next (14)p->prior=s (15)p->next->prior=p (16)p->prior->next=p (17)p->next->prior=p->prior (18)r->next=p (19)r=p (20)r->next=q->next 三、应用题 1．顺序表：逻辑上相邻的数据元素其物理存储位置必须紧邻。其优点是：节省存储，可以随机存取。 链表：逻辑上相邻的数据元素其物理存储位置不要求紧邻，用指针来描述结点间的逻辑关系，故插入和删除运算比较方便。 2．在带表头结点的单链表中，头指针指向表头结点，不带表头结点的单链表中，头指针指向表中第一个结点(又称首元)，当进行查找运算时，必须从头指针开始去顺次访问表中每一个元素。 头结点是另设一个结点，其指针域指向存放表中第一个元素的结点，设置头结点的好处是：无需对在第一个结点前插入一个结点或删除一个结点时进行特殊处理，也可以对空表和非空表的运算进行统一处理。 四、算法设计题 1． 先判断表满否，若表未满，则从最后一个元素an开始，逐个与x进行比较，若ai>x(1≤i≤n)，则将ai后移一个位置，直到ai≤x，最后把x插入到这个位置，表长+1。算法描述如下： #define M 100 int insort(Slist *L，int z) {int i； if(L->n>=M) 48 2 {printf(“overflow\； return 0；} else for(i=L->n;i>=0;i--) if(L->data[i]>x L->data[i+1]=L->data[i]; else break； L->data[i+1]=x； L->n++； return 1； } 2．逐个查找单链表中的结点x，并计数。 int number(lnode *h,int x) { int n=0； while(h) {if(h->data==x) n++； h=h->next； } return s； } 3．前插法建立带表头结点的单链表算法中的tag为输人数据结束标志。Lnode *createhh(int tag) { int x； Lnode *p，*h=(Lnode *)malloc(sizeof(Lnode))； h->next=NULL； printf(“input x:”)； scanf(“%d”,&x); while(x!=tag) {p=(Lnode*)malloc(sizeof(Lnode)); p->data=x; p->next=h->next; h->next=p; scanf(“%d”,&x); } return h; } 49 4.先建立一个表头结点，用尾插法建立该单链表。然后将尾结点的指针域值置为表中第一个结点的首地址，最后释放表头结点。算法描述如下： Lnode *createht(int tag) { int x； Lnode *p，*r,*h=(Lnode *)malloc(sizeof(Lnode))； r=h; printf(“input x:”)； scanf(“%d”,&x); while(x!=tag) {p=(Lnode*)malloc(sizeof(Lnode)); p->data=x; r->next=p; r=p; scanf(“%d”,&x); } r->next=h->next; free(h); return r; } 5．设p指向待逆置链表中的第一个结点，先将表头结点的链域置空。顺次取出待逆置链表中的第一个结点，用前插法插入到带表头结点的单链表中。 Void reverseh(Lnode *h) { Lnode *s,*p=h->next; h->next=NULL; while(p) {s=p;p=p->next; s->next=h->next; h->next=s; } } 6.逐个检测顺序表中其值在x和y之间的元素，并计数k,再将其值大于y的元素向前移动k个元素。算法描述如下： void deletexy(Slist *a,int x,int y) { int i,k=0; for(i=0;i if(a->data[i]>=x&&a->data[i]<=y) k++; 50