.
算法与数据结构复习题
一、单选题
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．23415 B．54132 C.23145 D.15432
9．设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是(B)。
A．2 B．3 C.5 D.6
10．设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为(B)。A．4 B．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+1 D．不确定
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.任一结点无右孩子
13
/ 1
.
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）。
D.V1V3V4V5V2
C.V1V4V3V5V2 A.V1V2V3V4V5 B.V1V2V3V5V4
．以下说法不正确的是(D)。21 A．无向图中的极大连通子图称为连通分量 B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索的左、右孩，并已知A)．在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子的不平衡点是A22 (B)。子的平衡因子分别为-1和0，则应进行的平衡旋转是 RR型型 D． B．LR型 C．RLLLA．型，四个，现将关键字8438，61，14，哈希函数H(key)=key％11，表中已有数据的关键字为15，23．设哈希表长为。49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是(A)为9
5 ．D．．8 B．3 CA ．对散列文件，以下说法错误的是(D)。24 A．散列文件插入、删除方便，不需要索引区且节省存储空间 B．散列文件只能按关键字随机存取且存取速度快 C．经过多次插入、删除后，可能出现溢出桶满的情况 D．散列文件顺序存取方便）。18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为（D26．对有3
，2，，，53 D.9，4．2B.9，A.12，3 ，5，，3 C9，的左孩子的平衡因子为027．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A 。1，则应调整以使其平衡，所作的平衡旋转是（C）右孩子的平衡因子为型型B.LR C.RL型D.RR A.LL型。Bn28．在个结
点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）13
/ 2
.
2)
n) D.O(nA.O(n) B.O(logn) C.O(nlog22(A)。29．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是 D．堆C．快速 A．插入 B．选择
。树和B树的叙述中，不正确的结论是30．下面关于B-+ B树都能有效地支持顺序查找．B
+ (A)
树和A-+ B树都能有效地支持随机查找．B树和B-+ B树都是平衡的多叉树．B树和C-+ B树都可用于文件索引结构．B树和D-。(B)31．关键路径是事件结点网络中．最短的回路．最长的回路 D．从源点到汇点的最长路径 B．从源点到汇点的最短路径 CA 。n个元素的有序表归并成一个有序表，其最少的比较次数是(A)32．将两个各有n-1
．．2n DA．n B．2n-1 C 。的是（A）33．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlogn)2快速排序直接选择排序 D. B.冒泡排序 C.A.堆排序）34．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（D 直接插入排序 D.冒泡排序 B. C.快速排序A.堆排序。A）中有10000个元素，如果仅要求求出其中最大的10个元素，则采用最节省时间的排序算法是（35．数据表A 直接选择排序 D.B.希尔排序 C.快速排序A.堆排序。）），其中D 是（36．数据结构被形式地定义为（D,R 数据关系的集合 D.操作的集合 C.数据元素的集合A.算法 B. 。A）37．顺序表是线性表的（ D.散列存储结构链式存储结构顺序存储结构 B. C.索引存储结构A. ）。之后插入结点*s，则执行操作（B38．在一个
单链表中，已知*p结点不是最后结点，若在*pB.s->next=p->next;p->next=s
A.s->next=p;p->next=s;
D.p->next=s;s->next= p ;
C.s->next=p->next;p=s;
(A)。front和rear分别表示队头及队尾，则循环队列满的条件是39．循环队列A[O..m-1]存
放其元素值，用Q.rear==Q.front+1 B．(Q.rear+1)％m==Q.front A．Q.real==Q.front D．．Q.rear+l=Q.front C ( B )。40．如果以链栈为存储结构，则出栈操作时 D.不必作任何判别 C.判别栈中元素类型 A．必须判栈满 B．必须判别栈空。41．对矩阵压缩存储是为了(B) 提高运算速度方便存储 D.方便运算 B.节省空间 C.A.个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为10042．将一棵有。的结点的左孩子编号
为（B）1，则编号为49D.48
C.50 A.98 B.99
。D）43．二义树在线索化后，仍不能有效求解的问题是（中序线索二叉树中求中序后继 B.A.先序线索二叉树中求先序后继后序线索二又树中求后序后继 D.C.中序线索二叉树中求中序前趋）。，100)，用筛选法建堆，则开始结点的键值必须为（C，60，157，18，25，44．对于关键字序列(12，1311，18，D.15
B.12
C.60 A.100
，
，d，e，aceC．a，，b，，f, d D．。用邻接表存储，则拓扑排序的时间复杂度为(B )．设图46G ×e)0(nn) DO(n+e) CD(n) BA．．．O(n×．13
/ 3
.
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中有弧
C．G中没有弧
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 )。已知二叉树有50个叶子结点，则该二叉树的总结点数至少是（99）。将一棵有100个结点的完全二叉树从根这一层13
/ 4
.
开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩
子编号为（98 ）。有64个结点的完全二叉树的深度为( 7 )。
16．拓扑排序只能用于（有向无环图）。连通图是指图中任意两个顶点之间（都连通的无向图）。一个有n个顶点的无向连通图，它所包含的连通分量个数最多为( 1 )个。任何一个无向连通图的最小生成树（有一棵或多棵）。若含有n个顶点的图形成一个环，则它有（n）棵生成树。
（prim（普里姆））算法适合于求稠密图的最小生成树，（kruskal 17．求图的最小生成树有两种算法，
（克鲁斯卡尔））算法适合于求稀疏图的最小生成树。设图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(logn) ）次。
．贪心算法的基本思想是，逐步构造最优解，每步都按照一定的标准，称为（贪心）准则，225
做出决策。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为叶子结点数，n为度为k的结点数，n为结点总数（依题意：n=n+n(1) n= kn+1 (2)
(1) 和(2)得： n=n-(n-1)/k
kok ok—综合
设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k,
o30.
最好采用什么排序方法？为什么？如有这样一个序列：{59,11,26,34,17,91,25}，得到的部分序列是{11,17,25}，对于该例使用所选择的方法实现时，共执行多少次比较？
（1）采用堆排序最合适，因为当部分序列较小时，堆排序的时间复杂度近似为O(n)。
13
/ 5
.
（2）初始建堆：比较8次输出11,第一次调整：比较４次输出17
第二次调整：比较2次输出 25,总共比较14次。
31. 设二叉排序树中关键字由1至1000的整数组成，现要查找关键字为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）画出该树的后序线索树。（略）
1 2 3 4 5 6 7 8 9 10 11
2．按顺序输入下列顶点对: (1,2)、(1,6)、(2,6)、
A C
B E D (1,4)、(6,4)、(1,3)、(3,4)、(6,5)、(4,5)、(1,5)、(3,5)，
（1）画出相应的邻接表。
（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS序列和DFS生成树。
（1）邻接表
0 V1 4 2 3 5 1 ∧
V2 1 5 0 ∧
2 V
3
4 3 0 ∧V4 3 4 2
5 0 ∧
4 V5
2 0
3 5 ∧ 5
V6 4 3 1 0 ∧13
/ 6
.
2-0-1-5-3-4
（2）DFS序列H(key)=key,
3．设一哈希表长为13，采用线性探测法解决冲突，哈希函数后的哈希表。72，675220）画出
在空表中依次插入关键字25，，36，15，41，，29，（1 ）求在等概率情况下，查找成功和查找不
成功的平均查找长度。（2 100 101 102 103 104 105 106 107 108 109 110 111 112
）（125
36
52
15
41
29
67
20
72
）平均查找长度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 查找不成功的平均查找长度，采用线性探测再散列解，4025，26，36，370.8），若查找表的装填因子为．对下面的关键字
集（430，15，21，（）设计哈希函数；2）画出哈希表；决冲突：（1 H(key)=key%7 α=8/0.8
数据结构与算法基础知识总结 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表示队列满
《数据结构与算法设计》 实验报告 ——实验一 学院： 班级： 学号： 姓名：
一、实验目的 第一题利用单向环表实现约瑟夫环。 第二题归并顺序表。 二、实验内容 第一题采用单向环表实现约瑟夫环。 请按以下要求编程实现： ①从键盘输入整数m，通过create函数生成一个具有m个结点的单向环表。环表中的结点编号依次为1，2，……，m。 ②从键盘输入整数s（1<=s<=m）和n，从环表的第s个结点开始计数为1，当计数到第n个结点时，输出该第n结点对应的编号，将该结点从环表中消除，从输出结点的下一个结点开始重新计数到n，这样，不断进行计数，不断进行输出，直到输出了这个环表的全部结点为止。 例如，m=10，s=3，n=4。则输出序列为：6，10，4，9，5，2，1，3，8，7。 第二题选作：归并顺序表。 请按以下要求编程实现： ①从键盘输入两个升序排列的整数序列linka和linkb，每个序列以输入0为结束标记。 ②将链表linka和linkb归并为linkc，linkc仍然为升序排列。归并完成后，linka 和linkb为空表。输出linkc。 ③对linkc进行处理，保持升序不变，删除其中重复的整数，对重复的整数只保留一个，输出删除重复整数后的链表。 例如：linka输入为：10 20 30 40 50 0 linkb输入为：15 20 25 30 35 40 45 50 0 归并后的linkc为：10 15 20 20 25 30 30 35 40 40 45 50 50 删除重复后的linkc为：10 15 20 25 30 35 40 45 50 三、程序设计 1、概要设计 第一题为了实现程序功能，应当建立单向环表来寄存信息及结点，通过查找结
第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 算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储（B）个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点？（A） A．存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n]，假设A[0][0]存放位置在600 (10)，A[3][3]存放位置在678 (10) ， 每个元素占一个空间，问A[2][3] (10)存放在什么位置？(脚注 (10) 表示用10进制表示,m>3)C A．658 B．648 C．633 D．653 下列关于二叉树遍历的叙述中，正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B．若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C．若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D．若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找，其前提条件是( C). A.线性表以链接方式存储，并且按关键码值排好序 B.线性表以顺序方式存储，并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储，并且按关键码值排好序 D. 线性表以链接方式存储，并且按关键码值的检索频率排好序 对n个记录进行堆排序，所需要的辅助存储空间为（C） A. O（1og2n） B. O（n） C. O（1） D.O（n2） 对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（D）个， A．1 B．2 C．3 D．4 下列关于数据结构的叙述中，正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时，一般不考虑（ A ）。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（B）。A．单链表B．静态链表C．线性链表D．顺序存储结构 设指针变量p指向单链表中结点A，若删除单链表中结点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)； 数据结构与算法设计知识点 试题类型： 本课程为考试科目（闭卷笔试），试题类型包括：概念填空题（10 %），是非判断题（10 %），单项选择题（40 %），算法填空题（10%），算法应用题（20 %)，算法设计题（10 %）。 第一章绪论 重点内容及要求： 1、了解与数据结构相关的概念（集合、数据、数据元素、数据项、关键字、元 素之间的关系等）。 数据：所有能被输入到计算机中，且能被计算机处理的符号的 集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定 的符号表示形式。 数据元素：是数据（集合）中的一个“个体”，数据结构中的基本 单位，在计算机程序中通常作为一个整体来考虑和处理。 数据项：是数据结构中讨论的最小单位，数据元素可以是一个或 多个数据项的组合 关键码：也叫关键字（Key），是数据元素中能起标识作用的数 据项。 其中能起到唯一标识作用的关键码称为主关键码（简称主码）； 否则称为次关键码。通常，一个数据元素只有一个主码，但可以有多 个次码。 关系：指一个数据集合中数据元素之间的某种相关性。 数据结构：带“结构”的数据元素的集合。这里的结构指元素之 间存在的关系。 数据类型：是一个值的集合和定义在此集合上的一组操作的总 称。 2、掌握数据结构的基本概念、数据的逻辑结构（四种）和物理结构（数据元素 的表示与关系的表示、两类存储结构：顺序存储结构和链式存储结构）。 数据结构包括逻辑结构和物理结构两个层次。 数据的逻辑结构：是对数据元素之间存在的逻辑关系的一种抽象的描述，可以用一个数据元素的集合和定义在此集合上的若干关系来表示 逻辑结构有四种：线性结构、树形结构、图状结构、集合结构数据的物理结构：是其逻辑结构在计算机中的表示或实现，因此又称其为存储结构。 存储结构：顺序存储结构和链式存储结构 顺序存储结构：利用数据元素在存储器中相对位置之间的某种特定的关系来表示数据元素之间的逻辑关系； 链式存储结构：除数据元素本身外，采用附加的“指针”表示数据元素之间的逻辑关系。 3、了解算法分析的基本方法，掌握算法时间复杂度相关的概念。 算法：是为了解决某类问题而规定的一个有限长的操作序列 或处理问题的策略 一个算法必须满足以下五个重要特性：1．有穷性2．确定性3．可行性4．有输入5．有输出 设计算法时，通常还应考虑满足以下目标： 1.正确性， 2.可读性， 3.健壮性 4.高效率与低存储量需求 数据结构试卷（一） 一、单选题（每题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条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 复习题集─参考答案 一判断题 （√）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.折半查找可以在有序的双向链表上进行。 烟台大学计算机学院课程设计（算法与数据结构） 设计题目： 班级 姓名 学号 指导教师 成绩 二○一三年四月十日 内容包括： 一、课程设计题目： 二、课程设计内容： 三、算法设计： 四、程序正确性验证（指边界测试数据，即程序对于精心选择的典型、苛刻 而带有刁难性的几组输入数据能够得出满足要求的结果）： 五、课程设计过程中出现的主要问题、原因及解决方法： 六、课程设计的主要收获： 七、对今后课程设计的建议： 算法与数据结构课程设计题目 一、单项分值：25分 1、约瑟夫环游戏 2、八皇后问题(图形表示加20分) 3、表达式的求值问题 4、迷宫问题(图形表示加10分) 二、单项分值：80分 5、HTML文档标记匹配算法 要求：输入一段HTML代码，判断该代码是否符合HTML的语法 提示：HTML文档由不同的标记划分为不同的部分与层次。与括号类似，这些标记需要成对出现，对于名为算法与数据结构复习资料
数据结构与算法设计知识点
算法与数据结构试题及答案
数据结构与算法复习题及参考答案
《算法与数据结构》课程设计报告书
:节的头部 ●
数据结构复习题 第一章概论 一、选择题 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)。
数据结构与方法 1、算法的基本特征:可行性、确定性、有穷性、拥有足够的情报 2、算法的基本运算与操作:算术运算、逻辑运算、关系运算、数据传输 3、算法的基本控制结构:顺序结构、选择结构、循环(重复)结构 4、算法设计的基本方法:列举法、归纳法、递推、递归、减半递推技术、回溯法 5、算法的复杂度主要包括:时间复杂度、空间复杂度 6、算法的时间复杂度:指执行算法所需要的计算工作量 7、算法的空间复杂度:指执行这个算法所需要的内存空间 8、数据结构主要研究:数据的逻辑结构、数据的存储结构、对各种数据结构进行的运算 9、数据结构研究的目的:提高数据处理的效率 10、数据处理的效率:数据处理的速度、减少处理过程中占用计算机的存储空间 11、数据处理:指对数据集合中的各元素以各种方式进行运算 12、数据元素:指在数据处理中,每一个需要处理的对象都可以抽象成数据元素 13、数据结构:指反映数据元素之间关系的数据元素集合的表示 14、数据的逻辑结构:指反映数据元素之间逻辑关系的数据结构,两要素:数据元素的集合、数据元素在集合上的关系 15、数据的存储结构:指数据的逻辑结构在计算机存储空间的存放形式,常用的存储结构有:顺序、链接、索引等 16、数据结构的图形表示中每个元素加上方框成为结点 17、数据结构一般分为:线性结构、非线性结构 18、线性结构满足:有且仅有一个根结点、每个结点最多有一个前件与后件、在一个线性结构中插入与删除任何一个结点后还就是线性结构 19、线性表定义:线性表就是由n个数据元素a1、a2、a3、a4……an组成的一个有限序列,表中每一个数据元素,除了第一个外,有且仅有一个前件,除了最后一个外,有且仅有一个后件20、非线性表的特征:有且只有一个根节点a1,它无前件、有且只有一个终结点an,它无后件、除了第一个与最后一个外,其她所有结点只有一个前件与一个后件 21、线性表的长度:线性表中的结点的个数n成为线性表的长度,当n=0时,成为空表 22、线性表的顺序存储的特点:所有元素所占的存储空间就是连续的、各数据元素在存储空间中就是按逻辑顺序一次存放的 23、线性表的随机存取地址计算公式:ADD(ai)=ADD(a1)+(i-1)*k 24、线性表的主要操作:插入、删除、查找、排序、分解、合并、复制、逆转 25、栈的定义:栈就是限定在一端进行插入与删除的线性表,它按照“先进后出,后进先出”的原则组织数据 26、栈的顺序存储:在程序设计语言中,一般一维数组S(1:m)作为栈的顺序存储空间,其中m 为栈的最大容量 27、栈的基本运算:入栈、退栈、读栈顶元素 28、入栈运算:首先将栈顶指针(top)加1,然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,称为“上溢”错误 29、退栈运算:首先将栈顶元素赋给一个指定的变量,然后将栈顶指针(top)减1。当栈顶指针为0时,说明栈空,成为“下溢”错误 30、队列的定义:队列就是指允许在一端进行插入,而在另一端进行删除的线性表,它按照“先进先出”的原则组织数据 31、循环队列:在实际应用中,队列的顺序存储结构一般采用循环队列的形式。所谓循环队列,
《算法与数据结构》习题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. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。 【答案】 int count=0; void algo2(BTNode *bt){ if (bt){ if(bt->lchild || bt->rchild){ printf(bt->data); count++; } algo2(bt->lchild); algo2(bt->rchild); } } 2. 阅读下列函数arrange() int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t； i=1；j=h； while(i 数据结构模拟试题... 一、简答题（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，所需的关键码比 内江师范学院 数据结构与算法设计课程设计实验报告册 编制算法设计课题组审定曾意 数学与信息科学学院 2014年9月 1. 学生在做实验之前必须要准备实验，主要包括预习与本次实验相关的理论知识，熟练与本次实验相关的软件操作，收集整理相关的实验参考资料，要求学生在做实验时能带上充足的参考资料；若准备不充分，则学生不得参加本次实验，不得书写实验报告； 2. 要求学生要认真做实验，主要是指不得迟到、早退和旷课，在做实验过程中要严格遵守实验室规章制度，认真完成实验内容，极积主动地向实验教师提问等；若学生无故旷课，则本次实验等级计为D； 3. 学生要认真工整地书写实验报告，实验报告的内容要紧扣实验的要求和目的，不得抄袭他人的实验报告； 4. 实验成绩评定分为A+、A、A-、B+、B、C、D 各等级。根据实验准备、 实验态度、实验报告的书写、实验报告的内容进行综合评定，具体对应等级如下：完全符合、非常符合、很符合、比较符合、基本符合、不符合、完全不符 合 实验名称：算法设计基础实验(实验一) 指导教师：牟廉明，刘芳实验时数： 4 实验设备：安装了VC++计算机 实验日期：年_月_日实验地点：第五教学楼北802 实验目的： 掌握算法设计的基本原理，熟悉算法设计的基本步骤及其软件实现。 实验准备： 1. 在开始本实验之前，请复习相关实验内容； 2. 需要一台准备安装Windows XP Professional操作系统和装有VC++6.0的计算机。 实验内容： 求n至少为多大时，n个1组成的整数能被2013整除。 实验过程： 1.1算法思想 2013=61*33,6个1能够整除33,寻找满足n个1能够整除61的n即可。 1.2算法步骤 1?定义变量y储存余数，i储存1的个数，m为被除数，初始化为111111； 2?如果被除数能够除尽61,输出i; 如果被除数不能够除尽61，while继续循环，m=y*1000000+111111,i++; 3?重复2，直到找到满足条件的m为止，输出i; 1.3算法实现(C++程序代码) #in clude 数据结构与算法基础 一．判断题： 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. 输入、输出 《数据结构》 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．静态查找表和动态查找表二者的根本差别在于（）算法与数据结构试题及答案
数据结构与算法设计课程设计
数据结构与算法基础
算法与数据结构练习题
数据结构和C++程序设计_题库
相关主题
文本预览