算法与数据结构复习题

算法与数据结构复习题

一、单选题

1．要求具有同一逻辑结构的数据元素具有相同的特性，其含义为（B）。

A.数据元素具有同一的特点

B.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致

C.每个数据元素都一样

D.仅需要数据元素包含的数据项的个数相同

2．下列程序段for(i=1;i<=n;i++) A[I,j]=0;的时间复杂度是（D）。

A.O(1)

B. O(0)

C. O(1+n)

D. O(n)

3．在一个单链表中，已知*q 结点是 *p 结点的前驱结点，若在*q和*p之间插入结点*s，则执行操作（C）。

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

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

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

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

4．在一个单链表中，若删除*p 结点的后继结点，则执行操作（A）。

A.q=p->next;p->next=q->next;free(q);

B. p=p->next;p->next=p->next->next;free(p);

C.p->next=q->next;free(p->next);

D. p=p->next->next;free(p->next);

5．设指针 p 指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映（C）。

A.p->prior->next=p->next->next;

B. p->prior->prior=p->next->prior;

C.p->prior->next=p-> next->prior;

D. p->next->next= p->prior->prior;

6．表达式 a*(b+c)--d 的后缀表达式是 (B) 。

A． abcd*+- B． abc+*d-C． abc*+d- D． -+*abcd

7．设一个栈的输入序列为A， B， C， D，则借助一个栈所得到的输出序列不可能是(D) 。

A．A，B， C，D B．D，C，B，A C.A， C， D， B D.D， A， B，C

8．设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是(B) 。

A． 23415B． 54132 C.23145 D.15432

9．设有一个顺序栈， 6 个元素1、 2、 3、 4、5、 6依次入栈，如果 6 个元素出栈的顺序是 2、 3、 4、6、 5、 1，则

栈的容量至少应该是(B) 。

A． 2B． 3 C.5 D.6

10．设有一个顺序栈的入栈序列是a、 b、 c，则 3 个元素都出栈的可能不同排列个数为(B) 。

A． 4B． 5 C.6 D.7

11．若已知一个栈的入栈序列是1，2， 3，, ， n，其输出序列为pl ， p2， p3，, ， pn，若 pl是 n，则 pi是（ C）。A． i B． n-I C． n-i+1D．不确定

12．已知广义表 LS=((a ， b，c) ， (d ， e， f)) ，运算 head 和 tail函数取出元素 e 的运算是 (C) 。

A． head(tail(LS))B． tail(head(LS))

C． head(tail(head(tail(LS))))D． head(tail(tail(head(LS))))

13．二维数组 A 的每个元素是由 6 个字符组成的串，其行下标i=0 ， l ，, ， 8，列下标为 j=1 ， 2．, ， 10。设每

个字符占一个字节, 若按行先存储，元素A[8 ， 5] 的起始地址与 A 按列存储时起始地址相同的元素是(B) 。

A．A[8 ，5] B．A[3，10] C ．A[5 ，8]D． A[0， 9]

14．数组 A[1..5， 1..6] 的每个元素占 5 个单元，将其按行优先次序存储在起始地址为1000 的连续的内存单元中，

则元素 A[5 ， 5] 的地址为 (A)

A.1140

B.1145

C.1120

D.1125

15．对二叉树从 1 开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其

左孩子的编号小于其右孩子的编号，则可采用遍历方式是（C）。

A. 先序

B. 中序

C.后序

D.从根开始的层次遍历

16．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是（B）。

A. 空或只有一个结点

B. 高度等于其结点数

C.任一结点无左孩子

D. 任一结点无右孩子

17．下列说法正确的是(D) 。

(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索

(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前

(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值

A． (1)(2)(3)B． (1)(2)C． (1)(3)D．前面的可选答案都不对

18．下面的说法中正确的是(B) 。

(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。

(2) 按二叉树定义，具有三个节点的二叉树共有 6 种。

A． (1) ， (2) B ． (1)C． (2)D． (1) ， (2) 都错

19．树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是(B) 。

A．树的后根遍历与其对应的二叉树的后根遍历相同

B．树的后根遍历与其对应的二叉树的中根遍历相同

C．树的先根遍历与其对应的二叉树的中根遍历相同

D．以上都不对

20．下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是（D）。

A.V1V2V3V4V5

B.V1V2V3V5V4

C.V1V4V3V5V2

D.V1V3V4V5V2

21．以下说法不正确的是(D) 。

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点

C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点

D．有向图的遍历不可采用广度优先搜索

22．在平衡二叉树中插入一个结点后引起了不平衡，设最低( 最接近于叶子) 的不平衡点是A，并已知 A 的左、右孩

子的平衡因子分别为-1 和 0，则应进行的平衡旋转是(B) 。

A．LL 型 B．LR型 C．RL 型 D．RR型

23．设哈希表长为14，哈希函数H(key)=key ％ 11，表中已有数据的关键字为15， 38， 61， 84，四个，现将关键字

为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(A) 。

A．8B．3C．5D．9

24．对散列文件，以下说法错误的是(D) 。

A．散列文件插入、删除方便，不需要索引区且节省存储空间

B．散列文件只能按关键字随机存取且存取速度快

C．经过多次插入、删除后，可能出现溢出桶满的情况

D．散列文件顺序存取方便

26．对有 18 个元素的有序表作二分查找，则查找A[3] 的比较序列的下标为（D）。

A.1，2，3

B.9 ，5，2， 3C． 9，5， 3 D.9，4，2， 3

27．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知 A 的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是（C）。

A.LL 型

B.LR 型

C.RL 型

D.RR型

28．在 n 个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（B）。

29．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是(A) 。

A．插入B．选择C．快速D．堆

30．下面关于B-树和 B+树的叙述中，不正确的结论是(A) 。

A． B-树和 B+树都能有效地支持顺序查找

B． B-树和 B+树都能有效地支持随机查找

C． B-树和 B+树都是平衡的多叉树

D． B-树和 B+树都可用于文件索引结构

31．关键路径是事件结点网络中(B) 。

A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长的回路D．最短的回路

32．将两个各有 n 个元素的有序表归并成一个有序表，其最少的比较次数是(A) 。

A． n B． 2n-1 C ． 2n D． n-1

33．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是（A）。

A. 堆排序

B. 冒泡排序

C.直接选择排序

D.快速排序

34．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D）

A. 堆排序

B. 冒泡排序

C.快速排序

D. 直接插入排序

35．数据表 A 中有 10000 个元素，如果仅要求求出其中最大的10 个元素，则采用最节省时间的排序算法是（A）。

A. 堆排序

B. 希尔排序

C.快速排序

D. 直接选择排序

36．数据结构被形式地定义为（D,R），其中 D 是（）。

A. 算法

B. 操作的集合

C.数据元素的集合

D. 数据关系的集合

37．顺序表是线性表的（A）。

A. 顺序存储结构

B.链式存储结构

C.索引存储结构

D. 散列存储结构

38．在一个单链表中，已知*p 结点不是最后结点，若在 *p 之后插入结点 *s ，则执行操作（ B）。

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 ;

39．循环队列 A[O..m-1]存放其元素值，用front和 rear 分别表示队头及队尾，则循环队列满的条件是(A) 。

A． (Q.rear+1) ％ m==Q.front B． Q.rear==Q.front+1

C． Q.rear+l=Q.front D． Q.real==Q.front

40．如果以链栈为存储结构，则出栈操作时( B )。

A．必须判栈满B．必须判别栈空 C. 判别栈中元素类型 D. 不必作任何判别

41．对矩阵压缩存储是为了(B) 。

A. 方便运算

B. 节省空间

C.方便存储

D. 提高运算速度

42．将一棵有 100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为

1，则编号为 49 的结点的左孩子编号为（B）。

A.98

B.99

C.50

D.48

43．二义树在线索化后，仍不能有效求解的问题是（D）。

A. 先序线索二叉树中求先序后继

B. 中序线索二叉树中求中序后继

C. 中序线索二叉树中求中序前趋

D.后序线索二又树中求后序后继

44．对于关键字序列 (12 ，13，11， 18，60，15，7，18， 25，100) ，用筛选法建堆，则开始结点的键值必须为（C）。

A.100

B.12

C.60

D.15

45．无向图 G=(V E) ，其中 V={a ， b， C， d， e， f} ， E={， ， ， ， ， ， } ，对该图进行深度优先排序，得到的顶点序列正确的是(D) 。

A． a， b， e， c， d，f B．a，c，f, e，b，d

C． a， e， b， c， f, d D．a，e，d，f, c, b

46．设图 G用邻接表存储，则拓扑排序的时间复杂度为(B ) 。

A． D(n) B．O(n+e)C．O(n× n)D．0(n×e)

47．关于散列法查找说法正确的是(B) 。

A．采用链地址解决冲突时，查找一个元素的时间是相同的

B．采用链地址解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的

C．采用链地址解决冲突容易引起聚集现象

D．再散列不易产生聚集

48．在平衡二叉树中插入一个结点后引起了不平衡，设最低( 最接近于叶子 ) 的不平衡点是A，并已知 A 的左、右孩子的平衡因子分别为 -1和 0，则应进行的平衡旋转是(B) 。

A．LL 型B． LR

型C．RL型D． RR型

49．在有向图 G的拓扑序列中，若顶点Vi 在顶点 Vj之前，则下列情形不可能出现的是(D) 。

A． G中有弧 B． G中有一条从 Vi 到 Vj 的路径

C． G中没有弧 D． G中有一条从 Vj 到 Vi 的路径

50．排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多的是（C）。

A. 堆排序

B. 冒泡排序

C.快速排序

D.SHELL排序

二、填空（问答）题

1．数据结构被形式地定义为（D,R），其中 D 和 R 的含义是什么。（ D 是数据元素的集合，R 是数据关系的集合）。数据的逻辑结构包括哪四种类型。（线性结构、树形结构、图形结构、集合类型）。从存储结构的概念上讲，顺序表是

线性表的（顺序存储结构），链表是（链式存储结构）。

2．算法的五个重要特性有哪些。（有穷性、确定性、可行性、输入、输出）。抽象数据类型是指一个（数学模型）

以及定义在该模型上的（一组操作）。

3．在含有 n 个结点的顺序存储的线性表中，在任意一个结点前插入一个结点所需要移动结点的平均次数为（ n/2）。在含有 n 个结点的顺序存储的线性表中，任意删除一个结点所需要移动结点的平均次数为（n-1/2 ）。对一个线性

表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（O(n) ）。

4．线性结构中的一个结点代表一个（数据元素）。若线性表中最常用的操作是取第i 个元素和查找该元素的前驱，

则采用的存储方式最能节省时间的是（顺序表）。若最常用的操作是插入和删除第i 个元素，则采用的存储方式最

能节省时间的是（单链表）。

5．在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除操作过程不同，，需要修改（头指针）。在单链表中设置头结点的作用是（便于操作），无论链表是否为空。使（头指针）均不为空。对于双向链表，在两

个结点之间插入一个新结点需修改的指针共有（ 4 个），单链表为（ 2 个）。

6．如果以链栈为存储结构，则出栈操作时(必须判别栈空) ，与顺序栈相比，链栈有一个明显的优势是(不易出现栈满 )。

7．循环队列采用数组data[1 ．．n] 来存储元素的值，并用front 和 rear 分别作为其头尾指针。为区分队列的满和

空，约定：队中能够存放的元素个数最大为n-l ，也即至少有一个元素空间不用，则在任意时刻，至少可以知道一

个空的元素的下标是（front ）；入队时，可用语句（rear=rear+1%n ）求出新元素在数组data 中的下标。

8．已知栈的输入序列为1，2，3, ．， n，输出序列为a1， a2，, ， an， a2=n 的输出序列共有（ n-1 ）种输出序列。9．稀疏矩阵一般的压缩存储方法有两种，它们是用（哈希表、三元组和十字链表)。对矩阵压缩存储是为了( 节省空间)。

10．将下三角矩阵 A[l..8， 1..8] 的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则 A[7 ， 5] 的地址为（ 1100）。

11．已知数组 A[1..10 ，1..10]为对称矩阵，其中每个元素占 5 个单元。现将其下三角部分按行优先次序存储在起

始地址为1000 的连续的内存单元中，则元素A[5 ， 6] 对应的地址为（ 1095）。

12．两个串相等的充要条件是，两个串的( 长度 ) 相等，且其所对应各个位置的（字符）也相等。

13．取出广义表 A=((x ， (a ，b， c， d)))中原子 C 的函数是（ head(tail(tail((head(tail(head(A))))))）。14．在有 n 个结点的二又链表中，值为非空的链域的个数为（n-1 ）。在有 n 个叶子结点的哈夫曼树中，总结点数是

（ 2n-1 ）。在树形结构中，根结点数只有（ 1 个），其余每个结点有且仅有一个元素（前驱）结点。

15．一棵二叉树 L 的高度为 h，所有结点的度或为 0，或为2，则这棵二叉树最少的结点数为( 2h-1 ) 。

开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（98 ）。有64 个结点的完全二叉树的深度为( 7 )。

16．拓扑排序只能用于（有向无环图）。连通图是指图中任意两个顶点之间（都连通的无向图）。一个有 n 个顶点的无向连通图，它所包含的连通分量个数最多为( 1 ) 个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有 n 个顶点的图形成一个环，则它有（n）棵生成树。

17．求图的最小生成树有两种算法，（ prim（普里姆））算法适合于求稠密图的最小生成树，（ kruskal （克鲁斯卡尔））算法适合于求稀疏图的最小生成树。设图G用邻接表存储，则拓扑排序的时间复杂度为(O(n+e) ) 。

18．在一棵三叉树中，度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为0 的结点数为(6) 。

19．中序表达式 A*(B+C) ／ (D-E+F) 的后序表达式是 (ABC+*DE-F+/ )。

20．有向图 G用邻接矩阵 A 存储，则顶点 i 的入度等于 A 中（第 i列 1 的元素之和）。具有 10 个顶点的无向图，

边的总数最多为（ 45）个，具有 n 个顶点的强连通有向图G，边的总数至少有（n）条。

21．从未排序序列中依次取出元素与已排序序列( 初始时为空 ) 中的元素进行比较，将其放入已排序序列的正确位置

上的方法，称为 ( 插入排序 ) 。对于关键字序列(12 ，13， 11， 18，60， 15， 7，18， 25， 100) ，用筛选法建堆，则开始结点的键值必须为（60）。

22．在有序表 A[l..20]中，采用二分查找算法查找元素值等于A[12] 的元素，所比较过的元素的下标依次为

（ 10,15,12 ），查找元素值等于 5 的元素，所比较过的元素个数为（5）个。分别采用堆排序、快速排序、插入排序

和归并排序算法对初始状态为递增序列的表按递增顺序排序，最省时间的是（插入排序）算法，最费时问的是（快

速排序）算法。直接选择排序算法所执行的元素交换次数最多为（n-1 ）次，最好情况下所作的交换元素的次数为

（ 0）次。在堆排序，希尔排序，快速排序，归并排序算法中，占用辅助空间最多的是(归并排序 ) 。二分查找法要求查找表中各元素的关键字的值得排列必须是（递增或递减或有序）。

23．若一个待散列存储的线性表长度为n，用于散列的散列表长度为m，则 m应（小于等于） n，装填因子公式为（ n/m）。散列表的平均查找长度 ( 与处理冲突方法有关而与表的长度有关) 。

24．在平衡二叉树上删除一个结点后可以通过旋转使其平衡，最坏情况下需旋转（O(log 2n) ）次。

25．贪心算法的基本思想是，逐步构造最优解，每步都按照一定的标准，称为（贪心）准则，做出决策。0/1 背包问题的三种贪心准则中，相对较优的是（价值密度）贪心准则。分治法与（递归）技术紧密结合。与分治法不同的

是，动态规划是（自底向上或自下而上）、逐级求解子问题。分枝定界的搜索策略与（广度优先）类似，而回溯方

法则采用（深度优先）搜索策略。

26．对于单链表、单循环链表和双向链表，若仅仅知道一个指向链表中某结点的指针p，能否将 p 所指的结点的数据元素与它的直接前趋（假设存在）交换？若不可以，说明理由；若可以，写出主要算法。

（ 1）单链表不能，单循环链表和双向链表可以。

（ 2）单循环链表 q=p;while(q－ >next!=p) q=q－ >next;temp=p－>data; p － >data=q － >data;q － >data=temp;

（3）双向链表： q=p－ >prior; temp=q － >data; q － >data=p － >data;p － >data=temp;

27．设有三对角矩阵a[1..n,1..n]把非零元素按列存储在向量b[1..3*n-2]中，使得b[k]=a[i,j]。

求：⑴用i，j表示k的下标变换公式（k=2*(j-1)+i）

⑵用 k 表示 i ， j 的下标变换公式（j=(k DIV 3)+1 i=k-2*(j-1)）

28．内存中一片连续空间（不妨设地址从 1 到 m），提供给两个栈S1 和 S2 使用，怎样分配这部分存储空间，使得对

任意一个栈，仅当这部分全满时才发生上溢。( 为了尽量利用空间，减少溢出的可能，可采用栈顶相向，栈底分设

两端的存储方式，这样，对任何一个栈，仅当整个空间全满时才会发生上溢。)

29．有一 n 个结点的树，其中所有分支结点的度均为k，求该树中叶子结点的个数。

设 n o为叶子结点数，n k为度为 k 的结点数， n 为结点总数（依题意：n=n o+n k— (1) n= kn k+1 (2)

综合 (1)和(2)得：n o=n-(n-1)/k

30.设有n个无序元素，按非递减次序排序，但只想得到前面长度为k 的部分序列，其中n>>k, 最好采用什么排序

方法？为什么？如有这样一个序列：{59,11,26,34,17,91,25}，得到的部分序列是{11,17,25}，对于该例使用所选

择的方法实现时，共执行多少次比较？

（ 1）采用堆排序最合适，因为当部分序列较小时，堆排序的时间复杂度近似为O(n) 。

（ 2）初始建堆：比较8次第二次调整：比较2次输出31.设二叉排序树中关键字由

输出 11, 第一次调整：比较４次输出

25, 总共比较 14 次。

1 至 1000 的整数组成，现要查找关键字为

17

363 的结点，下述关键字序列哪一个不可

能是在二叉排序树中查到的序列？说明原因。

（1） 51,250,501,390,320,340,382,363;

（2） 24,877,125,342,501,623,421,363;

((1 ）是；⑵不是。因为查询序列是：查421 时，其 623 左、右两个区间都不存在，查找失败。)

32.在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反方向的移动，从而认为该算法是不稳定

的，这种说法对么？为什么？

（不正确。算法的稳定性是考察最终排行的位置交换，与中间过程无关。如：对于整数序列（18，36，25）。按基数排序的LSD方法，第一趟排序后（25， 36， 18），第二趟排序后得到（18，25， 36）， 18 虽向相反方向移动，但

不影响最终位置。）

33.将算术表达式（（ a+b） +c*(d+e)+f ）*(g+h) 转化为二叉树 ( 二叉链表结构 ) （略）

34．在线性结构中，开始结点没有（前驱）结点，最后一个元素没有（后继）结点。

35．线性表的逻辑结构是（线性结构），其所含结点的个数称为线性表的（长度）。

36．队列的特性是（先入先出或后入后出），栈的特性是（后入先出或先入后出）。

37．数组 A[l..10，1..10]的每个元素占 5 个单元，将其按列优先次序存储在起始地址为1000 的连续的内存单元中，则元素 A[5 ， 6] 的地址为（1270）。

38．若某二叉树有20 个叶子结点，有30 个结点仅有一个孩子，则该二叉树的总结点数是（69）。

39 ．树 t的存储结构为二叉链表bt ，树 t中的一个叶子结点在 bt中满足条件（ bt->lchild<>null&&

bt->rchild<>null;

40．求图的最小生成树有两种算法，(prim （普里姆） )算法适合于求稠密图的最小生成树。

41．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的（长度）有关，而且与每一块中的元素（长度）有关。

42．分枝定界的搜索策略与 ( 广度优先 )类似，而回溯方法则采用( 深度优先 ) 搜索策略。

43． 0/1背包问题的三种贪婪准则中，相对较优的是( 价值密度 )贪婪准则。

三、应用题

1．有一个二叉树按层次顺序存放在一维数组中，如下图所示：

试求：（ 1）该树的后序遍历序列。（ C,E,B,D,A ）

（ 2）画出该树的后序线索树。（略）

1234567891011

A C

B E D

2．按顺序输入下列顶点对:(1,2) 、 (1,6) 、(2,6)、 (1,4)、(6,4)、 (1,3) 、(3,4) 、(6,5)、 (4,5) 、(1,5)、 (3,5)，（ 1）画出相应的邻接表。

（ 2）写出在邻接表上，从顶点 3 开始（表下标从0 开始）的 DFS序列和 DFS生成树。

（ 1）邻接表

0V142351∧

1V2

50∧

2V3

430∧

3V4

4250∧

4V5

2035∧

4310∧

（2） DFS序列 2-0-1-5-3-4

3．设一哈希表长为13，采用线性探测法解决冲突，哈希函数H(key)=key%13,

（1）画出在空表中依次插入关键字25， 20， 36， 15， 41， 52， 29， 72， 67 后的哈希表。

（2）求在等概率情况下，查找成功和查找不成功的平均查找长度。

（ 1） 100101 102 103 104 105 106 107108 109 110 111 112

521541296720723625

（ 2）平均查找长度

查找成功的平均查找长度=(5*1+3*2+1*4)/9=1.6

查找不成功的平均查找长度=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/13

4．对下面的关键字集（30，15， 21，40， 25，26， 36，37），若查找表的装填因子为0.8 ，采用线性探测再散列解

决冲突：（ 1）设计哈希函数；（2）画出哈希表；

（1）表长 : m=n/ α=8/0.8 =10哈希函数： H(key)=key%7

（2）哈希表

0123456789

2115303625402637

5．写出对关键字序列 {503,087,512,061,908,124,897,275,653,426}建立一棵平衡二叉排序树的过程，并写出调整平衡时的旋转类型。

503503

087512RL087897

061124908061124512908

897

503503

087897RR087897

061124512908061 275512908

275653124 426653

426

6.已知一棵二叉树的先序序列和中序序列分别为：abdgicefhj 及 bgidaecfjh ，画出该的二叉树的后序线索二叉树。（略）

7.假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110 ， 10， 110， 111， 00， 0111

和010。

（1）画出此哈夫曼树（略）

（2）若这些字符在电文中出现的频度分别为3、 35、 13、15、 20、5、 9，求哈夫曼树的带权路径长度。（带权路径长度 WPL=2.53）

8.已知有一个 10 个顶点的连通图，顶点编号为 1 至 10，其边的关系集合表示为 {（ 1，2）（ 1，3），（ 1，8），（ 2，4），

（ 3， 9），（ 3， 10），（ 5，7），（ 6， 7），（7， 8），（ 8，9） } ，试求：画出该连通图及以顶点③为根的深度优先生成树。（略）

9.对下面的关键字集{35 ， 15，21， 99，25， 26，36， 37， 01， 18} 写出快速排序的每趟结果和最终结果。（略）10．有字符串次序为3*-y-a/y^2 ，利用栈，给出将次序改为3y-*ay2^/- 的操作步骤。（可用 X 代表扫描改字符串过程中顺序取一个字符进栈的操作，用S 代表从栈中取出一个字符加入到新字符串尾的出栈操作。例如，ABC变为 BCA的操作步骤为 XXSXSS）。（略）

11.设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“ // ”后面加上必要的注释。

p=L→next; pre=p; //pre为最小结点指针

while(p){ if(p→ data

pre=p; p=p→ next; //（1）

}//while

printf(pre→ data); //（2）

if(pre → next && pre→ data%2！=0) { //（3）

temp=pre →data; pre→ data=pre→ next→ data; pre→next→ data=temp;

}//if

}//F1

算法功能：找出最小值结点，且打印该数值。若该数值是奇数且有后继，则与后继结点的数值交换。

(1)查找最小值结点；

（2）输出最小值结点；

（3）若该数值是奇数且有后继，则与后继结点的数值交换。

12.已知二叉树的存储结构为二叉链表，LinkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型，

阅读下面算法并回答：

LinkList L=Null; p;

void F2(BiTree T){

if(T){ F2(T→ lchild);

if((!T→ lchild)&&(!T→child){ p=(ListNode *)malloc(sizeof(ListNode));

p→ data=T → data; p→ next=L;L=p; }//if

F2(T →rchild);

}//if

}//F2

（ 1）说明该算法的功能；

（ 2）对于一棵有8 个结点的完全二叉数（假设结点顺序为A、B、C、D、 E、 F、 G、H），画出执行上述算法后建立的结构。

（ 1）按中序遍历二叉树，逆序建立以叶子结点为链表结点、以L 为头指针的无头结点的单链表。（2）（略）

四、算法分析与设计题

1．设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“// ”后面加上必要的注释。

void F1(Linklist &L){

p=L→ next; pre=p; //pre为最小结点指针

while(p){ if(p→ data

pre=p; p=p→ next;//（1）查找最小值结点

}//while

printf(pre→ data); //（2）输出最小值结点

if(pre → next && pre→ data%2==0) {//（3）删除其后继结点

p=pre →next,

pre → next=p → next;free(p);

}//if

}// F1

算法功能：找出最小值结点，打印该数值。若该值是偶数且有后继，则将其后继结点删除。

2．设有n 个大小不等的数据组（n 个数据组中数据的总数为m），顺序存放在空间区 D 内，每个数据占一个存储单元。数据组的首地址由数组S 给出，阅读下面的算法，指出该算法的功能，并在“// ”后面加上必要的注释。

void F1(sqlist &L,int i, ElemType x){

if(i>=1&&i<=L.length){ //（1）插入到D 区

for(j=0,p=L.elem[0];j<=m;j++) p++; //（2）求D区空闲空间首地址

if(i==L.length) *p=x;//（3）插入到第n 个数组

else { for(q=L.elem[i];p>=q;--p) *(p+1)=*p; *p=x; //插入x

for(q=&L.elem[i],p=&L.elem[L.length-1]; p>=q;q++) (*q)++;//else

m++; }//if

}//F1

算法功能：将数据x 插入到 D 区，插入后D和 S 关系不变。

3．设有一个正整数序列组成的非递减有序单链表，阅读下面的算法，指出该算法的功能，并在“// 后面加上必要的注释。

void F1 (Linklist L;int,x){

p= L→ next; q=p; //p为工作指针

pre=L;L→next=NULL; .//q指最小元素

while(P&&P → data

r= p→ next; p→next=L→next;

L→ next=p; p=r; //（2）置逆

}//while

q→next=p; pre=q; //（3）重新链接

}//F1

算法功能：在单链表中将比正整数x 小的数按递减次序排列。

4．假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树T 中，阅读下面的算法，指出该算法的功能，并在“// ”后面加上必要的注释。

int F1(BiTrec T){

if(!T) return 0;

if(!T → lchild &&!T→ rchild)//（1）判断是否为叶子结点

return (T→ data);

Lv= F1(T →lchild);Rv= F1(T→ rchild);

switch(T→data){//（2）运算

case’ +’ : V=Lv+Rv; break;

case’ - ’ : V=Lv-Rv; break;

case’ * ’: V=Lv*Rv; break;

case’ / ’ : V=lv/Rv; break;

} //switch

return V;//（3）返回结果

}//F1

算法功能：后序遍历二叉树，求算术表达式的值。

5．在有向图G中，如果r 到 G 的每个结点都有路径可达，则称结点r 为 G的根结点，下面算法的功能是判断有向图 G是否有根，若有，则打印出所有根结点的值。请填空补全算法，并在“// ”后面给以注释。

void F2(ALGraph G){ //利用深度优先搜索，判断有向图G是否有根结点。

int visited[maxsige],count; //count为记录结构的顶点数。

for(v=0;v

for(v=0;v

count=0; DFS(G,v) ; if(count==(2)_)//判断是否为根

printf(G.ver[v].data); }

}// F2

visited[v]=1; count++;

for(p=G.vertices[v].firstarc; p; p=p→ nextarc){

w=p→ adjvex; if(!visited[w]) (3)_;//深度优先搜索

}

}//DFS

（1） visited[v]=0;（2）G.vexnum（3）DFS(G,w) ;

6．下面算法的功能是实现单链表中的简单选择排序，其中L 为链表的头结点指针，请填空补全算法，并在“// ”

后面给以注释。

void F2(LinkList &L){//用单链表实现简单选择排序

p=L－ >next; //初始化，p为工作指针

while(p){ min=p; (1)___________;// q为插入指针，min为当前最小指针

while((2)___________){ //一趟选择排序

if(q－ >datadata) min=p; q=q－>next;

}//while(q)

if( (3)___________){//交换

temp=p－ >data; p－>data=min－>data;min－>data=temp;

}//if

p=p － >next;

}//while(p)

}//F2

（ 1） q=p－ >next;（2）q或q !=null（3）min

7．设计算法DeleteX 的功能是：删除单链表L 中值为 x 的结点的直接前趋结点。（设L是带头结点的单链表的头指针，并为已知的LinkList类型）

void DeleteX(LinkList &L){ //删除单链表中的直接前驱结点

p=L－ >next; //初始化，p为工作指针

while(p&& p－>next－>data!=x){//q为前驱结点指针

q=p;p=p－ >next;

}// while

if(p){ //删除

q－ >next=p － >next;

free(p);

}//if

}// DeleteX

8． Internet的域名系统是一个典型的层次结构，可用树形结构表示。每一个域名服务器提供的区域信息恰好是以该结点为根的子树中的全部的IP 地址。设计算法以孩子- 兄弟链表作为树的存储结构, 实现搜索所有www域名的 IP 地址。

void Outpath(CSTree T,Stack &S){//搜索IP地址

while(T){ Push(S,T－>data)

if(!T－ >firstchild && T－>data==” www”)

visitstack(S);//输出一条路径

else Outpath(T－>firstchild ,&S)//递归遍历左子树

Pop(S,e); T=T－>nextsibiling; //遍历右子树

}//while

}//Outpath

9．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序（要求给出逆邻接表的存储结构定义）。

(1) 存储结构定义

顶点结构vexdata firstin

表结点结构

adjvex info firstarc

(2) 算法设计

int toposort (ALGraph G,int tpv[]){ //以逆邻接表为存储结构的有向图的拓扑排序

top=0;

for(i=0;i

findoutdegree(G,outdegree); //对各顶点求出度

outdegree[p→adjvex]++; InitStack(&S); //初始化栈

for(i=0;i

if(outdegree[i]==0)Push(&S,i); //出度为零的顶点入栈

while(!Stack(S)){

Pop(&S,i);printf(G.adjlist[i].vextex);

tpv[top++]=i;

for(p=G.adjlist[i].firstedge;p;p→next){

j=p→ adjvex; outdegree[j]--;

if(!outdegree[j]) Push(&S,j);

// 出度为零的顶点入栈

}//for

}//while

if(top

else {//输出顶点拓扑排序序列

for(i=0;j=top-1;i< G.vexnum/2;i++,j--){//置逆输出

temp=tpv[i];tpv[i]=tpv[j];tpv[j]=temp;

}//for

return 1;

}//else

}//toposort

10．已知深度为h 的二叉树采用顺序存储结构存放在数组B[1..2h-1]中，设计一个递归算法，产生该二叉树的二叉链表结构。

void CreateTree(int B[2h],int j,BiTree t){

//创建 t 树的二叉链表结构， j 为数组下标，初值为 1

t=( BiTree ) malloc( sizeof(BiTNode));

t － >data=B[j]; //创建根结点

if(2*j>2h) t－>Lchild=null;//无左子树

else //递归创建左子树

t－ >Lchild=CreateTree(B,2*j,t－>Lchild)；

if(2*j+1>2h) t－>Rchild=null;//无右子树

else //递归创建右子树

t－ >Rchild=CreateTree(B,2*j+1,t－>Rchild)；

}// CreateTree

11．假设哈希函数为H（ key） , 编写用链地址法解决冲突的哈希表的插入和删除算法。

哈希表插入，用链地址法解决冲突

void F2( HashTable &H, keytype Key){//

i=H(Key);;//获取哈希地址

if(H[i]==Null){

s=(Linklist)malloc(sizeof(Lnode));

}//if

else{ p=H[i];//查找

while(p&&p → data!=key) p=p→ next;

if(p→ data==key) exit(1);

else{ s=(Linklist)malloc(sizeof(Lnode));//产生新结点，插入表头

s→ next=H[i]; H[i]=s;

}// else

}//else

}//F2

void Delete_HS(HashTable &H, KeyType key){

//哈希表删除，用链地址法解决冲突

i=H(key);//获得哈希地址

if(H[i]= =Null) exit(1);

p=H[i];q=p; // p为工作指针，q为p前趋

while(p&&p→ data!=key) {//查找

q=p; p=p → next;

}//while

if(!p) exit(1);

if(q==H[i]){ //key为第一结点

H[i]p→ next; free(p);

}// if

else{

q→ next=p → next;

free(p);

}//else

}//Delete_HS

12．设关键字是一个由26 个小写字母组成的字符串，哈希表的长度为26。试编写算法，建立哈希表，并以第一个字符的字典顺序输出哈希表中的所有关键字。设哈希函数为hast(x)=x中的第一个字符在字典顺序中的序号，采用线性探测再散列法来解决冲突。（假设函数f(x) 能够计算出x 中的第一个字符在字典顺序中的序号）。

void create_Hs(RedType &H,key Type key){

i=Hash(key);//创建哈希表

if(H(i)==Null)//插入

H(i)=key;

else{ //解决冲突，再插入

j=(i+1)%m; //m为表长

while (j!=i){

if(H[j]==Null)

H[j]=key;

else j=(j+1)%m;

}//while

}//create_Hs

void print_Hs(RedType H){

//输出哈希表

for (i=0;i<26;i++){

j=1;

while(H[j])!=Null{

if(f(H[j])==i)

printf(H[j]);

j=(j+1)%m;

}//while

}//for

}//print_Hs

13.已知 f 为单链表的表头指针，链表中存储的都是整型数据，试设计算法用直接插入排序使链表非递减有序。

void InsertSort_L(Linklist &La){

//用直接插入排序使链表递增有序

if(La→ next){ //链表不空

p=La→next → next;

La→ next → next → Null;

while(p!=Null){

r=p → next;//暂存p的后继。

q=La;

while(q→ next&&q → next → data

q=q→ next;//查找插入位置。

p→ next=q → next;//插入

q→ next=p;

p=r;

}//while

}//if

}//InsertSort_L

14.设计算法，判断一个以邻接表为存储结构的无向图G是否连通有，若连通，则返回1，否则，返回0。

int connect(ALGraph G){ //判断以邻接表为存储结构的无向图是否连通

flag=1;

for(i=0;i

for(i=0;i

if(visited[i]=0){ flag==0; breek; }

return flag;

}// connect

void dfs(ALGraph G,int visited[],int v){

//采用深度优先遍历的算法思想

visited[v]=1;

p=G.ver[v].firstarc;

while(p){

if(visited[p→adjvex]==0)

dfs(G,visited,p→ adjvex);

p=p→ next;

}//whike

}//dfs

数据结构与算法习题及答案

第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （1）在数据结构中，从逻辑上可以把数据结构分成（）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 （2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A．存储结构B．存储实现 C．逻辑结构D．运算实现 （3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。 A．数据具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位 C．数据结构是带有结构的各数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 （5）以下与数据的存储结构无关的术语是（）。 A．顺序队列B.链表C.有序表D.链栈 （6）以下数据结构中，（）是非线性数据结构 A．树B．字符串C．队D．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：

（1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。 线性表的顺序存储结构具有以下两个基本特点： （1）线性表中所有元素的所占的存储空间是连续的； （2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为：adr(ai)=adr(a1)+(i-1)k,，adr(a1)为第一个元素的地址，k代表每个元素占的字节数。 顺序表的运算：插入、删除。（详见14--16页） 4 栈和队列 栈是限定在一端进行插入与删除的线性表，允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。 栈按照“先进后出”（filo）或“后进先出”（lifo）组织数据，栈具有记忆作用。用top表示栈顶位置，用bottom表示栈底。 栈的基本运算：（1）插入元素称为入栈运算；（2）删除元素称为退栈运算；（3）读栈顶元素是将栈顶元素赋给一个指定的变量，此时指针无变化。 队列是指允许在一端（队尾）进入插入，而在另一端（队头）进行删除的线性表。rear指针指向队尾，front指针指向队头。 队列是“先进行出”（fifo）或“后进后出”（lilo）的线性表。 队列运算包括（1）入队运算：从队尾插入一个元素；（2）退队运算：从队头删除一个元素。循环队列：s=0表示队列空，s=1且front=rear表示队列满

数据结构与算法实验指导实验十

#include"stdio.h" #include"stdlib.h" #define NULL 0 #define maxsize 50 typedef struct node{ char data; struct node *lchild,*rchild; }Bitree; int a[maxsize]; int temp=0; Bitree *Q[maxsize]; Bitree *Creatree(){ char ch; int front,rear; Bitree *T,*S; T=NULL; front=1;rear=0; printf("建立二叉树,以@表示虚节点，以#结束输入:\n"); ch=getchar(); while(ch!='#'){ S=NULL; if(ch!='@'){ //@表示虚节点不是虚节点是建立新节点 S=(Bitree *)malloc(sizeof(Bitree)); S->data=ch; S->lchild=S->rchild=NULL; } rear++;Q[rear]=S; //将虚节点指针NULL或新节点地址入队 if(rear==1) T=S; //输入第一个节点为根节点 else{ if(S!=NULL&&Q[front]!=NULL) if(rear%2==0) Q[front]->lchild=S; else Q[front]->rchild=S; if(rear%2==1) front++; //节点Q[front]的两个孩子已经处理完毕，front+1 } ch=getchar(); } return T; } void Inorder(Bitree *T){ //中序遍历二叉树，并将每个结点数据存入数组中if(T!=NULL){ Inorder(T->lchild);

算法与数据结构试题及答案

数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。

算法与数据结构实验

学生实验报告册 （理工类） 课程名称：算法与数据结构专业班级 学生学号：学生： 所属院部：计算机工程学院指导教师：章海鸥 2016 ——2017 学年第 1 学期 金陵科技学院教务处制 实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸一律采用 A4的纸。

实验报告书写说明 实验报告中一至四项容为必填项，包括实验目的和要求；实验仪器和设备；实验容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课程的实验大纲。

实验项目名称：顺序表实验学时： 2 同组学生：╱实验地点： 实验日期：实验成绩： 批改教师：批改时间：

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 VC6.0 三、实验容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个顺序表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将 新结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。 程序清单： (1) #include #define maxsize 20 typedef int datatype; typedef struct{ datatype data[maxsize];

数据结构与算法复习题库含答案

数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。

算法与数据结构实验册

实验报告书写要求 实验报告原则上要求学生手写，要求书写工整。若因课程特点需打印的，要遵照以下字体、字号、间距等的具体要求。纸张一律采用A4的纸张。 实验报告书写说明 实验报告中一至四项内容为必填项，包括实验目的和要求；实验仪器和设备；实验内容与过程；实验结果与分析。各院部可根据学科特点和实验具体要求增加项目。 填写注意事项 （1）细致观察，及时、准确、如实记录。 （2）准确说明，层次清晰。 （3）尽量采用专用术语来说明事物。 （4）外文、符号、公式要准确，应使用统一规定的名词和符号。 （5）应独立完成实验报告的书写，严禁抄袭、复印，一经发现，以零分论处。 实验报告批改说明 实验报告的批改要及时、认真、仔细，一律用红色笔批改。实验报告的批改成绩采用百分制，具体评分标准由各院部自行制定。 实验报告装订要求 实验批改完毕后，任课老师将每门课程的每个实验项目的实验报告以自然班为单位、按学号升序排列，装订成册，并附上一份该门课 程的实验大纲。

实验项目名称：顺序表实验学时： 2 同组学生姓名：全班同学实验地点： 1318 实验日期： 10 月14号实验成绩： 批改教师：批改时间：

实验1 顺序表 一、实验目的和要求 掌握顺序表的定位、插入、删除等操作。 二、实验仪器和设备 Turbo C 2.0 三、实验内容与过程（含程序清单及流程图） 1、必做题 （1）编写程序建立一个数续表，并逐个输出顺序表中所有数据元素的值。 编写主函数测试结果。 （2）编写顺序表定位操作子函数，在顺序表中查找是否存在数据元素x。 如果存在，返回顺序表中和x值相等的第1个数据元素的序号（序号 从0开始编号）；如果不存在，返回－1。编写主函数测试结果。 （3）在递增有序的顺序表中插入一个新结点x，保持顺序表的有序性。 解题思路：首先查找插入的位置，再移位，最后进行插入操作；从第 一个元素开始找到第一个大于该新结点值x的元素位置i即为插入位 置；然后将从表尾开始依次将元素后移一个位置直至元素i；最后将新 结点x插入到i位置。 （4）删除顺序表中所有等于X的数据元素。 2、选做题 （5）已知两个顺序表A和B按元素值递增有序排列，要求写一算法实现将A和B归并成一个按元素值递减有序排列的顺序表（允许表中含有值 相同的元素）。 程序清单： 第一题： #include #define maxsize 100 typedef struct{ int datatype [maxsize]; int last; }sequenlist; void main(){ sequenlist a={{1,2,3,4},4}; for(int i=0;i

计科本科生《算法与数据结构》实验报告4

学院专业姓名学号 实验1：约瑟夫环问题（3学时） [问题描述] 将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。 [实验目的] （1）掌握线性表的顺序存储结构和循环顺序存储结构。 [实验内容及要求] （1）构造数据结构。 （2）对线性表进行初始化。 [测试数据] 输入一组n，m值时，程序输出出列顺序。 [思考] （1）你采用的存储结构是顺序表还是循环顺序表？哪个比较合适？ （2）当存储结构为循环链表时，如何修改你的程序？并考虑两种存储结构的优缺点。

学院专业姓名学号 实验2：ADT List（线性表）（3学时） [问题描述] 线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算或并运算。[实验目的] （1）掌握线性表的链表存储结构。 （2）掌握在单链表上基本操作的实现。 （3）在掌握单链表的基本操作上进行综合题的实现。 [实验内容及要求] （1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。 （2）集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。 （3）显示两个集合的内容及其运算结果。 [测试数据] （1）set1={3, 8, 5, 8,11}，set2={22, 6, 8, 3, 15,11,20 } set1∪set2＝ set1∩set2＝ （2）set1={1, 3, 5, 7}，set2={2, 3, 7, 14, 25,38} set1∪set2＝ set1∩set2＝

算法与数据结构习题

《算法与数据结构》习题1 第一部分 一、单项选择题 1.（）二叉排序树可以得到一个从小到大的有序序列。 A、先序遍历 B、中序遍历 C、后序遍历 D、层次遍历 2.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i 结点的左孩子结点的编号为（）。 A、2i+1 B、2i C、i/2 D、2i-1 3.设指针变量p指向单链表中结点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)； 4.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得 到序列为（）。 A、BADC B、BCDA C、CDAB D、CBDA 5.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。 A、n B、n-1 C、m D、m-1 6.设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 A、O(1) B、O(log2n) C、O(nlog2n) D、O(n2) 7.设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A、25 B、10 C、7 D、1 二、填空题 1.设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A 的后面插入结点X的操作序列为______=p；s->right=p->right；______=s； p->right->left=s；（设结点中的两个指针域分别为left和right）。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为______。 3.设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为 3的结点数有______个。 4.后缀算式9 2 3 + - 10 2 / -的值为______。中缀算式（3+4X）-2Y/3对应的后缀算式 为______。 5.设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元 素开始进行筛选。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点

数据结构与算法复习题及参考答案

复习题集─参考答案 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 （×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 （√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续存空间时，为提高存利用率，减少溢出机会，应把两个栈的栈底分别设在这片存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] （×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] （√）28.树形结构中每个结点至多有一个前驱。 （×）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。 （×）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。 （×）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。 （×）32.顺序查找方法只能在顺序存储结构上进行。 （×）33.折半查找可以在有序的双向链表上进行。

数据结构与算法的实验报告

数据结构与算法第二次实验报告 电子105班 赵萌 2010021526

实验二：栈和队列的定义及基本操作 一、实验目的： . 熟练掌握栈和队列的特点 . 掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用 . 掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作 . 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力 二、实验内容: 定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素; 实现十进制数与八进制数的转换; 定义链式队列，完成队列的基本操作：入队和出队; 1．问题描述： （1）利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作： . 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; . 完成一个元素的入栈操作，修改栈顶指针; . 完成一个元素的出栈操作，修改栈顶指针; . 读取栈顶指针所指向的元素的值; . 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除 d 取余法。例如：（1348）10=（2504）8 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 从中我们可以看出，最先产生的余数 4 是转换结果的最低位，这正好符合栈的特性即后进先出的特性。 所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换; . 编写主程序，实现对各不同的算法调用。 （2）利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作： . 初始化一个空队列，形成一个带表头结点的空队; . 完成一个元素的入队操作，修改队尾指针; . 完成一个元素的出队操作，修改队头指针; . 修改主程序，实现对各不同的算法调用。

算法与数据结构试题及答案

数据结构模拟试题... 一、简答题（15分，每小题3分） 1.简要说明算法与程序的区别。 2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？ 3.说明在图的遍历中，设置访问标志数组的作用。 4.说明以下三个概念的关系：头指针，头结点，首元素结点。 5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？ 二、判断题（10分，每小题1分） 正确在括号内打√，错误打× ( )（1）广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。 ( )（2）在哈夫曼树中，权值最小的结点离根结点最近。 ( )（3）基数排序是高位优先排序法。 ( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。 ( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next = s; s->next = p->next; ( )（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。 ( )（7）数组元素的下标值越大，存取时间越长。 ( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。 ( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 ( )（10）长度为1的串等价于一个字符型常量。 三、单项选择题（10分, 每小题1分） 1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序 B、直接插入排序 C、快速排序 D、冒泡排序 2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该： A）将邻接矩阵的第i行删除B）将邻接矩阵的第i行元素全部置为0 C）将邻接矩阵的第i列删除D）将邻接矩阵的第i列元素全部置为0 3．有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是： A.head->priro==NULL B. head->next==NULL C. head->next==head D. head->next-> priro==NULL 4. 在顺序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比

数据结构与算法实验报告册

. . 河南工程学院 理学院学院 实验报告 （数据结构与算法） 学期: 课程: 专业: 班级: 学号: 姓名: 指导教师:

. . 目录 实验一线性表1（顺序表及单链表的合并） (1) 实验二线性表2（循环链表实现约瑟夫环） (1) 实验三栈和队列的应用（表达式求值和杨辉三角） (1) 实验四赫夫曼编码 实验五最小生成树 (1) 实验六排序算法

. . 实验一线性表1 一、实验学时：2学时 二、实验目的 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系。在计算机中 表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。 2.熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储 结构上的实现。 三、实验内容 1. 编写程序，实现顺序表的合并。 2. 编写程序，实现单链表的合并。 四、主要仪器设备及耗材 硬件：计算机一台 软件：VC++ 6.0，MSDN2003或者以上版本 五、算法设计 1. 顺序表合并的基本思想 程序流程图： 2. 单链表合并的基本思想 程序流程图 六、程序清单

. 七、实现结果 .

. 八、实验体会或对改进实验的建议.

. . 实验二线性表2 一、实验学时：2学时 二、实验目的 1.了解双向循环链表的逻辑结构特性，理解与单链表的区别与联系。 2.熟练掌握双向循环链表的存储结构以及基本操作。 三、实验内容 编写程序，采用循环链表实现约瑟夫环。 设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。 四、主要仪器设备及耗材 硬件：计算机一台 软件：VC++ 6.0，MSDN2003或者以上版本 五、算法设计 约瑟夫环实现的基本思想 程序流程图： 六、程序清单

数据结构实验报告全集

数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include >验目的 掌握顺序栈的基本操作：初始化栈、判栈空否、入栈、出栈、取栈顶数据元素等运算以及程序实现方法。 2.实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）分析问题的要求，编写和调试完成程序。 （3）保存和打印出程序的运行结果，并分析程序的运行结果。 3.实验内容 利用栈的基本操作实现一个判断算术表达式中包含圆括号、方括号是否正确配对的程序。具体完成如下：

（1）定义栈的顺序存取结构。 （2）分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。 （3）定义一个函数用来判断算术表达式中包含圆括号、方括号是否正确配对。其中，括号配对共有四种情况：左右括号配对次序不正确；右括号多于左括号；左括号多于右括号；左右括号匹配正确。 （4）设计一个测试主函数进行测试。 （5）对程序的运行结果进行分析。 实验代码： #include < > #define MaxSize 100 typedef struct { int data[MaxSize]; int top; }SqStack;

数据结构与算法基础

数据结构与算法基础 一．判断题： 1．数据元素是数据的最小单位。 2．数据结构是带有结构的数据元素的集合。 3．数据结构、数据元素、数据项在计算机中的映像（或表示）分别称为存储结构、结点、数据域。 4．数据项是数据的基本单位。 5．数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的。 6．数据的物理结构是指数据在计算机内实际的存储形式。 7．算法和程序没有区别，所以在数据结构中二者是通用的。 答案： 1．错误 2．正确 3．正确 4．错误 5．正确 6．正确 7．错误 二． 数据结构是研究数据的 A 和 B 以及它们之间的相互关系，并对这种结构定义相应的 C ，设计出相应的 D ，而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案： A、Ｂ：ａ理想结构ｂ抽象结构ｃ物理结构ｄ逻辑结构 Ｃ、Ｄ、Ｅ：ａ运算ｂ算法ｃ结构ｄ规则ｅ现在的ｆ原来的 答案： Ａ：ｃＢ；ｄＣ：ａＤ：ｂＥ：ｆ 三．从供选择的答案中选取正确的答案填在下面叙述中的横线上： 1． A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成，在这种情况下，称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合，是数据的子集。 4. Ｆ是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为Ｇ。 6. 算法的计算量的大小称为计算的Ｈ。 供选择的答案： Ａ－Ｆ：ａ数据元素ｂ符号ｃ记录ｄ文件ｅ数据ｆ数据项ｇ数据对象ｈ关键字ｉ数据结构

算法与数据结构练习题

《算法与数据结构》习题1 一、单项选择题 1. 数据结构从逻辑上分为（）。 A．动态结构和静态结构 B．内部结构和外部结构 C．紧凑结构和非紧凑结构 D．线性结构和非线性结构 2. 栈和队列的共同点是（）。 A．都是先进后出 B．都是后进先出 C．只允许在端点处插入和删除元素 D．没有共同点 3．若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素，然后结合栈的操作，能得到下列序列中的哪些序列？（） A．decfbga B．fegdacb C．efdgbca D．dcbefag 4. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点 s，则执行（）。 A．s→link=p→link；p→link =s；

B．p→link =s；s→link=q； C．p→link=s→link；s→link =p； D．q→link =s；s→link=p； 5．算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 6. 一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C 7. 从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8. 以下数据结构中，哪一个是线性结构？（） A．广义表 B. 二叉树 C. 稀疏矩阵

D. 串 二、多项选择题 1. 以下说法正确的是（）。 A. 二叉树的特点是每个结点至多只有两棵子树 B. 二叉树的子树无左右之分 C. 二叉树只能进行链式存储 D. 树的结点包含一个数据元素及若干指向其子树的分支2．在数组上能做的操作有（）。 A.插入 B.删除 C.取值操作 D.赋值操作 3. 图的应用算法有（）。 A. 克鲁斯卡尔算法 B. 哈弗曼算法 C. 迪杰斯特拉算法 D. 拓扑排序算法 4. 计算机算法必须具备（）等特性。 A. 可行性、确定性 B. 可行性、可移植性 C. 输入、输出

数据结构和C++程序设计_题库

《数据结构》 Part1 一．选择 1. 组成数据的基本单位是（） A）数据项B）数据类型C）数据元素D）数据变量 2．算法分析的目的是（） A）找出数据结构的合理性B）研究算法的输入/输出关系 C）分析算法的效率以求改进D）分析算法的易读性 3．在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）A）O(1) B）0(n) C）O(n^2) D）O(nlog2n) 4．若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100，则第12个元素的存储地址是（） A）112 B）144 C）148 D）412 5．下面关于线性表的叙述中，错误的是（） A）顺序表使用一维数组实现的线性表B）顺序表必须占用一片连续的存储单元. C）顺序表的空间利用率高于链表D）在单链表中,每个结点只有一个链域. 6．在需要经常查找结点的前驱与后继的情况下，使用（）比较合适 A）单链表B）双链表C）顺序表D）循环链表 7．队列通常采用的两种存储结构是（） A）顺序存储结构和链式存储结构B）散列方式和索引方式 C）链表存储结构和线性存储结构D）线性存储结构和非线性存储结构 8．在一个单链表中，若删除p所指结点的后继结点，则执行（） A）p->next=p->next->next；B）p=p->next；p->nex=p->next->next； C）p->next=p->next；D）p=p->next->next； 9．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间 A）单链表B）仅有头指针的单循环链表C）双链表D）仅有尾指针的单循环链表 10．按二叉树的定义，具有三个结点的二元树共有（）种形态。 A）3 B）4 C）5 D）6 11．任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）A）发生改变B）不发生改变C）不能确定D）以上都不对12．深度为5的二叉树至多有（）个结点 A）16 B）32 C）31 D）10 13．在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，那么度为0的结点数为（）个。 A）4 B）5 C）6 D）7 14．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组(顶点表)的大小为（） A）n B）n+1 C）n-1 D）n/2 15．静态查找表和动态查找表二者的根本差别在于（）

全国计算机二级第1章数据结构与算法

考点1 算法的复杂度 【考点精讲】 1．算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征：可行性、确定性、有穷性、拥有足够的情报。 2．算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1．逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成 B=（D，R） 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。例如，如果把一年四季看作一个数据结构，则可表示成 B =（D,R） D ={春季，夏季，秋季，冬季} R ={（春季，夏季）,（夏季，秋季），（秋季，冬季）} 2．存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构（也称数据的物理结构）。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此，为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系（即前后件关系），在数据的存储结构中，不仅要存放各数据元素的信息，还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接等存

储结构。 顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域，用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为两大类型：线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构，则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1．栈的基本概念 栈（stack）是一种特殊的线性表，是限定只在一端进行插入与删除的线性表。在栈中，一端是封闭的，既不允许进行插入元素，也不允许删除元素；另一端是开口的，允许插入和删除元素。通常称插入、删除的这一端为栈顶，另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素，从而也是最先被删除的元素；栈底元素总是最先被插入的元素，从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如，枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的，最后被压入弹匣的子弹总是最先被弹出，而最先被压入的子弹最后才能被弹出。 2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素。 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素。 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量。 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1．队列的基本概念 队列是只允许在一端进行删除，在另一端进行插入的顺序表，通常将允许删除的这一端称为队头，允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的，因此队列也称为先进先出的线性表，或者后进后出的线性表。例如：火车进遂道，最先进遂道的是火车头，最后是火车尾，而火车出遂道的时候也是火车头先出，最后出的是火车尾。若有队列： Q =（q1，q2，…，qn） 那么，q1为队头元素（排头元素），qn为队尾元素。队列中的元素是按照q1，q2，…，qn 的顺序进入的，退出队列也只能按照这个次序依次退出，即只有在q1，q2，…，qn-1 都退队之后，qn才能退出队列。因最先进入队列的元素将最先出队，所以队列具有先进先出的