山东财经大学成人高等教育期末考试-算法与数据结构-17专科计算机复习资料

算法与数据结构17专科计算机复习资料

一、单选题

在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行

（B）。

A.HL=p;p->next=HL;B.p->next=HL->next;HL->next=p;

C.p->next=HL;p=HL;D.p->next=HL;HL=p;

若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元

素.A.nB.n-1C.n+1D.不确定

下述哪一条是顺序存储方式的优点？（A）

A.存储密度大B.插入和删除运算方便

C.获取符合某种条件的元素方便D.查找运算速度快

设有一个二维数组A[m][n],假设A[0][0]存放位置在600,阳，A[3][3]存放位置在678<⑹，

每个元素占一个空间，问A[2][3]n。）存放在什么位置？（脚注（⑹表示用10进制表示,m〉3）C

A.658B.648C.633D.653

下列关于二叉树遍历的叙述中，正确的是（D）。

A.若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最

后—个结点

B.若二窄点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后

一个结点

C.春二个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一

个结点

D.若二个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个

结点

k层‘二叉树的结点总数最多为（A）.

A.2k-1B.2K+1C.2K-1D.2k-1

对线性表进行二分法查找，其前提条件是（C）.

A.线性表以链接方式存储，并且按关键码值排好序

B.线性表以顺序方式存储，并且按关键码值的检索频率排好序

C.线性表以顺序方式存储，并且按关键码值排好序

D.线性表以链接方式存储，并且按关键码值的检索频率排好序

对n个记录进行堆排序，所需要的辅助存储空间为（C）

A.O（log2n）B.O（n）C.O（1）D.O（n2）

对于线性表（7,34,77,25,64,49,20,14）进行散列存储时，若选用H（K）=K%7

作为散列函数，则散列地址为0的元素有（D)个,

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

下列关于数据结构的叙述中，正确的是（D).

A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼

C.树是一种线性结构

D,用一维数组存储一棵完全二叉树是有效的存储方法

在决定选取何种存储结构时，一般不考虑（A）o

A.各结点的值如何B.结点个数的多少

C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便

需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。

A.单链表B.静态链表C.线性链表D.顺序存储结构

设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列

为（A

A.q=p->next；p->data=q->data；p->next=q->next；free（q）；

B.q=p->next；q->data=p->data；p->next=q->next；free（q）；

C.q=p->next；p->next=q->next；free（q）；

D.q=p->next；p->data=q->data；free(q)；

设有一个栈，元素依次进栈的顺序为A、B、C、D、E,下列(C)是不可能的出栈

序列。

A.A,B,C,D,EB.B,C,D,E,AC.E,A,B,C,DD.E,D,C,B,A

一个非空广义表的表头(D)。

A.不可能是子袤B.只能是子表

C.只能是原子D.可以是子表或原子

设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行

出队操作后其头指针front值为(D)。

A.front=front+lB.front=(front+1)%(m-1)

C.front=(front-1)%mD.front=(front+1)%m

若串S='software',其子串的数目是(B)。

A.8B.37C.36D.9

在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还

是线索化信息，若0标识树结构信息，1标识线索，对应叶结点的左右链域，应标识为

(D)。

A.00B.01C.10D.11

以下说法错误的是(B)o

A.散列法存储的思想是由关键字值决定数据的存储地址

B.散列表的结点中只包含数据元素自身的信息，不包含指针

C.负载因子是散列表的一个重要参数，它反映了散列表的饱满程度

D.散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。

设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速

排序的结果为(C)«

A.2,3,5,8,6B.3,2,5,8,6

C.3,2,5,6,8D.2,3,6,5,8

二、填空题

了前程序段的时间复杂度为—0(22)________

product=1;

for(i=n;i>0;i—)

for(j=i+l;j<n;j++)

product*=j;

若以邻接轴阵表示看向图，则邻接矩阵上第i行中非零元素的个数即为顶点vi的出度。

假定一棵树的广义表表示为A(D(E,G),H(I,J)),则树中所含的结点数为7

个，树的深度为2,树的度为2。

后缀算式79230+-42/*的值为94。中缀算式(3+X*Y)-2Y/3

对应的后缀算式为—3XY*+2Y*3/-o

在一个具有10个顶点的无向完全图中，包含有45条边，在一个具有n个顶点

的有向完全图中，包含有____n(nzl)条边。

数据的逻辑结构被分为集合结构线性结构树结构和图结构四种。

一个算法的时间复杂度为(3n3+2000nlog2n+90)/n2,其数量级表示为0(n)一。

对于一个长度为n的单链存储的队列，在表头插入元素的时间复杂度为0(1),在表

尾插入元素的时间复杂度为0(1)。

假定一个线性表为(12,17,74,5,63,49,82,36),若按Key/4条件进行划分，使得同一余

数的元素成为一个子表，则得到的四个子表分别为(12,36)(17,5,49)(74,

82)和(63)。

对一棵B_树进行删除元素的过程中，若最终引起树根结点的合并时，会使新树的高度比原

树的高度减少1(或减少)。

在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为—O(nlog2n)______,整

个堆排序过程的时间复杂度为—O(nlog2n)_

空串的长度是0.；空格串的长度是空格的戮耳.。

在一棵度为3的树中，度为-2的结点个数是1,国为0的结点个数是6,则度为4.的结点

个数是2

在串S=Structure7'中，以t为首字符的子串有12个。

在线性表的散列存储中，装填因子a又称为装填系数，若用m表示散列表的长度，n表示待

散列存储的元素的个数，则a等于一n/m_o

当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的，时回复圣封=

在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作存储密度。

在一棵高度为5的理想平衡树中，最少含有个结点，最多含有结点。

在树中，一个结点的直接后继结点称为该结点的孩子(或子)结点____________o一个

结点的直接前趋结点称为该结点的—跖亲(或父)结点。

栈顶的位置是随着—进栈了口出栈操作而变化的。

三.判断题

二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩

子的殖。(X)

循环链表不是线性表。(X)

对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。

(X)

具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。(V)

对任何数据结构链式存储结构一定优于顺序存储结构。(义)

广义表(((a),b),c)的袤又是((a),b),表尾是(c)。(V)

用一一个维广义数卖组的存表储头主版攵杲树一时个，总广是义以表前c(序遍X历顺)序存储结点。(X)

强连通图的各顶点间均可达。(V)

在平衡二叉树中，任意结点左右子树的高度差(绝对值)不超过1。(V)

四、操作题

假设以数组se哭［m］存放循环队列的元素,设变量rear和quelen分别指示循环队列中

队尾元素的位亶和元素的个数。

(1)写出队满的条件表达式;

(2)写出队空的条件表达式；

(3)浚m=40,rear=13,quelen=19,求队头兀素的位置;

(4)写出一般情况下队头元素位置的表达式。

答：(1)quelen==m

(2)quelen==0

(3)(13-19+40)%40=34

(4)(rear-quelen+m)%m

设无向图G(所下鼠所示)，要求给出该图的深度优先和广度优先遍历的序列并给出该图的

最小生成树。

答:深度优先遍历序列：125364,广度优先遍历序列：123456,最小生成树T的边集为£={(1,

4),(1,3),(3,5),(5,6),(5,6)}

设一组有序的记录关键字序列为(13,18,24,35,47,50,62,83,90),查找方法用二

分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。

答：ASL=91*l+2*2+3*4+4*2)=25/9

已知一棵二叉树的中序序列为ABCDEFG,层序序列为BAFEGCD,请画出该二叉树。

答：1)(A),B,(CDEFG)

2)(A),B,((CDE),F,(G))

B

AF

EG

C

\

D

五.阅读算法

现面算法的功能是什么？

voidABC(BTNode*BT)

(

ifBT{

cout«BT->data«";

ABC(BT->left);

ABC(BT->right);

答：前序遍历链式存储的二叉树。

在下面的每个程序段中，假定线性表La的类型为List,元素类型ElemType为int,并假定

每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。

(1)InitList(La);

Inta[]={100,26,57,34,79);

For(i=0;i<5;i++)

Insert(La,a[i]);

TraverseList(La);

(2)DeleteFront(La);

InsertRear(La,DeleteFront(La));

TraverseList(La);

(3)ClearList(La);

For(i=0;i<5;i++)

InsertFront(La,a[i]);

TraverseList(La);

答：(1)La=(26,34,57,79,100)

(2)La=(57,79,100,34)

(3)La=(79,34,57,26,100)

六.算法设计题

试写出在链式存储结构上建立一棵二叉树的算法，以及判断一棵二叉树是否是二叉排序树

的算法

答：在解式存储结构上建立一棵二叉树的算法。

typedefchardatatype;

typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;

voidcreatebitree(bitree*&bt)

(

charch;scanf(n%cn,&ch);

{bt=O;return;}

bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;

createbitree(bt->lchild);createbitree(bt->rchild);

判断一棵二叉树是否是二叉排序树的算法。

intminnum=-32768,flag=l;

typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;

voidinorder(bitree*bt)

(

if(bt!=O)

{inorder(bt->lchild);if(minnu