数据结构期中考试试卷答案（最终定稿）

第一篇：数据结构期中考试试卷答案

2014－2015学年度第一学期《数据结构》

期中考试试卷

一、选择题（每题2分，共20分）

1.计算机内部数据处理的基本单位是（B）。

A.数据 B.数据元素

C.数据项

D.数据库 2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。

for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O(n)C.O(n)

D.O(n)

33.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素。

A．n-i B．n-i+l C．n-i-1 D．i 4.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。

A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。C A．top不变

B．top=0 C．top--D．top++ 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.两个字符串相等的条件是（D）。

A.两串的长度相等 B.两串的长度相等，并且两串包含的字符相同 C.两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同

8.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大 B.3

C.2 D.5 10.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。

A.15

B.16

C.17

D.47

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

1.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图

2.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间

3.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7．顺

（第1页，共3页）

序，链接

4.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n)5.可以在线性表的______位置插入和删除元素；对于栈只能在_______位置删除元素；对于队列只能在_______位置插入元素。9任何，栈顶，队尾 6.设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。3.“BCDEDE”

7.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序

8.三维数组R[c1„d1,c2„d2,c3„d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）

9.数组A[1„10，-2„6，2„8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。10.913

三、简答题（每题6分，共18分）1.已知L是无表头结点的单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)在P结点后插入S结点。(2)在表首插入S结点。(3)在表尾插入S结点。2已知L是带表头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)删除P结点的直接后继结点。(2)删除P结点。（3）删除尾元结点。3． LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L；

S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL；

} return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, „,an）,写出算法执行后的返回值所表示的线性表。

该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

四、算法设计题（每题14分，共42分）1.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。

解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下：

void delete(LinkList *p){ //在链表中删除p所指结点的前趋结点 LinkList *q,*t;

q=p;

while(q->next->next!=p)//q->next不是p的前趋结点

（第2页，共3页）

q=q->next;

t=q->next;//t指向要删除结点

q->next=p;//删除t结点

free(t);｝

2.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。

2．算法描述如下：

delete(LinkList *head, int max, int min){ LinkList *p,*q;

q=head;

p=head->next;

while(p!=NULL)

if((p->data<=min)||(p->data>=max))

{ q=p;

p=p->next;

} else { q->next=p->next;free(p);p=q->next;} }

3.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。

（第3页，共3页）

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

一、选择题（每小题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;} }