2024年4月30日发(作者：)

试卷三

一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母

标号填入题干的括号内。每小题2分，共30分)

1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（ ）

A.S上的算法 B.S的存储结构

C.在S上的一个基本运算集 D.在S上的所有数据元素

2．下列说法正确的是（ ）

A.线性表的逻辑顺序与存储顺序总是一致的

B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续

C.线性表的线性存储结构优于链式存储结构

D.每种数据结构都具有插入、删除和查找三种基本运算

3．稀疏矩阵一般采用（ ）方法压缩存储。

A.三维数组 B.单链表

C.三元组表 D.散列表

4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。

A. s↑.next:=p；p↑.next=s;

B. s↑.next:=p↑.next;p↑.next:=s；

C. s↑.next:=p↑.next;p:=s;

D. p↑.next:=s;s↑.next=p;

5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是

( )。

A.110 B.108 C.100 D.120

6.下面的二叉树中，( )不是完全二叉树。

7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始堆为

( )。

A.78、47、61、33、39、80 B.80、78、61、33、39、47

C.80、78、61、47、39、33 D.80、61、78、39、47、33

8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要把一个指

针s所指的新结点作为非空双链表中q所指地点(中间结点)的直接后继结点插入到该双向

链表中，则下列算法段能正确完成上述要求的是( )

A.q->right=s; s->left=q; q->right->left=s; s->right=q->right;

B.s->left=q; q->right=s; q->right->left=s; s->right=q->right;

C.s->left=q; s->right=q->right; q->right->left=s; q->right=s;

D.以上都不对

9.由下列三棵树组成转的森林换成一棵二叉树为( )

10. for（i=0；i

for（j=0；j

c［i］［j］=0；

for（i=0；i

for（j=0；j

for（k=0；k

c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；

上列程序的时间复杂度为（ ）

A.O（m+n×t） B.O（m+n+t）

C.O（m×n×t） D.O（m×t+n）

11.设循环队列的元素存放在一维数组Q［0‥30］中，队列非空时，front指示队头元素的前

一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值为25，则rear应

指向的元素是（ ）

A.Q［4］ B.Q［5］

C.Q［14］ D.Q［15］

12.定义二维数组A［1‥8，0‥10］，起始地址为LOC，每个元素占2L个存储单元，在以

行序为主序的存储方式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储方

式下，该元素的存储地址为（ ）

+28L +36L

+50L +52L

13.采用排序算法对n个元素进行排序，其排序趟数肯定为n-1趟的排序方法是（ ）

A.插入和快速 B.冒泡和快速

C.选择和插入 D.选择和冒泡

14.设h是指向非空带表头结点的循环链表的头指针，p是辅助指针。执行程序段

p=h;

while (p->next->next!=h)

p=p->next;

p->next=h;

后（其中，p->next为p指向结点的指针域），则( )

A. p->next指针指向链尾结点 B. h指向链尾结点

C. 删除链尾前面的结点 D. 删除链尾结点

15.某二叉树的先根遍历序列和后根遍历序列正好相反，则该二叉树具有的特征是( )

A.高度等于其结点数 B.任一结点无左孩子

C.任一结点无右孩子 D.空或只有一个结点

二、填空题(本大题共13小题，每小题2分，共26分)

请在每小题的空格中填上正确答案。错填、不填均无分。

16.数据的逻辑结构通常包括集合、线性结构、____________和图状结构。

17．给定n个值构造哈夫曼树。根据哈夫曼算法，初始森林中共有n棵二叉树，经过 次

合并后才能使森林中的二叉树的数目由n棵减少到只剩下一棵最终的哈夫曼树。

18．树型结构结点间通过“父子”关系相互关联，这种相互关联构成了数据间的 关系。

19.在一个具有n个结点的单链表中查找值为m的某结点，若查找成功，则需平均比较的结

点数为____________。

20.数据表示和________________是程序设计者所要考虑的两项基本任务。

21.在循环队列中，存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素，队

尾指针指向队尾元素，那么其队空标志为rear=front，队满标志为 _________。

22.深度为k的二叉树至多有 _________个结点，最少有 _________个结点。

23．在堆排序和快速排序中，若原始记录已基本有序，则较适合选用 。

24.在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列。

25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。

26.三个结点可构成________种不同形态的二叉树。

27.设需将一组数据按升序排序。在无序区中依次比较相邻两个元素a

i

和a

i+1

的值，若a

i

的

值大于a

i+1

的值，则交换a

i

和a

i+1

。如此反复，直到某一趟中没有记录需要交换为止，

该排序方法被称为_________。

28.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为

2n个，其中________个用于链接孩子结点。

三、应用题（本大题共5小题，每小题6分，共30分）

29.已知一棵二叉树的前序序列是ABCDEFG，中序序列是CBDAEGF。请构造出该二叉树，

并给出该二叉树的后序序列。

30．有一字符串序列为5*-x-y/x+2，利用栈的运算将其输出结果变为5x-*yx+/-2，试写出该

操作的入栈和出栈过程（采用push(a)表示a入栈，pop(a)表示a出栈）。

31.已知某二叉树的顺序存储结构如图所示，试画出该二叉树，并画出其二叉链表表示。

A B C D E F G

32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列

作升序排序，并给出每一趟的排序结果。

33.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。

四、算法设计题(本大题共3小题，共14分)

34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。（4分）

35.某带头结点的单链表的结点结构说明如下： （6分）

typedef struct node1

{

int data;

struct node1 *next

}node；

试设计一个算法int copy(node *head1, node *head2)，将以head1为头指针的单链表复制到一

个不带头结点且以head2为头指针的单链表中。

36.若二叉树存储结构采用二叉链表表示，试编写一算法，计算一棵二叉树的所有结点数。（4

分）

参考答案

一、选择题（本题共30分,每题2分）

1、 C 2、B 3、C 4、B 5、B 6、C 7、B 8、C 9、A

10、C 11、B 12、D 13、C 14、D 15、A

二、填空题（本题共26分,每小题2分）

16、树状结构 17、 n-1

18、逻辑 19、 n/2

20、数据处理 21、 front==(rear+1)%n

22、2

k

-1，k 23、堆排序

24、中序 25、有序

26、5 27、冒泡排序

28、n-1

三、应用题（本题共30分，每小题6分）

29、

后序序列：CDBGFEA (3分)

B

A

E

C D

F

G

(3分)

30、push(5);pop(5);push(*);push(-);push(x);pop(x);pop(-);pop(*);push(-);push(y);

pop(y);push(/);push(x);pop(x);push(+);pop(+);pop(/);pop(-);push(2);pop(2);

32、

第1趟： [37] 38 [73 52 40 64 56 43]

第2趟： 37 38 [43 52 40 64 56] 73

第3趟： 37 38 [40] 43 [52 64 56] 73

第4趟： 37 38 40 43 52 [64 56] 73

第5趟： 37 38 40 43 52 [56] 64 73

第6趟： 37 38 40 43 52 56 64 73

31、

ROOT

A

B

∧ C

∧ D

E

∧ F ∧ ∧ G

33、

28

12 45

20 33

55

18 37

四、算法设计题（本题共14分）

34、(4分)

typedef struct node *pointer;

struct node

{

datatype data;

pointer next;

};

typedef pointer lklist;

void insert_lklist(lklist head,datatype x,int i)

{

pointer *p,*s;

p=head;

j=0;

while((p->next!=NULL)&&(j

{p=p->next;j++;}

A

B

C

D

E

F G

if(j!=i-1)

{printf("不存在第i个位置");

break();

}

else {s=malloc(size);s->data=x;

s->next=p->next;

p->next=s;}

}

35、(6分)

int copy(node *head1,node *head2)

{

Node *p,*s;

P=head1->next;

If(p!=NULL)

{

*r=malloc(size);

r->data=p->data;

head2=r;

p=p->next;

}

else

{head2=NULL;

Return(0);

}

While(p!=NULL)

{ *s=malloc(size);

s->data=p->data;

r->next=s;

r=s;

p=p->next;

}

r->next=NULL;

return(1);

}

36、（4分）

typedef char DataType;

typedef struct node

{

DataType data;

struct node *lchild, *rchild;

} BinTNode;

typedef BinTNode *BinTree;

int nodes(BinTree T)

{

int num1,num2;

if(T==NULL) return(0);

else if (T->lchild==NULL && T->rchild==NULL) return(1);

else

{

num1=nodes(T->lchild);

num2=nodes(T->rchild);

return(num1+num2+1);

}

}

试卷A

一、选择题（本题共20分，每小题1分）

1．在数据结构中，从逻辑上可以把数据结构分成 （ ） 。

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

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

2．线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( ) 。

A. 必须是连续的 B. 部分地址必须是连续的

C. 一定是不连续的 D. 连续不连续都可以

3．不带头结点的单链表 head 为空的判定条件是( ) 。

A. head == NULL B. head->next ==NULL

C. head->next == head D. head! = NULL

4．在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入

s 结点，则执行( ) 。

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

C. q->next=s; s->next=p; D. p-next=s; s->next=q;

5．从一个具有n个结点的单链表中查找其值等于 x 结点时，在查找成功的情况下，需平均

比较( )个结点。

A. n B. n/2

C. (n-1)/2 D. (n+1)/2

6．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是( )。

A. edcba B. decba C. dceab D. abcde

7．判定一个循环队列 QU（最多元素为 m0）为满队列的条件是( )。

A. QU->front==QU->rear B. QU->front!=QU->rear

C. QU->front==(QU->rear+1) % m0 D. QU->front!=(QU->rear+1) % m0

8．栈和队列的共同点是( ) 。

A. 都是先进后出 B. 都是先进先出

C. 只允许在端点处插入和删除元素 D. 没有共同点

9．数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从

首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为

( ) 。

A. SA+141 B. SA+144

C. SA+222 D. SA+225

10．广义表((a，b)，c，d)的表尾是( )。

A. a B. b

C. (a，b) D. (c，d)

11．设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放

在一维数组 B[1，n(n-1)/2]中，对下三角部分中任一元素 ai,j(i≥j)，在一维数组 B 的

下标位置k的值是（ ）。

A. i(i-1)/2+j-1 B. i(i-1)/2+j

C. i(i+1)/2+j-1 D. i(i+1)/2+j



a

1,1





a



a

2,12,2



A





............





aa...a

n,1n,2n,n



13. 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列

是（ ）。

A. acbed B. decab C. deabc D. cedba

12. 如下图所示的 4 棵二叉树中，（ ）不是完全二叉树。

14. 按照二叉树的定义，具有 3 个结点的二叉树有（ ）种。

A. 3 B. 4

C. 5 D. 6

15. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点

数至少为（ ）。

A. 2h B. 2h-1

C. 2h+1 D. h+1

16．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ） 倍。

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

17．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要（ ）条边。

A. n B. n+1

C. n-1 D. n/2

18．已知一有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算法，从顶点

v1 出发，所得到的顶点序列是 （ ）。

A. v1，v2，v3，v5，v4 B. v1，v2，v3，v4，v5

C. v1，v3，v4，v5，v2 D. v1，v4，v3，v5，v2

19. 采用顺序查找方法查找长度为 n 的线性表时，每个元素的平均查找长度为

（ ）。