数据结构与算法期末练习题(含答案)
《数据结构与算法》期末练习
一选择题
1．以下与数据的存储结构无关的术语是（ D ）。
A．循环队列 B. 链表 C. 哈希表 D. 栈
2. 算法的时间复杂度取决于（ A ）
A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu
3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
4. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（ B ）
A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）
5．对于有n 个结点的二叉树, 其高度为（ D ）
A．nlog2n B．log2n C．?log2n?|+1 D．不确定
6．从下列有关树的叙述中,选出正确的叙述（ C ）
A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B．当K≥1时高度为K的二叉树至多有2k-1个结点。
C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
D．在二叉树中插入结点,该二叉树便不再是二叉树。
7．设无向图的顶点个数为n，则该图最多有（ B ）条边。
A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2
8．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={
A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7
C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7
9．下列排序算法中，其中（ D ）是稳定的。
A. 堆排序，冒泡排序
B. 快速排序，堆排序
C. 希尔排序，归并排序
D. 归并排序，冒泡排序
10．对一组数据（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
11. 则采用的排序是 ( A )。
A. 选择
B. 冒泡
C. 快速
D. 插入
12．以下数据结构中，哪一个是线性结构（ D ）？
A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串
13．下面关于线性表的叙述中，错误的是哪一个？（ B ）
A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
14. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。
A. 5 1 2 3 4
B. 4 5 1 3 2
C. 4 3 1 2 5
D. 3 2 1 5 4
15. 设n为正整数.下列程序段中前置以@的语句的频度为（ B ）。
i = 1; k = 0;
do{
@ k+= 10*i;
i++;
}While(i <= n-1);
A. n – 1
B. n
C. n + 1
D. n - 2
16. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）
A．?logn?+1 B．logn+1 C．?logn? D．logn-1
17．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。
A. 不确定
B. n-i+1
C. i
D. n-i
18．n个结点的完全有向图含有边的数目（ D ）。
A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）
19．稳定的排序方法是（ B ）
A．直接插入排序和快速排序 B．折半插入排序和起泡排序
C．希尔排序和四路归并排序 D．树形选择排序和shell排序
20．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。
A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
21．以下那一个术语与数据的存储结构无关？（ A ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表
22．下面关于串的的叙述中，哪一个是不正确的？（ B ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
23. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ D ）。
A. a，c，b，d
B. b, c，d，a
C. c, d，b, a
D. d, c，a，b
24. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是（ D ）
A．①②③ B．②③④ C．②④ D．①④
25．高度为 K的二叉树最大的结点数为（ C ）。
A．2k B．2k-1 C．2k -1 D．2k-1-1
26．从下列有关树的叙述中,选出正确的叙述（ C ）
A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。
B．当K≥1时高度为K的二叉树至多有2k-1个结点。
C．用树的前序遍历和中序遍历可以导出树的后序遍历。
D．哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较近。
27. 关键路径是事件结点网络中（ A ）。
A．从源点到汇点的最长路径 B．从源点到汇点的最短路径
C．最长回路 D．最短回路
28．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。
A．逆拓扑有序 B．拓扑有序 C．无序的
29．一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。
A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)
C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)
30. 一个向量的第一个元素的地址是begin，每个元素的长度是k ，则第i个元素的地址是( D )
A. begin+(k-1)i
B. begin+(k-2)i
C. begin+ki
D. begin+(i-1)k
31. 有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找63，要经过( C )次与63比较。
A. 12
B. 6
C. 4
D. 5
32. 一个序列的初始状态为（46，77，82，53，31，70），今对其进行冒泡排序，当进行两趟冒泡后，序列中的元素排列为( D )。
A.（31，46，70，53，77，82）
B.（46，77，53，31，70，82）
C.（46，31, 82，53，77，70）
D. (46 ，53，31，70，77，82)
33. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )个元素。
A. i
B. n-i
C. n+1
D. n-i+1
34. 不带表头的单链表，头指针为head ，判断其是否为空的条件是( A )
A. head==0
B. head->next==null
C. head==head
D. head->next==head
35. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是( A )。
A) q->next=s; s->next =p B) s->next=p->next; q->next=s;
C) p->nexr=s; s->next=p ; D) p->next=s; s->next=q;
36. 非空循环链表head 的尾结点 *p 满足下列( C )条件
A) head->next==p; B) head==p; C) p->next==head; D) p->next==0
37. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。
A. ecdab B) cebda C) daecb D) abcde
38. 设栈s的类型为sqstack ，判定栈空的条件是( C )。
A. s==NULL B) s->top==0 C) s.top==0 D) s.top==NULL
39. 深度为5 的二叉树至多有个( B )结点。
A. 12
B. 31
C. 14
D. 15
40. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二叉树的前根遍历序列是( C )。
A) defbca B) fedbca C) abcdef D) fedcba
41. 一个有n个顶点的有向图最多有( B )弧。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) n(n-1)/2
42. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连通图。
A) n(n+1) B) n-1 C) n+1 D) n(n-1)
43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( B )。
A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 2
44. 一个向量的第一个元素的地址是100，每个元素的长度是 2 ，则第五个元素的地址是( C )
A) 102 B) 110 C) 108 D) 120
45. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear ，则队列中元素个数为( A )。（maxlen 为循环顺序表的长度） A. (rear-front+maxlen) % maxlen B. (rear-front) % maxlen C. rear-front+1 D. front-rear+1
46. 一个有n 个顶点的图最少有( D )条边。
A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0
47. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连通图。 A) 4 B) 5 C) 6 D) 7
48. 设栈s 的类型为sqstack ，最多可容纳maxlen 个元素，则判定栈满的条件是( B )。 A. s==maxlen-1 B) s.top==maxlen-1 C) s->top==maxlen-1 D) s.top==0
49. 一个顺序队列q 的类型为sqqueue,队头、尾指针分别为front,rear ，最多可容纳maxlen 个元素，则队空的条件是( C )。
A) front==rear B) rear==0 C) q.front==q.rear D) rear==maxlen-1
50. 在具有n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( B )
A.O(1)
B.O(n)
C.O(nlogn)
D.O(n*n)
51. 链栈与顺序栈相比，比较明显的优点是( D )
A.插入操作更加方便
B.删除操作更加方便
C.不会出现下溢的情况
D.不会出现上溢的情况
52. 二叉树中第5层上的结点个数最多为( C )
A.8
B.15
1 2 3 4
C.16
D.32
53. 下列编码中属前缀码的是( A )
A.{1,01,000,001}
B.{1,01,011,010}
C.{0,10,110,11}
D.{0,1,00,11}
54. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ B ）
A．深度优先搜索算法B．广度优先搜索算法
C．求最小生成树的prim算法D．拓扑排序算法
55. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( B )
A.O(1)
B.O(logn)
C.O(n)
D.O(n logn)
56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( C )
A. (n-1)/2
B. n/2
C. (n+1)/2
D. n
57. 对于哈希函数H(key)=key%13,被称为同义词的关键字是( D )
A.35和41
B.23和39
C.15和44
D.25和51
58. 关于线性表的说法,下面选项正确的是（ B ）
A 线性表的特点是每个元素都有一个前驱和一个后继
B 线性表是具有n(n>=0)个元素的一个有限序列
C 线性表就是顺序存储的表
D 线性表只能用顺序存储结构实现
59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为（ A ）
A (n-1)/2
B n/2
C n
D n-1
60. 设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头节点。若想在指针p 所指节点之后插入指针s所指节点，则应执行下列哪一个操作？（ D ）
A p->RLink=s; s->LLink=p;
p->RLink->LLink=s; s->RLink=p->RLink;
B p->RLink=s; p->RLink->LLink=s;
s->LLink=p; s->RLink=p->RLink;
C s->LLink=p; s->RLink=p->RLink;
p->RLink=s; p->RLink->LLink=s;
D s->LLink=p; s->RLink=p->RLink;
p->RLink->LLink=s; p->RLink=s;
61. 栈和队列都是（ A ）
A 限制存取位置的线性结构
B 链式存储的非线性结构
C 顺序存储的线性结构
D 限制存取位置的非线性结构
62. 单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（ A ）
A O(n)
B O(1)
C O(n*n)
D O(n*logn)
63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少？（ C ）
A n-k
B n-k+1
C |log k n|+1
D |log k n| 其中|k|表示下取整
64. 下列序列中( B )不是堆。
A. 12 36 53 68 48 60 75
B. 12 48 53 68 36 60 75
C. 12 48 36 60 75 68 53
D. 12 36 60 53 48 68 75
65. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。
A. 直接插入排序
B. 简单选择排序
C. 快速排序
D. 希尔排序
66. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其中s.top为栈顶指针，s.elem为栈空间，出栈的元素存放在x中。
A. s.top:=s.top+1;
B. x:=s.elem[s.top];
x:=s.elem[s.top]; s.top:=s.top+1;
C. s.top:=s.top-1;
D. x:=s.elem[s.top];
x:=s.elem[s.top]; s.top:=s.top-1;
67. 已知L是带头结点的单链表，p指向表中某结点，则要删除p结点的后继结点应执行操作( A )；要在p结点后插入s结点应执行操作( D )。
A. p→next:=p→next→next;
B. p→next→next:= →.next;
C. p→next:=s; s→next:=p→next;
D. s→next:=p→next; p→next:=s;
68. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序（ D ）。
A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆
69. 下面给出的四种排序法中( D )排序法是不稳定性排序法。
A. 插入
B. 冒泡
C. 二路归并
D. 快速排序
70. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。
A. 快速排序
B. 堆排序
C. 归并排序
D. 直接插入排序
二填空题
1、在单链表L中，指针p所指结点有后继结点的条件是：
p->next!=null
2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是：
(请在表达式中用点(.)将数隔开)
23.12.3*2-4/34.5*7/++108.9/+
3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是
60
4、深度为9的完全二叉树具有的个结点
256
5、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是
ABDEGCF
6、先根遍历树林正好等同于按__ _遍历对应的二叉树.
先序
7、构造n个结点的强连通图，至少有_______条弧。
n
8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为
6,9,11,12
9、在单链表指针为p的结点之后插入指针为s的结点的操作是：s->next=p->next;p->next=s;
10、有N个顶点的有向图，至少需要量_______条弧才能保证是连通的。
N-1
11、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值12，需做的关键码比较次数为
4
13、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处（顶点号由1开始）
0 1 0 1 1
1 0 1 0 0
0 1 0 1 0
1 0 1 0 1
1 0 0 1 0
该图的顶点数为该图的边数为顶点3的度为。
5 6 2
14、后根遍历树林正好等同于按__(6) _遍历对应的二叉树。
中序
15、n个结点的完全有向图含有边的数目__(7)
n*（n－l）
16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的________。时间复杂度
17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”的操作序列为___________。
SXSSXXSSXSSXXX
18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结
点个数是________。
2
19、如图所示的有向无环图可以排出________种不同的拓扑序列。
12
20、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。
75, 66, 48, 29, 31, 37
21、对长度为20的有序表进行二分查找的判定树的高度为________。
5
22、n个顶点的连通无向图，其边的条数至少为________________________。
n-1
23、排序(sorting)有哪几种方法_______________，_____________，____________，
_____________，____________。
直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等
24、下面程序段的时间复杂度为______________。（用O估计）
FOR i:=1 TO n DO
FOR j:=i TO n DO
s=s+j;
O（n*n）
25、非线性结构包括______________和_________________。
树，图
26、在线性表的___________存储结构上进行插入或删除操作要移动元素。
顺序存储结构
27、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front
和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，
队空的条件是_____________________________。
Front=rear, rear+1=front
28、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀
表达式是____________________________。
+*a-bc/de , abc-*de/+
a的最早开始时间和最晚开始时间，则当且
29、在AOE-网中，设e(i)和l(i)分别表示活动i
a为关键活动。
仅当_________________时，i
e(i)==l(i)
30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。
存在回路，123456798
31、二叉排序树的特点是其序列是有序的。
中序遍历
三简答题
1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性；
（3）散列法(hashing)；（4）索引文件。
2、堆与二元查找树的区别?
3、快速分类法的基本思想是什么?
4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？
5、二叉树的后根遍历的序列中，任何一个非叶子结点均处在其孩子结点后面。该论断是否正确？
6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。
7、对于一个队列，若入队的顺序为a,b,c, 则所有可能的出队序列是什么？
8、已知一个图如下，试画出其逆邻接链表。
9、若一个栈的输入序列是1,2,3……，n, 其输出序列为p1,p2,……pn,
若 p1=n，则pi为多少？
10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？
11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。
12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？
13、栈的存储方式有哪两种？
14、对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针p，能否将p所指结点的数据元素与其确实存在的直接前驱交换?请对每一种链表作出判断，若可以，写出程序段；否则说明理由。其中：
单链表和单循环链表的结点结构为 双向链表的结点结构为
15、假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
16、对于线性表的两种存储结构（顺序存储和链式存储结构），如果线性表基本稳定，并且很少进行插入和删除操作，但是要求以最快速度存取线性表中的元素，则应选择哪种存储结构？试说明理由。
17、内存中一片连续空间（不妨假设地址从1到m ）提供给两个栈s1和s2使用，怎样分配这部分存储空间，使得对任一栈，仅当这部分空间全满时才发生上溢。如何判断栈满，栈空，并对两个栈的容量进行分析。
18、设某二叉树的前序遍历序列为：ABCDEFGHI ，中序遍历序列为：BCAEDGHFI 。（1）试画出该二叉树；（2）画出该二叉树后序线索化图。（3）试画出该二叉树对应的森林。
19、 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。
20、 试证明：若借助栈由输入序列1,2,…,n 得到输出序列为P 1,P 2,…,P n （它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i 四 算法阅读 1、void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) print(Pop(S)); } 该算法被调用后得到的输出结果为： 2、 void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if } 该函数执行的功能是什么？ 3、在下面的每个程序段中，假定线性表La的类型为List，e的类型为ElemType,元素类型ElemType为int，并假定每个程序段是连续执行的。试写出每个程序段执行后所得到的线性表La。 （1）InitList(La); Int a[]={100,26,57,34,79}; For (i=0;i<5;i++) ListInsert(La,1,a[i]); （2）ListDelete(La,1,e); ListInsert(La,ListLength(La)+1,e); （3）ClearList(La); For (i=0;i<5;i++) ListInsert(La,i+1,a[i]); 4、int Prime(int n) { int i=1; int x=(int) sqrt(n); while (++i<=x) if (n%i==0) break; if (i>x) return 1; else return 0; } (1)指出该算法的功能； (2)该算法的时间复杂度是多少？ 5. 写出下述算法A的功能： 其中BiTree定义如下: Typedef struct BiTNode{ TElemType data; struct BiTNode *LChild, *RChild; }BiTNode, *BiTree; Status A(BiTree T) { Queue Q; InitQueue(Q); ENQueue(Q,T); While(not QueueEmpty(Q)) { DeQueue(Q,e); If(e==NULL) break; Else { Print(e.data); ENQueue(Q,e.LChild); ENQueue(Q.e.RChild); } } } 6.阅读下列函数algo,并回答问题： (1)假设队列q中的元素为(2,4,5,7,8),其中“2”为队头元素。写出执行函数调用algo(&q) 后的队列q； (2)简述算法algo的功能。 void algo(Queue *Q) { Stack S; InitStack(&S); while (!QueueEmpty(Q)) Push(&S, DeQueue(Q)); while (! StackEmpty(&S)) ＥnQueue(Q,Pop(&S)); } 五算法填空 1、下面是在带表头结点的循环链表表示的队列上，进行出队操作，并将出队元素的值保留在x中的函数，其中rear是指向队尾结点的指针。请在横线空白处填上适当的语句。 typedef struct node { int data; struct node *next; } lklist; void del( lklist rear, int &x); { lklist p,q; q=rear-> next; if (__________) printf( “it is empty!\n” ); else { p=q->next; x=p->data; _________________ ; if (___________) rear=q; ; }; }; 2、堆分配存储方式下，串连接函数。 typedef struct { char * ch； int len； } HString； HString *s， t; Status StrCat(s， t) /* 将串t连接在串s的后面 */ { int i; char *temp; f if (temp==NULL) return(0); for (i=0; ;i++) temp［i］=s->ch［i］; for ( ;i temp［i］=t.ch［i-s->len］; s->len+=t.len; fr s->ch=temp; return(1); } 3、向单链表的末尾添加一个元素的算法。 LNode是一个包含（data，Next）的结构体 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<"Memory allocation failare!"< exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 4、L 为一个带头结点的循环链表。函数f30的功能是删除L 中数据域data 的值大于c 的所有结点，并由这些结点组建成一个新的带头结点的循环链表，其头指针作为函数的返回值。请在空缺处填入合适的内容，使其成为一个完整的算法。 LinkList f30(LinkList L, int c) { LinkList Lc,p,pre; pre=L; p= (1) ; Lc=(LinkList) malloc(sizeof(ListNode)); Lc->next=Lc; while(p!=L) if(p->data>c) { pre->next=p->next; (2) ; Lc->next=p; p=pre->next; } else { pre=p; (3) ; } return Lc; } 5、已知图的邻接链表的顶点表结点结构为 边表结点EdgeNode 的结构为 下列算法计算有向图G 中顶点v i 的入度。请在空缺处填入合适的内容，使其成为一个完整 的算法。 int FindDegree(ALGraph *G,int i)//ALGraph 为图的邻接表类型 { int dgree, j; EdgeNode *p; degree= (1) ; for(j=0;j p=G->adjlist ［j ］. firstedge; while ( (2) ) { if( (3) ) { degree++; break; } p=p->next; } } return degree; } 六简单应用题 1、已知一个非空二元树，其按中根和后根遍历的结果分别为： 中根：C G B A H E D J F I 后根：G B C H E J I F D A 试将这样二元树构造出来;若已知先根和后根的遍历结果，能否构造这棵二元树，为什么? 2、对于下图，画出按Kruskal（克鲁斯卡尔）算法和Prim（普里姆）算法构造最小生成树的过程。 3、画出由下面的二叉树转换成的森林。 4、用Floyed（弗洛伊徳）算法求下图每一对顶点之间的最短路径及其长度，将计算过程的中间和最后结果填入下表： 5、哈夫曼树在构造时，首先进行初始化存储空间，结果如左下图，当构造完成后，请填写最后状态表，如右下图。 weigh t Paren t Lchil d Rchil d weigh t Paren t Lchil d Rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 6、考虑右图： (1)从顶点A 出发，求它的深度优先生成树(4分) (2)从顶点E 出发，求它的广度优先生成树(4分) (3）根据普利姆(Prim) 算法，求它的最小生成树(请画出过程) (设该图用邻接表存储结构存储，顶点的邻接点按顶点编号升序排列)(6分) 答案如下： 七编写算法题 1、设计函数，求一个单链表中值为x的结点个数。并将结果放在头结点的data 域中。 void count1(lklist head,int x) 2、设计递归函数，求一棵二叉树的深度。 int depth (bitreptr root) 3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct { int data[ maxsize][maxsize]; int dem,e; }sqgraph; sqgraph crt (sqgraph g) 4、设计函数，将不带表头结点的单链表清除。 5、设计递归函数，求一棵非空的二叉树的深度。 6、设线性表A=(a1,a2,a3,…,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。 7、试编写一个算法，能由大到小遍历一棵二元树。 8、假设二元树用左右链表示，试编写一算法，判别给定二元树是否为完全二元树? 9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。 10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。 11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明零时变量、指针）。 该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode { ElemType data; Struct LNode* next; }List, LNode; 函数定义：void invert(List & L) 12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{ DataType data; Struct BiTNode *LChild, * RChild; }BiTNode, *BiTree; 函数定义：CountLeaf (BiTree T, int & LeafNum) 13、写出二叉树前根遍历的递归算法 已知二叉树结点定义为： struct node{ elemtp data; struct node *lc,*rc; ); Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点 void preorder(bitreptr P) { If(P!=0) { printf(P->data); preorder(P->lc); preorder(P->rc); } } 14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; 第一章练习题 一、单项选择题 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. 发达市场经济国家 B. 发展中国家 C. 社会主义国家 D.美国 8. 一些海岛国家，如英国、日本，也常用以表示对外贸易的是（） A. 国际贸易 B. 转口贸易 C. 海外贸易 D.货物贸易 9. 关于国际贸易的统计方法，我国采用的是（） A. 国际贸易额 B.国际贸易量 C.总贸易体系 D.专门贸易体系 10. 下列指标中，剔除了价格变动影响的是（） A.对外贸易值 B.对外贸易量 C.对外贸易额 D.贸易差额 二、多项选择题 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．贸易政策 E．运输条件 6．就对外贸易与国内贸易的不同点来说，下列表述正确的有（）A．对外贸易的困难比国内贸易多 B．从交易过程来看，对外贸易与国内贸易有着明显的区别 C．对外贸易与国内贸易的经营目的不一样 D．对外贸易比国内贸易复杂 E．对外贸易比国内贸易风险大 7．下列国家中，采用总贸易体系统计国际货物贸易的国家有（） A. 英国 B. 法国 C. 日本 D 德国 E 澳大利亚 8．对外贸易构成可以反映出该国的（） A．经济发展水平 B. 产业结构状况 C．服务发展水平 第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 云计算与虚拟化考试 一、单项选择题(每题2分,共45题) 1、云计算就是把计算资源都放到上（B ） A、对等网 B、因特网 C、广域网 D、无线网 2、我们常提到的"Window装个VMware装个Linux虚拟机"属于（C） A、存储虚拟化 B、内存虚拟化 C、系统虚拟化 D、网络虚拟化 3、简单的理解为云计算等于资源的闲置而产生的。（A） A、正确 B、错误 4、一个有10个硬盘组成的Raid5阵列最多可以允许（D）个硬盘出现故障不影响其数据的完整性。 A、1个 B、2个 C、4个 D、5个 5、相比各种网路存储的设置技术来讲，本地硬盘还是最快的（A ）。 A、正确 B、错误 6、SaaS是（A ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 7、微软于2008年10月推出云计算操作系统是（C） A、GoogleAppEngine B、蓝云 C、Azure D、EC2 8、虚拟化资源指一些可以实现一定操作具有一定功能，但其本身是（A ）的资源，如计算池，存储池和网络池、数据库资源等，通过软件技术来实现相关的虚拟化功能包括虚拟环境、虚拟系统、虚拟平台。 A、虚拟 B、真实 C、物理 D、实体 9、云计算是对（D）技术的发展与运用 A、并行计算 B、网格计算 C、分布式计算 D、三个选项都是 10、虚拟交换机可以连多块物理网卡，所以同一块物理网卡可以连多个虚拟交换机。(B ) A、正确 B、错误 11、（D ）在许多情况下，能够达到99.999%的可用性。 A、虚拟化 B、分布式 C、并行计算 D、集群 12、下列哪个特性不是虚拟化的主要特征（D） A、高扩展性 B、高可用性 C、高安全性 D、实现技术简单 13、与开源云计算系统HadoopHDFS相对应的商用云计算软件系统是（A） A、GoogleGFS B、GoogleMapReduce C、GoogleBigtable D、GoogleChubby 14、IaaS是（C ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 15、云计算可以把普通的服务器或者PC连接起来以获得超级计算机计算机的计算和存储等功能，但是成本更低。(A) A、正确 B、错误 16、Raid1是备份量极高的Raid策略，相应的他的保护能力也很强（B）。 A、正确 单项选择 1、1.反映一国一定时期内真正贸易规模的指标为（）（分数：1分） A. 对外贸易额 B. 对外贸易量 C. 贸易条件 D. 贸易差额 正确答案：B 2、专门贸易体系是指以（）作为标准统计进出口。（分数：1分） A. 关境 B. 国境 C. 货物进出口 D. 服务进出口 正确答案：A 3、货币差额论的代表人物是（）。（分数：1分） A. 托马斯?孟 B. 亚当?斯密 C. 威廉?斯塔福 D. 李斯特 正确答案：C 4、赫克歇尔和俄林的理论是（）。（分数：1分） A. 重商主义 B. 绝对成本说 C. 比较成本说 D. 要素禀赋说 正确答案：D 5、世界市场上通过供求公开竞争而形成的价格是（）。（分数：1分） A. 封闭市场价格 B. 调拨价格 C. 内部价格 D. 自由市场价格 正确答案：D 6、发达国家给予发展中国家的非歧视、非互惠关税为（）关税。（分数：1分） A. 正常 B. 优惠 C. 约束 D. 普惠制 正确答案：D 7、下列不属于直接非关税壁垒的是（）。（分数：1分） A. 进口押金制 B. 进口配额制 C. 进口许可证 D. “自动”出口限制 正确答案：A 8、下列不属于直接非关税壁垒的是（）。（分数：1分） A. 进口押金制 B. 进口配额制 C. 进口许可证 D. “自动”出口限制 正确答案：A 9、接参加国的经济发展水平划分，经济发展水平大致相同大的国家与地区间所组成的一体化是（）。 A. 垂直经济一体化 B. 水平经济一体化 C. 部门经济一体化 D. 全盘经济一体化 正确答案：B 10、中国于（）正式加入世界贸易组织。（分数：1分） A. 1945年 B. 1995年 C. 2000年 D. 2001年 正确答案：D 11、《2010年通则》中买方责任最大的贸易术语是（）。（分数：1分） A. EXW B. CIF C. DES D. DDP 正确答案：A 12、凡凭样品买卖，如合同中无其他规定，则卖方所交的货物（）。（分数：1分） A. 可以与样品大致相同 B. 许可合理的公差 C. 必须与样品一致 D. 可以与样品不同 正确答案：C 13、我出口机器一批，合同规定应符合ISO9001,这种规定品质的方法是（）。（分数：1分） A. 凭规格买卖 B. 凭等级买卖 C. 凭标准买卖 D. 凭说明书买卖 正确答案：C 14、某外商欲购我“飞龙”牌电扇，但要求改用“赏月”商标，并不得注明产地和厂商名称。外商这一要求属于( )。 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 云计算期末考试总结 Engine。什么是SaaS？它的针对性更强，它将某些特定应用软件功能封装成服务，如Salesforce公司提供的在线客户关系管理CRM服务。云计算技术体系结构分为四层：物理资源层、资源池层、管理中间件层和SOA构建层（管理中间件层和资源池层是云计算技术的最关键部分）物理资源层包括计算机、存储器、网络设施、数据库和软件。资源池层是将大量相同类型的资源构成同构或接近同构的资源池，如计算资源池、数据资源池。构建资源池更多的是物理资源的集成和管理工作。管理中间件层负责对云计算的资源进行管理，并对众多应用任务进行调度，使资源能够高效、安全地为应用服务。大数据具有4V+1C的特征：（1）、数据量大（2）、多样（3）、快速（4）、价值密度低（5）、复杂度全球企业的IT开销分为三部分:硬件开销、能耗和管理成本。云计算的优势：云计算有更低的硬件和网络成本、更低管理成本和电力成本以及更高的资源利用率。云计算与大数据之间的关系：大数据是需求，云计算是手段。没有大数据，就不需要云计算。没有云计算就无法处理大数据。什么是云计算：长定义：云计算是一种商业计算模型。它将计算任务分布在大量计算机构成的资源池上，使各种应用系统能够根据需要获取计算力、存储空间和信息服务。短定义：云计算是通过网络按需提供可动态伸缩的廉价计算服务。云计算的管理中间件层:负责资源管理、任务 管理、用户管理、和安全管理等工作。资源管理:负责均衡地使用云资源节点，检测节点的故障并试图恢复或屏蔽它，并对资源的使用情况进行监视统计；任务管理:负责执行用户或应用提交的任务，包括完成用户任务映像部署和管理、任务调度、任务管理、生命周期管理。简述亚马逊的云计算：AWS率先在全球提供了弹性计算云EC2和简单服务存储服务S3，为企业提供计算和存储服务。亚马逊是最大的服务商，谷歌是最大的云计算技术的使用者。第二章Google云计算技术包括：Google文件系统 GFS、分布式计算编程模型MapReduce、分布式锁服务Chubby、分布式结构化数据表Bigtable。当前主流分布式文件系统有哪些?各有什么优缺点？答：RedHat的GFS（Global File System）、IBM的GPFS、Sun的Lustre等。优缺点：①GFS采用廉价的商品机器构建分布式文件系统，同时将GFS的设计与Google应用的特点紧密结合，简化实现，GFS将容错的任务交给文件系统完成，利用软件的方法解决系统可靠性问题，使存储成本下降；GFS将服务器故障视为正常现象，并采用多种方法、从多个角度，使用不同的容错措施，确保数据存储的安全、保证提供不间断的数据存储服务。 ②IBM GPFS并行文件系统软件在设计上不存在任何性能瓶颈，因此GPFS并行文件系统可以充分发挥硬件系统的性能。换句话说，GPFS并行文件系统的性能完全取决于硬件配置的好坏，而文件系统软件本身对性能的影响微乎其微。IBM GPFS并行文件系统与其它并行文件系统之间最大的区别在于GPFS不需要专用的元数据 2010--2011学年度第二学期《国际贸易原理》期末 复习 一、名词解释 1、产业内贸易：是产业内国际贸易的简称，是指一个国家或地区，在一段时间内，同一产业部门产品既进口又出口的现象。 2、贸易差额：是一国在一定时期内（如一年、半年、一季、一月）出口总值与进口总值之间的差额。当出口总值与进口总值相等时，称为“贸易平衡”。当出口总值大于进口总值时，出现贸易盈余，称“贸易顺差”或“出超”。当进口总值大于出口总值时，出现贸易赤字，称“贸易逆差”或“入超”。 3、对外贸易依存度：又称为对外贸易系数，是指一国的对外贸易值占该国国民生产总值的比重。反映一国对国际市场的依赖程度，是衡量一国对外开放程度的重要指标。 4、易货贸易：指一国和另一国用货物相互交换的一种贸易方式。 5、转移价格：又称调拨价格，指跨国公司根据其全球利润最大化的战略目标，在跨国公司系统内部、母公司与子公司、子公司与子公司之间销售商品时所采用的价格。 6、自由贸易政策：自由贸易政策是自由放任经济政策的一个重要组成部分。国家取消对进出口贸易和服务贸易的限制和障碍，取消对本国进出口贸易和服务贸易的各种特权和优待，使商品自由进出口，服务贸易自由经营，也就是说国家对贸易活动不加或少加干预，任凭商品、服务和有关要素在国内外市场公平、自由的竞争。 7、多边出口管制：是指几个国家政府为了共同的政治与经济目的，通过一定方式建立国际性的多边出口管制机构，商讨和编制多边出口管制货单和出口管制国别，规定出口管制办法等，以协调彼此的出口管制政策和措施。 8、保护贸易政策: 国家广泛利用各种措施对进口和经营领域与范围进行限制，保护本国的产品和服务在本国市场上免受外国产品和服务的竞争，并对本国出口的产品和服务给予优待与补贴。国家对于贸易活动进行干预，限制外国商品、服务和有关要素参与本国市场竞争。 9、自由经济区：是一国为了发展经济，扩大对外贸易，在国内适当地区专门划出一定范围，实行豁免海关管制，减免税收等特殊优惠政策的地区。 10、最惠国待遇：又称“无歧视待遇”。是国际经济贸易关系中常用的一项制度，是国与国之间贸易条约和协定的法律待遇条款，在进出口贸易、税收、通航等方面互相给予优惠利益、提供必要的方便、享受某些特权等方面的一项制度。 11、国际服务贸易壁垒：是指一国政府对国外生产的服务销售所设置的有阻碍作用的政策措施。该定义中的国际服务贸易壁垒仅仅增加国外的服务生产者的负担，并且"壁垒"(barrier)指国际贸易政策中贸易保护主义措施体现的形式。 12、服务贸易自由化就是各成员方通过多边贸易谈判，降低和约束关税，取消其他贸易壁垒，消除国际贸易中的歧视待遇，扩大本国市场准入度。实现上述目标的途径是以市场经济为基础，进行贸易自由化。自由贸易政策允许货物和生产要素的自由流动，在国际价值规律作用下，可以刺激竞 1 / 8 《云平台与存储技术》2016-2017-2 复习题目 一选择题 1.云计算是对（）技术的发展与运用； A.并行计算B网格计算C分布式计算D三个选项都是； 答案：D 2.从研究现状上看，下面不属于云计算特点的是（）； A.超大规模 B.虚拟化 C.私有化 D.高可靠性； 答案：C 3. https://www.wendangku.net/doc/5015317189.html,公司通过（）计算云，可以让客户通过WEB Service方式租用计算机来运行自己的应用程序。 A. S3 B. HDFS C. EC2 D. GFS 答案：C 5. IBM在2007年11月退出了“改进游戏规则”的（）计算平台，为客户带来即买即用的云计算平台。 A. 蓝云 B. 蓝天 C. ARUZE D. EC2 答案：A 6. 亚马逊AWS提供的云计算服务类型是（） A. IaaS B.PaaS C.SaaS D.三个选项都是 答案：D 7. 将平台作为服务的云计算服务类型是（） A. IaaS B.PaaS C.SaaS D.三个选项都不是 答案：B 8 将基础设施作为服务的云计算服务类型是IaaS，其中的基础设施包括 （） A.CPU资源 B.内存资源 C 应用程序 D.存储资源 E.网络资源 答案：C 9 关于虚拟化的描述，不正确的是（） A 虚拟化是指计算机元件在虚拟的基础上而不是真实的基础上运行。 B 虚拟化技术可以扩展硬件的容量，简化软件的重新配置过程。 C 虚拟化技术不能将多个物理服务器虚拟成一个服务器 D CPU的虚拟化技术可以单CPU模拟多CPU运行，允许一个平台同时运行多个操作系统。答案：C 10 windows azure 属于云服务的哪一类（） A SaaS B PaaS C IaaS D 以上三项都不是 答案：B 11云计算作为中国移动蓝海战略的一个重要部分，于2007年由移动研究院组织力量，联合中科院计算所，着手起步了一个叫做（）的项目。 外经济贸易大学 《国际贸易实务》期末考试试题（A卷） 课程序号：ITR303—（0—4） 学号：姓名： 班级：成绩： 一、是非判断题（正确用“√”表示，错误用“X”表示。每题1分，共20分）1．按照INCOTERMS2000的规定，卖方在CIF术语下承担的风险、责任和费用要比FOB术语下的大。（） 2．按照INCOTERMS2000的规定，在所有的贸易术语下，出口强制检验的费用都由卖方承担。（） 3．按照INCOTERMS2000的规定，按CIF术语成交，海运途中的风险由买方承担，卖方对货物的延误或灭失不承担责任，因此，合同中如果作出相反的规定是无效的。（） 4．按照FOB Under Tackle的规定，卖方的交货地点是买方指定船舶的吊钩所及之处。（） 5．在品质公差范围内的货物，买方不得要求调整价格。（） 6．某商品每箱体积为30cm×40cm×50cm，毛重为62kgs，净重为59kgs，如果班轮运费计收标准为W/M，则船公司应按尺码吨计收运费。（） 7．海运货物保险中的战争险责任起讫不是采用“仓至仓”，而是仅限于“水面危险”。（） 8．ICC恶意损害险不承保出于政治动机的人的行动所造成的货物的灭失和损害。（） 9．不清洁提单是指带有宣称货物及/或包装有缺陷状况的条款或批注的提单。如，提单上批注“货物由旧麻袋包装”。（） 10．航空运单和海运单都不是物权凭证，收货人都是凭到货通知提货。（）11．UCP500规定，信用证修改通知书有多项内容时，只能全部接受或全部拒绝，不能只接受其中一部分而拒绝另一部分。（） 第1页共12页 国际贸易实务 12．UCP500规定，在分期装运中任何一期未按规定装运，则本期及以后各期均告失效。（） 13．在国际贸易中，如果买方没有利用合理的机会对所收到的货物进行检验，就是放弃了检验权，也就丧失了拒收货物的权利。（） 14．在国际货物买卖中，如果交易双方愿意将履约中的争议提交仲裁机构裁决，则必须在买卖合同中订立仲裁条款，否则仲裁机构将不予受理。（） 15．按《联合国国际货物销售合同公约》的规定，发盘可以撤回，其条件是发盘人的撤回通知必须在受盘人发出接受通知前传达到受盘人。（） 16．在票汇业务中，收款人是持以银行为受票人的银行汇票办理提款手续，所以，票汇业务属于银行信用。（） 17．光票托收是指金融单据不附有商业单据的托收，而跟单托收是指金融单据附有商业单据的托收。（） 18．银行汇票的付款人是银行，而商业汇票的付款人可以是银行，也可以是商号、个人。（） 19．按国际招标惯例，如招标人在评标过程中认为所有的投标均不理想从而不想 精心整理 第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5 A 6 {x=x-10;y--;} elsex++; （2）for(i=0;i （4）i=1; while(i<=n) i=i*3; （5）x=0; for(i=1;i （8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。 A．nB．2n-1 C．2nD．n-1 （9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。 A．n-i B．n-i+1 C．n-i-1D．i (10)线性表L=(a1，a2,……a n)，下列说法正确的是（）。 A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素 C．表中诸元素的排列必须是由小到大或由大到小 D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 (11)若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。 2 , pa=La->next;pb=Lb->next; Lc=pc=La;//用La的头结点作为Lc的头结点 while(pa&&pb){ if(pa->data (1) 1.云计算是对（ D ）技术的发展与运用 A. 并行计算 B网格计算 C分布式计算 D三个选项都是 2.IBM在2007年11月退出了“改进游戏规则”的（ A ）计算平台，为客户带来即买即用的云计算 平台。 A.蓝云 B. 蓝天 C. ARUZE D. EC2 3.微软于2008年10月推出云计算操作系统是（ C ） A. Google App Engine B. 蓝云 C. Azure D. EC2 4.2008年，（ A ）先后在无锡和北京建立了两个云计算中心 A. IBM B. Google C. Amazon D. 微软 5.将平台作为服务的云计算服务类型是（ B ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 6.将基础设施作为服务的云计算服务类型是（ A ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 7.IaaS计算实现机制中，系统管理模块的核心功能是（ A ） A. 负载均衡 B 监视节点的运行状态 C应用API D. 节点环境配置 8.云计算体系结构的（ C ）负责资源管理、任务管理用户管理和安全管理等工作 A.物理资源层 B. 资源池层 C. 管理中间件层 D. SOA构建层 9.云计算按照服务类型大致可分为以下类（ A、B、C ） A.IaaS B. PaaS C. SaaS D.效用计算 10.下列不属于Google云计算平台技术架构的是（ D ） A. 并行数据处理MapReduce B.分布式锁Chubby C. 结构化数据表BigTable D.弹性云计算EC2 11.在目前GFS集群中，每个集群包含（ B ）个存储节点 A.几百个 B. 几千个 C.几十个 D.几十万个 12.下列选项中，哪条不是GFS选择在用户态下实现的原因（ D ） A.调试简单 B.不影响数据块服务器的稳定性 C. 降低实现难度，提高通用性 D. 容易扩展 13.GFS中主服务器节点存储的元数据包含这些信息（ BCD ） A.文件副本的位置信息 B.命名空间 C. Chunk与文件名的映射 D. Chunk副本的位置信息 14.单一主服务器（Master）解决性能瓶颈的方法是（ ABCD ） A.减少其在数据存储中的参与程度 B. 不适用Master读取数据 C.客户端缓存元数据 D. 采用大尺寸的数据块 15.（ B ）是Google提出的用于处理海量数据的并行编程模式和大规模数据集的并行运算的软件 架构。 A. GFS B.MapReduce C.Chubby D.BitTable 16.Mapreduce适用于（ D ） A.任意应用程序 B. 任意可在windows servet2008上运行的程序 C.可以串行处理的应用程序 D. 可以并行处理的应用程序 《国际贸易》考试试卷 二、判断题（每小题１分，共10分） 1、在从价税率不变的情况下，从价税额与商品价格的涨落成正比关系。（√） 2、世界国际货物贸易额是各国和地区的货物进口额或货物出口额之和。（╳） 3、根据总贸易体系规定，以国境为标准统计进口额，凡进入国境的商品，不论其是否办理通关 手续，一律列入进口，作为总进口的一部分。（√） 4、战后，在国际分工中，发达国家与发展中国家间的分工居于主导地位。（╳） 5、财政关税的主要目的是增加财政收入，因此，其税率通常较高，以增加关税收入。（╳） 6、关税是海关直接向本国进出口商征收，但它仍是间接税。（√） 7、如果某种贸易对一个人是好事，那么，它就不能对另外一个人也是好事（╳）。 8、贸易会降低本国相对稀缺要素的价格。（√） 9、转移价格是跨国公司内部贸易所采取的价格。（√） 10、如果一国的人口比较多，那么该国一定属于劳动力密集型国家。（╳） 三、选择题（每小题1分，共15分） 1、能够比较确切地反映一国对外贸易实际规模，便于各个时期进行比较的是（D ） A.贸易顺差 B.对外贸易额 C.对外贸易商品结构 D.对外贸易量 2、亚当斯密的国际分工理论是（A ） A.绝对优势理论 B.比较优势理论 C.机会成本学说 D.边际成本学说 4、共同市场在关税同盟的基础上，实现了（B ） A. 对外统一的关税税率 B.生产要素的自由流动 C. 制定某些经济社会政策 D.货物的自由流动 5、某国的国民生产总值为2万亿美元，商品进口值为1200亿美元，出口值为800亿美元，则该国对外贸易依存度为（A ） A. 10% B. 11% C. 12% D. 9% 6、经济同盟与共同市场相比，不同之处在于（C ） A.实现货物的自由移动 B.实现生产要素的自由移动 C.制定和执行统一对外的某些共同的经济与社会政策 D.政策完全一致 7、在商品价格下降的情况下，加强了关税保护作用的税收是（B ） A.从价税 B.从量税 C.选择税 D.混合税 8、贸易顺差是指（A ） A.出口总额大于进口总额 B.进口总额大于出口总额 C.国际收支为正 D.国际收支为负 9、以1990年为基期，2000年某国的进口商品价格指数为120，出口价格指数为144，则该国的净贸易条件为（A ） A. 1.2 B. 0.83 C. 1.1 D. 1.3 10、各国征收反倾销税的目的在于（A ） A.抵制商品倾销，保护本国的市场与工业 B.防止本国商品不顾成本到国外倾销 C.保护本国出口商的利益 D.保护本国进口商的利益 11、我国正式加入世界贸易组织的日期是（C ） A. 2001年11月9日 B. 1997年10月1日 C. 2001年12月11日 D. 1999年11月15日 12、世界贸易组织正式成立的日期为（C ） 云计算期末考试试题和答案解析 云计算与虚拟化考试 一、单项选择题(每题2分,共45题) 1、云计算就是把计算资源都放到上（B ） A、对等网 B、因特网 C、广域网 D、无线网 2、我们常提到的"Window装个VMware装个Linux虚拟机"属于（C） A、存储虚拟化 B、内存虚拟化 C、系统虚拟化 D、网络虚拟化 3、简单的理解为云计算等于资源的闲置而产生的。（A） A、正确 B、错误 4、一个有10个硬盘组成的Raid5阵列最多可以允许（D）个硬盘出现故障不影响其数据的完整性。 A、1个 B、2个 C、4个 D、5个 5、相比各种网路存储的设置技术来讲，本地硬盘还是最快的（A ）。 A、正确 B、错误 6、SaaS是（A ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 7、微软于2008年10月推出云计算操作系统是（C） A、GoogleAppEngine B、蓝云 C、Azure D、EC2 8、虚拟化资源指一些可以实现一定操作具有一定功能，但其本身是 （A ）的资源，如计算池，存储池和网络池、数据库资源等，通过软件技术来 实现相关的虚拟化功能包括虚拟环境、虚拟系统、虚拟平台。 A、虚拟 B、真实 C、物理 D、实体 9、云计算是对（D）技术的发展与运用 A、并行计算 B、网格计算 C、分布式计算 D、三个选项都是 10、虚拟交换机可以连多块物理网卡，所以同一块物理网卡可以连多个虚拟交换机。(B ) A、正确 B、错误 11、（D ）在许多情况下，能够达到99.999%的可用性。 A、虚拟化 B、分布式 C、并行计算 D、集群 12、下列哪个特性不是虚拟化的主要特征（D） A、高扩展性 B、高可用性 C、高安全性 D、实现技术简单 13、与开源云计算系统HadoopHDFS相对应的商用云计算软件系统是（A） A、GoogleGFS B、GoogleMapReduce C、GoogleBigtable D、GoogleChubby 14、IaaS是（C ）的简称。 A、软件即服务 B、平台即服务 C、基础设施即服务 D、硬件即服务 15、云计算可以把普通的服务器或者PC连接起来以获得超级计算机计算机的计算和存储等功能，但是成本更低。(A) A、正确 B、错误 复习题集─参考答案 一判断题 （√）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.折半查找可以在有序的双向链表上进行。 《国际贸易概论练习题》 一、单项选择题 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、补贴和反补贴措施 25、乌拉圭回合谈判的新议题包括与贸易有关的投资措施、服务贸易和_与贸易有关的知识产权___。 6、各国对外贸易政策的制订与修改是由（）进行的。 A、国家行政机构 B、海关 C、国家执法机构 D、国家立法机构 7、1993年11月1日获得所有成员国批准生效并标志欧洲联盟正式成立的条约是（）。 A、《罗马条约》 B、《布鲁塞尔条约》 C、《马斯特里赫特条约》 D、《欧洲单一文件》 8、1979年以来我国先后在深圳、珠海、汕头等地设立的经济特区属于（） A、综合型经济特区 B、自由边境区 C、过境区 D、科学工业园区 9、阐述协议国际分工理论的著作是（） A、《国富沦》 B、《对外贸易论》 C、《政治经济学的国民体系》 D、《就业、利息与货币通论》 24、日本教授小岛清在其著作__《对外贸易论》__中提出了协议国际分工理论。 10、歧视性政府采购一般是指政府优先购买（）。 A、外国产品 B、合资产品 C、名牌产品 D、本国产品 11、《北美自由贸易协定》正式生效的时间是（）。 A、1992年8月12日 B、1989年1月1日 C、1994年1月1日 D、1996年11月18日 12、承租人选定机器设备，由出租人购置后出租给承租人使用，承租人按期支付租金。这种租赁方式是（） 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};国际贸易全套练习题及答案(DOC)
数据结构与算法习题及答案
云计算期末考试试卷及答案.
国际贸易复习题及答案
数据结构与算法复习题10(C语言版)
云计算期末考试总结
国际贸易原理复习题开放本科含答案
云计算期末习题含答案
对外经贸大学国贸实务期末习题及答案
数据结构与算法习题及答案
云计算期末试题(整理,来自网络)
国际贸易学复习试题(含答案)
云计算期末考试试题和答案解析教学提纲
数据结构与算法复习题及参考答案
《国际贸易概论》练习题及完整答案
数据结构与算法分析习题与参考答案
- 【精选资料】北京交通大学数据结构与算法期末考试参考答案
- 数据结构与算法期末复习题
- 北京大学数据结构与算法2016-2017数据结构期末考试题试卷答案版
- 数据结构与算法期末考试复习试题
- 大数据结构与算法期末考试复习试题
- 数据结构与算法C语言版期末复习题
- 《数据结构与算法》期末试题试卷A
- 《数据结构与算法》期末考试题型
- 四川大学计算机学院数据结构与算法分析期末试题(2009级A)_无答案
- 数据结构与算法分析—期末复习题及答案
- 北京大学数据结构与算法北大2013数算期末考试题考试
- 数据结构和算法期末考试复习试题整理
- 2004级《算法与数据结构》期末试卷(A)及答案
- 数据结构与算法期末考试复习试题
- 数据结构期末复习
- 软件学院数据结构与算法分析期末试题(2006级B)
- 数据结构与算法期末考试复习试题
- 《数据结构与算法》期末考试试卷(B卷)
- 厦门大学大数据结构与算法(陈海山)期末习题问题详解解析汇报
- 北京交通大学数据结构与算法期末测验考试参考答案