企业官网建设流程全解析

数据结构（本）试题一

一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）

1. 数据结构中，与所使用的计算机无关的是数据的（ D ）。

A. 存储结构 B. 物理和存储结构

C. 物理结构 D. 逻辑结构

2．在数据结构中，从逻辑上可以把数据结构分为（ D ）。

A.动态结构和静态结构 B.紧凑结构和非紧凑结构

C.内部结构和外部结构 D.线性结构和非线性结构

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

A. i B. n-i-1

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

4． 设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ D )可使其成为单向循环链表。

A. head = p; B. p=head;

C. p->next = NULL ; D. p->next=head;

5． 一个栈的进栈序列是10，20，30，40，50，则栈的不可能输出序列是（ B ）（进栈出栈可以交替进行）。

A．10,20,30,40,50 B．40,30,50,10,20

C．40,50,30,20,10 D．50,40,30,20,10

6．在一个栈顶指针为top的链栈中删除一个结点时，用 x保存被删结点的值，则执行（ D ）。

A．x=top;top=top->next;

B．x=top->data;

C．top=top->next; x=top->data;

D．x=top->data; top=top->next;

7．判断一个顺序队列sq（最多元素为m）为空的条件是（ C ）。

A．sq->rear-sq->front== m

B．sq->rear-sq->front-1= = m

C．sq->front==sq->rear

D．sq->front==sq->rear+1

8．串函数Strcat（a,b）的功能是进行串（ D ）。

A．比较 B．复制

C．赋值 D．连接

9．稀疏矩阵采用压缩存储的目的主要是（ D ）。

A．表达变得简单

B．对矩阵元素的存取变得简单

C．去掉矩阵中的多余元素

D．减少不必要的存储空间的开销

10. 深度为5的二叉树至多有（ C ）个结点。

A. 16 B. 32

C. 31 D. 10

11. 如图所示二叉树的中序遍历序列是（ B ）。

A. abdgcefh B. dgbaechf

C. gdbehfca D. abcdefgh

12. 一个具有n个顶点的无向完全图包含（ C ）条边。

A．n（n-1） B．n（n+1）

C．n（n-1）/2 D．n（n+1）/2

13. 图的深度优先遍历算法类似于二叉树的（ A ）遍历。

A．先序 B．中序

C．后序 D．层次

14. 在有序表{1，3，8，13，33，42，46，63，76，78，86，97，100}中，用折半查找值86时，经（ B ）次比较后查找成功。

A．3 B．4

C．6 D．8

解析：

第一次：mid=(1+13)/2=7

第二次：mid=(8+13)/2=10

第三次：mid=(11+13)/2=12

第四次：mid=(11+11)/2=11

15. 依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ D ）。

A. 插入排序 B. 交换排序

C. 选择排序 D. 归并排序

二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）

1. 数据元素可以有一个或多个数据项组成。(√)

2．数据结构中,元素之间存在多对多的关系称为树状结构。(×)

3．设有一个不带头结点的单向循环链表，结点的指针域为next，指针p指向尾结点，现要使p指向第一个结点，可用语句p=p->next;。 (√)

4．要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next，可执行 p->next=s; s->next= p->next；的操作。(×)

5. 链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。(√)

6. 在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。(×)

7. 一个递归算法不必包括递归终止条件。(×)

8．空串的长度是1。(×)

9. 一个广义表((a),((b),c),(((d))))的长度为3，深度为4。(√)

10．如果结点A有3个兄弟，而且B是A的双亲，则B的度是4。(√)

11. 哈夫曼树只存在着双支结点，不存在单支结点。(√)

12. 无向图的邻接矩阵一定是对称的。（√）

13. AOV网拓扑排序的结果是惟一的。（×）

14. 折半查找的前提条件是，查找表中记录相应的关键字值必须有序或者部分有序。(×)

15. 对16个元素的序列用冒泡排法进行排序，通常需要进行15趟冒泡。(√)

三、综合应用及程序设计题（每小题5分，共25分）

1．设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印出来，并把其中之一从链表中删除，填写程序中的空格。(A)

prep=head;

p=prep->next;

while(p->data!=prep->data)

{ prep=p;

____①____;

}

printf(“%d”, p->data);

prep->next=____②____;

A. ①p=p->next ②p->next B. ①prep->data ②p->next

C. ①p->next ②p=p->next D.①p->next ②p->data

2．设SeqStack为顺序栈，写出下列程序段执行后的结果。(A)

SeqStack S;

InitStack(S);

Push(S,3);

Push(S,4);

Push(S,5);

int x=Pop(S)+2*Pop(S);

Push(S,x);

int i,a[4]={5,8,12,15};

for (i=0;i<4;i++) Push(S,a[i]);

while(!StackEmpty(S)) Printf(“%d “,Pop(S));

执行后的输出结果为：__________________。

1. 15 12 8 5 13 3
2. 3 5 8 12 13 15
3. 15 13 12 8 5 3
4. 15 12 13 3 8 5

3．以下程序段执行后，c的值为（ A ）。

char *a[5]={“12378”,”1237”,”1236789”,”1237”,”123708”}

int i,c=0

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

if (strcmp(a[i],”1237”)==0) c++;

A. 2 B. 5

C. 0 D. 1237

4． 以1，2，3 ，6，7，8作为叶结点的权，构造一棵哈夫曼树是如下哪个图？（ B ）

5．以下直接插入排序算法对存放在a[0],a[1],···,a[n-1]中，长度为n的记录序列按关键字key由小到大排序，完成程序中空格部分。(C)

void disort (NODE a[ ], int n)

{ int i,j;

NODE temp;

for (i=1;i<n;i++)

{ temp=a[i];

j=i-1;

while ( j>=0&&temp.key<a[j].key)

{ a[j+1]=a[j];

_______;

}

a[j+1]=temp;

}

}

A. j++ B. i++

C. j-- D. i--

解析：这题根据推断就可判定选j--，因为while条件中有j>=0，如果循环中没有让j减小的操作，则会j>=0这个判断没有意义