数据结构试卷

1/6

习题一

一、选择题(每小题2分，共20分)

1．以下程序段的时间复杂度为（）。

i=0，s=0；while(s

(A)O(n/2)(B)O(n/3)(C)O(n)(D)O(n2)

2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用以下（）存储

方式最节省运算时间。

(A)单向链表(B)单向循环链表(C)双向链表(D)双向循环链表

3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s

指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。

(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；

4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

(A)5，3，4，6，1，2(B)3，2，5，6，4，1

(C)3，1，2，5，4，6(D)1，5，4，6，2，3

5．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存

储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0]

[0]的地址之差为（）。

(A)10(B)19(C)28(D)55

6．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数

为m的结点，则该树中共有（）个叶子结点。

7.二叉排序树中左子树上所有结点的值均（）根结点的值。

(A)<(B)>(C)=(D)!=

2/6

8.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一

棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

(A)129(B)219(C)189(D)229

9.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到H

ASH表中需要做（）次线性探测。

(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/2

10.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵

二叉中共有（）个结点。

(A)2n(B)n+l(C)2n-1(D)2n+l

二、填空题(每空2分，共50分)

1.数据元素与其关系在计算机存储器的表示称为。

2.假设某个带头结点的单链表的头指针为head，则判定该表为空表的条件

是。

3.栈是一种操作受限的线性结构，其操作的主要特征是。若进

栈序列为123，则不可能的出栈序列为。

4.已知广义表C=(a，(b，c)，d)，则：tail(head(tail(C)))=。

5.要在单链表中指针p所指向结点后插入s所指的结点，应顺序执

行和语句。

6.具有3个结点的二叉树有种形态。

7.一棵二叉树采用二叉链表存储，则必有个指针域不空。

8.对关键字序列<46，79，56，38，40，84>采用快速排序以位于最左位置的对象为基

准而得到的第一次划分结果为。

9.在哈希查找中，处理冲突的方法有、再哈希

法、和建立公共溢出区。

10.在堆排序过程中，由n个待排序记录建成初始堆需要进行次

筛选。

11.已知二叉树中叶子结点数为50，则该二叉树的总结点数至少应

有个。

3/6

12.一个具有n个顶点无向连通图最少有条边，最多

有条边。

13.图的深度优先搜索遍历算法类似于二叉树的遍历，图的广度

优先遍历算法类似于二叉树的遍历。

14.在二叉排序树上进行遍历，可以得到一个关键字的递增序

列。

15.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该

顶点的；对于有向图来说等于该顶点的。

16.若待排序序列中存在多个具有相同关键字的记录，若排序完成后这些记录的相对位

置发生改变，则称该排序法是。写出3种不稳定的排序

法、、。

三、判断题(每小题1分，共10分)

1.单链表的头结点是必不可少的。（）

2.如果一个二叉树中没有度为1的结点，则必为满二叉树。（）

3．顺序存储结构只能用来存放线性结构，链式存储结构只能用来存放非线性结构。

（）

4.队列只能在队首进行删除，在队尾进行插入。（）

5.一棵树转换成二叉树后根结点一定没有右孩子。（）

6.有向图中，所有结点的出度之和等于入度之和。（）

7.部排序是指排序过程在存中进行的排序。（）

8.在一个大根堆中，最小元素不一定在最后。（）

9.一棵赫夫曼树中不存在度为1的结点。（）

10.平衡二叉树左子树和右子树的深度之差的绝对值不超过1。（）

四、算法设计题(每题10分，共20分)

1．从顺序表中删除具有最小值的元素并返回被删元素的值。空出的位置由最后一个元

素填补，若顺序表为空则显示出错信息。

顺序表的类型描述如下：

4/6

#definemaxsize100

typedefstruct

{

ElemTypeelem[maxsize]；/*线性表占用的数组空间。*/

intlast；/*记录线性表中最后一个元素在数组elem[]中

的位置（下标值），空表置为-1*/

}SeqList；

2．已知一个二叉树采用二叉链表存放，写一算法，计算二叉树的度为2的结点的个数。

二叉链表的类型描述如下：

typedefstructNode

{

DataTypedata;

structNode*lchild;

structNode*rchild;

}BiTNode,*BiTree;

答案：

一、选择题

1．A2．D3．B4．B5．B

6．D7．A8．D9．D10．C

二、填空题

1.物理结构或存储结构

->next==NULL

3.先进后出或后进先出、312

5/6

4.（c）

5.s->next=p->next、p->next=s

6.5种

7.n-1个

8.（40,38,46,56,79,84）

9.开放定址法、链地址法

10.n/2

11.99

12.n-1、n(n-1)/2

13.先序，层次

14.中序

15.度、出度

16.不稳定、（简单项选择择排序、堆排序、快速排序、希尔排序）任选3个

三、判断题

1-10：×××√√√√√√√

四、算法设计题

1.解：

#defineOK1

#defineERROR0

intDelList(SeqList*L,ElemType*e)

/*在顺序表L中删除最小值的数据元素，并用指针参数e返回其值。空出的位置由最

后一个元素填补*/

{

intm=0,i;//假定0号元素的值最小

6/6

if(L->last==-1)//表空,中止操作返回

{printf(“ListisEmpty!n”);returnerror;}for(i=1;i<=L->la

st;i++)//循环,寻找具有最小值的元素if(L->elem[i]elem[m])m=i;/

/让m指向当前具最小值的元素

*e=L->elem[m];

L->elem[m]=L->elem[L->last];L->last--;//空出位置由最后元素填

补,表最后元素位置减1

returnok;

}

}

2.解：

/*NodeCount保存满足条件的结点的数目的全局变量,调用之前初始化值为0*/

voidNode(BiTreeroot)

{

if(root!=NULL)

{Node(root->LChild,x);

Node(root->RChild,x);

if(root->lchild！=NULL&&root->rchild！=NULL)

NodeCount++;

}

}