数据结构试卷1

考试科目：数据结构与算法（A卷）
注意事项：请将答案写在答题纸上，写在题册上的答案无效。

…………………………………………………………………………………………
一、选择题(单选题，每题2分，共20分）
1、下列程序的时间复杂度为（）。

int i=0, s=0；
while（s<n）
{ i++；s=s+i；}
A. O（n）
B.O（n2）
C. O（n）
D.O（n2）
2. 二维数组A［10］［6］(即二维数组有10行，6列）采用行优先的存储方法，若每个元
素占4个存储单元，已知元素A［3］［4］的存储地址为1000，则元素A［4］［4］的存储地址为（）
A.1020
B.1024
C.1036
D.1240
3.循环队列sq中，用数组elem［0…25］（循环队列长度为26）存放数据元素，sq.front指示队头元素的前一个位置，sq.rear指示队尾元素的当前位置，设当前sq.front为20，sq.rear 为11，则当前队列中的元素个数为（）。

A.8
B. 16
C.17
D. 18
4.对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )。

A. (e,f)
B. ((e,f))
C. (f)
D. ( )
5.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）。

A. 0
B. 1
C. 48
D. 49
6.下列所示各图中是中序线索化二叉树的是( )。

7.在含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为（）。

A. e
B.2e
C. n2-e
D. n2-2e
8.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，最后一个元素放在A[18]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
9.对关键字序列(6，1，4，3，7，2，8，5)进行快速排序时，以第1个元素为基准的一次
快速排序的结果为（）
A.(5，1，4，3，6，2，8，7)
B.(5，1，4，3，2，6，7，8)
C.(5，1，4，3，2，6，8，7)
D.(8，7，6，5，4，3，2，1)
10.已知用某种排序方法对关键字序列（51，35，93，24，13，68，56，42，77）进行排序时，前两趟排序的结果为
（35，51，24，13，68，56，42，77，93）
（35，24，13，51，56，42，68，77，93）
所采用的排序方法是（）。

A. 插入排序
B. 冒泡排序
C. 快速排序
D. 归并排序
二、填空题（每题2分，共10分）
1、从空树起，依次插入关键字1l，27，35，48，31和34构造所得的平衡二叉树，在等概率查找的假设下，查找成功时的平均查找长度为__________。

2. 已知一棵哈夫曼树含有201个结点，则该树中有_________个叶子结点。

3、已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为_________。

4、已知一组关键字为{25，46，38，97，34，88，57，62，23，96}，其中每相邻两个关键字构成一个有序子序列。

对这些子序列进行一趟两两归并的结果是______________。

5、对序列{55，46，13，05，94，17，42}进行基数排序，第二趟排序后的结果是_________。

三、应用题（每题6分，共30分）
1、给出字符串‘babababaa’在KMP算法中的next和nextval数组。

2、用迪杰斯特拉(Dijkstra)算法求下列图中从顶点V1到其余各顶点的最短路径，按求解
过程依次写出各条最短路径及其长度。

3、如图所示的AOE网，在该网中，顶点表示事件，边表示活动，边上的权值表示活动持续的时间。

求各个事件Vj的最早发生时间ve( j )和最迟发生时间vl( j )、活动a i的最早开始时间e( i )和最迟开始时间l( i )，并写求出所有关键路径。

4、采用哈希函数Ｈ(k)=k mod 13并用线性探测开放地址法处理冲突，在数组地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51构造哈希表，要求画哈希表示意图，并在等概率情况下查找成功的平均查找长度。

5. 已知3阶B-树如图所示。

画出插入关键字100、88和38之后B-树的形状。

四、程序阅读题（共20分，每题5分）
1、以下算法的功能是用头插法建立单链表的算法，请填空完善之。

Linklist CreateFromHead( )
{ LinkList L;
Node *s;
char c;
L=(Linklist)malloc(sizeof(Node)); /*为头结点分配存储空间*/
L->next=NULL;
while( ( c=getchar()) !=’#’)
{ s=(Node*)malloc(sizeof(Node)); /*为读入的字符分配存储空间*/ s->data=c;
(1) ;
(2) ;
}
return L;
}
2、阅读下面的程序，写出该程序的运行结果。

void function( int n )
{ initstack(s); //堆栈初始化
while(n)
{ push(s,n%2); //入栈
n=n/2;
}
while(! Stackempty(s))
{ pop(s,e); //出栈
printf(“%d”,e);
}
}
void main()
{
function(121);
}
3、阅读下列算法，并回答问题：
（1）假设串由合法的英文字母和空格组成，并以’\0’作结束符。

设串s=”⊔⊔I⊔am⊔a⊔⊔⊔student”(⊔表示空格符)，写出f43（s）的返回值；
（2）简述算法f43的功能。

int f43 (char*s){
int i, n, inword;
n=inword=0;
for (i=0;s[i]!=’\0’;i++)
if (s[i]!=’⊔’&& inword= =0){
inword=1;
n++;
}
else if (s[i]= =’⊔’&& inword= =1)
inword=0;
return n;
}
4、假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node {
DataType data;
struct node * lchild, * rchild; //左右孩子指针
} * BinTree ;
阅读下列算法，并回答问题：
(1)已知以T为根指针的二叉树如图所示，
写出执行f44(T)之后的返回值；
(2)简述算法f44的功能。

int f44 ( BinTree T)
{ int d;
if ( !T) return 0;
d = f44 ( T - > lchild) + f44( T - > rchild) ;
if (T - > lchild && T - > rchild) //如果有左右孩子
return d + 1 ;
else
return d;
}
五、编程题（每题10分，共20分）
1.假设一元多项式以循环链表表示，链表的结点结构为：
typedef struct PNode {
float coef; //系数
int exp; //指数
struct PNode *next;
}*LinkList;
现需要将一个用循环链表h表示的代数多项式拆分成两个多项式循环链表h1和h2，其中h1仅含多项式的奇次项，h2仅含多项式的偶次项。

要求利用原链表中的结点构成链表h1和h2。

例如多项式7x8+5x3-4x的循环链表为
经拆分之后的情况应是：
请编写完成上述拆分的算法。

2. 编写一个算法判断是否为二叉排序树。

试卷题目所用到的数据结构如下：线索二叉树
typedef struct thBtree
{
int data;
struct thBtree * lchild, *rchild;
int Lflag:1;
int Rflag:1;
}ThBTree;
二叉树链式存储结构：
typedef struct BiTree
{
int data;
struct thBtree * lchild, *rchild;
}BinTree;
单链表节点结构体类型
typedef struct linklist
{
int data;
struct linklist *next;
}LinkList;。