第一部分 选择题 (共分)
一单项选择题(本大题共小题每小题分共分)
在每小题列出的四个备选项中只有一个是符合题目要求的请将其代码填写在题后的括号内错选多选或未选均无分
数据元素及其关系在计算机存储器内的表示称为数据的( )
A逻辑结构 B存储结构 C线性结构 D非线性结构
某带头结点的单链表的头指针为head判定该链表为非空的条件是( )
Ahead==NULL Bhead>next==NULL Chead!=NULL Dhead>next!=NULL
导致栈上溢的操作是( )
A栈满时执行的出栈 B栈满时执行的入栈
C栈空时执行的出栈 D栈空时执行的入栈
设数组A[m]为循环队列Q的存储空间front为队头指针rear为队尾指针则判定Q为空队列的条件是( )
A(rearfront)%m= = Bfront= =rear
C(rearfront)%m= =m Dfront= =(rear+)%m
假设S=″I AM A STUDENT″则运算substr(S)的结果为( )
A″M A S″ B″M A STUD″ C″A STUDEN″ D″STUD″
在执行简单的串匹配算法时最坏的情况为每次匹配比较不等的字符出现的位置均为( )
A模式串的最末字符 B主串的第一个字符
C模式串的第一个字符 D主串的最末字符
从广义表L=(((d)cd))中分解得到(d)的操作为( )
Ahead(head(head(L))) Bhead(tail(head(L)))
Ctail(head(head(L))) Dtail(tail(head(L)))
假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中其中根结点存放在BT[]若BT[i]中的结点有左孩子则左孩子存放在( )
ABT[i/] BBT[*i] CBT[*i] DBT[*i+]
右图所示二叉树的中序序列是( )
ADHEBAFIJCG BDHEBAFJICG CDBHEAFCJIG DDBHEAFJICG
连通图是指图中任意两个顶点之间( )
A都连通的无向图 B都不连通的无向图
C都连通的有向图 D都不连通的有向图
下图所示带权无向图的最小生成树的权为( )
A B C D
对记录序列()依次按个位和十位进行两趟基数排序之后所得结果为( )
A B
C D
在待排关键字序列基本有序的前提下效率最高的排序方法是( )
A直接插入排序 B快速排序 C直接选择排序 D归并排序
在下列各棵二叉树中二叉排序树是( )
采用ISAM或VSAM组织的文件是( )
A索引非顺序文件 B顺序文件 C索引顺序文件 D散列文件
第二部分 非选择题 (共分)
二填空题(本大题共小题每小题分共分)
请在每小题的空格中填上正确答案错填不填均无分
在一个长度为n的循环链表中删除其元素值为x的结点的时间复杂度为______
已知指针p指向某单链表中的一个结点则判别该结点有且仅有一个后继结点的条件是______
如果入栈序列是…且出栈序列的第一个元素为则出栈序列中第个元素为______
已知广义表LS为空表则其深度为______
假设以行优先顺序存储三维数组A[][][]其中元素A[][][]的地址为且每个元素占个存储单元则A[][][]的地址是______
已知一棵二叉树的先序序列为ABCD中序序列为BCAD则它的后序序列为______
在含n个顶点的连通图中任意两个不同顶点之间的一条简单路径最多包含______条边
对关键字序列()进行直接插入排序当将第个关键字插入到当前的有序子表中时为寻找插入位置需进行______次关键字之间的比较
对有序表进行二分查找的过程可用判定树来描述其判定树的形态只取决于______
将有序表中n个元素依次插入到一棵空的二叉排序树中则在等概率查找的情况下该二叉排序树在查找成功时的平均查找长度是______
三解答题(本大题共小题每小题分共分)
()写出右侧图形表示的广义表L
()画出其表头与表尾均为(a(bc))的广义表L的图形表
()
()
试推导一棵满k叉树上的叶子结点数a与非叶子结点数b之间满足以下关系
a=(k)b+
假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径按求解过程依次写出各条最短路径及其长度
已知关键字序列在R[]中的初始状态为
R
写出在将它调整为大根堆的过程中每一次筛选后R的状态
四算法阅读题(本大题共小题每小题分共分)
如果希望循环队列中的向量单元都能得到利用则可设置一个标志域tag每当尾指针和头指针值相同时以tag的值为或来区分队列状态是空还是满请对下列函数填空使其分别实现与此结构相应的入队列和出队列的算法
int EnQueue(CirQueue *QDataType x){
if( () ) return ;
Q>data[Q>rear]=x;
Q>rear=(Q>rear+)% MAXQSIZE
()
return ;
}
int DeQueue(CirQueue *QDataType *x){
if( () ) return ;
*x=Q>data[Q>front];
Q>front= () ;
() ;
return ;
}
()
()
()
()
()
已知具有n个结点的完全二叉树采用顺序存储结构存储在向量BT[n]中结点的数据元素为字符类型请阅读下列算法并回答问题
()假设向量BT中的内容为
BT
A
B
C
D
E
F
写出执行f(BT)后的输出结果;
()说明该算法的功能
void f(char BT[]int n)
{ int i=;
while(i>)
if(i<=n) {
printf(″%c″ BT[i]);
i=i*;
}else{
do {i=i/;} while(i%);
if(i>) i++;
}
}
()
()
设数组f的初始元素序列为
f[]=()
阅读下列算法并回答问题其中算法f中调用的函数swap(ab)用以完成交换a和b的值
()写出执行f(f)之后f[]中的元素序列并写出在执行过程中调用swap函数的次数
()简述算法f的功能
void f(int f[]int nint xint y) {
int i=j=k=n;
while (j<=k)
if (f[j]==y)j++;
else if (f[j]==x)
{ swap(f[i]f[j]);i++;j++;}
else {swap(f[k]f[j];k;}
}
()
()
下列算法利用二分查找方法在有序表r中插入元素x并保持表r的有序性其中参数*n为表r的长度请在空缺处填入合适的内容使其成为一个完整的算法
void BinInsert(SeqList rint *nDataType x)
{ int low=high=*nmidi;
while(low<=high)
{ mid= () ;
if (xkey else (2) ;
}
for(i=*n; (3) ;i--)
r[i+1]=r[i];
(4) ;
*n++;
}
(1)
(2)
(3)
(4)
五、算法设计题(本题共10分)
34.假设一元多项式以循环链表表示，链表的结点结构为：
typedef struct PNode {
float coef; //系数
int exp; //指数
struct PNode *next;
}*LinkList;
现需要将一个用循环链表h表示的代数多项式拆分成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。TW.winGWIt.COm要求利用原链表中的结点构成链表h1和h2。例如多项式7x8+5x3-4x的循环链表为
经拆分之后的情况应是：
请编写完成上述拆分的算法，并进行算法分析。
