一单项选择题 ( 本大题共 小题每小题 分共 分 )
在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题干的括号内错选多选或未选均无分
下列各式中按增长率由小至大的顺序正确排列的是 ( )
A n ! n n / B n / n n logn
C n log n n logn n / D logn n n n
若要在单链表中的结点 *p 之后插入一个结点 *s 则应执行的语句是 ( )
A s>next=p>next; p>next=s; B p>next=s; s>next=p>next;
C p>next=s>next; s>next=p; D s>next=p; p>next=s>next;
若要在 O ( )的时间复杂度上实现两个循环链表头尾相接则应对两个循环链表各设置一个指针分别指向 ( )
A 各自的头结点
B 各自的尾结点
C 各自的第一个元素结点
D 一个表的头结点另一个表的尾结点
栈的两种常用存储结构分别为 ( )
A 顺序存储结构和链式存储结构 B 顺序存储结构和散列存储结构
C 链式存储结构和索引存储结构 D 链式存储结构和散列存储结构
已知循环队列的存储空间为数组 data[] 且当前队列的头指针和尾指针的值分别为 和 则该队列的当前长度为 ( )
A B
C D
已知在如下定义的链串结点中每个字符占 个字节指针占 个字节则该链串的存储密度为
typedef struct node {
char data[];
struct node *next;
} LinkStrNode;
A / B /
C / D /
应用简单的匹配算法对主串 s= ″ BDBABDABDAB ″与子串 t= ″ BDA ″进行模式匹配在匹配成功时进行的字符比较总次数为 ( )
A B
C D
二维数组 A[][] 采用列优先的存储方法若每个元素占 个存储单元且第 个元素的首地址为 则元素 A[][] 的存储地址为 ( )
A B
C D
对广义表 L=((ab)cd) 进行操作 tail(head(L)) 的结果是 ( )
A ( cd ) B (d)
C b D (b)
已知一棵树的前序序列为 ABCDEF 后序序列为 CEDFBA 则对该树进行层次遍历得到的序列为 ( )
A ABCDEF B ABCEFD
C ABFCDE D ABCDFE
一个含 n 个顶点和 e 条弧的有向图以邻接矩阵表示法为存储结构则计算该有向图中某个顶点出度的时间复杂度为 ( )
A O(n) B O(e)
C O(n+e) D O(n )
在关键字序列 ( ) 中二分查找关键字为 和 的结点时所需进行的比较次数分别为 ( )
A B
C D
下列排序方法中最好与最坏时间复杂度不相同的排序方法是 ( )
A 冒泡排序 B 直接选择排序
C 堆排序 D 归并排序
已知含 个结点的二叉排序树是一棵完全二叉树则该二叉排序树在等概率情况下查找成功的平均查找长度等于 ( )
A B
C D
在下列各种文件中不能进行顺序查找的文件是 ( )
A 顺序文件 B 索引文件
C 散列文件 D 多重表文件
二填空题 ( 本大题共 小题每小题 分共 分 )
抽象数据类型是指数据逻辑结构及与之相关的 ___________
已知在结点个数大于 的单循环链表中指针 p 指向表中某个结点则下列程序段执行结束时指针 q 指向结点 *p 的 ___________ 结点
q=p;
while(q>next!=p)q=q>next;
假设 S 和 X 分别表示进栈和出栈操作由输入序列 ABC 得到输出序列 BCA 的操作序列为 SSXSXX 则由 a*b+c/d 得到 ab*cd/+ 的操作序列为 ___________
在文本编辑程序中查找某一特定单词在文本中出现的位置可以利用串的 ___________ 运算
假设以行优先顺序将一个 n 阶的 对角矩阵压缩存储到一维数组 Q 中则数组 Q 的大小至少为 ___________
在含 个结点的完全二叉树中叶子结点的个数为 ___________
在无向图中若从顶点 a 到顶点 b 存在 ___________ 则称 a 与 b 之间是连通的
如果排序过程不改变 ___________ 之间的相对次序则称该排序方法是稳定的
索引顺序查找适宜对 ___________ 的顺序表进行查找
文件的检索操作可按检索条件不同分为下列四种询问它们是简单询问范围询问函数询问及 ___________
三解答题 ( 本大题共 小题每小题 分共 分 )
画出下图所示二叉树的中序线索链表的存储表示
已知图 G= ( V E )其中
V={abcde}
E={(ab)(bd)(cb)(cd)(de)(ea)(ec)}
( )画出图 G ;
( )画出图 G 的邻接表
( )
( )
已知自顶向下的二路归并排序的算法如下所示按此算法对关键字序列( )进行排序列出算法执行过程中前 次调用 Merge 函数进行归并之后的关键字序列
void MergeSorDC(SeqList R int low int high)
{// 用分治法对 R[lowhigh] 进行二路归并排序 }
int mid;
if (low mid=(low+high)/2; // 分解
MergeSortDC(R, low, mid); // 递归地对 R[low..mid] 排序
MergeSortDC(R,mid+1,high); // 递归地对 R[mid+1..high] 排序
Merge(R, low, mid, high); // 组合，将两个有序区归并为一个有序区
}
} //MergeSortDC
29 .由于元素的插入先后次序不同，所构成的二叉排序树可能有多种形态。tW.wingwit.cOM请画出 4 棵含 1 ， 2 ， 3 ， 4 ， 5 ， 6 六个元素且以 1 为根、深度为 4 的二叉排序树。
四、算法阅读题 ( 本大题共 4 小题，每小题 5 分，共 20 分 )
30 . L 为一个带头结点的循环链表。函数 f30 的功能是删除 L 中数据域 data 的值大于 c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。
LinkList f30(LinkList L, int c)
{
LinkList Lc,p,pre;
pre=L;
p= (1) ;
Lc=(LinkList) malloc(sizeof(ListNode));
Lc->next=Lc;
while(p!=L)
if(p->data>c)
{
pre->next=p->next;
(2) ;
Lc->next=p;
p=pre->next;
}
else
{
pre=p;
(3) ;
}
return Lc;
}
(1)
(2)
(3)
31 . 设栈 S=(1,2,3,4,5,6,7), 其中 7 为栈顶元素。
( 1 )写出调用 f31(&S) 后的 S ;
( 2 )简述函数 f31 中第 1 个循环语句的功能。
void f31 (Stack *S)
{
Queue Q;
Stack T;
int i=0;
InitQueue(&Q);
InitStack(&T);
while(!StackEmpty(S))
if ((i=!t)!=0) Push(&T,Pop(S));
else EnQueue(&Q, Pop(S));
while(!StackEmpty(&T))
Push(S,PoP(&T));
while(!QieueEmpty(&Q))
Push(S,DeQueue(&Q));
}
(1)
(2)
32 .图的邻接矩阵表示描述如下：
#define MaxNum 20 // 图的最大顶点数
typedef struct {
char vexs[MaxNum]; // 字符类型的顶点表
int edges[MaxNum][MaxNum]; // 邻接矩阵
int n, e; // 图的顶点数和边数
} MGraph; // 图的邻接矩阵结构描述
阅读下列算法，并回答问题：
( 1 )对于下列图 G 的邻接矩阵，写出函数调用 f32(&G,3) 的返回值;
( 2 )简述函数 f32 的功能;
( 3 )写出函数 f32 的时间复杂度。
int f32(MGraph *G, int i)
{
int d=0,j;
for(j=0;jn;j++)
{
if (G->edges[i][j]) d++;
