电大-数据结构-期末考试历届真题考试试卷

本题目为历年电大真题试卷，对于期末考试具有极大意义。祝所有考生，考试顺利通过!

13.如图1所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种

顶点序列为（）.•

A.abecdfgB.acfebgd

C.aebcfgd^Sjaedfcgb

14.字符串“DABcdabcd321ABC”的子串是（）.

少cd32"B.“ABcD”

C.“aBcd”D.“321a”

15.如图2所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点

序列为（）•

A^bcdfgeB.abcdfeg

C.acbfedgD・abcfgde

1.同一种逻辑结构（〉.

A.只能有唯一的存储结构可以有不同的存储结构

C只能褒示某一种数据元素之间的关系B以上三种说法均不正确

2.链表所具备的特点是（）.

A.可以随机访问任一结点

R占用连续的存储空间

©插入II除元素的操作不病要移动元素结点

D.可以通过下标对健表进行直接访问

3.数据的物理结构（).

A.与数据的逻辑结构无关R仅仅包括数据元素的表示

G只包括数据元素间关系的表示（ED包括数据元素的表示和关系的亵示

4.线性结构中数据元素的位置之间存在（）的关系.

一对一

R一对多

Q多对多

n每一个元素都有一个直接前驱和一个直接后继

5.以下表中可以随机访问的是（）.

A.单向链表R双向修表

C单向循环徒表序表

6.算法的时间复杂度与（）有关.

A.所使用的计算机R与计算机的操作系统

B与算法本身D与数据结构

设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为（）

A.n—i+1

Qn-i-1Dii

8.在一个单货表中,p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后

继，现要删除q所指结点，可用的语句是（）.

q->next

l>next=q->next

9.从一个栈顶指针为top的摄栈中射除一个结点时，用变量x保存被副结点的值，则执

行（）•

C^A]xss=top->dataitop=top->next；Bx=top->dataj

C.top=top->next।x=top->dataiD.top==top->nextix=data»

10.在一个集队中，假设f和r分别为队头和队尾指针，则射除一个结点的运算为（）.

A.r=f->nextjB.r=r->nextj

qy=f->nextD,f=r->next；

11.一个栈的进栈序列是a,b,ache,则栈的不可能输出序列是《）（进栈出栈可以交

替进行）.

UadceabB.edcba

GdecbaD.abcde

12.有一个长度为10的有序表,按折半查找对该装进行查找，在等概率情况下行找成功

的平均比较次数为（）.

929/10

A.26/10

G29/9D.31/10

13.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元*进行

比较（要求比较次数尽■少），然后将其放入巳排序序列的正确位♦的方法是（）.

A.胃泡a直接插入

O折半插入D,选界排序

14.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到

一维数组B中（数组下标从1开始），则矩阵中元素儿，在一维数组B中的下标是（）.

Q>33R32

Q85D.41

15.在一个无向图中，所有顶点的度数之和等于边数的（）倍・

A.3R2.5

Q1.5（^2

1.在C语言中，顺序存储长度为3的字符中，需要占用（）个字节.

AA.4B.3

C6D.12

2.审函数StrCa“a,b）的功能是进行串（）.,A-3A4.HS.A

DA.比较B.复制

C.赋值D.连接

A3.一棵TTn个结点采用链式存储的二叉树中，共有（）个指针域为空。

A.n+1B.n

C.n-1D.n—2

4.设一棵哈夫曼树共有n个非叶结点，则该树有（）个叶结点.

BA.nB.n+l

Z\5.Cn—1D.2n

从一个栈顶指针为lop的链栈中删除一个结点时,用变fitx保存被删结点的值，则执

行（）•

A.x=top->dataitop=top->nextB.x=top->data

C.top=top->next；x~top->dataD.top=top->next；x-data

6.一棵完全二叉树共有5层，且第5层上有六个结点，该树共有（）个结点.

A.30B.20

C.21D.23

[J7.在一个无向图中，所有顶点的度数之和等于边数的（）倍.

A.3B,2.5

C.1.5_D_2

8.已知如图1所示的一个图，若从顶点V1出发，按深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）.

V,vvvvvvv

O24t536r

B.V,V2V4VsVaV3V<V,

C.v1v2v4v8viv.v<vT

D・VM5V2VMV,

9.已知如困2所示的一个图，若从顶点a出发,按广度优先搜索法进行遍历，则可能得到

的一种顶点序列为（）・

A.abcedf

abcefd

C.aebcfd

D.acfdeb

10.对二叉排序树进行（）遍历，可以使遍历所得到的序列是有序序列.

A.按层次B.后序

中序D.前序

11.在有序表｛2,4,7,14,34,43,47,64,75,80,90,97,120｝中，用折半查找法查找值80

时，经（）次比较后查找成功.

A.4".B-2

丸--

C.3…D.5

12.有一个长度为9的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的

平均比较次数为（）.7.D8.A9.B10.C

A.25/1011.B12.B

C.20/9D.17/9

1135

13.C14.B15.D

13.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行

比较（要求比较次数尽量少），然后将其放入巳排序序列的正确位置的方法是（）・

A.口泡

B.直接插入

_Q折半吗匚

D.选择排序

14.一组记录的关键字序列为（46,79,56,38,40,84）,利用快速排序，以第一个关键字为

分割元素，经过一次划分后结果为（）•

A.40,38,46,79,56,84

B._40,3乏46,56,79,84

C.40,38,46,84,56；冏

D.38,40,46,56,79,84

15.排序方法中，从尚未排序序列中挑选元素,并将其依次放入已排序序列（初始为空）的

一端的方法，苏为《）排序.

A.归并

B.插入

G快速

.3」选择

1.在数据结构和算法中，与所使用的计算机有关的是（）・

A.数据元数间的抽象关系Q）数据的存储结构

C.算法的时间复杂度D.数据的逻辑结构

2.对顺序表，以下叙述中正确的是（）.

®用一组地址连续的存储单元依次存放线性表的数据元索

B.各个数据元素的首地址是连续的

C.数据元素不循随机访问

D.插入操作不需要移动元素

3.设有一个长度为25的顺序表，要删除第10个元素（下标从1开始），需移动元素的个

数为（）.

A.9B.10

Q15D.16

4.设单向链表中，指针p指向结点A,若要删除A的直接后继，则所需修改指针的操作为

（）.

p->next=p->ncxt->nextjB.p-p->nextj

Qp=p->ncxt—>next；D♦p->next=p；

5.元素1,3,5"按顺序依次进栈，按该栈的可能摘出序列依次入队列，该队列的可加输

出序列是（）.（进栈出栈可以交替进行）

^7,5,3,1B.7,3,1,5

C.7,5,1.3D.5,1,3,7

6.对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（）.

A.p"top->nextjtop=top-*nextjB.p->next=top；

•j'P",>next«top；top=spjD.top=p.

7.设有一个18阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（）.

（矩阵中的第1个元素是

A.a^.iB.810.«

C.a«.：a«.s

8.设有一个17阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则矩阵中元素a1。,,在一维数组B中的下标是（）.

（矩阵中的第1个元素是斯」）

A.45,B.18

?51D.53

9.申函数5[©^（R8^「人1^口”）的值为（）.

A.0B.-1

^31D.3

10.一棵采用链式存储的二叉树中有n个指针域为空，该二叉树共有（）个结点.

A・n+1B.n

n-1D.n-2

U.设一棵哈夫曼树共有n个非叶结点，则该树有（）个结点.

A.2nB.2n+2

C.2n-102n+l

12.一棵结点数3lVnV4O的完全二叉树•最后一层有4个结点，则该树有（）个叶结

点.

口.18B.17

Q36D.35

13.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）・

C.acbcfdD.aedfbc

14.一组圮录的关键字序列为（46,20,30,79,56,38,40,84,90,110）,利用快速排序，以第

一个关键字为分割元素，经过一次划分后结果为（）.

A.20,30,40,38,46,79,56,84,90,100

40,20,30,38,46,56,79,84,90,110

C.30,20,40,38.46,84,56,79,90,100

0.20,3038,40,46,56,79,84,90,100

15.一组记录的关键字序列为（75,63,95,80,53,45,38,20）,利用堆排序（堆顶元索是最

大元素）的方法建立的初始堆为（）.

95,80,75,63,53,45,38,20

B.95,63,75,80,53,45.38,20

C.95,80,45,63,53,75,38,20

D.95,80,75,20,53,45,38,63

l.结构中的元素之间存在•对多的关系是（）.

A.集合a线性结构

Cc有D.图状结构

2.对不带头结点的单向链表,判断是否为空的条件是（“设头指针为head）.

A.head-3«NULLB.head-2>next==NULL

C.head->next~~hcadD.head-NULL

D3.在一个不带头结点的单■循环链表中.p、q分别指向表中第一个结点和尾结点，现要删

除第一个结点，可用的语句是（

A.p=q->next；p=p~>next；Rp->nexLq$p=p->next；

C.p->next~q->next；q=piD.p=p->next；q->nexLp；

34.一个栈的进栈序列是1.2,3,4,5,则栈的不可能输出序列是（）（进栈出栈可以交替

进行）.

A.12345B.43512

C.45321D.54321

一个队列的入队序列是2.4,6,8,按该队列的输出序列使各元素依次入枝.该栈的可能

输出序列是（

A.8,6.4.2B.6,2,4,8

C.8,4,2,6D.8,2.4,6

1033

l.C2.A3.D4.B5.A

6.B7.D8.B9.A10.A

g6.在一个蜷队中,假设f和r分别为队头和队尾指针•已生成一个结点p,要为结点p赋

值x,并入队的运算为（）,

A.p—>data=x；p—>next~NULL；f->ncxt=p；f—pt

Rp->data=x；p->next=NULL；r->next=p；r=p；

C.p->data=x：p->next=r；r=si

D.p—>data=-x；p->next~f；f-sj

/^7.设有一个25阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储

节匚维数组B中（数组下标从1开始），则矩阵中元素.&工在一维数组B中的下标是（）.

（矩阵中的第1个元素是曲.】）

A.34B.14

G26D.27

8.以下程序段的结果是c的值为(),

Schara[5]="1236789”，int«p=cw0»

while(*p++)c-h+；

A.8.a7

.C.10D.12

A%一棵有23个结点，采用链式存储的二叉树中，共有（）个指针域为空.

c\A.24B.25

八G231）,45

/Aio.在一棵二又树中，若编号为i的结点是其双亲结点的左孩子，则双亲结点的顺序编号

为《兀

A.i/2R2i-l

C2i+1D.i/2-1

11.设•棵哈夫城树共有2n+l个叶结点，则该树有（）个叶结点.

A.n-1

C.n*I

「12.已知如图I所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则可能得

到的一种顶点序列为（）.

A.abecdfB.acfebd

C.acbcfdD.aedbfc

13.已知如图2所示的一个图•若从顶点B出发，按r度优先法进行遍历,则可能得到的

一种顶点序列为（）.

A.BADEHCFG

B.ADEHCGF

C.BADECHFG⑶C14.B15・B

GD.BADEHCFG

2^14.一组记录的关键字序列为《46,38.56,40,79,84）,利用快速排序，以第一个关键字为

分割元素，经过一次划分后结果为（）.

A.40,38,46,79,56,84

B.40.38,46,56,79,84

C.40,38,46,84,56,79

、D.38.40,46,56,79.84

515.在有序表（21,23,28,33,43,45,46,73.77,78,89,99,106）中，用折半查找值43时,经

（）次比较后左找成功。

A.6B.3

C.8D.4

1.i种逻辑结构在存储时（）.

A.只要存M数据元索间的关系B.只能采用•种存储结构

Q可采用不同的存例结构【）.只要存储数据元素的值

2.对链表，以下叙述中正确的是（）.

4不能随机访问任一结点

B.结点占用的存储空间是连续的

C.插入删除元素的操作一定要移动结点

D.可以通过下标对链表进行直接访问

3.线性表在存储后••如果相关操作是：要求已知第i个结点的位置访问该结点的前驱结

点，则采用（）存储方式是不可行的.

。单链表

R双钱表

C.小循环捱衣D.顺序表

4.栈和队列的共同特点是（）.

A.都是先进后出B.元家都可以随机进出

G只容许在端点处插入和删除元素

D.都是先进先出

5.元索2,4,6,8按顺序依次进栈，按该枝的可能输出序列依次入队列•该队列的可传输

出序列是（）（进栈出栈可以交替进行）.

A.8.6,2,4B.8M,2,6

C.6,2,4,8U^8,6,4,2

6.在一个不带头结点的链队中•假设f和r分别为队头和队尾指针,则从该对列中删除一

个结点并把结点的值保存在变量x中的运算为（）.

A.xr->data；r=r-*next»B.r-r->next<x—r-^data

D.f=f-*next?xf-*data

7.设有一个20阶的对称矩阵A.采用压缩存储的方式，将其卜一三角部分以行序为行序存储

到一维数组B中（数组下标从】开始），则数组中第38号元素对应于矩阵中的元素是（）.

（矩阵中的第1个元素是血，）

A.dio.aB«a,.6

a,,?D.a*.s

8.在C语言中，分别存储"S"和'广，各需要占用（）字节。

A.一个和两个B.两个

C.一个J两个和一个

9.一棵有n个结点，采用链式存储的二叉树中,共有7）个指针域被有效使用（即指针

域为非空）.

A.n+】B.n

Qn-1D.n-2

10.在一棵二叉树中，若编号为i的结点存在双亲结点,则双亲结点的喉序编号为（）・

A.i/2.0口/2向下取整

C.2i4-lD.i+2

11.设一棵哈夫曼树共有2n+l个结点，则该树有（）个非叶结点.

nB.n+I

C.n~]D.2n

12.一棵完全二叉树共Tf1层.且第1层h有2个结点•该树共彳“）个非叶子结点

（根为第一层）.

A.5l

（：.3D.9

13.如图1所示的一个四•若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的

•种顶点序列为（）・

A.abedfcB.acfebd

^^aebcdfD.aebcfd

14.一组记录的关键字序列为（56,30,89,66.48,30.94,87,100）.利用快速排序，以第一

个关键字为分割元素，经过一次划分后结果为（）.

A.30,50,48.56,66,89,94,100,87

@50.30,48,56,66,89,94,87,100

C48,30,50,56,66.89,94,87.100

D.50,30,48,66,56,89.94.87,100

15.线性表以（）方式存储，能进行折半查找.

A.关键字有序的鞋接R顺序

O关键字有序的峨序D.数组

81.卜面关于线性表的叙述中•错误的是（）.

A.线性表采用顺序存储，必须占用一片连续的存储空间

B.线性表采用顺序存储，进行插入和删除操作,不需要进行数据元索间的移动

C.线性表采用链式存储，不必占用连续的存储空间

D.线性表采用链式存储,进行插入删除操作，不需要移动元素

B2.设有一个长度为28的顺序表，要在第12个元素之前插入一个元素（也就是插入元素

作为新表的第12个元索）,则移动元素个数为（）。

A.12B.17

D.11

d3.元素2,4,6,8按顺序依次进栈，则该栈的不可能输出序列是（）（进栈出栈可以交替

进行）.

A.A642

CC.4,2,8・6D.8.6,2,4

B4.对一个栈顶指针为lop的链栈进行出栈操作，用变量c保存栈顶元素的值，则执行（）.

A.e=top->nextjtop->data=e；B.c-top->data；top=top>nexi；

C.top'=top->>nextje=top->data；D.top=top->next;e=dataj

843

l.B2.B3.D4.B

5.D5.在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点•并作为

第一个结点，可执行（）.

A.rear-*next=s；s-*next=rear-*next

B.rear-*ncxt~s-»ncxti

C.rear=s-*next

D.s-*next~rear-*next）rcar-*next~sj

6.B6.设有一•个28阶的对称矩阵A（矩阵的第一个元素为aj）,采用氏缩存储的方式，将其

下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）•则数组中第40号元素而

应于矩阵中的元索是（）.

A.&i«,tB.,

Ca*.sD.a,.5

7.A7.数组a经初始化char圻]="Engli$h-a口[中存放的是（）.

A.字符nB.字符E

C."n"D."E"

8.C8,程序段chara[]="English"；char*p=a；intn=。；while（*p!='\0'）｛n++；P++；｝

结果中,P指向（）

A.字符hRa

C，字符串的结束符D.7

9.D9,在-♦棵二叉树中，编号为17的结点的双亲结点的的顺序编号为（）.

A.34B.7

C.9D.8

10.C10.设棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共布"20

个指针域为空.则该树共有（）个非叶子结点

A.21B.22

C9D.10

11.已知如图I所示的个图，若从顶点V0出发，按深度优先法进行遍历,则可能得到的

A.VcVlV2V4V,V6V3V6VfRVCVMKVSVHVMVY

C.VoVMVMVaVMV,D.V。V|VMV7V2V4V5Vli

12.B12.对（）进行中序遍历，可以使遍历所得到的序列是刈■序序列。

A.完全二叉树B.二又排序树

C.满二又树排D.哈夫曼树

13.A13.有一个长度为7的有序表，按折半查找对该表进行宜找,在等概率情况下查找成功的

平均比较次数为（）.

A.17/7B.18/7

C.21/71).20/7

14.C14.排序方法中，从未排序序列中挑选元索,并将其依次放入已排序序列（初始为空）的一

端的方法•称为（）排序。

A.堆B.冒泡

C.选择D.快速

15.R15.一组记录的关键字序列为（12,45,221,6,503利用快速排序，以第一个关键字为分割

元索.经过一次划分后结果为（）.

A,6,4,12,45,22.5086,4,12,22,45,50

06,4,12,50,22,45D.4,6.12,22,45,50

845

L对稀疏矩阵进行压缩存储，可采用三元组表，~个10行8列的稀跋矩阵A共有73个

零元索，其相应的三元组表共有《）个元素•

A.8B.80

D.10

2.字符串（）是“心。£1321人86»”的子串・

为“21AB”B.“abcD”

C.MaBCDwD.“321a”

3.栈和队列的共同特点是（）•

0都是操作受限的线性结构B.元素都可以随机进出

C.都超先进后出D.都是先进先出

4.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点，要为结点p所指

结点赋值x,并入队的运算为p->data=x；p—>next=NULL；（）.

A.f->next=p；f=p；£B|r->next=p；r=p1

C.r=pip—>next~nD.p->next=

5.数据结构中，与所使用的计算批无关的是数据的（）结构.

0逻辑B.存储

c.逻辑与存储D.物理

6.顺序表所具备的特点之一是（）.

（3可以随机访问任一结点B.不需要占用连续的存储空间

C.插入元素的操作不需要移动元素D.删除元素的操作不需要移动元素

7.数据元素是数据的基本单位，它（）.

A.只能有一个数据项组成

B,至少有二个数据项组成

<□可以是一个数据项也可以由若干个数据项组成

D.至少有一个数据项为指针类型

8.设有头指针为head的非空的单向链表，指针p指向其尾结点，要使该单向链表成为单

向循环链表，则可利用下述语句（）・

A.p=head；B.p=NULL：

>next=head：D.head=p»

9.在线性表的顺序结构中，以下说法正确的是（）.

A.逻辑上相邻的元素在物理位置上不一定相邻

B.数据元素是不能随机访问的

P逻辑上相邻的元索在物理位置上也相邻

【）.进行数据元案的插入、删除效率较高

10.对链友，以下叙述中正确的是（）.

《9不能随机访问任一结点

B.结点占用的存储空间是连续的

C.插入1M除元素的操作一定要要移动结点

D.可以通过下标对链表进行直接访问

11.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作

为新表的第5个元素），则移动元素个数为（）・

A.30Q31

C.5D.6

12.设有一个长度为40的顺序表，要删除第10个元素（下标从1开始）靠移动元素的个数

为（）.

A.11B.10

30D.31

13.设有一个25阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储

到一维数组B中（数组下标从1开始），则矩阵中元素a7c在一维数组B中的下标是（）.

A.25B.24

£^6D,27

14.线性表在存储后，如果相关操作中有要求：利用已知的指向某结点的指针或序号，访问

该结点的前驱结点，则采用（）的存储方式是不可行的.

P单向链表B.双向链表

C,单向循环锥表D.原序表

15.在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（）.

A.i/2.00.2»i

C.2*i+1D.i+2

1.对稀疏矩阵进行压缩存触，可采用三元的表••个有I。行的稀疏矩阵A共有97个零

元素，其相应的三元组表共有3个元素.该矩声A布工）列。

A.8B-9

C.700

2.子串“acd”在主审"abdcacdefac”中的位55是（）.

A.3

C.7D.1

3.序列12,16.8,4按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的不可能

输出序列度（）.（进栈、出栈可以交神进行）.

A.16.12.8,4XDl-8.12.16

C2D.

4.在一个不借头结点的住队中，假设1和r分别为队头和队兄指针,对该队列进行出队操

作，并把结点的值保存在变量e中•其运算为（兀

:

A.e-f—>datalr=r->next

B.e=f->data$r—>nexi=r

1^8.e=f—>data»（"（—>next

D.e=f—>data；f—>next=f

5.数据的逻辑结构在计算机内存中的表示是《）.

A.给相关变量分配存储单元Q数据的存储结构

C.数据的逻靶结恂D.算法的具体体现

6.以下说法正确的是（）.

A.线性表的链式存储结构必须占用连续的存储空间

种逻辑结构可以有不同的存储结构

C.一种逻辑结构只能有唯一的存储结构

D.线性表的顺序存储结构不必占用连续的存储空间

7.在一个单链裳中要膜除P所指结点的后继结点,可执行q=p-）桢4,和（

p->ncxt-*q~~>ncxtKp«»q->next

C.p->next=qD.p->nexi=q

8.在数据结构和算法中•与所使用的计第机有关的是《）.

A.数据元数间的抽象关系。