第一部分 选择题 (共分)
一单项选择题 (本大题共小题每小题分共分)
某算法的空间花费s(n)=nlogn+n+n+其空间复杂度为 [ ]
AO() BO(n)
CO(n) DO(nlogn)
在单项链表中删除一个指定结点的后继的时间复杂度为 [ ]
AO(n) BO(nlogn)
CO() DO(√n)
在n(n>)个元素的顺序栈中删除个元素的时间复杂度为 [ ]
AO() BO(√n)
CO(nlogn) DO(n)
对长度为n的字符串进行字符定位运算的时间复杂度为 [ ]
AO() BO(√n)
CO(nlogn) DO(n)
广义表的深度是 [ ]
A广义表中子表个数 B广义表括号个数
C广义表展开后所含的括号层数 D广义表中元素个数
高度为h(h>)的二叉树最少有________个结点 [ ]
Ah Bh
Ch+ Dh
n个顶点的带权无向连通图的最小生成树包含________个顶点 [ ]
An Bn
Cn/ Dn+
冒泡排序在最好情况下时间复杂度为 [ ]
AO() BO(nlogn)
CO(n) DO(n)
采用拉链法解决沖突的散列表中查找的平均查找长度 [ ]
A直接与关键字个数有关 B直接与装填因子a有关
C直接与表的容量有关 D直接与散列函数有关
经常修改的索引文件宜采用________做索引
A二叉排序树 B满二叉树
C多叉树 DB+树
第二部分 非选择题 (共分)
二填空题 (本大题共小题每空分共分)
某算法需要的辅助空间为s(n)=logn+/n+则该算法的空间复杂度为_______________
在n个结点的单链表中在P指向的结点之后插入一个结点的时间复杂度为_______________
设SQ为循环队列存储在数组d[m]中则SQ出队操作对其队头指针front的修改是_______________
串中所含字符个数称为该串的_______________
tail(tail(ab))=_______________
n(n>)个结点二叉树对应的森林最多包含_______________棵非空树
深度为n(n>)的二叉树最多有_______________个结点
n(n>)个结点(n)条边的连通无向图中顶点度数最大值为_______________
堆排序的空间复杂度_______________
倒排文件有_______________和主文件构成
三简答题 (本大题共小题每小题分共分)
设有函数
void fuc(int n)
{int i;
for(i=;i*i*i<=n;i++)
prinft(%di*i*i);
}
函数fuc饿时间复杂度是多少?
把依次进栈(栈初始为空)任何时刻(只要栈不空)都可以出(退)栈试写出所有可能的出栈序列(如)
若一二叉树有度结点个则其叶结点有多少个?该二叉树可以有多少个度顶点?
请画出广义表D的图形表示
D=(D(ab)((ab)c)())
有向图(带权)G如下所示
试给出用迪杰斯特拉(Dijkstra)算法求上图A到其它各顶点最短路径得到的数组P各元素值(ABCDEF编号依次是)
四理解题 (本大题共小题每小题分共分)
指出下面函数f的功能及返回值的含义
int f(char s[]char s[])
{
int i=j=;
while(s &&s[j]){
if(s >s[j])
return ;
else if(s
return ;
else i++j++;
}
if(s )
return ;
else if(s[j])
return ;
else return ;
}
指出下面函数FS的功能其中p指向先序线索二叉树的某个结点
typedef enum{LINKTHERAD}flag;
typedef char DataType;
typedef struct node{
DataType data;
flag ltagrtag;
struct node * lchild * rchild;
}BinNode;
BinNode * FS(BinNode *p)
{
if(p>ltag==LINK)
return p>lchild;
else
return p>rchild;
}
五算法填充题 (本大题共小题分)
下面函数diff的功能是根据两个由整数(都大于)按升序构成的单链表L和L(分别由AB指向)构造一个单链表L(由*r指向)要求L中的所有整数都是L并且不是L中的整数还要求L中的所有整数都两两不等在空缺处填上适当字句使其能正确工作
#include
typedef struct node {
int d;
struct node *next
} Node;
void diff (Node *A Node *B Node **r)
{
int lastnum;
Node * p;
*r=NULL;
if(!A)return;
while(_____________)
if (A>d < B>d)
_____________;
p=(Node*) malloc (sizeof(Node));
p>d=lastnum;
p>next=*r_____________;
do A=A>next;while(_____________);
}
else if (A>d > B>d)
B=B>next
else {
_____________;lastnum=A>d;
while (A&&A>d==lastnum)A=A>next;
}
while (A) {
lastnum=A>d;
p=(Node*) malloc (sizeof(Node));
p>d=lastnum;
_____________*r=p;
while (A&&A>d==lastnum) A=A>next;
}
}
