数据结构与算法试题(1)

一、选择题

1. 在逻辑上可以把数据结构分成（ A ）

A. 线性结构和非线性结构 B.动态结构和静态结构

C. 紧凑结构和非紧凑结构 D.内部结构和外部结构

2. 单链表中各结点之间的地址（C ）

A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对

3. 在一个长度为n 的顺序表中向第i 个元素（0

移动（B ）个元素。

A 、n-i B、n-i+1 C、n-i-1 D、i

4. 插入和删除操作只能在一端进行的线性表，称为（C ）。

A.队列 B.线性表 C.栈 D.循环队列

5、队列是仅允许在（）进行插入，而在（）进行删除。(A )

A. 队尾，队首 B.队尾，队尾 C.队首，队尾 D.队首，队首

6. 链表适合于（A ）查找。

A.顺序 B.二分 C.随机 D.顺序或二分

7. 数据的基本单位是（A ）。

A. 数据元素 B.数据结构 C.数据项 D.数据对象

8. 下列哪个不是算法的特性（B ）。

A. 有穷性 B.可数性 C.可行性 D.确定性

9. 在表长为n 的顺序表中进行线性查找，它的平均查找长度为（B ）。 A.ASL=n B.ASL=(n+1)/2 C.ASL=n +1 D.ASL=log2n

10. 一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址

是(C ）。

A.311 B.328 C.332 D.313

11. 设front 、rear 分别为循环双向链表结点的左指针和右指针，则指针P 所指的元素是双

循环链表L 的尾元素的条件是（D ）。

A.P==L B.P->front==L C.P==NULL D.P->rear==L

12. 已知P 为单链表中的非首尾结点，删除P 结点的后继结点Q 的语句为（A ）。

A.P->NEXT=Q->NEXT;FREE(Q); B.Q->NEXT=P; FREE(Q);

C.Q->NEXT=P->NEXT;FREE(Q); D.P->NEXT=S;S->NEXT=P;

13. 循环队列SQ 队满的条件是（B ）。

A.SQ->rear==SQ->front B. (SQ->rear+1)%MAXLEN==SQ->front

23. 最小生成树的构造可使用（B ）算法。

A.Dijkstra算法 B.Prim算法 C.Haffman算法 D.Floyd算法

24. 具有32个结点的完全二叉树的深度为（B ）。

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

25. 在有n 个叶子结点的哈夫曼树中，其结点总数为（D ）。

A ．不确定 B．2n C．2n+1 D．2n-1

26. 下列陈述正确的是（B ）。

A.二叉树是度为2的有序树 B. 二叉树中最多只有二棵树, 且有左右子树之分

C.二叉树必有度为2的结点 D. 二叉树中结点只有一个孩子时无左右之分

27. 先序为A ，B ，C 的二叉树共有（A ）种。

A.3 B.4 C.5 D.6

28. 在树结构中, 若结点B 有3个兄弟,A 是B 的父亲结点, 则A 的度为(B ) 。

A.3 B.4 C.5 D.6

29. 在一个图中，所有顶点的度数之和等于所有边数的（B ）倍。

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

30.n 个顶点的强连通图至少有（A ）边。

A 、n B、n-1 C、n+1 D、n (n-1)

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

有顶点的入度之和等于所有顶点出度之和的（C ）倍。

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

32. 任何一个无向连通图的最小生成树（B ）。

A 、只有一棵 B、一棵或多棵

C 、一定有多棵 D、可能不存在

33. 在图的表示法中，表示形式唯一的是（A ）

A 、邻接矩阵表示法 B、邻接表表示法

C 、逆邻接矩阵表示法 D、逆邻接表表示法

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

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

35. 在一个图中，所有顶点的度数之和等于图的边数的（B ）。

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

36．有7个结点的有向完全图有（C ）边。

A.30 B.40 C.42 D.56

37. 假定在一棵二叉树中，度为2的分支结点个数为15，度为1的分支结点个数为30个，

则叶子结点数为（B ）。

A 、15 B、16 C、17 D、47

38. 设n ，m 为一棵树上的两个结点，在中根遍历时，n 在m 前的条件是（C ）。

A 、n 在m 右方 B、n 是m 祖先

C 、n 在m 左方 D、n 是m 子孙

39. 某二叉树的后序遍历序列为：DABEC ，中序遍历序列为：DEBAC ，则前序遍历序列为（D ）。

A 、ACBED B、DECAB

C 、DEABC D、CEDBA

40. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号

为1，则编号为45的结点的左孩子的编号为（90），右孩子的编号为（91）。

A 、46 B、47 C、91 D、91

41. 某树中，若结点B 有4个兄弟，A 是B 的父亲结点，则A 的度为（C ）。

A 、3 B、4 C、5 D、6

42. 下列叙述正确的是（D ）

A 、二叉树是度为2的有序树

B 、二叉树结点只有一个孩子时无左右之分

C 、二叉树中必有度为2的结点

D 、二叉树中最多只有两棵子树，且有左右之分

43. 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带树路径长度为（D ）。

A 、23 B、37

C 、46 D、44

44．在图的表示方法中，表示形式是唯一的是（C ）。

A.邻接表 B.逆邻接表 C.邻接矩阵 D.其他

46. 设n ，m 为一棵树上的两个结点，在中根遍历时，n 在m 前的条件是（C ）。

A.n 在m 右方 B.n是m 祖先 C.n在m 左方 D.n是m 子孙

二、填空题

1. 树和 图 都属于非线性结构。

2. 顺序表中逻辑上相邻的元素在物理位置上 也 相邻。

3. 双向链表有两个指针域，一个指向前趋，另一个指向__后继__。

4. 若进栈的次序是A,B,C,D,E, 写出两种出栈顺序_ABCDE 、EDCBA 。

5. 队列存取数据应遵循的原则是先进先出。

6. 有20个结点的完全二叉树，编号为7的结点的父结点编号为 3 。

7. 两个序列分别为：L1={3，50，41，42，55，65，70，75}，L2={3，50，41，42，65，55，.

9. 有向图的边也称为 弧，用邻接矩阵存储有向图，其第i 行的所有元素之和等于顶点i 的

出度 。

10．树转换成的二叉树，其根结点的 右 子树一定为空。

11. 二叉排序树是一种 动态 查找表。

12. 对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7

条记录60插入到有序表中时，为寻找插入位置需比较 15 次。

13. 在树形结构中，树根结点没有（前驱）结点，其余每个结点有且只有 1 个前驱结点；

叶子结点没有后继 结点，其余结点的后继结点可以任意多个。

14. 在具有n 个结点的二叉树中，有n+1个空指针。

k-1k 15. 深度为k 的完全二叉树至少有2个结点，至多有2-1个结点，若按自上而下，从左到

右次序给结点从1开始编号，则编号最小的叶子结点的编号是n/2+1。

16. 由a ，b ，c 三个结点构成的二叉树，共有 30种不同形态，若是构成树，共有9 种形态。

17. 树所对应的二叉树其根结点的 右 子树一定为空。

18. 已知完全二叉树的第8层有8个结点，则其叶结点数是 68

三、综合应用题。

2. 已知完全二叉树的第8层有4个结点，请计算它的叶子结点数和总结点数。（写出计算过

程）。（6分）

解：由题意可知，

该完全二叉树有八层，其中

第一层结点数为：1

第二层结点数为：2

第三层结点数为：4

第四层结点数为：8

第五层结点数为：16

第六层结点数为：32

第七层结点数为：64

第八层结点数为：4

因为第八层结点数为4，且为完全二叉树，则第八层四个结点为叶子结点，第七层前两个结

点有子结点，其余62个结点无子结点，则第七层的后62个结点为叶子结点，故叶子结点

数有4+62=66

总结点数为1+2+4+8+16+32+64+4=131

6. 一棵具有6层的满二叉树中结点数为多少？请写出计算公式。

解：2-1=2-1=63

7. 给定一个权集W={4,8,6,9,18}，画出相应的哈夫曼树，并计算WPL 。

K 6

8.已知二叉树的先序遍历序列为:ABDGHCEFI,中序遍历的序列为：GDHBAECIF 。请完成以下各

题：

（1）画出此二叉树。

（2）写出它的后序遍历序列。

（2）其后序遍历的序列为：G H D B E I F C A

（3）

10. 给定一个权集W={4，5，7，8，6，12，18}

长度WPL 。

WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159

11. 假设用于通信的电文仅由A 、B 、C 、D

、E 、F 、G 、H 等8现的频率分别为7、19、2、6、32、3、21、10。试为这8个字母设计哈夫曼编码。

12. 已知一个无向图的顶点集为{a,b,c,d,e}，其邻接矩阵如下，画出草图，写出从顶点a

出发按深度优先搜索进行遍历的结点序列。

解：（1

（2）深度优先搜索：a b d c e （答案不唯一）

广度优先搜索：a b e d c （答案不唯一）

13. 网G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

0 8 10 11 0

8 0 3 0 13

10 3 0 4 0

解：

四、算法设计题

1、单向链表中，在p 指针所指向的结点前插入一个元素x, 写出相关算法, 并画出图形进行描述。

解：

#include

#include

typedef int DataType;

typedef struct node

{

DataType data;

struct node *next;

}Listnode;

int Insert(Listnode *head,DataType a,int b)//这个是插入算法

{

Listnode *p,*h,*s;

int k=1;

p=head;

h=head->next;

while(h!=NULL&&k

{

k++;

p=h;

h=h->next;

}

if(p==NULL)

{

printf("插入失败");

return 0;

}

s=(Listnode *)malloc(sizeof(Listnode));

s->data=a;

s->next=h;

p->next=s;

return 1;

}

void main()

{

Listnode *H,*p;

int x,y;

H=(Listnode*)malloc(sizeof(Listnode));

H->next=NULL;

printf("请输入将被存入链表中的数（0为结束）：");

scanf("%d",&x);

while(x!=0)

{

p=(Listnode*)malloc(sizeof(Listnode));

p->data=x;

p->next=H->next;

H->next=p;

scanf(" %d",&x);

}

printf("请输入将被插入的数:\n");

scanf("%d",&x);

printf("请输入将被插入的数的位置：\n");

scanf("%d",&y);

p=H->next;

printf("插入前，链表：");

while(p!=NULL)

{

printf("%d",p->data);

p=p->next ;

}

if(Insert(H,x,y))//这里是调用插入算法

{

p=H->next;

printf("插入后处理后的链表：\n");

while(p!=NULL)

{

printf("%d",p->data);

p=p->next;

}

printf("\n");

}

}

2、在单链表中删除第i 个结点, 若删除成功返回1, 否则返回0, 并要求画出图形进行描述。解：

#include

#include

template

class SeqList

{

public:

T Delete(int i);

T data[5];

int length;

};

template

T SeqList::Delete(int i)

{

int j;

T x;

if(length==0) throw"下溢";

if(ilength) throw"位置异常";

x=data[i-1];

for(j=i;j

data[j-1]=data[j];

length--;

return x;

}

int DelElem(LinkList *L,int i,datatype *x)

{ LinkList *p;

p=GetList(L, i-1); /*调用按序号查找第i-1个元素地址p 函数*/

if (p!=NULL && p->next!=NULL)

{ Del_Elem (p,x); /*调用删除已知结点p 之后结点函数*/ return 1;

}

else

return 0;

}

int main()

{

SeqList a;

cout>a.length;

cout

for(int i=0;i

{

cin>>a.data[i];

}

for(i=0;i

coutcout

cout>i;

a.Delete(i);

cout

for(i=0;i

coutcout

}