1111 数据结构试题1

《数据结构》试题 1

时间：120分钟 满分：100分

一、 选择题(每小题1分，共20分)

1．以下数据结构中， A 是线性结构。

A）队 B）树 C二叉树 D）图

2．5个顶点的无向图最多有 B 条边。

A、5 B、10 C、20 D、25 3．下面 C 是顺序存储结构的优点。

A）存储密度大 B）插入运算方便 C查找方便 D）适合各种逻辑结构的存储表示 4．下面关于串的叙述中， 是不正确的。

A）串是字符的有限序列

B）空串是由空格构成的串

C）模式匹配是串的一种重要运算 D）串既可以采用顺序存储，也可以采用链式存储 5． B 的邻接矩阵是对称矩阵。

A）有向图 B）无向图 C）AOV网 D）AOE网 6．用链式方式存储的队列，在进行删除运算时， A 。

A）仅修改头指针 B）仅修改尾指针

C）头、尾指针都要修改 D）头、尾指针可能都要修改

7．二叉树的先序遍历和中序遍历如下，则该二叉树右子树的树根是 G 。

先序序列：EFHIGJK 中序序列：HFIEJKG A）E B）F C）G D）H

8．下面 B 方法可以判断出一个有向图中是否有环。

A）深度优先遍历 B）拓朴排序 C）求最短路径 D）求关键路径 9． 若在线性表中采用折半查找法查找元素，该线性表应该 C 。

A）元素按值有序 B）采用顺序存储结构

C）元素按值有序，且采用顺序存储结构 D）元素按值有序，且采用链式存储结

构

10．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为 A 排序法。

A）插入 B）选择 C）冒泡 D）都不是

11．在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）插入一个新元素时，

需要从后向前依次后移 C 个元素。

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

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

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

?010???13．从邻接矩阵A??101?可以看出，该图共有 B 顶点。

?010???A、9 B、3 C、6 D、1 14．上题中，若是有向图，则有 B 条弧。

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

15．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是 D 。

A、i

B、2*i<=n

C、2*i+1>n

D、2*i>n

16．向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素。

A、64.5

B、64

C、63 D、65

17．在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行 D 。

A、q->next=p->next; p->next=q; B、p->next=q->next; q=p;

C、p->next=p->next; q->next=q; D、p->next=q->next; q->nxet=p; 18．对一个满二叉树，m个树叶，n个结点，深度为h，则有 D 。

A、n=h+m C、m=h-1

B、h+m=2n

D、n=2-1

h19．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件为 A 。

A、front==rear

C、rear!=NULL

B、front!=NULL D、front==NULL

20．在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 A 。

A、选择排序

B、冒泡排序 C、插入排序 D、希尔排序

二、判断题：（判断下列各题正误，正确的在题目后面的括号内写“对”，错误的在题目后面

的括号内写“错”。每小题2分，共10分）

（ × ）1. 栈和队列都是非线性数据结构。 （ √ ）2. 完全二叉树可以用顺序存储结构进行存储。 （ × ）3. 数据元素是数据的最小单位。(基本单位)

（ √ ）4. 含尾指针的单链循环表可以被用于队列操作。

（ √ ）5. 数据结构包含数据的逻辑结构、数据的存储结构以及数据集合上定义的运算。

三、填空题（每空2分，共10分）

1、 在线性表的单链表存储结构中，每个结点包含两个域，一个叫 数据（值） 域， 另一个叫 指针 域 。

2、 设字符串S1=‘ABCDEFG’，S2=‘PQRST’，则运算

S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为 BCDEF EF 。

3、 队列的插入操作在 队尾 进行，栈的删除操作在 栈顶 进行。

四、回答下列问题（每小题8分，共40分）

1． 分别给出对下图进行深度优先和广度优先遍历的结果。

9 1．深度：125963784 （不唯一） 广度：123456789 （不唯一）

2．已知序列（12，4，17，10，7，30），用直接选择排序法对其进行递增排序，写出每一趟的排序结果。

2．第1趟：4 12 17 10 7 30 第2趟：4 7 17 10 12 30 第3趟：4 7 10 17 12 30 第4趟：4 7 10 12 17 30 第5趟：4 7 10 12 17 30

3．一批数据有如下的逻辑结构B=(K ,R),其中 K={k1,k2,k3,?,k9}, R={r},

r={?k1,k2?,?k1,k3?,?k1,k4?,?k1,k7?,?k1,k8?,?k4,k5?,?k4,k6?,?k8,k9?} , 试用图示法表示其逻辑结构。

5 2 6 7 1 3 4 8

2 3 5 1 4 6 7 8 9 4．已知一棵非空二叉树，其按中序和后序遍历的结果分别为：

中序：CGBAHEDJFI 后序：GBCHEJIFDA

请画出这棵二叉树，并写出其前序遍历的结果。

前序遍历结果:ACBGDEHFJI

5．已知字符：C1，C2，C3，C4，C5，C6的权分别为：17，5，16，4，8，11，请构造相应的赫夫曼树，并给出相应字符的赫夫曼编码。

c1:10 c2:1111 c3:01 c4:1110 c5:110 c6:00

五、编写算法（每小题10分，共20分）

要求: 1、说明算法中使用的主要数据结构、变量；2、用C可

1．设有一个由正整数组成的无序无头结点的单链表，编写子程序(或函数)找到其最小值。

struc node { int d;

struct node *next; }

int minn(node *p) {int x=0; while(p) {

if(p->dd;} p=p->next;} RETURN(x); }

2．冒泡排序。

int n; int p[n];

void sort(int p[],n) {int i,j,t,k;

for (i=0; i

for(j=0;j++;j<=n-i-1) { if(p[j]>p[j+1]) {t=p[j]; p[j]=p[j+1]; p[j+1]=t; k=0; } } } }

本文来源：https://www.bwwdw.com/article/8pc8.html