一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。
4. 若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则可能出现的出栈序列为
- A.3,2,6,1,4,5
- B.3,4,2,1,6,5
- C.1,2,5,3,4,6
- D.5,6,4,2,3,1
A B C D
14. 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t),则在二分查找关键字b的过程中,先后进行比较的关键字依次为
- A.f,c,b
- B.f,d,b
- C.g,c,b
- D.g,d,b
A B C D
二、填空题1. 称算法的时间复杂度为O(f(n)),其含义是指算法的执行时间和______的数量级相同。
2. 在一个长度为n的单链表L中,删除链表中*p的前驱结点的时间复杂度为______。
3. 假设为循环队列分配的向量空间为Q[20],若队列的长度和队头指针值分别为13和17,则当前尾指针的值为______。
4. 设s="I AM A ATHLETE",t="GOOD",则执行下列串操作序列之后得到的suhl为______。
substr(sub1,s,5,2);substr(sub2,s,6,8);strcpy(t1,t);
strcat,(t1,sub2);strcat(sub1,t1);
6. 一棵含999个结点的完全二叉树的深度为______。
7. 含n个顶点的无向连通图中至少含有______条边。
8. 对表长为9000的索引顺序表进行分块查找,假设每一块的长度均为15,且以顺序查找确定块,则在各记录的查找概率均相等的情况下,其查找成功的平均查找长度为______。
9. 若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序,则得到的结果为______。
15,02,21,24,26,57,43,66,80,48,73
10. ISAM文件由主索引、______、______和主文件组成。
三、解答题1. 某广义表的表头和表尾均为(a,(b,c)),画出该广义表的图形表示。
已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。
(1)画出该二叉树;
(2)画出与(1)求得的二叉树对应的森林。已知带权图的邻接表如下所示,其中边表结点的结构为:
依此邻接表从顶点C出发进行深度优先遍历。
(1)画出由此得到的深度优先生成树;
(2)写出遍历过程中得到的从顶点C到其他各顶点的带权路径及其长度。从空树起,依次插入关键字37,50,42,18,48,12,56,30,23,构造一棵二叉排序树。
(1)画出该二叉排序树;
(2)画出从(1)所得树中删除关键字为37的结点之后的二叉排序树。 五、算法设计题1. 假设以带头结点的单链表表示有序表,单链表的类型定义如下:
typedef struct node{
DataType data;
struct node*next
}LinkNode,*LinkList;
编写算法,从有序表A中删除所有和有序表B中元素相同的结点。
参考答案一:
void f34(LinkList ha,LinkList hb)
{ //hb和hb分剐为存放A和B有序链表的头指针
LinkList p,q,r;
p=ha;
q=hb—>next;
while(p—>next&&q){
if(p—>next—>data<q->data)
p=p—>next;
else{
if(p—>next—>data==q—>data){
r=p—>next;
p—>next=r—>next;
free(r);
} //从A表删除相同的元素结点
q=q—>next;
}
}
}
参考答案二:
void f34(LinkList ha,LinkList hb)
{ //hb和hb分别为存放A和B有序链表的头指针
LinkList p,q,r;
r=ha;p=ha—>next;
q=hb—>next;
while(p&&q){
if(p—>data<q—>data){
r=p;p=p->next;
}else{
if(p—>data==q—>data){
r—>next=p—>next;
free(p);
p=r—>next;
} //从A表删除相同的元素结点
q=q—>next
}
}
}