数据结构复习题(2010)
数据结构期末复习题1（0907）一、基本要求
1．数据结构基本概念
（1）数据、数据对象和数据结构（逻辑、物理结构、基本操作）
（2）抽象数据类型
（3）算法的特征及评价的标准
2．线形结构
（1）顺序表的特点及存储结构
（2）链表的特点及存储结构
（3）栈的特点及基本操作
（4）队列的特点及基本操作
（5）顺序串和链串的存储结构
（6）二维数组的地址计算
（7）特殊矩阵的概念及存储结构（对称、三角、对角、稀疏）
（8）广义表的概念及存储结构
（9）线性表的排序（简单插入、选择和交换）
（10）线性表的查找（顺序、折半和分块索引）
3．树形结构
（1）二叉树的性质及存储结构（顺序、二叉链表、三叉链表）
（2）二叉树的遍历
（3）线索二叉树
（4）树的存储结构（双亲、孩子-双亲、孩子-兄弟链表）
（5）树、二叉树与森林的转化方法
（6）哈夫曼树
（7）二叉排序树及平衡化
（8）堆排序树
（9）树的等价类划分
4．图形结构
（1）图的定义及存储结构
（2）图的深度优先和广度优先遍历。
（3）图的连通性
（4）最小（代价）生成树
（5）拓扑排序
（6）关键路径
（7）最短路径（单源、顶点对）
5．查找表
（1）散列表的概念
（2）散列表解决散列冲突的方法（开放地址法、链地址法）
（3）散列表的插入和删除
（4）B_树的概念、存储结构及基本操作（查找、插入、删除）
6．排序方法
（1）希尔排序
（2）快速排序
（3）二路归并排序
（4）基数排序（链式、计数）
（5）排序方法比较和分析（时间性能、空间性能、稳定性）
二、单选题
1．要求具有同一逻辑结构的数据元素具有相同的特性，其含义为
A. 数据元素具有同一的特点
B.数据元素其对应的数据个数及数据项的类型要一致
C. 每个数据元素都一样
D. 仅需要数据元素包含的数据项的个数相同
2．在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q 和*p之间插入结点*s，则执行操作
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;
3．设指针p指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映
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;
4．表达式a*(b+c)--d的后缀表达式是
A．abcd*+- B．abc+*d-
C．abc*+d- D．-+*abcd
5．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
A．A，B，C，D B．D，C，B，A
C. A，C，D，B
D. D，A，B，C
6．设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A．4 B．5 C. 6 D. 7
7．若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3，…，pn，若pl是n，则pi是A．i B．n-i C．n-i+1 D．不确定
8．已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是
A．head(tail(LS))
B．tail(head(LS))
C．head(tail(head(tail(LS))))
D．head(tail(tail(head(LS))))
9．二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是
A．A[8，5] B．A[3，10]
C．A[5，8] D．A[0，9]
10．数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为
A. 1140
B. 1145
C. 1120
D. 1125
11．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点
B.高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
12．下列说法正确的是
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前
(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A．(1)(2)(3) B．(1)(2)
C．(1)(3) D．前面的可选答案都不对
13．下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错
14．树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A．树的后根遍历与其对应的二叉树的后根遍历相同
B．树的后根遍历与其对应的二叉树的中根遍历相同
C．树的先根遍历与其对应的二叉树的中根遍历相同
D．以上都不对
15．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是
A. V1V2V3V4V5
B. V1V2V3V5V4
C. V1V4V3V5V2
D. V1V3V4V5V2
16．以下说法不正确的是
A．无向图中的极大连通子图称为连通分量
B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过
的顶点
C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
D．有向图的遍历不可采用广度优先搜索
17．在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是
A．LL型B．LR型C．RL型D．RR型
18．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A．8 B．3 C．5 D．9
19．对散列文件，以下说法错误的是
A．散列文件插入、删除方便，不需要索引区且节省存储空间
B．散列文件只能按关键字随机存取且存取速度快
C．经过多次插入、删除后，可能出现溢出桶满的情况
D．散列文件顺序存取方便
20．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，
右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是
A. LL型
B. LR型
C. RL型
D. RR型
21．在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为
A. O(n)
B. O(log2n)
C. O(nlog2n)
D. O(n2)
22．下列排序算法中，在待排序数据已基本有序时，效率最高的排
序方法是
A．插入B．选择C．快速D．堆
23．关键路径是事件结点网络中
A．从源点到汇点的最长路径B．从源点到汇点的最短路径
C．最长的回路D．最短的回路
24．将两个各有n个元素的有序表归并成一个有序表，其最少的比
较次数是
A．n B．2n-1 C．2n D．n-1
25．下列排序算法中，时间复杂度不受数据初始状态影响，恒为
0(nlog2n)的是
A. 堆排序
B. 冒泡排序
C. 直接选择排序
D. 快速排序
26．数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用最节省时间的排序算法是
A. 堆排序
B. 希尔排序
C. 快速排序
D. 直接选择排序
27．在分块索引查找的索引表中查找，算法中采用的技术是
A. 穷举法
B. 贪心法
C. 分治法
D. 回溯法
28．有向图G用邻接矩阵A存储，则顶点i的入度等于A中
A. 第i行1的元素之和
B. 第i列1的元素之和
C. 第i行0的元素个数
D. 第i列非0的元素个数
三、问答题
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个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为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(log2n) ）次。
25．对于单链表、单循环链表和双向链表，若仅仅知道一个指向链表中某结点的指针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;
26．设有三对角矩阵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)）
27．内存中一片连续空间（不妨设地址从1到m），提供给两个栈S1和S2使用，怎样分配这部分存储空间，使得对任意一个栈，仅当这部分全满时才发生上溢。(为了尽量利用空间，减少溢出的可能，可采用栈顶相向，栈底分设两端的存储方式，这样，对任何一个栈，仅当整个空间全满时才会发生上溢。)
28．有一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
29. 设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中n>>k,最好采用什么排序
方法？为什么？如有这样一个序列：{59,11,26,34,17,91,25}，得到的部分序列是{11,17,25}，对于该例使用所选择的方法实现时，共执行多少次比较？
（1）采用堆排序最合适，因为当部分序列较小时，堆排序的时
间复杂度近似为O(n)。
（2）初始建堆：比较8次输出11,第一次调整：比较４次，
输出17
第二次调整：比较2次，输出25,总共比较14次。
30. 设二叉排序树中关键字由1至1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可
能是在二叉排序树中查到的序列？说明原因。
⑴51,250,501,390,320,340,382,363;
⑵24,877,125,342,501,623,421,363;
((1）是；⑵不是。因为查询序列是：查421时，其623左、
右两个区间都不存在，查找失败。)
31. 在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反方向的移动，从而认为该算法是不稳定
的，这种说法对么？为什么？
（不正确。算法的稳定性是考察最终排行的位置交换，与中间过程无关。如：对于整数序列（18，36，25）。
按基数排序的LSD方法，第一趟排序后（25，36，18），第二趟排序后得到（18，25，36），18虽向相反方向移动，但不影响最终位置。）
33. 将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树二叉链
表结构)。
四、应用题
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)、
(1,4)、(6,4)、(1,3)、(3,4)、(6,5)、(4,5)、(1,5)、(3,5)，
（1）画出相应的邻接表。
（2）写出在邻接表上，从顶点3开始（表下标从0开始）的DFS 序列和DFS 生成树。
（1）邻接表
（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） 100 101 102 103 104 105 106 107 108 109 110 111 112
（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）哈希表
0 1 2 3 4 5 6 7 8 9
5．写出对关键字序列
{503,087,512,061,908,124,897,275,653,426}建立一棵平衡二叉排序树的过程，并写出调整平衡时的旋转类型。
503 503
087 512 RL 087 897
061 124 908 061 124 512 908
897
503 503
087 897 RR 087 897
061 124 512 908 061 275 512 908
275 653 124 426 653
426
五、算法分析与设计题
1．设有一个正整数序列组成的非递减有序单链表，阅读下面的算
法，指出该算法的功能，并在“//后面加上必要的注释。
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小的数按递减次序排列。 2．假设一个仅包含二元运算符的算术表达式以二叉链表形式存储在二叉树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 算法功能：后序遍历二叉树，求算术表达式的值。 3．在有向图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 void DFS(ALGraph G,int v){ //从第v个顶点出发递归地深度优先遍历图G 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) ; 4．下面算法的功能是实现单链表中的简单选择排序，其中L为链表的头结点指针，请填空补全算法，并在“//”后面给以注释。 void F2(LinkList &L){//用单链表实现简单选择排序 p=L－>next; //初始化，p为工作指针 while(p){ min=p; (1)___________; // q为插入指针，min为当前最小指针 while((2)___________){ //一趟选择排序 if(q－>data 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！= p 5．设计算法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 6．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 7．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序（要求给出逆邻接表的存储结构定义）。 (1)存储结构定义 顶点结构 表结点结构 (2) 算法设计 int toposort (ALGraph G,int tpv[]){ //以逆邻接表为存储结构的有向图的拓扑排序 top=0; for(i=0;i for(p=G.adjlist*i+.firstedge;p;p→next) 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 8．已知深度为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 9．假设哈希函数为H（key）,编写用链地址法解决冲突的哈希表的 插入和删除算法。 void F2( HashTable &H, keytype Key){ //哈希表插入，用链地址法解决冲突 i=H(Key);;// 获取哈希地址 if(H[i]==Null){ s=(Linklist)malloc(sizeof(Lnode)); s→data=key; s→next=H*i+; H*i+=s; }//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 10．设有一个由正整数组成的无序单链表，阅读下面的算法，指出该算法的功能，并在“//”后面加上必要的注释。 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 算法功能：找出最小值结点，打印该数值。若该值是偶数且有 后继，则将其后继结点删除。 六、考题举例 （一）单选题 1．数据结构被形式地定义为（D,R），其中D 是 A. 算法 B. 操作的集合 C. 数据元素的集合 D. 数据关系的集合 2．在一个单链表中，已知*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 ; 3．循环队列A[O..m-1]存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是A．(Q.rear+1)％m==Q.front B．Q.rear==Q.front+1 C．Q.rear+l=Q.front D．Q.real==Q.front 4．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 A. 98 B. 99 C. 50 D. 48 5．关于散列法查找说法正确的是 A．采用链地址解决冲突时，查找一个元素的时间是相同的 B．采用链地址解决冲突时，若规定插入总是在链首，则插入 任一个元素的时间是相同的 C．采用链地址解决冲突容易引起聚集现象 D．再散列不易产生聚集 （二）填空题 1．在线性结构中，开始结点没有（）结点，最后一个元素没有（）结点。 2．数组A[l..10，1..10]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，6]的地址为（）。 3．求图的最小生成树有两种算法，( ) 算法适合于求稠密 图的最小生成树。 4．在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表的长度有关，而且与每一块中的元素（）有关。 5．分枝定界的搜索策略与广度优先类似，而回溯方法则采用 ( )搜索策略。 （三）应用题 1. 已知一棵二叉树的先序序列和中序序列分别为：abdgicefhj及bgidaecfjh，画出该的二叉树的后序线索二叉树。 2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。 （1）画出此哈夫曼树。 （2）若这些字符在电文中出现的频度分别为3、35、13、15、 20、5、9，求哈夫曼树的带权路径长度。 （四）算法阅读题 1. 已知二叉树的存储结构为二叉链表，LinkList和BiTree为已定义的指针类型，ListNode为已定义的结点类型，阅读下面算法并回答： LinkList L=Null; p; void F2(BiTree T){ if(T), F2(T→lchil d); 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. 设计算法，判断一个以邻接表为存储结构的无向图G是否连通有，若连通，则返回1，否则，返回0。 int connect(ALGraph G){ //判断以邻接表为存储结构的无向图是否连通 flag=1; for(i=0;i visited[i]=0; dfs(G,visited,0); 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→adj vex]==0) dfs(G,visited,p→adjvex); p=p→next; }//whike }//dfs 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 数据结构复习题 第一章概论 一、选择题 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、混凝土的收缩（ ）。 A ．随混凝土的压应力增大而增大 B.随水灰比增大而增大 C. 随混凝土密实度增大而增大 D.随养护齢期增大而增大 2、钢筋混凝土梁的混凝土保护层厚度是指（ ）。 A.外排纵筋的外表面至混凝土外表面的距离 B.箍筋的外表面至混凝土外表面的距离 C.外排纵筋的内表面至混凝土外表面的距离 D.外排纵筋的形心至混凝土外表面的距离 3、钢筋混凝土大偏心受压构件的破坏特征是（ ）。 A.远离纵向压力一侧的钢筋受拉屈服，随后另一侧钢筋受压屈服，砼被压碎 B.远离纵向压力一侧的钢筋应力不定，而另一侧钢筋受压屈服，砼被压碎 C.靠近纵向压力一侧的钢筋受拉屈服，随后另一侧钢筋受压屈服，砼被压碎 D.靠近纵向压力一侧的钢筋应力不定，而另一侧钢筋受压屈服，砼被压碎 4、承载能力极限状态下结构处于失效状态时，其功能函数 （ ）。 A.大于零 B.等于零 C.小于零 D.以上都不是 5、只配螺旋筋的混凝土柱体受压试件，其抗压强度高于c f 是因为（ ）。 A.螺旋筋参于受压 B.螺旋筋使混凝土密实 C.螺旋筋约束了混凝土的横向变形 D.螺旋筋使混凝土中不出现内裂缝 6、无腹筋梁的三种斜截面破坏形态的性质为（ ）。 A.都属于脆性破坏 B.斜压和斜拉属于脆性，剪压属于延性 C. 斜拉属于脆性，斜压、剪压属于延性 D.斜压属于脆性，斜拉、剪压属于延性 7、下列（ ）状态被认为超过正常使用极限状态。 A 、影响正常使用的变形； B 、因过度的塑性变形而不适合于继续承载； C 、结构或构件丧失稳定； D 、连续梁中间支座产生塑性铰； 8、钢筋混凝土梁的受拉区边缘达到（ ）时，受拉区开始出现裂缝。 A 、混凝土的实际抗拉强度； B 、混凝土的抗拉强度标准值； C 、混凝土的抗拉强度设计值； D 、混凝土的抗压强度设计值； 9、布置有双排纵向受力钢筋的梁，其截面有效高度取（ ） A 、h-60 B 、h-35 C 、h-20 D 、h-15 10、混凝土各项强度指标的基本代表值（ ） 中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A 一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 1、地震动的三要素是什么？ 答：地震动的主要特征可通过地震动的峰值、频谱和持续时间这三个要素密切相关。 2、地震的基本概念是什么？ 答：因地球内部缓慢积累的能量突然释放而引起的地球表层的振动。 3、地震波的基本概念是什么？ 答：地震引起的振动以波的形式从震源向各个方向传播并释放能量，这就是地震波。 4、地震按成因分为哪几类？ 5 6 答：主要有板块构造运动假说和断层假说。 7、极震区的基本概念是什么？ 答：震中及其附近的地方称为震中区，也称极震区。 8、根据图示解释震源、震中、震源深度、震中距和震源距的基本概念？ 震源：地壳岩层发生断裂破坏、错动，产生剧烈振动的地方，称为震源。 震中：震源正上方的地面位置称为震中。 震中距：地面某点至震中的距离称为震中距。 震源深度：震中到震源的距离或震源到地面的垂直距离,称为震源深度。 震源距：地面某点至震源的距离称为震源距。 9、地震波的主要成分有哪些？ 答：地震波是一种弹性波，包含体波和面波。体波为在地球内部传播的波。它有纵波和横波两种形式。面波是只限于在地球表面传播的波。它有瑞雷波和乐甫波两种形式。 实际地震时记录到的地震波可以看出，首先达到的是（纵波），接着是（横波），（面波）达到的最晚。 10、什么是地震烈度？地震烈度的影响因素是什么？ 答：一次地震对某一地区的影响和破坏程度称地震烈度，简称为烈度。 一般而言，震级越大，烈度就越大。同一次地震，震中距小烈度就高，反之烈度就低。影响烈度的因素，除了震级、震中距外，还与震源深度、地质构造和地基条件等因素有关。11、什么是多遇烈度、基本烈度和罕遇烈度，多遇烈度和罕遇烈度烈度与基本烈度的关系怎样？ 答：多遇烈度：发生概率最多的地震，在50年期限内，一般场地条件下，可能遭遇的超越概率为63.2%的地震烈度值，相当于50年一遇的烈度值。相当于基本烈度-1.55度。 基本烈度：一个地区的基本烈度是指该地区在今后50年期限内，在一般场地条件下可能遭遇超越概率为10％的地震烈度。 罕遇烈度：在50年期限内，一般场地条件下，可能遭遇的超越概率为2%～3%的地震烈度值，相当于1600～2500年一遇的烈度值。相当于基本烈度+1度。 12、设防烈度的基本概念是什么？ 答：按国家规定的权限批准作为一个地区抗震设防依据的地震烈度称为设防烈度。 13、“三水准”抗震设防目标的简要概述。 答：“三水准”抗震设防目标可以简要概述为小震不坏、中震可修和大震不倒。 14、简要概述建筑抗震设防目标通过什么来实现。 答：建筑抗震设防目标具体通过“三水准”的抗震设防要求和“两阶段”的抗震设计方法实现。 15、建筑抗震设防类别分为哪四类？ 答：《建筑工程抗震设防分类标准》GB50223确定建筑工程应分为特殊设防类、重点设防类、标准设防类和适度设防类四个抗震设防类别。 16、我国《抗震规范》（GB50011－2010）规定，进行抗震设计的建筑，其基本的抗震设防目标是如何规定的？ 答：(1)当遭受低于本地区抗震设防烈度的多遇地震影响时，主体结构不受损坏或不需修理仍可继续使用，即小震不坏； (2)当遭受相当于本地区抗震设防烈度的设防地震影响时，可能发生损坏，经一般性修理仍可继续使用，即中震可修； (3)当遭受高于本地区抗震设防烈度的罕遇地震影响时，不致倒塌或发生危及生命的严重破坏，即大震不倒。 17、什么是概念设计？ 答：根据地震灾害和工程经验等所形成的基本设计原则和设计思想进行建筑和结构总体布置并确定细部构造的过程称为概念设计。 18、场地的基本概念是什么？ 答：指工程群体所在地，具有相似的反应谱特征，其范围大体相当于厂区、居民小区和自然村或不小于1.0km2的平面面积。 19、建筑场地类别如何划分？ 答：抗震设计规范根据场地土层的等效剪切波速和覆盖层厚度将建筑场地划分为四类场地。 23、结构自振周期、基本周期与设计特征周期、场地卓越周期的基本概念是什么？ 答：自振周期：结构按某一振型完成一次自由振动所需的时间。 基本周期：结构按基本振型（第一振型）完成一次自由振动所需的时间。 设计特征周期Tg：抗震设计用的地震影响系数曲线的下降段起始点所对应的周期值，与地震震级、震中距和场地类别等因素有关。 场地卓越周期：根据场地覆盖层厚度d和土层平均剪切波速Vs，按公式T = 4d/Vs计算的周期，表示场地土最主要的振动特性。 24、反应谱的基本概念是什么？根据反应量不同分类情况如何？ 《数据结构》期中试卷（2009级） 2010-2011学年第一学期姓名：学号：成绩： 一、选择题：（每小题2分，共20分） 1.有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 2.在一个有125个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（） 个元素。 A．8 B. 62.5 C. 62 D. 7 3. 已知广义表A＝((a,b,c),(d,e,f),(h,(i,j)),g)，从A表中取出原子项e的运算是：( ) A.head(tail(A)) B.head(tail(tail(A))) C.head(head(tail(tail(A)))) D.head(tail(head(tail(A)))) 4.循环队列存储在数组A[0..m]中，设front和rear分别为队列的头指针和尾指针，则入队 时的操作为（）。 A. front=( front +1) mod (m+1) B. rear=(rear+1) mod (m+1) C. front=( front +1) mod m D. rear=(rear+1) mod m 5. 在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指 针的操作是( ) (假设双向循环链表的结点结构为(llink,data,rlink)。A．p->llink=q； q->rlink=p；p->llink->rlink=q；q->llink=q； B．p->llink=q；p->llink->rlink=q ；q->rlink= p；q->llink=p->llink； C．q->rlink=p；q->llink=p->llink；p->llink->rlink=q; p->llink=q; D．q->llink=p->llink；q->rlink=p；p->llink=q；p->llink=q； 6. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）。 A．250 B．500 C．254 D．以上答案都不对 7. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果 为（）。 A．CBEFDA B．FEDCBA C．CBEDFA D．不定 8. 利用二叉链表存储树时，则根结点的右指针是（）。 A．指向最左孩子B．指向最右孩子C．空D．非空 9.设有二维数组A[0..9, 0..19], 其中每个元素占两个字节，第一个元素的存储地址为100， 若按列优先顺序存储，则元素A[6,6]存储地址为( )。 A. 252 B. 132 C. 352 D.232 10. 引入二叉线索树的目的是（） A．加快查找结点的前驱或后继的速度 B．为了能在二叉树中方便的进行插入与删除 C．为了能方便的找到双亲 D．使二叉树的遍历结果唯一 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 1.以下与数据的存储结构无关的术语是（ c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ C ） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（ D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示 一、名词解释 合金，细晶强化，热处理，珠光体，加工硬化，同素异构转变，强度，塑性，滑移，珠光体，疲劳，固溶强化，固溶体，过冷度，铁素体，马氏体，织构，再结晶温度，冷加工，共晶转变，孪生，淬火。 二、填空题 根据结合键的性质，工程材料可以分为金属材料、高分子材料、陶瓷材料和复合材料四大类。一般可以把结合键分为：（金属键）、（共价键）、离子键和分子键四种。 纯金属中常见的晶体结构为面心立方晶体结构、体心立方晶体结构和密排六方晶体结构。体心立方晶体结构晶胞中的原子数为2/4个，晶胞边长a与原子半径r之间的关系是r等于a的四分子根3倍/根2倍，致密度为0.68/0.74。 根据合金中的相，合金的晶体结构可分为固溶体和金属间化合物。设纯金属A为体心立方晶体结构，纯金属B为面心立方晶体结构，A和B以一定的方式形成了合金C，若C为体心立方晶体结构，则C属于固溶体，若C为面心立方晶体结构，则C属于固溶体，若C为密排六方晶体结构，则C属于金属间化合物。 通过拉伸实验，在应力应变曲线上可以获得的力学性能指标包括弹性模量/弹性/刚度/弹性比例极限/弹性极限、屈服强度、抗拉强度和断裂强度。根据拉伸试样可以获得的塑性指标包括断面收缩率和伸长率。 常用的硬度测试方法主要指布氏硬度测试法、洛氏硬度测试法和维氏硬度测试法。如果进行硬度仲裁，应选用的为布氏硬度测试法；如果测试显微硬度，应选用的为维氏硬度测试法。晶体中的缺陷根据几何性质可以分为点缺陷、线缺陷和面缺陷。点缺陷如空位、间隙原子，线缺陷主要指位错，面缺陷主要指晶界。 纯金属结晶的温度必然低于其理论结晶温度，这种现象称为过冷现象。 结晶的基本过程可分为形核和长大两个基本过程。实际金属结晶一般以树枝晶的方式长大。单晶体塑性变形的基本方式是滑移和孪生，其中滑移是单晶体金属塑性变形的基本方式。冷塑性变形后，用于消除内应力的加热工艺称为回复，用于消除加工硬化现象的工艺称为再结晶。 热加工是材料在高于室温时的加工 冷加工是在零摄氏度以下的塑性加工。 再结晶前后及过程中，材料的晶体结构不发生变化。 共析钢在加热保温形成晶粒细小，成分均匀的奥氏体后，在冷却转变过程中可能发生的转变包括珠光体转变、贝氏体转变和马氏体转变。 钢中的常存元素是指锰、硅、硫、磷，其中具有热脆倾向的元素是硫，具有冷脆倾向的元素是磷，具有降低热脆倾向的元素是锰。 20钢的含碳量约是0.2%，T10钢的含碳量约为1%，1Cr18Ni9Ti的含碳量为0.1%，含Ti 量约为1%，12CrMoV的含碳量约为0.12%。 钢铁牌号Q235中的Q的是指屈服强度，235是该材料的最小屈服强度值。 铸铁根据其中石墨的形态可分为灰铸铁、球墨铸铁、蠕墨铸铁和可锻铸铁，其中球墨铸铁的综合力学性能最好。 QT400-18中QT标示该材料为球墨铸铁，400标示该材料最小抗拉强度为400Mpa，18标示该材料最小伸长率为18%。 铜及铜合金按俗称可分为紫铜、黄铜、白铜和青铜。其中青铜是指除黄铜和白铜以外的铜合金。HSn90-1标示的是含铜量为90%，含锡量为1%的黄铜。 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 数据结构习题集含答案 目录 选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性 7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0; 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 工程结构复习题 一、填空题 1、--------------------的计算是分析结构水平地震作用反应的基本条件 之一。 2、多层砌体房屋中，屋盖和楼盖将水平地震剪力传给各抗侧力构件 时，是随—————和抗侧力构件刚度的不同而分配得不同的。 3、进行结构设计的出发点是使建筑物使用美观、安全可靠、经济合 理，其中--------------和---------------是一对基本矛盾。 4、结构转变为机动体系而丧失承载能力属于---------------------------- 极限状态。 5、北京朝阳体育馆是属于————————结构。 6、当------------------时，按单向板设计，近似地假定板面荷载仅由短 向传给长边支座。 7、在桁架结构中，各杆件单元（上弦杆、下弦杆、斜腹杆、竖杆） 均为--------------------构件，使材料的强度可以得到充分的发挥。 8、钢结构通常在—————时，就会失去承载能力，产生很大的变 形，导致钢柱屈曲，钢梁弯曲，结果不能继续工作。 9、剪力墙结构的变形特点，当层数较低、墙体的高宽比小于1的情 形，水平荷载作用下墙体以-------------------变形为主。 10、砌体结构中横墙承重方案，荷载的主要传递路线为：———— -————。 11、受弯构件的箍筋直径和间距除应满足计算要求外，还应该满足 12、一般地说，钢结构轴心受压构件的承载能力是由-----------条件 决定的，它应该满足整体稳定和局部稳定的要求。 13、施加预应力的方法有——————和——————。 14、结构振动控制体系根据-------------------分为被动控制体系和主 动控制体系。 15、砌体结构房屋在水平荷载作用下产生的侧移大小与建筑物的 空间刚度有关，而建筑物空间刚度大小则是确定------------------并进行内力计算的主要依据。 16、钢筋混凝土现浇楼梯按其结构型式一般分为——————和 ——————。 17、当倾覆力矩等于抗倾覆力矩时，可以认为是倾覆的 -----------------------。 18、材料分项系数是概率极限状态设计方法所确定的分项系数之 一，反映材料------------------对承载能力的影响。 19、板的设计要点中，计算简图取——————的连续板进行内力 分析。 20、屋架结构的选型应考虑房屋的用途、-----------、屋面防水构造、 屋架的跨度、结构材料的供应、施工技术条件等因素。 21、双向板实用内力分析方法有————————和————— ———两种。 22、受弯构件的箍筋直径和间距除应满足计算要求外，还应该满足 2010年招收攻读硕士学位研究生入学考试试题（副题） ******************************************************************************************** 学科、专业名称：计算机技术、软件工程 研究方向：各专业 考试科目名称：830数据结构 考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。 一.选择题(每题2分，共40分) 1.具有n个顶点的完全有向图的边数为( ). A n(n-1)/2 B n(n-1) C n2 D n2-1 2.队列操作的原则是（） A.先进先出 B.后进先出 C.只能进行插入 D.只能进行删除 3. 顺序栈S的Pop(S, e)操作弹出元素e，则下列( )是正确的操作。 A. e=*(s.top) B. e=*(s.top--) C. e=*(--s.top) D. e=--s.top 4. 对具有n个结点的有序表折半查找时，其时间复杂度是 ( ) 。 A. O(log2n） B. O(nlog2n） C. O(n） D. O(n2） 5. 若线性表最常用的操作是存取第i个元素及其前趋的值,则采用( )存储方式节省时间。 A.单链表 B.双链表 C.单循环链表 D.顺序表 6. 线性表的链接实现有利于( )运算 A.插入 B. 读表元素 C .查找 D.定位 7. 设连通图G的顶点数为n,则G的生成树的边数为( ) A. n B. n-1 C.2n D. 2n-1 8.从一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需向前移动（）个元素。 A.n-i B.n-i+1 C.n-i-1 D. i 9. 若有一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n,则第i个输出元素是（） A.n-i B.n-i-1 C.n-i+1 D.不确定 10. 二叉树第i(i≥1)层上至多有( )个结点。 A. 2i B.2i C.2i-1 D.2i-1 11.串是一种特殊的线性表, 其特殊性体现在( ) A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个 12. 稀疏矩阵一般的压缩存储方法有两种,即: ( ) A.二维数组和三维数组 B.三元组和散列 C.三元组和十字链表 D.散列和十字链表 考试科目：数据结构共 4 页，第 1 页 《工程结构》复习题 一、名词解释题 1、徐变 2、结构抗力 3、结构的可靠度 4、结构的极限状态 5、梁的截面有效高度 6、界限破坏 7、相对受压区高度 8、剪跨 9、抵抗弯矩图 10、预应力损失 二、单项选择题 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 、界限破坏 7．（ ）作为受弯构件正截面承载力计算的依据。 A 、Ⅰa 状态 B 、Ⅱa 状态 C 、Ⅲa 状态 D 、第Ⅱ阶段 8．受弯构件正截面承载力中，对于双筋截面，下面哪个条件可以满足受压钢筋的屈服（ ） A 、0h x b ξ≤ B 、0h x b ξ> C 、'2s a x ≥ D 、'2s a x < 9．在钢筋混凝土梁中，下列钢筋属于构造钢筋的是（ ） A 、纵向受力钢筋 B 、弯起钢筋 C 、架立钢筋 D 、箍筋 10．下列钢筋混凝土构件中，按其受力特点进行分类，属于受压构件的是（ ） A 、梁 B 、剪力墙 C 、楼梯板 D 、屋面板 11．受弯构件斜截面承载力计算公式是以（ ）为依据的。 计算机学院2010-2011学年第一学期 《数据结构》试卷（A 卷）（考试时间：100分钟） 专业： 计算机专业 班级： 序号： 姓名： 注意：所有答案都必须写在答题纸上！！！ 三．简答（每小题10分，共50分） 1．有如图所示的有向图，请给出该图的: 1) 邻接矩阵表示； 2) 逆邻接表表示。 2．假定存在数据表：（3，4，5，7，24，30，54，63，72，87，95，102），请解决如下问题： 1) 假设哈希函数为：H(key)=key mod 13，用该哈希函数将数据表存入长度为13 的哈希表，（利用线性探测）请画出存放状态； 2) 请按比较顺序写出查找102的过程中比较的数值，以及比较的次数； 3．请写出对序列{21，25，49，28，16，22，25，38}的二叉排序树构造过程。 4．试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步的状态。 5．如果一个项目由10个主要任务构成，其计划图展示了任务之间关系与任务所需天数，则项目关键路径如何求解，请展示其过程。 四．算法（10分，共10分） 请写出折半查找方法的函数Search_Bin( SSTable S, value v)。 要求： 1）函数名使用给出的函数名，参数SSTable 表示序列，使用一维数组存放，下标从0开始，value 表示要查找的值； 2）如果找到，则函数返回值为该数在序列中的位置，否则返回负1； 3）不用写出主函数与相关定义，如果使用其他函数，请注明函数用途。 计算机学院2010-2011学年第一学期 《数据结构》答题纸（A卷）一．填空（2*20=40分）数据结构复习题(附答案)
数据结构与算法复习题库含答案
建筑工程结构复习题
数据结构-数据结构历年考题及答案2
数据结构复习题附答案
工程结构抗震复习题及答案
2010年数据结构期中考试试卷及答案
数据结构期末考试试题及答案
数据结构期末复习题答案
2010-2011(1)工程材料-复习题
2010级数据结构期末复习题(E)
数据结构考试题库含答案
数据结构练习试题和答案解析
工程结构复习题
数据结构2010
工程结构复习考试资料
中国矿业大学2010年数据结构试卷及答案