《数据结构》期末考试复习题及参考答案
数据结构复习题
（课程代码 252259）
一、填空题（本大题共40小题）
1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号
为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，
数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n
个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元
素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____
增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，
整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子
树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
16.栈又称为______后进先出__________的线性表。
17.数据结构在计算机中的表示称为数据的__物理结构____。
18.有4个结点的不同的二叉树有__9___棵。
19.含有60个结点的树有____59____条分支。
20.在图结构中，前驱元素和后继元素之间存在着_____多对多____的联系。
21.____哈夫曼树____又称最优二叉树。
22.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结
点有___33___个。
23.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head
可用p表示为head=______ p－＞next－＞next ____。
24.栈顶的位置是随着_____进栈和出栈______操作而变化的。
25.设一个散列表的容量为M，用线性探测法解决冲突.。若要查找一个键值，至少要进行
1次比较，至多要进行_____M_____次比较。
26.在n个结点的线索二叉链表中，有____ n-1___个线索指针。
27.具有180个结点的二叉树，其深度至少为___8______。
28.序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择______
_____直接插入_____排序算法。
29.若堆栈的入栈序列为1,2,3,…,n-1,n，输出元素i需要进行____ n-i+1______次出栈操作。
30.对于队，只能在队尾插入元素，只能在队头
删除元素。
31.抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示：数据对
象、数据关系和基本操作。
32.栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是后进先出
33.在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：
s->next=p->next；p->next=s
34.通常从四个方面评价算法的质量：___正确性易读性强壮性高效率_____。
35.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___ O(n)_____。
36.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数
为___9_______个，树的深度为_____3______，树的度为___3______。
37.后缀算式9 2 3 +- 10 2 / -的值为____－1______。中缀算式（3+4X）-2Y/3对应的后缀算
式为_______3 4 X * + 2 Y * 3 / -________________________。
38.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指
针。在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有__n-1______个指针域是存放了地址，有_______n+1_________个指针是空指针。
39.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点
分别有_____e__个和____2e____个。
40.AOV网是一种________有向无回路___________的图。
二、单项选择题（本大题共50小题）
1．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（D ）
A）O（1）B）O（n）C）O（m）D）O（m+n）
2．如下所示的图的拓扑序列为（D）
A） C1，C2，C3，C4，C5，C6
B)C1，C2，C5，C3，C4，C5，C7
C)C1，C4，C2，C3，C5，C6
D)C1，C2，C5，C4，C3，C6
3．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D ) A）e B）2e C）n2－e D）n2－2e
4．设有6个结点的无向图，该图至少应该有(A)条边才能确保是一个连通图A．5 B．6 C．7 D．8
5．有N个结点的图的邻接矩阵存储法中，链表的表头结点有（A ）个。
A、N
B、2N
C、N/2
D、N*N
E、N-2
6．具有4个顶点的无向完全图有（A ）条边。
A、6
B、12
C、16
D、20
7．邻接矩阵是对称矩阵的图为(D ）。
A、有向图
B、带权有向图
C、带权连通图
D、无向图
8．在长度为n的线性表中查找值为x的数据元素的时间复杂度为（ C ）。
A）O(0) B）O(1) C）O(n) D）O(n2)
9．若一个栈的输入序列是1，2，3，……，n，输出序列的第一个元素是n，则第i个输出元素是（ D ）。
A）不确定 B）n-i C、n-i-1 D、n-i+1
10．设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2,e4,e3,e6,e5,e1，则栈的容量至少应该是（ C ）。
A、6
B、4
C、3
D、2
11．一个栈的入栈序列是1，2，3，4，5，则栈的不可能的出栈序列是（ C ）。
A、5，4，3，2，1
B、4，5，3，2，1
C、4，3，5，1，2
D、1，2，3，4，5
12．设计一个判别表达式中左右括号是否匹配的算法，采用（ B ）数据结构最佳。
A、顺序表
B、栈
C、队列
D、链表
13．在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印缓冲区，该缓冲区应该是一个（ B ）结构。
A、栈
B、队列
C、数组
D、线性表
14．线性表若采用链表存储结构，要求内存中可用存储单元地址( D )
A．必须连续B．部分地址必须连续C．一定不连续D．连续不连续均可
15．依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ C ）
A）X B）Y C）Z D）W
16．已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS 序列为（ A ）。
A) a d b e f c
B) a d c e f b
C) a d c b f e
D) a d e f c b
17．若连通无向图G有n个顶点，则图G的生成树有（B ）条边
A）n B）n-1 C）n(n-1)/2 D）n/2
18．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（D ）
A）front=front+1 B）front=(front+1)%(m-1)
C）front=(front-1)%m D）front=(front+1)%m
19．设某算法的问题规模函数f(n)=25n3+5000n2，则它的渐进时间复杂度为（ A ）。
A）O(n3) B）O(n2) C）O(n) D）O(1)
20．假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为( D )。
A）f+1==r B）r+1==f C）f==0 D）f==r
21．线性表采用链式存储时，结点的存储地址（B ）
A）必须是不连续的B）连续与否均可
C）必须是连续的D）和头结点的存储地址相连续
22．设计递归问题的非递归算法一般需要用到（ D ）。
A）链表B）队列C）树D）堆栈
23．对下面二叉树，按中序遍历所得到的结点序列为（ A ）。
A）DBEAFC
B）DEBFCA
C）BDEACF
D）ABCDEF
24．对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为（A ）。
A）n B）n+1 C）n-1 D）n+边数
25．设有一个含有n 个(n>2)关键字的有序表，设s和h分别是用顺序查找法和二分查找法进行查找时的等概率情况下查找成功的平均查找次数，则s和h的关系是（ B ）。
A）s = h B）s > h C）s < h D）不能确定
26．一棵深度为7的满二叉树有（ D ）叶子结点。
A）7 B）14 C）32 D）64
27．设二叉树根结点的层次为1，含有15个结点的二叉树中的最小高度是（ 4 ）A）6 B）5 C）4 D）3
28．在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数为（ B ）。
A）i-1 B）n-i+1 C）i D）n-i
29．一棵深度为8的满二叉树有（ C ）叶子结点。
A）256 B）255 C）128 D）127
30．在一非空二叉树的中序遍历序列中，根结点的右边(A )
A．只有右子树上的所有结点B．只有右子树上的部分结点
C．只有左子树上的所有结点D．只有左子树上的部分结点
31．以下关于数据结构的叙述，正确的是( C)
A．线性表的线性存储结构优于链式结构
B．二叉树的第I层上有2的（I-1）次幂个结点，深度为K的二叉树上有2的（k-1）次幂个结点
C．二维数组是其数据元素为线性表的线性表
D．栈的操作方式是先进先出
32．在单链表中，增加头结点的目的是为了（C ）。
A．使单链表至少有一个结点
B．表示表结点中首结点的位置
C．方便运算的实现
D．说明单链表是线性表的链式存储实现
33．使用双向链表存放数据的优点是(A )
A．提高检索速度B．很方便地插入和删除数据
C．节约存储空间D．很快回收存储空间
34．带头结点的单链表Head为空的判定条件是(B )
A．Head=NIL B．Head^.Next=NIL C．Head^.Next=Head D．Head=Head
35．下列哪一种图的邻接矩阵是对称矩阵(B )
A．有向图B．无向图C．AOV网D．AOE网
36．下列叙述中，正确的是( D)
A．线性表的线性存储结构优于链表存储结构B．队列的操作方式是先进后出
C．栈的操作方式是先进先出D．二维数组是指它的每个数据元素为一个线性表的线性表
37．一维数组与线性表的区别是( A )
A．前者长度固定，后者长度可变B．后者长度固定，前者长度可变
C．两者长度均固定D．两者长度均可变
38．设有三个元素A、B、C顺序进栈，在进栈过程中可以出栈，出栈次序错误的排列是(C ) A．ABC B．BCA C．CAB D．CBA
39．若进栈序列为1，2，3．4假定进栈和出栈可以穿插进行，则可能的出栈序列是( D) A．2，4，1，3 B．3，1，4，2 C．3，4，1，2 D．1，2，3，4
40．若已知一个栈的入栈顺序是1，2，3…n，其输出序列为P1,P2，P3…Pn，若P1是n，则Pi是（C）
（A）I （B）n-i （C）n-i+1 （D）不确定
41．栈和队列都是(C )
A．顺序存储的线性结构B．链式存储的非线性结构
C．限制存取点的线性结构D．限制存取点的非线性结构
42．循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是(A )
A．（rear-front+m）MOD m B．rear-front-1 C．rear-front+1 D．rear-front
43．设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应是（B ）
A．2 B．3 C．4 D．6
44．一个文本屏幕有25列及80行，屏幕的左上角以（1，1）表示，而右下角则以（80，25）表示，屏幕上每一个字符占用两字节（byte），整个屏幕则以线性方式存储在电脑的存储器内，从屏幕左上角开始，位移为0，然后逐列逐列存储。求位於屏幕（X，Y）的第一个字节的位移是（）
A.（Y*80+X）*2-1
B.（（Y-1）*80+X-1）*2
C.（Y*80+X-1）*2
D.（（Y-1）*80+X）*2-1
45．对任何一棵二叉树T，设N0、N1、N2分别是度数为0、1、2的结点数，则下列判断正确的是（A）
A．N0＝N2＋1B．N1＝N0＋1C．N2＝N0＋1D．N2＝N1＋1
46．下面关于二叉树的叙述正确的是(A )
A．一棵二叉树中叶子结点的个数等于度为2的结点个数加1
B．一棵二又树中的结点个数大于0
C．二叉树中任何一个结点要么是叶，要么恰有两个子女
D．二叉树中，任何一个结点的左子树和右子树上的结点个数一定相等
47．先序序列和中序序列相同的二叉树为空树或(C )
A．任一结点均无右孩子的非空二叉树B．仅有两个结点的二叉树
C．任一结点均无左孩子的非空二叉树D．不存在这样的二叉树
48．给出一组整型数28、10、37、63、35、30、23，请用二叉树对它进行排序。为此，首先要生成一棵二叉树，规则是把第一数放在根处，接着凡比它小的数放在左子树，比它大的数放在右子树，直到把所有的数均安排好。然后对此二叉树进行( )，得到的就是按照升序排列好的序列。( B)
A．前序遍历B．中序遍历C．后序遍历D．横向遍历
49．下面关于数据结构的叙述中，不正确的叙述是( A)
A．顺序存储方式的优点是存储密度大，且插入、删除运算效率高
B．链表中的每一个结点都包含一个指针
C．包含n个结点的二叉排序树的最大检索长度为n
D．将一棵树转换为二又树后，根结点没有右子树
50．由3个结点可以构造出多少种不同的有序树(D )
A．2 B．3 C．4 D．5
三、判断题（本大题共30小题）
1.（×）折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
2.（√）数据的机内表示称为数据的存储结构。
3.（√）程序就是算法，但算法不一定是程序。
4.（√）{101，88，46，70，34，39，45，58，66，10}是堆。
5.（√）程序就是算法，但算法不一定是程序。
6.（×）二叉树中任何一个结点的度都是2。
7.（×）双循环链表中任一结点的前趋指针均指向其逻辑前趋
8.（×）若从有向图的某个顶点出发进行一次深度优先搜索可以访问图的每个顶点，
则该图一定是有向完全图。
9.（√）强连通图的各顶点间均可达。
10.（×）对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该
图的每个顶点。
11.（√）在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录
的相对次序仍然保持不变，称这种排序为稳定排序。
12.（×）不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。
13.（√）单链表中至多只有一个结点的后继指针为空。
14.（×）对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有
序排列。
15.（√）散列法存储的思想是由关键字值决定数据的存储地址。
16.（×）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、
小于其右孩子的值。
17.（×）队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的
结构。
18.（×）串是一种特殊的线性表，其特殊性体现在可以顺序存储。
19.（×）长度为1的串等价于一个字符型常量。
20.（×）空串和空白串是相同的。
21.（×）数组元素的下标值越大，存取时间越长。
22.（√）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。
23.（×）一个无向图的邻接矩阵中各元素之和与图中边的条数相等。
24.（√）程序就是算法，但算法不一定是程序。
25.（×）设S=”cart”，S’=”cat”，则S’为S的子串。
26.（×）有n个结点的不同的二叉树有n！棵。
27.（√）一棵哈夫曼树中不存在度为1的结点。
28.（×）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。
29.（×）冒泡排序算法关键字比较的次数与记录的初始排列次序无关。
30.（√）具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。
四、应用题（本大题共10道小题）
1、初始序列的键值：（84，85，83，34，98，28，19，76，54，48），采用冒泡排序法
进行从小到大的排序，请写出每一趟排序的结果，并记录每一趟排序时交换元素的次数最后求出该排序过程的总的元素交换次数。
排序过程：
初始：84，85，83，34，98，28，19，76，54，48 交换次数
第1趟： 84，83，34，85，28，19，76，54，48，98 7
第2趟： 83，34，84，28，19，76，54，48，85 7
第3趟： 34，83，28，19，76，54，48，84 6
第4趟： 34，28，19，76，54，48，83 6
第5趟： 28，19，34，54，48，76 4
第6趟： 19，28，34，48, 54 2
第7趟： 19，28，34，48 0
上一趟无交换，排序完成
总共交换了2+4+6+6+7+7=32次
2、证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。
参考答案：
证明采用归纳法。
设二叉树的前序遍历序列为a1a2a3… an，中序遍历序列为b1b2b3… bn。
当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树；
假设当n<=k时，前序遍历序列a1a2a3… ak和中序遍历序列b1b2b3… bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3… akak+1和中序遍历序列b1b2b3… bk bk+1可唯一确定一棵二叉树。
在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2… bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3… ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3… ai和中序遍历序列b1b2… bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2…
ak+1和中序遍历序列bi+1bi+2… bk+1唯一确定了根结点的右子树。
3、逐个结点插入构成平衡二叉树，插入结点的数据顺序为：
12,4,1,7,8,10,9,2,11,6,5，
在插入过程中平衡树条件如被破坏，则进行必要的调整，试画出每插入一个结点后平衡树的情况。
参考答案：
4、画出将下面的树转化成二叉树的过程，并写出构造出的二叉树的先根、中根和后根
遍历序列。
参考转换过程：
先根：ABCEFGDIJK
中根：BFGECIJKDA
后根：GFEKJIDCBA
5、设有升序排列的线性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），
用二分查找法进行查找。
1)画出查找关键字27的过程（3分）
第1次：[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
↑
第2次：2, 4, 7, 10, 12, 16, 18, 19, 20, [24, 27, 29, 30, 35, 36, 40, 41]
↑
第3次：2, 4, 7, 10, 12, 16, 18, 19, 20, [24, 27, 29,] 30, 35, 36, 40, 41
↑
查找成功。
2)画出查找关键字11的过程（4分）
第1次：[2, 4, 7, 10, 12, 16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41]
↑
第2次：[2, 4, 7, 10, 12, 16, 18, 19],20, 24, 27, 29, 30, 35, 36, 40, 41
↑
第3次：2, 4, 7, 10, [12, 16, 18, 19],20, 24, 27, 29, 30, 35, 36, 40, 41
↑
第4次：2, 4, 7, 10, [12],16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41
↑
第5次：2, 4, 7, 10,][ 12,16, 18, 19, 20, 24, 27, 29, 30, 35, 36, 40, 41
无数据可比，查找不成功。
3)计算该表在等概率的情况下查找成功的平均查找次数为多少？(3分)
先画出该序列对应的二分查找树：
共有17个值，很明显
总的查找次数= 1 + 2×2 + 4×3 + 8×4 + 2×5
= 1+4+12+32+10
= 59
ASL = 59/17 = 3.47
6、假设以数组sq[0..7]存放循环队列元素,变量f指向队头元素的前一位置,变量r
指向队尾元素，如用A和D分别表示入队和出队操作，请给出：
（1）队空的初始条件；
答：队空的初始条件：f=r=0；
（2）执行操作序列A3 D1 A5 D2 A1 D2 A4时的状态,并作必要的说明。（A3表示三次入队操作，D1表示一次出队操作）
答：执行操作A3后，f=0，r=3；//A3表示三次入队操作
执行操作D1后，f=1，r=3；//D1表示一次出队操作执行操作A5后，f=1，r=0；执行操作D2后，f=3，r=0；执行操作A1后，f=3，r=1；执行操作D2后，f=5，
r=1；
执行操作A4后，按溢出处理。因为执行A3后，r=4，这时队满，若再执行A操作，则出错。
7、已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不
同的存储结构完成求和运算的优缺点。
答：设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；
因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << m×n时，采用三元组顺序表存储可获得较好的时、空性能。
8、设有如下的的散列表，散列函数为Ｈ（Ｋ）＝Ｋ mod 13，用线性探测法解决冲突。
1)写出查找19的计算过程
根据散列函数，可得H(19) = 19 mod 13 = 6，而地址6存储的元素正好为6，所以只需要比较一次，即可得到查找19的结果。
2)写出查找27的比较次数（要求写出计算和分析过程）
根据散列函数，可得H(27) = 27 mod 13 = 1，而地址1存储的元素非27，即出
现查找冲突。已知采用线性探测法进行冲突解决，所以按线性递增的方式查找
地址2，而地址2非空且也不等于27，再线性增长地址跟地址3比较，也非27，再线性增长地址跟地址4比较，查找成功。所以查找27需要比较4次。
3)计算等概率情况下查找成功的ASL。
根据散列函数及冲突解决方法可计算出各元素的哈希值和查找次数：
H(14) = 14 mod 13 = 1, 比较1次
H（1）= 1 mod 13 = 1，比较2次
H（68）= 68 mod 13 = 3，比较1次
H（27）= 27 mod 13 = 1，比较4次
H（5）= 5 mod 13 = 5，比较1次
H（19）= 19 mod 13 = 6，比较1次
H（20）= 20 mod 13 = 7，比较1次
H（84）= 84 mod 13 = 6，比较3次
H（23）= 23 mod 13 = 10，比较1次
H（11）= 11 mod 13 = 11，比较1次
故可得这10个元素查找成功总的比较次数为1+2+1+4+1+1+1+3+1+1 = 16次
所以查找成功的ASL = 16/10 = 1.6
4)等概率情况下查找不成功的ASL。
查找不成功必须是比较到空元素，根据冲突解决方法可知这13个存储单元查找不成功的比较次数：
A[0]为空，所以只需比较 1次
A[1]非空，按线性探测方法要比较到A[9]，即9次比较
以此类推
A[2]比较8次
A[3]比较7次
A[4]比较6次
A[5]比较5次
A[6]比较4次
A[7]比较3次
A[8]比较2次
A[9]比较1次
A[10]比较3次
A[11]比较2次
A[12]比较1次
可得查找不成功总的比较次数为1+9+8+7+6+5+4+3+2+1+3+2+1 = 52次所以查找不成功的ASL = 52/13 = 4
9、对于如下图所示的的无向网络：
（1）画出表示此网络的邻接矩阵。
（2）画出表示此网络的邻接表
（3）画出用普里姆算法构造其最小生成树的过程。
10、试比较线性表的两种存储结构的优缺点,在什么情况下用顺序表比链表好?
①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插入.删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入.删除操作，则采用链表。
五、算法编写（本大题共6小题）
1.试写出二分查找的递归算法int BinSearch(Seqlist R,int low,int high,KeyType k)。
int BinSearch(Seglist R,int low,int high,keyType k)
{int mid;
if(low<=high) ∥保证在low<=high的时候才进入函数体
{
mid=(low+high)/2; ∥确定中间元素位置
if(R［mid］.kid==k)
return mid; ∥如果中间元素关键字值等于k，返回位置mid else if(R［mid］.key>k)
return Binsearch(R,low,mid－1,k); ∥如果中间元素关键字值大于k，
在low和mid-1之间继续寻找else
return BinSearch(R,mid+1,high,k); ∥如果中间元素关键字值小于k，
在mid+1和high之间继续寻找}
return(－1); ∥返回－1表示没有找到
}
2.以下为带空头结点的循环链式队列逻辑结构，请写出队列的入队和出队算法。
参考算法：
// 结点数据结构
Struct node {
DATATYPE data;
Struct node *next;
} ;
// 入队算法
void InQueue(struct node *rear, DATA TYPE x) {
struct node *p;
p = (struct node *)malloc(sizeof(struct node));
p->data = x;
if (rear->next = rear)
{
p->next = rear;
real->next = p;
}
Else
{
p->next = rear->next->next;
rear->next->next = p;
};
}
// 出队算法
DA TATYPE OutQueue(struct node *rear)
{
struct node *p, *q;
DATATYPE rlt;
if (rear->next = rear)
{
Error(“队列已空,不能出队!”);
}
Else
{
p = rear;
while(p->next !=rear)
p = p->next;
p->next = rear->next;
q=rear;
rear = p;
rlt = q->data;
free(q);
return rlt;
};
}
3.编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若
查找成功则由item带回整个结点的值并返回true，否则返回false。
bool Find( BTreeNode * BST , ElemType & item )
{
while ( BST != NULL )
{
if ( item == BT->data ) {
item = BST->data;
return true;
}
else if (item
else BST=BST->right;
}
return false;
}
4.以下为带空头结点的链式队列，请写出该队列的入队和出队算法。
参考算法：
/* 设数据元素的类型为DataType */
struct node
{
DataType data; /* 存储元素*/
struct node *next;
} ;
/****************************************/
/* 入队*/
/****************************************/
EnQueue (struct node *real, DataType x)
{
struct node *p;
p = (struct node *)malloc(sizeof(struct node));
p->data = x;
p->next = NULL; /* 保证p是尾结点*/
real->next = p;
real = p; /* real指向队尾*/
}
/****************************************/
/* 出队*/
/****************************************/
OutQueue (struct node *front, struct node *p)
{
if (front->next == NULL) /* 队空*/
error("Queue is Empty!");
else
{
p = front->next; /* 保存队首结点*/
/* 队首结点脱链*/
Front->next = p->next;
}
}
5.写出链式存储结构的栈的入栈和出栈算法。
参考算法：
/* 设数据元素的类型为DataType */
struct node
{
DataType data; /* 存储元素 */
struct node *next ; /* 链接下一元素 */
} ;
/****************************************/
/* 将元素x压入栈顶 */
/****************************************/
Push (struct node *S, DataType x)
{
struct node *p;
/* 将生成结点p放置x */
p = (struct node *)malloc(sizeof(struct node));
p->data = x;
/* 将结点p插入到表头(栈顶) */
p->next = S ;
S = p ;
}
/****************************************/
/* 将栈顶元素弹出并用p带回 */
/****************************************/
Pop (struct node *S, struct node *p)
{
if (S==NULL) /* 栈空 */
error("Stack is Empty!");
else
{
p = S; /* p指向栈顶 */
S = p->next; /* 栈从栈顶下一结点开始 */
p->next = NULL; /* 让p结点从链中脱开 */
} /* 原栈顶元素在p中 */
}
6.2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所
有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n)
void move(SqList &L)
{
int i=0,j=L.length-1;
int temp;
while(i while(i while(i if(i { temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; } } i=1; while(i { j=L.length-2; temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; i=i+2; j=j-2; } } c期末考试试题及答案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 AutoCAD 试卷 一、 单项选择 1、AutoCAD 默认扩展名是 A 、dwt B 、dwg C 、bak D 、dxf 答案：B 2、在CAD 中，以下哪个命令可用来绘制横 平竖直的直线 A 、栅格 B 、捕捉 C 、正交 D 、对象捕捉答案：C 3、按哪个键可切换文本窗口和绘图窗口 A 、F2 B 、F8 C 、F3 D 、F5答案：A 4、默认情况下，命令提示行显示为几行 A 、3 B 、5 C 、2 D 、8答案：A 5、在CAD 中为一条直线制作平行线用什么命令 A 、移动 B 、镜像 C 、偏移 D 、旋转答案：C 6、在图层特性管理器中不可以设定哪项 A 、颜色 B 、页面设置 C 、线 宽 D 、是否打印答案：B 7、绘制建筑图步骤为 A 、墙线、轴线、门窗 B 、墙线、 门窗、轴线 C 、轴线、门窗、墙线 D 、轴线、 墙线、门窗答案：D 8、哪个命令可用于绘制直线与圆弧的复合 体 A 、圆弧 B 、构造线 C 、多段线 D 、样条曲线答案：C 9、如何在图中输入“直径”符号 A 、%%P B 、%%C C 、%%D D 、%%U 答案：B 10、如果要在一个圆的圆心写一个“A”字，应使用以下哪种对正方式 A、中间 B、对齐 C、中心 D、调整答案：A 11、在哪个层创建的块可在插入时与当前层特性一致 A、0层 B、在所有自动产生的层 C、所有图层 D、新建的图层答案：A 12、一个完整的尺寸由几部分组成 A、尺寸线、文本、箭头 B、尺寸线、尺寸界线、文本、标记 C、基线、尺寸界线、文本、箭头 D、尺寸线、尺寸界线、文本、箭头 答案：D 13、要将图形中的所有尺寸都为原有尺寸的2倍，应设定以下哪项A、文字高度 B、使用全局比例 C、测量单位比例 D、换算单位 答案：B 14、三维模型中哪种模型可以进行布尔运算 A、线框模型 B、实心体模型 C、表面体模型答案：B 15、渲染三维模型时，哪种类型可以渲染出物体的所有效果 A、一般渲染 B、普通渲染 C、照片级真实感渲染 D、照片级光线跟踪渲染答案：D 16、样板文件的括展名是 A、BAK B、SVS C、DWT D、DWG 答案：C 17、以下哪种相对坐标的输入方法是画8个单位的线长 A．8, 0 B．@0，8 C．@0<8 九、期末考试试题及参考大案 古代汉语试题（A） 一.填空题（每空2分，10空，共20分） 1.许慎六书“假借”的定义_____________________________。 2.本义__________________________________________。 3.异体字_______________________________________。 4.文字学家辨别汉字的本义主要依靠汉字的_________。 5.我国第一部字典是东汉许慎着的_________________。 6.判断句是以___________________作谓语。 7.上古汉语判断句很少用判断词_______来表示。 8.教材第一篇文章《郑伯克段于鄢》选自《十三经》中的_______。 9.“莫”的本义是______，“莫”的今字是________。 二．解释下列词语意义并指出词性（每题1分，共20题，共20分）1.都城过百雉，国之害也。 雉： 2.昭王之不复，君其问诸水滨！ 诸： 3.一之为甚，其可再乎？ 其： 4.行李之往来，共其乏困。 行李： 5.必死是间，余收尔骨焉。 焉： 6.靡不有初，鲜克有终。 克： 7.贼民之主，不忠。 贼： 8.此车一人殿之，可以集事。 殿： 9.虽然，必告不谷。 不谷： 10.晋侯问嗣焉，称解狐。 称： 11.于是乘其车，揭其剑，过其友。过： 12齐王使使者问赵威后，书未发。 发： 13.见兔而顾犬，未为晚也。 顾： 14.赵诚发使尊秦昭王为帝，秦必喜，罢兵去。 诚： 15.老臣贱息舒祺，最少，不肖。 息： 16.君子于其言，无所茍而已矣。 茍： 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 四、程序设计题（本大题共2小题，每小题15分，共30分） 1.对于教学数据库的三个基本表 学生student (sno,sname,sex,sage,sdept) 学习sc(sno,cno,grade) 课程course(cno,cname,cpno,ccredit) 试用SQL语句表示：下列语句。 （1）"查询全男同学信息情况" "select * from student where sex='男'" （2）"查询选修了1号课的学生的学号和成绩" "select sno,grade from sc where cno='1'" （3）"查询所有选修过课的学生的姓名，课程名及成绩" "select sname,cname,grade from student,sc,course where student.sno=sc.sno and https://www.wendangku.net/doc/4014024752.html,o=https://www.wendangku.net/doc/4014024752.html,o" （4）"查询选修了数据库原理课的最高成绩" "select max(grade) as '最高成绩' from student,sc,course where student.sno=sc.sno and https://www.wendangku.net/doc/4014024752.html,o=https://www.wendangku.net/doc/4014024752.html,o and cname='数据库原理'" （5）查询所有选修了1号课程的同学的姓名" " select sname from student where student.sno in (select sc.sno from sc where cno='1')" 2．设有一个SPJ数据库，包括S，P，J，SPJ四个关系模式（20分）供应商表S（SNO,SNAME,STATUS,CITY）; 零件表P(PNO,PNAME,COLOR,WEIGHT); 工程项目表J(JNO,JNAME,CITY); 供应情况表SPJ(SNO,PNO,JNO,QTY)；SPJ表 J表 S表 P表 请用关系代数完成如下查询： 1．求供应工程J1零件的供应商号 SNO 2．求供应工程J1零件P1的供应商号吗SNO 3．求供应工程J1零件为红色的供应商号码SNO 4．求没有使用天津供应商生产的红色零件的工程号JNO 5．求至少用了供应商S1所供应的全部零件的工程号JNO 1.∏sno（σJNO＝‘J1’（SPJ）） 2.∏sno（σJNO＝‘J1’ΛPNO=’P1’（SPJ）） 3.∏sno（σJNO＝‘J1’（SPJ）∞σcolor＝‘红’（P）） 4.∏jno（SPJ）-∏jno（∏sno（σcity＝‘天津’（S））∞∏sno，jno （SPJ）∞∏jno σcolor＝‘红’（P）） 5.∏jno, pno（SPJ）÷∏pno（σsno＝‘s1’（SPJ）） 五、分析题（本大题共2小题，每小题15分本大题共30分） 1. 学生运动会模型: (1)有若干班级,每个班级包括: 班级号,班级名,专业,人数 (2)每个班级有若干运动员,运动员只能属于一个班,包括:运动员号,姓名,性别,年龄 一，判断 1 √ 2.× 3.√ 4.× 5. × 6. ×7. ×8. ×9.√10. ×二，选择 1. D 2. D 3. B 4. B 5. B 6. A 7. D 8. B 9. C 10. A 三填空 1. 测试计划、测试用例 2. 稳定性测试、负载测试、压力测试 3. 非增量是集成测试自顶向下增量式测试、自底向上增量式测试 4. 回归 5. 软件需求 四简答题（30分） 1.试描述软件测试的定义？（3分） 答：利用手工或者自动化的方式，按照测试方案对系统执行测试用例的过程叫做软件测试。 2.什么是软件缺陷？（4分） 答：满足以下条件的问题都叫缺陷： 软件未达到产品说明书中已标明的功能 软件出现了产品说明书中指明不会出现的错误 软件功能超出了产品说明书指明的范围 软件未达到产品说明书虽未指出但应达到的目标 软件测试员认为软件难以理解，不易使用，运行速度缓慢，或者最终用户认为该软件使用效果不好。 3.常见的黑盒测试用例的设计方法？并分别简单介绍一下各自的思想。（8分）答：等价类划分：等价类划分法是一种重要的、常用的黑盒测试方法，它将不能穷举的测试过程进行合理分类，从而保证设计出来的测试用例具有完整性和代表性。 边界值分析：对输入输出的边界值进行测试的一种黑盒测试方法。 决策表法：决策表是分析和表达多逻辑条件下执行不同操作的情况的工具 因果图分析法：是一种利用图解法分析输入的各种组合情况，从而设计测试用例的方法，它适合于检查程序输入条件的各种组合情况。 错误推测法：基于经验和直觉推测程序中所有可能存在的各种错误，从而有针对 性的设计测试用例的方法。 4. 列举常见的系统测试方法。答出来5个即可。（5分） 答：恢复测试 安全测试 强度测试 性能测试 正确性测试 可靠性测试 兼容性测试 Web测试 5.文档测试主要测试哪些内容？答出来5点即可（5分） 答：（1）检查产品说明书属性 （2）检查是否完整 （3）检查是否准确 （4）检查是否精确 （5）检查是否一致 （6）检查是否贴切 （7）检查是否合理 （8）检查代码无关 （9）检查可测试性 6. 单元测试主要测试那几方面的问题？（5分） 答：模块接口、局部数据结构、边界条件、独立的路径和错误处理。五，设计题 开放英语(1)期末考试模拟试题(及答案) 一、语音知识 ( 每题1分, 共5分) 比较下列各组单词的读音, 从A、 B、 C、 D中找出一个其划线部分与其它三个划线部分发音不同的选题。 1.( ) A. fast B. water C. dance D. ask 2. ( ) A. cup B. but C. rush D. during 3. ( ) A. food B. soon C. cool D. book 4. ( ) A. hear B. earn C. dear D. near 5. ( ) A. article B. sharp C. quarter D. harm 二、词语填空 ( 每题1分, 共5分) 6. The boy looked, but he could not ________ anything. A. look B. looked C. look at D. see 7. Speak loudly, please. I can’t ________ you. A. listen B. listen to C. hear D. heard 8. Lei Feng liked helping ________. A. some B. another C. other D. others 9. He was late ________ the bus. A. because B. because of C. for D. but 10. She can ________ English well. A. say B. talk C. speak D. tell 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 数据库期末考试试题 ━━━━━━━━━━━━━━━ 一、填空共30题（共计30分） ━━━━━━━━━━━━━━━ 第1题（分）题号:2385 ORDER BY 子句实现的是【1】. 答案： =======(答案1)======= 排序 第2题（分）题号:2374 如果列上有约束,要删除该列,应先删除【1】 答案： =======(答案1)======= 相应的约束 第3题（分）题号:2394 在每次访问视图时,视图都是从【1】中提取所包含的行和列. 答案： =======(答案1)======= 基表 第4题（分）题号:2372 1.在增加数据文件时,如果用户没有指明文件组,则系统将该数据文件增加到【1】文件组.答案： =======(答案1)======= 主 第5题（分）题号:2371 查看XSCJ数据库信息的存储过程命令是【1】 答案： =======(答案1)======= sp_helpdb 第6题（分）题号:2392 创建视图定义的T-SQL语句的系统存储过程是【1】. 答案： =======(答案1)======= sp_helptext 第7题（分）题号:2379 1.表的外键约束实现的是数据的【1】完整性. 答案： =======(答案1)======= 参照 第8题（分）题号:2390 要进行模糊匹配查询,需要使用【1】关键字来设置查询条件. 答案： =======(答案1)======= LIKE 第9题（分）题号:2380 定义标识列的关键字是【1】. 答案： =======(答案1)======= identity 第10题（分）题号:2383 在进行多表查询是,必须设置【1】条件. 答案： =======(答案1)======= 连接 第11题（分）题号:2363 联系两个表的关键字称为【1】 答案： =======(答案1)======= 外键 第12题（分）题号:2382 用【1】字句可以实现选择行的运算. 答案： 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 《国际贸易实务》 期末考试模拟试题及答案 参考答案： 一、是非判断题（正确用“√”表示，错误用“X”表示。每题1分，共20分） 1．按照INCOTERMS2000的规定，卖方在CIF术语下承担的风险、责任和费用要比FOB术语下的大。（X ）2．按照INCOTERMS2000的规定，在所有的贸易术语下，出口强制检验的费用都由卖方承担。（X ）3．按照INCOTERMS2000的规定，按CIF术语成交，海运途中的风险由买方承担，卖方对货物的延误或灭失不承担责任，因此，合同中如果作出相反的规定是无效的。（X ） 4．按照FOB Under Tackle的规定，卖方的交货地点是买方指定船舶的吊钩所及之处。（X ） 5．在品质公差范围内的货物，买方不得要求调整价格。（√ ） 6．某商品每箱体积为30cm×40cm×50cm，毛重为62kgs，净重为59kgs，如果班轮运费计收标准为W/M，则船公司应按尺码吨计收运费。（X ） 7．海运货物保险中的战争险责任起讫不是采用“仓至仓”，而是仅限于“水面危险”。（√ ） 8．ICC恶意损害险不承保出于政治动机的人的行动所造成的货物的灭失和损害。（√ ） 9．不清洁提单是指带有宣称货物及/或包装有缺陷状况的条款或批注的提单。如，提单上批注“货物由旧麻袋包装”。（X ） 10．航空运单和海运单都不是物权凭证，收货人都是凭到货通知提货。（√ ） 11．UCP500规定，信用证修改通知书有多项内容时，只能全部接受或全部拒绝，不能只接受其中一部分而拒绝另一部分。（√ ） 12．UCP500规定，在分期装运中任何一期未按规定装运，则本期及以后各期均告失效。（√ ） 13．在国际贸易中，如果买方没有利用合理的机会对所收到的货物进行检验，就是放弃了检验权，也就丧失了拒收货物的权利。（√ ） 14．在国际货物买卖中，如果交易双方愿意将履约中的争议提交仲裁机构裁决，则必须在买卖合同中订立仲裁条款，否则仲裁机构将不予受理。（X ） 15．按《联合国国际货物销售合同公约》的规定，发盘可以撤回，其条件是发盘人的撤回通知必须在受盘人发出接受通知前传达到受盘人。（X ） 16．在票汇业务中，收款人是持以银行为受票人的银行汇票办理提款手续，所以，票汇业务属于银行信用。（X ） 17．光票托收是指金融单据不附有商业单据的托收，而跟单托收是指金融单据附有商业单据的托收。（X ）18．银行汇票的付款人是银行，而商业汇票的付款人可以是银行，也可以是商号、个人。（√ ） 19．按国际招标惯例，如招标人在评标过程中认为所有的投标均不理想从而不想选定中标人，也可宣布招标失败，拒绝全部投标。（√ ） 20．卖期保值是指从事现货交易的商人为避免现货市场价格变动的风险，在买进现货的同时，在期货市场上卖出同等金额、同一交货期的期货，然后再以多头进行平仓的做法。（X ） 二、选择题（答案可能为一个或多个选项，每题2分，共20分） 1．以下贸易术语中，（BC ）只适用于水上运输。 A．DEQ B．FOB C．FAS D．DDU 2．在国际贸易中，如果卖方交货数量多于合同规定的数量，根据《联合国国际货物销售合同公约》的解释，买方可以（ACD ）。 A．接受全部货物B．拒绝全部货物C．只接受合同规定货物而拒绝多交部分D．接受合同规定数量及多交部分中的一部分 一、选择题（每题1分，共20分） 1．在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。在这几个阶段中，数据独立性最高的是（ A ）阶段。 A. 数据库系统 B. 文件系统 C. 人工管理 D.数据项管理 2．数据库三级视图，反映了三种不同角度看待数据库的观点，用户眼中的数据库称为（D）。 A. 存储视图 B. 概念视图 C. 内部视图 D. 外部视图 3．数据库的概念模型独立于（A）。 A.具体的机器和DBMS B. E-R图 C. 信息世界 D. 现实世界 4．数据库中，数据的物理独立性是指（C）。 A. 数据库与数据库管理系统的相互独立 B. 用户程序与DBMS的相互独立 C. 用户的应用程序与存储在磁盘上的数据库中的数据是相互独立的 D. 应用程序与数据库中数据的逻辑结构相互独立 5．关系模式的任何属性（A）。 A. 不可再分 B. 可再分 C. 命名在该关系模式中可以不惟一 D.以上都不是 6．下面的两个关系中，职工号和设备号分别为职工关系和设备关系的关键字： 职工（职工号，职工名，部门号，职务，工资） 设备（设备号，职工号，设备名，数量） 两个关系的属性中，存在一个外关键字为（ C ）。 A. 职工关系的“职工号” B. 职工关系的“设备号” C. 设备关系的“职工号” D. 设备关系的“设备号” 7．以下四个叙述中，哪一个不是对关系模式进行规X化的主要目的（ C ）。 A. 减少数据冗余 B. 解决更新异常问题 C. 加快查询速度 D. 提高存储空间效率 8．关系模式中各级X式之间的关系为（ A ）。 A. B. C. D. 9．保护数据库，防止未经授权或不合法的使用造成的数据泄漏、非法更改或破坏。这是指数据的（ A ）。 A. 安全性 B.完整性 C.并发控制 D.恢复 10．事务的原子性是指（ B ）。 A. 事务一旦提交，对数据库的改变是永久的 B. 事务中包括的所有操作要么都做，要么都不做 C. 一个事务内部的操作及使用的数据对并发的其他事务是隔离的 D. 事务必须使数据库从一个一致性状态变到另一个一致性状态 11．下列哪些运算是关系代数的基本运算（ D ）。 A. 交、并、差 B. 投影、选取、除、联结 C. 联结、自然联结、笛卡尔乘积 D. 投影、选取、笛卡尔乘积、差运算 2017《数据结构》期末考试试题及答案 《数据结构》期末考试试题及答案 1 ................................................................. 2..试题 1 答案............................................................ 7..《数据结构》期末考试试题及答案 2 ................................................................. 9..试题 2 答案........................................................................ 1.. 4. 《数据结构》期末考试试题及答案 3 ............................................................... 1..6试题 3 答案........................................................................ 2.. 1. 数据结构》期末考试试题及答案 1 单选题（每题 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（io ）, A[2][2]存放 若有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 （ 1 og 2n ） D. O （n2） 9. 对于线性表（ 7， 34， 55， 25， 64， 46， 20， 10）进行散列存储时，若选 用 H （K ）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个， 位置在 676（10），每个元素占一个空间， 表示用 10 进制表示。 问 A[3][3] （10）存放在什么位置？脚注 （10） 5. A ．688 B ．678 C ． 692 D ． 696 树最适合用来表示 （ ）。 A.有序数据元素 B.无序数据元素 6. C.元素之间具有分支层次关系的数据 D .元素之间无联系的数据 二叉树的第 k 层的结点数最多为 （ ）. A ．2-1 B.2K+1 C.2K-1 D. 2k-1 7. 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 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. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 绝密★启用前 秦皇岛职业技术学院 2009-2010_学年第_2_学期609各班期末考试A 卷 《毛泽东思想和中国特色社会主义理论体系概论》 一、多项选择（2分*10=20分） 1、毛泽东思想的科学涵义是（ ） A ．是马克思列宁主义在中国的运用和发展 B.是被实践证明了的关于中国革命和建设的正确的理论原则和经验总结 C ．是中国共产党集体智慧的结晶 D ．是建设有中国特色社会主义的理论 E ．是符合中国实际的革命理论 2、下列关于中国的新民主主义革命的认识正确的是（ ） A 、革命的性质是无产阶级领导的资产阶级的民主主义革命 B 、这场革命已经不再是一般的旧式资产阶级民主革命,而成为新式的资产阶级革命。 C 、 在新民主主义革命条件下革命的任务是为了推翻帝国主义和封建势力，革命有资产阶级的参加，要把封建地主土地所有制变为农民土地所有制，为民族资本主义发展扫清道路并保护之 D 、 新民主主义革命的前途是要建立无产阶级领导的各革命阶级的联合专政，其前途是经由新民主主义走向社会主义 E 、新民主主义革命就是社会主义革命 3、新民主主义革命胜利的“三大法宝”是（ ）。 A 农村包围城市 B 武装夺取政权道路 C 统一战线 D 武装斗争 E 党的建设 4、马克思列宁设想的对资产阶级和平赎买在中国之所以能够实现，是因为（ ） A 、新中国脱胎于半殖民地半封建的社会 B 、民族资本主义经济弱小 C 、民族资产阶级在新中国建立后依然有两面性 D 、中国共产党制定并实行对民族资本主义经济的“利用、限制、改造”政策 E 、新中国建立了强大的政权机构 5、社会主义的本质，是解放生产力，发展生产力，消灭剥削，消除两极分化，最终实现共同富裕。这段话深刻的揭示了( ) A 要坚持科学发展观 B 社会主义发展的根本目的 C 社会主义的根本任务 D 社会主义发展的路径 6、中国社会主义改造道路的特点有（ ） A 、社会主义工业化和社会主义改造同时并举 B 、通过一系列逐步过渡的由低级到高级的社会主义改造形式 C 、和平改造特别是对资产阶级实现了和平赎买 D 、对经济制度的改造与对人的改造相结合 E 、对民族资产阶级的改造实行了专政 7、邓小平指出：“计划经济不等于社会主义，资本主义也有计划；市场经济不等于资本主义，社会主义也有市场。”这一论断表明（ ）。 A ．计划和市场都是经济手段 B ．计划经济与市场经济没有什么本质区别 C ．社会主义以计划经济为主，资本主义以市场经济为主 D ，计划与市场的多少不是资本主义与社会主义的本质区别 8、在实现共同富裕的道路上出富裕程度的差别是（） 。 A ．贯彻按劳分配原则的必然结果 B ．实行多种所有制形式和多种分配方式的必然结果 C ．发展社会主义市场经济必然结果 D ．科技发展水平低的结果 9、社会主义核心价值体系包括四个方面的基本内容（ ） 装 订 线 装 订 线 内 不 要 答 题 学号 姓 名 班 级 贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j 考试模拟题 /////////////////////////////////////////////////// 1.— MSIL __________ 是独立于CPU的指令集，它可以被高效地转换为特定于某种CPU的代码. A.CLR B.CLS C.MSIL Microsoft 中间语言 D.XML Web Service 正确答案: C 2.在Visual https://www.wendangku.net/doc/4014024752.html, 窗口中,在_________ 类视图______ 窗口中可以察看当前项目的类和类型的层次信息 A.解决方案资源管理器 B.类视图 C.资源视图 D.属性 正确答案: B 3.关于C#语言的基本语法,下列哪些说法是正确的？ A.C#语言使用using关键字来引用.NET预定义的名字空间； B.用C#编写的程序中,Main函数是唯一允许的全局函数； C.C#语言中使用的名称严格区分大小写； D.C#中一条语句必须写在一行内； 正确答案: A 、C 4.C# 中每个int 类型的变量占用_________ 个字节的内存. A. 1 btye(0---255) sbtye(-128---127) bool(ture,false) B. 2 short(-32768---32767) unshort(0---32767) char C. 4 int uint float D.8 lo ng ulo ng double 12 decimal 精确的十进制值 object不定(其他所有类型的基类型) stri ng不定(任意长度的Uni code字符序列) 正确答案: C 5.在C#中,表示一个字符串的变量应使用以下哪条语句定义？ A.CString str； B.string str； C.Dim str as string D.char * str； 正确答案: B 6.在C#编制的财务程序中，需要创建一个存储流动资金金额的临时变量，则应使用下列哪条语句？ A.decimal theMoney； B.int theMoney； C.string theMoney； D.Dim theMoney as double 正确答案: A 7. C# 中, 新建一字符串变量str, 并将字符串”Tom's Living Room ”保存到串中, 则应 该 使用下列哪条语 句？ A. string str = 's“LTivoinmg Room ”; B. string str = “ Tom's Living Room ”; C. string str( Tom's Living Room ” )； 毛概期末考试试题 项选择题<每题1分，共15分）1、全面贯彻“三个代表”重要思想的关键在 D、把我国建设成为富强、民主、文明的社会主义现代化国家7、我国的工业化任务还没有完成，总体上看，现在还处于< C） A、农业社会 B、现代化工业社会 C、工业化中期阶段 D、工业化高级阶段 8、实现全面建设小康社会的目标重点和难点在< D） A、大城市 B、中等城市 C、小城镇 D、农村 9、实行以家庭承包经营为基础、统分结合的双层经营体制，是党在农村的基本政策，必须长期坚持。稳定和完善这一双层经营体制的关键和核心是 2005年－2006学年第二学期“数据结构”考试试题（A） 姓名学号(序号)_ 答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 解 D。 5. 一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。 A.edcba B.decba C.dceab D.abcde 答：C。 6. 循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90, 80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94, 40 答：C。 9. 以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80, 77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80, 60,66,98,82,10,20}c期末考试试题及答案完整版
古代汉语期末考试模拟题和答案
2017年数据结构期末考试题及答案A
数据库期末考试模拟试题及答案(一)
最新软件测试期末考试试题及答案
开放英语期末考试模拟试题及答案
数据结构复习资料,java数据结构期末考试
数据库期末考试试题及答案
《数据结构》期末考试题及答案
《国际贸易实务》期末考试模拟试题及答案
数据库期末考试试题及答案
2017数据结构期末考试试题及答案
《数据结构》期末考试试卷
期末考试题及答案
数据结构期末考试试题及答案
C#期末考试模拟试题及答案
2018毛概期末考试试题及答案
数据结构期末考试试题含答案