数据结构样卷.docx

数据结构样卷.docx

《数据结构样卷.docx》由会员分享，可在线阅读，更多相关《数据结构样卷.docx（14页珍藏版）》请在冰点文库上搜索。

数据结构样卷

2009级《数据结构》考试样卷

一、单项选择题（本大题共30小题，每小题1分，共30分）

1.在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（C）

A.q.next=p.next；p.next=q；B.p.next=q.next；q=p；

C.p.next=q.next；q.next=p；D.q.next=p；p.next=q.next；

2.数据的四种存储结构是（A）

A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构

B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构

C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构

D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构

3.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是（C）

A.无头结点的单向链表B.带头结点的单向链表

C.带头结点的双循环链表D.带头结点的单循环链表

4.若带头结点的单链表的头引用为head，则判断链表是否为空的条件是（B）

A.head=NULLB.head.next=NULLC.head!

=NULLD.head.next!

=head

5.若元素的入栈顺序为1，2，3....，n，如果第2个出栈的元素是n，则输出的第i（1<=i<=n）个元素是（D）A.n-iB.n-i+lC.n-i+2D.无法确定

6.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是（B）

A.树中没有度为2的结点B.树中只有一个根结点

C.树中非叶结点均只有左子树D.树中非叶结点均只有右子树

7.若根结点的层数为1，则具有n个结点的二叉树的最大高度是（A）

A.nB.n/2C.+1D.

8.在图G中求两个结点之间的最短路径可以采用的算法是（A）

A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法

C.普里姆（Prim）算法D.广度优先遍历（BFS）算法

9.下图G=（V,E）是一个带权连通图，G的最小生成树的权为（D）

A.15B.16

C.17D.18

题9图题10图

10.在下图中，从顶点1出发进行深度优先遍历可得到的序列是（B）

A.1234567B.1426375C.1425367D.1246537

11.用链接方式存储的队列，在进行删除运算时（D）.

A.仅修改头指针　B.头、尾指针都要修改

C.仅修改尾指针D.头、尾指针可能都要修改

12.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为（D）

A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，3

13.对有n个记录的线性表进行冒泡排序，最好情况（正序）时，其时间复杂度（比较次数）为（B）。

A.O

（1）　　B.O（n）　　C.O（1og2n）D.O（n2）

14.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（D）个。

A．1B．2C．3D．4

15.设有6个结点的无向图，该图至少应有（A）条边才能确保是一个连通图。

A.5B.6C.7D.8

16.设顺序循环队列Q[0：

M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（C）。

A.R-FB.F-RC.（R-F+M）％MD.（F-R+M）％M

17.设某有向图中有n个顶点，则该有向图对应的邻接表中有（B）个表头结点。

A.n-1B.nC.n+1D.2n-1

18.设一组初始记录关键字序列为（5,2,6,3,8,10,1,7,9），对其进行希尔排序，第一趟的分组距离d=3，则对其完成第一趟希尔排序后的结果为（C）。

A.2,3,5,8,6,1,7,9,10B.3,2,6,1,7,9,5,8,10

C.1,2,6,3,7,9,5,8,10D.1,2,3,5,6,7,8,9,10

19.设某数据结构的二元组形式表示为A=（D，R），D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（B）。

A.线性结构B.树型结构C.物理结构D.图型结构

20.设一棵二叉树的深度为k，则该二叉树中最多有（D）个结点。

A.2k-1B.2kC.2k-1D.2k-1

21.设用链表作为栈的存储结构则退栈操作（B）。

A.必须判别栈是否为满B.必须判别栈是否为空

C.判别栈元素的类型D.对栈不作任何判别

22.函数substr（“DATASTRUCTURE”，5，9）的返回值为（A）。

A.“STRUCTURE”B.“DATA”

C.“ASTRUCTUR”D.“DATASTRUCTURE”

23.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（C）。

A.front.next=s；front=s；B.s.next=rear；rear=s；

C.rear.next=s；rear=s；D.s.next=front；front=s；

24.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（D）。

A.top=top+1;B.top=top-1;C.top.next=top;D.top=top.next;

25.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（C）。

A.head==0B.head.next==0C.head.next==headD.head!

=0

26.在一个长度为n的顺序存储线性表中，删除第i个元素（1≤i≤n）时，需要移动（A）个元素。

A.n-iB.n-i+1C.n-i-1D.i

27.一个栈的入栈序列是a,b,c,d,e，则下列序列中不可能的出栈序列是（B）

A.b,c,d,a,eB.e,d,a,c,bC.b,c,a,d,eD.a,e,d,c,b

28.对对称矩阵进行压缩存储的目的是（C）

A.便于进行矩阵运算B.便于输入和输出

C.节省存储空间D.降低运算的时间复杂度

29.将一棵树t转化为孩子-兄弟链表示的二叉树h，则t的后根遍历是h的（C）

A.先序遍历B.后序遍历C.中序遍历D.层序遍历

30.对下面有向图给出了四种可能的拓扑序列，其中错误的是（C）

A．1,5,2,6,3,4B．1,5,6,2,3,4C．5,1,6,3,4,2D．5,1,2,6,4,3

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

1.C#语言中，接口定义的某种数据结构基本操作是定义在数据的上的。

（填：

A.逻辑结构;B.物理结构）（A）

2.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

删除一个元素时平均移动表中的个元素。

删除操作的时间复杂度为。

（n-1）/2;O（n）

3.对于一个长度为n带头结点的单链表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。

O

（1）、O（n）

4.有模式串T=“ADABCADADA”,在与目标串进行匹配时，i,j分别是指向目标串和模式串进行比较字符的指针，当匹配进行到i=19,j=7时出现了不匹配。

则要进行指针回溯再进行下一次匹配，请问按照KMP算法下一次匹配开始时的i=和j=。

按BF算法进行其下一次匹配开始时的i=和j=。

Next[j]-1001001232答：

KMP算法：

i=19;j=2BF算法：

i=13;j=0

5.确定矩阵A[100,100]中元素a[0],[0]和a[99],[99]的值的时间复杂度是分别是

和？

O

（1）；O

（1）

6.确定有n个顶点的以邻接矩阵存储的图中有多少条边的时间复杂度是？

O（n2）

7.一有100个顶点的无向图以行序为主序存储其邻接矩阵A[100,100]上三角的元素于数组B[k]中。

求矩阵元素A[70,50]在数组B[k]中的位置，即k=；3744

8.若A[50,50]为上三角矩阵，则A[45,30]存储在数组B[k]中，则k=。

1275

9.具有20个结点的二叉树最小高度为。

5

10.设森林F中有四棵顺序树：

T1、T2、T3、T4，它们的结点个数分别为N1、N2、N3、N4，与森林F对应的二叉树根结点的左子树上的结点数是；右子树上的结点数是。

N1-1；N2+N3+N4，

11.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。

e2e

12.后缀算式923+-102/-的值为__________。

中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。

-134X*+2Y*3/-

13．已知有向图如下所示，其中顶点A到顶点C的最短路径是；

最短路径的长度是_________。

（A,D,E,C）35

14设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为___________________________;______________________________（设结点中的两个指针域分别为llink和rlink）。

P.llink.rlink=p.rlink;p.rlink.llink=p.llink

15.设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。

50，51

16.分块查找时要求数据按块有序，并建立索引表，索引记录至少需要包括每块的_____________________和___________________等信息,以便在查找时，定位所在的块。

最大关键码,起始位置

17．一组初始记录关键字（十进制表示）序列为（55，63，44，38，75，80，31，56），按最低位基数优先排序算法进行排序，完成第一趟分配和收集后的结果为___________________________。

（80，31，63，44，55，75，56，38）

三、综合题（共8小题，共28分）

1.已知广义表如下：

A=（B,y）；B=（x，L）；L=（a，b）。

要求：

（3分）

（1）写出下列操作的结果：

tail（A）=______；（1分）head（B）=_________。

（1分）（y）x

（2）请画出广义表A对应的图形表示。

（1分）

2.在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。

（2分）

A01234567

data

60

50

78

90

34

40

next

3

5

7

2

0

4

1

线性表为：

（78，50，40，60，34，90）

3.请画出下图的邻接矩阵和邻接表。

（4分）

1.邻接矩阵：

邻接表如下：

4.已知一个图的顶点集V和边集E分别为：

V={1,2,3,4,5,6,7};

E={（1,2）3,（1,3）5,（1,4）8,（2,5）10,（2,3）6,（3,4）15,

（3,5）12,（3,6）9,（4,6）4,（4,7）20,（5,6）18,（6,7）25};

用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。

（4分）

用克鲁斯卡尔算法得到的最小生成树为：

（1,2）3,（4,6）4,（1,3）5,（1,4）8,（2,5）10,（4,7）20

5.设一组初始记录关键字序列为（45，80，48，40，22，78），则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。

（4分）

（22，40，45，48，80，78），（40，45，48，80，22，78）

（4分）6．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=Kmod7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

0

1

2

3

4

5

6

（2）求出在查找每一个元素概率相等情况下查找成功时的平均查找长度。

H（36）=36mod7=1;H１（22）=（1+1）mod7=2;….冲突

H（15）=15mod7=1;….冲突H2（22）=（2+1）mod7=3;

H１（15）=（1+1）mod7=2;

H（40）=40mod7=5;

H（63）=63mod7=0;

H（22）=22mod7=1;….冲突（2分）

（1）（1分）

0

1

2

3

4

5

6

63

36

15

22

40

（2）ASL=

（1分）

7.设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。

（3分）DEBCA

8.假定用于通信的电文仅由8个字母a，b，c，d，e，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。

试为这8个字母设计Huffman编码，并画出Huffman树及该电文的总码数。

（4分）

解：

其huffman编码为（1分）

a

b

c

d

E

f

g

H

0100

10

0000

0101

001

011

11

0001

电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=253（1分）

Huffman树：

（2分）

98

3959

2336

1722

7101111

3456

四．算法题（共3小题，共12分）

1.已知用有序链表存储整数集合的元素。

阅读算法f30，并回答下列问题：

intf30（LinkListha,LinkListhb）

{//LinkList是带有头结点的单链表

//ha和hb分别为指向存储两个有序整数集合的链表的头指针

LinkListpa,pb;

pa=ha.next;

pb=hb.next;

while（pa&&pb&&pa.data==pb.data）

{pa=pa.next;

pb=pb.next;

}

if（pa==NULL&&pb==NULL）return1;

elsereturn0;

}

（1）写出执行f30（a,b）的返回值，其中：

a和b分别为指向存储集合

{2，4，5，7，9}和{2，4，5，7，9}的链表的头指针；（2分）

（2）简述算法f30的功能；（2分）

答案：

（1）.1

（2）.判断两个整数集合是否完全相同（个数相同，对应位置上的数字相等），若相当等返回1不等返回0

2.下面是单链表的两种定义方法，分别写出两种定义方法下的求单链表的长度的算法

publicintGetLength（），并指出算法的时间复杂度。

（5分）

（1）定义方法一：

publicclassLinkList:

IListDS

{privateNodehead;//单链表的头引用

intlength;//单链表长度

//头引用属性

publicNodeHead

{get{returnhead;}

set{head=value;}}

//构造器，初始化单链表

publicLinkList（）

{head=null;}

}

（2）定义方法二：

publicclassLinkList:

IListDS

{privateNodehead;//单链表的头引用

//头引用属性

publicNodeHead

{get{returnhead;}

set{head=value;}}

//构造器，初始化单链表

publicLinkList（）

{head=null;}

}

（1）

publicintGetLength（）

{

returnlength;（1分）

}时间复杂度为O

（1）（1分）

（2）

publicintGetLength（）

{Nodep=head;（1分）

intlength=0;

while（p!

=null）

{++length;

p=p.Next;（1分）

}

returnlength;

}时间复杂度为O（n）（1分）

4、下面是链队列的出队列操作的算法，横线处是否缺少了语句？

若不缺少语句请说明理由，若缺少请补充所缺语句，并说明所补充语句的作用。

（3分）

publicTOut（）

{if（IsEmpty（））

{Console.WriteLine（"Queueisempty!

"）;

returndefault（T）;}

Nodep=front;

front=front.Next;

（1分）

（1分）

--num;

returnp.Data;

}

答案：

if（front==null）（1分）

{rear=null;}（1分）

当出队列的是该链队列的最后一个元素时，解除该结点的尾引用，以便于自动垃圾回收，从而提高算法的空间效率。

（1分）