数据结构试卷及参考答案_5

第一篇：数据结构试卷及参考答案_5

数据结构试卷

（五）一、选择题(20分)

1．数据的最小单位是（）。

(A)数据项(B)数据类型(C)数据元素(D)数据变量

2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。

(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。

(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。

(A)“STRUCTURE”

(B)“DATA”

(C)“ASTRUCTUR”

(D)“DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。

(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。

(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。

(A)25(B)10(C)7(D)1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。

(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。

(A)n-i(B)n-1-i(C)n+1-i(D)不能确定 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。

(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80

二、填空题(共20分)1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。

2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。3.设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。

4.栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。

5.设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。6.设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。

7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。

8.设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。

9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。

void bubble(int r[n]){ for(i=1;i<=n-1;i++){ for(exchange=0,j=0;j<_____________;j++)

if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;} if(exchange==0)return； } } 10.下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。struct record{int key;int others;};int bisearch(struct record r[ ], int k){

int low=0,mid,high=n-1;

while(low<=high){ ________________________________;

if(r[mid].key==k)return(mid+1);else if(____________)high=mid-1;else low=mid+1;

}

return(0);}

三、应用题(32分)

1.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。2.设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。

3.设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。4.设散列表的长度为8，散列函数H(k)=k mod 7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。

四、算法设计题(28分)1． 设计判断两个二叉树是否相同的算法。2． 设计两个有序单链表的合并排序算法。

数据结构试卷

（五）参考答案

一、选择题 1．A 2．B 6．B 7．B

二、填空题

1.top1+1=top2 2.可以随机访问到任一个顶点的简单链表 3.4.5.6.7.i(i+1)/2+j-1 FILO，FIFO ABDECF，DBEAFC，DEBFCA 8，64 出度，入度

3．A 8．B

4．A 9．C

5．D 10．C 8.ki<=k2i&& ki<=k2i+1 9.n-i，r[j+1]=r[j] 10.mid=(low+high)/2，r[mid].key>k

三、应用题

1.DEBCA 2.E={(1,5),(5,2),(5,3),(3,4)},W=10 3.ASL=(1*1+2*2+3*4)/7=17/7 4.ASL1=7/6，ASL2=4/3

四、算法设计题

1.设计判断两个二叉树是否相同的算法。

typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;int judgebitree(bitree *bt1,bitree *bt2){

if(bt1==0 && bt2==0)return(1);

else if(bt1==0 || bt2==0 ||bt1->data!=bt2->data)return(0);

else return(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));} 2.设计两个有序单链表的合并排序算法。

void mergelklist(lklist *ha,lklist *hb,lklist *&hc){

lklist *s=hc=0;

while(ha!=0 && hb!=0)

if(ha->datadata){if(s==0)hc=s=ha;else {s->next=ha;s=ha;};ha=ha->next;}

else {if(s==0)hc=s=hb;else {s->next=hb;s=hb;};hb=hb->next;}

if(ha==0)s->next=hb;else s->next=ha;}

第二篇：数据结构期中试卷及答案

一、选择题（每小题2分，共30分）1.数据结构是（D）。

A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合

D．相互之间存在一种或多种特定关系的数据元素的集合

2．以下与数据的存储结构无关的术语是（D）。

A．链队列 B.链表 C.顺序表 D.栈

3．以下数据结构中，（A）是非线性数据结构

A．树 B．字符串 C．队 D．栈

4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。

A．98 B．100 C．102 D．106

5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A．插入 B．删除 C．排序 D．查找

6．线性表采用链式存储时，其地址(D)。

A．必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以

7．线性表是(A)。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空

8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。

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

9.若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C）。

A．k B．n-k-1 C．n-k+1 D．不确定

10.对于队列操作数据的原则是（A）。

A.先进先出 B.后进先出 C.先进后出 D.不分顺序 11.栈和队列的共同点是（C）。

A.都是先进先出 B.都是先进后出 C.只允许在端点处插入和删除元素 D.没有共同点

12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（A）。

A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear

13.空串与空格串（B）。

A．相同 B．不相同 C．可能相同 D．无法确定

14.串与普通的线性表相比较，它的特殊性体现在（C）。A．顺序的存储结构 B．链接的存储结构 C．数据元素是一个字符 D．数据元素可以任意

15.串的长度是指（B）。

A.串中所含不同字母的个数 B.串中所含字符的个数

C.串中所含不同字符的个数 D.串中所含非空格字符的个数

二、填空题（每空2分，共20分）

1． 线性表、栈和队列，串都是__线性_____结构。2． 数据的基本单位是__数据元素_______________。

3． 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序______存储结构。4． 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为Loc(a1)，那么，第i个元素的存储地址Loc(ai)= Loc(a1)+(i-1)*k。5． 栈（stack）是限定在表尾进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为__栈顶________，而另一端称为_栈底________。6． 一个循环队列Q中，头指针和尾指针分别为Q.front和Q.rear，且最大队列长度为MaxQSize，则判断队空的条件为 Q.rear==Q.front,判断队满的条件为(Q.rear+1)%MaxQSize==Q.front。队列的长度为(.rear-Q.front+MaxQSize)%MaxQSize

7． 两个串相等的充分必要条件是 两个串的长度相等，且各个对应位置的字符都相等。

三、程序填空题（每空3分，共30分）

1.在带头结点的单链表L中第i个数据元素之前插入数据元素e的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。

typedef struct node {int data；

struct node *next；

}linknode,*link；

int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0；

while(p && j < i-1){ p=p->next ； ++j； } // 寻找第i-1个结点 if(!p || j > i-1)return 0；

s=(link)malloc(sizeof(linknode))；// 生成新结点s s->data = e；

s->next=p->next ； p->next = s； // 插入L中 return 1； }

2.对顺序栈的C语言描述算法如下，其中top为栈顶指针，请填充算法中标出的空白处，插入元素e为新的栈顶元素。

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack;

int Push(SqStack &S, char e){ //

if((s.top-s.base)>=s.stacksize)//栈满，追加存储空间 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0；

S.top = s.base+s.stacksize ； //修改栈顶指针 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； }

3.对链队列的C语言描述算法如下，请填充算法中标出的空白处，删除队列Q 的队头元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr；

typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue；

int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p；

if(Q.front==Q.rear)retrun 0；//队列空，返回 p = Q.front-> next； e = p->data；

Q.front-> next=p->next；//修改指针

if(Q.rear==p)Q.rear= Q.front ； //队列只有一个元素的情况 free(p)；//释放结点空间 return 1； }

三、算法设计与分析题（每题10分，共20分）

1、简述下列算法实现的功能：（每题5分，共10分）（1）typedef struct LNode{

Char data;

struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是无头结点单链表 LNode *Q,*P;if(L&&L->next){

Q=L;L=L->next;P=L;while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

} return L;}// Demo 答：将单链表的第一个结点删除，放到链尾。

———————————————————————————————————————————————————

（2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize;

} Stack;void Demo1(Stack &S, int m){ Stack T;int i;

InitStack(T);//初始化栈

while(!StackEmpty(S))//判断栈是否为空

if((i=Pop(S))!=m)Push(T,i);//入栈操作

while(!StackEmpty(T))

{

i=Pop(T);//出栈操作

Push(S,i);

}

} 答：删除栈S中所有值为m的数据元素

2.有一个带头结点的单链表，头指针为head，编写一个算法计算所有数据域为X的结点的个数（不包括头结点）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;}

第三篇：数据结构试卷(一)及答案

数据结构试卷

（一）一、选择题（20分）

1．组成数据的基本单位是（）。

(A)数据项(B)数据类型(C)数据元素(D)数据变量

2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A)线性结构(B)树型结构(C)图型结构(D)集合 3．数组的逻辑结构不同于下列（）的逻辑结构。

(A)线性表(B)栈(C)队列(D)树 4．二叉树中第i(i≥1)层上的结点数最多有（）个。

ii-1(A)2i(B)2(C)2(D)2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A)p->next=p->next->next(B)p=p->next

(C)p=p->next->next(D)p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A)6(B)4(C)3(D)2 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A)100(B)40(C)55(D)80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A)3(B)4(C)5(D)1 9．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A)4(B)5(C)6(D)7 10.设有以下四种排序方法，则（）的空间复杂度最大。

(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序

二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________。

2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。

4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。

5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。

6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。

8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。

9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。

int index(char s[ ], char t[ ]){ i=j=0;while(i

三、应用题（30分）

1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。

2．设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。

3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求给出以19为基准的一趟快速排序结果以及第2趟直接选择排序后的结果。

4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树。

四、算法设计题(20分)1.设计判断单链表中结点是否关于中心对称算法。2.设计在链式存储结构上建立一棵二叉树的算法。3.设计判断一棵二叉树是否是二叉排序树的算法。

数据结构试卷

（一）参考答案

一、选择题

1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B

二、填空题 1.(F+1)% m 2.O(n)，O(n)3.2n，n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1

三、应用题

1.链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼树略，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23)

h0h18h2012345674.线性探测： 链地址法：h310

81025322768h42532h568h6275.深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}

四、算法设计题

1.设计判断单链表中结点是否关于中心对称算法。

typedef struct {int s[100];int top;} sqstack;int lklistsymmetry(lklist *head){

sqstack stack;stack.top=-1;lklist *p;

for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;}

for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0);

return(1);} 2.设计在链式存储结构上建立一棵二叉树的算法。

typedef char datatype;typedef struct node {datatype data;struct node *lchild,*rchild;} bitree;void createbitree(bitree *&bt){

char ch;scanf(“%c”,&ch);

if(ch=='#'){bt=0;return;} bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);} 3.设计判断一棵二叉树是否是二叉排序树的算法。

int minnum=-32768,flag=1;typedef struct node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){

if(bt!=0)

{inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} }

第四篇：广东海洋大学数据结构试卷及答案

广东海洋大学

2013 ——

2014 学年第 1 学期

《数据结构与算法》课程试题

一、选择题（6小题，每题3分）

1.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（A)存储方法最节省时间 A 顺序表

B单链表

C 双链表

D单循环链表 2.一个栈的入栈序列是1,2,3,4,5，则不可能的出栈序列是(C)A 5,4,3,2,1

B 4,5,3,2,1

C 4,3,5,1,2

D 1,2,3,4,5 3.深度为k的完全二叉树至多有（C）个结点 A 2k2

1B 2k1

C

D 2k11

k4.G是一个非连通无向图，共28条边，则该图至少有（D）个顶点2A 6

B 7

C 8

D 9

1

5.在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（C）型调整以使其平衡 A LL

B LR

C RL

D RR 6.下述排序方法中，时间性能和待排序记录的初始状态无关的是（C）A 插入排序和快速排序

B 归并排序和快速排序 C 选择排序和归并排序

D 插入排序和归并排序

二、填空题

1.数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素位置，计算队列中元素个数的公式为______（rear-front+n）%n______________。

2.已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有__12_________个叶子结点。

3.已知无向图的顶点数为n，边数为e，其邻接表表示的空间复杂度为____________O(n+e)____。4.假定一个数列{25,43,62,31,48,56}，采用散列函数为H(k)=k mod 7，则元素48的同义词是____62_______。5.利用简单选择排序对n个记录进行排序，最坏情况下，记录交换次数为_____n-1_______。

三、（15分）已知一棵二叉树的中序遍历序列为DBKEHJAFCIG，后序遍历序列为DKJHEBFIGCA，试画出该二叉树并给出其前序遍历序列

四、（15分）设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，它们在电文中出现的频度分别为{0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06}，回答下面问题：（1）为这八个字符设计哈夫曼编码（2）对这八个字符进行等长编码需要几位二进制数，哈夫曼编码比等长编码电文总长压缩多少？

五、（20分）已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题（1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？

（2）如果对线性表元素排序后进行折半查找，画出折半查找判定树，假设每个元素查找概率相同，计算平均查找长度。

六、（12分）已知数据序列为（11,4,8,19,6,31,23），写出快速排序及堆排序每一趟的结果 解：

七、（11分）设单链表以非递减有序排列，设计算法实现在单链表中删除值相同的多余结点。

第五篇：数据结构试卷(八)及答案

数据结构试卷

（八）一、选择题(30分)1.字符串的长度是指（）。

(A)串中不同字符的个数(B)串中不同字母的个数

(C)串中所含字符的个数(D)串中不同数字的个数 2.建立一个长度为n的有序单链表的时间复杂度为（）(A)O(n)(B)O(1)(C)O(n)(D)O(log2n)3.两个字符串相等的充要条件是（）。

(A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等

(C)同时具备(A)和(B)两个条件(D)以上答案都不对

4.设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。

(A)99(B)97(C)91(D)93 5.在二叉排序树中插入一个关键字值的平均时间复杂度为（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n)6.设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。

(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4] 7.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。

(A)8(B)7(C)6(D)5 8.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。

(A)5(B)6(C)7(D)8 9.设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。

(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc 10.队列是一种（）的线性表。

(A)先进先出(B)先进后出(C)只能插入(D)只能删除

二、判断题(20分)1.如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）2.设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）3.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）4.二维数组和多维数组均不是特殊的线性结构。（）

5.向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）6.如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）7.非空的双向循环链表中任何结点的前驱指针均不为空。（）8.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）

9.图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（）

三、填空题(30分)1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。2． 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。

typedef struct node{int data;struct node *lchild;struct node *rchild;}bitree;void bstinsert(bitree *&t,int k){ if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;} else if(t->data>k)bstinsert(t->lchild,k);else__________________________;} 3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_________________。4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。

5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。

6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。

7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。

8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。

9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。

四、算法设计题(20分)1.设计一个在链式存储结构上统计二叉树中结点个数的算法。2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

数据结构试卷

（八）参考答案

一、选择题 1．C 2．C 3．C 4．B 5．B 6．C 7．B 8．C 9．A 10．A

二、判断题

1．对 2．错 3．对 4．错 5．错 6．对 7．对 8．对 9．对 10．对

三、填空题

1.(49，13，27，50，76，38，65，97)2.t=(bitree *)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.p->next=s 4.head->rlink，p->llink 5.CABD 6.1，16 7.0 8.(13，27，38，50，76，49，65，97)9.n-1 10.50

四、算法设计题

1.设计一个在链式存储结构上统计二叉树中结点个数的算法。

void countnode(bitree *bt,int &count){

if(bt!=0)

{count++;countnode(bt->lchild,count);countnode(bt->rchild,count);} } 2.设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。

typedef struct {int vertex[m];int edge[m][m];}gadjmatrix;typedef struct node1{int info;int adjvertex;struct node1 *nextarc;}glinklistnode;typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode;void adjmatrixtoadjlist(gadjmatrix g1[ ],glinkheadnode g2[ ]){ int i,j;glinklistnode *p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){ p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode *)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;} }